Enhanced evolutionary automated program repair by finer-granularity ingredients and better search algorithms

Bug repair is time consuming and tedious, which hampers software maintenance. To alleviate the burden, automated program repair (APR) is proposed and has been fruitful in the last decade. Evolutionary repair is the seminal work of this field and proliferated a family of approaches. The performance of evolutionary repair approaches is affected by two main factors: (1) search space, which defines all possible patches, and (2) search algorithms, which navigate the space. Although recent approaches have achieved remarkable progress, the main challenges of the two factors still remain. On one hand, the different kinds of search space are very coarse for containing correct patches. On the other hand, the search process guided by genetic algorithms is inefficient in finding the correct patches in an appropriate time budget. In this paper, we propose MicroRepair, a new evolutionary repair approach to address the two challenges. Rather than finding statement-level patches like existing genetic repair approaches, MicroRepair enlarges the search space by breaking the statements into finer-granularity ingredients that consist of AST leaves. As the search space grows exponentially, the former search algorithms may become inefficient in navigating the larger space. We utilize the best multiobjective search algorithm selected from our empirical comparison of a set of search algorithms. At last, we find redundancies search in the existing genetic process, and we further design a history-aware search strategy to accelerate the process.We evaluated MicroRepair on 224 bugs of real-world from the benchmark Defects4J and compared it with several state-of-the-art repair approaches. The evaluation results show that MicroRepair correctly repaired 26 bugs with a precision of 62%, which significantly outperforms the state-of-the-art evolutionary APR approaches in terms of precision. Moreover, the history-aware search boosts the repair execution speed by 4% on average. MicroRepair is a new automated program repair approach that enlarges the search space by breaking statements into finer-granularity ingredients. It outperforms state-of-the-art evolutionary APR approaches in terms of precision, correctly repairing 26 bugs with a 62% precision rate. image