C-Reduce-Techniken, die sich in jeder Sprache verwenden lassen

 (bernsteinbear.com)
1 Punkte von GN⁺ 2024-11-28 | 1 Kommentare | Auf WhatsApp teilen
  • C-Reduce ist ein Werkzeug zum Verkleinern von Reproduktionscode für C-Compiler-Bugs, lässt sich aber auch auf andere Sprachen anwenden, wenn es eine deterministische Bedingung, eine schnelle Reproduktion und bearbeitbare Quelldateien gibt
  • Das Beispiel zeigt den Prozess, einen Bug zu verkleinern, der beim Ausführen von scrapscript in RustPython auftrat; interesting.sh prüft dabei anhand einer bestimmten Fehlermeldung, ob der Fehler reproduziert wurde
  • Allein mit creduce --not-c interesting.sh scrapscript.py wurde die Dateigröße schnell reduziert, und schon früh war ein Fortschritt von fast 50 % Reduktion zu sehen
  • --not-c ist eine Option, die C-spezifische Reduktions-Pässe vermeidet, und hilft bei Eingaben wie Python, unnötige Laufzeit zu sparen
  • Wenn sich die Bedingung für die Fehlerreproduktion als kurzes Skript formulieren lässt, können auch Bug-Reports für Nicht-C-Sprachen mit C-Reduce kleiner und leichter handhabbar gemacht werden

Bedingungen für den Einsatz von C-Reduce bei Nicht-C-Eingaben

  • C-Reduce ist ein von Regehr und Kollegen entwickeltes Werkzeug zur Minimierung von Reproduktionscode für C-Compiler-Bugs
  • Wenn eine 10.000 Zeilen lange C-Datei einen Clang-Bug auslöst, kann es verwendet werden, um die riesige Datei automatisch zu verkleinern, statt sie unverändert einzureichen
  • Es wirkt wie ein C-spezifisches Werkzeug, kann aber auch für Eingaben anderer Sprachen verwendet werden, wenn die folgenden Bedingungen erfüllt sind

    • Deterministische Bedingung

      • Eine relativ schnelle Reproduktionsmethode, die der Reduktionsgeschwindigkeit zugutekommt
      • Eine oder mehrere bearbeitbare Quelldateien, die C-Reduce verkleinern kann
      • Deterministische Bedingungen lassen sich mit einem Schleifen-Wrapper auch probabilistisch nachbilden

