Kokonaislukujen ylivuoto

Kokonaisluvun ylivuoto on tietokonearitmetiikassa  tilanne, jossa operaation tuloksena laskettua arvoa ei voida sijoittaa n-bittiseen kokonaislukutietotyyppiin . Erottele ylivuoto esityksen yläreunan ja alareunan kautta ( englanniksi Underflow ). 

Esimerkki: kahden 8 - bittisen muuttujan lisääminen ja tuloksen tallentaminen samankokoiseen muuttujaan:

ylivuoto tapahtuu.

Tässä tapauksessa tulos ei kirjoiteta odotettua , vaan . On syytä huomata, että tässä laskenta tapahtui modulo 2 n , ja moduloaritmetiikka on syklistä, eli 255+1=0 (jos n = 8). Tämän ylivuototilanteen korjaa tietokone asettamalla lippujen Overflow ja Carry rekisteriin erikoisbitit (lauseke 3.4.3.1 Yhdistetty volyymi: Volume 1 [1] ). Assembly-kielellä ohjelmoitaessa tällainen tilanne voidaan määrittää suoraan esimerkiksi tarkistamalla lippurekisterin tila manuaalisesti toimenpiteen suorittamisen jälkeen (lause 7.3.13.2 Yhdistetty volyymi: Volume 1 [1] ).

Ongelman alkuperä

Rekisterin bittisyvyys määrittää sen datan alueen, joka voidaan esittää siinä. Kokonaislukutyyppien esitysalueet binääritietokoneissa:

Bitness 8-bittinen 16-bittinen 32-bittinen 64-bittinen
allekirjoittamaton Alue 0..2 8 −1 0..2 16 −1 0..2 32 −1 0..2 64 −1
Alue (desimaali) 0...255 0..65535 0..4294967295 0.. 18446744073709551615
Ikoninen Alue -2 7 .. 2 7 −1 -2 15 .. 2 15 -1 -2 31 .. 2 31 -1 -2 63 .. 2 63 -1
Alue (desimaali) -128...127 -32768..32767 -2147483648.. 2147483647 -9223372036854775808.. 9223372036854775807

Lähdekoodissa voi tapahtua ylivuoto johtuen ohjelmoijan virheestä tai syöttötietojen tarkkailun puutteesta [2] .

Tietoturvariskit _

Ohjelmoijat käyttävät ylivuotoominaisuutta laajalti esimerkiksi hajautus- ja salaustoimintoihin, satunnaislukujen generointiin ja tyyppiesityksen rajojen löytämiseen [4] . Samaan aikaan esimerkiksi C- ja C++-kielten standardin mukaan etumerkittömiä laskutoimituksia suoritetaan modulo 2, kun taas etumerkillinen ylivuoto on klassinen esimerkki [5] määrittelemättömästä käyttäytymisestä [6] .

Tällainen koodin virheellisyys johtaa seuraaviin seurauksiin [4] :

  1. Kokoaminen voi mennä odottamatta. Koska ohjelmassa on määrittelemätöntä toimintaa , kääntäjien optimoinnit voivat muuttaa ohjelman käyttäytymistä.
  2. Aikapommi. Käyttöjärjestelmän nykyisessä versiossa, kääntäjässä, käännösvaihtoehdoissa, ohjelman rakenteellisessa organisaatiossa jne., kaikki voi toimia, mutta millä tahansa muutoksella, esimerkiksi aggressiivisempien optimointien ilmestymisellä, se rikkoutuu.
  3. Ennustettavuuden illuusio. Tietyllä kääntäjäkonfiguraatiolla voi olla hyvin spesifinen käyttäytyminen, esimerkiksi C- ja C++-kääntäjät toteuttavat tyypillisesti operaatioita modulo 2 n ja etumerkityille tyypeille (vain ne, jotka tulkitaan kahden komplementissa), jos aggressiiviset optimoinnit on poistettu käytöstä. Tällaista käytöstä ei kuitenkaan voi toivoa, muuten on olemassa "aikapommin" vaikutuksen vaara.
  4. Murteiden muodostuminen. Jotkut kääntäjät tarjoavat lisävaihtoehtoja määrittelemättömän toiminnan laajentamiseen . Esimerkiksi sekä GCC että Clang tukevat vaihtoehtoa -fwrapv, joka tarjoaa yllä kuvatun toiminnan (kohdassa 3).

