Integer túlcsordulás

Az egész szám túlcsordulása a számítógépes aritmetika olyan helyzete, amelyben a művelet eredményeként számított érték nem helyezhető el n bites egész adattípusba. Tegyen különbséget az ábrázolás felső határán keresztül történő túlcsordulás és az alsó határon keresztül ( angol Underflow ).

Példa: két 8 bites változó hozzáadása és az eredmény tárolása egy azonos méretű változóban:

$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}}$

túlcsordulás lép fel.

Ebben az esetben az eredményt nem a várt , hanem a . Érdemes megjegyezni, hogy a számítás itt modulo 2 n , és a modulo aritmetika ciklikus, azaz 255+1=0 (n = 8 esetén). Ezt a túlcsordulási helyzetet a számítógép az Overflow és Carry jelzők regiszterének speciális bitjeinek beállításával javítja (3.4.3.1 Kombinált kötet: 1. kötet [1] ). Assembly nyelven történő programozáskor egy ilyen helyzet közvetlenül megállapítható, például a jelzőregiszter állapotának manuális ellenőrzésével a művelet végrehajtása után (7.3.13.2. Kombinált kötet: 1. kötet [1] ). ${\displaystyle 271_{10}={\szín {piros}1}00001111_{2))$ ${\displaystyle 15_{10}=00001111_{2))$

A probléma eredete

Egy regiszter bitmélysége határozza meg a benne ábrázolható adatok körét. Az egész típusok ábrázolási tartományai bináris számítógépekben:

Bitness		8 bites	16 bites	32 bites	64 bites
aláírás nélküli	Hatótávolság	0..2 8 −1	0..2 16 −1	0..2 32 −1	0..2 64 −1
aláírás nélküli	Tartomány (tizedes)	0..255	0..65535	0..4294967295	0.. 18446744073709551615
ikonszerű	Hatótávolság	-2 7 .. 2 7 −1	-2 15 .. 2 15 −1	-2 31 .. 2 31 −1	-2 63 .. 2 63 −1
ikonszerű	Tartomány (tizedes)	-128..127	-32768..32767	-2147483648.. 2147483647	-9223372036854775808.. 9223372036854775807

Túlcsordulás fordulhat elő a forráskódban a programozó hibája vagy a bemeneti adatok éberségének hiánya miatt [2] .

Aláírt és előjel nélküli eltérés . Ha a számok a számítógépen egy további kódban vannak ábrázolva, akkor egy bitfolyamnak különböző számok felelnek meg. A 32 bites aritmetikában az előjeles −1 az előjel nélküli 4294967295-nek (az ábrázolás felső határa) felel meg. Vagyis az egyik típus áttétele a másikra jelentős jelentésbeli eltérést eredményezhet. Ez a fajta hiba gyakran előjelezési hibából ( és ), azaz a különböző előjelű típusok közötti hibás típusadásból adódik .
Vágási probléma. Akkor fordul elő, ha egy számot kisebb hosszúságú egész számként értelmezünk. Ebben az esetben csak a legkisebb jelentőségű bitek maradnak a számban. Az időseket eldobjuk, ami a számérték változásához vezet
Jel kiterjesztés. Érdemes megjegyezni, hogy egy előjeles szám nagyobb hosszúságú típusba öntésekor a legjelentősebb bitet másolják, ami ha előjel nélkülinek értelmezzük, akkor nagyon nagy számhoz vezet [3]

Biztonsági kockázatok

A túlcsordulási képességet a programozók széles körben használják például kivonatolásra és kriptográfiára, véletlen számok generálására és a típusábrázolás határainak megtalálására [4] . Ugyanakkor például a C és C++ nyelvek szabványa szerint az előjel nélküli számításokat modulo 2 végzi, míg az előjeles túlcsordulás a definiálatlan viselkedés klasszikus példája [5] [6] .

A kód ilyen jellegű helytelensége a következő következményekkel jár [4] :

