Par une nuit d’orage d’automne en 1988 à Madison, dans le Wisconsin, le professeur d’informatique Barton Miller travaillait depuis son domicile sur un terminal relié à sa station de travail UNIX universitaire via un modem commuté à 1200 bauds et une ligne téléphonique analogique. Dehors, la foudre frappait sans relâche, injectant par induction électromagnétique des rafales de bruit parasite dans la ligne téléphonique et corrompant les flux de caractères ASCII envoyés au shell UNIX.

Ce que Miller observa alors le stupéfia : chaque fois que le bruit de la ligne injectait des séquences d’octets incohérentes dans des utilitaires UNIX standard pourtant éprouvés — tels que vi, cc, awk, sed, csh ou indent — ces programmes utilisés quotidiennement par des milliers d’ingénieurs ne se contentaient pas d’afficher une erreur de syntaxe : ils plantaient brutalement avec des fautes de segmentation (SIGSEGV) ou se figeaient dans des boucles infinies.

Fasciné par cette fragilité, Miller confia à ses étudiants de master un projet consistant à bombarder d’entrées aléatoires près de 90 utilitaires sur sept variantes d’UNIX, baptisant ce générateur de bruit « Fuzz ». Les résultats ébranlèrent l’industrie : entre 25 % et 33 % des utilitaires UNIX standard plantaient dès qu’on leur soumettait des flux d’octets purement aléatoires.

Plus de trente-cinq ans plus tard, le fuzzing (test à données aléatoires) a évolué d’un simple générateur de bruit aveugle vers la discipline de découverte automatique de vulnérabilités la plus puissante de l’informatique, fusionnant l’instrumentation compilateur (LLVM IR), les algorithmes génétiques darwiniens, les solveurs formels SMT et la mémoire fantôme (Shadow Memory). À elle seule, l’infrastructure OSS-Fuzz de Google a découvert automatiquement plus de 10 000 vulnérabilités de sécurité et plus de 36 000 bugs dans des projets critiques comme OpenSSL, SQLite, FFmpeg et le noyau Linux.

Pourquoi des milliers de tests unitaires écrits par des humains laissent-ils passer des corruptions mémoire fatales que la mutation automatique débusque en quelques minutes ? Cet article décortique l’explosion combinatoire de l’espace d’entrée, les quatre paradigmes du fuzzing, l’architecture interne d’AFL / AFL++ / LibFuzzer (bitmap de 64 Ko en cache L1, preuve mathématique du décalage >> 1, Forkserver et ordonnancement markovien), le fonctionnement d’AddressSanitizer (ASan) et l’algorithme de Delta Debugging (ddmin) d’Andreas Zeller.

Chapitre 1 : L’abîme combinatoire des espaces d’entrée et l’effet réverbère

1.1 Un tampon de 64 octets contient $10^{154}$ univers possibles

Pourquoi les suites de tests manuels ne peuvent-elles pas éradiquer les bugs ? À cause de l’explosion combinatoire de l’espace d’entrée. Considérons une fonction C qui analyse un en-tête binaire de seulement $N = 64$ octets. Chaque octet pouvant prendre $|\Sigma| = 2^8 = 256$ valeurs, le nombre total d’entrées possibles est :

À titre de comparaison, le nombre d’Eddington (le nombre total estimé de protons dans l’univers observable) n’est que d’environ $10^{80}$. Même si tous les processeurs sur Terre testaient mille milliards ($10^{12}$) d’entrées par seconde depuis le Big Bang il y a 13,8 milliards d’années, ils n’exploreraient pas $10^{-124}$ de cet espace de 64 octets.

1.2 L’effet réverbère (Streetlight Effect) et la « Weird Machine »

Lorsqu’un développeur écrit des tests unitaires, il est victime de l’effet réverbère (biais d’observation) : comme le passant qui cherche ses clés perdues uniquement sous le lampadaire parce qu’il y fait clair, l’humain ne teste que les cas nominaux spécifiés et les valeurs limites évidentes (0, -1, NULL) auxquelles il a déjà pensé en codant. Or, les vulnérabilités critiques résident dans l’ombre, au sein de la « Weird Machine » (Bratus et al.) — l’automate d’états émergent né de l’interaction entre troncatures d’entiers et invariants implicites :

 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;          // Attend la signature "IMG!"
    if (width == 0 || height == 0) return -1;    // Le développeur a testé 0 !

    uint16_t alloc_size = width * height;        // [BUG] Dépassement d'entier 16 bits !
    if (flags & 0x80) alloc_size += 16;
    uint8_t *pixel_buf = malloc(alloc_size);     // Alloue seulement 0 ou 16 octets
    memcpy(pixel_buf, buf + 16, (size_t)width * height); // Copie 65 536 octets -> corruption du tas !
    ...
}

