Fuzzing

En programmation et en développement de logiciels , le fuzzing ou le fuzz testing est une technique de test logiciel automatisée qui consiste à fournir des données non valides, inattendues ou aléatoires en tant qu'entrées à un programme informatique . Le programme est ensuite surveillé pour détecter des exceptions telles que des plantages , des échecs d'assertions de code intégrées ou des fuites de mémoire potentielles . En règle générale, les fuzzers sont utilisés pour tester des programmes qui prennent des entrées structurées. Cette structure est spécifiée, par exemple, dans un format de fichier ou un protocole et distingue les entrées valides des entrées non valides. Un fuzzer efficace génère des entrées semi-valides qui sont « suffisamment valides » dans le sens où elles ne sont pas directement rejetées par l'analyseur, mais créent des comportements inattendus plus profondément dans le programme et sont « suffisamment invalides » pour exposer des cas particuliers qui n'ont pas été correctement traités.

Pour des raisons de sécurité, les entrées qui franchissent une limite de confiance sont souvent les plus utiles. Par exemple, il est plus important de tester le code qui gère un fichier téléchargé par un utilisateur que de tester le code qui analyse un fichier de configuration accessible uniquement à un utilisateur privilégié.

Le terme « fuzz » provient d'un projet de classe de 1988 dans le cours de systèmes d'exploitation avancés (CS736) enseigné par le professeur Barton Miller à l' université du Wisconsin , dont les résultats ont été publiés en 1990. Pour tester par fuzz un utilitaire UNIX , il était prévu de générer automatiquement des paramètres d'entrée et de ligne de commande aléatoires pour l'utilitaire. Le projet a été conçu pour tester la fiabilité des programmes de ligne de commande UNIX en exécutant un grand nombre d'entrées aléatoires en succession rapide jusqu'à ce qu'ils se bloquent. L'équipe de Miller a pu faire planter 25 à 33 % des utilitaires qu'ils ont testés. Ils ont ensuite débogué chacun des plantages pour déterminer la cause et ont catégorisé chaque échec détecté. Pour permettre à d'autres chercheurs de mener des expériences similaires avec d'autres logiciels, le code source des outils, les procédures de test et les données de résultat brutes ont été rendus publics. Ce fuzzing précoce serait désormais appelé fuzzing de boîte noire, générationnel, non structuré (stupide ou « classique »).

Selon le professeur Barton Miller, « lors de la rédaction de la description du projet, j'ai dû donner un nom à ce type de test. Je voulais un nom qui évoquerait la sensation de données aléatoires et non structurées. Après avoir essayé plusieurs idées, j'ai opté pour le terme fuzz. »

L'une des contributions clés de ces premiers travaux était un oracle simple (presque simpliste). Un programme échouait à son test s'il plantait ou se bloquait sous l'entrée aléatoire et était considéré comme réussi dans le cas contraire. Bien que les oracles de test puissent être difficiles à construire, l'oracle de ces premiers tests de fuzz était simple et universel à appliquer.

En avril 2012, Google a annoncé ClusterFuzz, une infrastructure de fuzzing basée sur le cloud pour les composants critiques de sécurité du navigateur Web Chromium . Les chercheurs en sécurité peuvent télécharger leurs propres fuzzers et collecter des primes de bug si ClusterFuzz détecte un crash avec le fuzzer téléchargé.

