research-article

MEDIC

Information and Software Technology, Volume 68, Issue C

Pages 1 - 17

https://doi.org/10.1016/j.infsof.2015.07.009

Published: 01 December 2015 Publication History

Abstract

Context: The equivalent mutant problem is a well-known impediment to the adoption of mutation testing in practice. In consequence of its undecidable nature, a complete automated solution is unattainable. To worsen the situation, the manual analysis of the generated mutants of a program under test is prohibitive due to their vast number and the complexity of determining their equivalence.Objective: This paper focuses on the automated identification of equivalent and partially equivalent mutants, i.e. mutants that are equivalent to the original program for a specific subset of paths. To this end, the utilisation of a series of previously proposed data flow patterns is investigated. This study also examines the cross-language nature of these patterns and the killability of the detected partially equivalent mutants.Method: A tool, named MEDIC (Mutants' Equivalence DIsCovery), incorporating the aforementioned patterns was developed. Its efficiency and effectiveness were evaluated based on a set of manually analysed mutants from real-world programs, written in the Java programming language. Furthermore, MEDIC was employed to test subjects written in the JavaScript programming language.Results: MEDIC managed to detect 56% of the examined equivalent mutants in 125 s, providing strong evidence regarding both its effectiveness and efficiency. Additionally, MEDIC was able to identify equivalent mutants in the JavaScript test subjects, lending colour to the cross-language nature of the implemented patterns. Finally, the identified partially equivalent mutant set consisted largely of killable mutants, 16% of which were stubborn ones.Conclusion: It can be concluded that pattern-based equivalent mutant identification forms a viable approach for combating the equivalent mutant problem. MEDIC automatically detected a considerable number of the manually identified equivalent mutants and was successfully applied to test subjects in all examined programming languages.

References

[1]

R. Hamlet, Testing programs with the aid of a compiler, IEEE Trans. Softw. Eng. SE-3 (4) (1977) 279-290.

Digital Library

[2]

R. DeMillo, R. Lipton, F. Sayward, Hints on test data selection: help for the practicing programmer, Computer 11 (4) (1978) 34-41.

Digital Library

[3]

Y. Jia, M. Harman, An analysis and survey of the development of mutation testing, IEEE Trans. Softw. Eng. 37 (5) (2011) 649-678.

Digital Library

[4]

A. Offutt, R. Untch, Mutation 2000: uniting the orthogonal, in: W. Wong (Ed.), Mutation Testing for the New Century, The Springer International Series on Advances in Database Systems , 24, Springer US, 2001, pp. 34-44.

[5]

J.H. Andrews, L.C. Briand, Y. Labiche, Is mutation an appropriate tool for testing experiments? in: Proceedings of the 27th International Conference on Software Engineering, in: ICSE '05, ACM, New York, NY, USA, 2005, pp. 402-411.

[6]

J.H. Andrews, L.C. Briand, Y. Labiche, A.S. Namin, Using mutation analysis for assessing and comparing testing coverage criteria, IEEE Trans. Software Eng. 32 (8) (2006) 608-624.

Digital Library

[7]

A.J. Offutt, J. Pan, K. Tewary, T. Zhang, Experiments with data flow and mutation testing., Technical Report ISSE-TR-94-105, Department of Information and Software Systems Engineering, George Mason University, 1994.

[8]

A.P. Mathur, W.E. Wong, An empirical comparison of data flow and mutation-based test adequacy criteria, Softw. Test., Verification Reliability 4 (1) (1994) 9-31.

[9]

A.J. Offutt, J. Pan, K. Tewary, T. Zhang, An experimental evaluation of data flow and mutation testing, Softw.: Pract. Experience 26 (2) (1996) 165-176.

Digital Library

[10]

P.G. Frankl, S.N. Weiss, C. Hu, All-uses vs mutation testing: an experimental comparison of effectiveness, J. Syst. Softw. 38 (3) (1997) 235-253.

Digital Library

[11]

N. Li, U. Praphamontripong, J. Offutt, An experimental comparison of four unit test criteria: mutation, edge-pair, all-uses and prime path coverage, in: Proceedings of the International Conference on Software Testing, Verification and Validation Workshops, 2009. ICSTW '09., 2009, pp. 220-229.

Digital Library

[12]

Y.-S. Ma, J. Offutt, Y.R. Kwon, Mujava: an automated class mutation system, Softw. Test. Verification Reliability 15 (2) (2005) 97-133.

Digital Library

[13]

R.A. DeMillo, A.J. Offutt, Constraint-based automatic test data generation, IEEE Trans. Softw. Eng. 17 (9) (1991) 900-910.

Digital Library

[14]

M. Papadakis, N. Malevris, Mutation based test case generation via a path selection strategy, Informat. Softw. Technol. 54 (9) (2012) 915-932.

Digital Library

[15]

G. Fraser, A. Zeller, Mutation-driven generation of unit tests and oracles, IEEE Trans. Softw. Eng. 38 (2) (2012) 278-292.

Digital Library

[16]

A.J. Offutt, J. Pan, Automatically detecting equivalent mutants and in-feasible paths, Softw. Test., Verification Reliability 7 (3) (1997) 165-192.

[17]

R. Hierons, M. Harman, S. Danicic, Using program slicing to assist in the detection of equivalent mutants, Softw. Test., Verification. Reliability 9 (4) (1999) 233-262.

[18]

M. Harman, R. Hierons, S. Danicic, The relationship between program dependence and mutation analysis, in: W. Wong (Ed.), Mutation Testing for the New Century, The Springer International Series on Advances in Database Systems , 24, Springer US, 2001, pp. 5-13.

[19]

M. Kintis, M. Papadakis, N. Malevris, Isolating first order equivalent mutants via second order mutation, in: Proceedings of the IEEE Fifth International Conference on Software Testing, Verification and Validation (ICST), 2012, pp. 701-710.

[20]

D. Schuler, A. Zeller, Covering and uncovering equivalent mutants, Softw. Test., Verification Reliability 23 (5) (2013) 353-374.

[21]

M. Kintis, N. Malevris, Using data flow patterns for equivalent mutant detection, in: Proceedings of the IEEE Seventh International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2014, pp. 196-205.

[22]

T. Budd, D. Angluin, Two notions of correctness and their relation to testing, Acta Inform. 18 (1) (1982) 31-45.

Digital Library

[23]

B. Alpern, M.N. Wegman, F.K. Zadeck, Detecting equality of variables in programs, in: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, in: POPL '88, ACM, New York, NY, USA, 1988, pp. 1-11.

Digital Library

[24]

B.K. Rosen, M.N. Wegman, F.K. Zadeck, Global value numbers and redundant computations, in: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, in: POPL '88, ACM, New York, NY, USA, 1988, pp. 12-27.

Digital Library

[25]

R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, F.K. Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Trans. Program. Lang. Syst. 13 (4) (1991) 451-490.

Digital Library

[26]

IBM T.J. Watson Research Center. T. j. watson libraries for analysis, Last Accessed June 2015 http://wala.sourceforge.net.

[27]

J. Maldonado, M. Delamaro, S. Fabbri, A. Silva Simão, T. Sugeta, A. Vincenzi, P. Masiero, Proteum: a family of tools to support specification and program testing based on mutation, in: W. Wong (Ed.), Mutation Testing for the New Century, The Springer International Series on Advances in Database Systems , 24, Springer US, 2001, pp. 113-116.

[28]

J.-D. Choi, R. Cytron, J. Ferrante, Automatic construction of sparse data flow evaluation graphs, in: Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, in: POPL '91, ACM, New York, NY, USA, 1991, pp. 55-66.

Digital Library

[29]

M. Braun, S. Buchwald, S. Hack, R. Leia, C. Mallon, A. Zwinkau, Simple and efficient construction of static single assignment form, in: R. Jhala, K. De Bosschere (Eds.), Compiler Construction, Lecture Notes in Computer Science , 7791, Springer Berlin Heidelberg, 2013, pp. 102-122.

[30]

P. Briggs, K.D. Cooper, T.J. Harvey, L.T. Simpson, Practical improvements to the construction and destruction of static single assignment form, Software: Practice and Experience 28 (8) (1998) 859-881.

Digital Library

[31]

Neo Technology. Neo4j graph database, Last Accessed June 2015 http://neo4j.com.

[32]

J. Offutt, N. Li, The ¿java home page (version 3), Last Accessed June 2015 http://cs.gmu.edu/~offutt/mujava/index-v3-nov2008.html.

[33]

X. Yao, M. Harman, Y. Jia, A study of equivalent and stubborn mutation operators using human analysis of equivalence, in: Proceedings of the 36th International Conference on Software Engineering, in: ICSE 2014, ACM, New York, NY, USA, 2014, pp. 919-930.

Digital Library

[34]

M. Kintis, M. Papadakis, N. Malevris, Evaluating mutation testing alternatives: A collateral experiment, in: Proceedings of the 17th Asia Pacific Software Engineering Conference (APSEC), 2010, pp. 300-309.

[35]

P. Ammann, M.E. Delamaro, J. Offutt, Establishing theoretical minimal sets of mutants, in: Proceedings of the 2014 IEEE International Conference on Software Testing, Verification, and Validation, in: ICST '14, IEEE Computer Society, Washington, DC, USA, 2014, pp. 21-30.

Digital Library

[36]

L. Zhang, M. Gligoric, D. Marinov, S. Khurshid, Operator-based and random mutant selection: Better together, in: Proceedings of the IEEE/ACM 28th International Conference on Automated Software Engineering (ASE), 2013, pp. 92-102.

[37]

M. Kintis, M. Papadakis, N. Malevris, Employing second-order mutation for isolating first-order equivalent mutants, Softw. Test., Verification Reliability (2014).

[38]

L. Madeyski, W. Orzeszyna, R. Torkar, M. Jozala, Overcoming the equivalent mutant problem: a systematic literature review and a comparative experiment of second order mutation, IEEE Trans. Software Eng., 40 (1) (2014) 23-42.

Digital Library

[39]

D. Baldwin, F. Sayward, Heuristics for Determining Equivalence of Program Mutations., Technical Report 276, Department of Computer Science, Yale University, 1979.

[40]

R. DeMillo, D. Guindi, W. McCracken, A. Offutt, K. King, An extended overview of the mothra software testing environment, in: Proceedings of the Second Workshop on Software Testing, Verification, and Analysis, 1988, pp. 142-151.

[41]

A.J. Offutt, W.M. Craft, Using compiler optimization techniques to detect equivalent mutants, Softw.Test. Verification Reliability 4 (3) (1994) 131-154.

[42]

M. Papadakis, Y. Jia, M. Harman, Y. LeTraon, Trivial compiler equivalence: a large scale empirical study of a simple, fast and effective equivalent mutant detection technique, in: Proceedings of the 2015 International Conference on Software Engineering, 2015.(in press)

[43]

Oracle Technology Network. The Java Hotspot performance engine architecture, Last Accessed June 2015 http://www.oracle.com/technetwork/java/whitepaper-135217.html.

[44]

A. Offutt, J. Pan, Detecting equivalent mutants and the feasible path problem, in: Proceedings of the Eleventh Annual Conference on Computer Assurance, 1996. COMPASS '96, Systems Integrity. Software Safety. Process Security., 1996, pp. 224-236.

[45]

S. Nica, F. Wotawa, Using constraints for equivalent mutant detection, in: Proceedings of the Second Workshop on Formal Methods in the Development of Software, 2012. WS-FMDS, 2012, pp. 1-8.

[46]

S. Nica, F. Wotawa, EqMutDetect - A tool for equivalent mutant detection in embedded systems, in: Proceedings of the Tenth Workshop on Intelligent Solutions in Embedded Systems, 2012. WISES, 2012, pp. 57-62.

[47]

J.M. Voas, G. McGraw, Software Fault Injection: Inoculating Programs Against Errors, John Wiley & Sons, Inc., New York, NY, USA, 1997.

[48]

J. Offutt, Y.-S. Ma, Y.-R. Kwon, The class-level mutants of mujava, in: Proceedings of the 2006 International Workshop on Automation of Software Test, in: AST '06, ACM, New York, NY, USA, 2006, pp. 78-84.

Digital Library

[49]

Y. Jia, M. Harman, Higher order mutation testing, Informat. Softw. Technol. 51 (10) (2009) 1379-1393. Source Code Analysis and Manipulation, {SCAM} 2008

Digital Library

[50]

M. Polo, M. Piattini, I. GarcÃa-RodrÃguez, Decreasing the cost of mutation testing with second-order mutants, Softw. Test., Verification Reliability 19 (2) (2009) 111-131.

Digital Library

[51]

M. Papadakis, N. Malevris, An empirical evaluation of the first and second order mutation testing strategies, in: Proceedings of the Third International Conference on Software Testing, Verification, and Validation Workshops (ICSTW), 2010, 2010, pp. 90-99.

Digital Library

[52]

B. Grün, D. Schuler, A. Zeller, The impact of equivalent mutants, in: Proceedings of the International Conference on Proceedings of the Software Testing, Verification and Validation Workshops, 2009. ICSTW '09., 2009, pp. 192-199.

Digital Library

[53]

D. Schuler, V. Dallmeier, A. Zeller, Efficient mutation testing by checking invariant violations, in: Proceedings of the Eighteenth International Symposium on Software Testing and Analysis, in: ISSTA '09, ACM, New York, NY, USA, 2009, pp. 69-80.

Digital Library

[54]

D. Schuler, A. Zeller, (Un-)Covering equivalent mutants, in: Proceedings of the Third International Conference on Software Testing, Verification and Validation (ICST), 2010, 2010, pp. 45-54.

Digital Library

[55]

D. Schuler, A. Zeller, Javalanche: efficient mutation testing for java, in: Proceedings of the the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering, in: ESEC/FSE '09, ACM, New York, NY, USA, 2009, pp. 297-298.

[56]

J. Nanavati, F. Wu, M. Harman, Y. Jia, J. Krinke, Mutation testing of memory-related operators, in: Proceedings of the IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), 2015, 2015, pp. 1-10.