Si width = 256 et height = 256, le produit $256 \times 256 = 65536 \equiv 0 \pmod{2^{16}}$ provoque un dépassement d’entier sur 16 bits : malloc(16) alloue un minuscule tampon que memcpy écrase immédiatement avec 64 Ko de données.

Chapitre 2 : Les quatre grands paradigmes du fuzzing

Pour franchir une barrière telle que if (magic != 0x494D4721) (probabilité aléatoire de $2^{-32} \approx 1 / 4,29\times 10^9$), quatre paradigmes se sont succédé :

Dans l’exécution concolique (Concrete + Symbolic), les octets d’entrée sont modélisés par des variables symboliques $\vec{\alpha}$ et la dernière condition de branchement est inversée pour le solveur SMT :

À l’inverse, AFL (créé par Michał Zalewski en 2013), AFL++ et LibFuzzer remplacent le solveur SMT par une boucle évolutive guidée par la couverture d’arêtes.

  flowchart LR
    SeedQueue["File de graines (Seed Corpus)<br/>Entrées 'intéressantes' retenues"] --> NextInput["1. Sélection de graine<br/>(Ordonnancement AFLFast / Entropic)"]
    NextInput --> Mutator["2. Moteur de mutation génétique<br/>(Bitflips, Arith, CmpLog, Havoc, Splice)"]
    Mutator --> ForkServer["3. Exécution haute vitesse<br/>(Forkserver / Mode Persistant)"]
    ForkServer --> Bitmap["4. Bitmap mémoire partagée 64 Ko<br/>(Suivi des transitions d'arêtes CFG)"]
    ForkServer --> Sanitizer{"Crash ou alerte<br/>Sanitizer ?"}
    Sanitizer -- "Oui (SIGSEGV / ASan)" --> Triage["Triage & Minimisation<br/>(Stack Hash & ddmin)"]
    Sanitizer -- "Non" --> NewCov{"Nouvelle arête CFG ou<br/>nouveau palier de compteur ?"}
    Bitmap --> NewCov
    NewCov -- "Oui (Gain d'adaptation !)" --> AddQueue["Promotion dans la file de graines<br/>(Devient parent pour la génération suivante)"]
    AddQueue --> SeedQueue
    NewCov -- "Non (Chemin redondant)" --> Discard["Rejet immédiat de l'entrée mutée"]

Chapitre 3 : Au cœur du moteur d’AFL — Instrumentation d’arêtes, bitmap de 64 Ko et preuve de >> 1

3.1 Pourquoi la couverture d’arêtes (Edge Coverage) surpasse la couverture de blocs

Si le fuzzer ne notait que les blocs de base visités, après une exécution empruntant $A \to B \to C$, les blocs $\{A, B, C\}$ seraient tous marqués comme visités. Lorsqu’une seconde entrée contourne l’initialisation en $B$ en prenant directement l’arête $A \to C$ (déclenchant un déréférencement NULL dans $C$), l’ensemble $\{A, C\} \subset \{A, B, C\}$ serait jugé redondant et jeté ! En suivant les couples de transition (arêtes) $(B_{\text{prev}} \to B_{\text{cur}})$, AFL détecte immédiatement que la transition $(A \to C)$ est inédite.

3.2 Le trampoline de 3 lignes, le cache L1 de 64 Ko et la nécessité mathématique de >> 1

À la compilation, AFL injecte à l’entrée de chaque bloc de base ces trois instructions :

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;

La taille de shared_mem est fixée à $2^{16} = 65\,536$ octets (64 Ko) afin de résider intégralement dans le cache de données L1/L2 du processeur, évitant tout défaut de cache vers la RAM et limitant le surcoût à ~1 nanoseconde par saut.

Pourquoi le décalage d’un bit vers la droite (>> 1) dans prev_location = cur_location >> 1; est-il indispensable ? Sans ce décalage, l’opérateur OU exclusif (XOR) souffrirait de deux dégénérescences algébriques fatales :

