research-article

Trivial compiler equivalence: a large scale empirical study of a simple, fast and effective equivalent mutant detection technique

Authors:

Mike Papadakis,

Yves Le TraonAuthors Info & Claims

ICSE '15: Proceedings of the 37th International Conference on Software Engineering - Volume 1

Pages 936 - 946

Published: 16 May 2015 Publication History

Abstract

Identifying equivalent mutants remains the largest impediment to the widespread uptake of mutation testing. Despite being researched for more than three decades, the problem remains. We propose Trivial Compiler Equivalence (TCE) a technique that exploits the use of readily available compiler technology to address this long-standing challenge. TCE is directly applicable to real-world programs and can imbue existing tools with the ability to detect equivalent mutants and a special form of useless mutants called duplicated mutants. We present a thorough empirical study using 6 large open source programs, several orders of magnitude larger than those used in previous work, and 18 benchmark programs with hand-analysis equivalent mutants. Our results reveal that, on large real-world programs, TCE can discard more than 7% and 21% of all the mutants as being equivalent and duplicated mutants respectively. A human-based equivalence verification reveals that TCE has the ability to detect approximately 30% of all the existing equivalent mutants.

References

[1]

R. Just, D. Jalali, L. Inozemtseva, M. D. Ernst, R. Holmes, and G. Fraser, "Are mutants a valid substitute for real faults in software testing?" in FSE, 2014, pp. 654--665.

Digital Library

[2]

J. H. Andrews, L. C. Briand, and Y. Labiche, "Is Mutation an Appropriate Tool for Testing Experiments?" in ICSE, 2005, pp. 402--411.

Digital Library

[3]

M. Daran and P. Thévenod-Fosse, "Software error analysis: A real case study involving real faults and mutations," in ISSTA, 1996, pp. 158--171.

Digital Library

[4]

R. Baker and I. Habli, "An empirical evaluation of mutation testing for improving the test quality of safety-critical software," IEEE Trans. Softw. Eng., vol. 39, no. 6, pp. 787--805, 2013.

Digital Library

[5]

B. H. Smith and L. Williams, "On guiding the augmentation of an automated test suite via mutation analysis," Emp. Soft. Eng., vol. 14, no. 3, pp. 341--369, 2009.

Digital Library

[6]

A. J. Offutt, J. Pan, K. Tewary, and T. Zhang, "An Experimental Evaluation of Data Flow and Mutation Testing," Software Pract. Exper., vol. 26, no. 2, pp. 165--176, 1996.

Digital Library

[7]

P. G. Frankl, S. N. Weiss, and C. Hu, "All-Uses Versus Mutation Testing: An Experimental Comparison of Effectiveness," Polytechnic University, Brooklyn, New York, Technique Report, 1994.

[8]

L. Inozemtseva and R. Holmes, "Coverage is not strongly correlated with test suite effectiveness". in ICSE, 2014, pp. 435--445.

Digital Library

[9]

M. Gligoric, A. Groce, C. Zhang, R. Sharma, M. A. Alipour, and D. Marinov, "Comparing non-adequate test suites using coverage criteria," in ISSTA, 2013, pp. 302--313.

Digital Library

[10]

Y. Jia and M. Harman, "An Analysis and Survey of the Development of Mutation Testing," IEEE Trans. Softw. Eng., vol. 37, no. 5, pp. 649--678, 2011.

Digital Library

[11]

G. Fraser and A. Zeller, "Mutation-driven generation of unit tests and oracles," in ISSTA, 2010, pp. 147--158.

Digital Library

[12]

M. Papadakis and N. Malevris, "Automatic mutation test case generation via dynamic symbolic execution," in ISSRE, 2010, pp. 121--130.

Digital Library

[13]

M. Harman, Y. Jia, and W. B. Langdon, "Strong higher order mutation-based test data generation," in FSE, 2011, pp. 212--222.

Digital Library

[14]

L. Zhang, S.-S. Hou, J.-J. Hu, T. Xie, and H. Mei, "Is operator-based mutant selection superior to random mutant selection?" in ICSE, 2010, pp. 435--444.

Digital Library

[15]

W. E. Wong and A. P. Mathur, "Reducing the Cost of Mutation Testing: An Empirical Study," J. Syst. Software, vol. 31, no. 3, pp. 185--196, December 1995.

Digital Library

[16]

