Infeasible Path Identification And Its Application In Structural Test

Structural test is beneficial to evaluate whether the test is sufficient. However, it iscommon that testing is not sufficient, more test cases should be selected to improve thesufficiency of the test. Usually, each new test case selected need to be executed on some specialpaths. The first question encountered is how to decide if the path is feasible, which means thatthe path is feasible by some input. In the area of structural test, identification of infeasible pathbecomes more and more important. The earlier the infeasible path in the program wasidentified, the fewer the time spent. There exist some methods of infeasible path identification,which have their own disadvantages. This dissertation surveys the principle and the manner ofstructural test and shows the significance of infeasible path to the structural test. Then analysisthe reason of infeasible path generation, and surveys the recent development of identificationof infeasible path. A method of infeasible path identification is proposed based on control flowgraph (CFG), and the information of infeasible path was applied to optimized structural test,which can improve the accuracy of path test and data-flow test.The major contributions of this dissertation are summarized as follows.1. A method of infeasible path identification is proposed. This method is based onControl Flow Graph (CFG). We compute the define/used reach information of each basic blockby data-flow analysis, those information can be used to detect the branch correlation. Finally, arule of identifying infeasible path from path set is established according to the result of branchcorrelation analysis. We improve the rate of branches covered by selecting proper conditionpredication and decrease complexity of branch correlation by data-flow analysis.2. A generation method of relative basis set of path is proposed based on effect of branchcorrelation. In the method, we have considered the branch correlation in the process of pathgeneration, which improve the rate of paths covered in the relative basis set of path, whichfacilitate paths test. Relative basis set of path is a part of path set and has such attributes asfollow: (1) each path is one independent path and includes one edge at least which does notexist in any other paths. (2) All of edges in the program will be included. The relative basis setof path has the higher rate of edges covered in the CFG than the path set which has beenexcluded infeasible paths directly.3. A method of data-flow test based on infeasible path is proposed. We extend themethod proposed in [5], and add the effect of infeasible path into the method, so we can get thehigher veracity of fault detection in the software. And we propose a new set of manner of setcomputing to adapt to the infeasible path existing, so we can judge if the fault in the software isdue to infeasible path or not, and locate the fault effectively, which can provide more usefulinformation to programmer and tester to improve the performance of program.The proposed methods have been implemented on Open Resource Compiler (ORC),experimental results reveal their efficiency.