Az összeállítás váratlanul indulhat. A programban előforduló meghatározatlan viselkedés miatt a fordítóoptimalizálás megváltoztathatja a program viselkedését.
Időbomba. Az operációs rendszer jelenlegi verzióján, fordítón, fordítási lehetőségeken, a program szerkezeti felépítésén, stb., minden működhet, de bármilyen változtatással, például agresszívebb optimalizálás megjelenésével, ez tönkremegy.
A kiszámíthatóság illúziója. Egy adott fordítókonfiguráció nagyon specifikus viselkedést mutathat, például a C és C++ fordítók jellemzően modulo 2 n műveleteket valósítanak meg , és az előjeles típusoknál (csak a kettős komplementerben értelmezetteknél), ha az agresszív optimalizálás le van tiltva. Ilyen viselkedésben azonban nem lehet reménykedni, különben fennáll az „időzített bomba” hatásának veszélye.
A nyelvjárások kialakulása. Egyes fordítók további lehetőségeket kínálnak a meghatározatlan viselkedés kiterjesztésére . Például a GCC és a Clang is támogatja a -fwrapv opciót, amely a fent leírt viselkedést biztosítja (a 3. pontban).

A szabvány megváltoztatása új túlcsordulási problémákat okozhat. Például az 1<<31 az ANSI C és C++98 szabványokban implementációfüggő volt , míg a C99 és C11 (32 bites egész számok esetén) definiálatlanná vált. [négy]

Ezenkívül egy ilyen hibának egyéb következményei is lehetnek, például puffertúlcsordulás .

Kihasználás és utóhatások

Főbb biztonsági vonatkozások [7] :

A hozzáférhetőség érdekében . Lehetséges rendszerhiba (ablak DoS támadásokhoz )
Az integritásért . Az adatokhoz való jogosulatlan hozzáférés
A magánéletért . Harmadik féltől származó kód végrehajtása a védelmi mechanizmus megkerülésével

Klasszikusan a túlcsordulást puffertúlcsorduláson keresztül lehet kihasználni.

img_t * table_ptr ; /*képadatokat tartalmazó struktúra, mindegyik 10 kB*/ int num_imgs ; ... num_imgs = get_num_imgs (); table_ptr = ( img_t * ) malloc ( sizeof ( img_t ) * num_imgs ); ...

Ez a példa [7] egyszerre több sebezhetőséget mutat be. Először is, a túl nagy num_imgs hatalmas puffert foglal le, ami a program összes rendszererőforrásának felhasználását vagy összeomlását okozhatja .

Egy másik sebezhetőség az, hogy ha a num_imgs még nagyobb, akkor túlcsordul a malloc argumentum. Ekkor csak egy kis puffer kerül lefoglalásra. Amikor ír rá, puffertúlcsordulás lép fel , aminek a következményei lehetnek: a végrehajtás feletti irányítás elfogása, a támadó kódjának végrehajtása, fontos információkhoz való hozzáférés. [nyolc]

A probléma elkerülése

Az ilyen viselkedés elleni védelmet több szinten kell végrehajtani [7] :

Programtervezés és követelmények:
- Győződjön meg arról, hogy az összetevők közötti kommunikációs protokollok szigorúan meg vannak határozva. Beleértve azt is, hogy a nézet határain kívül eső összes számítást a rendszer észleli. És megkövetelik ezeknek a protokolloknak a szigorú betartását
- Használjon olyan programozási nyelvet és fordítót , amely nem teszi lehetővé a sérülékenység megvalósulását, vagy megkönnyíti annak észlelését, vagy automatikus határellenőrzést végez. A fordító által biztosított eszközök közé tartoznak a fertőtlenítők (pl . Address Sanitizer vagy Undefined Behavior Sanitizer).
Program architektúrák:
- Használjon bevált könyvtárakat vagy keretrendszereket , amelyek segítenek a számítások elvégzésében a kiszámíthatatlan következmények kockázata nélkül . Ilyenek például a SafeInt (C++) vagy az IntegerLib (C vagy C++) könyvtárak.
- A CWE-602 megelőzése érdekében az ügyféloldali biztonsági ellenőrzéseket meg kell ismételni a szerver oldalon . A támadó megkerülheti az ügyféloldali érvényesítést azáltal, hogy közvetlenül az érvényesítés átadása után módosítja az értékeket, vagy az ügyfél módosításával teljesen eltávolítja az érvényesítést.
Megvalósítások:
- Érvényesítse a bejövő numerikus adatokat, hogy megbizonyosodjon arról, hogy a várt tartományon belül van. Ügyeljen arra, hogy ellenőrizze mind a minimális, mind a maximális küszöböt. Lehetőség szerint használjon előjel nélküli számokat. Ez megkönnyíti a túlcsordulás ellenőrzését.
- Fedezze fel a numerikus számítástechnikához kapcsolódó programozási nyelv ( CWE-681 ) összes szükséges árnyalatát . Hogyan jelennek meg, mi a különbség az előjeles és az előjel nélküli , a 32 bites és a 64 bites között, az öntéssel kapcsolatos problémák (kivágás, előjeles-előjel nélküli típusú öntés – fent), és hogyan túl kicsik vagy éppen ellenkezőleg, nagyok a számok gépi ábrázolásukat dolgozzák fel. Győződjön meg arról is, hogy a használt típus (pl. int vagy long) lefedi a szükséges ábrázolási tartományt
- Vizsgálja meg részletesen a fordítói figyelmeztetéseket, és oldja meg a lehetséges biztonsági problémákat, például a memóriaműveletek operandusjel-eltéréseit vagy az inicializálatlan változók használatát . Még ha a sebezhetőség nagyon kicsi is, az az egész rendszert veszélyeztetheti.