M. Papadakis and N. Malevris, "An Empirical Evaluation of the First and Second Order Mutation Testing Strategies," in ICST Workshops, 2010, pp. 90--99.

Digital Library

[17]

L. Zhang, D. Marinov, and S. Khurshid, "Faster mutation testing inspired by test prioritization and reduction," in ISSTA, 2013, pp. 235--245.

Digital Library

[18]

R. Just, M. D. Ernst, and G. Fraser, "Efficient mutation analysis by propagating and partitioning infected execution states," in ISSTA, 2014, pp. 315--326.

Digital Library

[19]

T. A. Budd and D. Angluin, "Two Notions of Correctness and Their Relation to Testing," Acta Informatica, vol. 18, no. 1, pp. 31--45, 1982.

Digital Library

[20]

X. Yao, M. Harman, and Y. Jia, "A Study of Equivalent and Stubborn Mutation Operators Using Human Analysis of Equivalence," in ICSE, 2014, pp. 919--930.

Digital Library

[21]

A. J. Offutt and W. M. Craft, "Using Compiler Optimization Techniques to Detect Equivalent Mutants," Softw. Test. Verif. Rel., vol. 4, no. 3, pp. 131--154, 1994.

[22]

D. Baldwin and F. G. Sayward, "Heuristics for Determining Equivalence of Program Mutations," Yale University, New Haven, Connecticut, Research Report 276, 1979.

[23]

A. T. Acree, "On Mutation," PhD Thesis, Georgia Institute of Technology, Atlanta, Georgia, 1980.

Digital Library

[24]

A. J. Offutt and J. Pan, "Detecting Equivalent Mutants and the Feasible Path Problem," in COMPASS, 1996, pp. 224--236.

[25]

A. J. Offutt and J. Pan, "Automatically Detecting Equivalent Mutants and Infeasible Paths," Softw. Test. Verif. Rel., vol. 7, no. 3, pp. 165--192, September 1997.

[26]

J. Voas and G. McGraw, Software Fault Injection: Inoculating Programs Against Errors. John Wiley & Sons, 1997.

Digital Library

[27]

R. M. Hierons, M. Harman, and S. Danicic, "Using Program Slicing to Assist in the Detection of Equivalent Mutants," Softw. Test. Verif. Rel., vol. 9, no. 4, pp. 233--262, 1999.

[28]

M. Harman, R. Hierons, and S. Danicic, "The relationship between program dependence and mutation analysis," in Mutation Testing for the New Century. Kluwer Academic Publishers, 2001, pp. 5--13.

Digital Library

[29]

K. Adamopoulos, M. Harman, and R. M. Hierons, "How to Overcome the Equivalent Mutant Problem and Achieve Tailored Selective Mutation Using Co-evolution," in GECCO (2). Springer, 2004, pp. 1338--1349.

[30]

B. J. M. Grün, D. Schuler, and A. Zeller, "The Impact of Equivalent Mutants," in ICST Workshops, 2009, pp. 192--199.

Digital Library

[31]

D. Schuler, V. Dallmeier, and A. Zeller, "Efficient Mutation Testing by Checking Invariant Violations," in ISSTA, 2009.

Digital Library

[32]

D. Schuler and A. Zeller, "Covering and uncovering equivalent mutants," Softw. Test. Verif. Rel., vol. 23, no. 5, pp. 353--374, 2013.

[33]

D. Schuler and A. Zeller, "(Un-)Covering Equivalent Mutants," in ICST, 2010, pp. 45--54.

Digital Library

[34]

S. Nica and F. Wotawa, "Using constraints for equivalent mutant detection," in WS-FMDS, 2012, pp. 1--8.

[35]

M. Kintis, M. Papadakis, and N. Malevris, "Isolating first order equivalent mutants via second order mutation," in ICST, 2012, pp. 701--710.

Digital Library

[36]

M. Kintis, "Employing second-order mutation for isolating first-order equivalent mutants," Softw. Test. Verif. Rel., pp. n/a--n/a, 2014.

Digital Library

[37]

M. Kintis and N. Malevris, "Using data flow patterns for equivalent mutant detection," in ICST Workshops, 2014, pp. 196--205.

Digital Library

[38]

M. Papadakis, M. Delamaro, and Y. L. Traon, "Mitigating the effects of equivalent mutants with mutant classification strategies," Sci. Comput. Program., vol. 95, pp. 298--319, 2014.

Digital Library

[39]

