Přetečení celého čísla - Integer overflow

Přetečení celých čísel lze demonstrovat na přetečení počítadla ujetých kilometrů , což je mechanická verze jevu. Všechny číslice jsou nastaveny na maximum 9 a další přírůstek bílé číslice způsobí, že kaskáda přenosových sčítání nastaví všechny číslice na 0, ale žádná vyšší číslice (1 000 000 s číslice) se nezmění na 1, takže počítadlo resetuje na nulu. Toto je obtékání na rozdíl od nasycení .

V počítačovém programování dochází k přetečení celých čísel, když se aritmetická operace pokusí vytvořit číselnou hodnotu, která je mimo rozsah, který lze reprezentovat daným počtem číslic - buď vyšší než maximální, nebo nižší než minimální reprezentovatelná hodnota.

Nejběžnějším výsledkem přetečení je, že jsou uloženy nejméně významné reprezentativní číslice výsledku; výsledek se říká, že obepíná maximum (tj. moduluje výkon radixu , v moderních počítačích obvykle dva, ale někdy deset nebo jiný radix).

Stav přetečení může poskytnout výsledky vedoucí k nezamýšlenému chování. Zejména pokud tato možnost nebyla předvídána, může přetečení ohrozit spolehlivost a zabezpečení programu .

U některých aplikací, jako jsou časovače a hodiny, může být vhodné přetékání. Standard C11 uvádí, že u celých čísel bez znaménka je definovaným chováním modulo wrapping a termín overflow nikdy neplatí: "výpočet zahrnující nepodepsané operandy nemůže nikdy přetečit."

U některých procesorů, jako jsou grafické procesorové jednotky (GPU) a digitální signálové procesory (DSP), které podporují aritmetiku nasycení , by přetečené výsledky byly „upnuty“, tj. Nastaveny na minimální nebo maximální hodnotu v reprezentativním rozsahu, spíše než omotány.

Původ

Šířka registr z procesoru určuje rozsah hodnot, které mohou být zastoupeny v její evidence. Ačkoli drtivá většina počítačů může na operandech v paměti provádět aritmetiku s více přesnostmi, což umožňuje libovolně dlouhé číslování a zamezení přetečení, šířka registru omezuje velikosti čísel, která lze provozovat (např. Sčítat nebo odčítat) pomocí jedna instrukce na operaci. Mezi typické šířky binárních registrů pro celá čísla bez znaménka patří:

  • 4 bity: maximální reprezentativní hodnota 2 4 - 1 = 15
  • 8 bitů: maximální reprezentativní hodnota 2 8 - 1 = 255
  • 16 bitů: maximální reprezentativní hodnota 2 16 - 1 = 65 535
  • 32 bitů: maximální reprezentativní hodnota 2 32 - 1 = 4 294 967 295 (nejběžnější šířka pro osobní počítače od roku 2005),
  • 64 bitů: maximální reprezentativní hodnota 2 64 - 1 = 18 446 744 073 709 551 615 (nejběžnější šířka CPU osobních počítačů , stav z roku 2017),
  • 128 bitů: maximální reprezentovatelný hodnota 2 128 - 1 = 340.282.366.920.938.463.463.374.607.431.768.211.455

Když aritmetická operace vytvoří výsledek větší než maximum uvedené výše pro N-bitové celé číslo, přetečení sníží výsledek na N-tý výkon modulo 2, přičemž zachová pouze nejméně významné bity výsledku a efektivně způsobí obtékání .

Zejména násobení nebo sčítání dvou celých čísel může mít za následek hodnotu, která je neočekávaně malá, a odečtení od malého celého čísla může způsobit zalomení velké kladné hodnoty (například 8bitové sčítání celých čísel 255 + 2 má za následek 1, což je 257 mod 2 8 a podobně odečtením 0 - 1 vznikne 255, reprezentace komplementu dvojky −1).

