Heltals överflöde

Ett heltalsspill är en  situation inom datoraritmetik där värdet som beräknats som ett resultat av en operation inte kan placeras i en n-bitars heltalsdatatyp. Skilj på överflöde genom representationens övre gräns och genom den nedre ( engelska Underflow ). 

Exempel: lägga till två 8 -bitars variabler och lagra resultatet i en variabel av samma storlek:

översvämning inträffar.

I det här fallet skrivs resultatet inte det förväntade utan . Det är värt att notera att beräkningen här ägde rum modulo 2 n , och modulo aritmetik är cyklisk, det vill säga 255+1=0 (för n = 8). Denna bräddningssituation fixas av datorn genom att sätta speciella bitar i registret för flaggorna Overflow and Carry (klausul 3.4.3.1 Kombinerad volym: Volym 1 [1] ). Vid programmering i assemblerspråk kan en sådan situation fastställas direkt, till exempel genom att manuellt kontrollera flaggregistrets tillstånd efter att operationen utförts (klausul 7.3.13.2 Kombinerad volym: Volym 1 [1] ).

Ursprunget till problemet

Bitdjupet för ett register bestämmer intervallet av data som kan representeras i det. Representationsintervall för heltalstyper i binära datorer:

Bithet 8 bitar 16 bitar 32 bitar 64 bitar
osignerad Räckvidd 0..2 8 −1 0..2 16 −1 0..2 32 −1 0..2 64 −1
Intervall (decimal) 0..255 0..65535 0..4294967295 0.. 18446744073709551615
Ikonisk Räckvidd -2 7 .. 2 7 −1 -2 15 .. 2 15 −1 -2 31 .. 2 31 −1 -2 63 .. 2 63 −1
Intervall (decimal) -128..127 -32768..32767 -2147483648.. 2147483647 -9223372036854775808.. 9223372036854775807

Ett spill kan uppstå i källkoden på grund av en programmerares fel eller bristande vaksamhet mot indata [2] .

Säkerhetsrisker _

Överflödesförmågan används i stor utsträckning av programmerare, till exempel för hash och kryptografi, generering av slumpmässiga tal och för att hitta gränser för en typrepresentation [4] . Samtidigt, till exempel, enligt standarden för C- och C++-språk , utförs osignerade beräkningar modulo 2, medan signerad overflow är ett klassiskt exempel [5] på odefinierat beteende [6] .

Denna typ av felaktigheter i koden leder till följande konsekvenser [4] :

  1. Sammanställningen kan gå oväntat. På grund av förekomsten av odefinierat beteende i ett program kan kompilatoroptimeringar ändra programmets beteende.
  2. Tidsinställd bomb. På den nuvarande versionen av operativsystemet, kompilator, kompileringsalternativ, strukturell organisation av programmet, etc., kan allt fungera, men med alla förändringar, till exempel utseendet på mer aggressiva optimeringar, kommer det att gå sönder.
  3. Illusion av förutsägbarhet. En speciell kompilatorkonfiguration kan ha mycket specifikt beteende, till exempel C- och C++-kompilatorer implementerar vanligtvis operationer modulo 2 n och för signerade typer (endast de som tolkas i tvåkomplement) om aggressiva optimeringar är inaktiverade. Men man kan inte hoppas på ett sådant beteende, annars finns det risk för effekten av en "tidsinställd bomb"
  4. Bildande av dialekter. Vissa kompilatorer tillhandahåller ytterligare alternativ för att utöka odefinierat beteende . Till exempel stöder både GCC och Clang alternativet -fwrapv, som ger det beteende som beskrivs ovan (i punkt 3).

Att ändra standarden kan leda till nya spillproblem. Till exempel var 1<<31 implementeringsberoende i ANSI C och C++98-standarderna, medan det blev odefinierat i C99 och C11 (för 32-bitars heltal). [fyra]

Det kan också finnas andra konsekvenser av ett sådant fel, till exempel ett buffertspill .

Exploatering och efterdyningar

Viktiga säkerhetskonsekvenser [7] :

Klassiskt sett kan ett spill utnyttjas via ett buffertspill.

img_t * table_ptr ; /*struct som innehåller img-data, 10kB vardera*/ int num_imgs ; ... num_imgs = get_num_imgs (); table_ptr = ( img_t * ) malloc ( sizeof ( img_t ) * num_imgs ); ...

Detta exempel [7] illustrerar flera sårbarheter samtidigt. För det första kommer för stora num_imgs att allokera en enorm buffert, vilket kan få programmet att förbruka alla systemresurser eller få det att krascha .

En annan sårbarhet är att om num_imgs är ännu större kommer det att svämma över malloc-argumentet. Då kommer endast en liten buffert att tilldelas. När du skriver till det kommer ett buffertspill att inträffa , vars konsekvenser kan vara: avlyssning av kontroll över exekvering, exekvering av angriparens kod, tillgång till viktig information. [åtta]

