Test-Case-Reducer sind unterschätzte Debugging-Werkzeuge

• Wenn man in einer großen Eingabe den Teil finden will, der ein Problem verursacht, machen Test-Case-Reducer das Debugging einfacher, indem sie die Eingabe automatisch verkleinern
• Ein Reducer nimmt ein Programm, eine Eingabe und einen Interessantheitstest und prüft wiederholt, ob kürzere Kandidateneingaben dasselbe Problem reproduzieren
• Selbst ein einfacher zeilenlöschender Reducer lässt in /usr/share/dict/words nur ein langes Wort übrig und reduziert in einem C-Beispiel 78 Zeilen in unter 10 Sekunden auf 54
• Interessantheitstests müssen korrekt und schnell geschrieben sein, weil übermäßige Reduktion, langsame Ausführung, endlose Ausführung und parallele Ausführungsumgebungen Probleme verursachen können
• Wenn man in den Interessantheitstest nicht nur die Eingabelänge, sondern auch Metriken wie Fehlerhäufigkeit oder Länge des Execution-Trace aufnimmt, hilft das beim Debugging von nichtdeterministischen Bugs und großen Trace-Logs

---

Verkleinern von Testfällen

• Wenn ein Programm bei einer großen Eingabe abstürzt und unklar ist, welcher Teil der Eingabe die Ursache ist, wird es leichter, die Ursache zu verstehen, wenn man die Eingabe verkleinert
• Manuelle Verkleinerung bedeutet, Teile der Eingabe in einem Texteditor zu löschen und anschließend zu prüfen, ob derselbe Absturz bestehen bleibt
• Bei manueller Verkleinerung übersieht man leicht viele Löschmöglichkeiten, und nach dem Löschen kann das Programm normal beenden oder einen anderen, harmlosen Fehler melden
• Wenn es nur hilft, die voneinander getrennten Teile A und B gemeinsam zu löschen, wächst der Suchraum stark an

Grundstruktur eines Test-Case-Reducers

• Ein Test-Case-Reducer ist ein Werkzeug, das ein Programm, eine Eingabe und einen Interessantheitstest nimmt und die Eingabe kürzer macht
• Der Interessantheitstest gibt 0 zurück, wenn die verkleinerte Eingabe den relevanten Fehler reproduziert, andernfalls einen von 0 verschiedenen Wert
• Reduktionen um 95–99 % sind bei Test-Case-Reducern üblich und können das Debugging erheblich erleichtern
• Der Reducer funktioniert auch dann, wenn er semantisch nicht versteht, welche Teile der Eingabe entfernt werden müssen

• Beispiel für einen einfachen Reducer

  • Das Beispielprogramm liest Zeilen aus einer Datei und gibt Word too long aus, wenn eine Zeile länger als 25 Zeichen ist
  • Der Interessantheitstest gibt 0 zurück, wenn die Programmausgabe Word too long enthält, andernfalls 1
  • Der einfache Python-Reducer liest die Eingabe zeilenweise, schreibt eine Kandidateneingabe mit einer entfernten Zeile in eine temporäre Datei und führt dann den Interessantheitstest aus
  • Wenn die Kandidateneingabe interessant ist, ersetzt sie die aktuelle Eingabe; wenn keine weitere Verkleinerung mehr möglich ist, wird das Ergebnis auf stdout ausgegeben
  • Das Ergebnis bei Ausführung auf /usr/share/dict/words lässt nur antidisestablishmentarianism übrig

Stärkere Reducer und Shrink Ray

• Das Beispiel mit dem 78-zeiligen C-Programm behandelt ein Problem, bei dem die Einstellungen FAST=0 und FAST=1 unterschiedliche Ausgaben erzeugen
• Der Interessantheitstest besteht nur dann, wenn nach dem Kompilieren mit beiden Einstellungen die Ausgabe für FAST=0 0d754a56 ist und die Ausgabe für FAST=1 davon abweicht
• Der einfache Reducer verkleinert die 78 Zeilen C-Eingabe in unter 10 Sekunden auf 54 Zeilen, also um rund 30 % gemessen an der Zeilenzahl
• Wenn man i=0 hinzufügt, sodass nach jedem interessanten Kandidaten wieder ab der ersten Zeile gelöscht wird, steigt die Laufzeit fast auf das Zehnfache und es lassen sich drei weitere Zeilen entfernen
• Shrink Ray bietet mehrere Reduktionsregeln und parallele Ausführung; mit --no-clang-delta nutzt es kein Spezialwissen über C
• Nach etwa 15 Minuten hatte Shrink Ray die Eingabe gemessen in Bytes um mehr als 60 % verkleinert; in einem anderen Fall fand es nach etwa 20 Minuten eine Reduktion um 90 % und verkleinerte anschließend weiter bis auf 99 %
• Shrink Ray kennt die Standard-Syntax für Kommentare und versucht früh, sie zu entfernen; außerdem versucht es, Ganzzahlen auf kleinere Werte zu reduzieren

