Přetečení celého čísla

Přetečení celého čísla je situace  v počítačové aritmetice, ve které nelze hodnotu vypočítanou jako výsledek operace umístit do datového typu n-bitové celé číslo. Rozlišujte přetečení přes horní hranici znázornění a přes spodní ( anglicky Underflow ). 

Příklad: přidání dvou 8bitových proměnných a uložení výsledku do proměnné stejné velikosti:

dojde k přetečení.

V tomto případě se výsledek nezapíše očekávaný , ale . Stojí za zmínku, že výpočet zde proběhl modulo 2 n a aritmetika modulo je cyklická, tedy 255+1=0 (pro n = 8). Tuto situaci přetečení opraví počítač nastavením speciálních bitů registru příznaků Overflow a Carry (článek 3.4.3.1 Combined Volume: Volume 1 [1] ). Při programování v jazyce symbolických instrukcí lze takovou situaci přímo nastolit, například ruční kontrolou stavu příznakového registru po provedení operace (článek 7.3.13.2 Combined Volume: Volume 1 [1] ).

Původ problému

Bitová hloubka registru určuje rozsah dat, která v něm mohou být reprezentována. Rozsahy reprezentace pro celočíselné typy v binárních počítačích:

Bitness 8 bitů 16 bit 32 bit 64 bit
nepodepsaný Rozsah 0..2 8 −1 0..2 16 −1 0..2 32 −1 0..2 64 −1
Rozsah (desítkové) 0..255 0..65535 0..4294967295 0.. 18446744073709551615
ikonický Rozsah -2 7 .. 2 7 −1 -2 15 .. 2 15 −1 -2 31 .. 2 31 −1 -2 63 .. 2 63 −1
Rozsah (desítkové) -128..127 -32768..32767 -2147483648.. 2147483647 -9223372036854775808.. 9223372036854775807

Ve zdrojovém kódu může dojít k přetečení v důsledku chyby programátora nebo nedostatečné ostražitosti vstupních dat [2] .

Bezpečnostní rizika

Schopnost přetečení je široce používána programátory, například pro hashování a kryptografii, generování náhodných čísel a hledání hranic na reprezentaci typů [4] . Přitom např. podle standardu jazyků C a C++ se výpočty bez znaménka provádějí modulo 2, zatímco přetečení se znaménkem je klasickým příkladem [5] nedefinovaného chování [6] .

Tento druh nesprávnosti v kódu vede k následujícím důsledkům [4] :

  1. Kompilace může probíhat neočekávaně. Kvůli přítomnosti nedefinovaného chování v programu mohou optimalizace kompilátoru změnit chování programu.
  2. Časovaná bomba. Na aktuální verzi OS, kompilátoru, možnosti kompilace, strukturální organizace programu atd. může fungovat vše, ale při jakékoli změně, například vzhledu agresivnějších optimalizací, se to zlomí.
  3. Iluze předvídatelnosti. Konkrétní konfigurace kompilátoru může mít velmi specifické chování, například kompilátory C a C++ obvykle implementují operace modulo 2 n a pro typy se znaménkem (pouze ty, které jsou interpretovány ve dvou doplňcích), pokud jsou zakázány agresivní optimalizace. V takové chování však nelze doufat, jinak hrozí účinek „časované bomby“
  4. Tvorba dialektů. Některé kompilátory poskytují další možnosti pro rozšíření nedefinovaného chování . Například GCC i Clang podporují volbu -fwrapv, která poskytuje chování popsané výše (v bodě 3).

Změna standardu může přinést nové problémy s přetečením. Například 1<<31 byla implementace závislá ve standardech ANSI C a C++98, zatímco ve standardech C99 a C11 se stala nedefinovanou (pro 32bitová celá čísla). [čtyři]

Taková chyba může mít i další důsledky, například přetečení vyrovnávací paměti .

Využití a následky

Klíčové bezpečnostní důsledky [7] :

Klasicky lze přetečení využít přes přetečení vyrovnávací paměti.

img_t * tabulka_ptr ; /*struktura obsahující img data, každá 10kB*/ int num_imgs ; ... num_imgs = get_num_imgs (); table_ptr = ( img_t * ) malloc ( sizeof ( img_t ) * num_imgs ); ...

Tento příklad [7] ilustruje několik zranitelností najednou. Za prvé, příliš velký počet num_imgs alokuje velkou vyrovnávací paměť, což může způsobit, že program spotřebovává všechny systémové prostředky nebo může způsobit pád .

Další slabinou je, že pokud je num_imgs ještě větší, přeteče argument malloc. Poté bude přidělena pouze malá vyrovnávací paměť. Při zápisu do něj dojde k přetečení bufferu , jehož důsledky mohou být: zachycení kontroly nad prováděním, spuštění kódu útočníka, přístup k důležitým informacím. [osm]

Předcházení problému

