UCLA

Grammar-based fuzzing is an effective method of testing software that requires highly structured inputs. However, these fuzzers require a user-provided input grammar that often does not exist for niche and emerging domains.

Grammar inference algorithms fill this gap by inferring a grammar using a set of training example inputs that satisfy a black-box oracle. However, existing grammar inference algorithms have shown to require on the order of hours to days to infer an input grammar from a handful of examples. We observe that some software systems such as AWS CloudFormation (CF) and Ansible take inputs that conform to a schema built on top of common formats like JSON or YAML.

We introduce GramRefine, a grammar inference algorithm that refines the given base grammars into more precise input grammars. By using the base grammar as a starting point, we significantly reduce the time needed to infer a grammar and obviate the need for language-specific heuristics, such as matching parenthesis or specific delimiter usages.

We conduct a comprehensive evaluation of GramRefine against the recent state-of-the-art black-box grammar inference algorithm TreeVada [4] on AWS CloudFormation templates, Ansible playbooks, and four sets of MLIR dialects, using a generic JSON grammar and generic MLIR grammar as the base grammars respectively. GramRefine is on average 654x faster and achieves 194x greater branch coverage than TreeVada. GramRefine's refined grammars creates qualitatively better examples than the base grammars---With more work to improve input validity (i.e oracle satisfaction), this could eventually translate to better coverage. GramRefine has the significant potential to improve input coverage and fault detection, while altering the burden to write a complex grammar by hand.