This thesis develops new methods for addressing the problem of software security bugs, shows that these methods scale to large commodity software, and lays the foundation for a service that makes automatic, effective security testing available at a modest cost per bug found. We make the following contributions:
We introduce a new search algorithm for systematic test generation that is optimized for large applications with large input files and exhibiting long execution traces where the search is bound to be incomplete (Chapter 2).
We introduce optimizations for checking multiple properties of a program simultaneously using dynamic test generation, and we formalize the notion of active property checking (Chapter 3).
We describe the implementation of tools that implement dynamic test generation of large binary programs for Windows and for Linux: SAGE and SmartFuzz. We explain the engineering choices behind their symbolic execution algorithm and the key optimization techniques enabling both tools to scale to program traces with hundreds of millions of instructions (Chapters 2 and 4).
We develop methods for coordinating large scale experiments with fuzz testing techniques, including methods to address the defect triage problem (Chapter 4).
Dynamic Test Generation for Large Binary Programs
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).