In einer stürmischen Herbstnacht im Jahr 1988 saß Barton Miller, Informatikprofessor an der University of Wisconsin–Madison, zu Hause an seinem Terminal. Über ein 1200-Baud-Modem und eine analoge Telefonleitung war er mit einer UNIX-Workstation der Universität verbunden, während draußen ein heftiges Gewitter tobte. Jeder Blitzeinschlag induzierte elektromagnetisches Rauschen in der Telefonleitung und verfälschte seine getippten Befehle durch zufällige Byte-Sequenzen.

Was dann geschah, verblüffte ihn: Immer wenn das Leitungsrauschen verstümmelte Bytes in vermeintlich ausgereifte Standard-UNIX-Werkzeuge wie vi, cc, awk, sed, csh oder indent einspeiste, gaben diese Programme nicht etwa eine saubere Fehlermeldung aus – sie stürzten reihenweise mit Speicherzugriffsverletzungen (SIGSEGV, Segmentation Fault) ab oder froren in Endlosschleifen ein.

Miller machte daraus ein Forschungsprojekt für seinen Betriebssystemkurs und ließ Studierende einen Generator für Zufallszeichenströme bauen, den er „Fuzz“ nannte. Das Ergebnis erschütterte die Fachwelt: 25 % bis 33 % aller getesteten UNIX-Standardprogramme auf sieben verschiedenen UNIX-Systemen stürzten bei rein zufälligen Eingaben sofort ab.

Mehr als 35 Jahre später hat sich Fuzzing (Fuzz Testing) von diesem blinden Rauschgenerator zur erfolgreichsten automatisierten Methode für das Aufspüren von Sicherheitslücken in der Informatik entwickelt – durch die Verschmelzung von Compiler-Instrumentierung, evolutionären genetischen Algorithmen, SMT-Constraint-Solvern und virtuellem Shadow-Memory-Mapping. Allein Googles kontinuierliche Fuzzing-Plattform OSS-Fuzz hat in kritischen Open-Source-Projekten wie OpenSSL, SQLite, FFmpeg und dem Linux-Kernel über 10.000 Sicherheitslücken und mehr als 36.000 Bugs vollautomatisch entdeckt.

Warum übersehen tausende handgeschriebene Unit-Tests katastrophale Speicherfehler, während automatisierte Mutation sie mühelos freilegt? Dieser Artikel analysiert die mathematischen und systemtechnischen Grundlagen des modernen Fuzzings: die kombinatorische Explosion des Eingaberaums, die vier Fuzzing-Paradigmen, die Architektur von AFL / AFL++ / LibFuzzer (Edge-Coverage-Bitmaps, der mathematische Beweis des 1-Bit-Rechtsshifts >> 1, Forkserver und Markov-Power-Schedules), AddressSanitizer (ASan) sowie Andreas Zellers Delta Debugging (ddmin).

Kapitel 1: Die kombinatorische Explosion des Eingaberaums und der Laternenpfahl-Effekt

1.1 Ein 64-Byte-Puffer umfasst $10^{154}$ mögliche Zustände

Warum können manuelle Unit-Tests Softwarefehler niemals vollständig eliminieren? Der Grund liegt in der kombinatorischen Explosion des Eingaberaums. Betrachten wir eine einfache C-Funktion, die einen nur $N = 64$ Byte langen Paket- oder Bild-Header einliest. Da jedes Byte $|\Sigma| = 2^8 = 256$ Werte annehmen kann, beträgt die Gesamtzahl aller möglichen 64-Byte-Eingaben:

Zum Vergleich: Die Eddington-Zahl (die geschätzte Anzahl aller Protonen im beobachtbaren Universum) liegt bei lediglich ca. $10^{80}$. Selbst wenn alle Prozessoren der Erde seit dem Urknall vor 13,8 Milliarden Jahren jede Sekunde eine Billion ($10^{12}$) Tests ausgeführt hätten, wäre nicht einmal der Bruchteil von $10^{-124}$ dieses winzigen 64-Byte-Raums abgedeckt.

