Replication Package for Input Algebras

Summary

Grammar-based fuzzers are effective and efficient. They can produce an infinite number of syntactically valid test inputs, which can be used to explore the input space without bias. However, it is notoriously difficult to generate focused inputs to induce a specific behavior such as failure without affecting their effectiveness. This is the fuzzer taming problem. In our paper Input Algebras, we show how one can specialize the grammar towards inclusion or exclusion of specific patterns, and their arbitrary boolean combinations. The resulting specialized grammars can be used both for focused fuzzing and also as validators that can indicate the presence or absence of specific behavior-inducing input patterns. In our evaluation of real-world bugs, we show that specialized grammars are accurate both in producing and validating targeted inputs. We also provide a completely worked out Jupyter notebook that explains our algorithms in detail along with a sufficient number of examples. Further, we describe in detail how to replicate our evaluation.