Takový wraparound může způsobit poškození zabezpečení - pokud je jako počet bytů přidělených pro vyrovnávací paměť použita přetečená hodnota, bude vyrovnávací paměť přidělena neočekávaně malá, což může vést k přetečení vyrovnávací paměti, které v závislosti na použití vyrovnávací paměti může turn způsobit spuštění libovolného kódu.

Pokud má proměnná typ celého čísla se znaménkem , může program předpokládat, že proměnná vždy obsahuje kladnou hodnotu. Přetečení celých čísel může způsobit, že se hodnota zalomí a stane se zápornou, což porušuje předpoklad programu a může vést k neočekávanému chování (například 8bitové celočíselné přidání 127 + 1 má za následek −128, dvojkový doplněk 128). (Řešením tohoto konkrétního problému je použít celočíselné typy bez znaménka pro hodnoty, které program očekává a předpokládá, že nikdy nebudou záporné.)

Vlajky

Většina počítačů má dva vyhrazené příznaky procesoru, které kontrolují podmínky přetečení.

Flag carry je nastaven, když je výsledek sčítání nebo odčítání, vzhledem k operandy a výsledek jako nepodepsané čísla, nezapadá do daného počtu bitů. To znamená přetečení s přenášením nebo vypůjčením z nejvýznamnějšího bitu . Bezprostředně následující operace s přidáním nebo odečtením pomocí vypůjčení by pomocí obsahu tohoto příznaku upravila registr nebo paměťové místo, které obsahuje vyšší část víceslovné hodnoty.

Příznak přetečení je nastaven, když je výsledek operace na znaménkem nemá náznak, že by se dalo předpovědět z příznaků operandů např negativním výsledkem při přidání dvou kladných čísel. To znamená, že došlo k přetečení a podepsaný výsledek reprezentovaný ve formě dvou doplňků by se v daném počtu bitů nevešel.

Variace definice a nejednoznačnost

Pokud je pro nepodepsaný typ ideální výsledek operace mimo reprezentativní rozsah typu a vrácený výsledek je získán zabalením, pak je tato událost běžně definována jako přetečení. Naproti tomu standard C11 definuje, že tato událost není přetečením, a uvádí, že „výpočet zahrnující nepodepsané operandy nemůže nikdy přetečit“.

Když je ideální výsledek celočíselné operace mimo reprezentativní rozsah typu a vrácený výsledek je získán upínáním, pak je tato událost běžně definována jako sytost. Použití se liší podle toho, zda je sytost přetokem nebo ne. K eliminaci nejednoznačnosti lze použít termíny obtékání přetečení a saturační přetečení.

Termín podtečení se nejčastěji používá pro matematiku s plovoucí desetinnou čárkou, a nikoli pro matematiku celočíselnou. Lze však nalézt mnoho odkazů na podtečení celého čísla. Když se používá termín celočíselné podtečení, znamená to, že ideální výsledek byl blíže mínus nekonečnu než reprezentativní hodnota výstupního typu nejblíže mínus nekonečnu. Když je použit termín podtečení celé číslo, definice přetečení může zahrnovat všechny typy přetečení nebo může zahrnovat pouze případy, kdy byl ideální výsledek blíže kladnému nekonečnu než reprezentativní hodnota výstupního typu nejblíže kladnému nekonečnu.

Pokud ideálním výsledkem operace není přesné celé číslo, může být význam přetečení v okrajových případech nejednoznačný. Uvažujme případ, kdy ideální výsledek má hodnotu 127,25 a maximální reprezentovatelná hodnota typu výstupu je 127. Pokud je přetečení definováno jako ideální hodnota mimo reprezentativní rozsah výstupního typu, pak by tento případ byl klasifikován jako přetečení. U operací, které mají dobře definované chování zaokrouhlování, může být nutné klasifikaci přetečení odložit, dokud nebude použito zaokrouhlení. Standard C11 definuje, že převody z plovoucí čárky na celé číslo se musí zaokrouhlovat směrem k nule. Pokud se k převodu hodnoty s pohyblivou řádovou čárkou 127,25 na celé číslo použije C, pak by mělo být nejprve použito zaokrouhlení, aby byl poskytnut ideální celočíselný výstup 127. Protože zaokrouhlené celé číslo je v rozsahu výstupů, standard C by tento převod neklasifikoval jako přetečení .