1.2 Der Laternenpfahl-Effekt (Streetlight Effect) und die „Weird Machine“

Beim Schreiben manueller Unit-Tests unterliegen Entwickler unweigerlich dem Laternenpfahl-Effekt (Beobachtungsverzerrung): Wie ein Nachtschwärmer, der seinen verlorenen Schlüssel nur direkt unter der Straßenlaterne sucht, weil es dort hell ist, testen Menschen nur spezifizierte Normalfälle und offensichtliche Randwerte (0, -1, NULL), an die sie beim Programmieren ohnehin gedacht haben. Kritische Schwachstellen verbergen sich jedoch im Dunkeln – in der sogenannten „Weird Machine“ (Bratus et al.), dem unbeabsichtigten Zustandsautomaten aus subtilen Parser-Annahmen und Integer-Überläufen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

int parse_image_chunk(const uint8_t *buf, size_t len) {
    if (len < 16) return -1;
    uint32_t magic  = *(const uint32_t *)(buf + 0);
    uint16_t width  = *(const uint16_t *)(buf + 4);
    uint16_t height = *(const uint16_t *)(buf + 6);
    uint8_t  flags  = buf[8];

    if (magic != 0x494D4721) return -1;          // Erwartet Magic "IMG!"
    if (width == 0 || height == 0) return -1;    // Entwickler hat 0-Randwert getestet!

    uint16_t alloc_size = width * height;        // [BUG] 16-Bit-Integer-Überlauf!
    if (flags & 0x80) alloc_size += 16;
    uint8_t *pixel_buf = malloc(alloc_size);     // Allokiert nur 0 oder 16 Bytes
    memcpy(pixel_buf, buf + 16, (size_t)width * height); // Kopiert 65.536 Bytes -> Heap-Überlauf!
    ...
}

Für width = 256, height = 256 ergibt $256 \times 256 = 65536 \equiv 0 \pmod{2^{16}}$ einen 16-Bit-Integer-Wraparound. malloc(16) reserviert einen winzigen Puffer, in den memcpy anschließend 64 KB schreibt und den gesamten Heap korrumpiert.

Kapitel 2: Die vier Paradigmen des Fuzzings

Um Barrieren wie if (magic != 0x494D4721) (Zufallswahrscheinlichkeit $2^{-32} \approx 1 : 4{,}29\text{ Mrd.}$) zu überwinden, haben sich vier Hauptparadigmen entwickelt:

Bei der White-Box-Concolic-Execution werden Eingabebytes als symbolische Variablen $\vec{\alpha}$ behandelt und die letzte Zweigbedingung $c_k(\vec{\alpha})$ für den SMT-Solver negiert:

Das 2013 von Michał Zalewski (lcamtuf) entwickelte American Fuzzy Lop (AFL) (sowie AFL++ und LibFuzzer) ersetzte schwere SMT-Beweiser durch extrem schnelle Compile-Time-Kanteninstrumentierung und evolutionäre Selektion.

  flowchart LR
    SeedQueue["Seed-Queue (Corpus)<br/>Gespeicherte 'interessante' Eingaben"] --> NextInput["1. Seed-Auswahl<br/>(AFLFast / Entropic Power Schedule)"]
    NextInput --> Mutator["2. Genetischer Mutator<br/>(Bitflips, Arith, CmpLog, Havoc, Splice)"]
    Mutator --> ForkServer["3. Hochgeschwindigkeits-Ausführung<br/>(Forkserver / Persistent Mode)"]
    ForkServer --> Bitmap["4. 64-KB-Shared-Memory-Bitmap<br/>(Aufzeichnung der CFG-Kantenübergänge)"]
    ForkServer --> Sanitizer{"Absturz oder<br/>Sanitizer-Alarm?"}
    Sanitizer -- "Ja (SIGSEGV / ASan)" --> Triage["Crash-Triage & Minimierung<br/>(Stack Hash & ddmin)"]
    Sanitizer -- "Nein" --> NewCov{"Neue CFG-Kante oder<br/>neuer Hit-Count-Bucket?"}
    Bitmap --> NewCov
    NewCov -- "Ja (Fitness-Gewinn!)" --> AddQueue["Aufnahme in die Seed-Queue<br/>(Eltern-Seed für nächste Generation)"]
    AddQueue --> SeedQueue
    NewCov -- "Nein (bekannter Pfad)" --> Discard["Mutierte Eingabe sofort verwerfen"]