Standardin muuttaminen voi aiheuttaa uusia ylivuotoongelmia. Esimerkiksi 1<<31 oli toteutuksesta riippuvainen ANSI C- ja C++98-standardeissa, kun taas se muuttui määrittelemättömäksi C99:ssä ja C11:ssä (32-bittisille kokonaisluvuille). [neljä]

Tällaisella virheellä voi myös olla muita seurauksia, esimerkiksi puskurin ylivuoto .

Hyödyntäminen ja jälkimainingit

Tärkeimmät turvallisuusvaikutukset [7] :

Perinteisesti ylivuotoa voidaan hyödyntää puskurin ylivuodon kautta.

img_t * table_ptr ; /*rakenne, joka sisältää kuvatietoja, 10kt kukin*/ int num_imgs ; ... num_imgs = get_num_imgs (); table_ptr = ( img_t * ) malloc ( sizeof ( img_t ) * num_imgs ); ...

Tämä esimerkki [7] havainnollistaa useita haavoittuvuuksia kerralla. Ensinnäkin liian suuri num_imgs varaa valtavan puskurin, mikä voi saada ohjelman kuluttamaan kaikki järjestelmäresurssit tai saada sen kaatumaan .

Toinen haavoittuvuus on, että jos num_imgs on vielä suurempi, se ylittää malloc-argumentin. Tällöin vain pieni puskuri varataan. Sille kirjoitettaessa tapahtuu puskurin ylivuoto , jonka seuraukset voivat olla: suorituksen hallinnan sieppaus, hyökkääjän koodin suorittaminen, pääsy tärkeisiin tietoihin. [kahdeksan]

Ongelman välttäminen

Suojaus tällaista käyttäytymistä vastaan ​​tulisi suorittaa useilla tasoilla [7] :

  1. Ohjelmasuunnittelu ja vaatimukset:
  2. Ohjelmaarkkitehtuurit:
    • Käytä todistettuja kirjastoja tai kehyksiä , jotka auttavat sinua suorittamaan laskelmia ilman odottamattomien seurausten riskiä . Esimerkkejä ovat kirjastot, kuten SafeInt (C++) tai IntegerLib (C tai C++).
    • Kaikki asiakaspuolen turvatarkastukset tulee kopioida palvelinpuolella CWE-602 :n estämiseksi . Hyökkääjä voi ohittaa asiakaspuolen vahvistuksen muuttamalla itse arvoja heti hyväksynnän läpäisyn jälkeen tai muokkaamalla asiakasta poistamaan vahvistuksen kokonaan.
  3. Toteutukset:
    • Tarkista kaikki saapuvat numeeriset tiedot varmistaaksesi, että ne ovat odotetulla alueella. Muista tarkistaa sekä vähimmäis- että enimmäisarvo. Käytä etumerkittömiä numeroita mahdollisuuksien mukaan. Tämä helpottaa ylivuotojen tarkistamista.
    • Tutustu kaikkiin numeeriseen laskemiseen liittyvän ohjelmointikielen ( CWE-681 ) tarvittaviin vivahteisiin . Kuinka ne esitetään, mitä eroja on etumerkittyjen ja allekirjoittamattomien , 32-bittisten ja 64-bittisten välillä , ongelmat suoratoistossa (trimmaus, etumerkitty-merkitty tyyppi Casting  - edellä) ja kuinka numerot ovat liian pieniä tai päinvastoin suuria heidän koneesityksensä käsitellään. Varmista myös, että käyttämäsi tyyppi (esim. int tai long) kattaa vaaditun esitysalueen
    • Tutki kääntäjän varoituksia yksityiskohtaisesti ja ratkaise mahdolliset tietoturvaongelmat, kuten operandin merkkien yhteensopimattomuus muistitoiminnoissa tai alustamattomien muuttujien käyttö . Vaikka haavoittuvuus on hyvin pieni, se voi johtaa vaaraan koko järjestelmälle.