Undviker problemet

Skydd mot sådant beteende bör utföras på flera nivåer [7] :

  1. Programplanering och krav:
    • Se till att alla kommunikationsprotokoll mellan komponenter är strikt definierade. Inklusive att alla beräkningar utanför vyns gränser kommer att upptäckas. Och kräver strikt efterlevnad av dessa protokoll
    • Använd ett programmeringsspråk och en kompilator som inte tillåter denna sårbarhet att materialisera sig, antingen gör det lättare att upptäcka eller utför automatisk kontroll av gränser. Verktyg som tillhandahålls av kompilatorn inkluderar desinficeringsmedel (t.ex. Address Sanitizer eller Undefined Behavior Sanitizer).
  2. Programarkitekturer:
    • Använd beprövade bibliotek eller ramverk som hjälper dig att utföra beräkningar utan risk för oförutsägbara konsekvenser . Exempel inkluderar bibliotek som SafeInt (C++) eller IntegerLib (C eller C++).
    • Alla säkerhetskontroller på klientsidan bör dupliceras på serversidan för att förhindra CWE-602 . En angripare kan kringgå validering på klientsidan genom att själva ändra värdena omedelbart efter att ha godkänt valideringen, eller genom att modifiera klienten för att ta bort validering helt.
  3. Implementeringar:
    • Validera alla inkommande numeriska data för att säkerställa att de ligger inom det förväntade intervallet. Var noga med att kontrollera både lägsta tröskel och max. Använd osignerade nummer där det är möjligt. Detta gör det lättare att kontrollera efter spill.
    • Utforska alla nödvändiga nyanser av programmeringsspråket associerat med numerisk beräkning ( CWE-681 ). Hur de representeras, vilka är skillnaderna mellan signerad och osignerad , 32-bitars och 64-bitars , problem med casting (trimning, signerad-osignerad typ casting  - ovan) och hur siffror som är för små eller omvänt stora för deras maskinrepresentation bearbetas. Se också till att typen du använder (t.ex. int eller long) täcker det erforderliga representationsintervallet
    • Undersök kompilatorvarningar i detalj och lös eventuella säkerhetsproblem som operandtecken som inte matchar minnesoperationer eller användning av oinitierade variabler . Även om sårbarheten är mycket liten kan den leda till fara för hela systemet.

Andra regler för att undvika dessa sårbarheter publicerade i CERT C Secure Coding Standard 2008 inkluderar [9] :

  • Skriv eller använd inte stränginmatningshanteringsfunktioner om de inte hanterar alla fall
  • Använd inte bitoperationer på signerade typer
  • Utvärdera uttryck på en större typ innan du jämför eller tilldelar dem till en mindre
  • Var försiktig innan du kastar mellan en siffra och en pekare
  • Se till att moduloberäkningar eller divisionsresultat inte resulterar i efterföljande division med noll
  • Använd intmax_t eller uintmax_t för formaterad I/O av anpassade numeriska typer

Verkliga exempel

SPECCINT-studie

I artikeln [4] studeras ett av de mest använda och välkända testpaketen SPEC , som används för prestationsmätningar, i detalj, som ämne för att studera C- och C++-program för heltalsspill. Den består av fragment av de vanligaste uppgifterna, såsom: test av beräkningsmatematik, kompilering, arbete med databaser, disk, nätverk och så vidare.

Resultaten av SPECCINT2000-analysen visar närvaron av 219 statiska bräddkällor i 8 av 12 riktmärken, varav 148 använde osignerat spill och 71 använde signerat spill ( odefinierat beteende igen ). Samtidigt är osignerad overflow inte heller alltid avsiktlig och kan vara ett fel och en källa till sårbarhet (till exempel Listing 2 i samma artikel [4] ).

Testade även för "tidsbomber" i SPECCINT2006. Hans idé är att returnera ett slumpmässigt tal på varje plats av odefinierat beteende och se vilka konsekvenser detta kan leda till. Om vi ​​utvärderar odefinierat beteende ur C99 / C ++ 11-standardens synvinkel, kommer så många som 6 av 9 riktmärken att misslyckas i testet.

Exempel från andra programpaket

int addi ( int lhs , int rhs ) { errno = 0 ; if (((( lhs + rhs ) ^ lhs ) & (( lhs + rhs ) ^ rhs )) >> ( sizeof ( int ) * CHAR_BIT -1 )) { error_handler ( "ÖVERFLÖDE FEL" , NULL , EOVERFLOW ); errno = EINVAL ; } returnera lhs + rhs ; }

