Effective automatic program repair based on state abstraction

Abstract

Automatic program repair (APR) aspires to automate the otherwise expensive and laborious process of patching bugs. Most existing APR techniques use tests to drive the repair process, where a buggy program with passing and failing tests is used as the input to generate a number of candidate fxes that can make all the tests pass as the output. The test driven APR techniques can be categorized into two groups: synthesis-based techniques and search-based techniques. While exciting progress has been made in search-based automated program repair and some of such techniques have been successfully applied in industry in the past few years, several limitations are preventing those techniques from being more effective and efficient in fixing more bugs: The quality of generated fixes may not be satisfactory from a programmer's point of view since test cases are just weak oracles for program correctness; Existing fault localization techniques deliver only subpar efficiency that cripples the performance of APR techniques because the localization process is not tightly integrated with the repair process; The generic information about fix patterns learned from human-written patches in the past may not be enough to guarantee an effective and efficient fixing process. We have developed novel techniques in this thesis that address these limitations and advance the state-of-the-art in search-based automated repair of Java programs. Particularly, we devised the JAID technique that abstracts program states based on a rich set of predicates derived from regular Java code and mitigates the overftting problem by grounding the repair generation and validation processes on the abstraction; We pioneered the RESTORE technique that reuses the outcome of failed patch validation to yield accurate information about fault locations without incurring onerous computational costs; We introduced the PRIDE technique that enables program repair to apply valuable knowledge repeatedly learned from both completed and ongoing fixing processes to better navigate the space of candidate fixes. Supporting tools have also been implemented to enable programmers to use these techniques in their everyday development to generate high quality fixes to errors in Java programs in an automated fashion. To evaluate the effectiveness and efficiency of these techniques, we applied the tools to automatically repair bugs from benchmarks like DEFECTS4J, INTROCLASS-JAVA, QUIXBUGS, and BEARS. Experimental results show that, compared with other Java APR tools of the same time, ours can produce correct fixes to more bugs with a comparable amount of time.