Muita CERT C Secure Coding Standardissa vuonna 2008 julkaistuja sääntöjä näiden haavoittuvuuksien välttämiseksi ovat [9] :

  • Älä kirjoita tai käytä merkkijonosyöttötoimintoja, elleivät ne käsittele kaikkia tapauksia
  • Älä käytä bittioperaatioita allekirjoitetuissa tyypeissä
  • Arvioi lausekkeet suuremmalla tyypillä ennen kuin vertaat tai määrität pienemmän tyypin
  • Ole varovainen ennen kuin siirrät numeron ja osoittimen väliin
  • Varmista, että modulolaskelmat tai jakotulokset eivät johda myöhempään nollalla jakoon
  • Käytä intmax_t tai uintmax_t mukautettujen numeeristen I/O- muotojen muotoiluun

Esimerkkejä tosielämästä

SPECCINT-tutkimus

Artikkelissa [4] tutkitaan kokonaislukujen ylivuodon C- ja C++-ohjelmia, yksi yleisimmin käytetyistä ja tunnetuimmista testipaketeista SPEC , jota käytetään suorituskyvyn mittaamiseen. Se koostuu fragmenteista yleisimmistä tehtävistä, kuten: laskennallisen matematiikan testit, käännös, työskentely tietokantojen, levyn, verkon ja niin edelleen.

SPECCINT2000-analyysin tulokset osoittavat 219 staattisen ylivuotolähteen läsnäolon 8:ssa 12 vertailuarvosta, joista 148 käytti etumerkittyä ylivuotoa ja 71 käytti etumerkittyä ylivuotoa ( taas määrittelemätön toiminta ). Samanaikaisesti allekirjoittamaton ylivuoto ei myöskään aina ole tarkoituksellista ja voi olla virhe ja haavoittuvuuden lähde (esimerkiksi saman artikkelin luettelo 2 [4] ).

Testattu myös "aikapommeille" SPECCINT2006:ssa. Hänen ideansa on palauttaa satunnainen luku jokaiseen määrittelemättömän käyttäytymisen paikkaan ja katsoa, ​​mihin seurauksiin tämä voi johtaa. Jos arvioimme määrittelemätöntä käyttäytymistä C99 / C ++ 11 -standardin näkökulmasta, niin jopa 6 yhdeksästä vertailuarvosta epäonnistuu testissä.

Esimerkkejä muista ohjelmistopaketeista

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

Tämä IntegerLib-paketin koodinpätkä [4] tarkistaa, voidaanko lhs ja rhs lisätä yhteen ilman ylivuotoa. Ja täsmälleen rivillä 3 tämä ylivuoto voi tapahtua (kun lisätään lhs + rhs). Tämä on UB, koska lhs ja rhs ovat etumerkkityyppejä. Lisäksi tästä kirjastosta löytyi 19 muuta UB-ylivuotoa.

Kirjoittajat raportoivat myös 13 ylivuotoa SQLitessa, 43 SafeIntissa, 6 GNU MPC -kirjastossa, 30 PHP:ssä, 18 Firefoxissa, 71 GCC:ssä, 29 PostgreSQL:ssä, 5 LLVM:ssä ja 28 Pythonissa. Suurin osa virheistä korjattiin pian.

Muita esimerkkejä

Kuuluisa esimerkki kokonaislukujen ylivuodosta esiintyy pelissä Pac-Man , aivan kuten muissakin sarjan peleissä: Ms. Pac-Man , Jr. Pac Man . Tämä häiriö esiintyy myös Pac-Man Google Doodlessa niin sanottuna "pääsiäismunana". [10] Tässä, tasolla 256, voidaan havaita " kuoleman näyttö ", ja itse tasoa kutsutaan " jaetun näytön tasoksi ". Harrastajat ovat purkaneet lähdekoodin yrittääkseen korjata virheen muokkaamalla peliä .

