Heltalsoverløb

Et heltalsoverløb er en situation i computeraritmetik, hvor værdien beregnet som et resultat af en operation ikke kan placeres i en n-bit heltalsdatatype. Skelne mellem overløb gennem repræsentationens øvre grænse og gennem den nederste ( engelsk Underflow ).

Eksempel: tilføjelse af to 8 -bit variabler og lagring af resultatet i en variabel af samme størrelse:

$210_{10}+61_{10}=11010010_{2}+00111101_{2}=?$

${\begin{array}{c}{\begin{array}{cc}+&{\begin{array}{c}11010010_{2}\\00111101_{2}\end{array))\\ \end{array}}\\\hline {\begin{array}{cc}&{\color {Red}1}00001111_{2}\end{array}}\end{array}}$

overløb opstår.

I dette tilfælde skrives resultatet ikke det forventede , men . Det er værd at bemærke, at beregningen her fandt sted modulo 2 n , og modulo aritmetik er cyklisk, det vil sige 255+1=0 (for n = 8). Denne overløbssituation korrigeres af computeren ved at indstille specielle bits i registret for flagene Overflow og Carry (klausul 3.4.3.1 Kombineret volumen: bind 1 [1] ). Ved programmering i assemblersprog kan en sådan situation etableres direkte, for eksempel ved manuelt at kontrollere flagregisterets tilstand efter operationen er udført (klausul 7.3.13.2 Kombineret volumen: bind 1 [1] ). ${\displaystyle 271_{10}={\color {Red}1}00001111_{2))$ ${\displaystyle 15_{10}=00001111_{2))$

Oprindelsen af problemet

Bitdybden af et register bestemmer rækkevidden af data, der kan repræsenteres i det. Repræsentationsintervaller for heltalstyper i binære computere:

Bithed		8 bit	16 bit	32 bit	64 bit
usigneret	Rækkevidde	0..2 8 −1	0..2 16 −1	0..2 32 −1	0..2 64 −1
usigneret	Interval (decimal)	0..255	0..65535	0..4294967295	0.. 18446744073709551615
ikonisk	Rækkevidde	-2 7 .. 2 7 −1	-2 15 .. 2 15 −1	-2 31 .. 2 31 −1	-2 63 .. 2 63 −1
ikonisk	Interval (decimal)	-128..127	-32768..32767	-2147483648.. 2147483647	-9223372036854775808.. 9223372036854775807

Et overløb kan forekomme i kildekoden på grund af en programmørs fejl eller manglende årvågenhed over for inputdata [2] .

Underskrevet og usigneret uoverensstemmelse . Hvis tallene er repræsenteret på computeren i en ekstra kode, svarer forskellige tal til én bitstrøm. I 32-bit aritmetik svarer fortegn -1 til ufortegn 4294967295 (den øvre grænse for repræsentationen). Det vil sige, at støbning af en type til en anden kan resultere i en væsentlig forskel i betydning. Denne type fejl er ofte resultatet af en signedness-fejl ( og ), dvs. en forkert typecast mellem typer med forskellige fortegn.
Skære problem. Opstår, når et tal fortolkes som et heltal af mindre længde. I dette tilfælde vil kun de mindst signifikante bits forblive i tallet. Seniorer vil blive kasseret, hvilket vil medføre en ændring i den numeriske værdi
Skilteudvidelse. Det er værd at huske på, at når man støber et fortegnet tal til en type af større længde, kopieres den mest signifikante bit, hvilket, hvis det tolkes som usigneret, vil føre til et meget stort tal [3]

Sikkerhedsrisici redigér

Overløbsevnen bruges i vid udstrækning af programmører, for eksempel til hashing og kryptografi, generering af tilfældige tal og til at finde grænser for en typerepræsentation [4] . Samtidig udføres for eksempel i henhold til standarden for C og C++ sprog modulo 2 usignerede beregninger, mens signed overflow er et klassisk eksempel [5] på udefineret adfærd [6] .

Denne form for ukorrekthed i koden fører til følgende konsekvenser [4] :

