Heltal overløb - Integer overflow

Heltalsoverløb kan demonstreres gennem et kilometertæller, der overfylder, en mekanisk version af fænomenet. Alle cifre er indstillet til maksimum 9, og den næste stigning i det hvide ciffer får en kaskade af overførselstilføjelser til at sætte alle cifre til 0, men der er ikke noget højere ciffer (1.000.000 s ciffer) til at ændre sig til et 1, så tælleren nulstilles til nul. Dette er indpakning i modsætning til mætning .

I computerprogrammering sker der et heltalsoverløb , når en aritmetisk handling forsøger at oprette en numerisk værdi, der ligger uden for det område, der kan repræsenteres med et givet antal cifre - enten højere end maksimum eller lavere end den mindste repræsentative værdi.

Det mest almindelige resultat af et overløb er, at de mindst betydningsfulde cifre i resultatet lagres; resultatet siges at vikle omkring maksimum (dvs. modulo en effekt af radix , normalt to i moderne computere, men nogle gange ti eller en anden radix).

En overløbstilstand kan give resultater, der fører til utilsigtet adfærd. Især hvis muligheden ikke er forudset, kan overløb kompromittere et programs pålidelighed og sikkerhed .

For nogle applikationer, såsom timere og ure, kan indpakning på overløb være ønskeligt. De C11 standard hedder, at for unsigned heltal modulo indpakning er den definerede adfærd og udtrykket overløb gælder aldrig: "en beregning, der involverer usignerede operander kan aldrig overflow"

På nogle processorer som grafikprocessorenheder (GPU'er) og digitale signalprocessorer (DSP'er), der understøtter metningsmæssig aritmetik , ville overfyldte resultater blive "fastspændt", det vil sige indstillet til minimums- eller maksimumværdien i det repræsentative område, snarere end viklet rundt.

Oprindelse

Den register bredde af en processor bestemmer række værdier, der kan repræsenteres i sine registre. Selvom langt de fleste computere kan udføre regning med flere præcisioner på operander i hukommelsen, så numre kan være vilkårligt lange og overløb undgås, begrænser registerbredden størrelserne på tal, der kan betjenes (f.eks. Tilføjes eller trækkes fra) ved hjælp af en enkelt instruktion pr. operation. Typiske binære registerbredder for usignerede heltal omfatter:

