Les réducteurs de cas de test sont des outils de débogage sous-estimés

• Lorsqu’il faut trouver, dans une grande entrée, la partie qui provoque un problème, un réducteur de cas de test réduit automatiquement l’entrée pour faciliter le débogage
• Le réducteur prend un programme, une entrée et un test d’intérêt, puis vérifie de façon répétée si des entrées candidates plus courtes reproduisent le même problème
• Même un simple réducteur par suppression de lignes peut, à partir de /usr/share/dict/words, ne conserver qu’un seul mot long, et dans un exemple en C, réduire 78 lignes à 54 en moins de 10 secondes
• Le test d’intérêt doit être écrit de façon précise et rapide à cause des risques de sur-réduction, des exécutions lentes, des boucles infinies et des environnements d’exécution parallèles
• En intégrant au test d’intérêt des métriques comme la fréquence d’apparition de l’erreur ou la longueur d’une trace d’exécution, et pas seulement la longueur de l’entrée, on peut mieux déboguer les bugs non déterministes et les gros journaux de trace

---

Réduction de cas de test

• Quand un programme plante avec une grande entrée et qu’on ne sait pas quelle partie de cette entrée en est la cause, réduire l’entrée aide à identifier plus facilement l’origine du problème
• La réduction manuelle consiste à supprimer une partie de l’entrée dans un éditeur de texte, puis à vérifier si le même plantage se produit toujours
• La réduction manuelle fait souvent manquer de nombreuses possibilités de suppression, et après suppression le programme peut se terminer normalement ou produire une autre erreur normale
• Si l’effet recherché n’apparaît qu’en supprimant ensemble deux parties éloignées A et B, l’espace de recherche augmente fortement

Structure de base d’un réducteur de cas de test

• Un réducteur de cas de test est un outil qui prend un programme, une entrée et un test d’intérêt, puis rend l’entrée plus courte
• Le test d’intérêt renvoie 0 si l’entrée réduite reproduit l’erreur recherchée, et une valeur différente de 0 sinon
• Avec un réducteur de cas de test, une réduction de 95 à 99 % est courante, ce qui peut rendre le débogage beaucoup plus simple
• Le réducteur peut fonctionner sans comprendre sémantiquement quelles parties de l’entrée doivent être supprimées

• Exemple de réducteur simple

  • Le programme d’exemple lit les lignes d’un fichier et affiche Word too long si l’une d’elles dépasse 25 caractères
  • Le test d’intérêt renvoie 0 si la sortie du programme contient Word too long, sinon 1
  • Le simple réducteur Python lit l’entrée ligne par ligne, écrit dans un fichier temporaire une entrée candidate avec une ligne supprimée, puis exécute le test d’intérêt
  • Si l’entrée candidate est intéressante, elle devient l’entrée courante, et lorsqu’on ne peut plus réduire davantage, le résultat est affiché sur stdout
  • Exécuté sur /usr/share/dict/words, il ne laisse plus que antidisestablishmentarianism

Des réducteurs plus puissants et Shrink Ray

• L’exemple d’un programme C de 78 lignes traite d’un problème où les réglages FAST=0 et FAST=1 produisent des sorties différentes
• Le test d’intérêt ne réussit qu’après compilation avec les deux réglages, lorsque la sortie avec FAST=0 vaut 0d754a56 et que celle avec FAST=1 est différente de cette valeur
• Le simple réducteur peut réduire l’entrée C de 78 lignes à 54 lignes en moins de 10 secondes, soit environ 30 % de réduction en nombre de lignes
• Si l’on ajoute i=0 pour recommencer les suppressions depuis la première ligne à chaque fois qu’une entrée intéressante est trouvée, le temps d’exécution augmente presque d’un facteur 10 et on gagne encore 3 lignes
• Shrink Ray fournit plusieurs règles de réduction et une exécution parallèle, et avec --no-clang-delta, il n’utilise pas de connaissances spécifiques au C
• Après environ 15 minutes, Shrink Ray avait réduit l’entrée de plus de 60 % en octets, et dans un autre cas, il a trouvé une réduction d’environ 90 % après 20 minutes avant de pousser jusqu’à 99 %
• Shrink Ray connaît la syntaxe standard des commentaires et essaie de les supprimer très tôt, et tente aussi de réduire les entiers vers des valeurs plus petites

Les difficultés d’écriture d’un test d’intérêt

• Un réducteur de cas de test suit le test d’intérêt à la lettre, donc si le test accepte par erreur une entrée, une sur-réduction peut se produire et aller plus loin que ce qui est souhaité
• Shrink Ray vérifie explicitement si le test d’intérêt accepte une entrée vide, et ce type de situation peut survenir assez souvent
• Dans l’exemple C, si l’on vérifie seulement que les deux sorties sont différentes, des écarts de sortie sans importance ou trompeurs peuvent être classés comme intéressants
• La vérification test "$slow_out" = "0d754a56" confirme que la version lente a bien le comportement attendu, ce qui réduit le risque de sur-réduction

