💻 computer science

On Interaction Effects in Greybox Fuzzing

Dit paper introduceert MuoFuzz, een greybox fuzzer die interactie-effecten tussen mutatoren leert en benut om via een random walk de meest veelbelovende mutatorreeksen te selecteren, wat resulteert in een hogere codecoverage en het vinden van meer bugs dan bestaande tools zoals AFL++ en MOPT.

Oorspronkelijke auteurs: Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

Gepubliceerd 2026-04-24

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Kern: Fuzzing als een "Gokker"

Stel je voor dat je een enorme, complexe slotkast hebt (een computerprogramma) en je wilt weten of er een sleutelgat in zit dat je kunt openen zonder de sleutel te hebben. Dit is wat Greybox Fuzzing doet. Het is een robot die miljoenen willekeurige pogingen doet om een programma te laten crashen (en zo bugs te vinden).

De robot heeft een doos vol met mutators (gereedschappen). Sommige gereedschappen draaien een boutje los (een bit omkeren), andere hakken een stukje weg (een blok bytes verwijderen).

Hoe werkt het nu normaal?
De robot pakt een startpunt (een 'zaadje') en gebruikt willekeurig een reeks gereedschappen om het aan te passen.

Huidige aanpak (zoals bij AFL++): De robot heeft een vaste lijst met kansen. Gereedschap A heeft 4% kans, Gereedschap B heeft 3%. Hij pakt ze eruit alsof hij blindelings uit een hoed trekt.
Huidige aanpak (zoals bij MOPT): De robot leert welk gereedschap alleen het beste werkt, en gebruikt dat vaker. Maar hij kijkt niet naar wat er daarvoor is gebeurd.

Het Nieuwe Inzicht: Het is een Teamwerk

De auteurs van dit paper (Kitsios, Böhme en Bacchelli) hadden een idee: Misschien werkt gereedschap A alleen maar goed als je het na gereedschap B gebruikt.

Stel je voor dat je een auto repareert:

Als je eerst de motor verwijdert (gereedschap B) en daarna de wielen eraf haalt (gereedschap A), lukt het misschien perfect.
Maar als je eerst de wielen eraf haalt en daarna de motor verwijdert, valt de auto misschien in elkaar en werkt het niet.

De volgorde maakt dus uit! De huidige robots kijken niet naar deze interactie. Ze denken dat gereedschappen onafhankelijk van elkaar werken, maar dat is niet zo.

De Oplossing: MuoFuzz

De auteurs hebben een nieuwe robot gebouwd, genaamd MuoFuzz. Deze robot leert een heel slimme truc:

De Leerfase (Training): In het begin laat de robot een tijdje losjes proberen. Hij houdt een groot notitieboek bij: "Als ik gereedschap X gebruik, wat is de kans dat gereedschap Y daarna een goed resultaat geeft?"
- Vergelijking: Het is alsof je een chef-kok bent die leert welke ingrediënten goed samengaan. Als je eerst zout doet, werkt peper misschien beter dan als je eerst suiker doet.
De Gids-fase (Guided Mutation): Nadat hij heeft geleerd, gebruikt hij dit notitieboek. Als hij gereedschap X heeft gebruikt, kijkt hij in zijn boek en kiest hij met een hoge kans het gereedschap Y dat daar het beste bij past.
- Vergelijking: In plaats van blindelings uit een hoed te trekken, loopt de robot een pad af dat hij zelf heeft uitgezocht. Hij weet: "Na stap 1, is stap 2 het meest kansrijk."

Wat hebben ze ontdekt?

Ze hebben dit getest op echte software (zoals webbrowsers en PDF-lezers) en vergeleken met de beste robots die er nu zijn (AFL++ en MOPT).

Meer dekking: MuoFuzz vond in 10 van de 13 gevallen meer "nieuwe plekken" in de code dan de anderen.
Sneller: MuoFuzz bereikte de resultaten van de andere robots in minder tijd.
Meer bugs: MuoFuzz vond vier bugs die de andere robots gemist hadden, en zelfs een bug die niemand anders vond.

Waarom werkt dit?