Schwierigkeiten beim Schreiben von Interessantheitstests

• Test-Case-Reducer folgen dem Interessantheitstest wörtlich. Wenn der Test fälschlich besteht, kommt es zu übermäßiger Reduktion, bei der weiter verkleinert wird als gewünscht
• Shrink Ray prüft explizit, ob der Interessantheitstest eine leere Eingabe akzeptiert, und solche Situationen können häufig vorkommen
• Wenn man im C-Beispiel nur prüft, ob sich die beiden Ausgaben unterscheiden, können auch irrelevante oder irreführende Unterschiede als interessante Eingabe klassifiziert werden
• Die Prüfung test "$slow_out" = "0d754a56" verifiziert, dass die langsame Version tatsächlich das erwartete Verhalten zeigt, und senkt so die Wahrscheinlichkeit übermäßiger Reduktion

• Geschwindigkeit und Timeouts

  • Wenn der Interessantheitstest schnell ist, kann ein Reducer ihn Hunderte Male pro Sekunde ausführen
  • Schon mittelgroße Beispiele können zu Hunderttausenden Reduktionsversuchen führen, sodass die Optimierung des Interessantheitstests großen Einfluss auf die Gesamtzeit hat
  • Es gibt ein Beispiel, in dem der Interessantheitstest etwa dreimal schneller wurde, indem die automatische Erzeugung von Core Dumps deaktiviert wurde
  • Ein Reducer kann durch Entfernen einer Zeile wie i-=1 ein terminierendes Programm in eines verwandeln, das endlos läuft
  • Wenn ein Programm in 0,1 Sekunden läuft, der Timeout aber auf 60 Sekunden gesetzt ist, wird die gesamte Reduktion massiv verlangsamt
  • Bei schnellen Programmen wird timeout häufig auf 1–2 Sekunden aufgerundet; sonst nimmt man etwa das 1,5- bis 2-Fache der anfänglichen Laufzeit

• Parallele Ausführung

  • Reducer wie Shrink Ray führen Interessantheitstests parallel aus
  • Shrink Ray führt jeden Interessantheitstest in einem temporären Verzeichnis aus und räumt dieses Verzeichnis anschließend automatisch auf
  • Es gibt aber Fälle, in denen temporäre Verzeichnisse allein nicht ausreichen, und die nötigen Maßnahmen unterscheiden sich von Fall zu Fall

Determinismus mit Interessantheitstests erzwingen

• Das Beispiel erzeugt wegen len([])==0 einen Divide-by-zero-Fehler, aber wegen der Bedingung random.random() < 0.33 tritt das Problem nur in etwa einem Drittel der Ausführungen auf
• Nichtdeterministische Bugs erscheinen und verschwinden scheinbar zufällig, was die Überprüfung von Hypothesen schwieriger und langwieriger macht
• Wenn der Reducer den Aufruf von random.random() entfernt oder den Bedingungsausdruck verändert, kann aus einem nichtdeterministischen Fehler ein deterministischer werden
• In realen Fällen entsteht Nichtdeterminismus oft dadurch, dass mehrere Teile der Eingabe auf ungünstige Weise zusammenwirken, sodass er sich schwer beseitigen lässt
• Ein Test-Case-Reducer verhält sich wie ein Hill-Climbing-Algorithmus, der die Eingabelänge als Ersatzmetrik für „besser“ verwendet
• Ein Hill-Climbing-Ansatz bleibt leicht in lokalen Optima stecken, und eine kürzere Eingabe ist nicht immer besser für die Fehlersuche

