Übersetzer für Programmiersprachen sind äußerst komplexe Anwendungen, an die hohe
Korrektheitsanforderungen gestellt werden: Ist ein Übersetzer fehlerhaft (d.h. weicht sein Verhalten
vom dem durch die Sprachspezifikation definierten Verhalten ab), so generiert dieser u.U.
fehlerhaften Code oder stürzt bei der Übersetzung mit einer Fehlermeldung ab. Solche Fehler in
Übersetzern sind oftmals schwer zu bemerken oder zu umgehen. Nutzer erwarten deshalb i.A. eine
(möglichst) fehlerfreie Implementierung des verwendeten Übersetzers.Leider lassen sowohl vergangene Forschungsarbeiten als auch Fehlerdatenbanken im Internet vermuten,
dass kein real verwendeter Übersetzer fehlerfrei ist. Es wird deshalb an Ansätzen geforscht, mit
deren Hilfe die Qualität von Übersetzern gesteigert werden kann. Da die formale Verifikation (also
der Beweis der Korrektheit) in der Praxis oftmals nicht möglich oder rentabel ist, zielen viele der
Forschungsarbeiten darauf ab, Übersetzer möglichst umfangreich und automatisiert zu testen. In den
meisten Fällen erhält der zu testende Übersetzer dabei ein Testprogramm als Eingabe. Anschließend
wird das Verhalten des Übersetzers bzw. des von ihm generierten Programms überprüft: Weicht dieses
vom erwarteten Verhalten ab (stürzt der Übersetzer also beispielsweise bei einem gültigen
Eingabeprogramm mit einer Fehlermeldung ab), so wurde ein Fehler im Übersetzer gefunden. Soll dieser
Testvorgang automatisiert stattfinden, ergeben sich zwei wesentliche Herausforderungen:
Woher kommen die Testprogramme, auf die der Übersetzer angewendet wird?
Was ist das erwartete Verhalten des Übersetzers bzw. des von ihm erzeugten Codes? Wie kann bestimmt werden, ob das tatsächliche Verhalten des Übersetzers korrekt ist?
Während die wissenschaftliche Literatur diverse Lösungen für die zweite Herausforderung vorstellt,
die auch in der Praxis bereits etabliert sind, stellt die automatisierte Generierung zufälliger
Testprogramme noch immer eine große Hürde dar. Damit Testprogramme zur Detektion von Fehlern in
allen Teilen des Übersetzers verwendet werden können, müssen diese allen Regeln der jeweiligen
Programmiersprache genügen, d.h. die Programme müssen syntaktisch und semantisch korrekt (und damit
übersetzbar) sein. Auf Grund der Vielzahl an Regeln "echter" Programmiersprachen stellt die
Generierung solcher übersetzbarer Programme eine schwierige Aufgabe dar. Dies wird zusätzlich
dadurch erschwert, dass das Programmgenerierungsverfahren möglichst effizient arbeiten muss: Die
wissenschaftliche Literatur zeigt, dass die Effizienz eines solchen Verfahrens maßgebliche
Auswirkungen auf seine Effektivität hat -- nur wenn in kurzer Zeit viele (und große) Programme
generiert werden können, kann das Verfahren sinnvoll zur Detektion von Übersetzerfehlern eingesetzt
werden.
In der Praxis scheitert das automatisierte Testen von Übersetzern deshalb oftmals daran, dass kein
zugeschnittener Programmgenerator verfügbar ist und die Entwicklung eines solchen einen zu hohen
Aufwand bedeutet. Ziel unseres Forschungsprojekts ist daher die Entwicklung von Verfahren, die den
Aufwand für die Implementierung von effizienten Programmgeneratoren reduzieren.
Im Jahr 2018 haben wir mit der Entwicklung eines entsprechenden Werkzeugs begonnen. Als Eingabe
dient eine Spezifikation der syntaktischen und semantischen Regeln der jeweiligen Programmiersprache
in Form einer abstrakten Attributgrammatik. Eine solche erlaubt eine knappe Notation der Regeln auf
hohem Abstraktionsniveau. Ein von uns neu entwickelter Algorithmus erzeugt dann Testprogramme, die
allen spezifizierten Regeln genügen. Der Algorithmus nutzt dabei diverse technische Ideen aus, um
eine angemessene Laufzeit zu erreichen. Dies ermöglicht die Generierung großer Testfallmengen in
vertretbarer Zeit, auch auf üblichen Arbeitsplatzrechnern. Eine erste Evaluation hat nicht nur
gezeigt, dass unser Verfahren sowohl effektiv als auch effizient ist, sondern auch dass es flexibel
einsetzbar ist. So haben wir mit Hilfe unseres Verfahrens nicht nur Fehler in den C-Übersetzern gcc
und clang entdeckt (unser Verfahren erreicht dabei eine ähnliche Fehleraufdeckungsgüte wie ein
sprachspezifischer Programmgenerator aus der wissenschaftlichen Literatur), sondern auch diverse
Bugs in mehreren SMT-Entscheidern. Einige der von uns entdeckten Fehler waren den jeweiligen
Entwicklern zuvor noch unbekannt.