• Vitesse et timeouts

  • Si le test d’intérêt est rapide, le réducteur peut l’exécuter des centaines de fois par seconde
  • Même un exemple de taille moyenne peut entraîner plusieurs centaines de milliers de tentatives de réduction, si bien que l’optimisation du test d’intérêt a un effet majeur sur le temps total
  • Il existe un cas où le test d’intérêt a été rendu environ 3 fois plus rapide en désactivant la génération automatique de core dumps
  • Le réducteur peut supprimer une ligne comme i-=1 et transformer ainsi un programme qui se termine en un programme qui tourne indéfiniment
  • Si un programme s’exécute en 0,1 seconde mais que le timeout est fixé à 60 secondes, la réduction entière devient beaucoup plus lente
  • Pour les programmes rapides, on utilise souvent un timeout arrondi à 1 ou 2 secondes ; sinon, on prend environ 1,5 à 2 fois le temps d’exécution initial

• Exécution parallèle

  • Des réducteurs comme Shrink Ray exécutent les tests d’intérêt en parallèle
  • Shrink Ray exécute chaque test d’intérêt dans un répertoire temporaire et nettoie automatiquement ce répertoire
  • Un simple répertoire temporaire ne suffit pas toujours, et les mesures nécessaires varient selon les cas

Utiliser le test d’intérêt pour forcer le déterminisme

• L’extrait d’exemple provoque une erreur de division par zéro à cause de len([])==0, mais comme la condition random.random() < 0.33 n’est vraie qu’environ un tiers du temps, le problème n’apparaît que dans environ un tiers des exécutions
• Les bugs non déterministes rendent les hypothèses plus difficiles et plus longues à vérifier, parce que l’erreur apparaît et disparaît de façon aléatoire
• Si le réducteur supprime l’appel à random.random() ou modifie la condition, une erreur non déterministe peut devenir déterministe
• En pratique, la non-déterminisme vient souvent d’interactions défavorables entre plusieurs parties de l’entrée, ce qui peut rendre sa suppression difficile
• Un réducteur de cas de test fonctionne comme un algorithme de montée de colline qui utilise la longueur de l’entrée comme métrique de substitution pour « meilleur »
• Cette approche de montée de colline se bloque facilement dans des optima locaux, et une entrée plus courte n’est pas toujours meilleure pour explorer une erreur

• Méthode par exécutions répétées

  • Pour traiter un bug non déterministe, on utilise une approche où le test d’intérêt exécute l’entrée plusieurs fois et l’accepte si l’erreur recherchée survient au moins une fois
  • Cette approche peut aider à augmenter la fréquence d’apparition de l’erreur
  • Un test qui réussit dès qu’une erreur apparaît au moins une fois accepte aussi des entrées non déterministes, si bien que la non-déterminisme peut en fait augmenter au fil de la réduction
  • Une approche plus stricte consiste à n’accepter l’entrée que si l’erreur se produit dans les n répétitions
  • Un test strict rend le démarrage de Shrink Ray plus difficile parce que l’entrée initiale a peu de chances de réussir ; dans l’exemple avec 3 répétitions, la probabilité initiale de réussite n’est que de 3,6 %
  • Un contournement pratique consiste à commencer par un test « au moins une erreur sur n exécutions », puis à passer à un test « erreur sur n exécutions consécutives » une fois obtenue une entrée réduite où l’erreur survient plus souvent

Compteurs globaux et autres métriques cibles

• L’intervention manuelle est puissante, mais elle oblige à surveiller Shrink Ray et il est facile de rater le bon moment pour intervenir
• Pour guider le réducteur avec une propriété autre que la longueur de l’entrée, on peut imposer cette propriété dans un unique test d’intérêt
• Dans le débogage de yk, la longueur de la trace d’exécution, c’est-à-dire une valeur proche du nombre d’instructions exécutées par le programme, est plus importante que la longueur de l’entrée
• La sortie YKD_LOG="$t:jit-asm" écrit dans un fichier une trace IR textuelle et des instructions machine, et une sortie jit-asm courte facilite le débogage
• wc -l sert à compter le nombre de lignes du fichier journal et joue le rôle de métrique de substitution pour la longueur de la trace
• Le test d’intérêt traite l’entrée comme non intéressante si le nombre courant de lignes de trace dépasse le meilleur minimum précédent, ce minimum étant stocké dans /tmp/global_best
• Cette méthode n’est pas sûre en réduction parallèle et repose sur certaines hypothèses quant à la façon dont le réducteur invoque le test, mais pour un petit script jetable, cette imperfection est jugée acceptable
• Dans un cas de segfault de yk, une réduction normale laissait une trace de 40 K lignes, alors que cette technique a produit, au lieu d’une entrée plus courte, une trace de 10,1 K lignes et a permis d’identifier le bug de fond en moins de 30 minutes