De robot leert dat bepaalde combinaties van mutaties (gereedschappen) een "chemische reactie" veroorzaken die de software dwingt om diep in zijn code te kijken, waar de bugs vaak zitten.

Interessant detail: Soms werkt het beste om te beginnen met een willekeurig gereedschap, en pas daarna de slimme volgorde te volgen. Als je te specifiek begint, wordt de robot te voorspelbaar en mist hij creatieve oplossingen.

Conclusie

Dit onderzoek toont aan dat we bij het testen van software niet alleen moeten kijken naar welke gereedschappen we gebruiken, maar vooral naar in welke volgorde we ze gebruiken.

De boodschap in één zin:
Net zoals een goede kok weet dat de volgorde van ingrediënten de smaak bepaalt, weet MuoFuzz dat de volgorde van test-pogingen bepaalt of hij een software-bug vindt of niet. Door te leren welke stappen het beste op elkaar volgen, wordt de robot veel slimmer en efficiënter.

Titel: Over Interactie-effecten in Greybox Fuzzing

Auteurs: Konstantinos Kitsios, Marcel Böhme en Alberto Bacchelli
Publicatie: ICSE 2026 (voorgesteld)

1. Het Probleem

Greybox fuzzing is een geautomatiseerde softwaretesttechniek die nieuwe testinput genereert door mutaties (zoals bit-flips of het verwijderen van bytes) toe te passen op bestaande "seed"-inputs. De efficiëntie van deze techniek hangt sterk af van de mutatiestrategie: de volgorde en combinatie van mutatoren die worden toegepast.

Huidige state-of-the-art fuzzers, zoals AFL++, gebruiken een vaste strategie waarbij elke mutator een statische, vooraf gedefinieerde selectieprobabiliteit heeft. Zelfs geavanceerdere varianten zoals MOPT passen deze kansen wel aan, maar doen dit onafhankelijk van elkaar. Ze optimaliseren de kans dat een specifieke mutator interessant is, zonder rekening te houden met de mutator die daarvoor is gebruikt.

De auteurs hypothetiseren dat er een interactie-effect bestaat tussen mutatoren: de volgorde waarin mutatoren worden toegepast, beïnvloedt de kans op het genereren van "interessante input" (input die nieuwe code-dekking oplevert). Als mutator A gevolgd wordt door mutator B, kan dit effectiever zijn dan de som van hun individuele prestaties, maar dit wordt door bestaande tools genegeerd.

2. Methodologie

De studie volgt een drieledige aanpak: het empirisch bewijzen van het interactie-effect, het ontwikkelen van een nieuwe strategie, en het valideren hiervan.

A. Empirisch Onderzoek naar Interactie-effecten

Om te bewijzen dat mutatoren interactie vertonen, hebben de auteurs een dataset verzameld door AFL++ uit te voeren op 13 doelprogramma's. Ze beperkten de mutatiereeksen tot lengte 2 ( $\langle i, j \rangle$ ) om de interactie tussen paren te meten.

Model: Ze pasten een lineair model toe met een interactieterm ( $\gamma_{ij}$ $γ_{ij}$ ).
- $N(i, j) = \mu + \alpha_i + \beta_j + \gamma_{ij}$
- Waarbij $\gamma_{ij}$ de interactie-effecten vertegenwoordigt.
Statistische Analyse: Een tweeweg-ANOVA (Analysis of Variance) werd uitgevoerd. De resultaten toonden aan dat de interactieterm statistisch significant is ( $p < 0.0001$ ) en een aanzienlijk deel van de variantie in het aantal interessante inputs verklaart. Dit bevestigt dat de volgorde van mutatoren ertoe doet.

B. Ontwikkeling van MuoFuzz

Op basis van deze bevindingen hebben de auteurs MuoFuzz ontwikkeld. Dit is een greybox fuzzer die de selectie van de volgende mutator conditioneert op de vorige.