• 4 bit: maksimal repræsentabel værdi 2 ⁴ - 1 = 15
• 8 bits: maksimal repræsentabel værdi 2 ⁸ - 1 = 255
• 16 bits: maksimal repræsentabel værdi 2 ¹⁶ - 1 = 65.535
• 32 bit: maksimal repræsentabel værdi 2 ³² - 1 = 4.294.967.295 (den mest almindelige bredde for personlige computere fra 2005),
• 64 bits: maksimal repræsenterbare værdi 2 ⁶⁴ - 1 = 18,446,744,073,709,551,615 (den mest almindelige bredde til personlige computer CPU'er , som af 2017),
• 128 bits: maksimal repræsenterbare værdi 2 ¹²⁸ - 1 = 340.282.366.920.938.463.463.374.607.431.768.211.455

Når en aritmetisk operation producerer et resultat, der er større end maksimum ovenfor for et N-bit heltal, reducerer et overløb resultatet til modulo N-th effekt på 2, idet det kun bevarer de mindst signifikante bits af resultatet og effektivt forårsager en omvikling .

Især kan multiplikation eller tilføjelse af to heltal resultere i en værdi, der er uventet lille, og at trække fra et lille heltal kan forårsage en omvikling til en stor positiv værdi (f.eks. 8-bit heltalstilsætning 255 + 2 resulterer i 1, hvilket er 257 mod 2 ⁸ , og på samme måde subtraktion 0 - 1 resulterer i 255, en tos komplement repræsentation af −1).

En sådan omslutning kan forårsage sikkerhedsskader - hvis en overfyldt værdi bruges som antallet af bytes, der skal allokeres til en buffer, tildeles bufferen uventet lille, hvilket potentielt kan føre til et bufferoverløb, der afhængigt af bufferen kan vende årsag udførelse af vilkårlig kode.

Hvis variablen har en signeret heltalstype , kan et program antage, at en variabel altid indeholder en positiv værdi. Et heltalsoverløb kan få værdien til at vikle sig og blive negativ, hvilket krænker programmets antagelse og kan føre til uventet adfærd (for eksempel resulterer 8-bit heltalstilsætning af 127 + 1 i −128, en tos komplement på 128). (En løsning på dette særlige problem er at bruge usignerede heltalstyper til værdier, som et program forventer og antager aldrig vil være negative.)

Flag

De fleste computere har to dedikerede processorflag til at kontrollere for overløbsforhold.

Den bære flaget er sat, når resultatet af en addition eller subtraktion, overvejer de operander og resultatet som usigneret tal, der ikke passer i den givne antal bits. Dette indikerer et overløb med en carry eller lån fra den mest betydningsfulde bit . En umiddelbart efterfølgende tilføjelse med carry eller subtract med låneoperation ville bruge indholdet af dette flag til at ændre et register eller en hukommelsesplacering, der indeholder den højere del af en værdi med flere ord.

Den overflow flaget er sat, når resultatet af en operation på underskrevne tal ikke har tegn på, at man ville forudsige fra tegnene på de operander, for eksempel et negativt resultat, når du tilføjer to positive tal. Dette indikerer, at der er sket et overløb, og det underskrevne resultat repræsenteret i tos komplementform ville ikke passe i det givne antal bits.

Definitionsvariationer og tvetydighed

For en usigneret type, når det ideelle resultat af en operation ligger uden for typens repræsentative område, og det returnerede resultat opnås ved indpakning, defineres denne hændelse almindeligvis som et overløb. I modsætning hertil definerer C11 -standarden, at denne hændelse ikke er et overløb og siger "en beregning, der involverer usignerede operander, kan aldrig flyde over."

Når det ideelle resultat af en heltalsoperation ligger uden for typens repræsentative område, og det returnerede resultat opnås ved fastspænding, defineres denne hændelse almindeligvis som en mætning. Anvendelsen varierer, om en mætning er et overløb eller ej. For at fjerne tvetydighed kan udtrykkene wrapping overflow og saturating overflow bruges.

Udtrykket underflow bruges mest til floating-point matematik og ikke til heltals matematik. Men der kan findes mange referencer til heltal underflow. Når udtrykket heltal underflow bruges, betyder det, at det ideelle resultat var tættere på minus uendelig end outputtypens repræsentative værdi tættest på minus uendeligt. Når udtrykket heltal underflow bruges, kan definitionen af ​​overløb omfatte alle typer overløb, eller det kan kun omfatte tilfælde, hvor det ideelle resultat var tættere på positiv uendelighed end outputtypens repræsentative værdi, der er tættest på positiv uendelighed.

Når det ideelle resultat af en operation ikke er et eksakt heltal, kan betydningen af ​​overløb være tvetydig i kanttilfælde. Overvej det tilfælde, hvor det ideelle resultat har værdien 127,25, og outputtypens maksimale repræsentative værdi er 127. Hvis overløb er defineret som den ideelle værdi, der ligger uden for outputtypens repræsentative område, vil denne sag blive klassificeret som et overløb. For operationer, der har en veldefineret afrundingsadfærd, skal overløbsklassificering muligvis udskydes til efter afrunding. C11 -standarden definerer, at konverteringer fra flydende punkt til heltal skal runde mod nul. Hvis C bruges til at konvertere floating point -værdien 127,25 til et helt tal, skal afrunding først anvendes for at give et ideelt heltal output på 127. Da det afrundede heltal er i outputområdet, ville C -standarden ikke klassificere denne konvertering som et overløb .

Inkonsekvent adfærd

Det er værd at bemærke, at adfærden ved forekomst af overløb muligvis ikke er konsistent under alle omstændigheder. I Rust programmeringssprog for eksempel, mens funktionalitet er forudsat at give brugerne valg og kontrol, den adfærd til grundlæggende brug af matematiske operatorer er naturligt fast; denne faste adfærd adskiller sig imidlertid mellem et program, der er bygget i 'debug' -tilstand og en indbygget' release '-tilstand. I C er usigneret heltalsoverløb defineret til at vikle rundt, mens underskrevet heltalsoverløb forårsager udefineret adfærd .

Metoder til at løse problemer med heltaloverløb

Opdagelse

Run-time overløbsdetekteringsimplementering UBSaner tilgængelig for C-kompilatorer .

I Java 8 er der overbelastede metoder , f.eks. Lignende Math.addExact(int, int), som kaster ArithmeticExceptioni tilfælde af overløb.

Computer-beredskabsteam (CERT) udviklede As-if Infinitely Ranged (AIR) heltalsmodellen, en stort set automatiseret mekanisme til at eliminere heltalsoverløb og afkortning i C/C ++ ved hjælp af fejlhåndtering i løbetid.

Undgåelse

Ved at allokere variabler med datatyper, der er store nok til at indeholde alle værdier, der muligvis kan beregnes og lagres i dem, er det altid muligt at undgå overløb. Selv når den ledige plads eller de faste datatyper, der leveres af et programmeringssprog eller miljø, er for begrænsede til at tillade variabler defensivt at blive tildelt med generøse størrelser, ved omhyggeligt at bestille operationer og kontrollere operander på forhånd, er det ofte muligt at sikre på forhånd at resultatet aldrig bliver større end det kan gemmes. Statiske analyseværktøjer , formel verifikation og design ved kontraktteknikker kan bruges til mere sikkert og robust at sikre, at der ikke kommer et overløb ved et uheld.

Håndtering

Hvis det forventes, at overløb kan forekomme, kan der indsættes tests i programmet for at opdage, hvornår det sker, eller er ved at ske, og foretage anden behandling for at afbøde det. For eksempel, hvis et vigtigt resultat beregnet ud fra brugerinput overløber, kan programmet stoppe, afvise input og måske bede brugeren om forskellige input, i stedet for at programmet fortsætter med den ugyldige overfyldte input og sandsynligvis ikke fungerer korrekt som en konsekvens. Denne fulde proces kan automatiseres: det er muligt automatisk at syntetisere en handler for et heltalsoverløb, hvor handleren f.eks. Er en ren afslutning.

CPU'er har generelt en måde at registrere dette til at understøtte tilføjelse af tal større end deres registerstørrelse, typisk ved hjælp af en statusbit; teknikken kaldes multi-precision aritmetik. Det er således muligt at tilføje to tal hver to byte bred ved hjælp af kun en byte -tilføjelse i trin: tilføj først de lave bytes, derefter tilføj de høje bytes, men hvis det er nødvendigt at udføre de lave bytes, er dette aritmetisk overløb af byte -tilføjelse, og det bliver nødvendigt at registrere og øge summen af ​​de høje bytes.

Håndtering af mulig overløb af en beregning kan undertiden give et valg mellem at udføre en kontrol før den faktiske beregning (for at afgøre, om overløb kommer til at forekomme eller ej), eller efter det (for at overveje, om det sandsynligvis er sket baseret på den resulterende værdi) . Der skal udvises forsigtighed over for sidstnævnte valg. For det første, da det måske ikke er en pålidelig detektionsmetode (for eksempel kan en tilføjelse ikke nødvendigvis vikle til en lavere værdi). For det andet fordi forekomsten af ​​overløb i sig selv i nogle tilfælde kan være en udefineret adfærd . I programmeringssproget C resulterer overløb af usignerede heltalstyper i indpakning, men overløb af signerede heltalstyper er udefineret adfærd; følgelig kan en C -kompilator frit antage, at programmøren har sikret, at underskrevet overløb umuligt kan forekomme, og dermed kan den lydløst optimere enhver kontrol efter beregningen, der indebærer at kontrollere resultatet for at registrere det uden at give programmereren nogen advarsel om, at dette har været Færdig. Det er derfor tilrådeligt altid at foretrække at gennemføre kontroller før beregninger ikke efter dem.

Eksplicit udbredelse

hvis en værdi er for stor til at blive gemt, kan den tildeles en særlig værdi, der angiver, at der er sket overløb, og derefter få alle successive operationer til at returnere denne flagværdi. Sådanne værdier omtales undertiden som NaN for "ikke et tal". Dette er nyttigt, så problemet kan kontrolleres en gang i slutningen af ​​en lang beregning frem for efter hvert trin. Dette understøttes ofte i floating point hardware kaldet FPU'er .

Understøttelse af programmeringssprog

Programmeringssprog implementerer forskellige afbødningsmetoder mod et utilsigtet overløb: Ada , Seed7 (og visse varianter af funktionelle sprog) udløser en undtagelsestilstand ved overløb, mens Python (siden 2.4) problemfrit konverterer intern repræsentation af nummeret til at matche dets vækst og til sidst repræsenterer det som long- hvis evne kun er begrænset af den tilgængelige hukommelse.

På sprog med indbygget understøttelse af Aritmetik med vilkårlig præcision og typesikkerhed (f.eks. Python , Smalltalk eller Common Lisp ) promoveres numre automatisk til en større størrelse, når der forekommer overløb, eller der kastes undtagelser (betingelser signaleres), når der er en rækkegrænse. Brug af sådanne sprog kan derfor være en hjælp til at afhjælpe dette problem. På nogle sådanne sprog er der dog stadig situationer, hvor der kan forekomme et heltaloverløb. Et eksempel er eksplicit optimering af en kodesti, der betragtes som en flaskehals af profilen. I tilfælde af Common Lisp er dette muligt ved at bruge en eksplicit erklæring til at skrive-annotere en variabel til et maskinstørrelsesord (fixnum) og sænke typesikkerhedsniveauet til nul for en bestemt kodeblok.

I skarp kontrast til ældre sprog som C, giver nogle nyere sprog, f.eks. Rust , indbygget funktionalitet, der gør det let at opdage og vælge bruger over, hvordan overløb skal håndteres fra sag til sag. I Rust, mens brug af grundlæggende matematiske operatorer naturligvis mangler en sådan fleksibilitet, kan brugerne alternativt udføre beregninger via et sæt metoder leveret af hver af de heltals primitive typer. Disse metoder giver brugerne flere valgmuligheder mellem at udføre en 'kontrolleret' (eller 'overfyldt') operation (hvilket angiver, om overløb skete via returtypen eller ej); en 'ukontrolleret' operation en operation, der udfører indpakning, eller en handling, der udfører mætning ved de numeriske grænser.

Mættet regning

I computergrafik eller signalbehandling er det typisk at arbejde på data, der spænder fra 0 til 1 eller fra -1 til 1. Tag f.eks. Et gråtonebillede, hvor 0 repræsenterer sort, 1 repræsenterer hvid, og værdierne imellem repræsenterer gråtoner. En handling, som man måske vil støtte, er at lysne billedet op ved at gange hver pixel med en konstant. Mættet regning gør, at man bare blindt kan multiplicere hver pixel med den konstante uden at bekymre sig om overløb ved blot at holde sig til et rimeligt resultat, at alle disse pixels større end 1 (dvs. "lysere end hvid" ) bare bliver hvide og alle værdier "mørkere end sort" "Bliv bare sort.

Eksempler

Uventet aritmetisk overløb er en temmelig almindelig årsag til programfejl . Sådanne overløbsfejl kan være svære at opdage og diagnosticere, fordi de kun kan manifestere sig for meget store inputdatasæt, som er mindre tilbøjelige til at blive brugt i valideringstest.

At tage det aritmetiske middelværdi af to tal ved at tilføje dem og dividere med to, som det gøres i mange søgealgoritmer , forårsager fejl, hvis summen (dog ikke det resulterende middel) er for stor til at blive repræsenteret og derfor overløber.

Et uhåndteret aritmetisk overløb i motorstyringssoftwaren var den primære årsag til styrtet i 1996 -jomfruturen i Ariane 5 -raketten. Softwaren var blevet betragtet som fejlfri, da den var blevet brugt i mange tidligere flyvninger, men de brugte mindre raketter, der genererede lavere acceleration end Ariane 5. Frustrerende nok var den del af softwaren, hvor overløbsfejlen opstod, ikke engang nødvendig løb for Ariane 5 på det tidspunkt, hvor det fik raketten til at mislykkes-det var en lanceringsregimeproces for en mindre forgænger af Ariane 5, der var blevet tilbage i softwaren, da den blev tilpasset til den nye raket. Desuden var den faktiske årsag til fejlen en fejl i den tekniske specifikation for, hvordan softwaren håndterede overløbet, da den blev opdaget: den foretog en diagnostisk dump til sin bus, som ville have været forbundet til testudstyr under softwaretest under udvikling men var forbundet til raketstyringsmotorerne under flyvningen; datadumpen drev motordysen hårdt til den ene side, hvilket satte raketten ud af aerodynamisk kontrol og udløste dens hurtige opbrud i luften.

Den 30. april 2015 meddelte den amerikanske føderale luftfartsmyndighed, at den vil pålægge Boeing 787 -operatører at nulstille sit elektriske system med jævne mellemrum for at undgå et heltaloverløb, der kan føre til tab af elektrisk strøm og udsendelse af luftturbiner , og Boeing implementerede en softwareopdatering i fjerde kvartal. Det Europæiske Luftfartssikkerhedsagentur fulgte den 4. maj 2015. Fejlen sker efter 2³¹ centisekunder (248,55134814815 dage), hvilket angiver et 32-bit signeret heltal .

Overflow -fejl er tydelige i nogle computerspil. I arkadespillet Donkey Kong er det umuligt at komme videre forbi niveau 22 på grund af et heltalsoverløb i sin tid/bonus. Spillet tager niveauet, en bruger er på, multiplicerer det med 10 og tilføjer 40. Når de når niveau 22, er tid/bonusnummeret 260, hvilket er for stort til dets 8-bit 256 værdiregister, så det nulstiller sig selv til 0 og giver de resterende 4 som tid/bonus - for kort til at afslutte niveauet. I Donkey Kong Jr. Math , når det forsøger at beregne et tal over 10.000, viser det kun de første 4 cifre. Overflow er årsagen til det berømte "split-screen" niveau i Pac-Man . Den berygtede Nuclear Gandhi -fejl i civilisationen blev angiveligt forårsaget af et helt tal underflow, der opstod, da spillet forsøgte at trække 2 fra Gandhis standardaggressionsniveau på 1 og satte det til 255, næsten 26 gange højere end det normale maksimum på 10. ( Sid Meier hævdede i et interview, at dette faktisk var forsætligt.) En sådan fejl forårsagede også "Far Lands" i Minecraft, der eksisterede fra Infdev -udviklingsperioden til Beta 1.7.3; det blev senere rettet i Beta 1.8, men findes stadig i Pocket Edition og Windows 10 Edition versioner af Minecraft . I Super NES -spillet Lamborghini American Challenge kan spilleren få deres pengebeløb til at falde under $ 0 i løbet af et løb ved at blive idømt en bøde over grænsen for resterende penge efter at have betalt gebyret for et løb, som fejler heltalet og giver spilleren $ 65.535.000 mere end det ville have haft efter at være gået negativt. En lignende fejl opstår i STALKER: Clear Sky, hvor spilleren kan falde til et negativt beløb ved hurtigt at rejse uden tilstrækkelige midler og derefter fortsætte til den begivenhed, hvor spilleren bliver stjålet og får fjernet al deres valuta. Efter at spillet har forsøgt at tage spillerens penge væk til et beløb på $ 0, får spilleren 2147482963 i spilvaluta.

I datastrukturen for Pokémon i Pokémon-spil gemmes antallet af opnåede oplevelsespoint i et 3-byte heltal. I den første og anden generation beregnes imidlertid Medium Slow -oplevelsesgruppen, der kræver 1.059.860 Experience Points for at nå niveau 100, at have -54 Experience Points på niveau 1 (et niveau, der normalt ikke stødes på under normalt spil). På grund af at heltalet er usigneret, bliver værdien til 16.777.162. Hvis Pokémon får mindre end 54 oplevelsespoint i en kamp, ​​springer Pokémon øjeblikkeligt til niveau 100.

En helhedssignaturfejl i stakkonfigurationskoden, der blev udsendt af Pascal -kompilatoren, forhindrede Microsoft / IBM MACRO Assembler Version 1.00 (MASM), et DOS -program fra 1981 og mange andre programmer, der blev kompileret med den samme compiler, til at køre under nogle konfigurationer med mere end 512 KB hukommelse.

Microsoft / IBM Macro Assembler (MASM) Version 1.00, og sandsynligvis alle andre programmer bygget af den samme Pascal -kompilator, havde et heltalsoverløb og en signaturfejl i stakkekonfigurationskoden, hvilket forhindrede dem i at køre på nyere DOS -maskiner eller emulatorer under nogle almindelige konfigurationer med mere end 512 KB hukommelse. Programmet enten hænger eller viser en fejlmeddelelse og afslutter DOS.

I august 2016 udskrev en casinomaskine på Resorts World casino en præmiebillet på $ 42.949.672,76 som følge af en overløbsfejl. Kasinoet nægtede at betale dette beløb og kaldte det en fejlfunktion, idet de i deres forsvar forsvarede, at maskinen klart oplyste, at den maksimale udbetaling var $ 10.000, så enhver gevinst, der oversteg, måtte være et resultat af en programmeringsfejl. Den Iowa Højesteret medhold kasinoet.

Se også

• Bufferoverløb
• Bunkeoverløb
• Modulær regning
• Markøren svirrer
• Software test
• Stack bufferoverløb
• Statisk programanalyse
• Unix signal

Referencer

eksterne links

• Phrack #60, Basic Integer Overflows
• Phrack #60, Big Loop Integer Protection
• Effektiv og præcis registrering af heltal-baserede angreb
• WASC Threat Classification - Integer Overflows
• Forstå Integer Overflow i C/C ++
• Binary Overflow - Binær aritmetik
• ISO C11 Standard