AG-Fuzzer

Softwaresysteme, die strukturierte Eingaben verarbeiten, verfügen oft nicht über vollständige und aktuelle Spezifikationen, die sowohl die Eingabesyntax als auch die Semantik der Eingabeverarbeitung beschreiben. Während sich Verfahren zum Grammar Mining bisher auf die Wiederherstellung syntaktischer Strukturen konzentriert haben, blieb die Semantik der Eingabeverarbeitung weitgehend unerforscht. In dieser Arbeit stellen wir einen neuartigen Ansatz zur Ableitung attributierter Grammatiken aus Parser-Implementierungen vor. Ausgehend von einer Eingabegrammatik analysiert unsere Technik dynamisch die Implementierung rekursiv-absteigender Parser, um die semantischen Aspekte der Eingabeverarbeitung zu rekonstruieren, wodurch Spezifikationen in Form attributierter Grammatiken entstehen. Durch die Beobachtung von Programmausführungen und die Abbildung des Laufzeitverhaltens des Programms auf die Grammatik extrahieren wir systematisch semantische Aktionen und betten sie in die Grammatikregeln ein. Dies ermöglicht eine umfassende Wiederherstellung der Spezifikation. Wir demonstrieren die Machbarkeit unseres Ansatzes anhand einer ersten Reihe von Programmen und zeigen, dass er das Programmverhalten mithilfe der generierten attributierten Grammatiken präzise reproduzieren kann.

Eine Vielzahl von Softwaresystemen enthält Komponenten, die strukturierte Eingaben parsen und verarbeiten. Neben Programmiersprachen, die von Compilern oder Interpretern analysiert werden, gibt es zahlreiche Komponenten, die standardisierte oder proprietäre Datenformate unterschiedlicher Komplexität verarbeiten. Selbst wenn solche Komponenten ursprünglich auf Basis einer Spezifikation, etwa einer Grammatik, entwickelt und getestet wurden, können zahlreiche Änderungen und Anpassungen im Laufe der Softwareentwicklung dazu führen, dass sich nicht mehr genau bestimmen lässt, welche Eingaben tatsächlich akzeptiert werden. In dieser Situation kann Grammar Mining eingesetzt werden, um die Spezifikation in Form einer Grammatik zu rekonstruieren. Etablierte Verfahren liefern bereits brauchbare Ergebnisse, sofern ausreichend Eingabedaten zur vollständigen Abdeckung der Eingabesprache vorhanden sind. Diese Vollständigkeit zu erreichen, stellt jedoch eine große Herausforderung dar. In der Praxis stehen meist nur Eingabedaten zur Verfügung, die während des Betriebs der Softwaresysteme aufgezeichnet wurden. Werden diese Daten für das Grammar Mining verwendet, spiegelt die resultierende Grammatik nur die tatsächlich verarbeiteten Eingaben wider, nicht jedoch die vollständige Grammatik der von der Softwarekomponente akzeptierten Eingabesprache. Dadurch fehlen in der generierten Grammatik Randfälle oder zuvor unterstützte Funktionen, die in den verfügbaren Eingabedaten nicht mehr vorkommen. Diese Arbeit begegnet dieser Herausforderung, indem sie einen neuartigen Ansatz zur automatischen Generierung von Eingaben für das Grammar Mining vorstellt. Obwohl Eingabegeneratoren bereits für Fuzz-Testing eingesetzt werden, ist unklar, ob sie sich auch für Grammar Miner eignen. Aufbauend auf dem Grammar Miner Mimid präsentiert diese Arbeit einen vollautomatisierten Ansatz zur Eingabegenerierung. Der Ansatz nutzt Dynamic Symbolic Execution (DSE) und erweitert diese um zwei Mechanismen, um die Einschränkungen von DSE bei strukturierten Eingabe-Parsern zu überwinden. Erstens wird die Suche nach neuen Eingaben durch eine iterative Erweiterung gesteuert, die mit einer Eingabe aus einem einzelnen Zeichen beginnt und diese schrittweise erweitert. Zweitens ist die Eingabegenerierung in einen neuartigen dreiphasigen Ansatz gegliedert, der die Generierung von Eingaben für Parser-Funktionen aufteilt. Die vorgeschlagene Methode wurde anhand einer vielfältigen Menge von elf Benchmark-Anwendungen aus der bestehenden Literatur evaluiert. Die Ergebnisse zeigen, dass der Ansatz für die extrahierten Grammatiken eine Präzision und Trefferquote erreicht, die nahe an jener liegt, die mit modernsten Grammar Minern wie Mimid erzielt wird. Bemerkenswert ist, dass er erfolgreich subtile Merkmale und Randfälle in Parsern aufdeckt, die von solchen Grammar Minern typischerweise übersehen werden. Die Wirksamkeit der Methode wird durch empirische Belege gestützt, die zeigen, dass sie in verschiedenen Domänen auch ohne vorab vorhandene Eingabebeispiele eine hohe Leistung erzielen kann. Dieser Beitrag ist für Forschende und Praktiker im Software Engineering von Bedeutung, da er eine automatisierte, skalierbare und präzise Lösung für das Grammar Mining bietet. Indem die Notwendigkeit einer manuellen Eingabegenerierung entfällt, reduziert der Ansatz nicht nur den Arbeitsaufwand, sondern verbessert auch die Robustheit und Vollständigkeit der extrahierten Grammatiken. Mit diesem Ansatz können Software-Entwickler:innen Spezifikationen aus bestehenden (Legacy-)Parsern rekonstruieren.

Unentdeckte Fehler in Softwaresystemen sind eine häufige Ursache für Schwachstellen und Sicherheitslücken. Grammar Fuzzing ist eine wirksame Methode zum Testen dieser Systeme, hat aber Einschränkungen, wie z.B. fehlendes Wissen über die Semantik des Programms und die Schwierigkeit, eine Grammatik für diese Systeme zu erhalten. Um diese Einschränkungen zu beheben, schlagen wir einen Ansatz vor, um automatisch Grammatiken zu ermitteln und diese mit semantischen Regeln und kontextuellen Einschränkungen zu erweitern, um Attributgrammatiken zu erstellen. Diese Attributgrammatiken können dann für Fuzzing verwendet werden. Unsere vorläufigen Ergebnisse zeigen, dass dieser automatische Extraktionsprozess durchführbar ist, da wir ihn erfolgreich auf einen Ausdrucksparser angewandt haben und in der Lage waren, eine Attributgrammatik zu extrahieren, die die Funktionalität des Parsers darstellt.