UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Test-Equivalence Analysis for Automatic Patch Generation

Mechtaev, S; Gao, X; Tan, SH; Roychoudhury, A; (2018) Test-Equivalence Analysis for Automatic Patch Generation. ACM Transactions on Software Engineering and Methodology (TOSEM) , 27 (4) , Article 15. 10.1145/3241980. Green open access

[thumbnail of tosem18.pdf]
tosem18.pdf - Accepted version

Download (1MB) | Preview


Automated program repair is a problem of finding a transformation (called a patch) of a given incorrect program that eliminates the observable failures. It has important applications such as providing debugging aids, automatically grading student assignments, and patching security vulnerabilities. A common challenge faced by existing repair techniques is scalability to large patch spaces, since there are many candidate patches that these techniques explicitly or implicitly consider. The correctness criteria for program repair is often given as a suite of tests. Current repair techniques do not scale due to the large number of test executions performed by the underlying search algorithms. In this work, we address this problem by introducing a methodology of patch generation based on a test-equivalence relation (if two programs are “test-equivalent” for a given test, they produce indistinguishable results on this test). We propose two test-equivalence relations based on runtime values and dependencies, respectively, and present an algorithm that performs on-the-fly partitioning of patches into test-equivalence classes. Our experiments on real-world programs reveal that the proposed methodology drastically reduces the number of test executions and therefore provides an order of magnitude efficiency improvement over existing repair techniques, without sacrificing patch quality.

Type: Article
Title: Test-Equivalence Analysis for Automatic Patch Generation
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/3241980
Publisher version: https://doi.org/10.1145/3241980
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10088928
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item