💻 computer science

On Interaction Effects in Greybox Fuzzing

Cet article propose MuoFuzz, un fuzzing gris qui améliore l'efficacité des tests en apprenant et en exploitant les interactions entre mutateurs pour générer des séquences d'opérations plus prometteuses, surpassant ainsi des outils comme AFL++ et MOPT en termes de couverture de code et de détection de bugs.

Auteurs originaux : Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

Publié 2026-04-24

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Konstantinos Kitsios, Marcel Böhme, Alberto Bacchelli

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ Le Détective et le Chaos : Comment trouver les bugs cachés dans les logiciels

Imaginez que vous essayez de trouver des failles de sécurité dans un logiciel (comme un coffre-fort numérique). Vous ne pouvez pas tout ouvrir manuellement, c'est trop long. Alors, vous utilisez un robot détective appelé "Fuzzer" (ou "brouilleur").

1. Le Robot Brouilleur (Le Fuzzing Gris)

Ce robot a une mission : il prend un document valide (un "grain" ou seed), le modifie au hasard, et le donne au logiciel pour voir ce qui se passe.

Si le logiciel plante ou fait une bêtise, le robot crie : "J'ai trouvé un bug !"
Si le logiciel réagit d'une nouvelle façon (il explore une nouvelle partie du code), le robot garde ce nouveau document pour l'essayer encore plus tard.

Le problème ? Le robot a une boîte à outils avec 32 outils différents (des marteaux, des tournevis, des pinces, etc.). Il peut :

Changer un seul bit (un 0 en 1).
Effacer un bloc de données.
Insérer un mot du dictionnaire.

Dans les méthodes classiques (comme AFL++), le robot choisit ses outils au hasard, comme un enfant qui lance des dés. Parfois, il utilise un marteau, puis un tournevis. Parfois, deux marteaux de suite. Il ne réfléchit pas à l'ordre.

2. La Grande Découverte : L'Effet de Duo 🤝

Les auteurs de cet article (Kitsios, Böhme et Bacchelli) ont eu une intuition : L'ordre des outils compte !

Imaginez que vous essayez d'ouvrir un cadenas complexe.

Si vous tapez d'abord avec un marteau (pour casser la coque) et ensuite avec une pince (pour saisir le mécanisme), vous avez de grandes chances de réussir.
Mais si vous faites l'inverse (pince puis marteau), vous risquez de casser la pince sans rien ouvrir.

Les chercheurs ont prouvé mathématiquement que certains outils fonctionnent mieux ensemble que d'autres. Ce n'est pas juste une question de "quel outil est le meilleur", mais de "quel outil suit quel autre". C'est ce qu'ils appellent l'effet d'interaction.

3. La Solution : MuoFuzz (Le Robot qui Apprend)

Pour exploiter cette découverte, ils ont créé un nouveau robot appelé MuoFuzz. Au lieu de lancer des dés aveuglément, MuoFuzz fonctionne en deux étapes, comme un étudiant qui apprend avant d'examiner :

Étape 1 : L'Entraînement (La Phase d'Apprentissage)
Pendant la première heure, MuoFuzz teste toutes les combinaisons possibles de deux outils (Outil A puis Outil B, Outil C puis Outil D, etc.). Il note dans un carnet : "Quand j'ai utilisé le marteau, la pince a souvent réussi à trouver un bug juste après."
Il crée une carte de probabilité : "Si je viens d'utiliser l'outil X, il y a 80% de chances que l'outil Y soit le suivant le plus prometteur."
Étape 2 : La Chasse Guidée
Une fois la carte apprise, le robot arrête de deviner. Il utilise cette carte pour choisir intelligemment la suite de ses actions. C'est comme un promeneur dans un labyrinthe : au lieu de tourner au hasard à chaque intersection, il regarde les traces laissées par ses pas précédents pour choisir le chemin qui mène le plus souvent à la sortie.

4. Les Résultats : Qui gagne ? 🏆

Les chercheurs ont mis MuoFuzz en compétition contre les champions actuels (AFL++ et MOPT) sur de vrais logiciels complexes.

