A Method For Localizing Program Faults Based On Similar Path Set Generation

Nowadays the relation of people and software is increasingly tight, and the significance of the software quality is well accepted. When software system fails or program has a failing run, the problem of how to make the debugging automated is worth exploring. Although there are a few experiences and methods to exploit, the automated program faults localization is the core and it needs further research.Under the support of the techniques, such as test path generation, test input data generation and dynamic program slicing, the difference between the failed test path and the passed similar test paths is analyzed in this dissertation, using the program dicing, and in the process of analysis the idea of "Nearest Neighbor" is combined. On the basis of the existing methods for calculating the similarity between two paths and for generating similar paths, in the dissertation a novel criterion for similarity metric between two paths is proposed, which is based on the program control flow, and then a algorithm for similar paths generation is designed and implemented, which is based on replacing the unconstrained edge in a decision-to-decision graph. Through some experiments, the complex of this algorithm is analyzed and the scheme for extending the algorithm is discussed. Subsequently, the program faults localization experiments are made, using the proposed similar paths generation algorithm, Gupta method, dynamic program slicing algorithm of Chen's and program dicing policy. The experimental result shows that the proposed method is effective in localizing the program faults related to program control flow errors.The works in this dissertation are mainly focused on the following aspects:1) Because of the limitation of the similar paths generation method of Wang's, the thesis presents a novel criterion for similarity metric between a failed path and its similar paths, which is based on the program control flow, and then it discusses the algorithm for generating the similar path set for a failed test path according to the criterion. The algorithm has taken the infeasible path into account. In order to produce the feasible paths as much as possible it adopts the "Least Predicate" heuristic policy when generating the candidate paths. It also has taken the side effect which is brought by ignoring the data flow information when calculating similarity between two paths into account. So it produces a similar path set not a single similar path in the candicate paths generation step and in the succedent steps the times analyzing the difference between two paths using program dicing is added to increase the accurate of faults localization. And the feasibility of the proposed algorithm is approved by some experiments on the Siemens benchmark suite.2) A few experiments have been done on some C programs that every one contains a single error, which uses the fault localization method this thesis proposed. The experimental results show that this method can reduce the cost for debugging in some sense. Especially, high accurate is obtained when localizing the faults which is relative to the program control flow.3) The thesis discusses a framework of the program faults localization prototype system, which is based on analyzing difference between the failed path and its similar paths. And then it introduces the usable tools and resources in the framework. At last it gives the answers how to develop a tool for generating the similar path set and a tool for reporting the possible program faults.