Diplomityöstä: mikä se nyt oikeastaan oli

Tosiaan, tein diplomityön joka on nyt hyväksytty ja olen kypsä aikuinen ja valmis diplomi-insinööri. Viimeiset puoli vuotta olen vastaillut ihmisten kysymykseen "niin mistä oikeastaan teet sen työn?", ja olen mutissut jotain epäselvää geneettisistä algoritmeista, tietoturvatestauksesta ja optimoinnista. Koska kaikkia on kiinnostanut ennenkin, niin kerron nyt tässä postauksessa mitä olen tehnyt. Ehkä se selvittää omiakin ajatuksia, ja antaa muille paremman mahdollisuuden ymmärtää mihin olen aikani laittanut. Varoitan että kaikki tässä on vähän yksinkertaistettua, mutta saattaa silti tietokoneisiin perehtymättömälle kuulostaa vaikealta.

Pitäkää hatustanne kiinni, nyt mennään syvään päähän. Tai ainakin keskimääräistä saliblogia syvempään.

Eli kaikki alkaa alusta. Fuzzaamisesta. Termi on todennäköisesti outo, mutta kyse on tietokoneen ohjelmiston testauksesta, jossa ohjelmaa testataan semi-satunnaisella inputilla. Tällä tavalla yritetään löytää koodista höpöjä, jotka kaatavat ohjelman. Eli fuzzaus on onnistunut silloin kun se särkee ohjelman mahdollisimman monella tavalla ja useasti, mikä saattaa kuulostaa nurinkuriselta testaukselta asiaan tutustumattomasta.

"Mitä hyötyä on testata ohjelmaa satunnaisella syötteellä, ketä kiinnostaa jos softa kaatuu kun siihen työnnetään jotain mitä se ei normaalisti käsittele?"

Yksi sana: tietoturva. Ja toinenkin sana: vakaus. Ensinnäkin, fuzzaus on hyvä löytämään C/C++ kielistä muistin käpistelyn virheitä, joka saattaa aiheuttaa haavoittuvuuksia (puskurin ylikirjoitus/-luku, muuttujan käyttö ennen muistin varausta yms. muistijutut). Esimerkiksi ylikirjoituksella voidaan tietyissä tilanteissa ohjata ohjelman suoritusta mielivaltaisiin osoitteisiin tai aiheuttaa muuta hauskaa esim. stack smashin muodossa.

Toisekseen, vakaus. Se, että ohjelma ei kaadu heti kun yksi bitti on vinossa ei ole "mukava lisäominaisuus", vaan sen kuuluisi olla ihan normaalia toiminnallisuutta.

Eniveis, sitä on fuzzailu. Fuzzauksessa voi testata esimerkiksi tiedostojen latausta Gimpissä, itse testailin pari vuotta sitten sitä. Aluksi kerätään jonkinlainen määrä valideja kuvafiluja, jotka toimivat normaalisti. Seuraavaksi jyräytetään tiedostot fuzzerin läpi, joka tekee tiedostoihin korruptioita. Lopputuloksena tulevat semi-korruptoituneet tiedostot työnnetään ohjelmaan ja katsotaan mitä tapahtuu: löytyykö ylivuotoja vai hanskaako ohjelma särkyneen inputin erittäin hyvin, ellei täydellisesti.

Keskiverto-ohjelma kokeilee parsia fuzzattua inputtia

Homma kuulostaa siis periaatteessa helpolta. Ja sitä se onkin, kirjoitin kandidaatintyön muutama vuosi takaperin tällaisella simppelillä setupilla. Ongelma tässä lähestymistavassa on vain se, että tällainen black-box on kohtuullisen tehoton lähestymistapa. Black-boxilla tarkoitetaan siis sitä, että testaus ei hyödynnä lähdekoodia, tai yhtään mitään muutakaan informaatiota testauksessa, vaan pukkaa korruptiota sen kummemmin ajattelematta miksi. Ja tässä olikin sauma allekirjoittaneen diplomityölle.

Fuzzerit yleensä käplivät tiedostoja epäsatunnaisen satunnaisesti. Pseudosatunnaisnumerogeneraattori on kovassa käytössä, mutta yleensä fuzzaus tapahtuu myös jossain määrin säännönmukaisesti. On olemassa erilaisia mutatorifunktioita, jotka käsittelevät validia tiedostoa tietyllä tavalla: yksi poistaa 8 bittiä, toinen lisää satunnaisen merkkijonon jokaisen numeron tilalle, kolmas siirtelee satunnaisen mittaisia pätkiä dataa sinne tänne ja niin päin pois.