Points clés

• Les réducteurs de cas de test ne sont pas des outils utiles uniquement aux auteurs de compilateurs ; ils peuvent aussi servir pour des problèmes qui n’ont rien à voir avec les compilateurs
• Au-delà de l’objectif de base qui consiste à réduire la longueur de l’entrée, on peut guider le test d’intérêt vers des propriétés comme la fréquence d’erreur, le temps mur, le niveau de non-déterminisme ou la longueur de trace
• La précision du test d’intérêt, sa vitesse d’exécution, ses timeouts et sa sûreté en exécution parallèle déterminent largement l’efficacité réelle du réducteur
• Même sans presque rien comprendre à la sémantique de l’entrée et du programme, le réducteur peut conserver le problème sous une forme plus petite et améliorer la productivité du débogage

[GN⁺]

Commentaires sur Lobste.rs

• Je me demande vraiment s’il existe des gens qui ne reconnaissent pas la valeur de la réduction automatique de cas de test. Le mot « sous-estimé » donne l’impression qu’il y aurait des personnes qui ne veulent pas toujours réduire les cas de test.
  Même si on peut identifier immédiatement le bug, n’a-t-on pas quand même besoin d’un cas réduit pour les tests de régression ?

  • En général, les développeurs n’ont probablement même jamais pensé à ça comme à une technique
  • La première ligne de l’article dit : « Test-case reducers are less well known than they should be, [...] », et même après avoir recommandé pendant des années aux gens d’utiliser le fuzzing et les tests basés sur les propriétés, c’était exactement mon impression.
    Les deux incluent souvent une forme de réduction des cas d’échec, ou de « shrinking », ce qui les rend bien plus pratiques à utiliser
  • J’en ai une idée générale dans le contexte des fuzzers. Le fuzzer trouve un cas d’échec puis le réduit automatiquement, et cette partie fonctionne très bien.
    En revanche, d’après mon expérience du fuzzing en général, surtout avec AmericanFuzzyLop et AFL++, la configuration est tellement pénible que j’ai tendance à l’éviter.
    La plupart des bugs que je rencontre ressemblent aussi moins à « ce fichier d’entrée provoque un mauvais comportement » qu’à « ça se comporte mal pour un certain utilisateur, quelque part ». Parfois, on peut encore réduire ça à « si l’on suit une série d’étapes dans certaines conditions, ça se comporte mal », mais 1) je ne vois pas très bien comment appliquer un réducteur automatique de cas de test à « un utilisateur fait des choses dans un certain ordre », et 2) une fois qu’on a trouvé comment reproduire le problème localement, 99 % du travail de débogage est déjà fait.
    J’imagine que l’auteur considérerait probablement cette attitude de ma part comme une forme de « sous-estimation »
  • Je pense déjà que les gens qui savent ce qu’est la réduction de cas de test sont une minorité

• Cet article et ses exemples disent que les réducteurs devraient être plus largement utilisés hors des cas de compilateurs, tout en gardant un point de vue assez fortement biaisé vers les auteurs de compilateurs.
  Comme l’a écrit ~silentbicycle, la plupart des réductions de cas de test se produisent dans le cadre du fuzzing ou des tests basés sur les propriétés, avec une fonction de réduction intégrée à un framework plus large. Les compilateurs sont l’un des rares domaines où un réducteur autonome est utile. Je ne sais pas vraiment s’il existe beaucoup d’autres cas où un réducteur autonome serait utile.
  L’aspect déterministe est aussi intéressant. L’exemple commence par un cas où le déterminisme vient du fichier d’entrée qui provoque le bug, c’est-à-dire le script, et non d’une propriété déterministe du programme bogué lui-même, à savoir l’interpréteur. L’article n’indique pas clairement s’il veut dire que la technique d’« interestingness » fonctionne aussi dans des cas non liés aux compilateurs où le programme bogué lui-même est non déterministe.
  Pour reformuler un problème de test d’une manière adaptée au fuzzing et à la réduction de cas de test, je recommande de construire un ensemble numéroté de commandes impératives. Chaque commande devrait inclure une vérification de cohérence légère capable de détecter un échec de test, y compris dans les cas où il n’y a pas de crash immédiat. Les vérifications lourdes gagnent à être déplacées dans des commandes séparées pour ralentir moins fortement les tests. Pour des tests aléatoires simples, le harnais de test peut choisir des commandes au hasard jusqu’à ce que quelque chose casse ; ensuite, au moment de passer à un harnais de fuzzing, il suffit d’utiliser le flux d’octets d’entrée du fuzzer pour choisir les commandes. On obtient alors automatiquement les bonnes choses comme des tests de régression déterministes et la réduction de cas de test.
  Je n’ai pas obtenu de résultats particulièrement convaincants en demandant explicitement à libfuzzer de réduire des cas de test, probablement parce qu’il les avait déjà réduits pendant la génération des entrées. Du coup, je n’ai pas vraiment été motivé à essayer davantage de vérifications d’interestingness pour aider des fuzzers généralistes à réduire les cas de test. Je me demande si d’autres ont déjà eu du succès avec ça

  • Tout à fait d’accord. J’utilise souvent ce genre d’approche. On construit une représentation symbolique d’une interface avec état, généralement avec un interpréteur simple basé sur switch-case ou match, puis on génère aléatoirement une liste d’opérations à exécuter et on réduit les entrées qui déclenchent des assert révélant des violations de préconditions/postconditions ou une corruption interne.
    Qu’on appelle cela tests basés sur les propriétés, fuzzing ou model checking léger, cela peut être étonnamment efficace pour trouver des bugs profonds. J’ai souvent vu des interfaces avec état où chaque opération est correcte prise isolément, mais où leurs hypothèses respectives divergent légèrement ; lorsqu’on combine ces opérations de manière inattendue, cela peut se transformer en corruption interne.
    Il est également utile d’exécuter la liste d’opérations en parallèle d’une implémentation simple en mémoire, par exemple fondée sur une table de hachage ou une liste, puis de vérifier que les résultats concordent. Quand il y a une différence, c’est généralement soit un bug, soit un cas limite qui mérite une meilleure documentation
  • Il m’arrive de travailler sur de l’optimisation du transport, et je tombe souvent sur des scénarios assez complexes où des invariants sont violés. Avoir un réducteur de cas de test serait vraiment appréciable, mais autrefois il fallait se contenter de réduire ça manuellement[0].
    Malheureusement, les fichiers de données sont tellement complexes qu’il me semble peu probable que shrinkray puisse les traiter. Il lit des données tabulaires provenant de plusieurs « fichiers » différents, avec aussi des dépendances à longue portée, donc il faudrait probablement encoder directement dans la méthode de réduction des connaissances métier sur le domaine.
    Vu le rythme des progrès de l’IA, je pense que la prochaine fois que je rencontrerai un scénario de ce type, j’écrirai un réducteur sur mesure.
    [0] Si l’on veut invoquer une ontologie ambiguë, un problème d’optimisation est un problème de recherche visant à minimiser un coût, ce qui en fait en pratique quelque chose de similaire à un compilateur ; ce n’est donc pas un exemple parfaitement distinct

• J’ai dû lire ça trois fois pour comprendre comment appliquer cette idée à des tests écrits avec pytest.
  Je veux réduire la complexité de ma suite de tests, donc je pense le relire une quatrième fois quand je ne travaillerai pas

  • Si vous utilisez Python, la première étape consiste à adopter Hypothesis, qui intègre la réduction de cas de test

• L’an dernier, en enquêtant sur un problème d’ordre d’exécution des tests dans la CI, j’ai créé un outil qui aidait à réduire une liste de tests.
  En gros, il fonctionnait en coupant les lignes par moitié et en réessayant.
  Le script lui-même a pas mal de bugs, mais voir une liste de 5000 tests se réduire à environ 4 tests déclenchant mon bug de concurrence, c’était impressionnant.
  Je me demande vraiment si Shrink Ray aurait simplement fonctionné dans mon cas. Je pense sincèrement que « réduire un ensemble de lignes en se basant sur un test » devrait faire partie des utilitaires en ligne de commande standard

• Sur un sujet connexe, les tests basés sur les propriétés utilisent aussi une approche assez similaire consistant à « réduire » l’espace des états des entrées générées afin de produire des contre-exemples de test.
  L’avantage des tests basés sur les propriétés, c’est qu’ils permettent de guider et de structurer l’espace de recherche. On peut transformer les entrées en un ensemble de transitions qui pilotent une machine à états modélisant le programme.
  Je suis toujours surpris de voir à quel point cette technique reste sous-utilisée, même dans des domaines où elle est particulièrement adaptée, comme les bases de données et les systèmes distribués. Pas plus tard que la semaine dernière, j’ai monté un test de ce type en quelques heures à peine chez $WORK, et il a rapidement révélé que notre système ne convergait pas. Le test produisait une trace claire, immédiatement compréhensible lorsqu’on la montrait à des collègues.
  Personnellement, je pense que c’est la technique de test avec le meilleur retour sur investissement pour déboguer des systèmes complexes