Kapitel 3: Die Architektur von AFL — Kanteninstrumentierung, 64-KB-Bitmap und der Beweis von >> 1

3.1 Warum Kantenabdeckung (Edge Coverage) statt Basisblock-Abdeckung?

Würde ein Fuzzer nur protokollieren, welche Basisblöcke (Knoten) besucht wurden, wäre nach dem Pfad $A \to B \to C$ die Menge $\{A, B, C\}$ vollständig markiert. Wenn eine zweite Eingabe den Initialisierungsblock $B$ überspringt und direkt $A \to C$ nimmt (wodurch in $C$ ein NULL-Zeiger dereferenziert wird), ist $\{A, C\} \subset \{A, B, C\}$ – ein Knoten-Fuzzer würde die Eingabe als redundant verwerfen! Durch die Aufzeichnung gerichteter Kantenübergänge (Edge Tuples) erkennt AFL sofort, dass die Kante $(A \to C)$ neu ist.

3.2 Das 3-Zeilen-Trampolin, 64 KB L1-Cache und die Mathematik hinter >> 1

AFL injiziert zur Compile-Zeit am Anfang jedes Basisblocks folgende drei Operationen:

1
2
3
4
5
6
7
8

/* Compile-time random 16-bit ID assigned to the current basic block */
cur_location = <COMPILE_TIME_RANDOM_16BIT>;

/* Record the transition edge (prev -> cur) in the 64 KB shared bitmap */
shared_mem[cur_location ^ prev_location]++;

/* Right-shift by 1 bit to preserve directionality and self-loops */
prev_location = cur_location >> 1;

Warum ist shared_mem exakt $2^{16} = 65.536$ Bytes (64 KB) groß? Weil 64 KB vollständig in den L1-Datencache bzw. L2-Cache moderner CPU-Kerne passen. Jeder Kantenzähler-Zugriff erfolgt damit ohne DRAM-Cache-Miss in rund einer Nanosekunde!

Warum ist die 1-Bit-Rechtsverschiebung (>> 1) in prev_location = cur_location >> 1; mathematisch zwingend erforderlich? Ohne diesen Shift hätte eine reine XOR-Verknüpfung $A \oplus B$ zwei fatale algebraische Defekte:

1. Verlust der Richtung durch Kommutativität ($A \oplus B = B \oplus A$): Der Übergang $A \to B$ und der Rücksprung $B \to A$ würden denselben Index erzeugen.
2. Auslöschung aller Selbstschleifen durch Nilpotenz ($A \oplus A = 0$): Jede enge Schleife eines Blocks auf sich selbst ($A \to A$) ergäbe $0$ – sämtliche Selbstschleifen des gesamten Programms würden im selben Byte shared_mem[0] kollidieren!

Der 1-Bit-Shift bricht Symmetrie und Nilpotenz in einem einzigen Taktzyklus. Zusätzlich quantisiert AFL die 8-Bit-Trefferzähler in 8 logarithmische Buckets ($1, 2, 3, 4\text{–}7, 8\text{–}15, 16\text{–}31, 32\text{–}127, 128\text{–}255$), um wichtige Meilensteine bei Schleifendurchläufen zu erkennen, ohne die Queue zu fluten.

3.3 Forkserver, Persistent Mode und Markov-Power-Schedules (AFLFast / Entropic)

