Fuzzer une calculatrice !

“Beware of bugs in the above code; I have only proved it correct, not tried it.” — Donald Knuth

Une étape majeure dans le développement d’un logiciel est de vérifier qu’il se comporte comme on l’attend. C’est cette étape qui nous intéresse aujourd’hui : comment tester un programme ? Comment rendre son logiciel “robuste” ?

La première solution est la plus naturelle : essayer de tester soi-même toutes les fonctionnalités du programme. Cependant, deux problèmes vont se poser très rapidement. Tout d’abord, nos tests manuels sont très souvent biaisés : on prend malgré soi des habitudes lorsque l’on utilise un logiciel et l’on ne pense donc pas à tester certaines fonctionnalités.
Un second problème est la quantité de tests à effectuer : elle est souvent infinie… Dans le cas d’Epsilon, le logiciel de notre calculatrice, l’utilisateur peut appuyer sur 46 touches différentes ; pour tester tous les scénarios où l’utilisateur appuie sur 10 touches, on aurait besoin de faire déjà 42420747482776576 tests manuels. À raison d’un appuie de touche par seconde, cela prendrait… plus d’un milliard d’années ! Et un scénario de dix touches, c’est pourtant loin d’être bien long.

Automatiser des tests

Mais finalement, pourquoi ne pas générer automatiquement des routines de tests aléatoires et les exécuter sur le logiciel cible ? Dans le cas d’Epsilon, on pourrait générer une suite d’événements tapée par l’utilisateur (par exemple : OK, flèche gauche, sinus, 9, …), et la faire exécuter automatiquement par l’ordinateur. Il est en effet bien plus rapide que nous : en moyenne un ordinateur est capable de simuler 150 000 appuis de touches par seconde.

cat /dev/urandom|pv|./app.bin
1.54MiB 0:00:10 [ 152KiB/s]

Et l’ordinateur ne se lassera jamais, que ce soit pour générer de faux scénarios de test ou pour les appliquer effectivement. Aussi appelée monkey-testing, cette simple méthode ne discrimine aucun test, la métaphore est assez parlante : une armée de singes appuyant chacun sur les boutons de leur calculatrice, en espérant trouver un bug.

Automatique, mais intelligent !

L’ensemble des tests étant immense, on pourrait dérouler des milliards de scénarios pendant des heures sans voir apparaître un problème intéressant. C’est pourquoi, il est important de guider le générateur de scénarios vers des situations intéressantes. C’est précisément ce que fait un fuzzer : on lui fournit des séquences d’événements que l’utilisateur est susceptible de taper et le fuzzer tricote à partir de ces routines pour en générer aléatoirement d’autres qui sont susceptibles d’être intéressantes. Plus spécifiquement, le fuzzer american fuzzy lop utilise un algorithme génétique : on lui fournit en entrée un ensemble de routines qu’il modifie en leur faisant subir des altérations mineures - des “mutations” ; puis, ces nouveaux tests sont sélectionnés lorsqu’ils apportent de nouveaux états de l’exécutable. Pour savoir que tel ou tel scénario exerce de nouvelles zones du programme, celui-ci doit être compilé avec une instrumentation spéciale qui permet à AFL de savoir quelles parties du programmes sont utilisées par un scénario donné.

En pratique, on fournit au fuzzer une dizaine de scénario d’exemples, et quelques heures (ou jours…) après, il nous renvoie les routines d’événements qui mettent le programme en échec ou qui ne terminent jamais. Le fuzzer a de plus l’amabilité d’essayer de minimiser les routines pour ne nous renvoyer que les sous-routines intéressantes pour faciliter la correction du programme.

Le fuzzing n’est pas une solution miracle

Le fuzzing, c’est évidemment génial (merci Michal Zalewski pour afl) cependant le critère d’échec est restreint : la non terminaison du programme ou sa sortie due à une erreur. Toutefois, Epsilon par exemple pourrait afficher “1+2 = 11” sans pour autant planter : le fuzzer ne se rendrait pas compte de l’erreur. Toutes les méthodes de tests ont leur propres défauts : bien qu’il soit rapide et automatisé, le fuzzing ne peut pas avoir de notion du fonctionnement interne d’un logiciel et de ses exigences. C’est pourquoi une combinaison de plusieurs méthodes de test est souvent nécessaire pour éradiquer le plus de bugs possibles. Dans notre cas, nous utilisons entre autres les suivants :

• Des tests unitaires: on génère une tripotée de tests spécifiques à notre logiciel qui constituent une source de vérité. Par exemple, “1+1 doit être égal à 2” ou “racine(8) doit se simplifier en 2*racine(2)”. Ces tests permettent de faire évoluer le code tout en vérifiant régulièrement que l’on n’a pas perturbé d’autres fonctionnalités.
• Des programmes de détection de défauts de gestion de la mémoire (memcheck de Valgrind)
• De l’analyse statique (clang-checker et coverity scan)
• Et enfin et malgré tout, de bons vieux tests manuels !