• Wiederholte Ausführung

  • Beim Umgang mit nichtdeterministischen Bugs kann der Interessantheitstest die Eingabe mehrfach ausführen und sie akzeptieren, wenn der relevante Fehler mindestens einmal auftritt
  • Dieser Ansatz kann helfen, die Fehlerhäufigkeit zu erhöhen
  • Ein Test, der schon bei einem einzigen Auftreten besteht, akzeptiert aber auch nichtdeterministische Eingaben, sodass die Nichtdeterministik während der Reduktion sogar zunehmen kann
  • Ein strengerer Ansatz akzeptiert die Eingabe nur dann, wenn der Fehler in allen n Wiederholungen auftritt
  • Solch ein strenger Test erschwert den Start von Shrink Ray, weil die Wahrscheinlichkeit sinkt, dass die ursprüngliche Eingabe besteht; im Beispiel mit drei Wiederholungen beträgt sie 3,6 %
  • Ein praktischer Workaround ist, zunächst mit einem Test vom Typ „mindestens 1 Fehler in n Läufen“ zu beginnen und später, wenn eine verkleinerte Eingabe den Fehler häufiger auslöst, auf „Fehler in n aufeinanderfolgenden Läufen“ umzuschalten

Globale Zähler und andere Zielmetriken

• Manuelle Eingriffe sind mächtig, aber man muss Shrink Ray dabei beobachten, und es ist leicht, den richtigen Eingriffszeitpunkt zu verpassen
• Wenn man einen Reducer nach anderen Eigenschaften als der Eingabelänge steuern will, kann man diese Eigenschaft innerhalb eines einzelnen Interessantheitstests erzwingen
• Beim Debugging von yk ist statt der Eingabelänge oft eher die Länge des Execution-Trace wichtig, also ein Wert nahe an der Zahl der vom Programm ausgeführten Instruktionen
• Die Ausgabe YKD_LOG="$t:jit-asm" schreibt textuelles Trace-IR und Maschinenbefehle in eine Datei; eine kurze jit-asm-Ausgabe erleichtert das Debugging
• wc -l zählt die Zeilen in der Log-Datei und dient als Ersatzmetrik, die der Trace-Länge nahekommt
• Der Interessantheitstest behandelt eine Eingabe als nicht interessant, wenn die aktuelle Zahl der Trace-Zeilen größer ist als der bisher beste Wert; der Bestwert wird in /tmp/global_best gespeichert
• Dieser Ansatz ist bei paralleler Reduktion nicht sicher und enthält Annahmen über die Art, wie der Reducer aufgerufen wird, wird für Wegwerfskripte aber als akzeptable Unvollkommenheit angesehen
• In einem yk-Segfault-Fall ließ eine normale Reduktion einen Trace mit 40K Zeilen zurück, während diese Technik statt einer stärker verkleinerten Eingabe einen Trace mit 10,1K Zeilen erzeugte und half, den zugrunde liegenden Bug innerhalb von 30 Minuten zu finden

Kernaussagen

• Test-Case-Reducer sind nicht nur für Compiler-Entwickler nützliche Werkzeuge, sondern können auch bei Nicht-Compiler-Problemen eingesetzt werden
• Über das grundlegende Ziel hinaus, die Eingabelänge zu verringern, kann man mit Interessantheitstests auch Eigenschaften wie Fehlerhäufigkeit, Wall-Clock-Zeit, Grad an Nichtdeterminismus oder Trace-Länge steuern
• Die Genauigkeit, Ausführungsgeschwindigkeit, Timeout-Werte und Parallelisierungssicherheit des Interessantheitstests bestimmen maßgeblich die praktische Wirksamkeit eines Reducers
• Auch ohne die Semantik von Eingabe und Programm wirklich zu verstehen, kann ein Reducer ein Problem in kleinerer Form erhalten und so die Produktivität beim Debugging steigern

[GN⁺]

Lobste.rs-Kommentare

