Theory Of Evolutionary Generation Of Test Data For Complex Software And Applications

One of the approaches to improve the quality of software is to do a large number of tests before delivery and usage in order to detect defects or errors in the software. Software testing is an expensive, tedious and labor-intensive task, and accounts for up to 50% of the total cost of software development. If the test process can be automated, it will undoubtedly shorten the software development period and improve the quality of software, so as to enhance the market competitiveness. One of the most difficult aspects of automated software testing is the generation of effective test data satisfying selected test adequacy criteria. Existed research data show that traditional random method and form-based analysis are always inefficient to the problems of test data generation for complex software. In recent years, although many scholars have used intelligent optimization methods to solve this problem, such as simulated annealing algorithm, genetic algorithm, and tabu search algorithm, etc., but the research results are often difficult to be applied in the test of actual complex software because of their one-sidedness. Considering the complexity of actual software under test, this issue investigates theories and applications of evolutionary generation of test data for complex software based on different test adequacy criteria. The main results include:For path coverage problem, a theory and method of automatically detecting infeasible paths based on branch correlations of different conditional statements are proposed. This method can help to detect all or most of infeasible paths in a program, thus provides benefit to improving the efficiency of path coverage. Then, a general model for problem of multi-path coverage is established, which takes each optimization problem corresponding to test data generation for one target path as a sub-problem, and a number of sub-problems form a large optimization problem. Based on this model, a multi-population evolutionary algorithm is proposed to solve this problem. The key step of our algorithm lies in individual sharing of different populations. By this way, the efficiency of finding optimal solutions of each sub-problem improves. Besides, we present a method of evolutionary generation of test data for many paths coverage based on grouping. Target paths are divided into several groups based on their similarities, and each group forms a sub-optimization problem. Thus, a complicated optimization problem is transformed into several simpler sub-optimization problems, which are continuously simplified along with the process of generating test data, so as to improve the efficiency of generating test data.For statement coverage problem, a novel testability transformation theory based on equivalence of target statements is given, and a method of test data generation based on testability transformation is proposed. First, we propose a novel method of testability transformation to tackle the flag problem, whose basic idea is: search for a new target statement (or a set of target statements) equivalent to the original one, and then transform the problem of generating test data that cover the original target statement into the one that cover the new target statement (or a set of target statements). The key step in our method is not the transformation of source code, but that of target statements, so it is very different with traditional methods. Second, we proposed a novel approach to achieve test data reduction by reducing the set of target statements based on dominant relations. First, the dominant digraph is constructed according to the dominant relations of target statements; then, the minimum path coverage of the dominant digraph can be obtained using a proposed theory; finally, test data set covering the reduced set of target statements is generated by genetic algorithm. The proposed method can significantly reduce the number of target statements, and thus provides an effective way to test data reduction.In order to improve the efficiency of mutation testing, we propose a novel mutation testing method based on the comparison of paths. First, we give the criteria of this mutation testing, i.e. if a test datum can distinguish a mutation and the original program by causing each to traversing different paths in the control flow graph, then the test datum is said to"kill"the mutation. Then, we propose a method of test data generation for mutation testing based on path coverage. In the mathematic model, the objective is killing the mutation and the restriction is satisfying the given path coverage.Results of this study not only enriched the theoretical knowledge of software testing, but also improve the efficiency of test data generation from different aspects, thus greatly saved the cost and time of software testing and improved software quality, therefore, have important theoretical and practical values.