Mutant Selection by Using Fourier Expansion

Abstract

Mutation analysis is a widely used technique to evaluate the effectiveness of test cases in both hardware and software testing. The original model is mutated systematically under certain fault assumptions and test cases are checked against the mutants created to see whether the test cases can detect the faults or not. Mutation analysis is usually a computationally intensive task, particularly in finite state machine (FSM) testing due to a possibly huge amount of mutants. Random selection could be a practical reduction method under the assumption that each mutant is identical in terms of the probability of occurrence of its associating fault. The present study proposes a mutant selection method based on Fourier analysis of Boolean functions. Fourier helps to identify the most effective transitions on the output so that the mutants related to those transitions can be selected. Such mutants are considered more important since they are more likely to be killed. To evaluate the method, test cases are generated by the well-known W method, which has the capability of detecting every potential fault. The original and reduced sets of mutants are compared with respect to their importance values. Evaluations show that the mutants selected by the proposed technique are more effective, which reduces the cost of mutation analysis without sacrificing the performance of the mutation analysis.