Input grammars in practice: Methods for symbolic mining, systematic evaluation, and grey-box testing

Abstract

Automatically inferring input grammars from programs provides significant benefits for test input generation, documentation, and reverse engineering. Existing approaches depend on sample inputs, which are often incomplete or unavailable. This dissertation introduces a novel sample-free approach that infers input grammars using symbolic execution. Tailored to recursive descent parsers, our approach produces highly accurate grammars. Research on grammar inference is typically evaluated by comparing the languages of the inferred grammar and a ground-truth grammar. We observe that the commonly used metric is biased, as it relies on a fixed sample size and favors short inputs. To address this limitation, we propose a new grammar accuracy metric that systematically explores the grammar space. Using our metric to re-evaluate input grammars inferred by five prior studies, we find that both precision and recall can decrease significantly. Recent advances in language-based test generation enable the creation of inputs that satisfy both grammatical structure and semantic constraints. However, these con- straints are restricted to the input domain. We integrate execution feedback into the input generation process of the Fandango tool, allowing testers to additionally express constraints over the execution domain. Through grey-box fuzzing experiments, we demonstrate that our unified approach achieves better results compared to input or execution constraints alone.

Die automatische Ableitung von Eingabegrammatiken aus Programmen bietet erhebliche Vorteile für die Generierung von Testeingaben, die Dokumentation und das Reverse Engineering. Bestehende Verfahren erfordern Beispieleingaben, die oft unvollständig oder nicht verfügbar sind. Diese Dissertation stellt einen neuen Ansatz vor, der symbolische Ausführung verwendet und keine Beispieleingaben benötigt. Unser Ansatz wurde für rekursive Abstiegsparser entwickelt und erzeugt hochgradig akkurate Grammatiken. Forschungsarbeiten im Bereich der Grammatikinferenz werden in der Regel evaluiert, indem die Sprachen der abgeleiteten Grammatik und einer idealen Grammatik verglichen werden. Wir stellen fest, dass die gängige Metrik verzerrt ist, da sie eine feste Stichprobengröße verwendet und kurze Eingaben bevorzugt. Um das zu verbessern, schlagen wir eine neue Metrik vor, die den Grammatikraum systematisch abtastet. Unter Verwendung dieser neuen Metrik evaluieren wir die in fünf bestehenden Studien abgeleiteten Eingabegrammatiken erneut und stellen fest, dass Präzision und Recall erheblich sinken können. Aktuelle Fortschritte in der sprachbasierten Testgenerierung ermöglichen die Erzeugung von Eingaben, die sowohl syntaktisch gültig sind als auch bestimmte semantische Einschränkungen erfüllen. Allerdings können diese Einschränkungen bislang nur über die Eingabedomäne ausgedrückt werden. Wir erweitern dieses Konzept mit Ausführungsinformationen, die wir in den Eingabegenerierungsprozess des Fandango- Werkzeugs integrieren, und ermöglichen es Testern so, zusätzlich Einschränkungen über die Ausführungsdomäne spezifizieren zu können. Anhand einer Reihe von Grey-Box-Fuzzing-Experimenten zeigen wir, dass unser einheitlicher Ansatz bessere Ergebnisse erzielt als die alleinige Berücksichtigung von Eingabe- oder Ausführungseinschränkungen.