A feedback-directed method of evolutionary test data generation for parallel programs

Context: Genetic algorithms can be utilized for automatic test data generation. Test data are encoded as individuals which are evolved for a number of generations using genetic operators. Test data of a parallel program include not only the program input, but also the communication information between each pair of processes. Traditional genetic algorithms, however, do not make full use of information provided by a population's evolution, resulting in a low efficiency in generating test data. Objective: This paper emphasizes the problem of test data generation for parallel programs, and presents a feedback-directed genetic algorithm for generating test data of path coverage. Method: Information related to a schedule sequence is exploited to improve genetic operators. Specifically, a scheduling sequence is evaluated according to how well an individual covers the target path. The probability of the crossover and mutation points being located in the region is determined based on the evaluation result, which prevents a good schedule sequence from being destroyed. If crossover and mutation are performed in the scheduling sequence, the location of crossover and mutation points is further determined according to the relationship between nodes to be covered and the scheduling sequence. In this way, the population can be evolved in a narrowed search space. Results: The proposed algorithm is applied to test 11 parallel programs. The experimental results show that, compared with the genetic algorithm without utilizing information during the population evolution, the proposed algorithm significantly reduces the number of generations and the time consumption. Conclusion: The proposed algorithm can greatly improve the efficiency in evolutionary test data generation.