• Ich frage mich ehrlich: Gibt es überhaupt jemanden, der den Wert der automatischen Reduktion von Testfällen nicht anerkennt? Das Wort „unterbewertet“ klingt, als gäbe es Leute, die keine Testfallreduktion wollen.
  Selbst wenn man den Bug sofort eingrenzen kann, braucht man für Regressionstests nicht trotzdem einen reduzierten Fall?

  • Wahrscheinlich haben die meisten Entwickler das noch nie als Technik betrachtet
  • Der erste Satz des Artikels lautet: „Test-case reducers are less well known than they should be, [...]“, und genau so habe ich es auch erlebt, obwohl ich seit Jahren Leuten empfehle, Fuzzing und Property-based Testing zu verwenden.
    Beides enthält oft eine Form der Reduktion von Fehlfällen oder „shrinking“, und genau dadurch wird es viel praktischer nutzbar
  • Bei Fuzzern kenne ich das grob. Nachdem der Fuzzer einen Fehlfall gefunden hat, verkleinert er ihn automatisch, und dieser Teil funktioniert sehr gut.
    Meine Erfahrung mit Fuzzing allgemein, insbesondere mit AmericanFuzzyLop und AFL++, ist allerdings, dass die Einrichtung so schmerzhaft ist, dass ich es meist vermeide.
    Die meisten Bugs, auf die ich stoße, sind außerdem eher von der Art „für irgendeinen Benutzer irgendwo verhält es sich falsch“ als „wenn man diese Eingabedatei hineinwirft, funktioniert es falsch“. Manchmal lässt sich das noch auf „unter bestimmten Bedingungen verhält es sich nach einer Reihe von Schritten falsch“ reduzieren, aber 1) ich weiß nicht so recht, wie man einen automatischen Testfall-Reduzierer auf „ein Benutzer macht Dinge in einer Reihenfolge“ anwenden soll, und 2) sobald man einen Weg gefunden hat, das lokal zu reproduzieren, sind 99 % des Debuggings im Grunde erledigt.
    Vermutlich würde der Autor diese meine Haltung als „unterbewertet“ ansehen
  • Ich glaube, schon die Zahl der Leute, die überhaupt wissen, was Testfallreduktion ist, ist klein

• Dieser Artikel und seine Beispiele sagen zwar, dass Reduzierer auch außerhalb von Compiler-Szenarien breiter genutzt werden sollten, aber die Perspektive ist ziemlich stark auf Compiler-Autoren ausgerichtet.
  Wie ~silentbicycle schrieb, findet die meiste Testfallreduktion im Kontext von Fuzzern oder Property-based Testing statt, wo die Reduktionsfunktion in ein größeres Framework eingebaut ist. Compiler sind eines der ungewöhnlichen Gebiete, in denen eigenständige Testfall-Reduzierer nützlich sind. Mir ist nicht klar, ob es viele andere Fälle gibt, in denen ein eigenständiger Reduzierer hilfreich ist.
  Der Teil über Determinismus ist ebenfalls interessant. Das Beispiel beginnt mit einer Eingabedatei, die einen Bug auslöst, also mit einem Skript, das Determinismus schafft, und nicht damit, dass das fehlerhafte Programm selbst, also der Interpreter, deterministisch wäre. Es ist nicht ganz klar, ob der Artikel meint, dass die „interestingness“-Technik auch in nicht Compiler-bezogenen Situationen funktioniert, in denen das fehlerhafte Programm selbst nicht deterministisch ist.
  Um Testprobleme an Fuzzing und Testfallreduktion anzupassen, würde ich empfehlen, eine nummerierte Menge imperativer Befehle zu erstellen. In jeden Befehl kommt eine leichte Konsistenzprüfung, die Testfehler erkennen kann und auch Fälle erwischt, die nicht sofort crashen. Schwere Konsistenzprüfungen würde ich in separate Befehle auslagern, damit die Tests nicht so stark verlangsamt werden. Bei einfachem Zufallstesten wählt das Test-Harness die Befehle zufällig aus, bis etwas kaputtgeht; wenn man später auf ein Fuzzer-Harness umstellt, lässt man die Befehle stattdessen durch einen Fuzz-Eingabe-Byte-Stream auswählen. Dann bekommt man automatisch all die guten Dinge wie deterministische Regressionstests und Testfallreduktion.
  Ich hatte keinen großen Erfolg damit, libfuzzer ausdrücklich anzuweisen, Testfälle zu verkleinern, vermutlich weil libfuzzer das schon beim Erzeugen der Eingaben getan hat. Deshalb hatte ich nie einen starken Anreiz, weitere Interestingness-Prüfungen auszuprobieren, mit denen ein allgemeiner Fuzzer beim Verkleinern von Testfällen helfen könnte. Es würde mich interessieren, ob andere damit Erfolg hatten

  • Stimme voll zu. Ich verwende so etwas oft. Man erstellt eine symbolische Darstellung einer zustandsbehafteten Schnittstelle, baut meist einen einfachen Interpreter auf Basis von switch-case oder match, erzeugt dann zufällig Listen von Operationen, führt sie aus und reduziert die Eingaben, die eine assert wegen Verletzung von Vor-/Nachbedingungen oder interner Beschädigung auslösen.
    Ob man das nun Property-based Testing, Fuzzing oder leichtgewichtiges Model Checking nennt: Es kann erstaunlich effektiv sein, um tiefe Bugs zu finden. Ich habe viele zustandsbehaftete Schnittstellen gesehen, bei denen die einzelnen Operationen für sich korrekt sind, ihre Annahmen aber leicht gegeneinander verschoben sind; wenn diese Operationen dann auf unerwartete Weise kombiniert werden, wächst das zu interner Beschädigung aus.
    Es ist auch nützlich, die Operationsliste parallel gegen eine einfache In-Memory-Hash-Table- oder listenbasierte Implementierung laufen zu lassen und zu prüfen, ob die Ergebnisse übereinstimmen. Falls nicht, ist das meist entweder ein Bug oder ein Grenzfall, der besser dokumentiert werden sollte
  • Ich arbeite gelegentlich an Transportoptimierung und stoße dabei oft auf ziemlich komplexe Szenarien, in denen Invarianten verletzt werden. Ein Testfall-Reduzierer wäre da wirklich großartig, aber früher musste ich mich damit zufriedengeben, das manuell zu verkleinern[0].
    Leider sind die Datendateien so komplex, dass shrinkray sie wohl kaum verarbeiten kann. Es liest tabellarische Daten aus mehreren unterschiedlichen „Dateien“, und es gibt Abhängigkeiten über große Distanzen hinweg, sodass man das Domänenwissen über die Reduktionsmethode vermutlich selbst einkodieren müsste.
    Wenn ich mir das Tempo der KI-Entwicklung ansehe, würde ich beim nächsten solchen Szenario wahrscheinlich einen maßgeschneiderten Reduzierer schreiben.
    [0] Wenn man eine verschwommene Ontologie bemühen will: Ein Optimierungsproblem ist ein Suchproblem zur Minimierung von Kosten, und das ist im Grunde dasselbe wie ein Compiler, also kein vollkommen sauberes Beispiel

