Research On Similar Path From Software Execution Traces

With the rapid development of information technology, Sequence database is growing explosived,technical data’s similarity query is also facing serious challenges.Excavated similar function from a large number of software execution trace execution path is provide a reliable guarantee for optimizing the use case set, reducing the high redundancy, finding the critical path and other applications.In the context of complex networks, we collected information on the implementation of software test cases, sort out the execution information, and then researched the sequence similarity algorithms, digged out a similar function execution path, the main contents are as follows.Firstly, we propose sequence of software execution path construction algorithm, This algorithm considered each function as a network nodes and the relationship between functions is the edge. Then, the execution path convered the sequence of function calls.Secondly, we present a similar path mining algorithm based on common subsequence.The algorithm creates dynamic matrix and path matrix on the basis of calling sequence.The common subsequence can be obtained by the Path matrix and then we measure the similarity of two sequences.This paper designes a common subsequence Bacing Rule which can find dissimilarity between sequences accurately.Then, we improve edit distance algorithm to make it more suitable for the software network.So we propose a similar path mining algorithm based on improved edit distance.The algorithm creates a dynamic matrix of two sequences, and then we present a new rule used to update the dynamic matrix to Backtracing matrix, so we are able to find all edit distance Backtracing Path and common subsequence under the same space complexity and then we measure the similarity of two sequences. In the last, the article puts forward the common subsequence backtracking rules. It is possible to find the optiamal match between the two sequences.Finally, we test the algorithm with java programming language, vertify by experiments, The proposed algorithms are strengthen the similarity measurement ofstrength to be able to draw a wide range of coverage as a new software execution sequence of test cases, thereby improves the efficiency of software testing.