[57]

M. Kintis, N. Malevris, Identifying more equivalent mutants via code similarity, in: Proceedings of the 20th Asia-Pacific Software Engineering Conference (APSEC), 1, 2013, pp. 180-188.

Cited By

Gómez-Abajo PPérez-Soler SCañizares PGuerra Ede Lara J(2024)Mutation Testing for Task-Oriented ChatbotsProceedings of the 28th International Conference on Evaluation and Assessment in Software Engineering10.1145/3661167.3661220(232-241)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3661167.3661220
Demeyer SParsai AVercammen Svan Bladel BAbdi M(2020)Formal Verification of Developer Tests: A Research Agenda Inspired by Mutation TestingLeveraging Applications of Formal Methods, Verification and Validation: Engineering Principles10.1007/978-3-030-61470-6_2(9-24)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-61470-6_2
Naeem MLin TNaeem HLiu H(2019)A machine learning approach for classification of equivalent mutantsJournal of Software: Evolution and Process10.1002/smr.223832:5Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1002/smr.2238
Show More Cited By

MEDIC
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Using coverage criteria on RepOK to reduce bounded-exhaustive test suites
TAP'12: Proceedings of the 6th international conference on Tests and Proofs

Bounded-exhaustive exploration of test case candidates is a commonly employed approach for test generation in some contexts. Even when small bounds are used for test generation, executing the obtained tests may become prohibitive, despite the time for ...
A Static Approach to Prioritizing JUnit Test Cases