A sérülékenységek elkerülésére a 2008-ban a CERT C Secure Coding Standardban közzétett további szabályok a következők: [9] :

Ne írjon és ne használjon karakterlánc-beviteli kezelő függvényeket, hacsak nem kezelik az összes esetet
Ne használjon bitműveleteket előjeles típusoknál
Értékelje a kifejezéseket egy nagyobb típuson, mielőtt összehasonlítaná vagy hozzárendelné egy kisebbhez
Legyen óvatos, mielőtt egy szám és egy mutató közé dob
Győződjön meg arról, hogy a modulo számítások vagy az osztási eredmények nem eredményeznek további nullával való osztást
Használja az intmax_t vagy uintmax_t értéket az egyéni numerikus típusok formázott I/O- jához

Példák az életből

SPECCINT tanulmány

A [4] cikkben az egész szám túlcsordulásra szolgáló C és C++ programok tanulmányozásának tárgyaként az egyik legszélesebb körben használt és legismertebb teljesítménymérésre használt SPEC tesztcsomagot tanulmányozzuk részletesen. A leggyakoribb feladatok töredékeiből áll, mint például: számítási matematikai tesztek, fordítás, adatbázisokkal, lemezzel, hálózattal stb.

A SPECCINT2000 elemzés eredményei 12 benchmark közül 8-ban 219 statikus túlcsordulási forrás jelenlétét mutatják, amelyek közül 148 előjel nélküli túlcsordulást, 71 pedig előjeles túlcsordulást ( megint meghatározatlan viselkedés ) használt. Ugyanakkor az előjel nélküli túlcsordulás szintén nem mindig szándékos, és hiba és sebezhetőség forrása lehet (például ugyanazon cikk 2. listája [4] ).

"Időzített bombákra" is tesztelték a SPECCINT2006-ban. Az ő ötlete az, hogy minden meghatározatlan viselkedés helyén egy véletlen számot adjon vissza, és nézze meg, hogy ez milyen következményekkel járhat. Ha a definiálatlan viselkedést a C99 / C ++ 11 szabvány szempontjából értékeljük, akkor 9 benchmarkból akár 6 is megbukik a teszten.

Példák más szoftvercsomagokból

int addi ( int lhs , int rhs ) { errno = 0 ; if (((( lhs + rhs ) ^ lhs ) & (( lhs + rhs ) ^ rhs )) >> ( sizeof ( int ) * CHAR_BIT -1 )) { error_handler ( "OVERFLOW ERROR" , NULL , EOVERFLOW ); errno = EINVAL ; } return lhs + rhs ; }

Ez a kódrészlet [4] az IntegerLib csomagból ellenőrzi, hogy az lhs és az rhs összeadható-e túlcsordulás nélkül. És pontosan a 3. sorban fordulhat elő ez a túlcsordulás (lhs + rhs összeadásakor). Ez az UB, mert az lhs és rhs előjeles típusok. Ezenkívül 19 további UB-túlcsordulást találtunk ebben a könyvtárban.

A szerzők emellett 13 túlcsordulásról számoltak be az SQLite-ben, 43-ról a SafeInt-ben, 6-ról a GNU MPC-könyvtárban, 30-ról a PHP-ben, 18-ról a Firefoxban, 71-ről a GCC-ből, 29-ről a PostgreSQL-ből, 5-ről az LLVM-ből és 28-ról a Python-ban. A hibák nagy részét hamarosan kijavították.

