Speeding up constraint-based program repair using a search-based technique

Jooyong Yi

doi:10.1016/j.infsof.2022.106865

2022-06-01

PRE

Jooyong Yi *

Elkhan Ismayilzada

DOI：10.1016/j.infsof.2022.106865

原文链接

原文求助

摘要

En 中文

Context: Constraint-based program repair has been developed as one of the main techniques for automated program repair. Given a buggy program and a test suite, constraint-based program repair first extracts a repair constraint T, and then synthesizes a patch satisfying T. Since a patch is synthesized in a correct-by-construction manner (rather than compiling and testing each repair candidate source code), the constraint-based approach, in theory, requires less runtime overhead than the G&V approach. Nevertheless, the performance of existing constraint-based approaches is still suboptimal.Objective: In this work, we propose a novel technique to expedite constraint-based program repair. We aim to boost runtime performance without sacrificing repairability and patch quality. Method: The existing constraint-based program repair searches for a patch specification in an unguided manner. We introduce a novel guided search algorithm based on MCMC sampling.Results: Our experimental results for the 50 buggy versions of 5 real-world subjects (i.e., Libtiff, PHP, GMP, Gzip, and Wireshark) show that our method named FAngelix is on average an order of magnitude faster than Angelix (a state-of-the-art constraint-based program repair tool), showing up to 23 times speed-up. This speed-up is achieved without sacrificing repairability and patch quality. Conclusion: This paper proposes a novel technique that expedites constraint-based program repair, using a search-based technique based on MCMC sampling. Our experimental results show the promise of our approach.

Keyword:

Automated program repair

Constraint-based program repair

Guided search

MCMC sampling