On Interaction Effects in Greybox Fuzzing

1. Problemstellung

Mutation-basiertes Greybox-Fuzzing (z. B. AFL++) ist eine weit verbreitete Technik zur automatisierten Softwaretests, die durch das Mutieren von Seed-Eingaben neue Testfälle generiert. Der Kernprozess besteht darin, eine Sequenz von Mutatoren (z. B. Bit-Flip, Byte-Deletion) auf einen Seed anzuwenden.

Das zentrale Problem, das in diesem Paper adressiert wird, ist die Annahme der Unabhängigkeit bei der Auswahl von Mutatoren.

• Bestehende Ansätze: Tools wie AFL++ verwenden feste Wahrscheinlichkeiten für jeden der 32 Mutatoren. Fortgeschrittenere Ansätze wie MOPT optimieren diese Wahrscheinlichkeiten, behandeln aber jeden Mutator als unabhängige Einheit. Das bedeutet, die Wahrscheinlichkeit, einen Mutator $m_n$ auszuwählen, hängt nicht davon ab, welcher Mutator $m_{n-1}$ zuvor gewählt wurde.
• Hypothese der Autoren: Es existiert ein Interaktionseffekt zwischen aufeinanderfolgenden Mutatoren. Bestimmte Kombinationen von Mutatoren (Sequenzen) führen signifikant häufiger zu „interessanten" Eingaben (d. h. Eingaben, die neue Code-Pfade abdecken oder Bugs finden) als andere, unabhängig von den einzelnen Mutatoren.

2. Methodik

Die Autoren verfolgen einen dreistufigen Ansatz:

A. Empirische Untersuchung des Interaktionseffekts (RQ1)

Um die Existenz von Interaktionseffekten zu beweisen, wurde ein Datensatz erstellt:

• Datenerhebung: AFL++ wurde auf 13 Zielprogrammen (aus dem FuzzBench-Benchmark) mit modifizierten Parametern ausgeführt.
  • Die Länge der Mutator-Sequenzen wurde auf $l=2$ begrenzt.
  • Mutatoren wurden gleichverteilt zufällig ausgewählt (statt nach festen Wahrscheinlichkeiten), um eine ausgewogene Datengrundlage zu schaffen.
  • Eine Matrix $N(i, j)$ wurde geführt, die zählt, wie oft die Sequenz $\langle i, j \rangle$ zu einer neuen Code-Abdeckung führte.
• Modellierung: Ein lineares Modell wurde angepasst: $\hat{N}(i, j) = \mu + \alpha_i + \beta_j + \gamma_{ij}$.
  • $\alpha_i$ und $\beta_j$ repräsentieren den individuellen Effekt der Mutatoren.
  • $\gamma_{ij}$ repräsentiert den Interaktionseffekt.
• Statistische Analyse: Eine Zwei-Wege-ANOVA (Analysis of Variance) bestätigte, dass der Interaktionsterm $\gamma_{ij}$ statistisch signifikant ist ($p < 0.0001$). Das bedeutet, die Kombination von Mutatoren beeinflusst den Erfolg signifikant mehr als die Summe ihrer Einzelwirkungen.

B. Entwicklung von MuoFuzz

Basierend auf diesem Befund wurde MuoFuzz entwickelt, ein Fuzzer, der diese Interaktionen nutzt.

• Zwei-Phasen-Ansatz:
  1. Trainingsphase: Für eine festgelegte Zeit (z. B. 1 Stunde) wird AFL++ mit den oben genannten Modifikationen ausgeführt, um die Matrix $N(i, j)$ zu füllen. Daraus wird die bedingte Wahrscheinlichkeit berechnet:
     $$Pr(m_n = j | m_{n-1} = i) = \frac{N(i, j)}{\sum_{k} N(i, k)}$$
     Dies entspricht einem Markov-Modell (Bigram-Modell), bei dem die Wahl des nächsten Mutators vom vorherigen abhängt.
  2. Geführte Mutationsphase: Der Fuzzer generiert Sequenzen durch Abtastung (Random Walk) aus der gelernten bedingten Wahrscheinlichkeitsverteilung.
• Hyperparameter: Die Länge der Sequenz wird dynamisch mittels eines Multi-Armed-Bandit-Algorithmus ($\epsilon$-greedy) optimiert. Der erste Mutator wird zufällig gewählt (was sich als effektiver erwies als eine gewichtete Auswahl).

C. Evaluierung

MuoFuzz wurde gegen zwei State-of-the-Art-Baselines verglichen:

