Papers we love: Automatisch repareren van bugs, hoe doe je dat?

Bugs. Out-of-bounds errors, integer overflows, divide by zero errors. Wie kent ze niet? Het zijn allemaal bugs met eenzelfde achtergrond en hebben gemeen dat ze nogal eens optreden, zeker in de meer low-level talen. Wat nu als je dit soort fouten automatisch zou kunnen herstellen? Dat is precies de vraag die de auteurs van de deze paper zich stelden. De paper van deze maand heet Automatic error elimination by horizontal code transfer across multiple applications en komt bij MIT CSAIL vandaan.

Het uitgangspunt van het artikel is als volgt: functionaliteit in software wordt door veel verschillende codebases gerealiseerd. Enerzijds zijn dit implementaties van standaarden, zoals bestandsformaten en communicatieprotocollen, anderzijds zijn het juist verschillende versies van codebases, zoals nieuwe (bugfix) releases van een specifiek programma. Wanneer er nu een bug wordt gevonden in een stuk code is er volgens de auteurs grote kans dat er ergens een stuk code is wat wellicht wel correct zou werken. Er is immers sprake van een grote diversiteit aan code die hetzelfde resultaat wil kunnen bereiken. Een alternatieve implementatie kan een bugfix release zijn van hetzelfde pakken, maar ook simpelweg een alternatieve implementatie van een standaard zoals een bestandsformaat.

De auteurs beginnen met dit uitgangspunt en willen de drie genoemde soorten fouten automatisch gepatched laten worden. Ze willen, geheel automatisch, de binary van de applicatie aanpassen zodat deze zich dan wel correct zal gedragen, of op zijn minst veilig termineert. Om dit te doen wordt er foutieve en correcte input uitgevoerd met de applicatie in kwestie. Hiermee is er dus een automatische manier om te beoordelen of een applicatie om kan gaan met de data in kwestie en of deze ook geraakt wordt door dezelfde fout. Door dit ook te doen bij donor applicaties kan er gekeken worden of deze programma’s wel correct met de betreffende input omgaan. Wanneer er nu een applicatie gevonden wordt waarbij er geen crash optreed dan zal deze als donor dienen voor de genoemde ‘code transfer’: er wordt een stukje code uit de donor gehaald en in de originele applicatie geplaatst. Het komt mij dan ook over als een soort genetische modificatie van het oorspronkelijke programma.

De manier waarop dit proces is ingericht vind ik erg interessant: het is primair een multidisciplinaire aanpak. In een notendop ziet de gehele cyclus er als volgt uit. Detecteer dat een applicatie geraakt wordt door een fout. Geef, naast deze foutieve input, ook een seed waarde mee die de applicatie correct laat functioneren. Kies vervolgens alternatieve applicaties die ook met deze inputs om kunnen gaan. Deze applicatie hoeft niet hetzelfde te zijn, er kunnen bijvoorbeeld twee verschillende image viewers worden gebruikt. Daarna instrumenteer je de foutieve, maar ook de de donor applicatie en beoordeel je bij iedere conditional (JMP, JNZ, etc) of deze wordt beïnvloed door de meegegeven input. Het framework is dus in staat om een binary als zodanig te instrumenteren. Als er nu een pad gevonden wordt waarbij de foutieve input een andere route kiest dan bij de correcte input is er een potentiële oorzaak gevonden. Er wordt vervolgens een symbolische expressie gemaakt van het relevante deel van de binary, waarna deze wordt vereenvoudigd en ‘vertaald’. Dit vertalen houdt in dat er een automatische mapping wordt gemaakt van de data-representatie uit het ene programma naar de representatie van de andere. Twee applicaties kunnen, en zullen, immers op een andere manier de betreffende data representeren.

Natuurlijk geef ik nu een sterk vereenvoudigde representatie van de uitgevoerde stappen, maar dat is precies de kracht van de paper. Het geeft in eerste instantie een beeld dat, in ieder geval bij mij, erg veel vragen en zelfs scepsis opriep. In de sectie over design and implementation wordt hier verder op ingegaan en volgt er toelichting. Voor iedere stap binnen het proces worden andere specialismes gebruikt, waarbij je moet denken aan SMT solvers, debugging tools, memory analysis, dynamic code instrumentation, optimizers en graph traversal. Hierdoor is de aanpak erg multidisciplinair komt deze op mij over als een echte, pure engineering aanpak: los ieder probleem op binnen het domein waar het eigenlijk thuis hoort en doe dit ook met de technieken en tools die daar het meest geschikt voor zijn.

Hierdoor heb ik ook een dubbel gevoel overgehouden na deze paper. Ondanks het interessante perspectief heb ik niet het idee dat het elimineren van fouten middels dit soort software-donoren een levensvatbaar idee is. Ondanks de goede resultaten zijn de selecties nog lastig, zeker naarmate de variëteit toeneemt. Daarnaast zijn de type fouten wat mij betreft beter te ondervangen met specifieke taal-constructies (zie bijvoorbeeld memory safety guarantees of IntFlow). Wat ik wel enorm lovenswaardig vind is de denk-, en werkwijze van de auteurs. Er wordt een wisselende en grote hoeveelheid theorie en techniek ingeschakeld om tot een oplossing te komen van het probleem in kwestie. Daarnaast is het door de grote lijst aan referenties ook een leuk startpunt voor een avondje jezelf verliezen in een groot wiki-hole van gave kennis. Wat mij betreft is het uiteindelijk dus wel een aanrader om te lezen.


Over deze papers we love: binnen Sogyo hebben we de traditie dat we maandelijks een nieuwsbrief rondsturen. De nieuwsbrief gaat veel over interne feitjes, echter sinds februari 2015 verzorgd Kevin van der Vlist het topic: papers we love. Hij deelt met ons papers die interessant zijn om te lezen en ons kunnen inspireren. De topic is uitgegroeid tot een mooie verzameling die we ook graag hier willen delen.