Detection Of Infeasible Paths Based On Hierarchical Clustering

With the development of science and technology and the progress of society, software has been extensively applied in various fields of society. The quality and reliability of software are very significant in many fields of applications. Software testing is a significant mean to ensure software quality and reliability. Path testing is one of the commonly used test methods in software testing. Path testing attempts to cover a path in the program by a suitable test case. If a path is infeasible, then test cases cannot be found to cover the target path, resulting in a waste of test resources. Large-scale programs have numerous features, and complex structures, which usually contain a lot of infeasible paths. Therefore, there is great significance to identify the infeasible paths in a program before path testing.Many experts and scholars at home and abroad presented a lot of methods for infeasible paths detection. However, there are still many deficiencies. Based on the analysis and study of existing detection methods, this paper proposes a method for detecting infeasible paths based on sub-path expansion and a method for similar execution paths generation based on hierarchical clustering and a method for detecting infeasible paths based on hierarchical clustering, finally implements an infeasible path detection tool for Java programs.Firstly, an approach for detecting infeasible paths based on sub-path expansion is proposed. The proposed method first generates sub-path set, and the feasibility issues will be converted into inequalities. Second, the constraint solver is utilized to solve the inequalities, and then we can distinguish the sub-paths into three parts: one part is infeasible sub-paths, the second part is feasible sub-paths, and the third part is undetermined. The paths that are expanded from the latter two parts will be tested again to determine their feasibility. Eventually, the feasibility of all the paths is detected. Most of the detecting work is on sub-path set, so our method makes an effective solution to the path explosion problem. Experimental results demonstrate that the proposed method can detect infeasible paths accurately and effectively.Secondly, a method for similar execution paths generation based on hierarchical clustering is proposed. Based on the idea of equivalence class partitioning, this method calculates the similarity between paths by the branch distance, and then clusters the execution paths hierarchically. Finally, this method generates similar execution paths based on the cluster model. Experimental results show that this method can generate similar execution path effectively, and improve the efficiency of path testing.Thirdly, a method for detecting infeasible paths based on hierarchical clustering is proposed. In the approach of detecting infeasible paths based on sub-path expansion, we introduced the method of similar execution paths generation based on hierarchical clustering into the sub-path expansion step. Based on the similarity of the path conditions, this method generates similar execution paths from sub-paths. Finally, infeasible paths detection is finished.Finally, we implement an infeasible path detection tool for Java programs. In the method for infeasible paths detection based on sub-path expansion, the most crucial step is sub-path expansion. This tool introduces the method for similar execution paths generation based on hierarchical clustering into the step of sub-path expansion. In the sub-path expansion step, this tool uses heuristic search mechanism combined with static analysis to make the sub-path expansion process more efficient, and saves lots of testing resources.