• Ich habe das dreimal gelesen, um herauszufinden, wie ich das auf mit pytest geschriebene Tests anwenden kann.
  Ich will die Komplexität meiner Test-Suite verringern und werde es wohl beim vierten Mal noch einmal lesen, wenn ich gerade nicht arbeite

  • Wenn du Python verwendest, wäre der erste Schritt, Hypothesis einzuführen; dort ist Testfallreduktion bereits eingebaut

• Letztes Jahr habe ich ein Problem mit der Testausführungsreihenfolge in der CI untersucht und dabei ein Tool gebaut, das beim Verkleinern einer Testliste hilft.
  Im Grunde lief es darauf hinaus, Zeilen wiederholt zu halbieren und zu sehen, ob es noch ausgeführt werden kann.
  Das Skript selbst ist ziemlich fehlerhaft, aber es war schon cool, eine Liste von 5000 Tests auf ungefähr 4 Tests zu reduzieren, die meinen Concurrency-Bug auslösen.
  Ich frage mich wirklich, ob Shrink Ray in meinem Fall einfach funktioniert hätte. Ich finde ernsthaft, „eine Menge von Zeilen anhand eines Tests reduzieren“ sollte Teil des Standard-Sets von Kommandozeilen-Tools sein

• Dazu passend verwendet auch Property-based Testing einen ziemlich ähnlichen Ansatz, indem es den Zustandsraum der erzeugten Eingaben „reduziert“, um Gegenbeispiele für Tests zu erzeugen.
  Der Vorteil von Property-based Testing ist, dass man den Suchraum lenken und strukturieren kann. Man kann die Eingaben zu einer Menge von Transitionen machen, die eine Zustandsmaschine antreiben, welche das Programm modelliert.
  Ich bin jedes Mal erstaunt, wie wenig diese Technik genutzt wird, selbst in Bereichen, in denen sie besonders gut passt, etwa bei Datenbanken und verteilten Systemen. Noch letzte Woche habe ich bei $WORK in nur wenigen Stunden einen solchen Test gebaut und schnell herausgefunden, dass unser System nicht konvergiert. Der Test hat einen sauberen Trace ausgegeben, den Kollegen sehen und sofort verstehen konnten.
  Persönlich halte ich das beim Debugging komplexer Systeme für die Testtechnik mit dem besten Return on Investment