An Improved Similar Path Generation Algorithm And Its Application For Fault Location

With the development of computer technology, 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, to make a automatic fault localization is a very meaningful research subject.Under the support of the researches, such as program static analyze, test path generation, test input data generation and dynamic program slicing, the differences 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. This research focuses on the path generation method of automatic fault location, designs and implements an improved similar path set generation algorithm on the foundation of the existing path algorithm, and analyses the complexity of the algorithm. Subsequently, the experiments of program faults localization 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. Finally, the facts in which the algorithm needs to expand are given after comparing the difference between the improved path algorithm and the original path algorithm.The works in this dissertation are mainly focused on the following aspects:1. Fault localization research based on similar paths generation. Paper[24] presented a similar paths generation algorithm based on fault path. Each time only one unconstrained edge in the fault path was replaced while algorithm is processing, leading to too little path and affecting the accuracy of fault localization. Aimed at the problem of Zhu' s algorithm, this paper presents an improved similar paths algorithm based on the fault path branch predications replacement. The algorithm searches the branch predicates of the fault path and replaces successively them to generate many similar paths. The algorithm checks the feasibility of a path as soon as this path was generated in order to detect feasibility of the path at the beginning of the algorithm, reducing later workload. Finally many experiments and analysis to these experiments results, proving the algorithm' effective in generating similar paths, were proposed, 2. This paper implemented Zhu's similar paths algorithm and the improved algorithm presented by this paper, and then compared the complexity of two algorithms.3. This paper performs experiments using automatic fault location method. This paper makes fault location experiments with a C-language source code containing known errors, analyses, compares the multi-set data. Based on these works a report of fault location was generated at last.