This project is developing new techniques for the creation of highly effective fuzz testers, also known as "fuzzers," for programming language compilers and interpreters. Fuzz testing is an automatic and low-cost technique for finding defects in software systems. A fuzzer randomly creates test inputs for a software system; a fuzzer is effective if it can continually create test cases that reveal defects throughout the system under test. It is difficult to create effective fuzzers for programming language compilers and interpreters because these systems have highly structured inputs, but it is important that such fuzzers exist. Programming language implementations are critical software infrastructure: defects in compilers and interpreters can potentially have great costs in terms of software correctness and reliability, human productivity, and computer security. This project seeks to reduce the time and human effort needed to create sophisticated fuzzers for programming language implementations. In so doing, this project is expected to advance the state of the art in random software testing, improve the quality of several programming language implementations selected for study, and produce new open-source software tools that programmers can use to develop new and more effective fuzz testers.
The techniques developed by this project will be embodied in a new generator of fuzz testers, called Xsmith. Xsmith will generate language fuzzers from specifications and thus reduce the time and effort required to create fuzzers. More importantly, Xsmith will inject sophisticated program-generation techniques into the language fuzzers it creates. This project will investigate three techniques in particular. This first is generation-time analysis, intended to allow Xsmith-derived fuzzers to create output that is both complex and meaningful. The second is feature subsetting, intended to increase the likelihood that Xsmith-derived fuzzers will output bug-triggering test programs. The third is iterative refinement, intended to further diversify the outputs from Xsmith-derived fuzzers. The project participants will use Xsmith to create fuzz testers for a varied set of programming languages. Where possible, the bug-finding power of Xsmith-derived fuzzers will be compared to that of existing fuzzers: quantitatively, in terms of the number of identifiably unique defects found within a fixed test-time budget, and qualitatively, in terms of the kinds of defects uncovered. This evaluation will allow the investigators to assess the impact of the techniques embodied in Xsmith, both individually and collectively, over a range of programming language implementations. Xsmith will be successful if it permits highly effective fuzz testers to be constructed with significantly less ad hoc code, and thus significantly less effort, than if they had been constructed from scratch.
This material is based upon work supported by the National Science Foundation under Grant Number 1527638. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.