Efficiently Finding Useless Mutants
Keywords:
Mutants, Weak Mutation, Theorem ProvingAbstract
Mutation analysis is a popular but costly approach to assess the quality of test suites. Equivalent and redundant mutants contribute to increase costs and are harmful to the design of test suites. We propose a lightweight technique to identify equivalent and redundant mutants based on theorem proving with Z3 in the context of weak mutation testing. The experiments reveal that our technique detects all equivalent mutants detected by TCE and we have an average reduction of 72.52% of mutants, when considering entire programs. We also apply our technique on HOMs. When considering both FOMs and HOMs, 91% of the mutations could be discarded on average. The results found by our approach may help to make mutation testing less expensive and more accurate.
Downloads
References
Acree, J. A. T. (1980). On mutation. PhD thesis, Georgia Institute of Technology.
Ammann, P., Delamaro, M. E., and Offutt, J. (2014). Establishing theoretical minimal sets of mutants. In Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation, ICST ’14, page 21–30, USA. IEEE Computer Society.
Budd, T. and Angluin, D. (1982). Two notions of correctness and their relation to testing. Acta Informatica, 18(1):31–45.
de Moura, L. M. and Bjørner, N. (2008). Z3: an efficient SMT solver. In Proceedings of the Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340.
DeMillo, R. A., Lipton, R. J., and Sayward, F. G. (1978). Hints on test data selection: Help for the practicing programmer. Computer, 11(4):34–41.
Fernandes, L., Ribeiro, M., Carvalho, L., Gheyi, R., Mongiovi, M., Santos, A., Cavalcanti, A., Ferrari, F., and Maldonado, J. C. (2017). Avoiding useless mutants. In Proceedings of the Generative Programming: Concepts & Experiences, pages 187–198.
Gheyi, R., Ribeiro, M., Souza, B., Guimarães, M., Fernandes, L., d’Amorim, M., Alves, V., Teixeira, L., and Fonseca, B. (2021). Identifying method-level mutation subsumption relations using Z3. Information and Software Technology, 132:106496.
Guimarães, M., Fernandes, L., Ribeiro, M., d’Amorim, M., and Gheyi, R. (2020). Optimizing mutation testing by discovering dynamic mutant subsumption relations. In Proceedings of the International Conference on Software Testing, Verification and Validation, pages 198–208. IEEE.
Howden, W. (1982). Weak mutation testing and completeness of test sets. Transactions on Software Engineering, 8(4):371–379.
Jia, Y. and Harman, M. (2009). Higher order mutation testing. Information and Software Technology, 51(10):1379 – 1393.
Jia, Y. and Harman, M. (2011). An analysis and survey of the development of mutation testing. Transactions on Software Engineering, 37(5):649–678.
Just, R., Jalali, D., Inozemtseva, L., Ernst, M. D., Holmes, R., and Fraser, G. (2014). Are mutants a valid substitute for real faults in software testing? In Proceedings of the Foundations of Software Engineering, pages 654–665.
Just, R. and Schweiggert, F. (2015). Higher accuracy and lower run time: efficient mutation analysis using non-redundant mutation operators. Software Testing, Verification and Reliability, 25(5-7):490–507.
Kintis, M., Papadakis, M., Jia, Y., Malevris, N., Traon, Y. L., and Harman, M. (2017). Detecting trivial mutant equivalences via compiler optimisations. Transactions on Software Engineering, 44(4):308–333.
Kintis, M., Papadakis, M., and Malevris, N. (2010). Evaluating mutation testing alternatives: A collateral experiment. In Proceedings of the 2010 Asia Pacific Software Engineering Conference, APSEC ’10, page 300–309, USA. IEEE Computer Society.
Ma, Y.-S., Offutt, J., and Kwon, Y.-R. (2005). MuJava: an automated class mutation system. Software Testing, Verification and Reliability, 15(2):97–133.
Madeyski, L., Orzeszyna, W., Torkar, R., and Jozala, M. (2014). Overcoming the equivalent mutant problem: A systematic literature review and a comparative experiment of second order mutation. Transactions on Software Engineering, 40(1):23–42.
Marcozzi, M., Bardin, S., Kosmatov, N., Papadakis, M., Prevosto, V., and Correnson, L. (2018). Time to clean your test objectives. In Proceedings of the 40th International Conference on Software Engineering, ICSE ’18, page 456–467, New York, NY, USA. Association for Computing Machinery.
Nguyen, Q.-V. and Madeyski, L. (2014). Problems of mutation testing and higher order mutation testing. Advances in Intelligent Systems and Computing, 282:157–172.
Offutt, A. J. and Lee, S. D. (1994). An empirical evaluation of weak mutation. Transactions on Software Engineering, 20(5):337–344.
Offutt, J. (2011). A mutation carol: Past, present and future. Information and Software Technology, 53(10):1098 – 1107.
Papadakis, M., Henard, C., Harman, M., Jia, Y., and Le Traon, Y. (2016). Threats to the validity of mutation-based test assessment. In Proceedings of the 25th International Symposium on Software Testing and Analysis, ISSTA 2016, page 354–365, New York, NY, USA. Association for Computing Machinery.
Papadakis, M., Jia, Y., Harman, M., and Le Traon, Y. (2015). Trivial compiler equivalence: A large scale empirical study of a simple, fast and effective equivalent mutant detection technique. In ICSE, ICSE ’15, pages 936–946, Piscataway, NJ, USA. IEEE Press.
Papadakis, M., Kintis, M., Zhang, J., Jia, Y., Traon, Y. L., and Harman, M. (2019). Chapter six - mutation testing advances: An analysis and survey. Advances in Computers, 112:275–378.
Papadakis, M. and Malevris, N. (2010). An empirical evaluation of the first and second order mutation testing strategies. In Proceedings of the 2010 Third International Conference on Software Testing, Verification, and Validation Workshops, ICSTW ’10, page 90–99, USA. IEEE Computer Society.
Petrovic, G. and Ivankovic, M. (2018). State of mutation testing at google. In 2018 IEEE/ACM 40th International Conference on Software Engineering: Software Engineering in Practice Track (ICSE-SEIP), pages 163–171.
Schuler, D. and Zeller, A. (2013). Covering and uncovering equivalent mutants. Software Testing, Verification and Reliability, 23(5):353–374.
Winterer, D., Zhang, C., and Su, Z. (2020). Validating SMT solvers via semantic fusion. In Proceedings of the Programming Language Design and Implementation, pages 718–730.
