Execution Path Clustering Method For Localizing Program Errors

Nowadays software has lots of uses in daily life and has its applications in almost all kinds of fields, the occurrence of software fault may lead to serious disaster. To rule out software errors, software debugging is a complex and time-consuming activity in software development. To reduce costs of software debugging, program fault localization, or program error localization, aims to locating the fault in the program quickly, correctly and automatically. There has been a lot of work on fault localization, among which the testing-based fault localization (TBFL) is a statistical method for pinpointing program faults by using the run-time coverage information.We classify TBFL techniques into distance measures-based methods and feature statistics-based ones. Wang method is one of the typical methods of the distance measures-based method which calculates the differences between the successful runs and failed runs to get the minimal differences as the bug sources. However, there still exists the need for improvements in diagnosing program errors, given the great variety and uncertainty of errors in programs.In this thesis, we propose a framework of fault localization based on test case clustering, which extends the original TBFL with clustering. To do so, we generalize the concept of difference by introducing the concept of "predicate". On that basis, we propose a new method to compute the difference by using the Predicate-block count spectra. We also propose "fitness" to evaluate the importance of the predicates, construct observation matrix to compute the fitness. Then we rank the predicate according to the fitness, use the ranking to elect predicates valuable for fault localization, thus accelerate the speed of fault localization. To reduce the redundant paths, we use the clustering method in data mining to cluster the paths, then use a class of paths to calculate the difference. We conduct detailed experiments on Siemens benchmark to compare our method with previously proposed methods. Experimental results show that our method can improve the efficiency and accuracy.