Fitness Function Design For Branch Exertion In Evolutionary Testing

Evolutionary Testing (ET) is an emerging and promising technology for automatic test data generation. The main idea of ET is to reformulate the problem of test data generation as an evolutionary search, and then the test data can be generated with the help of evolutionary algorithm.In ET, the test data generation process is guided by the fitness function, therefore, the guidance capability of the fitness function becomes very critical.However, for the non-linear features of the real programs, it is especially difficult to design a fitness function with guidance. In recent years, much research work has been done on this topic.However, previous fitness functions only could be applied to some specific program constructs, or the search process should be changed at the same time.Especially, for the recurrent flag variable case in industry programs, different fitness functions should be applied to different use cases of flag variables, while for the nested if-else construct, switch-case construct and programs with procedures construct, few work has been addressed.This dissertation addresses the fitness function design for the program constructs mentioned above.We found that the loss of the guidance in previous work was rooted in the ignorance of the inherent data and control-dependency in the program under test. New fitness functions are proposed for the following program constructs:1.For the flag problem, a unified fitness function is proposed. In this fitness function, the data dependency between the flag variables and others is considered, and a'flag cost function' is introduced to replace the branch distance in traditional fitness function.2.For the nested if-else construct, a new fitness function calculation rule is proposed. In this fitness function, the control-dependency among nested branches is taken into consideration and 'branch optimism level' is introduced to evaluate the test data for the nested branches.3.For the switch-case construct, a flat control dependency graph is proposed to represent the parallel semantic construct of all case branches.Consequently the distance between the test data and the target branch on the control flow could be evaluated more precisely.4.For the programs with the function call construct, a fitness function based on the function call dependency is proposed by incorporating the control dependency along the function call flow.Both experiment research and real industrial application show that the fitness function proposed in this dissertation could effectively guide the evolutionary search at much lower cost, making ET more practical in real industrial cases.