Kaikki funktiot eivät kuitenkaan toimi yhtä hyvin kaikilla inputeilla. Toinen syöte saattaa vaatia erittäin hienovaraisia muutoksia ettei tiedoston rakenne räjähdä käsiin, kun taas toista inputtia saa möykyttää urakalla ilman havaittavia vaikutuksia. Ohjelmat myös reagoivat eri tavalla erilaisiin muutoksiin. On siis tarpeen, että nämä funktiot optimoidaan tavalla tai toisella fuzzausprosessin aikana.

Diplomityö to the rescue

Ja tätä varten kehittelin geneettisen algoritmin, jonka pitäisi optimoida eri funktioiden todennäköisyydet. Normaalissa tilaanteessa fuzzeri ajaa yhden tai useamman mutatori-funktion vakiotodennäköisyydellä, ottamatta huomioon miten hyvin mutatorifunktio sopii kyseiseen tilanteeseen. Geneettinen algoritmi pyrkii kuitenkin optimoimaan nämä todennäköisyydet kulloiseenkin tilanteeseen sopivasti.

Millä perusteella geneettinen algoritmi sitten tietää, mikä on hyvä ja mikä huono funktio? Testikattavuuden ja ohjelman kaatumistiheyden perusteella. Ohjelman ajon aikana koodista ajetaan eri pätkiä. Mitä laajemman kattavuuden jokin mutatorifunktio saavuttaa, sitä paremmaksi se luokitellaan. Myöskin, mitä enemmän funktio kaataa testattavaa ohjelmaa, niin jälleen sitä parempi se on. Tavoitteena on kuitenkin pistää koko softa mahdollisimman paskaksi, näin kansankielellä ilmaistuna.

Ja lopputulos oli positiivinen. Optimointi tosiaan parantaa lopputulosta (eli fuzzaamisen kattavuutta ja kaatumistiheyttä) ainakin kolmella eri testatulla ohjelmalla. Eli ei se puolivuotinen hukkaan mennyt. Jos fuzzaus aiheena kiinnostaa enemmän, niin suosittelen seuraavia askeleita:

• Lue jonkun fiksumman kirjoittamia tekstejä
• Hanki AFL (american-fuzzy-lop)

Oliko riittävän ylimalkaista? AFL on näppärä fuzzaus-suite, joka sisältää käytännössä kaiken tärkeän instrumentoinnista fuzzaukseen ja optimointiin, jäljelle jää vain open-source ohjelman päättäminen ja validien samplejen valkkaus. AFL ei ehkä ole paras tai joustavin fuzzeri, mutta siitä huolimatta sillä voisi olla hyvä aloittaa sen all-in-one luonteen vuoksi (joskin se sisältää pari pöljää rajoitusta). Fuzzauksesta löytyy kohtuullisen paljon enemmän tai vähemmän laadukkaita tutkimuspapereita Google Scholarista, joten suosittelen sieltä myös etsimään tietoa aiheesta. Tai jostain kirjasta, niissä on yleensä tietoa. Tai täältä. En ole yleensä hyvä suosittelemaan luettavaa.

Ilmeeni kun heap-use-after-free on address 0x7f7ddab8c084 at pc 0x403c8c bp 0x7fff87fb82d0 sp 0x7fff87fb82c8

Että sellainen työ. En kyllä tiedä selvensikö tämä mitään. Ehkä tästä saa kuitenkin jonkinlaisen yleiskuvan. Parempi tämäkin on kuin se keskimäärin kahden kaljan jälkeen antamani "joo siellä on bittejä ja sitten optimoidaan nollat fuzzauksessa"-vastaus.

Nyt kun on tietotekniikasta kerran puhe, niin kerrotaan vielä tämä juttu mikä on vaivannut jo pitkään. Kaija Koo laulaa Kaunis Rietas Onnellinen -kappaleessa "Ja mä voin luvata ettei satuta kun kaiken pudottaa", mutta joskus elämässä DROP DATABASE komennon väärään paikkaan ajaneena rohkenen olla eri mieltä.

 

Kirjoittaja on diplomi-insinööri, joka sai jo viime lauantaina tietää mitä tarkoittaa kuvauskieli.