Couverture : MuoFuzz a exploré plus de zones du code que les autres. Il a trouvé des chemins que les autres robots n'avaient même pas vus.
Vitesse : Il a atteint le niveau de performance des autres robots beaucoup plus vite (parfois en 15 heures au lieu de 24).
Bugs trouvés : MuoFuzz a découvert 4 bugs que le champion AFL++ avait manqués, et 1 bug que même les deux autres robots n'avaient pas trouvés !

5. L'Analogie Finale : Le Rappeur et le Flow 🎤

Pour résumer simplement :

Les anciens robots (AFL++) sont comme un rappeur qui improvise des mots au hasard. Parfois ça sonne bien, souvent c'est du bruit.
MOPT (un autre robot) essaie de trouver le mot le plus cool, mais il choisit chaque mot indépendamment, sans se soucier de ce qui précède.
MuoFuzz, lui, comprend le flow. Il sait que si le mot précédent était "Rime", le mot suivant doit probablement être une "Chute" pour que la phrase ait du sens. Il ne choisit pas juste le mot, il choisit la séquence.

En conclusion

Ce papier nous apprend que dans la chasse aux bugs, l'ordre des opérations est aussi important que les opérations elles-mêmes. En apprenant à combiner intelligemment ses outils plutôt que de les utiliser au hasard, on peut trouver des failles de sécurité beaucoup plus rapidement et plus efficacement. C'est passer de l'artisanat aléatoire à l'art de la précision.

1. Problématique

Le fuzzing gris (greybox fuzzing) est une technique de test logiciel automatisé qui génère de nouvelles entrées de test en modifiant (mutant) des entrées de départ (seeds) existantes. Les fuzzer modernes, comme AFL++, utilisent une stratégie de mutation basée sur un ensemble de 32 mutateurs (opérations comme l'inversion de bits, la suppression de blocs, l'ajout de valeurs, etc.).

Le problème central identifié par les auteurs réside dans la stratégie de sélection des mutateurs.

Approche actuelle (AFL++) : Chaque mutateur a une probabilité de sélection fixe et prédéfinie, indépendante des autres mutateurs.
Approche adaptative (MOPT) : Optimise la probabilité de sélection de chaque mutateur individuellement, mais suppose toujours que les mutateurs sont indépendants les uns des autres au sein d'une séquence.
Hypothèse des auteurs : Il existe un effet d'interaction entre les mutateurs. C'est-à-dire que l'efficacité d'un mutateur dépend du mutateur qui le précède dans la séquence. L'ordre d'application des mutateurs influence la probabilité de générer une entrée "intéressante" (couvrant du nouveau code). Ignorer cette dépendance conditionnelle limite l'efficacité du fuzzing.

2. Méthodologie

Les auteurs proposent une approche en deux temps : d'abord valider l'existence de l'effet d'interaction, puis concevoir un algorithme pour l'exploiter.

A. Validation de l'effet d'interaction (RQ1)

Pour prouver l'hypothèse, les auteurs ont collecté un dataset en exécutant AFL++ sur 13 programmes cibles (benchmarks FuzzBench) avec des modifications spécifiques :