Nekonzistentní chování

Stojí za zmínku, že chování při výskytu přetečení nemusí být za všech okolností konzistentní. Například v programovacím jazyce Rust je funkce poskytována tak, aby uživatelé měli možnost volby a ovládání, ale chování pro základní použití matematických operátorů je přirozeně pevné; toto opravené chování se však liší mezi programem zabudovaným v režimu „ladění“ a programem zabudovaným v režimu „uvolnění“. V C je přetečení celých čísel bez znaménka definováno tak, aby se obtékalo, zatímco přetečení celých čísel se znaménkem způsobuje nedefinované chování .

Metody řešení problémů s přetečením celých čísel

Celé zpracování přetečení v různých programovacích jazycích
Jazyk Celé číslo bez znaménka Celé číslo se znaménkem
Ada modulo modul typu zvýšit Constraint_Error
C / C ++ modulo výkon dvou nedefinované chování
C# výkon modulo 2 v nekontrolovaném kontextu; System.OverflowExceptionje vyvolána v kontrolovaném kontextu
Jáva N/A modulo výkon dvou
JavaScript všechna čísla jsou s plovoucí desetinnou čárkou s dvojitou přesností kromě nového BigInt
MATLAB Integrovaná celá čísla jsou nasycená. Celá čísla s pevným bodem lze konfigurovat pro zalomení nebo nasycení
Python 2 N/A převést na dlouhý typ (bigint)
Semeno 7 N/A zvýšit OVERFLOW_ERROR
Systém N/A převést na bigNum
Simulink konfigurovatelné pro zabalení nebo nasycení
Pokec N/A převést na LargeInteger
Rychlý Způsobuje chybu, pokud nepoužíváte speciální operátory přetečení.

Detekce

Implementace detekce přetečení run-time UBSanje k dispozici pro C kompilátory .

V Javě 8 existují přetížené metody , například podobné Math.addExact(int, int), které se ArithmeticExceptionv případě přetečení vrhnou .

Tým počítačové reakce na mimořádné události (CERT) vyvinul celočíselný model As-if Infinitely Ranged (AIR), což je do značné míry automatizovaný mechanismus, který eliminuje přetečení a zkracování celých čísel v C/C ++ pomocí zpracování chyb za běhu.

Vyhýbání se

Přidělením proměnných datovým typům, které jsou dostatečně velké na to, aby obsahovaly všechny hodnoty, které je možné případně vypočítat a uložit do nich, je vždy možné zabránit přetečení. I když je dostupný prostor nebo pevné datové typy poskytované programovacím jazykem nebo prostředím příliš omezené na to, aby mohly být proměnné defenzivně přidělovány s velkorysými velikostmi, pečlivým objednáváním operací a kontrolou operandů předem, často je možné a priori zajistit že výsledek nikdy nebude větší, než lze uložit. Pomocí nástrojů statické analýzy , formálního ověření a návrhu pomocí smluvních technik lze jistěji a spolehlivěji zajistit, že nedojde k náhodnému přetečení.

Zacházení

Pokud se předpokládá, že může dojít k přetečení, lze do programu vložit testy, které detekují, kdy se to stane nebo se to má stát, a provést další zpracování, aby to zmírnily. Pokud například přeteče důležitý výsledek vypočítaný z přetečení vstupu uživatele, program se může zastavit, odmítnout vstup a možná uživatele vyzvat k zadání jiného vstupu, než aby program pokračoval neplatným přetečeným vstupem a v důsledku toho pravděpodobně selhal. Tento celý proces lze automatizovat: je možné automaticky syntetizovat obslužný program pro přetečení celých čísel, kde je obslužný program například čistý výstup.

