Research On Detection Of Infeasible Basis Paths Based On Association Analysis

With the development of society, software has been applied in various fields ofsociety. Software testing is an important means of improving software reliability.Many software testing problems can come down to the problem of path-wisegeneration of test data. However, the existence of infeasible paths is a problem in pathtesting and there is no input datum for these infeasible paths to be executed. Theexistence of infeasible paths causes a waste of test resources and produces greatdifficulties for software testing. The feasibility of paths has an immediate effect on theefficiency of software testing. Detecting infeasible paths effectively can improve testefficiency and can reduce test cost. Many researchers have paid attention todeveloping technology to detecting infeasible paths. But these approaches have somedefects in practice. By analyzing the existing researches, to address the limitations ofexisting techniques, the paper puts forward an approach to detecting infeasible pathsusing association analysis, and an improved algorithm of generating basis path set.Firstly, the paper proposes a new approach for automatic detection of infeasiblepaths based on association analysis and data flow analysis. First, it builds data-setswhich reflect the static dependencies and the dynamic execution information ofconditional statements by combining static analysis with dynamic analysis; then, itdetermines branch correlations based on association analysis and data flow analysis;finally, it detects infeasible paths according to branch correlations. The paper appliesthe proposed approach in some benchmark programs and industry programs. Theexperimental results show that our approach can detect infeasible paths accurately andimprove the efficiency of software testing.Secondly, based on detecting infeasible paths, an effective and automaticalgorithm of generating basis path set is proposed. Firstly, a basis path set of theprogram is generated by visiting all nodes of the program’s control flow graph;secondly, infeasible basis paths are detected by association analysis and are deletedfrom the basis path set at the same time; then, some feasible independent paths whichcontain the edges which are not covered by the path set are added into the path set;finally, some infeasible independent paths which contain the edges which are notcovered by the path set or are needed by linear operations. Experiment has beencarried to verify the effectiveness of the algorithm.Finally, based on the proposed methods of infeasible paths detection and basis path generation, this paper implements an automatic infeasible basis paths detectiontool for Java programs. This tool includes infeasible paths detection model and basispath generation model.