Beispiel: Verkleinerung einer RustPython-Bug-Reproduktion

  • Beim Ausführen von scrapscript in RustPython trat ein Bug auf; um ihn zu melden, wurde das Skript interesting.sh geschrieben
  • Das Skript führt scrapscript.py mit dem absoluten Pfad zur RustPython-Binärdatei aus und sucht dann in der Ausgabe einschließlich Standardfehler nach der folgenden Zeichenkette
    • tried to push value onto stack but overflowed max_stackdepth
  • Der Ausführungsbefehl lautet wie folgt
    • creduce --not-c interesting.sh scrapscript.py
  • C-Reduce führt den Interestingness-Test parallel aus und verkleinert dabei die Dateigröße schnell
    • Beispielhafte Fortschrittswerte werden als 0.5 %, 9.2 %, 18.1 %, 47.5 % usw. angezeigt
    • Innerhalb weniger Sekunden wird die Datei um fast 50 % verkleinert
    • Zum Zeitpunkt des Schreibens war bereits eine Reduktion von 96.9 % erreicht
  • Ohne --not-c verwendet C-Reduce zahlreiche C-spezifische Pässe
    • Bei Python-Eingaben können diese Pässe die Laufzeit verlangsamen
    • Das eigentliche Ergebnis wird dadurch wahrscheinlich nicht wesentlich verändert
  • Verwandte Inhalte wurden später auf die Seite Delta debugging verschoben

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-11-28
Hacker-News-Kommentare

  • Da keine reduzierte Datei geteilt wurde, habe ich es selbst ausprobiert. Ich habe RustPython gebaut, scrapscript.py geholt, den Pfad in interesting.sh geändert und es mit nix run nixpkgs#creduce -- --not-c interesting.sh scrapscript.py ausgeführt. Am Ende blieb es bei ungefähr 96,4 %, 7347 Byte stehen; das Ergebnis steht unter https://gist.github.com/judofyr/47cba8a20cb2cd5798943ef975d0...

    • Mir kam dabei der Gedanke, dass jemand anderes Sorge hatte, das Programm könne während der Reduktion kaputtgehen und auf der lokalen Maschine destruktive Aktionen ausführen. Wenn man den Reducer als Source-to-Source-Nix-Derivation ausführt, könnte man damit riskante Aktionen verhindern und ihn auch leicht auf Remote-Builder verteilen, dachte ich
    • Zum Vergleich: shrinkray reduziert es nach etwa 10 Minuten auf 162 Byte: https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...
      Wenn man es länger laufen lässt, wird es vielleicht noch etwas besser, aber es sah fast so aus, als würde es nicht mehr weiterkommen, also wurde mir langweilig und ich habe abgebrochen

  • Auch John Regehr, der Autor von C-Reduce, empfiehlt, für diesen Zweck Shrinkray auszuprobieren. Shrinkray sei darauf ausgelegt, formatunabhängig zu arbeiten, und passe gut zu Fällen, in denen C-Reduce nicht gut ist: https://mastodon.social/@regehr/113489759789563570

  • Es gibt ein Paper von John Regehr und weiteren Autoren aus dem Jahr 2012, das die Funktionsweise erklärt: https://fsl.cs.illinois.edu/publications/regehr-chen-cuoq-ei...

    • Ich habe dieses Paper gelesen und verstehe immer noch nicht wirklich, wie das möglich ist. Es wirkt, als würde es für beliebige Programmiersprachen Tokenisierung, das Zusammenführen von Zeilen, das Entfernen von Tokens usw. verstehen; ich frage mich, ob es ein weiteres Paper gibt, das nur diesen Algorithmus erklärt
    • Dieses Paper behandelt nicht C-Reduce insgesamt, sondern drei domänenspezifische Test-Case-Reducer, die dem Projekt hinzugefügt wurden
      Soweit ich mich erinnere, sind die meisten domänenunabhängigen Reduktionen in C-Reduce eher schlichtes Brute Force

  • Ich habe C-Reduce gerade erst entdeckt und bin schon fasziniert. Es fühlt sich ähnlich an wie damals, als ich zum ersten Mal git bisect entdeckt habe
    Das sollte ich mir irgendwo im Hinterkopf behalten, damit ich es verwenden kann, wenn irgendwann die passende Situation kommt

    • In meinem ersten Job nach dem Studium war ich in einem C/C++-Compiler-Team und habe solche Arbeit manuell gemacht. Dass man dasselbe automatisieren kann, ist ziemlich beeindruckend
    • Ich hatte bei cc65, einem C-Compiler für den 6502-Prozessor, ein Problem, das wie ein Compiler-Bug aussah. Zielsysteme sind etwa C64, NES und Apple 1
      Ich überlege, das einzurichten. Da VICE offenbar eine Funktion unterstützt, mit der es in Dateien des Host-Betriebssystems „ausgibt“, könnte man die Tests wohl im Emulator laufen lassen
    • Zusammen mit einem Generator für zufällige Testeingaben ist es großartig

  • Delta Debugging ist kein neues Konzept: https://en.wikipedia.org/wiki/Delta_debugging
    Meine eigene Delta-Debugging-Implementierung delta ist über 19 Jahre alt: https://github.com/dsw/delta
    Damals, als Microsoft Open Source noch als „Krebsgeschwür“ bezeichnete, schickte Microsoft Research jemanden in mein Büro, um mich zu bitten, es öffentlich freizugeben, also habe ich es als Open Source veröffentlicht. Auch in Latners Einführung zu LLVM wird es als „standardmäßiges Delta-Debugging-Tool“ erwähnt, es ist also ein recht bekanntes Werkzeug: https://aosabook.org/en/v1/llvm.html

    • C-Reduce ist etwas ausgefeilter als einfaches Delta Debugging. Laut Abstract des Papers „Test-Case Reduction for C Compiler Bugs“ von 2012 sind die Ergebnisse von C-Reduce im Durchschnitt mehr als 25-mal kleiner als die anderer Reducer oder der Reducer, die Compiler-Entwickler zuvor am häufigsten verwendet hatten
      Die Schlussfolgerung ist also, dass effektive Programmreduktion mehr erfordert als simples Delta Debugging. Natürlich ist auch C-Reduce inzwischen ein 12 Jahre altes Werkzeug
      Gleichzeitig ist das verlinkte LLVM-Tool BugPoint auf LLVM IR beschränkt, während C-Reduce allgemeiner wirkt. Automatische Tools und Techniken zur Minimierung von Test-Cases sind den meisten Entwicklern noch immer unbekannt; daher kann dieser Artikel nützlich sein, auch wenn die Idee in diesem Bereich schon lange bekannt ist

  • Ich habe einen Artikel mit Vorher-nachher-Beispielen gefunden: https://pramodkumbhar.com/2024/01/c-reduce-systematically-ta...
    Trotzdem verstehe ich noch nicht gut, woher es bei jeder Iteration weiß, was entfernt werden soll. Ein gewisses Maß an Tokenisierung muss es geben, aber ich weiß nicht, wie das über mehrere Programmiersprachen hinweg funktioniert

  • creduce ist großartig
    Als ich ein obskures LLVM-Target-Backend entwickelte, hatte ich ein Testskript, das mit CSmith stundenlang zufällige Testprogramme generierte. Wenn es zu einem Crash kam, ließ es automatisch C-Reduce laufen und legte eine Datei zum Untersuchen ab; das war wirklich eine enorme Hilfe

  • Funktioniert auch gut mit SQL. Ich nutze es in der Praxis und bin über https://github.com/sqlancer/sqlancer?tab=readme-ov-file#redu... darauf gestoßen.

  • Wenn nicht erklärt wird, warum es auch mit anderen Sprachen als C funktioniert, ist das schwer zu glauben. Ich halte es nicht für gelogen, aber dass das ohne LLM geht, irritiert mich.

    • Kurz gesagt lassen sich einige Reduktions-Passes recht gut auf C-artige Sprachen verallgemeinern, und diese Passes gehören zu den wirksamsten.
      Wenn man etwa die Eingabe nach C-Art tokenisiert und dann zufällig Stücke der Länge etwa 1 bis 13 verwirft, funktioniert das bei den meisten C-ähnlichen Sprachen gut, weil sie ähnliche Tokenisierungsregeln haben; so lassen sich unnötige Qualifier oder Attribute gut entfernen. Auch ein Pass, der Einheiten mit ausgeglichenen Klammern (), {}, [] entfernt, ist in fast allen Sprachen nützlich. Das Entfernen von Kommentaren und Whitespace ist ebenfalls effektiv, da viele Sprachen wie C die Stile /* */ und // verwenden.
      Tatsächlich gibt es nicht viele Passes, die sehr spezifisch für C/C++ sind. Nach meiner Erfahrung ist eine der großen Schwächen von creduce, dass es bei Reduktionsschritten zum Entfernen von Templates – also bei einer Aufgabe, die vergleichsweise leicht zu automatisieren scheint – wirklich schlecht ist.
    • Ich empfehle, das von asmeurer verlinkte PLDI-Paper zu überfliegen. Es ist gut zusammengefasst.
      Manche Transformationen sind ziemlich C-spezifisch und nutzen das Clang-Frontend, andere sind recht allgemein und dürften bei Algol-artigen Sprachen im Großen und Ganzen funktionieren. Da es ein modulares Tool ist, kann man bei Bedarf auch Transformationen hinzufügen, die andere Sprachen verstehen.
    • Das ist eher Computer Science alter Schule. Ich hoffe, HN hat diese traditionelle Computer Science nicht schon vergessen.
      Gemeint sind hier Dinge wie Algorithmen, nicht unheimliches Machine Learning. Dazu gehört auch so etwas wie Prolog für AI zu verwenden, mit dem kleinen Nachteil, dass es für den Zweck, AI zu bauen, nicht besonders gut funktioniert.
    • Wenn ich nicht verstehe, wie es funktioniert, weiß ich nicht, ob es sicher ist, es so zu benutzen. Könnte creduce das veränderte Eingabeskript ausführen und meine Dateien löschen oder mein Mittagessen wegfuttern?
    • Ohne das Paper gelesen zu haben, würde ich vermuten, dass es einem Fuzzer ähnelt, der Mutationen anwendet, die die Eingabegröße verringern.

  • Wie ist es im Vergleich zu dustmite? https://dlang.org/blog/2020/04/13/dustmite-the-general-purpo....