Automated test data generation for branch coverage using novel genetic algorithms

Abstract

Automating the process of software testing reduces the development cost effectively. Search Based Software Testing (SBST) approaches outperforms the other techniques. In general SBST methods starts with random test data set, and they are evaluated based on fitness function to find how close they were to reach the target branch. The test criterions such as branch coverage or statement coverage are used as fitness functions. Based on the fitness measure the test data will be modified according to the metaheuristic algorithms so that they can achieve the coverage. SBST makes use of Control Flow Graph (CFG) and metaheuristic search algorithms to accomplish the process. Hence, an efficient test data set could be generated with minimum cost. Among many metaheuristic algorithms, Genetic Algorithm (GA) is widely used for test data generation. This research work focuses on test data generation for branch coverage, the major problem here in using metaheuristic technique is that the CFG paths have to be traversed from the starting node to end node for each automated test data. This kind of traversal could be improved by branch ordering together with elitism. But still the population size and the number of iterations are maintained as same to keep all the branches alive. Two substantial modifications towards the improvement of Genetic Algorithm have been proposed in this research work, for the application of search based software test data generation. The first extension called, Incremental GA (IGA), where the GA is executed to generate the test data for every branch node, then these solutions are combined together to form the initial population for the classical GA phase in the second step. These partial solutions make the second phase to be completed in very shorter generations comparatively than the single step classical GA. And in the second extension, an extra buffer space is provided for IGA for maintaining the list of covered target branches and to store the test data. newline