1. Perte de directionnalité par commutativité ($A \oplus B = B \oplus A$) : L’arête aller $A \to B$ et l’arête retour $B \to A$ produiraient exactement le même indice.
2. Annihilation des boucles réflexives par nilpotence ($A \oplus A = 0$) : Toute boucle d’un bloc sur lui-même ($A \to A$) vaudrait $0$, faisant entrer en collision toutes les boucles réflexives du programme dans l’unique octet shared_mem[0] !

Le décalage >> 1 brise simultanément la symétrie et la nilpotence en un seul cycle d’horloge. De plus, les compteurs d’exécutions sont regroupés en 8 paliers logarithmiques ($1, 2, 3, 4\text{–}7, 8\text{–}15, 16\text{–}31, 32\text{–}127, 128\text{–}255$) pour capter les étapes clés du déroulement des boucles.

3.3 Forkserver, Mode Persistant et ordonnancement markovien (AFLFast / Entropic)

Pour éliminer le coût prohibitif d’execve() et de l’éditeur de liens dynamique (ld.so), le Forkserver d’AFL fige le processus juste avant main() et clone les processus enfants uniquement par Copy-on-Write (fork()) via les tubes fd 198/199. Le Mode Persistant (LLVMFuzzerTestOneInput) va encore plus loin en appelant directement la fonction cible en mémoire dans une boucle sans aucun fork(), dépassant $100\,000\text{ execs/s}$. Associé à CmpLog (RedQueen) (qui intercepte les opérandes des instructions cmp/memcmp) et aux ordonnanceurs AFLFast / Entropic basés sur les chaînes de Markov et l’entropie de Shannon $H(s)$, le fuzzer concentre son énergie sur les chemins rares :

Chapitre 4 : Transformer les corruptions silencieuses en crashs immédiats — Les Sanitizers

Comme l’unité de gestion mémoire (MMU) matérielle ne vérifie les permissions qu’à l’échelle de pages de $4\text{ Ko}$, un débordement de tampon d’un seul octet sur le tas ou un Use-After-Free ne déclenche presque jamais de SIGSEGV. AddressSanitizer (ASan) résout ce problème grâce à une projection mémoire fantôme (Shadow Memory) 1:8 :

Chaque mot aligné de 8 octets de mémoire applicative est associé à 1 octet fantôme : 0x00 si les 8 octets sont valides, $1 \le k \le 7$ si seuls les $k$ premiers octets sont valides, et une valeur négative pour les zones rouges empoisonnées (0xfa sur le tas, 0xf1 sur la pile) ou les blocs libérés placés en file de quarantaine (0xfd pour détecter les Use-After-Free). Avant chaque accès mémoire, le compilateur insère :

 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);
    }
}

Complété par UBSan (comportements indéfinis et dépassements d’entiers), MSan (suivi bit à bit de la mémoire non initialisée), TSan (détection des courses aux données par horloges vectorielles) et le fuzzing différentiel (comparaison des sorties de plusieurs implémentations indépendantes), le moindre défaut mémoire ou logique provoque un arrêt immédiat et traçable.

Chapitre 5 : Triage des crashs et Delta Debugging (ddmin) d’Andreas Zeller

Les milliers de crashs redondants sont d’abord dédupliqués par hachage de la pile d’appels (Stack Hash) des fonctions situées au sommet de la pile au moment de la faute. Ensuite, pour réduire un fichier de crash de plusieurs mégaoctets $c$ (de taille $N$) rempli de bruit de mutation en un cas de test minimal, l’algorithme de Delta Debugging (ddmin) d’Andreas Zeller recherche automatiquement un sous-ensemble 1-minimal $c^*$ tel que la suppression de n’importe quel octet supplémentaire fasse disparaître le crash :

En partitionnant l’entrée en $n$ blocs $\Delta_1, \dots, \Delta_n$ (initialement $n=2$), ddmin teste d’abord chaque sous-ensemble $\Delta_i$, puis chaque complémentaire $\nabla_i = c \setminus \Delta_i$, et double la granularité $n \leftarrow \min(2n, |c|)$ lorsque aucune réduction directe n’aboutit. Par cette généralisation de la recherche dichotomique, ddmin (utilisé dans afl-tmin et C-Reduce) réduit un fichier de 10 Mo en une preuve de concept (PoC) chirurgicale de quelques octets en seulement $\mathcal{O}(\log_2 N)$ étapes dans le meilleur cas.