En septembre 2014, Shellshock a été divulgué comme une famille de bugs de sécurité dans le shell Bash d'UNIX largement utilisé ; la plupart des vulnérabilités de Shellshock ont ​​été trouvées à l'aide du fuzzer AFL . (De nombreux services Internet, tels que certains déploiements de serveurs Web, utilisent Bash pour traiter certaines requêtes, ce qui permet à un attaquant de faire en sorte que des versions vulnérables de Bash exécutent des commandes arbitraires . Cela peut permettre à un attaquant d'obtenir un accès non autorisé à un système informatique. )

En avril 2015, Hanno Böck a montré comment le fuzzer AFL aurait pu trouver la vulnérabilité Heartbleed de 2014. (La vulnérabilité Heartbleed a été révélée en avril 2014. Il s'agit d'une vulnérabilité grave qui permet aux adversaires de déchiffrer des communications autrement cryptées . La vulnérabilité a été accidentellement introduite dans OpenSSL qui implémente TLS et est utilisé par la majorité des serveurs sur Internet. Shodan a signalé 238 000 machines toujours vulnérables en avril 2016 ; 200 000 en janvier 2017. )

En août 2016, la Defense Advanced Research Projects Agency (DARPA) a organisé la finale du premier Cyber ​​Grand Challenge , une compétition de capture de drapeau entièrement automatisée qui a duré 11 heures. L'objectif était de développer des systèmes de défense automatiques capables de découvrir, d'exploiter et de corriger les failles logicielles en temps réel . Le fuzzing a été utilisé comme une stratégie offensive efficace pour découvrir les failles dans les logiciels des adversaires. Il a montré un potentiel énorme dans l'automatisation de la détection des vulnérabilités. Le gagnant a été un système appelé « Mayhem » développé par l'équipe ForAllSecure dirigée par David Brumley .

En septembre 2016, Microsoft a annoncé le projet Springfield, un service de test fuzz basé sur le cloud pour trouver des bugs de sécurité critiques dans les logiciels.

En décembre 2016, Google a annoncé OSS-Fuzz qui permet le fuzzing continu de plusieurs projets open source critiques pour la sécurité.

Lors du Black Hat 2018, Christopher Domas a démontré l'utilisation du fuzzing pour révéler l'existence d'un cœur RISC caché dans un processeur. Ce cœur a pu contourner les contrôles de sécurité existants pour exécuter les commandes Ring 0 à partir de Ring 3.

En septembre 2020, Microsoft a publié OneFuzz , une plateforme de fuzzing en tant que service auto-hébergée qui automatise la détection des bugs logiciels . Elle prend en charge Windows et Linux. Elle a été archivée trois ans plus tard, le 1er novembre 2023.

Les programmes de test utilisant des entrées aléatoires remontent aux années 1950, époque à laquelle les données étaient encore stockées sur des cartes perforées . Les programmeurs utilisaient des cartes perforées récupérées dans la poubelle ou des jeux de cartes contenant des nombres aléatoires comme entrées pour les programmes informatiques. Si une exécution révélait un comportement indésirable, un bug avait été détecté.

L'exécution d'entrées aléatoires est également appelée test aléatoire ou test de singe .

En 1981, Duran et Ntafos ont formellement étudié l'efficacité des tests d'un programme avec des entrées aléatoires. Alors que les tests aléatoires étaient largement perçus comme le pire moyen de tester un programme, les auteurs ont pu montrer qu'il s'agissait d'une alternative rentable aux techniques de test plus systématiques.

En 1983, Steve Capps , d'Apple, a développé « The Monkey », un outil qui génère des entrées aléatoires pour les applications Mac OS classiques , telles que MacPaint . Le terme figuratif « singe » fait référence au théorème du singe infini qui stipule qu'un singe qui appuie au hasard sur les touches d'un clavier de machine à écrire pendant une durée infinie finira par taper l'intégralité des œuvres de Shakespeare. Dans le cas des tests, le singe écrirait la séquence particulière d'entrées qui déclencherait un crash.

En 1991, l'outil crashme a été publié, qui avait pour but de tester la robustesse des systèmes d'exploitation Unix et de type Unix en exécutant de manière aléatoire des appels système avec des paramètres choisis au hasard.

Un fuzzer peut être catégorisé de plusieurs manières :

1. Un fuzzer peut être basé sur la génération ou sur la mutation selon que les entrées sont générées à partir de zéro ou en modifiant les entrées existantes.
2. Un fuzzer peut être muet (non structuré) ou intelligent (structuré) selon qu'il est conscient ou non de la structure d'entrée.
3. Un fuzzer peut être de type boîte blanche, grise ou noire, selon qu'il est conscient ou non de la structure du programme.

Un fuzzer basé sur la mutation exploite un corpus existant d'entrées de semences pendant le fuzzing. Il génère des entrées en modifiant (ou plutôt en mutant ) les semences fournies. Par exemple, lors du fuzzing de la bibliothèque d'images libpng , l'utilisateur fournirait un ensemble de fichiers d'image PNG valides comme semences tandis qu'un fuzzer basé sur la mutation modifierait ces semences pour produire des variantes semi-valides de chaque semence. Le corpus de fichiers de semences peut contenir des milliers d'entrées potentiellement similaires. La sélection automatique des semences (ou la réduction de la suite de tests) permet aux utilisateurs de choisir les meilleures semences afin de maximiser le nombre total de bogues trouvés au cours d'une campagne de fuzzing.

Un fuzzer basé sur la génération génère des entrées à partir de zéro. Par exemple, un fuzzer basé sur la génération intelligente prend le modèle d'entrée fourni par l'utilisateur pour générer de nouvelles entrées. Contrairement aux fuzzers basés sur la mutation, un fuzzer basé sur la génération ne dépend pas de l'existence ou de la qualité d'un corpus d'entrées de départ.

Certains fuzzers ont la capacité de faire les deux, de générer des entrées à partir de zéro et de générer des entrées par mutation de graines existantes.

En général, les fuzzers sont utilisés pour générer des entrées pour des programmes qui acceptent des entrées structurées, telles qu'un fichier , une séquence d' événements de clavier ou de souris ou une séquence de messages . Cette structure distingue les entrées valides qui sont acceptées et traitées par le programme des entrées non valides qui sont rapidement rejetées par le programme. Ce qui constitue une entrée valide peut être explicitement spécifié dans un modèle d'entrée. Les grammaires formelles , les formats de fichiers , les modèles d' interface utilisateur graphique et les protocoles réseau sont des exemples de modèles d'entrée . Même les éléments qui ne sont normalement pas considérés comme des entrées peuvent être fuzzés, tels que le contenu des bases de données , la mémoire partagée , les variables d'environnement ou l'entrelacement précis des threads . Un fuzzer efficace génère des entrées semi-valides qui sont « suffisamment valides » pour ne pas être directement rejetées par l' analyseur et « suffisamment invalides » pour pouvoir mettre en évidence des cas particuliers et exercer des comportements de programme intéressants.

Un fuzzer intelligent (basé sur un modèle, basé sur une grammaire, ou basé sur un protocole arbre de syntaxe abstrait , alors un fuzzer intelligent basé sur la mutation utiliserait des transformations aléatoires pour déplacer des sous-arbres complets d'un nœud à un autre. Si l'entrée peut être modélisée par une grammaire formelle , un fuzzer intelligent basé sur la génération instancierait les règles de production pour générer des entrées valides par rapport à la grammaire. Cependant, en général, le modèle d'entrée doit être fourni explicitement, ce qui est difficile à faire lorsque le modèle est propriétaire, inconnu ou très complexe. Si un grand corpus d'entrées valides et non valides est disponible, une technique d'induction grammaticale , telle que l'algorithme L* d' Angluin , serait capable de générer un modèle d'entrée.

Un fuzzer muet ne nécessite pas le modèle d'entrée et peut donc être utilisé pour tester une plus grande variété de programmes. Par exemple, AFL est un fuzzer muet basé sur la mutation qui modifie un fichier de départ en retournant des bits aléatoires , en remplaçant des octets aléatoires par des valeurs « intéressantes » et en déplaçant ou en supprimant des blocs de données. Cependant, un fuzzer muet peut générer une proportion inférieure d'entrées valides et mettre l'accent sur le code d'analyse plutôt que sur les composants principaux d'un programme. L'inconvénient des fuzzers muets peut être illustré au moyen de la construction d'une somme de contrôle valide pour un contrôle de redondance cyclique (CRC). Un CRC est un code de détection d'erreur qui garantit que l' intégrité des données contenues dans le fichier d'entrée est préservée pendant la transmission . Une somme de contrôle est calculée sur les données d'entrée et enregistrée dans le fichier. Lorsque le programme traite le fichier reçu et que la somme de contrôle enregistrée ne correspond pas à la somme de contrôle recalculée, le fichier est rejeté comme non valide. Désormais, un fuzzer qui ne connaît pas le CRC est peu susceptible de générer la somme de contrôle correcte. Cependant, il existe des tentatives pour identifier et recalculer une somme de contrôle potentielle dans l'entrée mutée, une fois qu'un fuzzer basé sur une mutation stupide a modifié les données protégées.

En règle générale, un fuzzer est considéré comme plus efficace s'il atteint un degré de couverture de code plus élevé . La raison en est que si un fuzzer n'utilise pas certains éléments structurels du programme, il n'est pas non plus en mesure de révéler les bogues qui se cachent dans ces éléments. Certains éléments du programme sont considérés comme plus critiques que d'autres. Par exemple, un opérateur de division peut provoquer une erreur de division par zéro , ou un appel système peut faire planter le programme.

Un fuzzer de type boîte noire traite le programme comme une boîte noire et ne connaît pas la structure interne du programme. Par exemple, un outil de test aléatoire qui génère des entrées au hasard est considéré comme un fuzzer de type boîte noire. Par conséquent, un fuzzer de type boîte noire peut exécuter plusieurs centaines d'entrées par seconde, peut être facilement parallélisé et peut s'adapter à des programmes de taille arbitraire. Cependant, les fuzzers de type boîte noire peuvent seulement effleurer la surface et exposer des bugs « superficiels ». Par conséquent, il existe des tentatives de développement de fuzzers de type boîte noire qui peuvent apprendre progressivement la structure interne (et le comportement) d'un programme pendant le fuzzing en observant la sortie du programme à partir d'une entrée. Par exemple, LearnLib utilise l'apprentissage actif pour générer un automate qui représente le comportement d'une application Web.

Un fuzzer en boîte blanche exploite l'analyse du programme pour augmenter systématiquement la couverture du code ou pour atteindre certains emplacements critiques du programme. Par exemple, SAGE exploite l'exécution symbolique pour explorer systématiquement différents chemins dans le programme (une technique connue sous le nom d' exécution concolique ). Si la spécification du programme est disponible, un fuzzer en boîte blanche peut exploiter des techniques de test basées sur des modèles pour générer des entrées et vérifier les sorties du programme par rapport à la spécification du programme. Un fuzzer en boîte blanche peut être très efficace pour exposer les bugs qui se cachent au plus profond du programme. Cependant, le temps utilisé pour l'analyse (du programme ou de sa spécification) peut devenir prohibitif. Si le fuzzer en boîte blanche prend relativement trop de temps pour générer une entrée, un fuzzer en boîte noire sera plus efficace. Par conséquent, il existe des tentatives pour combiner l'efficacité des fuzzers en boîte noire et l'efficacité des fuzzers en boîte blanche.

Un fuzzer en boîte grise utilise l'instrumentation plutôt que l'analyse du programme pour recueillir des informations sur le programme. Par exemple, AFL et libFuzzer utilisent une instrumentation légère pour tracer les transitions de blocs de base exercées par une entrée. Cela conduit à une surcharge de performances raisonnable mais informe le fuzzer de l'augmentation de la couverture du code pendant le fuzzing, ce qui fait des fuzzers en boîte grise des outils de détection de vulnérabilité extrêmement efficaces.

Le fuzzing est principalement utilisé comme une technique automatisée pour exposer les vulnérabilités des programmes critiques pour la sécurité qui pourraient être exploitées avec une intention malveillante. Plus généralement, le fuzzing est utilisé pour démontrer la présence de bugs plutôt que leur absence. Exécuter une campagne de fuzzing pendant plusieurs semaines sans trouver de bug ne prouve pas que le programme est correct. Après tout, le programme peut toujours échouer pour une entrée qui n'a pas encore été exécutée ; l'exécution d'un programme pour toutes les entrées est extrêmement coûteuse. Si l'objectif est de prouver qu'un programme est correct pour toutes les entrées, une spécification formelle doit exister et des techniques issues de méthodes formelles doivent être utilisées.

Pour détecter les bugs, un fuzzer doit être capable de distinguer le comportement attendu (normal) du comportement inattendu (bogué) du programme. Cependant, une machine ne peut pas toujours distinguer un bug d'une fonctionnalité. Dans les tests de logiciels automatisés , ce problème est également appelé le problème de l'oracle de test .

En règle générale, un fuzzer fait la distinction entre les entrées qui plantent et celles qui ne plantent pas en l'absence de spécifications et pour utiliser une mesure simple et objective. Les plantages peuvent être facilement identifiés et peuvent indiquer des vulnérabilités potentielles (par exemple, un déni de service ou une exécution de code arbitraire ). Cependant, l'absence de plantage n'indique pas l'absence de vulnérabilité. Par exemple, un programme écrit en C peut ou non planter lorsqu'une entrée provoque un dépassement de tampon . Le comportement du programme est plutôt indéfini .

Pour rendre un fuzzer plus sensible aux échecs autres que les plantages, des assainisseurs peuvent être utilisés pour injecter des assertions qui font planter le programme lorsqu'un échec est détecté. Il existe différents assainisseurs pour différents types de bogues :

• pour détecter les erreurs liées à la mémoire, telles que les dépassements de tampon et l'utilisation après libération (en utilisant des débogueurs de mémoire tels que AddressSanitizer ),
• pour détecter les conditions de course et les blocages (ThreadSanitizer),
• pour détecter un comportement indéfini (UndefinedBehaviorSanitizer),
• pour détecter les fuites de mémoire (LeakSanitizer), ou
• pour vérifier l'intégrité du flux de contrôle (CFISanitizer).

Le fuzzing peut également être utilisé pour détecter des bogues « différentiels » si une implémentation de référence est disponible. Pour les tests de régression automatisés , les entrées générées sont exécutées sur deux versions du même programme. Pour les tests différentiels automatisés , les entrées générées sont exécutées sur deux implémentations du même programme (par exemple, lighttpd et httpd sont tous deux des implémentations d'un serveur Web). Si les deux variantes produisent des sorties différentes pour la même entrée, alors l'une peut être boguée et doit être examinée de plus près.

L'analyse statique d'un programme analyse un programme sans l'exécuter réellement. Cela peut conduire à des faux positifs lorsque l'outil signale des problèmes avec le programme qui n'existent pas réellement. Le fuzzing en combinaison avec l'analyse dynamique d'un programme peut être utilisé pour essayer de générer une entrée qui témoigne réellement du problème signalé.

Les navigateurs Web modernes sont soumis à un test de fuzzing approfondi. Le code Chromium de Google Chrome est continuellement testé par l'équipe de sécurité de Chrome avec 15 000 cœurs. Pour Microsoft Edge et Internet Explorer , Microsoft a effectué des tests de fuzzing avec 670 années-machine pendant le développement du produit, générant plus de 400 milliards de manipulations DOM à partir d'un milliard de fichiers HTML.

Un fuzzer produit un grand nombre d'entrées dans un temps relativement court. Par exemple, en 2016, le projet Google OSS-fuzz a produit environ 4 000 milliards d'entrées par semaine. Par conséquent, de nombreux fuzzers fournissent une chaîne d'outils qui automatise les tâches manuelles et fastidieuses qui suivent la génération automatisée d'entrées génératrices d'échecs.

Le triage automatisé des bogues est utilisé pour regrouper un grand nombre d'entrées provoquant des pannes par cause première et pour hiérarchiser chaque bogue individuel par gravité. Un fuzzer produit un grand nombre d'entrées, et bon nombre de celles qui provoquent des pannes peuvent effectivement exposer le même bogue logiciel . Seuls certains de ces bogues sont critiques pour la sécurité et doivent être corrigés avec une priorité plus élevée. Par exemple, le centre de coordination CERT fournit les outils de triage Linux qui regroupent les entrées de plantage par la trace de pile produite et répertorie chaque groupe en fonction de leur probabilité d'être exploitable . Le Microsoft Security Research Centre (MSEC) a développé l'outil « !exploitable » qui crée d'abord un hachage pour une entrée de plantage afin de déterminer son caractère unique, puis attribue une note d'exploitabilité :

• Exploitable
• Probablement exploitable
• Probablement pas exploitable, ou
• Inconnu.

Les bugs non signalés et triés peuvent être automatiquement signalés à un système de suivi des bugs . Par exemple, OSS-Fuzz exécute des campagnes de fuzzing à grande échelle et de longue durée pour plusieurs projets logiciels critiques pour la sécurité, où chaque bug distinct non signalé auparavant est signalé directement à un outil de suivi des bugs. Le système de suivi des bugs OSS-Fuzz informe automatiquement le mainteneur du logiciel vulnérable et vérifie à intervalles réguliers si le bug a été corrigé dans la révision la plus récente à l'aide des entrées minimisées induisant des échecs téléchargées.

La minimisation automatique des entrées (ou réduction des cas de test) est une technique de débogage automatisée permettant d'isoler la partie de l'entrée provoquant l'échec qui provoque réellement l'échec. Si l'entrée provoquant l'échec est volumineuse et principalement malformée, il peut être difficile pour un développeur de comprendre exactement ce qui cause le bogue. Étant donné l'entrée provoquant l'échec, un outil de minimisation automatisé supprimerait autant d'octets d'entrée que possible tout en reproduisant le bogue d'origine. Par exemple, le débogage Delta est une technique de minimisation automatique des entrées qui utilise un algorithme de recherche binaire étendu pour trouver une telle entrée minimale.

Voici une liste de fuzzers décrits comme « populaires », « largement utilisés » ou similaires dans la littérature universitaire.