Ochrana proti takovému chování by měla být prováděna na několika úrovních [7] :

  1. Plánování programu a požadavky:
    • Ujistěte se, že všechny komunikační protokoly mezi komponentami jsou přesně definovány. Včetně toho, že budou detekovány všechny výpočty mimo hranice pohledu . A vyžadovat přísné dodržování těchto protokolů
    • Použijte programovací jazyk a kompilátor , který nedovolí, aby se tato chyba zabezpečení zhmotnila, buď ji usnadní detekci, nebo provede automatickou kontrolu hranic. Nástroje poskytované překladačem zahrnují sanitizéry (např . Address Sanitizer nebo Undefined Behavior Sanitizer).
  2. Architektura programu:
    • Používejte osvědčené knihovny nebo rámce , které vám pomohou provádět výpočty bez rizika nepředvídatelných následků . Příklady zahrnují knihovny jako SafeInt (C++) nebo IntegerLib (C nebo C++).
    • Jakékoli bezpečnostní kontroly na straně klienta by měly být duplikovány na straně serveru , aby se zabránilo CWE-602 . Útočník může obejít ověření na straně klienta změnou samotných hodnot ihned po provedení ověření nebo úpravou klienta tak, aby ověření zcela odstranil.
  3. Implementace:
    • Ověřte všechna příchozí číselná data a ujistěte se, že jsou v očekávaném rozsahu. Nezapomeňte zkontrolovat minimální práh i maximum. Kde je to možné, používejte čísla bez znaménka. To usnadní kontrolu přetečení.
    • Prozkoumejte všechny potřebné nuance programovacího jazyka spojeného s numerickými výpočty ( CWE-681 ). Jak jsou zastoupeny, jaké jsou rozdíly mezi podepsanými a nepodepsanými , 32bitovými a 64bitovými , problémy s přeléváním (ořezávání, přelévání typu se znaménkem a bez znaménka  - výše) a jak čísla, která jsou příliš malá nebo naopak velká pro jsou zpracovány jejich strojní reprezentace. Také se ujistěte, že typ, který používáte (např. int nebo long), pokrývá požadovaný rozsah zobrazení
    • Podrobně prozkoumejte varování kompilátoru a vyřešte možné problémy se zabezpečením, jako jsou neshody znamének operandů v operacích s pamětí nebo použití neinicializovaných proměnných . I když je zranitelnost velmi malá, může vést k ohrožení celého systému.

Mezi další pravidla, jak se těmto zranitelnostem vyhnout, zveřejněná v CERT C Secure Coding Standard v roce 2008 patří [9] :

  • Nepište ani nepoužívejte funkce pro zpracování vstupu řetězce, pokud nezvládají všechny případy
  • U podepsaných typů nepoužívejte bitové operace
  • Vyhodnoťte výrazy na větším typu před porovnáním nebo přiřazením k menšímu
  • Buďte opatrní před sesíláním mezi číslem a ukazatelem
  • Zajistěte, aby výpočty modulo nebo výsledky dělení nevedly k následnému dělení nulou
  • Použijte intmax_t nebo uintmax_t pro formátované I/O vlastních číselných typů

Příklady ze života

Studie SPECCINT

V článku [4] , jakožto předmětu studia programů C a C++ pro přetečení celých čísel , je podrobně studován jeden z nejpoužívanějších a nejznámějších testovacích balíčků SPEC , sloužící k měření výkonu. Skládá se z fragmentů nejběžnějších úloh, jako jsou: testy z výpočetní matematiky, kompilace, práce s databázemi, diskem, sítí a tak dále.

Výsledky analýzy SPECCINT2000 ukazují přítomnost 219 statických zdrojů přetečení v 8 z 12 benchmarků, z nichž 148 použilo nepodepsané přetečení a 71 podepsané přetečení ( opět nedefinované chování ). Nepodepsané přetečení zároveň také není vždy úmyslné a může být chybou a zdrojem zranitelnosti (například Výpis 2 téhož článku [4] ).

Testováno také na "časované bomby" ve SPECCINT2006. Jeho myšlenkou je vrátit náhodné číslo na každé místo nedefinovaného chování a zjistit, k jakým důsledkům to může vést. Pokud budeme hodnotit nedefinované chování z pohledu standardu C99 / C ++ 11, pak v testu neprojde až 6 z 9 benchmarků.

Příklady z jiných softwarových balíků

int addi ( int lhs , int rhs ) { errno = 0 ; if (((( lhs + rhs ) ^ lhs ) & (( lhs + rhs ) ^ rhs )) >> ( sizeof ( int ) * CHAR_BIT -1 )) { error_handler ( "CHYBA PŘETEČENÍ" , NULL , EOVERFLOW ); errno = EINVAL ; } return lhs + rhs ; }