Egyéb példák

Az egész számok túlcsordulásának híres példája a Pac-Man játékban fordul elő , akárcsak a sorozat többi játéka: Ms. Pac-Man , Jr. Pac Man . Ezenkívül ez a hiba a Pac-Man Google Doodle-ben az úgynevezett "Easter Egg" néven jelenik meg. [10] Itt, a 256. szinten egy " halál képernyője " figyelhető meg, és magát a szintet " osztott képernyő szintnek " nevezik. A rajongók szétszedték a forráskódot, hogy a játék módosításával kijavítsák a hibát .

Ugyanez a probléma volt állítólag a Sid Meier's Civilization játékban, és Nuclear Gandhiként ismert [11] . A legenda szerint a játék egy nagyon békés Gandhival egy pontján az ellenségeskedés 0 szintjén túlcsordul , ami nukleáris háborúhoz vezethet Gandhival. Valójában egy ilyen mítosz csak a Civilization V megjelenésével jelent meg, ahol a nukleáris fegyverek létrehozását és használatát szabályozó mesterséges intelligenciájának paramétere a legmagasabb, 12-es, ami nem mond ellent annak, hogy Gandhi egy a játék legbékésebb vezetői közül [12] .

Egy másik példa a SimCity 2000 [13] hibája . A lényeg itt az, hogy a játékos költségvetése nagyon nagy lett, és miután átment 2 31 -en, hirtelen negatív lett. A játék vereséggel végződik.

Ez a hiba a Diablo III -tól származik . Az 1.0.8-as javítás egyik változása miatt a játék gazdasága összeomlott. A tranzakciók maximális összegét 1 millióról 10 millióra emelték, a vételi költség túlcsordult a 32 bites típuson, és a művelet lemondásakor a teljes összeg visszajárt. Vagyis a játékos 2 32 játékvaluta nyereséggel maradt [14]

Lásd még

Jegyzetek

↑ 1 2 Intel® 64 és IA-32 architektúrák szoftverfejlesztői kézikönyvei | Intel® szoftver . software.intel.com. Letöltve: 2017. december 22.
↑ x86 Exploitation 101: „Integer overflow” – még egy hozzáadása… aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa és eltűnt , gb_master /dev/null (2015. augusztus 12.). Letöltve: 2017. december 20.
↑ A Web Application Security Consortium / Integer Overflows . project.webappsec.org. Letöltve: 2017. december 8. (határozatlan)
↑ 1 2 3 4 5 6 W. Dietz, P. Li, J. Regehr, V. Adve. Az egész számok túlcsordulása a C/C-ben #x002B; #x002B; // 2012 34. International Conference on Software Engineering (ICSE). - 2012. június - S. 760-770 . - doi : 10.1109/icse.2012.6227142 .
↑ CWE - 2011 CWE/SANS A 25 legveszélyesebb szoftverhiba . cwe.mitre.org. Letöltve: 2017. december 21.
↑ ISO/IEC 9899 : 2011 - Információtechnológia - Programozási nyelvek - C. www.iso.org. Letöltve: 2017. december 21.
↑ 1 2 3 CWE-190: Integer Overflow vagy Wraparound (3.0 ) . cwe.mitre.org. Letöltve: 2017. december 12.
↑ CWE-119: A műveletek helytelen korlátozása a memóriapuffer határain belül (3.0 ) . cwe.mitre.org. Letöltve: 2017. december 12.
↑ CWE-738: CERT C Biztonságos kódolás (2008-as verzió) 04. szakasz – Egész számok (INT) (3.0 ) . cwe.mitre.org. Letöltve: 2017. december 15.
↑ 256. térkép Glitch , Pac - Man Wiki . Letöltve: 2017. december 12.
↑ Nuclear Gandhi , Know Your Meme . Letöltve: 2017. december 15.
↑ Artemy Leonov. Miért találták ki valószínűleg a Civilization "Nuclear Gandhi" hibatörténetét ? DTF (2019. szeptember 5.). Hozzáférés időpontja: 2020. október 24. (határozatlan)
↑ Sim City 2000 Integer Overflow . Blake O\'Hare. Letöltve: 2017. december 12. (határozatlan)
↑ A Diablo III Economy-t megtörte egy egészszámú túlcsordulási hiba , minimaxir | Max Woolf blogja . Letöltve: 2017. december 12.