Test case prioritization is used in regression testing to schedule the execution order of test cases so as to expose faults earlier in testing. Over the past few years, many test case prioritization techniques have been proposed in the literature. Most ...
Spartan: a spectral and entropy-based partial-scan and test point insertion algorithm

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Software Technology

Information and Software Technology Volume 68, Issue C

December 2015

98 pages

ISSN:0950-5849

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Butterworth-Heinemann

United States

Publication History

Published: 01 December 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gómez-Abajo PPérez-Soler SCañizares PGuerra Ede Lara J(2024)Mutation Testing for Task-Oriented ChatbotsProceedings of the 28th International Conference on Evaluation and Assessment in Software Engineering10.1145/3661167.3661220(232-241)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3661167.3661220
Demeyer SParsai AVercammen Svan Bladel BAbdi M(2020)Formal Verification of Developer Tests: A Research Agenda Inspired by Mutation TestingLeveraging Applications of Formal Methods, Verification and Validation: Engineering Principles10.1007/978-3-030-61470-6_2(9-24)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1007/978-3-030-61470-6_2
Naeem MLin TNaeem HLiu H(2019)A machine learning approach for classification of equivalent mutantsJournal of Software: Evolution and Process10.1002/smr.223832:5Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1002/smr.2238
Shin DYoo SBae D(2018)A Theoretical and Empirical Study of Diversity-Aware Mutation Adequacy CriterionIEEE Transactions on Software Engineering10.1109/TSE.2017.273234744:10(914-931)Online publication date: 12-Oct-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2732347
Kintis MPapadakis MPapadopoulos AValvis EMalevris NLe Traon Y(2018)How effective are mutation testing tools? An empirical analysis of Java mutation testing tools with manual analysis and real faultsEmpirical Software Engineering10.1007/s10664-017-9582-523:4(2426-2463)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1007/s10664-017-9582-5
Fernandes LRibeiro MCarvalho LGheyi RMongiovi MSantos ACavalcanti AFerrari FMaldonado J(2017)Avoiding useless mutantsACM SIGPLAN Notices10.1145/3170492.313605352:12(187-198)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3170492.3136053
Fernandes LRibeiro MCarvalho LGheyi RMongiovi MSantos ACavalcanti AFerrari FMaldonado JFlatt MErdweg S(2017)Avoiding useless mutantsProceedings of the 16th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/3136040.3136053(187-198)Online publication date: 23-Oct-2017
https://dl.acm.org/doi/10.1145/3136040.3136053

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents