Improved Genetic Algorithm to Reduce Mutation Testing Cost

Abstract

Mutation testing is a fault-based testing technique that helps generating effective test cases. Mutation testing is computationally expensive, because it requires executing hundreds and even thousands of mutants. In this situation, search-based approaches like genetic algorithm can help to automate test case generation to reduce the cost. In this paper, we present an improved genetic algorithm that can reduce computational cost of mutation testing. First, we present a novel state-based and control-oriented fitness function that efficiently uses object-oriented program features to evaluate a test case. We then empirically evaluate it using our implemented tool, eMuJava, and compare it with the standard fitness function. Results show that although our proposed fitness function provides detailed information about fitness of a test case but standard genetic algorithm is incapable of using that effectively to repair the test cases. Therefore, we propose a new two-way crossover and adaptable mutation methods that intelligently use the fitness information to generate fitter offspring. Finally, we compare the improved genetic algorithm with random testing, standard genetic algorithm, and EvoSuite. Experiment results prove that our proposed approach can find the optimal test cases in less number of attempts (reduces computational cost). Besides that it can detect software bugs from suspiciously equivalent mutants and these mutants eventually get killed (increases mutation score).

Keywords

• Control flow of program
• genetic algorithms
• mutation testing
• object oriented programming
• object’s state
• suspicious mutant