Software bugs are not going away. Millions of dollars and thousands of developer-hours are spent finding bugs, debugging the root cause, writing a patch, and reviewing fixes. Automated techniques like static analysis and dynamic fuzz testing have a proven track record for cutting costs and improving software quality. More recently, advances in automated program repair have matured and see nascent adoption in industry. Despite the value of these approaches, automated techniques do not come for free: they must approximate, both theoretically and in the interest of practicality. For example, static analyzers suffer false positives, and automatically produced patches may be insufficiently precise to fix a bug. Such limitations continue to impose substantial human effort amid the benefits of automation.

Software development activities revolve around changing code. Thus, performing and reasoning about program change has extensive bearing on the effectiveness of automated techniques. From this perspective, we develop new automated techniques for changing programs to improve analysis behavior, and, correspondingly, use automated reasoning and analysis to specialize program changes for automated program repair. We present the first evidence that automated program transformation, program analysis, and program repair are interrelated and cooperative. We first show that automated program transformation leads to higher quality static analysis (by reducing false positives) and dynamic fuzz testing (by reducing duplicate bug reports). We then show how high-quality static analyses can feed into and enable automated program repair, and how automated repair can circle back to further improve static analysis (e.g., by revealing more true positive bugs). The thesis is that automated syntactic and semantic search and application of program transformations enables efficient, scalable, and unassisted techniques for improving the effectiveness of existing program analyses and end-to-end repair of real-world programs.

We show that these techniques are effective compared to current approaches in the respective domains of static analysis, dynamic fuzz testing, and program repair. We demonstrate relevance and real-world applicability by evaluating on large, popular, and active projects across multiple languages. Our vision for this work is that new capabilities and techniques for automated program transformation foster effective ways to automate burdensome human effort and reasoning incurred by limitations in program analysis and repair.

202 pages

Thesis Committee:
Claire Le Goues (Chair)
Christian Kästner
Jan Hoffmann
Manuel Fähndrich (Facebook)

James D. Herbsleb, Interim Director, Institute for Software Research
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]