• AFL++: Verwendet feste Wahrscheinlichkeiten.
• MOPT: Optimiert die Wahrscheinlichkeiten einzelner Mutatoren isoliert (ohne Interaktionen).
• Benchmarks: FuzzBench (13 Programme, Fokus auf Code-Abdeckung) und MAGMA (8 Programme, Fokus auf gefundene Bugs).
• Statistik: Jeder Test wurde 20–30 Mal über 24 Stunden wiederholt, um die inhärente Zufälligkeit des Fuzzings auszugleichen (Mann-Whitney-U-Test).

3. Wichtige Ergebnisse

Code-Abdeckung (RQ2)

• MuoFuzz erreichte in 9 von 13 Programmen eine signifikant höhere Code-Abdeckung als AFL++ und in 8 von 13 Programmen eine signifikant höhere Abdeckung als MOPT.
• Effizienz: MuoFuzz benötigte im Median nur 15 Stunden, um die Abdeckung zu erreichen, die AFL++ nach 24 Stunden erreichte (und 16,5 Stunden für MOPT).
• In Programmen, in denen kein starker Interaktionseffekt vorlag (z. B. json, openssl), zeigte MuoFuzz keine signifikante Verbesserung, was die Hypothese untermauert, dass der Erfolg von der Existenz dieser Effekte abhängt.

Bug-Findung (RQ3)

• Auf dem MAGMA-Benchmark fand MuoFuzz 4 Bugs, die AFL++ verpasste.
• AFL++ fand nur 1 Bug, den MuoFuzz verpasste (TIF001), was auf die inhärente Zufälligkeit zurückgeführt wird.
• Im Vergleich zu MOPT fand MuoFuzz einen einzigartigen Bug (SQL010), den MOPT verpasste, während MOPT einen anderen (SSL001) fand, den MuoFuzz verpasste. Dies zeigt, dass die unterschiedlichen Mutationsstrategien zu unterschiedlichen Pfaden im Programm führen.

Ablationsstudie (RQ4)

Die Studie bestätigte, dass die Leistung von MuoFuzz auf dem Interaktionseffekt beruht:

• Die Verwendung von mehr als einem vorherigen Mutator als Kontext ($p=2$) führte aufgrund des „Fluchs der Dimensionalität" (zu viele leere Kombinationen) zu schlechteren Ergebnissen.
• Eine zufällige Matrix anstelle der gelernten Matrix führte zu schlechteren Ergebnissen.
• Eine gewichtete Auswahl des ersten Mutators war schlechter als eine zufällige Auswahl, da sie die Exploration reduzierte.

4. Hauptbeiträge

1. Empirischer Nachweis: Der Nachweis, dass Interaktionseffekte zwischen Mutatoren in Greybox-Fuzzern existieren und statistisch signifikant sind.
2. MuoFuzz: Die Implementierung einer neuen Mutationsstrategie, die bedingte Wahrscheinlichkeiten (Markov-Ketten) nutzt, um Mutator-Sequenzen zu generieren.
3. Leistungsnachweis: Der Nachweis, dass MuoFuzz sowohl in der Code-Abdeckung als auch in der Bug-Findung State-of-the-Art-Tools (AFL++, MOPT) übertrifft, insbesondere durch die effizientere Erkundung des Suchraums.

5. Bedeutung und Implikationen

• Paradigmenwechsel: Die Arbeit zeigt, dass die Annahme der Unabhängigkeit von Mutatoren in der Fuzzing-Forschung suboptimal ist. Die Berücksichtigung des Kontexts (des vorherigen Mutators) ist entscheidend für die Effizienz.
• Inspiration aus NLP: Die Methode ähnelt Bigram-Sprachmodellen (NLP). Die Autoren schlagen vor, dass fortgeschrittene Techniken wie RNNs oder Transformer für die Sequenzgenerierung von Mutatoren zukünftig eingesetzt werden könnten.
• Praktische Anwendung: Da MuoFuzz auf AFL++ aufbaut und nur geringe Overheads hat, ist es leicht integrierbar. Es demonstriert, dass intelligente Mutationsstrategien (die den Kontext nutzen) effektiver sind als reine Optimierung einzelner Wahrscheinlichkeiten.

Zusammenfassend beweist das Paper, dass das Verständnis und die Nutzung von Interaktionseffekten zwischen Mutatoren ein bisher ungenutzter Hebel ist, um Greybox-Fuzzer deutlich leistungsfähiger zu machen.