Twee Fasen:
1. Trainingsfase: Gedurende een initiële periode (bijv. 1 uur) verzamelt de fuzzer data over welke paren $\langle i, j \rangle$ interessante input genereren. Ze bouwen een matrix $N(i, j)$ met het aantal succesvolle paren.
2. Gestuurde Mutatiefase: De fuzzer gebruikt de geleerde conditionele waarschijnlijkheid $P(m_n = j | m_{n-1} = i)$ om mutatiereeksen te genereren via een Markov-willekeurige wandeling (random walk). De kans om mutator $j$ te kiezen, is evenredig met het aantal keren dat het succesvol was na mutator $i$ .
Hyperparameters: De lengte van de reeks en de keuze van de eerste mutator worden geoptimaliseerd (o.a. via Multi-Armed Bandit algoritmen), maar de kerninnovatie is het conditionele selectiemechanisme.

3. Belangrijkste Bijdragen

Empirisch Bewijs: Het leveren van statistisch onderbouwd bewijs dat er een significant interactie-effect bestaat tussen mutatoren in greybox fuzzing, wat de onafhankelijkheidsaanname van bestaande tools weerlegt.
MuoFuzz: Een nieuwe mutatiestrategie die conditionele kansen leert en toepast. In tegenstelling tot MOPT (die mutatoren isoleert) en AFL++ (die vaste kansen gebruikt), leert MuoFuzz de afhankelijkheid tussen opeenvolgende mutatoren.
Uitgebreide Evaluatie: Een robuuste vergelijking met state-of-the-art fuzzers (AFL++ en MOPT) op de FuzzBench en MAGMA benchmarks, inclusief een ablatiestudie om de impact van specifieke componenten te isoleren.

4. Resultaten

De experimenten werden uitgevoerd op 13 programma's van FuzzBench en 8 programma's van MAGMA (met bekende bugs).

Code Dekking:
- MuoFuzz behaalde de hoogste code-dekking in 10 van de 13 FuzzBench-programma's.
- Het was statistisch significant beter dan AFL++ in 9/13 programma's en beter dan MOPT in 8/13 programma's.
- Snelheid: MuoFuzz bereikte de dekking die AFL++ na 24 uur bereikte, gemiddeld al na 15 uur (een besparing van 9 uur). Voor MOPT was dit gemiddeld 16,5 uur.
Bug Opsporing (MAGMA):
- MuoFuzz vond 4 bugs die AFL++ miste.
- MuoFuzz vond 1 bug die zowel AFL++ als MOPT misten.
- In totaal vond MuoFuzz 3 unieke bugs in vergelijking met AFL++.
Ablatie Studie:
- Het gebruik van meer dan één vorige mutator als context (bijv. $p=2$ ) leidde tot slechtere prestaties door de "curse of dimensionality" (te veel lege combinaties).
- Het willekeurig kiezen van de eerste mutator bleek beter dan het gewogen kiezen van de meest succesvolle eerste mutator, omdat dit de exploratie van de fuzzer behoudt.
- Cross-programma generalisatie (leren op het ene programma en toepassen op het andere) werkte niet goed; per programma trainen bleef superieur.

5. Betekenis en Conclusie

Dit onderzoek toont aan dat de huidige aanpak van fuzzing, waarbij mutatoren als onafhankelijke eenheden worden behandeld, suboptimaal is. Door de interactie tussen mutatoren te modelleren en te leren, kan de efficiëntie van fuzzing aanzienlijk worden verbeterd.

Praktische Impact: MuoFuzz demonstreert dat het leren van sequentiële patronen leidt tot snellere code-dekking en het vinden van unieke bugs die met traditionele methoden worden gemist.
Toekomstperspectief: De auteurs vergelijken hun methode met bigram-taalmodellen uit de NLP-wereld. Dit opent de deur voor het toepassen van geavanceerdere sequentiële modellen (zoals RNN's of Transformers) om nog complexere mutatiepatronen te leren, en suggereert dat dezelfde logica ook kan worden toegepast op de locatie van mutaties binnen een input.

Kortom, MuoFuzz bewijst dat het begrijpen van de context van een mutatie (wat ging er net vooraf?) cruciaal is voor het maximaliseren van de effectiviteit van fuzzing.