Research On Whole Program Path Generation

Path testing is a white-box testing method with a high degree of coverage,which is based on paths generation.Analyzing the whole program path can effectively improve software reliability.However,as the size and complexity of softwares is growing,the nested use of branches,loops,and function calls in programs makes the length and the number of paths soar.At present,the existing test methods are difficult to automatically generate the whole program path and test all paths in detail.Aiming at solving the above problems,this paper proposes an automatic model of whole program path generation.The main contributions of this paper are presented as follows:(1)Aiming at the path explosion caused by branches and loops,a combinatorial method of basis path set generation is proposed.Firstly,the method is based on the depth-first search strategy.Then the method combine static analysis methods(such as backtracking method and critical path method)and dynamic execution method to generate the in-function paths.And then the feasibility and linear independence are determined to generate the feasible basis path set.(2)For the path explosion caused by function calls,a heuristic path generation method is proposed.Firstly,function calls can be divided into four categories:no-impact call,local influence call,post-impact call and local-post-impact call.Secondly,random selection strategy and interval matching strategy are used for different classifications.Finally,the objective function is defined and heuristically guides the interprocedural path generation.The above methods have been implemented on the function test system(FTS).Three open source C language projects are chosen for the experiment of generating the whole program path.The experimental results show that the automatic model of whole program path generation proposed in this paper can successfully avoid the path explosion problem and generate whole program paths for the project with more than 10,000 lines of code.