Spectral clustering based mutant reduction for mutation testing

Abstract Context: Mutation testing techniques, which attempt to construct a set of so-called mutants by seeding various faults into the software under test, have been widely used to generate test cases as well as to evaluate the effectiveness of a test suite. Its popularity in practice is significantly hindered by its high cost, majorly caused by the large number of mutants generated by the technique. Objective: It is always a challenging task to reduce the number of mutants while preserving the effectiveness of mutation testing. In this paper, we make use of an intelligent technique, namely spectral clustering, to improve the efficacy of mutant reduction. Method: First of all, we give a family of definitions and the method to calculate the distance between mutants according to the weak mutation testing criteria. Then we propose a mutant reduction method based on spectral clustering (SCMT), including the determination method of the number of clusters, spectral clustering of mutants, and selection of representative mutants. Results: The experimental studies based on 12 object programs show that the new approach can significantly reduce the number of mutants without jeopardizing the performance of mutation testing. As compared with other benchmark techniques, the new approach based on weak mutation testing criteria cannot only consistently deliver high effectiveness of mutation testing, but also help significantly reduce the time-cost of mutation testing. Conclusion: It is clearly demonstrated that the use of spectral clustering can help enhance the cost-effectiveness of mutation testing. The research reveals some potential research directions for not only mutation testing but also the broad area of software testing.