UC Berkeley

Software bugs remain pervasive in modern software systems. As software becomes increasingly intertwined in all aspects of our lives, the consequences of these bugs become increasingly severe. Since the mid-2010s, several important security vulnerabilities have emerged from basic correctness bugs in software. Modern fuzz testing or fuzzing tools have greatly helped reduce the consequences of these bugs. These fuzzing tools can automatically find inputs revealing bugs in large-scale software. Arming developers with these tools allows them to find bugs more rapidly, before they have significant security impacts.

However, even the most sophisticated modern fuzzing algorithms remain restricted in the software quality problems they solve. Most of the bugs they find automatically are memory mismanagement issues typical of C/C++ programs---like out-of-bounds array reads---and most of these bugs lie in the shallower parsing stages of programs. Further, in spite of the impressive search algorithms underlying modern fuzzing tools, they have only really been applied to this test-input generation problem. This thesis presents several algorithms which adapt fuzzing to new testing domains, and even looks at applying these algorithms to the problem of program synthesis. Taken as a whole, these algorithms provide a view of the promise of modern fuzzing algorithms, and how to alter these algorithms to solve diverse software quality problems.

This thesis finds that three key components of modern fuzzing algorithms must be extended in order to solve broader software quality problems. First, this thesis presents a generalized notion of feedback-directed fuzzing, which can be used to automatically find different types of bugs, including algorithmic complexity bugs, extreme memory allocations, and to target recently-modified code. Second, this thesis explores how well-structured mutations are key to enabling mutational fuzzers to explore deeper program states, and find bugs beyond those in parsers. Finally, this thesis shows that viewing random input generators as a specification of a search space, and adjusting the sampling distribution of these generators automatically, enables effective blackbox validity fuzzing and program synthesis for large APIs.