Tento kus kódu [4] z balíčku IntegerLib kontroluje, zda lze lhs a rhs sečíst bez přetečení. A přesně v řádku 3 může k tomuto přetečení dojít (při sčítání lhs + rhs). Toto je UB, protože lhs a rhs jsou typy se znaménkem. Kromě toho bylo v této knihovně nalezeno 19 dalších UB-overflows.

Autoři také ohlásili 13 přetečení v SQLite, 43 v SafeInt, 6 v knihovně GNU MPC, 30 v PHP, 18 ve Firefoxu, 71 v GCC, 29 v PostgreSQL, 5 v LLVM a 28 v Pythonu. Většina chyb byla brzy opravena.

Další příklady

Slavný příklad přetečení celého čísla se vyskytuje ve hře Pac-Man , stejně jako ostatní hry v sérii: Ms. Pac-Man , Jr. Pac Man . Tato závada se také objevuje v Pac-Man Google Doodle jako takzvané „Easter Egg“. [10] Zde, na úrovni 256, lze pozorovat " obrazovka smrti " a samotná úroveň se nazývá " úroveň rozdělené obrazovky ". Nadšenci rozebrali zdrojový kód ve snaze opravit chybu úpravou hry .

Stejný problém byl údajně ve hře Sid Meier's Civilization a je známá jako Nuclear Gandhi [11] . Podle legendy v určitém okamžiku hry s velmi mírumilovným Gándhím dojde k přetečení přes 0 úrovní nepřátelství, což může vyústit v jadernou válku s Gándhím. Ve skutečnosti se takový mýtus objevil až s vydáním Civilizace V , kde parametr jeho umělé inteligence regulující tvorbu a použití jaderných zbraní má nejvyšší hodnotu 12, což nebylo v rozporu s tím, že Gándhí je jeden. z nejmírumilovnějších vůdců ve hře [12] .

Dalším příkladem je závada v SimCity 2000 [13] . Jde o to, že rozpočet hráče se stal velmi velkým a po projití 2 31 se náhle stal záporným. Hra končí porážkou.

Tato závada pochází z Diabla III . Kvůli jedné ze změn v patchi 1.0.8 se ekonomika hry zhroutila. Maximální částka za transakce byla zvýšena z 1 mil. na 10 mil. Nákupní cena přetekla přes 32bitový typ a při zrušení operace byla vrácena celá částka. To znamená, že hráč zůstal se ziskem 2 32 herní měny [14]

Viz také

Poznámky

  1. ↑ 1 2 Intel® 64 a IA-32 Architectures Software Developer Manuals |  Software Intel® . software.intel.com. Staženo: 22. prosince 2017.
  2. ↑ x86 Exploitation 101: „Integer overflow“ – přidání jednoho dalšího… aaaaaaaaaaa je to pryč  , gb_master /dev/null  (12. srpna 2015). Staženo 20. prosince 2017.
  3. ↑ Konsorcium zabezpečení webových aplikací / přetečení celého čísla . projects.webappsec.org. Staženo: 8. prosince 2017.
  4. ↑ 1 2 3 4 5 6 W. Dietz, P. Li, J. Regehr, V. Adve. Pochopení přetečení celého čísla v C/C #x002B; #x002B;  // 2012 34. mezinárodní konference softwarového inženýrství (ICSE). - Červen 2012. - S. 760-770 . - doi : 10.1109/icse.2012.6227142 .
  5. ↑ CWE - 2011 CWE/SANS Top 25 nejnebezpečnějších softwarových chyb  . cwe.mitre.org. Staženo: 21. prosince 2017.
  6. ↑ ISO/IEC 9899 : 2011 - Informační technologie -- Programovací jazyky ​​-  C. www.iso.org. Staženo: 21. prosince 2017.
  7. ↑ 1 2 3 CWE-190: Integer Overflow nebo Wraparound (3.0  ) . cwe.mitre.org. Staženo: 12. prosince 2017.
  8. ↑ CWE-119: Nesprávné omezení operací v mezích vyrovnávací paměti (3.0  ) . cwe.mitre.org. Staženo: 12. prosince 2017.
  9. ↑ CWE-738: Zabezpečené kódování CERT C (verze 2008) Sekce 04 – Celá čísla (INT) (3.0  ) . cwe.mitre.org. Staženo: 15. prosince 2017.
  10. ↑ Mapa 256 Glitch  , Pac - Man Wiki . Staženo 12. prosince 2017.
  11. ↑ Nuclear Gandhi , Know Your Meme . Staženo 15. prosince 2017.
  12. ↑ Artemy Leonov. Proč je příběh chyby „nukleárního Gándhího“ civilizace pravděpodobně vymyšlený . DTF (5. září 2019). Datum přístupu: 24. října 2020.
  13. ↑ Sim City 2000 Integer Overflow . Blake O\'Hare. Staženo: 12. prosince 2017.
  14. ↑ Ekonomika Diablo III zlomena chybou přetečení celého čísla  , minimaxir | Blog Maxe Woolfa . Staženo 12. prosince 2017.