Um den enormen Overhead von execve() und dem dynamischen Linker (ld.so) zu vermeiden, startet AFL das Zielprogramm einmalig bis kurz vor main() als Forkserver und klont für jeden Testfall nur noch per Copy-on-Write (CoW) fork() über die Steuer-Pipes fd 198/199 ($>10.000\text{ execs/sec}$). Im Persistent Mode (LLVMFuzzerTestOneInput) entfällt selbst fork(), indem die Zielfunktion direkt in einer In-Memory-Schleife aufgerufen wird ($>100.000\text{ execs/sec}$). Über CmpLog (RedQueen) werden Operanden von Vergleichsbefehlen (cmp, memcmp) direkt in die Eingabe eingesetzt, während AFLFast und Entropic über Markov-Ketten und die Shannon-Entropie $H(s)$ selten besuchten Pfaden exponentiell mehr Mutationsenergie $p(s)$ zuweisen:

Kapitel 4: Stille Speicherkorruption in sofortige Abstürze verwandeln — Sanitizers

Da die Hardware-MMU des Prozessors Speicherschutz nur auf Ebene von $4\text{-KB}$-Seiten prüft, lösen ein 1-Byte-Heap-Overflow oder ein Use-After-Free fast nie ein SIGSEGV aus – das Programm läuft fehlerhaft weiter und der Fuzzer bemerkt den Bug nicht. AddressSanitizer (ASan) löst dieses Problem durch ein 1:8-Shadow-Memory-Mapping:

Je 8 Bytes Anwendungsspeicher werden auf 1 Shadow-Byte abgebildet: 0x00 bedeutet alle 8 Bytes gültig, $1 \le k \le 7$ bedeutet nur die ersten $k$ Bytes gültig, und negative Werte markieren vergiftete Redzones (0xfa Heap-Redzone, 0xf1 Stack-Redzone) oder freigegebene Blöcke in der Quarantine-Queue (0xfd für Use-After-Free). Vor jeden Speicherzugriff setzt der Compiler folgenden Check:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* Compiler-injected ASan check before an N-byte memory access (N = 1, 2, 4) */
uintptr_t shadow_addr = (addr >> 3) + ASAN_SHADOW_OFFSET;
int8_t shadow_val = *(int8_t *)shadow_addr;

if (UNLIKELY(shadow_val != 0)) {
    /* For partial 8-byte words (1 <= shadow_val <= 7) or negative redzones */
    if (shadow_val < 0 || (int8_t)((addr & 7) + N) > shadow_val) {
        __asan_report_error(pc, bp, sp, addr, is_write, N);
    }
}

Ergänzt durch UBSan (undefiniertes Verhalten & Integer-Overflows), MSan (bitgenaue Verfolgung nicht initialisierter Speicherzugriffe), TSan (Data-Race-Erkennung mittels Vektoruhren) und Differential Fuzzing (Vergleich mehrerer Implementierungen für logische/kryptographische Bugs) wird jeder subtile Fehler sofort in einen deterministischen Absturz verwandelt.

Kapitel 5: Crash-Triage und Andreas Zellers Delta Debugging (ddmin)

Tausende redundante Crash-Dateien werden zunächst über Stack Hashing (Hashing der obersten Call-Stack-Frames am Absturzort) nach ihrer Grundursache dedupliziert. Um anschließend eine mehrere Megabyte große, durch tausende Mutationen aufgeblähte Crash-Datei $c$ (Länge $N$) auf ein minimales Beispiel zu schrumpfen, nutzt man Andreas Zellers Delta Debugging (ddmin). Das Ziel ist ein 1-minimaler Testfall $c^*$, bei dem das Entfernen jedes einzelnen weiteren Bytes den Absturz verschwinden lässt:

ddmin teilt die Eingabe in $n$ Teile $\Delta_1, \dots, \Delta_n$ (Start mit $n=2$), prüft zuerst jede Teilmenge $\Delta_i$ und danach jedes Komplement $\nabla_i = c \setminus \Delta_i$ auf Reproduktion des Absturzes. Schlägt beides fehl, wird die Granularität verdoppelt ($n \leftarrow \min(2n, |c|)$). Im Bestfall reduziert ddmin ähnlich der binären Suche eine 10-MB-Datei in nur $\mathcal{O}(\log_2 N)$ Schritten auf wenige Bytes (afl-tmin bzw. AST-basiertes C-Reduce für Compiler-Bugs).