Search-based Efficient Automated Program Repair Using Mutation And Fault Localization

Program faults are unavoidable phenomena in software development.When a program is detected a fault,the debugging process can be divided into two steps:first,determine the location of the fault and the nature of it,then repair the fault.The first step,called "fault localization",is now considered to be one of the most expensive activities in the debugging phase of the software development process.At present,there have been many mature fault localization techniques,but the problem is that although detecting the existence of faults,the repair work still need the developers to complete,and fault fixes is considered more difficulty and complexity than that of the fault localization,so the automated program repair is a very important task.The applications of mutation and fault localization techniques are effective in automated program repair,but suffer the inevitable high execution cost as the number of mutants increases exponentially for large industry programs.Whether it is necessary to generate all mutants for the entire program and where to start mutation from the program are the chief obstacles to the applications of mutation based techniques.The combination with fault localization can reduce the cost by first mutating the statement with high suspicious value.However,the accuracy of fault localization techniques has been not good enough for real application,and some faults may occur on the statement related to the statement with high suspicious value rather than itself.Therefore,the greedy strategy used currently may be efficient but may not effective.Finding a mutant as a correct patch should be regarded as a continuous process of searching the global solutions.Therefore,the effective application of the global optimal method can effectively improve the efficiency of the search for repair patches.In this paper,we proposed a search based automated program repair using mutation and fault localization,which not only takes advantage of fault localization but also overcomes the disadvantage of the greedy strategy used in the mutation generation,and the approach also has certain ability to repair multiple fault programs.In order to deal with the shortcomings of search algorithm,this paper proposes two optimization methods to narrow the search space and accelerate the convergence speed,namely,the non-random initial population method and the hybrid-crossover strategy.The initial population of the search algorithm is constructed by the mutations generated from the statements with the high suspicious value from fault localization,which are a set of rough solutions.A hybrid crossover operator is then designed where fixed position crossover operator is used to converge the global optimal and random position crossover operator is used to explore the entire search space faster,respectively.In order to further verify the effectiveness and efficiency of the proposed automated program repair approach and the impact of the two optimization methods on search efficiency,we designed some experiments to study and discuss related problems.The experimental results on the Siemens suite indicate that the proposed approach can improve the efficiency with the same effectiveness compared to the exhaustive approach,and show that the non-random initial population method and hybrid-crossover strategy can improve the efficiency of the search process.