Minimizing Mutant Sets by Equivalence and Subsumption

Authors: Samia Alblwi, Amani Ayad

Abstract:

Mutation testing is the art of generating syntactic variations of a base program and checking whether a candidate test suite can identify all the mutants that are not semantically equivalent to the base; this technique can be used to assess the quality of test suite. One of the main obstacles to the widespread use of mutation testing is cost, as even small programs (a few dozen lines of code) can give rise to a large number of mutants (up to hundreds); this has created an incentive to seek to reduce the number of mutants while preserving their collective effectiveness. Two criteria have been used to reduce the size of mutant sets: equivalence, which aims to partition the set of mutants into equivalence classes modulo semantic equivalence, and selecting one representative per class; and, subsumption, which aims to define a partial ordering among mutants that ranks mutants by effectiveness and seeks to select maximal elements in this ordering. In this paper, we analyze these two policies using analytical and empirical criteria.

Keywords: Mutation testing, mutant sets, mutant equivalence, mutant subsumption, mutant set minimization.

References:

[1] M. A. Guimaraes, L. Fernandes, M. Ribeiro, M. D’Amorim, and R. Gheyi, “Optimizing Mutation Testing by Discovering Dynamic Mutant Subsumption Relations,” 2020. doi: 10.1109/ICST46399.2020.00029.
[2] Y. Jia and M. Harman, “Constructing subtle faults using Higher Order mutation testing,” 2008. doi: 10.1109/SCAM.2008.36.
[3] B. Kurtz, P. Ammann, M. E. Delamaro, J. Offutt, and L. Deng, “Mutant subsumption graphs,” 2014. doi: 10.1109/ICSTW.2014.20.
[4] X. LI, Y. WANG, and H. LIN, “Coverage-Based Dynamic Mutant Subsumption Graph,” DEStech Transactions on Computer Science and Engineering, no. mmsta, 2018, doi: 10.12783/dtcse/mmsta2017/19661.
[5] A. Parsai and S. Demeyer, “Dynamic mutant subsumption analysis using little darwin,” 2017. doi: 10.1145/3121245.3121249.
[6] B. Souza, “Identifying Mutation Subsumption Relations,” 2020. doi: 10.1145/3324884.3418921.
[7] M. C. Tenório, R. V. V. Lopes, J. Fechine, T. Marinho, and E. Costa, “Subsumption in mutation testing: An automated model based on genetic algorithm,” in Advances in Intelligent Systems and Computing, 2019, vol. 800 Part F1. doi: 10.1007/978-3-030-14070-0_24.
[8] I. Marsit et al., “The ratio of equivalent mutants: A key to analyzing mutation equivalence,” Journal of Systems and Software, vol. 181, 2021, doi: 10.1016/j.jss.2021.111039.
[9] D. Shin, S. Yoo, and D. H. Bae, “A Theoretical and Empirical Study of Diversity-Aware Mutation Adequacy Criterion,” IEEE Transactions on Software Engineering, vol. 44, no. 10, 2018, doi: 10.1109/TSE.2017.2732347.
[10] A. Mili, “Differentiators and detectors,” Information Processing Letters, vol. 169, 2021, doi: 10.1016/j.ipl.2021.106111.
[11] D. Gries, The Science of Programming. 1981. doi: 10.1007/978-1-4612-59831.
[12] A. Blikle, “Zohar Manna. Mathematical theory of computation. McGraw-Hill Book Company, New York etc. 1974, x + 448 pp.,” Journal of Symbolic Logic, vol. 44, no. 1, 1979, doi: 10.2307/2273714.
[13] C. A. R. Hoare, “An axiomatic basis for computer programming,” Commun ACM, vol. 12, no. 10, 1969, doi: 10.1145/363235.363259.
[14] R. G. H. V. R. B. J. D. G. by Harlan D. Mills, Principles of Computer Programming: A Mathematical Approach. Allyn & Bacon, 1986.
[15] M. Ali and T. Fairouz, Software Testing Concepts and Operations, vol. XXXIII, no. 2. 2015.
[16] X. Yao, M. Harman, and Y. Jia, “A study of equivalent and stubborn mutation operators using human analysis of equivalence,” in Proceedings International Conference on Software Engineering, 2014, no. 1. doi: 10.1145/2568225.2568265.