CPU obecně mají způsob, jak to zjistit, aby podporovaly sčítání čísel větších než je jejich velikost registru, obvykle pomocí stavového bitu; tato technika se nazývá aritmetika s více přesnostmi. Je tedy možné sčítat dvě čísla široká po dvou bajtech pomocí pouhého sčítání bajtů v krocích: nejprve přidejte nízké bajty a poté přidejte vysoké bajty, ale pokud je nutné provést z nízkých bajtů, jedná se o aritmetické přetečení sčítání bajtů a je nutné detekovat a zvýšit součet vysokých bajtů.

Zpracování možného přetečení výpočtu může někdy představovat volbu mezi provedením kontroly před skutečným výpočtem (určit, zda dojde k přetečení) nebo po něm (na základě výsledné hodnoty zvážit, zda k němu pravděpodobně došlo nebo ne) . Opatrnost by měla být věnována poslednímu výběru. Za prvé, protože to nemusí být spolehlivá metoda detekce (například přidání nemusí nutně zabalit na nižší hodnotu). Za druhé, protože samotný výskyt přetečení může být v některých případech nedefinovaným chováním . V programovacím jazyce C má přetečení typů bez znaménka za následek zalamování, nicméně přetečení typů se znaménkem je číslo nedefinované chování; v důsledku toho kompilátor C může předpokládat, že programátor zajistil, že k přetečení se znaménkem nemůže dojít, a proto může v tichosti optimalizovat jakoukoli kontrolu následnou po výpočtu, který zahrnuje kontrolu výsledku za účelem jeho detekce, aniž by programátor upozornil, že to bylo Hotovo. Je proto vhodné vždy dávat přednost provádění kontrol před výpočty, ne po nich.

Explicitní šíření

pokud je hodnota příliš velká na to, aby mohla být uložena, lze jí přiřadit speciální hodnotu indikující, že došlo k přetečení, a poté nechat všechny následující operace vrátit tuto hodnotu příznaku. Takové hodnoty jsou někdy označovány jako NaN pro „ne číslo“. To je užitečné, takže problém lze zkontrolovat jednou na konci dlouhého výpočtu, nikoli po každém kroku. To je často podporováno hardwarem s plovoucí desetinnou čárkou nazývaným FPU .

Podpora programovacího jazyka

Programovací jazyky implementují různé metody zmírnění proti náhodnému přetečení: Ada , Seed7 (a určité varianty funkčních jazyků), vyvolávají podmínku výjimky při přetečení, zatímco Python (od 2.4) bezproblémově převádí interní reprezentaci čísla tak, aby odpovídalo jeho růstu, případně to jako long- jehož schopnost je omezena pouze dostupnou pamětí.

V jazycích s nativní podporou aritmetiky a bezpečnosti typu arbitrární přesnost (například Python , Smalltalk nebo Common Lisp ) jsou čísla automaticky povýšena na větší velikost, když dojde k přetečení, nebo jsou vyvolány výjimky (signalizovány podmínky), pokud existuje omezení rozsahu. Použití takových jazyků může být proto užitečné ke zmírnění tohoto problému. V některých takových jazycích jsou však stále možné situace, kdy může dojít k přetečení celých čísel. Příkladem je explicitní optimalizace cesty k kódu, kterou profiler považuje za zúžení. V případě Common Lisp je to možné pomocí explicitní deklarace k typové anotaci proměnné ke slovu velikosti stroje (fixnum) a snížení úrovně bezpečnosti typu na nulu pro konkrétní blok kódu.

