Blog: Compiler testen

[Ironeer]

Warum sollte man Compiler testen?

Compiler sind für die Entwicklung zentrale Programme welche einen großen Teil der entwickelten Software erzeugen. Dies betrifft auch kritische Bereiche. Deshalb können Bugs in Compilern große Auswirkungen haben. Compiler Bugs haben dabei eine besondere Rolle, da es für Entwickler oft nicht zu erkennen ist, ob ein Fehler in ihrem Programmcode oder durch den Compiler entsteht. Außerdem wird Compilern durch ihren häufigen Einsatz ein großes Vertrauen entgegengebracht, welches dazu führt, dass ein Compiler Bug bei der Fehlersuche erst spät in Betracht gezogen wird. Findet man einen Compiler Bug muss man zusätzlich oft lange bis zum nächsten Release auf einen Fix warten und bis dahin einen Workaround finden. ^{1 2} Compiler Bugs sind auch keine Seltenheit, die Entwickler von Csmith, einem später erwähnten Tool, fanden innerhalb von 3 Jahren 325 neue Bugs in C Compilern. ³ Das formale Verifizieren von Compilern ist im Gegensatz zum Testen nur sehr eingeschränkt möglich. Es ist schließlich für eine Turingmaschine schon nicht entscheidbar, ob sie bei gegebenem Input terminiert (Halting-Problem). CompCert ist jedoch ein Tool, welches durch mathematische Operationen auf dem Compiler Sourcecode Compiler für Teile der C Spezifikation verifizieren konnte. Reale Compiler erfüllen dessen Voraussetzungen jedoch nicht. ^{1 4}

Arten von Compiler Bugs

Man kann Compiler Bugs in verschiedene Arten einteilen, im Folgenden werden ein paar Arten genannt ¹:

• das Kompilat ist syntaktisch oder semantisch falsch (entspricht nicht der Spezifikation). Diese Art von Bug wird auch 'Wrong Code Bug', 'Miscompilation' oder 'Semantic non-preservation' genannt
• das Kompilat ist sehr langsam. Fachbegriffe für diesen Bug sind 'Perfmormance-Bug' oder 'Slow Code Bug'
• der Compiler
  • akzeptiert nicht der Spezifikation entsprechenden Code
  • lehnt nach der Spezifikation korrekten Code ab
  • stürzt ab
  • terminiert nicht
• Code terminiert, aber das Kompilat nicht (Besonderer Semantic non-preservation Bug)

Als Beispiel für Ursachen eines Bugs kann man Optimierungen nennen, welche angewendet werden, obwohl sie die Semantik verändern. ³

Probleme während des Testens von Compilern

Wenn man einen Compiler testen möchte, sind hauptsächlich drei Probleme zu lösen, welche hier kurz beschrieben werden sollen.

Testerzeugung (Test Case Generation)

Das erste Problem während des Testens von Compilern ist die Testfallerzeugung. Ein Testfall besteht dabei aus Code, welcher die Spezifikation der zu kompilierenden Sprache erfüllt. Dabei muss der Code sowohl syntaktisch korrekt sein, als auch semantische Anforderungen der Spezifikation erfüllen. ^{5 1}

Ein semantisch und syntaktisch korrektes Stück Code alleine ist jedoch noch kein kompletter Testfall, da auch das Problem des nächsten Abschnitts gelöst werden muss, um einen sinnvollen Testfall zu generieren.

Test Orakel (Test Oracle)

Wenn zu testender Code vorliegt muss entschieden werden, was ein korrektes Erzeugnis (Kompilat) des Compilers dafür ist. Man muss ein Orakel (Test-Oracle) liefern, welches nach jeder Testausführung folgende Frage richtig entscheidet: Hat der Compiler den Test bestanden oder liegt ein Fehler vor?
Dabei gibt es grundsätzlich zwei Wege das Ergebnis zu prüfen. Unüblich ist zu definieren wie ein korrektes Kompilat aussieht, da mehrere Kompilate die gleiche Semantik und damit das gleiche Verhalten haben können. Verbreiteter ist das erwartete Verhalten bei Ausführung des Kompilats festzulegen. Dazu werden Konsolenausgabe oder Assertions genutzt. ^{5 3}

Undefiniertes Verhalten (Undefined Behavior) ¹

In Sprachen wie C wird die Erzeugung von Testfällen mit einem gültigen Orakel durch ein interessantes Phänomen erschwert: dem undefinierten Verhalten (undefined Behavior). Undefiniertes Verhalten tritt für Fälle auf, welche von einer Spezifikation (absichtlich) nicht definiert werden. Damit wird nicht definiert wie sich ein Programm in diesem Fall verhält und jedes Verhalten des Programms ist erlaubt. Enthält Code undefiniertes Verhalten, kann somit nicht gesagt werden, ob der Compiler ihn richtig kompiliert hat. Anders gesagt kann es kein Test Oracle geben. Jedes Verhalten wäre schließlich erlaubt.