A. J. Offutt, A. Lee, G. Rothermel, R. H. Untch, and C. Zapf, "An Experimental Determination of Sufficient Mutant Operators," ACM T. Softw. Eng. Meth., vol. 5, no. 2, pp. 99--118, April 1996.

Digital Library

[40]

A. S. Namin, J. H. Andrews, and D. J. Murdoch, "Sufficient Mutation Operators for Measuring Test Effectiveness," in ICSE, 2008, pp. 351--360.

Digital Library

[41]

R. H. Untch, A. J. Offutt, and M. J. Harrold, "Mutation Analysis Using Mutant Schemata," in ISSTA, 1993, pp. 139--148.

Digital Library

[42]

Y.-S. Ma, A. J. Offutt, and Y.-R. Kwon, "MuJava: An Automated Class Mutation System," Softw. Test. Verif. & Rel., vol. 15, no. 2, pp. 97--133, June 2005.

Digital Library

[43]

M. Kintis, M. Papadakis, and N. Malevris, "Evaluating mutation testing alternatives: A collateral experiment," in APSEC, 2010, pp. 300--309.

Digital Library

[44]

P. Ammann, M. E. Delamaro, and J. Offutt, "Establishing theoretical minimal sets of mutants," in ICST, 2014, pp. 21--30.

Digital Library

[45]

G. Kaminski, P. Ammann, and J. Offutt, "Better predicate testing," in AST, 2011, pp. 57--63.

Digital Library

[46]

G. Kaminski, "Improving logic-based testing," J. Syst. Software, vol. 86, no. 8, pp. 2002--2012, 2013.

Digital Library

[47]

R. Just, G. M. Kapfhammer, and F. Schweiggert, "Using non-redundant mutation operators and test suite prioritization to achieve efficient and scalable mutation analysis," in ISSRE, 2012, pp. 11--20.

Digital Library

[48]

K.-C. Tai, "Theory of fault-based predicate testing for computer programs," IEEE Trans. Softw. Eng., vol. 22, no. 8, pp. 552--562, 1996.

Digital Library

[49]

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

Digital Library

[50]

Y. Jia and M. Harman, "Constructing Subtle Faults Using Higher Order Mutation Testing," in SCAM, 2008, pp. 249--258.

[51]

W. B. Langdon, M. Harman, and Y. Jia, "Efficient multi-objective higher order mutation testing with genetic programming". J. Syst. Software, pp. 2416--2430, 2010.

Digital Library

[52]

M. Harman, Y. Jia, P. Reales Mateo, and M. Polo, "Angels and monsters: An empirical investigation of potential test effectiveness and efficiency improvement from strongly subsuming higher order mutation," in ASE, 2014, pp. 397--408.

Digital Library

[53]

J. H. Andrews, L. C. Briand, Y. Labiche, and A. S. Namin, "Using Mutation Analysis for Assessing and Comparing Testing Coverage Criteria," IEEE Trans. Softw. Eng., vol. 32, no. 8, pp. 608--624, 2006.

Digital Library

[54]

Y. Jia and M. Harman, "MILU: A Customizable, Runtime-Optimized Higher Order Mutation Testing Tool for the Full C Language," in TAIC PART, 2008, pp. 94--98.

Digital Library

[55]

A. Lakhotia, M. D. Preda, and R. Giacobazzi, "Fast location of similar code fragments using semantic 'juice'," in PPREW@POPL, 2013, p. 5.

[56]

M. E. Delamaro, L. Deng, V. H. S. Durelli, N. Li, and J. Offutt, "Experimental evaluation of sdl and one-op mutation for c," in ICST, 2014, pp. 203--212.

Digital Library

[57]

L. S. Ghandehari, J. Czerwonka, Y. Lei, S. Shafiee, R. Kacker, and D. R. Kuhn, "An empirical comparison of combinatorial and random testing". in ICST Workshops, 2014, pp. 68--77.

Digital Library

[58]

C. Wohlin, P. Runeson, M. Höst, M. C. Ohlsson, and B. Regnell, Experimentation in Software Engineering. Springer, 2012.

Digital Library

Cited By

Ma WChekam TPapadakis MHarman M(2021)MuDeltaProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00086(897-909)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00086
Ruland SLuthmann LBürdek JLity SThüm TLochau MRibeiro M(2020)Measuring effectiveness of sample-based product-line testingACM SIGPLAN Notices10.1145/3393934.327813053:9(119-133)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278130
Arrieta AAgirre JSagardui GCoello Coello C(2020)Seeding strategies for multi-objective test case selectionProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389810(1222-1231)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389810
Show More Cited By