V ostrém kontrastu se staršími jazyky, jako je C, některé novější jazyky, například Rust , poskytují integrované funkce, které umožňují snadnou detekci a volbu uživatele ohledně toho, jak by se mělo s přetečením zacházet případ od případu. V Rustu zatímco použití základních matematických operátorů přirozeně postrádá takovou flexibilitu, uživatelé mohou alternativně provádět výpočty pomocí sady metod poskytovaných každým z celočíselných primitivních typů. Tyto metody dávají uživatelům několik možností mezi provedením operace „zkontrolováno“ (nebo „přetékání“) (která udává, zda došlo k přetečení prostřednictvím návratového typu); „nekontrolovaná“ operace; operace, která provádí zalamování, nebo operace, která provádí nasycení na numerických hranicích.

Nasycená aritmetika

V počítačové grafice nebo zpracování signálu je typické pracovat s daty v rozsahu od 0 do 1 nebo od −1 do 1. Například pořiďte obrázek ve stupních šedi, kde 0 představuje černou, 1 představuje bílou a hodnoty mezi nimi představují odstíny šedi. Jedna operace, kterou by člověk mohl chtít podporovat, je rozjasnění obrazu vynásobením každého pixelu konstantou. Nasycená aritmetika umožňuje člověku pouze slepě znásobit každý pixel touto konstantou, aniž by se musel obávat přetečení, a to tak, že se jednoduše drží rozumného výsledku, že všechny tyto pixely větší než 1 (tj. „Jasnější než bílá“ ) se stanou bílými a všechny hodnoty „tmavší než černé“ „jen začerni.

Příklady

Neočekávané aritmetické přetečení je poměrně častou příčinou chyb programu . Takové chyby přetečení může být obtížné odhalit a diagnostikovat, protože se mohou projevit pouze u velmi velkých sad vstupních dat, u nichž je menší pravděpodobnost, že budou použity při ověřovacích testech.

Vezmeme -li aritmetický průměr dvou čísel jejich sčítáním a dělením dvěma, jak se to dělá v mnoha vyhledávacích algoritmech , způsobí chybu, pokud je součet (i když ne výsledný průměr) příliš velký na to, aby byl reprezentován, a proto přetéká.

Neošetřené aritmetické přetečení v softwaru řízení motoru bylo hlavní příčinou havárie prvního letu rakety Ariane 5 v roce 1996 . Software byl považován za bezchybný, protože byl používán při mnoha předchozích letech, ale ty používaly menší rakety, které generovaly nižší zrychlení než Ariane 5. Frustrující je, že část softwaru, ve které došlo k chybě přetečení, nebylo ani nutné běžel pro Ariane 5 v době, kdy způsobil neúspěch rakety-byl to proces spouštěcího režimu pro menšího předchůdce Ariane 5, který zůstal v softwaru, když byl upraven pro novou raketu. Kromě toho byla skutečnou příčinou chyby technická specifikace toho, jak se software vypořádal s přetečením, když byl detekován: provedl diagnostický výpis na sběrnici, která by byla připojena k testovacímu zařízení během testování softwaru během vývoje ale byl během letu připojen k motorům raketového řízení; skládka dat vyhnala trysku motoru tvrdě na jednu stranu, což vyřadilo raketu z aerodynamické kontroly a urychlilo její rychlý rozpad ve vzduchu.

Dne 30. dubna 2015 americký federální úřad pro letectví oznámil, že nařídí provozovatelům Boeingu 787 pravidelně obnovovat jeho elektrický systém, aby se předešlo přetečení celých čísel, které by mohlo vést ke ztrátě elektrické energie a nasazení vzduchové turbíny RAM , a Boeing nasadil aktualizaci softwaru v čtvrté čtvrtletí. Evropská agentura pro bezpečnost letectví a následně dne 4. května 2015. Tato chyba se stane po 2³¹ setinách (248.55134814815 dnů), což ukazuje na 32bitové podepsané celé číslo .

Přetečení chyby jsou evidentní v některých počítačových hrách. V arkádové hry Donkey Kong , to je nemožné postoupit minulé úrovně 22 v důsledku integer overflow ve svém časovém / bonus. Hra vezme číslo úrovně, na které je uživatel, vynásobí jej 10 a přičte 40. Když dosáhnou úrovně 22, je časové/bonusové číslo 260, což je na jeho 8bitový 256 hodnotový registr příliš velké, takže se samo resetuje na 0 a zbývajícím 4 dává čas/bonus - příliš krátký na dokončení úrovně. V Donkey Kong Jr. Math při pokusu o výpočet čísla přes 10 000 ukazuje pouze první 4 číslice. Přetečení je příčinou slavné úrovně „rozdělené obrazovky“ v Pac-Manu . Notoricky známá chyba Nuclear Gandhi v Civilizaci byla údajně způsobena podtečením celého čísla, ke kterému došlo, když se hra pokusila odečíst 2 od Gándhího výchozího stupně agresivity 1 a nastavit jej na 255, téměř 26krát vyšší než normální maximum 10. ( Sid Meier v rozhovoru tvrdil, že to bylo ve skutečnosti záměrné.) Taková chyba také způsobila „Far Lands“ v Minecraftu, které existovaly od vývojového období Infdev do Beta 1.7.3; později byl opraven v beta verzi 1.8, ale stále existuje ve verzích Minecraft pro Pocket Edition a Windows 10 Edition . Ve hře Super NES Lamborghini American Challenge může hráč způsobit, že jeho částka během závodu klesne pod 0 $ tím, že mu bude po zaplacení poplatku za závod uložena pokuta přes limit zbývajících peněz, čímž dojde k závadě celého čísla a hráči bude uděleno 65 535 000 $. víc, než by to mělo, kdyby to bylo negativní. Podobná závada se vyskytuje ve hře STALKER: Clear Sky, kde se hráč může dostat do záporné částky rychlým cestováním bez dostatečného množství finančních prostředků a poté přejít k události, kde bude hráč okraden a bude mu odebrána veškerá měna. Poté, co se hra pokusí odebrat peníze hráče na částku 0 $, je hráči přiděleno 2147482963 v herní měně.

V datové struktuře Pokémonů ve hrách Pokémon je počet získaných zkušenostních bodů uložen v 3bajtovém čísle. V první a druhé generaci však skupina Medium Slow experience, která k dosažení úrovně 100 vyžaduje 1 059 860 bodů zkušeností, počítá s tím, že na úrovni 1 bude mít -54 bodů zkušeností (úroveň, na kterou se při běžném hraní obvykle nenarazíte). Vzhledem k tomu, že celé číslo je bez znaménka, hodnota se změní na 16 777 162. Pokud Pokémon získá v bitvě méně než 54 zkušenostních bodů, pokémon okamžitě vyskočí na úroveň 100.

Celočíselná chyba podepsanosti v kódu nastavení zásobníku emitovaném kompilátorem Pascal zabránila programu Microsoft / IBM MACRO Assembler verze 1.00 (MASM), programu DOS z roku 1981 a mnoha dalším programům kompilovaným se stejným kompilátorem, aby běžely v některých konfiguracích s více než 512 kB paměti.

Microsoft / IBM Macro Assembler (MASM) verze 1.00, a pravděpodobně všechny ostatní programy vytvořené stejným kompilátorem Pascal, měly v kódu nastavení zásobníku chybu přetečení celého čísla a podpisu, což jim bránilo v spuštění na novějších počítačích nebo emulátorech DOS pod některými běžnými konfigurace s více než 512 kB paměti. Program buď zablokuje, nebo zobrazí chybovou zprávu a skončí do DOSu.

V srpnu 2016 vytiskl automat v kasinu Resorts World v důsledku přetečení chyby cenový lístek ve výši 42 949 672,76 USD. Kasino odmítlo zaplatit tuto částku, označilo to za poruchu, přičemž na svou obranu používalo, že stroj jasně uvedl, že maximální výplata byla 10 000 $, takže jakákoli cena přesahující tuto hodnotu musela být důsledkem chyby v programování. Iowa Nejvyšší soud rozhodl ve prospěch kasina.

Viz také

Reference

externí odkazy