A Study On The Key Techniques For Coverage-based Automated Fault Localization

Software debugging is one of the most time-consuming and expensive activities in software development. With the rapid development of information technologies, software is more and more complex and the scale is becoming even bigger, which is likely to make software debugging more difficult and time-consuming. During software debugging, developers perform three main activities, fault localization, fault understanding and fault fixing, in which fault localization is the key part. Fault localization is the most difficult and time-consuming during debugging. Automated fault localization technique can effectively improve the performance of software debugging and significantly reduce the debugging cost. Coverage-based automated fault localization technique has been widely studied and applied due to its low computation complexity and effectiveness.Coverage-based fault localization technique first collects program spectra and test execution results through test case executions; then designs risk assessment formulas to assess the risk value of each program entity; finally, ranks each program entity in the descending order of risk values. Program spectrum information, risk assessment formula and test execution results are three key important factors affecting coverage-based fault localization technique. In this thesis, our research focuses on how these three key factors affect coverage-based fault localization.(1) Aiming at the limitations of program spectrum information on the improvement of coverage-based fault localization, we propose an approach with the combination of class suspiciousness information to improve the effectiveness of coverage-based fault localization technique. Program spectrum only contains information whether program entities are covered by test executions and cannot distinguish the statements having the same coverage information. Hence, we utilize the suspiciousness information of each class to distinguish these statements belonging to different classes. First, we utilize the behaviors of each object to abstract the class feature of encapsulation based on multiple failed and passed test executions and quantify the suspiciousness information of each class; then, we propose an algorithm to effectively combine statement suspiciousness information with the class suspiciousness information. Our work is the first to consider the object-oriented language features into coverage-based fault localization technique. Empirical results show that our approach can significantly improve the effectiveness of coverage-based fault localization technique.(2) Aiming at the lack of contextual information in the statements ranking, we propose an approach combining contextual information of method call chains to improve coverage-based fault localization technique. In this approach, we first construct weighted call graph based on method call profiles; then design an algorithm to search the faulty statement based on weighted call graph. This approach correlates the isolated suspicious statements in the statements ranking through method call chains. The relevant method call chains are provided as contextual information which is helpful for fault understanding. Moreover, this approach reduces the amount of suspicious statements need to examine and effectively improves the effectiveness of coverage-based fault localization technique.(3) Risk assessment formulas are key important for coverage-based fault localization technique. We first refine a combination work of slicing-hitting-set-computation and coverage-based fault localization technique, then extend the set theory based analysis framework. We can prove that in the single-fault scenario the refined combination method performs better than the original combination method and coverage-based fault localization technique. The refined combination method is likely to obtain different fault localization effectiveness using different risk assessment formulas. Then, we theoretically analyze how different risk assessment formulas perform in the refined combination method and can prove the distinct maximal performance groups. Through theoretical analysis, we prove that the refined combination method is equivalent to a simple formula conversion. We are the first to give the theoretical conclusions of combination work of dynamic slicing and coverage-based fault localization technique.(4) Aiming at the test oracle problem in code coverage-based failure proximity, we propose an approach to apply metamorphic testing on this application domain. During locating multiple faults, failure proximity is the basis for clustering failed test cases; then coverage-based fault localization technique can be applied on the clustered failed test cases. Failure proximity always assumes test oracles exist. However, in many application domains, test oracle problem commonly exists. Hence the applicability of existing failure proximity is limited. Through three replacements, we can successfully apply metamorphic testing on code coverage-based failure proximity without test oracle. First, we replace the failed test cases by violated metamorphic test groups; then, the failure signatures of test execution slices are replaced by the metamorphic execution slices; finally, the distance between any two failed test cases is replaced by the distance between any two violated metamorphic test groups. The experimental results show that the quality of code coverage-based failure proximity obtained through our approach is statistically comparable to code coverage-based failure proximity with test oracle. It indicates that our approach is able to effectively alleviate the test oracle problem in code coverage-based failure proximity.