In der Compiler-Test-Community ist mir in den meisten Papern die Sprache C begegnet, diese weist 191 undefined Behaviors auf. ³
Hier ein paar Beispiel-Konstrukte für welche die Spezifikation von C kein Verhalten definiert und somit jedes Compiler Verhalten in Ordnung wäre:

• teilen durch 0
• Overflow
• Zeiger (Pointer) an eine nicht genutzte Speicherposition

Als kleine Randnotiz, da wir uns dieses Semester viel mit Java beschäftigt haben: Java besitzt streng genommen kein undefiniertes Verhalten, es beschreibt mindestens verschiedene mögliche Verhaltensweisen. ⁶

Beispiel: Undefined Behavior ¹

Um zu zeigen, wie schwierig es ist ein Test Oracle zu finden (mit oder ohne Undefined Behavior), folgt ein anschauliches Beispiel:

Der folgende Code eines OpenGL Shader ist im Detail nicht relevant, man sieht jedoch, dass er (mehr oder weniger) menschenlesbar ist und nicht autogeneriert wurde:

Wie kann man mit Sicherheit sagen, dass das folgende Bild die richtige Ausgabe des Shader Programms ist und der Compiler keinen Fehler gemacht hat?

Bisher könnte man noch argumentieren, dass ein (händisches) nachrechnen der RGB Werte jedes Pixels eine ausreichende Verifikation darstellt.
Betrachtet man nun jedoch die Spezifikation der OpenGL Shader-Sprache wird auch das unmöglich:

“Any denormalized value [...] can be flushed to O. The rounding mode cannot be set and is undefined.”

"Without any [precision] qualifiers, implementations are permitted to perform such optimizations that effectively modify the order or number of operations used to evaluate an expression, even if those optimizations may produce slightly different results relative to unoptimized code. "

Der Compiler oder der ausführende Prozessor darf also jeden Wert der "klein" ist zu 0 runden. Außerdem dürfen Optimierungen die Reihenfolge und Art der Operationen verändern, selbst wenn dadurch "leicht" andere Ergebnisse entstehen.

Die Folge dieses undefinierten Verhaltens ist, dass sehr viele Bilder mit leicht anderen RGB Werten korrekte Ausgaben des Codes sind. Für Grafiker ist ein leicht anderer Farbwert kein Problem und Hersteller von Compilern und Grafikprozessoren können das Verhalten für ihre Umsetzungen selbst definieren. Solche Spezifikationen, welche den konkreten Umsetzungen bewusst Freiheiten geben werden auch "umbrella smeantics" genannt, da sie alle Parteien unter einem Kompromiss (Regenschirm) vereinen. Die Spezifikation kann Verhalten aber auch offen lassen, um größeren Spielraum für Optimierungen zu lassen.

Test Reduction ⁵

Auf das Problem der Reduzierung von Testfällen kann hier aufgrund des Umfangs nur kurz eingegangen werden. Im Kern geht es darum einen fehlgeschlagenen Test aufzubereiten, um den Ursprung finden zu können (Root-Cause-Analysis). Gute Testfälle sind bereits von minimalem Umfang, große Testfälle müssen jedoch auf den Teil reduziert werden, in welchem das unerwartete Verhalten auftritt. Dieser Schritt wird meist manuell ausgeführt, es gibt jedoch erste Ansätze ihn zu automatisieren, besonders für automatisch generierte Testfälle. Zusätzlich gibt es Überlegungen, wie das Melden und die gelieferten Informationen von gefundenen Fehlern verbessert werden können.

Lösungen

Die folgenden Techniken sind gängige Lösungen für die benannten Probleme.

Random Testing (Fuzzing)

Random Testing (Fuzzing, von deutsch unscharf) stellt eine Technik zur Generierung von syntaktisch korrekten Programmen einer Spezifikation dar. Dabei wird die Grammatik als Grundlage genommen, um zufällig syntaktisch korrekte Programme zu erzeugen. Tools welche diese Aufgabe übernehmen werden Fuzzer oder Fuzzing-Tools genannt. Beispiele sind CSmith und YarpGen für C Code oder RustSmith für Rust. Algorithmische Grundlagen für solche Tools stellt der Purdon-Algorithmus von 1972 dar, welcher gültige Sätze einer Grammatik erzeugt. Eine Studie von 2019 für GCC und CLANG/LLVM hat gezeigt, dass von Fuzzer-Tools gefundene Bugs genauso häufig in realen Programmen (in der Studie dem debian package) vorkommen, wie Bugs welche Programmierer manuell finden. ⁷

Snapshot Testing