Saman ongelman väitettiin esiintyneen Sid Meier's Civilization -pelissä, joka tunnetaan nimellä Nuclear Gandhi [11] . Legendan mukaan jossain vaiheessa pelissä erittäin rauhanomaisen Gandhin kanssa tapahtuu yli 0 - tasoista vihamielisyyttä, mikä voi johtaa ydinsotaan Gandhin kanssa. Itse asiassa tällainen myytti ilmestyi vasta Civilization V :n julkaisun myötä, jossa hänen tekoälynsä parametrilla , joka säätelee ydinaseiden luomista ja käyttöä , on korkein arvo 12, mikä ei ollut ristiriidassa sen tosiasian kanssa, että Gandhi on yksi. pelin rauhanomaisimpia johtajia [12] .

Toinen esimerkki on häiriö SimCity 2000 :ssa [13] . Pointti tässä on, että pelaajan budjetista tuli erittäin suuri, ja 2 31 läpimenon jälkeen siitä tuli yhtäkkiä negatiivinen. Peli päättyy tappioon.

Tämä häiriö on Diablo III :sta . Yhden korjaustiedoston 1.0.8 muutoksista johtuen pelin talous hajosi. Transaktioiden enimmäismäärää nostettiin miljoonasta 10 miljoonaan. Ostokustannus ylitti 32-bittisen tyypin kautta, ja kun toiminto peruutettiin, koko summa palautettiin. Eli pelaaja pysyi 2 32 pelivaluutan voitolla [14]

Katso myös

Muistiinpanot

  1. ↑ 1 2 Intel® 64- ja IA-32-arkkitehtuurien ohjelmistokehitysoppaat | Intel®-  ohjelmisto . software.intel.com. Haettu: 22.12.2017.
  2. ↑ x86 Exploitation 101: "Integer overflow" – lisätään vielä yksi… aaaaaaaaaa ja se on poissa  , gb_masterin /dev/null  (12. elokuuta 2015). Haettu 20. joulukuuta 2017.
  3. ↑ Web Application Security Consortium / Integer Overflows . projects.webappsec.org. Haettu: 8. joulukuuta 2017.
  4. ↑ 1 2 3 4 5 6 W. Dietz, P. Li, J. Regehr, V. Adve. Kokonaisluvun ylivuodon ymmärtäminen C/C:ssä #x002B; #x002B;  // 2012 34th International Conference on Software Engineering (ICSE). - Kesäkuu 2012. - S. 760-770 . - doi : 10.1109/icse.2012.6227142 .
  5. ↑ CWE - 2011 CWE/SANS 25 vaarallisinta ohjelmistovirhettä  . cwe.mitre.org. Haettu: 21.12.2017.
  6. ↑ ISO/IEC 9899 : 2011 - Tietotekniikka - Ohjelmointikielet -  C. www.iso.org. Haettu: 21.12.2017.
  7. ↑ 1 2 3 CWE-190: Integer Overflow tai Wraparound (3.0  ) . cwe.mitre.org. Haettu: 12.12.2017.
  8. ↑ CWE-119: Toimintojen virheellinen rajoittaminen muistipuskurin rajoissa (3.0  ) . cwe.mitre.org. Haettu: 12.12.2017.
  9. ↑ CWE-738: CERT C Secure Coding (2008-versio) Osa 04 - Kokonaisluvut (INT) (3.0  ) . cwe.mitre.org. Haettu: 15. joulukuuta 2017.
  10. ↑ Kartta 256 Glitch  , Pac - Man Wiki . Haettu 12. joulukuuta 2017.
  11. ↑ Nuclear Gandhi , Know Your Meme . Haettu 15. joulukuuta 2017.
  12. ↑ Artemy Leonov. Miksi Civilizationin "Nuclear Gandhi" -vikatarina on todennäköisesti keksitty . DTF (5. syyskuuta 2019). Käyttöönottopäivä: 24.10.2020.
  13. ↑ Sim City 2000 Integer Overflow . Blake O'Hare. Haettu: 12.12.2017.
  14. ↑ Diablo III Economy rikottu Integer Overflow Bug  , minimaxir | Max Woolfin blogi . Haettu 12. joulukuuta 2017.