GrammarForge: Learning Program Input Grammars for Fuzz Testing

Providing good methods for testing properties of software is critical. Such methods often depend on a formal description of the program input language, in particular, when they are based on grammar-based fuzzing. Unfortunately, it cannot be ensured that such a formal description is always available. To tackle this problem, we propose a new method that automates grammar learning for the input language of the software under test, combining classical language membership queries with light weight source code analysis tools such as control flow graphs and program instrumentation. We present a prototype implementation (GrammarForge) of our method, which works following a process of automated conservative substitution of place holders by terminals, starting from an initial grammar structure extracted from the source code. It targets arbitrary parses implemented using recursive descent techniques. We perform extensive experimentation, which shows that GrammarForge outperforms alternative tools with respect to accuracy of the learned grammar. Moreover, and different to all other state of the art methods, our learning process does not need seed inputs from the target language.