Font Size: a A A

Research On The Key Techniques Of Automated Program Repair

Posted on:2014-11-08Degree:DoctorType:Dissertation
Country:ChinaCandidate:Y H QiFull Text:PDF
GTID:1108330479979629Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Automated program repair plays an important role in automating the activity of software maintenance and improving both software quality and trustworthy. Although the research on automated program repair has made some progress, current techniques still suffer from the limitation of repair effectiveness and efficiency. Through integrating the activities of fault localization, patch generation and patch validation, this project plans to systematically investigate the repair process. This project will 1) study the fault localization technique from the viewpoint of automated program repair, 2) investigate the patch generation mechanism based on random search, and 3) present the techniques to improve the efficiency of patch validation. This project will present a serial of techniques aiming to improve both repair effectiveness and efficiency. We also attempt to justify the advantage of each technique via the experiments on the real-life, large-scale faults in open source, and demonstrate its effectiveness and efficiency using rigorous statistical approaches. The key contributions of this dissertation are listed as follows.1) Studying fault localization techniques from the viewpoint of automated repair,and building the measurement on fault localization from this perspectiveAutomated fault localization has been used to provide the localization information of suspicious statements, and the accuracy of localization information will heavily impact the repair effectiveness. However, current localization techniques are often developed from the viewpoint of developers, and our experiment suggests that these localization techniques which can benefit developers better do not have good performance from the viewpoint of automated repair. Furthermore, Although fault localization techniques have developed over 30 years to benefit developers, the fact that most developers are still unwilling to debug faulty programs through existing fault localizers results in the natural doubt about the rationality of current evaluation measurement. Actually, to our knowledge most developers are more likely to proceed using traditional debugging such as breakpoints. The recent advance on automated program repair can be the ”killer” application for fault localization techniques. In the context, we are the first to investigate the effectiveness evaluation for localization techniques from the viewpoint of fully automated debugging, and present the evaluation measurement for evaluating and comparing the effectiveness of different localization techniques. Based on this evaluation measurement, we conduct a experiment to study the effectiveness of several popular localization techniques, and present some possible research directions on fault localization from the viewpoint of automated program repair.2) Presenting a new repair algorithm based on random searchWe use the simplest randomized algorithm(i.e., random search) to implement an algorithm on automated program repair. As one of the state-of-the-art techniques, Gen Prog has two main contributions presented: effective mutation operations and using genetic programming to guide the patch generation process. Although the promising repair ability has been shown by Gen Prog, whether the repair ability is got based on the guidance of genetic programming or just because the mutation operations are powerful enough to tolerate the inaction of genetic programming has never been studied. Given the above issues,we construct a new repair tool, which tries to repair faulty programs with the same mutation operations as Gen Prog but uses random search, rather than genetic programming, to guide the patch generation process. Experiment suggests that genetic programming does not better guide the patch process than random search. We discuss the possible reason,and suggest that every proposed technique using optimisation algorithm should check its effectiveness by comparing it with random search.3) Presenting the technique of weak recompilationFor traditional recompilation technique, there most often exists serious recompilation redundancy in the step of patch validation. To suppress the above time cost and make the repair process more efficient, a recompilation technique called weak recompilation is described in this dissertation. In weak recompilation, a program is assumed to be constructed from a set of components, and for each candidate patch only the changed components are recompiled to a shared library; and then the original program is dynamically updated by the function indirection mechanism. Experimental results show that weak recompilation can effectively reduce the recompilation cost in patch validation step, and thus improve the repair efficiency.4) Presenting the technique of fault-recorded testing prioritizationWe present a technique of Fault-Recorded Testing Prioritization(FRTP) with the goal of reducing the number of test case executions in the patch validation step. Unlike most existing prioritization techniques frequently requiring additional cost for gathering previous test executions information, FRTP does not require any information about test cases,but iteratively extracts that information just from the repair process, and prioritizes dynamically test cases according to extracted information, which incurs trivial performance lose. Experimental results suggest that FRTP can effectively reduce the number of test case executions in the repair process, and thus improve the repair efficiency.
Keywords/Search Tags:Automated Program Repair, Fault Localization, Patch Generalization, Patch Validation
PDF Full Text Request
Related items