  This paper presents a coverage-guided grammar-based fuzzing technique for
automatically generating a corpus of concise test inputs for programs such as
compilers. We walk-through a case study of a compiler designed for education
and the corresponding problem of generating meaningful test cases to provide to
students. The prior state-of-the-art solution is a combination of fuzzing and
test-case reduction techniques such as variants of delta-debugging. Our key
insight is that instead of attempting to minimize convoluted fuzzer-generated
test inputs, we can instead grow concise test inputs by construction using a
form of iterative deepening. We call this approach Bonsai Fuzzing. Experimental
results show that Bonsai Fuzzing can generate test corpora having inputs that
are 16--45% smaller in size on average as compared to a fuzz-then-reduce
approach, while achieving approximately the same code coverage and
fault-detection capability.
