2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), November 11-15, 2013, Palo Alto, USA

Desktop Layout

Technical Research Track
Medtrn. II
Leveraging Program Equivalence for Adaptive Program Repair: Models and First Results
Westley Weimer, Zachary P. Fry, and Stephanie Forrest
(University of Virginia, USA; University of New Mexico, USA)
Abstract: Software bugs remain a compelling problem. Automated program repair is a promising approach for reducing cost, and many methods have recently demonstrated positive results. However, success on any particular bug is variable, as is the cost to find a repair. This paper focuses on generate-and-validate repair methods that enumerate candidate repairs and use test cases to define correct behavior. We formalize repair cost in terms of test executions, which dominate most test-based repair algorithms. Insights from this model lead to a novel deterministic repair algorithm that computes a patch quotient space with respect to an approximate semantic equivalence relation. This allows syntactic and dataflow analysis techniques to dramatically reduce the repair search space. Generate-and-validate program repair is shown to be a dual of mutation testing, suggesting several possible cross-fertilizations. Evaluating on 105 real-world bugs in programs totaling 5MLOC and involving 10,000 tests, our new algorithm requires an order-of-magnitude fewer test evaluations than the previous state-of-the-art and is over three times more efficient monetarily.


Time stamp: 2019-06-24T21:19:40+02:00