From Validation to Automated Repair & Beyond with Constraint Solving

Abstract

Tremendous amounts of software engineering efforts go into the validation of software. Developers rely on many forms of software validation, from unit tests to assertions and formal specifications, dynamic contract checking to static formal verification, to ensure the reliability of software packages. Traditionally, however, the benefits seem to stop there, at checking whether there are problems. But once problems have been detected, those spent validation efforts play no role in the challenging task of debugging those problems, a task which requires manual, time-consuming, and error-prone developer efforts. The key insight of this dissertation is that we can leverage the efforts that developers currently put into the validation of software, such as unit tests and formal verification, to get software engineering benefits that can go beyond validation, including automated software repair. Validation mechanisms can be elevated to this status using modern constraint solving, a technology that is already in use for the purpose of formal verification of software. I present three novel and practical instances of this idea, that I was able to identify by focusing on particular domains and scenarios. The first work, used in development, builds on unit testing as the most common form of validation, and exploits a constraint solving method to automatically fix a certain class of bugs in the source code (offline repair). The second builds on dynamic, specification-based validation as in assertions and contracts used during development and testing, and applies it to deployed software to make it robust to unforeseen run-time failures by falling back to constraint solving (online repair). Finally, I use specifications and constraint solving to improve an existing validation methodology in test-driven development, used to enable testing when part of the depended upon software is unavailable or hard to set up.

UCLA Ph.D. Thesis, June, 2013