Kompileringen kan gå uventet. På grund af tilstedeværelsen af udefineret adfærd i et program, kan compiler-optimeringer ændre programmets adfærd.
Tidsindstillet bombe. På den nuværende version af operativsystemet, compiler, kompileringsmuligheder, strukturel organisering af programmet osv., kan alt fungere, men med enhver ændring, for eksempel udseendet af mere aggressive optimeringer, vil det bryde.
Illusion om forudsigelighed. En bestemt compilerkonfiguration kan have meget specifik adfærd, for eksempel implementerer C- og C++-compilatorer typisk operationer modulo 2 n og for signerede typer (kun dem, der fortolkes i to's komplement), hvis aggressive optimeringer er deaktiveret. Man kan dog ikke håbe på en sådan adfærd, ellers er der risiko for effekten af en "tidsindstillet bombe"
Dannelse af dialekter. Nogle compilere giver yderligere muligheder for at udvide udefineret adfærd . For eksempel understøtter både GCC og Clang indstillingen -fwrapv, som giver den adfærd, der er beskrevet ovenfor (i punkt 3).

Ændring af standarden kan medføre nye overløbsproblemer. For eksempel var 1<<31 implementeringsafhængig i ANSI C og C++98 standarderne, mens den blev udefineret i C99 og C11 (for 32-bit heltal). [fire]

Der kan også være andre konsekvenser af en sådan fejl, for eksempel et bufferoverløb .

Udnyttelse og eftervirkninger

Vigtige sikkerhedsimplikationer [7] :

For tilgængelighed . Mulig systemfejl (vindue til DoS-angreb )
For integritet . Uautoriseret adgang til data
For privatlivets fred . Udførelse af tredjepartskode, der omgår beskyttelsesmekanismen

Klassisk kan et overløb udnyttes via et bufferoverløb.

img_t * table_ptr ; /*struct indeholdende img-data, 10kB hver*/ int num_imgs ; ... num_imgs = get_num_imgs (); table_ptr = ( img_t * ) malloc ( sizeof ( img_t ) * num_imgs ); ...

Dette eksempel [7] illustrerer flere sårbarheder på én gang. For det første vil for store num_imgs allokere en enorm buffer, som kan få programmet til at forbruge alle systemressourcer eller få det til at gå ned .

En anden sårbarhed er, at hvis num_imgs er endnu større, vil det flyde over malloc-argumentet. Så vil der kun blive tildelt en lille buffer. Når du skriver til det, vil der opstå et bufferoverløb , hvis konsekvenser kan være: aflytning af kontrol over udførelsen, udførelse af angriberens kode, adgang til vigtig information. [otte]

Undgå problemet

Beskyttelse mod sådan adfærd bør udføres på flere niveauer [7] :

Programplanlægning og krav:
- Sørg for, at alle kommunikationsprotokoller mellem komponenter er nøje defineret. Herunder at alle beregninger uden for visningens grænser vil blive opdaget. Og kræver streng overholdelse af disse protokoller
- Brug et programmeringssprog og compiler , der ikke tillader denne sårbarhed at materialisere sig, enten gør det lettere at opdage eller udfører automatisk kontrol af grænser. Værktøjer leveret af compileren inkluderer desinfektionsmidler (f.eks. Address Sanitizer eller Undefined Behavior Sanitizer).
Programarkitekturer:
- Brug dokumenterede biblioteker eller rammer , der hjælper dig med at udføre beregninger uden risiko for uforudsigelige konsekvenser . Eksempler omfatter biblioteker såsom SafeInt (C++) eller IntegerLib (C eller C++).
- Eventuelle sikkerhedstjek på klientsiden bør duplikeres på serversiden for at forhindre CWE-602 . En angriber kan omgå validering på klientsiden ved selv at ændre værdierne umiddelbart efter at have bestået validering, eller ved at ændre klienten for at fjerne validering helt.
Implementeringer:
- Valider alle indkommende numeriske data for at sikre, at de er inden for det forventede interval. Sørg for at kontrollere både minimumstærsklen og maksimum. Brug usignerede numre, hvor det er muligt. Dette vil gøre det nemmere at kontrollere for overløb.
- Udforsk alle de nødvendige nuancer af programmeringssproget forbundet med numerisk databehandling ( CWE-681 ). Hvordan de er repræsenteret, hvad er forskellene mellem signeret og usigneret , 32-bit og 64-bit , problemer med casting (trimning, signed-unsigned type casting - ovenfor), og hvordan tal, der er for små eller omvendt store til deres maskinrepræsentation behandles. Sørg også for, at den type du bruger (f.eks. int eller long) dækker det påkrævede repræsentationsområde
- Undersøg kompileringsadvarsler i detaljer og løs mulige sikkerhedsproblemer såsom uoverensstemmelser mellem operandtegn i hukommelsesoperationer eller brug af uinitialiserede variabler . Selvom sårbarheden er meget lille, kan den føre til fare for hele systemet.

Andre regler for at undgå disse sårbarheder offentliggjort i CERT C Secure Coding Standard i 2008 omfatter [9] :

Skriv eller brug ikke strenginputhåndteringsfunktioner, medmindre de håndterer alle sager
Brug ikke bit-operationer på signerede typer
Evaluer udtryk på en større type, før du sammenligner eller tildeler dem til en mindre
Vær forsigtig, før du kaster mellem et tal og en pointer
Sørg for, at modulo-beregninger eller divisionsresultater ikke resulterer i efterfølgende division med nul
Brug intmax_t eller uintmax_t til formateret I/O af brugerdefinerede numeriske typer

Eksempler fra det virkelige liv

SPECCINT undersøgelse

I artiklen [4] , som emnet for at studere C- og C++-programmer til heltalsoverløb, studeres en af de mest udbredte og velkendte testpakker SPEC , der bruges til præstationsmålinger, i detaljer. Den består af fragmenter af de mest almindelige opgaver, såsom: test af beregningsmatematik, kompilering, arbejde med databaser, disk, netværk og så videre.

Resultaterne af SPECCINT2000-analysen viser tilstedeværelsen af 219 statiske kilder til overløb i 8 ud af 12 benchmarks, hvoraf 148 brugte usigneret overløb og 71 brugte signeret overløb ( udefineret adfærd igen ). Samtidig er usigneret overløb heller ikke altid tilsigtet og kan være en fejl og en kilde til sårbarhed (f.eks. liste 2 i samme artikel [4] ).

Også testet for "tidsindstillede bomber" i SPECCINT2006. Hans idé er at returnere et tilfældigt tal på hvert sted med udefineret adfærd og se, hvilke konsekvenser dette kan føre til. Hvis vi vurderer udefineret adfærd ud fra C99 / C ++ 11-standardens synspunkt, vil så mange som 6 ud af 9 benchmarks fejle testen.

Eksempler fra andre softwarepakker

int addi ( int lhs , int rhs ) { errno = 0 ; if (((( lhs + rhs ) ^ lhs ) & (( lhs + rhs ) ^ rhs )) >> ( sizeof ( int ) * CHAR_BIT -1 )) { error_handler ( "OVERFLØD FEJL" , NULL , EOVERFLØD ); errno = EINVAL ; } retur lhs + rhs ; }

Dette stykke kode [4] fra IntegerLib-pakken tjekker, om lhs og rhs kan lægges sammen uden overløb. Og præcis i linje 3 kan dette overløb opstå (ved tilføjelse af lhs + rhs). Dette er UB, fordi lhs og rhs er signerede typer. Derudover blev der fundet 19 flere UB-overløb i dette bibliotek.

Forfatterne rapporterede også 13 overløb 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 og 28 i Python. De fleste af fejlene blev snart rettet.

Andre eksempler

Et berømt eksempel på heltalsoverløb forekommer i spillet Pac-Man , ligesom andre spil i serien: Ms. Pac-Man , Jr. Pac Man . Denne fejl optræder også i Pac-Man Google Doodle som det såkaldte "Easter Egg". [10] Her, på niveau 256, kan en " skærm af død " observeres, og selve niveauet kaldes " delt skærmniveau ". Entusiaster har adskilt kildekoden i et forsøg på at rette fejlen ved at modificere spillet .

Det samme problem var angiveligt i spillet Sid Meier's Civilization og er kendt som Nuclear Gandhi [11] . Ifølge legenden er der på et tidspunkt i spillet med en meget fredelig Gandhi et overløb gennem 0 niveauer af fjendtlighed, hvilket kan resultere i en atomkrig med Gandhi. Faktisk dukkede en sådan myte kun op med udgivelsen af Civilization V , hvor parameteren for hans kunstige intelligens , som regulerer skabelsen og brugen af atomvåben , har den højeste værdi på 12, hvilket ikke modsiger det faktum, at Gandhi er en af de mest fredelige ledere i spillet [12] .

Et andet eksempel er en fejl i SimCity 2000 [13] . Pointen her er, at spillerens budget blev meget stort, og efter at have været igennem 2 31 blev det pludselig negativt. Spillet ender med nederlag.

Denne fejl er fra Diablo III . På grund af en af ændringerne i patch 1.0.8 brød spillets økonomi sammen. Det maksimale beløb for transaktioner blev forhøjet fra 1 mio. til 10 mio.. Købsomkostningerne løb over 32-bit-typen, og da operationen blev annulleret, blev det fulde beløb returneret. Det vil sige, at spilleren forblev med et overskud på 2 32 spilvaluta [14]

Se også

Noter

↑ 1 2 Manualer til softwareudviklere til Intel® 64 og IA-32 Architectures | Intel®- software . software.intel.com. Hentet: 22. december 2017.
↑ x86 Udnyttelse 101: “Integer overflow” – tilføjer en mere... aaaaaaaaaaand det er væk , gb_master 's /dev/null (12. august 2015). Hentet 20. december 2017.
↑ Webapplikationssikkerhedskonsortiet/heltalsoverløb . projects.webappsec.org. Hentet: 8. december 2017. (ubestemt)
↑ 1 2 3 4 5 6 W. Dietz, P. Li, J. Regehr, V. Adve. Forstå heltalsoverløb i C/C #x002B; #x002B; // 2012 34th International Conference on Software Engineering (ICSE). - juni 2012. - S. 760-770 . - doi : 10.1109/icse.2012.6227142 .
↑ CWE - 2011 CWE/SANS Top 25 mest farlige softwarefejl . cwe.mitre.org. Hentet: 21. december 2017.
↑ ISO/IEC 9899 : 2011 - Informationsteknologi - Programmeringssprog - C. www.iso.org. Hentet: 21. december 2017.
↑ 1 2 3 CWE-190: Integer Overflow eller Wraparound (3.0 ) . cwe.mitre.org. Hentet: 12. december 2017.
↑ CWE-119: Ukorrekt begrænsning af operationer inden for grænserne af en hukommelsesbuffer (3.0 ) . cwe.mitre.org. Hentet: 12. december 2017.
↑ CWE-738: CERT C Secure Coding (2008-version) Sektion 04 - Heltal (INT) (3.0 ) . cwe.mitre.org. Hentet: 15. december 2017.
↑ Kort 256 Glitch , Pac - Man Wiki . Hentet 12. december 2017.
↑ Nuclear Gandhi , Know Your Meme . Hentet 15. december 2017.
↑ Artemy Leonov. Hvorfor Civilizations "Nuclear Gandhi"-fejlhistorie sandsynligvis er opfundet . DTF (5. september 2019). Dato for adgang: 24. oktober 2020. (ubestemt)
↑ Sim City 2000 heltalsoverløb . Blake O\'Hare. Hentet: 12. december 2017. (ubestemt)
↑ Diablo III-økonomi brudt af en heltalsoverløbsfejl , minimaxir | Max Woolfs blog . Hentet 12. december 2017.