With the rapid development of information techniques in various social applications, computer software plays a more and more important role in information systems, and becomes huge and complicated. In some key fields of applications, how to ensure the high quality and reliability of software turns into a serious task.Software testing is a important way to guarantee the quality and reliability of software, and test data generation is the sticking point of software testing. In traditional methods, producing test data by hand is tedious, laborious, expensive and error-prone for tester. Techniques for automated testing use a method of automatic test data generation and drive the program execution, which effectively ensure the efficiency and effectiveness, and test cost could be significantly reduced. Search based automatic generation of test data has been a burgeoning technique of software testing in recent years, which is to reformulate the problem of test data generation as a search problem. Search based test data generation has acquired many achievement and successfully applied in many social practice of software.Evolutionary testing (ET) is an important method of automatic test data generation. For structural testing, although ET works well in many situations, it is hampered by many problems, such as the presence of unstructured control flow under the test criteria of node-oriented. When the software system includes poorly structured loops with arbitrary jump statements (such as goto), unstructuredness is present for the control flow of programs. Arbitrary jump statements make the control flow complicated and unambiguous, especially inner a loop, the boundary of loop can not be determined, and analysis of data and control dependence become difficult. Consequently a method of calculation of fitness should be design for this kind of programs, and provide guidance for evolutionary search.Data dependence is an import kind of program dependence, tester analyse the relation between datas via the definition and use of variables in programs. Analysis of data flow is the foundation for structural testing and programs slicing, data flow based testing is path based testing in a normal sence.Similarly with control dependence, due to the use of flag in selection path result in lose of data dependence, which affect the efficiency of ET, and the special character of flag variable cause the loseness of guidance of evolutionary search. Consequently data dependence should be considered adequately in fitness of ET, and characters of programs should be changed to guide the search via testability transformation. Traditional approaches can not deal with many flag problems in loop, such as multiple branches assignment of flag, break statement and semi-critical branches, which result in that traditional method should be improved.In industrial practice, multi-objective optimization is comprehensive applied to solve many multi-objective and multi-constraint problems. Coverage and test cost are commonly use to show the performance of a test suite, so multi-factor should be considered for test data generation, and then multi-objective optimization is brought forward to structural testing.As a presentation of search based approaches, ET achieved a lot in automatic test data generation, but the technique is hampered by big search space and special program stucture, and the effectiveness based on single path is useless. Multi-objective optimization of test suite generation ensures the optimization of the test suite, and number of test case is limited with higher coverage. On the other hand complicated program structure can not bring unnecessary evolutionary search, just rely on the execution of programs, and then automatic testing becomes true.Diversity directly influences the quality of Pareto front in multi-objective evolutionary algorithms, while traditional appoaches usually based on distance. Average coverage density describes the information of coverage of a certain test suite T, the value is smaller represent a higher coverage of T, and average coverage density also describes the diversity of T. The ratio of coverage and the number of test suite shows the elitist intensity, an individual with higher elitist intensity would have much better progenitive ability. Not like the traditional evolutionary algorithms, new operators for across and mutant are specially designed. |