Grammar-Based Fuzzing

This article presents new method for fuzzing programs accepting complex structured data based on BNF grammars. The majority of existing fuzzing methods do not take into account the structure of inputs for target program. Existing BNF structured data generating tools have various restrictions: BNF rules must be specified for target program, they are not scalable, generated data is not fully compatible with BNF rules, etc. We propose new algorithm for BNF structured data generation which uses ANTLR platform's descriptions of BNF rules for more than 120 languages and data formats. Every rule of grammar designed as universal pushdown automata, which allows as automatically generate BNF compatible data. Then we embed it as mutation plugin in fuzzing tool. According to experimental results in some cases we were able significantly increased code coverage.