2021/03/07 by Vasudev Vikram, Vikram, Vasudev, Rohan Padhye +3 · 1 citation
Computer Science · #FOS: Computer and information sciences #Programming Languages (cs.PL) #Software Engineering (cs.SE) #Software Engineering Research #Software Reliability and Analysis Research #Software Testing and Debugging Techniques #cs.PL #cs.SE
paper · pdf · doi:10.48550/arxiv.2103.04388
Accepted at the 43rd International Conference on Software Engineering (ICSE 2021)
arxiv created 2021/03/07 · openalex publication_date 2021/03/07 · arxiv updated 2021/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.