Static Grammar Inference for Ad Hoc Java Parsers

Abstract

Diese Arbeit befasst sich mit der Ableitung regulärer Ausdrücke (RegEx) aus Ad-hoc-Java-Parsern mithilfe statischer Analyse. Ad-hoc-Parser sind direkt im Quellcode implementiert, verwenden Java-String-Operationen und besitzen meist keine formale Grammatikdefinition. Der Ansatz dieser Arbeit besteht darin, die Weakest Liberal Precondition (WLP) aus der Logik der String-basierten Parser abzuleiten und daraus entsprechende reguläre Ausdrücke zu generieren. Diese RegExes können für das White-Box-Testing genutzt werden, um sowohl gültige als auch ungültige Eingabestrings zu erzeugen. Der methodische Ansatz umfasst:- Extraktion des Source Codes und Generierung des Abstract Syntax Tree (AST) mithilfe der Spoon-Bibliothek- Berechnung und Vereinfachung der WLP für logikbasierte String-Operationen- Ableitung und Transformation regulärer Ausdrücke für Java-String-Methoden sowie Validierung der ErgebnisseDie Evaluierung erfolgt durch automatisierte Generierung von Java-Parsern, systematische Tests mit RegEx-basierten Eingaben sowie die Anwendung auf praxisnahe Beispiele wie E-Mail-Adress-Parser und Unified-Format-Parser. Die Ergebnisse zeigen die Machbarkeit des Ansatzes bei der Verwendung nur einer String-Methode ohne vorheriger Transformation des Strings, verdeutlichen jedoch Herausforderungen bei der Kombination mehrerer String-Methoden.

This thesis focuses on extracting regular expressions (RegEx) from ad hoc Java parsers using static reasoning techniques. Ad hoc parsers often lack formal grammar definitions and are directly implemented in source code using Java string operations. The approach involves deriving the weakest liberal precondition (WLP) of string-based parsing logic to generate corresponding regular expressions. These regular expressions can serve as a model for testing, enabling white-box testing strategies by generating both valid and invalid input strings.\\The thesis introduces a systematic methodology:- Parsing the Java source code and extracting its Abstract Syntax Tree (AST) using the Spoon library- Generating RegEx representations for Java string methods, including transformations and validationsThe evaluation is performed through automated generation of Java parsers, systematic testing with RegEx-derived strings, and real-world use cases like email address and unified format parsers. The results demonstrate the feasibility of the approach for single methods without previous transformation of the string but reveal challenges in concatenated string method calls.