Denna kodbit [4] från IntegerLib-paketet kontrollerar om lhs och rhs kan läggas ihop utan översvämning. Och exakt i rad 3 kan detta överflöde uppstå (när man lägger till lhs + rhs). Detta är UB eftersom lhs och rhs är signerade typer. Dessutom hittades ytterligare 19 UB-spill i detta bibliotek.

Författarna rapporterade också 13 spill i SQLite, 43 i SafeInt, 6 i GNU MPC-biblioteket, 30 i PHP, 18 i Firefox, 71 i GCC, 29 i PostgreSQL, 5 i LLVM och 28 i Python. De flesta av felen korrigerades snart.

Andra exempel

Ett känt exempel på heltalsspill förekommer i spelet Pac-Man , precis som andra spel i serien: Ms. Pac-Man , Jr. Pac Man . Dessutom visas detta fel i Pac-Man Google Doodle som det så kallade "påskägget". [10] Här, på nivå 256, kan en " screen of death " observeras, och själva nivån kallas " delad skärmnivå ". Entusiaster har plockat isär källkoden i ett försök att fixa felet genom att modifiera spelet .

Samma problem fanns påstås i spelet Sid Meier's Civilization och är känt som Nuclear Gandhi [11] . Enligt legenden, vid någon tidpunkt i spelet med en mycket fredlig Gandhi, finns det ett överflöde genom 0 nivåer av fientlighet, vilket kan resultera i ett kärnvapenkrig med Gandhi. Faktum är att en sådan myt dök upp först när Civilization V släpptes, där parametern för hans artificiella intelligens , som reglerar skapandet och användningen av kärnvapen , har det högsta värdet på 12, vilket inte motsäger det faktum att Gandhi är en av de mest fredliga ledarna i spelet [12] .

Ett annat exempel är ett fel i SimCity 2000 [13] . Poängen här är att spelarens budget blev väldigt stor, och efter att ha gått igenom 2 31 blev den plötsligt negativ. Spelet slutar med förlust.

Detta fel kommer från Diablo III . På grund av en av ändringarna i patch 1.0.8 bröt spelets ekonomi samman. Det maximala beloppet för transaktioner höjdes från 1 miljon till 10 miljoner. Inköpskostnaden rann över genom 32-bitarstypen och när operationen avbröts återfördes hela beloppet. Det vill säga att spelaren förblev med en vinst på 2 32 spelvaluta [14]

Se även

Anteckningar

  1. ↑ 1 2 Handböcker för programvaruutvecklare för Intel® 64 och IA-32 Architectures | Intel®-  programvara . software.intel.com. Hämtad: 22 december 2017.
  2. ↑ x86 Exploitation 101: “Integer overflow” – lägger till ett till... aaaaaaaaaaaand det är borta  , gb_masters /dev/null  (12 augusti 2015). Hämtad 20 december 2017.
  3. ↑ Säkerhetskonsortiet för webbapplikationer/heltalsspill . projects.webappsec.org. Hämtad: 8 december 2017.
  4. ↑ 1 2 3 4 5 6 W. Dietz, P. Li, J. Regehr, V. Adve. Förstå heltalsspill i C/C #x002B; #x002B;  // 2012 34:e internationella konferensen om mjukvaruteknik (ICSE). - Juni 2012. - S. 760-770 . - doi : 10.1109/icse.2012.6227142 .
  5. ↑ CWE - 2011 CWE/SANS Topp 25 mest farliga programvarufel  . cwe.mitre.org. Hämtad: 21 december 2017.
  6. ↑ ISO/IEC 9899 : 2011 - Informationsteknologi - Programmeringsspråk -  C. www.iso.org. Hämtad: 21 december 2017.
  7. ↑ 1 2 3 CWE-190: Heltalsspill eller omslutande (3.0  ) . cwe.mitre.org. Hämtad: 12 december 2017.
  8. ↑ CWE-119: Felaktig begränsning av operationer inom gränserna för en minnesbuffert (3.0  ) . cwe.mitre.org. Hämtad: 12 december 2017.
  9. ↑ CWE-738: CERT C Secure Coding (2008 version) Avsnitt 04 - Heltal (INT) (3.0  ) . cwe.mitre.org. Hämtad: 15 december 2017.
  10. ↑ Karta 256 Glitch  , Pac - Man Wiki . Hämtad 12 december 2017.
  11. ↑ Nuclear Gandhi , Know Your Meme . Hämtad 15 december 2017.
  12. ↑ Artemy Leonov. Varför Civilizations "Nuclear Gandhi" Bug Story sannolikt är påhittad . DTF (5 september 2019). Tillträdesdatum: 24 oktober 2020.
  13. ↑ Sim City 2000 heltalsspill . Blake O\'Hare. Hämtad: 12 december 2017.
  14. ↑ Diablo III-ekonomin bruten av ett heltalsöverskottsfel  , minimaxir | Max Woolfs blogg . Hämtad 12 december 2017.