Equivalent Mutants in Configurable Systems: An Empirical Study

ABSTRACT

Mutation testing is a program-transformation technique that evaluates the quality of test cases by assessing their capability to detect injected artificial faults. The costs of using mutation testing are usually high, hindering its use in industry. Previous research has reported that roughly one-third of the mutants generated in single systems are equivalents. In configurable systems, a set of mutation operators that focus on preprocessor directives (e.g., #ifdef) has been proposed. However, there is a lack of existing studies that investigate whether equivalent mutants do occur with these operators. To perform this investigation, we provide a tool that implements the aforementioned mutation operators and we conduct an empirical study using 20 C files of four industrial-scale systems. In particular, we provide examples of equivalent mutants and detailed information, such as which mutation operators generate these mutants and how often they occur. Our preliminary results show that nearly 40% of the generated mutants are equivalent. Hence, testing costs can be drastically reduced if the community comes up with efficient techniques to avoid these equivalent mutants.

References

1. Iago Abal, Claus Brabrand, and Andrzej Wasowski. 2014. 42 Variability Bugs in the Linux Kernel: A Qualitative Analysis. In Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering. 421--432.
2. Mustafa Al-Hajjaji, Fabian Benduhn, Thomas Thüm, Thomas Leich, and Gunter Saake. 2016. Mutation Operators for Preprocessor-Based Variability. In Proceedings of the Tenth International Workshop on Variability Modelling of Software-intensive Systems. 81--88.
3. Mustafa Al-Hajjaji, Sebastian Krieter, Thomas Thüm, Malte Lochau, and Gunter Saake. 2016. IncLing: Efficient Product-line Testing Using Incremental Pairwise Sampling. In Proceedings of the International Conference on Generative Programming: Concepts Experience. 144--155.
4. Mustafa Al-Hajjaji, Jacob Krüger, Fabian Benduhn, Thomas Leich, and Gunter Saake. 2017. Efficient Mutation Testing in Configurable Systems. In Proceedings of the International Workshop on Variability and Complexity in Software Design (VACE '17). 2--8.
5. Mustafa Al-Hajjaji, Thomas Thüm, Malte Lochau, Jens Meinicke, and Gunter Saake. 2017. Effective Product-Line Testing Using Similarity-Based Product Prioritization. Software & Systems Modeling (2017). To appear.
6. Jr. Allen Troy Acree. 1980. On Mutation. Ph.D. Dissertation. Georgia Institute of Technology.
7. Paolo Arcaini, Angelo Gargantini, and Paolo Vavassori. 2015. Generating tests for detecting faults in feature models. In Software Testing, Verification and Validation. 1--10.
8. Douglas Baldwin and Frederick Sayward. 1979. Heuristics for Determining Equivalence of Program Mutations. Technical Report. DTIC Document.
9. Larissa Braz, Rohit Gheyi, Melina Mongiovi, Márcio Ribeiro, Flávio Medeiros, and Leopoldo Teixeira. 2016. A Change-centric Approach to Compile Configurable Systems with #ifdefs. In Proceedings of the International Conference on Generative Programming: Concepts and Experiences. 109--119.
10. Timothy Budd and Dana Angluin. 1982. Two notions of correctness and their relation to testing. Acta Informatica 18, 1 (1982), 31--45.
11. Timothy Alan Budd. 1980. Mutation Analysis of Program Test Data. Ph.D. Dissertation. Yale University, New Haven, CT, USA.
12. Richard DeMillo, Richard Lipton, and Frederick Sayward. 1978. Hints on Test Data Selection: Help for the Practicing Programmer. Computer 11, 4 (1978), 34--41.
13. Xavier Devroey, Gilles Perrouin, Maxime Cordy, Mike Papadakis, Axel Legay, and Pierre-Yves Schobbens. 2014. A Variability Perspective of Mutation Analysis. In Proceedings of the International Symposium on Foundations of Software Engineering. 841--844.
14. Xavier Devroey, Gilles Perrouin, Mike Papadakis, Axel Legay, Pierre-Yves Schobbens, and Patrick Heymans. 2016. Featured Model-based Mutation Analysis. In Proceedings of the International Conference on Software Engineering. 655--666.
15. Leonardo Fernandes, Márcio Ribeiro, Luiz Carvalho, Rohit Gheyi, Melina Mongiovi, André Santos, Ana Cavalcanti, Fabiano Ferrari, and José Carlos Maldonado. 2017. Avoiding Useless Mutants. In Proceedings of the 16th International Conference on Generative Programming: Concepts Experience. 187--198.
16. Christopher Henard, Mike Papadakis, and Yves Le Traon. 2014. Mutation-based generation of software product line test configurations. In International Symposium on Search Based Software Engineering. 92--106.
17. Christopher Henard, Mike Papadakis, Gilles Perrouin, Jacques Klein, Patrick Heymans, and Yves Le Traon. 2014. Bypassing the Combinatorial Explosion: Using Similarity to Generate and Prioritize T-Wise Test Configurations for Software Product Lines. IEEE Transaction Software Engineering 40, 7 (2014), 650--670.
18. Yue Jia and Mark Harman. 2011. An Analysis and Survey of the Development of Mutation Testing. IEEE Transactions on Software Engineering 37, 5 (2011), 649--678.
19. Martin Fagereng Johansen, Øystein Haugen, and Franck Fleurey. 2012. An Algorithm for Generating T-Wise Covering Arrays from Large Feature Models. In Proceedings of the International Software Product Line Conference. ACM, NY, USA, 46--55.
20. René Just. 2014. The Major mutation framework: Efficient and scalable mutation analysis for Java. In Proceedings of the International Symposium on Software Testing and Analysis. 433--436.
21. Marinos Kintis, Mike Papadakis, Yue Jia, Nicos Malevris, Yves Le Traon, and Mark Harman. 2017. Detecting Trivial Mutant Equivalences via Compiler Optimisations. IEEE Transactions on Software Engineering PP, 99 (2017), 1--1.
22. Hartmut Lackner and Martin Schmidt. 2014. Towards the assessment of software product line tests: a mutation system for variable systems. In Proceedings of the 18th International Software Product Line Conference: Companion Volume for Workshops, Demonstrations and Tools-Volume 2. 62--69.
23. Sascha Lity, Mustafa Al-Hajjaji, Thomas Thüm, and Ina Schaefer. 2017. Optimizing Product Orders Using Graph Algorithms for Improving Incremental Product-line Analysis. In Proceedings of the International Workshop on Variability Modelling of Software-intensive Systems. 60--67.
24. Lech Madeyski, Wojciech Orzeszyna, Richard Torkar, and Mariusz Jozala. 2014. Overcoming the Equivalent Mutant Problem: A Systematic Literature Review and a Comparative Experiment of Second Order Mutation. IEEE Transactions on Software Engineering 40, 1 (2014), 23--42.
25. A. Jefferson Offutt and W. Michael Craft. 1994. Using compiler optimization techniques to detect equivalent mutants. Software Testing, Verification and Reliability 4, 3 (1994), 131--154.
26. Mike Papadakis, Christopher Henard, and Yves Le Traon. 2014. Sampling program inputs with mutation analysis: Going beyond combinatorial interaction testing. In Software Testing, Verification and Validation. 1--10.
27. Mike Papadakis, Yue Jia, Mark Harman, and Yves Le Traon. 2015. Trivial Compiler Equivalence: A Large Scale Empirical Study of a Simple, Fast and Effective Equivalent Mutant Detection Technique. In IEEE International Conference on Software Engineering. 936--946.
28. Gilles Perrouin, Sagar Sen, Jacques Klein, Benoit Baudry, and Yves Le Traon. 2010. Automated and Scalable T-Wise Test Case Generation Strategies for Software Product Lines. In Proceedings of the International Conference on Software Testing, Verification and Validation. IEEE, Washington, 459--468.
29. Dennis Reuling, Johannes Bürdek, Serge Rotärmel, Malte Lochau, and Udo Kelter. 2015. Fault-Based Product-Line Testing: Effective Sample Generation Based on Feature-Diagram Mutation. In Proceedings of the the International Conference on Software Product Line. 131--140.
30. Ana B. Sánchez, Sergio Segura, and Antonio Ruiz-Cortés. 2014. A Comparison of Test Case Prioritization Criteria for Software Product Lines. In Proceedings of the International Conference on Software Testing, Verification and Validation. 41--50.
31. David Schuler and Andreas Zeller. 2013. Covering and Uncovering Equivalent Mutants. Software Testing, Verification and Reliability 23, 5 (2013), 353--374.
32. Lingming Zhang, Milos Gligoric, Darko Marinov, and Sarfraz Khurshid. 2013. Operator-Based and Random Mutant Selection: Better Together. In Proceedings of the International Conference on Automated Software Engineering. IEEE, 92--102.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Verification

• Software and its engineering

  • Software creation and management

    • Software development process management

    • Software verification and validation

      • Software defect analysis

        • Software testing and debugging

  • Software organization and properties

    • Software functional properties

      • Formal methods

        • Software verification