Research On Techniques For Software Test Case Automated Generation

Software testing is a very time-consuming job. According to statistics, software testing spends 40% of the time during the software development process. For certain critical software, the test time can reach up to 60%. As most of the software testing procedures are repetitive, it is feasible to apply automatic methods for software testing. In the past several years, extensive researches have been conducted on this field. However, it has to be pointed out that the current technologies for the automatic testing are not mature enough to meet the practical testing requirements. With all these being its background, the technologies of automated test data generation for software testing proposed in this dissertation are of great theoretic and practical significance.The state-of-art research of automated test data generation at home and abroad is summarized at first. Based on these, this dissertation conduct in-depth researches on the following five aspects: the research on the automated test data generation based on EDPN model; the research on the automated data generation based on expanded EDPN model; the research on the path analysis and software testing based on program execution and back-trace strategy; the research on the path analysis and software testing based on selective redundancy; and the research on the automated test data generation based on combinative match.1. Research on the automated test data generation based on the EDPN model: Based on the hierarchy and testing method of OOP, EDPN model is proposed at first. Then, based on the EDPN model, the class testing model has been established and the transformation from a UML graph to a EDPN graph has been discussed. The generation method and the related algorithm for marked UIO based on the EDPN model have been presented. The coverage rate of test data generated automatically by this algorithm is further analyzed. The result shows that all the state transformation has been covered at least once, thus the algorithm can ensure the sufficiency of the testing.2. Research on the automated data generation based on expanded EDPN: Based on the analysis of interactive relations among all the classes in OOP, a segmentation algorithm is presented.Based on iteration of the weighted EDPN, this algorithm divides the OOP system into sub-systems with different sizes and independent functions. Besides, this dissertation proposes an interactive testing method based on the combined EDPN model, and further extends the OATS method. An algorithm for the test data automated generation based on the extended OATS method is proposed to solve the problems of combination contradiction, test data explosion, and the extension of OATS method. Finally, based on the EMDPN model, an automated co-paths generation algorithm is proposed for hierarchical class testing. Algorithm analysis shows that the test data generated by this new algorithm meets the OSC criterion.3. Research on the path analysis and software testing based on the program execution and back-trace strategy: New concepts such as base node, control node, definition node and definition related control nodes set are proposed at first. Then, an algorithm to obtain the definition related control nodes set is provided. On the basis of combining both the method of linear approximation and DUC expression, an innovative automated test data generation algorithm based on the reversed binary tree is proposed. Based on the reversed binary tree constructed automatically by the algorithm, all of the feasible paths in the program from the source node to the base node are found, and the related test data are generated for each feasible path.4. Research on the path analysis and software testing based on the selective redundancy: Based on the selective redundancy, a new automated test data generation algorithm is proposed. This algorithm, adopting methods such as the linear approximation and minimization of branch function, automatically generates an initial test data suite. If valid test data cannot be obtained, then based on the selective redundancy, we further perform certain additional test data generation by examining the predicates and sub-paths not covered by the initial test data suite. Algorithm analysis and experiment results both show that the new algorithm can reduce the size of test data suite effectively and improve test performance.5. Research on the algorithm of automated test data generation based on the combinative match: Based on test generation strategies for pairwise testing, a new algorithm for the initial test data suite generation is provided. Then, based on combinative match, a new algorithm for test data generation is further proposed for pairwise testing. Experimental results show that the performance of this new algorithm is better than the existed ones, considering the size of test data suite and time consuming for the test data generation.