Snapshot Testing ist keine Test-Technik die speziell auf Compiler zugeschnitten ist. Bei einem Snapshot Test wird das aktuelle Verhalten eines Programms für konkrete Eingabedaten (nach Prüfung) als korrekt definiert, es wird somit ein Snapshot erstellt. Während eines Durchlaufs des Snapshot Tests wird der Satz an Eingabedaten erneut in das Programm gegeben und das Ergebnis mit dem Snapshot verglichen.

Die Testfälle entstehen meist manuell. Eine Herkunft sind natürlich kreative Überlegungen von Compiler-EntwicklerInnen, welche Fehler vorhersehen. Außerdem gibt es bekannte und erprobte Testfälle, wie zum Beispiel die McCarthy91 Funktion, mit welcher man testet, ob ein Compiler Rekursionen richtig auflöst. ⁸ Eine andere Herkunft kann auch die Spezifikation sein, welche Tests mitliefert (auch Comformance-Test-Suite genannt). Die häufigste Herkunft sind jedoch Testfälle in welchen ein Bug behoben wurde. Dort stellen Snapshot Tests sicher, dass der Bug behoben bleibt (das nennt man Regressions-Tests). ^{1 9}

Snapshot Tests sind besonders hilfreich bei der initialen Entwicklung eines Compilers im Rahmen des Test-Driven-Developments. Regressions-Tests zu erstellen ist ebenfalls eine weit verbreitete Praxis.

Differential Testing ⁵

Als Differential Testing beschreibt man das Vergleichen der Ergebnisse mehrerer Compiler als Test Oracle. Verhalten sich die Ergebnisse der Compiler unterschiedlich muss ein Fehler (oder undefiniertes Verhalten) vorliegen. Differential Testing ist somit nur möglich, wenn eine Sprache mehrere implementierte Compiler hat und bestenfalls einen Compiler der als "golden reference" dient, also als zuverlässig angenommen wird. Alternativ kann neben einem anderen Compiler (cross-compiler differential testing) auch der gleiche Compiler mit anderen aktivierten Optimierungen (cross-optimization differential testing) oder zu einem anderen Versionsstand (cross-version differential testing) als Vergleich genutzt werden. So können in beschränktem Umfang auch Compiler für eigene oder neue Sprachen getestet werden.

¹

Metamorphic Testing ⁵

Das Metamorphic Testing (auch Equivalence Modulo Inputs (EMI) genannt) versucht mehrere syntaktisch verschiedene Testfälle zu generieren, welche jedoch semantisch so vergleichbar sind, dass sie das gleiche Verhalten haben. Ein Testfall schlägt fehl, wenn bei der Ausführung der Kompilate nicht alle Verhalten übereinstimmen. Um aus einem Testfall mehrere Testfälle mit gleichem Verhalten zu generieren werden Tools wie Orion, Athena und Hermes genutzt. Um den initialen Testfall zu generieren, kann zum Beispiel Fuzzing genutzt werden.

¹

Gegenüberstellung der Techniken die ein Oracle bieten

Hier eine Überblicktabelle über die drei Test-Techniken welche ein Oracle definieren:

Überblick über Probleme und Lösungen

Es folgt ein grafischer Überblick über den Ablauf eines Compiler Tests. Die einzelnen Schritte sind durch gestrichelte Boxen den drei benannten Problemen zugeordnet, welche mit blauen Kreisen nummeriert sind. Random Testing ist durch die Nennung vieler Fuzzing Tools als Lösung für das Testcase Generation Problem aufgeführt. Differential Testing und Metamorphic Testing werden als Lösungen für das Test Oracle Problem genannt. Das nicht aufgeführte Snapshot Testing kann als (nicht skalierende) Lösung für die Probleme Testfallgenerierung und Test-Oracle angesehen werden. ⁵

Footnotes

1. Testing Language Implementations, Alastair Donaldson, PLISS 2017 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

2. An Empirical Comparison of Compiler Testing Techniques, Chen, Junjie and Hu, Wenxiang and Hao, Dan and Xiong, Ying:fei and Zhang, Hongyu and Zhang, Lu and Xie, Bing, 2016 ↩

3. Finding and understanding bugs in C compilers, Xuejun Yang, Yang Chen, Eric Eide, John Regehr, 2011 ↩ ↩² ↩³ ↩⁴

4. CompCert: https://compcert.org/motivations.html ↩

5. Compiler Testing: A Systematic Literature Analysis, Yixuan Tang and Zhilei Ren and Weiqiang Kong and He Jiang, 2018 ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

6. Java-Specification: https://docs.oracle.com/javase/specs/index.html ↩

7. Compiler fuzzing: how much does it matter? Michaël Marcozzi, Qiyi Tang, Alastair F. Donaldson, and Cristian Cadar. 2019 ↩

8. Properties of programs and partial function logic, Manna Zohar John McCarthy, 1961 ↩

9. Try Snapshot Testing for Compilers and Compiler-Like Things, Adrian Sampson, 20222 ↩