Limitation de séquence : Les séquences de mutation sont limitées à une longueur de 2 ( $l=2$ ) pour isoler les paires de mutateurs.
Échantillonnage uniforme : Les mutateurs sont sélectionnés aléatoirement (et non selon les probabilités fixes d'AFL++) pour garantir une couverture égale de toutes les paires.
Modélisation : Ils ont ajusté un modèle linéaire où la variable dépendante est le nombre d'entrées intéressantes générées par une paire de mutateurs $\langle i, j \rangle$ , et les variables indépendantes sont les mutateurs $i$ et $j$ ainsi que leur terme d'interaction $\gamma_{ij}$ .
Analyse statistique : Une analyse de variance (ANOVA) à deux voies a été utilisée pour tester la significativité du terme d'interaction.

B. Conception de MuoFuzz

Basé sur la découverte d'un effet d'interaction significatif, les auteurs ont développé MuoFuzz (Mut + Duo + Fuzz). La stratégie repose sur l'apprentissage de la probabilité conditionnelle :
$Pr(m_n = j \mid m_{n-1} = i)$
C'est-à-dire : quelle est la probabilité que le mutateur $j$ soit le suivant, sachant que le mutateur précédent était $i$ ?

L'algorithme fonctionne en deux phases :

Phase d'entraînement (Training Phase) : Pendant les premières heures (par défaut 1h), le fuzzer génère des séquences de longueur 2 de manière uniforme pour construire une matrice de comptage $N(i, j)$ représentant le nombre d'entrées intéressantes générées par chaque paire.
Phase de mutation guidée (Guided Mutation Phase) : Le fuzzer utilise la distribution de probabilité apprise pour générer des séquences de mutateurs via une marche aléatoire (random walk) sur une chaîne de Markov. Le choix du mutateur suivant dépend directement du mutateur précédent.

3. Contributions Clés

Preuve empirique de l'effet d'interaction : Démonstration statistique que l'interaction entre deux mutateurs affecte significativement le nombre d'entrées intéressantes générées, invalidant l'hypothèse d'indépendance utilisée par les stratégies actuelles.
Nouvelle stratégie de mutation (MuoFuzz) : Implémentation d'une stratégie qui apprend et utilise les probabilités conditionnelles de paires de mutateurs pour guider la génération de séquences.
Évaluation comparative rigoureuse : Comparaison de MuoFuzz avec l'état de l'art (AFL++ et MOPT) sur des benchmarks standards (FuzzBench et MAGMA), incluant des études d'ablation pour valider chaque composant de la conception.

4. Résultats Expérimentaux

Les expériences ont été menées sur 13 programmes FuzzBench et 8 programmes du benchmark MAGMA (contenant des bugs réels).

Couverture de code (Code Coverage) :
- MuoFuzz a atteint une couverture supérieure à AFL++ sur 9 programmes sur 13 et à MOPT sur 8 programmes sur 13 (avec significativité statistique).
- En termes de temps, MuoFuzz atteint la couverture finale de 24h d'AFL++ en moyenne en 15 heures, et celle de MOPT en 16,5 heures, démontrant une accélération de la découverte de code.
- L'amélioration est corrélée à la force de l'effet d'interaction : là où le modèle d'interaction est fort (bon $R^2$ ), MuoFuzz surpasse les autres. Là où l'effet est faible (ex: openssl, libpng), les performances sont comparables.
Détection de bugs (Bugs Found) :
- Sur le benchmark MAGMA, MuoFuzz a détecté 4 bugs que AFL++ avait manqués.
- Il a trouvé 1 bug (SQL010) que ni AFL++ ni MOPT n'avaient trouvé.
- Bien que le nombre total de bugs trouvés soit similaire entre MuoFuzz et MOPT, les bugs découverts sont souvent différents, suggérant que MuoFuzz explore des chemins d'exécution uniques grâce à sa stratégie de séquence.
Études d'ablation (RQ4) :
- L'utilisation de plus de 2 mutateurs comme contexte ( $p>2$ ) dégrade les performances (malédiction de la dimensionnalité).
- L'initialisation du premier mutateur de manière uniforme (aléatoire) fonctionne mieux qu'une sélection pondérée par la performance, car cela préserve l'exploration.
- L'apprentissage spécifique à chaque programme est supérieur à la généralisation inter-programmes.

5. Signification et Implications

Changement de paradigme : Ce travail démontre que les stratégies de mutation ne doivent pas traiter les mutateurs comme des entités indépendantes. La séquence et l'ordre comptent.
Inspiration linguistique : L'approche de MuoFuzz est analogue aux modèles de langage bigrammes (Bigram Language Models) utilisés en traitement du langage naturel, où la probabilité d'un mot dépend du mot précédent. Cela ouvre la voie à l'application de techniques d'IA plus avancées (RNN, Transformers) pour la génération de séquences de mutation.
Efficacité pratique : MuoFuzz offre une amélioration tangible de l'efficacité du fuzzing sans nécessiter de changements majeurs dans l'infrastructure, simplement en modifiant la logique de sélection des mutateurs. Il prouve que l'apprentissage de l'interaction entre les composants de mutation est une voie prometteuse pour l'avenir du test logiciel automatisé.

En conclusion, l'article établit que l'optimisation de la séquence de mutation, et non seulement de la fréquence d'utilisation individuelle des mutateurs, est cruciale pour maximiser l'efficacité des fuzzers gris.