Index Terms

Trivial compiler equivalence: a large scale empirical study of a simple, fast and effective equivalent mutant detection technique
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

A study of equivalent and stubborn mutation operators using human analysis of equivalence
ICSE 2014: Proceedings of the 36th International Conference on Software Engineering

Though mutation testing has been widely studied for more than thirty years, the prevalence and properties of equivalent mutants remain largely unknown. We report on the causes and prevalence of equivalent mutants and their relationship to stubborn ...
Study of trivial compiler equivalence on C++ object-oriented mutation operators
SAC '19: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing

Trivial Compiler Equivalence (TCE) has been recently proposed as an effective technique to detect equivalences between programs, where two or more programs are equivalent if the compiler produces the same binary code. Mutation testing can greatly ...
Observation equivalence as a testing equivalence

A notion of testing is developed for transition systems with divergence. The forms of testing include traces, refusals, copying and global testing. Both denotational and operational formulations of testing are given. The equivalence based on this notion ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '15: Proceedings of the 37th International Conference on Software Engineering - Volume 1

May 2015

999 pages

ISBN:9781479919345

General Chair:
Antonia Bertolino
ISTI-CNR, Italy
,
Program Chairs:
Gerardo Canfora
University of Sannio, Italy
,
Sebastian Elbaum
University of Nebraska-Lincoln

Sponsors

ACM: Association for Computing Machinery
SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS\DATC: IEEE Computer Society
TCSE: IEEE Computer Society's Tech. Council on Software Engin.

Publisher

IEEE Press

Publication History

Published: 16 May 2015

Check for updates

Qualifiers

Research-article

Conference

ICSE '15

Sponsor:

ACM
SIGSOFT
IEEE-CS\DATC
TCSE

ICSE '15: 37th International Conference on Software Engineering

May 16 - 24, 2015

Florence, Italy

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
243
Total Downloads

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

Reflects downloads up to 13 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma WChekam TPapadakis MHarman M(2021)MuDeltaProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00086(897-909)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00086
Ruland SLuthmann LBürdek JLity SThüm TLochau MRibeiro M(2020)Measuring effectiveness of sample-based product-line testingACM SIGPLAN Notices10.1145/3393934.327813053:9(119-133)Online publication date: 7-Apr-2020
https://dl.acm.org/doi/10.1145/3393934.3278130
Arrieta AAgirre JSagardui GCoello Coello C(2020)Seeding strategies for multi-objective test case selectionProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3389810(1222-1231)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3389810
Guo RGu TYao YXu FMa X(2019)Speedup Automatic Program Repair Using Dynamic Software UpdatingProceedings of the 11th Asia-Pacific Symposium on Internetware10.1145/3361242.3361245(1-10)Online publication date: 28-Oct-2019
https://dl.acm.org/doi/10.1145/3361242.3361245
Dallilo LPizzoleto AFerrari FMachado ISouza RMaciel RSant'Anna C(2019)An Evaluation of Internal Program Metrics as Predictors of Mutation Operator ScoreProceedings of the IV Brazilian Symposium on Systematic and Automated Software Testing10.1145/3356317.3356323(12-21)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3356317.3356323
Andrade SBrito CJúnior MMarciel AAbdalla GDelamaro MMachado ISouza RMaciel RSant'Anna C(2019)Analyzing the effectiveness of One-Op Mutation against the minimal set of mutantsProceedings of the IV Brazilian Symposium on Systematic and Automated Software Testing10.1145/3356317.3356321(22-31)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3356317.3356321
Chekam TPapadakis MLe Traon YDumas MPfahl DApel SRusso A(2019)Mart: a mutant generation tool for LLVMProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3341180(1080-1084)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3341180
Markiegi UArrieta AEtxeberria LSagardui GHung CPapadopoulos G(2019)Test case selection using structural coverage in software product lines for time-budget constrained scenariosProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297512(2362-2371)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297512
Delgado-Pérez PSegura SHung CPapadopoulos G(2019)Study of trivial compiler equivalence on C++ object-oriented mutation operatorsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3297499(2224-2230)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3297499
Shi ABell JMarinov DZhang DMøller A(2019)Mitigating the effects of flaky tests on mutation testingProceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3293882.3330568(112-122)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.1145/3293882.3330568
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents