La technique C-Reduce utilisable dans n’importe quel langage

 (bernsteinbear.com)
1 points par GN⁺ 2024-11-28 | 1 commentaires | Partager sur WhatsApp
  • C-Reduce est un outil qui réduit le code de reproduction de bugs de compilateurs C, mais il peut aussi s’appliquer à d’autres langages dès lors qu’on dispose d’une condition déterministe, d’une reproduction rapide et de fichiers source modifiables
  • L’exemple montre la réduction d’un bug survenu lors de l’exécution de scrapscript avec RustPython ; interesting.sh détermine si le bug est reproduit en recherchant un message d’erreur précis
  • La simple exécution de creduce --not-c interesting.sh scrapscript.py a rapidement réduit la taille du fichier, avec une progression montrant près de 50 % de réduction dès le début
  • --not-c est une option qui évite les passes de réduction propres au C, ce qui aide à réduire le temps d’exécution inutile sur des entrées comme du Python
  • Si l’on peut créer un court script décrivant les conditions de reproduction d’un bug, C-Reduce permet aussi de rendre les rapports de bug pour des langages autres que C plus petits et plus faciles à traiter

Conditions pour utiliser C-Reduce sur des entrées autres que du C

  • C-Reduce est un outil créé par Regehr et ses collègues pour minimiser le code de reproduction de bugs de compilateurs C
  • Lorsqu’un fichier C de 10 000 lignes déclenche un bug dans Clang, il permet de le réduire automatiquement au lieu d’envoyer l’énorme fichier tel quel
  • Même s’il ressemble à un outil réservé au C, il peut aussi être utilisé avec des entrées dans d’autres langages si les conditions suivantes sont réunies

    • Condition déterministe

      • Une méthode de reproduction relativement rapide, ce qui aide la réduction à aller vite
      • Un ou plusieurs fichiers source modifiables que C-Reduce peut réduire
      • La condition déterministe peut aussi être imitée de manière probabiliste à l’aide d’un wrapper en boucle

Exemple de réduction d’une reproduction de bug RustPython

  • Un bug est survenu lors de l’exécution de scrapscript avec RustPython, et un script interesting.sh a été écrit pour le signaler
  • Le script exécute scrapscript.py avec le chemin absolu du binaire RustPython, puis recherche la chaîne suivante dans la sortie, y compris l’erreur standard
    • tried to push value onto stack but overflowed max_stackdepth
  • La commande d’exécution est la suivante
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce exécute les tests d’intérêt en parallèle et réduit rapidement la taille du fichier
    • La progression de l’exemple est affichée avec des valeurs comme 0,5 %, 9,2 %, 18,1 %, 47,5 %, etc.
    • En quelques secondes, le fichier est réduit de près de 50 %
    • Au moment de terminer l’article, la réduction atteint 96,9 %
  • Sans --not-c, C-Reduce utilise de nombreuses passes propres au C
    • Sur une entrée Python, ces passes peuvent ralentir l’exécution
    • Elles ne changent probablement pas substantiellement le résultat lui-même
  • Le contenu associé a ensuite été déplacé vers la page Delta debugging

À lire aussi

1 commentaires

 
GN⁺ 2024-11-28
Commentaires sur Hacker News

  • Comme le fichier réduit n’était pas partagé, je l’ai lancé moi-même. J’ai compilé RustPython, récupéré scrapscript.py, puis modifié le chemin dans interesting.sh et exécuté nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py. Au final, ça s’est arrêté autour de 96,4 %, 7 347 octets, et le résultat est ici : https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

    • Une réflexion qui m’est venue : quelqu’un craignait que, pendant la réduction, le programme se casse et puisse effectuer des opérations destructrices sur la machine locale. En exécutant le réducteur comme une derivation Nix source-to-source, on pourrait peut-être empêcher les comportements dangereux et le déployer facilement aussi sur des builders distants
    • À titre de comparaison, shrinkray descend jusqu’à 162 octets en une dizaine de minutes : https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      En le laissant tourner plus longtemps, on pourrait peut-être faire un peu mieux, mais ça avait l’air presque bloqué, alors je me suis lassé et je l’ai arrêté

  • John Regehr, l’auteur de C-Reduce, recommande lui aussi d’essayer Shrinkray pour cet usage. Shrinkray a été conçu pour fonctionner indépendamment du format, et c’est, selon lui, un outil bien adapté dans des cas où C-Reduce s’en sort mal : https://mastodon.social/@regehr/113489759789563570

  • Il existe un article de 2012, écrit par John Regehr et d’autres auteurs, qui explique son fonctionnement : https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • J’ai lu cet article, mais je ne comprends toujours pas vraiment comment c’est possible. Il semble comprendre la tokenisation, la fusion de lignes, la suppression de tokens, etc., pour un langage de programmation arbitraire ; je me demande s’il existe un autre article qui explique uniquement cet algorithme
    • Cet article ne porte pas sur C-Reduce dans son ensemble, mais sur trois réducteurs de cas de test propres à un domaine ajoutés au projet
      Si je me souviens bien, la plupart des réductions non spécifiques à un domaine dans C-Reduce relèvent plutôt de la force brute assez simple

  • Je viens de découvrir C-Reduce et je suis déjà accro. Ça me rappelle la première fois que j’ai découvert git bisect
    Il faut que je garde ça dans un coin de ma tête pour pouvoir l’utiliser un jour, quand la bonne situation se présentera

    • À mon premier poste après l’université, dans une équipe de compilateurs C/C++, je faisais ce genre de travail manuellement. C’est assez bluffant de pouvoir automatiser la même chose
    • J’ai rencontré ce qui ressemble à un bug de compilateur dans cc65, un compilateur C pour processeur 6502. Les cibles sont du genre C64, NES, Apple 1
      Je me demande si je vais le configurer. VICE prend apparemment en charge une fonction permettant de « sortir » vers des fichiers du système d’exploitation hôte, donc il devrait être possible de lancer les tests dans l’émulateur
    • C’est excellent utilisé avec un générateur aléatoire d’entrées de test

  • Le delta debugging n’est pas un concept nouveau : https://en.wikipedia.org/wiki/Delta_debugging
    Mon implémentation de delta debugging, delta, a plus de 19 ans : https://github.com/dsw/delta
    À l’époque où Microsoft qualifiait l’open source de « cancer », Microsoft Research a envoyé quelqu’un jusqu’à mon bureau pour me demander de le publier, et je l’ai donc publié en open source. L’introduction à LLVM de Latner mentionne aussi l’« outil standard de delta debugging », c’est donc un outil assez connu : https://aosabook.org/en/v1/llvm.html

    • C-Reduce est un peu plus sophistiqué qu’un simple delta debugging. D’après le résumé de l’article de 2012 « Test-Case Reduction for C Compiler Bugs », les résultats de C-Reduce sont en moyenne plus de 25 fois plus petits que ceux d’autres réducteurs, ou que les réducteurs que les développeurs de compilateurs utilisaient le plus jusque-là
      Autrement dit, une réduction efficace de programmes nécessite davantage qu’un simple delta debugging. Bien sûr, C-Reduce est désormais lui aussi un outil vieux de 12 ans
      En même temps, l’outil LLVM lié, BugPoint, est spécifique à LLVM IR, tandis que C-Reduce semble plus général. Les outils et techniques de minimisation automatique de cas de test restent encore peu familiers à la plupart des développeurs ; cet article peut donc être utile même si l’idée est connue depuis longtemps dans le domaine

  • J’ai trouvé un article avec des exemples avant/après : https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    Malgré tout, je ne comprends toujours pas bien comment il sait quoi supprimer à chaque itération. Il doit bien y avoir un certain degré de tokenisation, mais je ne vois pas comment cela fonctionne à travers plusieurs langages de programmation

  • creduce est excellent
    Quand je développais un backend cible LLVM assez obscur, j’utilisais un script de test qui générait pendant des heures des programmes de test aléatoires avec CSmith. En cas de crash, il lançait automatiquement C-Reduce et me laissait un fichier à inspecter ; ça m’a énormément aidé

  • Fonctionne aussi très bien avec SQL. Je l’utilise en pratique, et je l’ai découvert via https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu...

  • Sans explication sur la raison pour laquelle ça marche aussi avec des langages autres que C, c’est une affirmation difficile à croire. Je ne pense pas que ce soit un mensonge, mais dire que ça se fait sans LLM, c’est déroutant

    • En bref, certaines passes de réduction se généralisent assez bien aux langages de la famille C, et ces passes font partie des plus efficaces
      Par exemple, tokeniser l’entrée à la manière de C puis supprimer au hasard des blocs d’environ 1 à 13 éléments fonctionne bien pour enlever des qualificateurs ou attributs inutiles, car la plupart des langages proches de C ont des règles de tokenisation similaires. Une passe qui supprime des unités de parenthèses équilibrées (), {}, [] est aussi utile dans presque tous les langages. La suppression des commentaires et des espaces est également efficace, puisque beaucoup de langages utilisent les styles /* */ et // comme en C
      En réalité, il n’y a pas tant de passes vraiment spécifiques à C/C++. D’après mon expérience, l’un des gros points faibles de creduce est qu’il est vraiment mauvais pour l’étape de réduction qui consiste à supprimer des templates, une tâche qui semble pourtant relativement facile à automatiser
    • Je recommande de parcourir l’article PLDI lié par asmeurer. Il est bien résumé
      Certaines transformations sont assez spécifiques à C, car elles utilisent le frontend Clang, tandis que d’autres sont assez générales et ont de bonnes chances de fonctionner globalement avec les langages de la famille Algol. Comme c’est un outil modulaire, on peut aussi ajouter, si on le souhaite, des transformations qui comprennent d’autres langages
    • C’est plutôt de l’ancienne informatique. J’espère que HN n’a pas déjà oublié cette tradition de l’informatique classique
      Il est ici question de choses comme des algorithmes, pas d’un apprentissage automatique inquiétant. Cela inclut aussi des approches comme l’utilisation de Prolog pour l’IA, avec le petit inconvénient que ça ne fonctionne pas très bien pour l’objectif de créer de l’IA
    • Si je ne comprends pas comment ça marche, je ne sais pas si l’utiliser de cette façon est sûr. creduce pourrait-il exécuter le script d’entrée modifié et supprimer mes fichiers, voire manger mon déjeuner ?
    • Sans avoir lu l’article, je devinerais que ça ressemble à un fuzzer qui applique des mutations allant dans le sens d’une réduction de la taille de l’entrée

  • Par rapport à dustmite, qu’est-ce que ça donne ? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo...