Mutation testing

Mutation testing (or mutation analysis or program mutation) is used to design new software tests and evaluate the quality of existing software tests. Mutation testing involves modifying a program in small ways.[1] Each mutated version is called a mutant and tests detect and reject mutants by causing the behavior of the original version to differ from the mutant. This is called killing the mutant. Test suites are measured by the percentage of mutants that they kill. New tests can be designed to kill additional mutants. Mutants are based on well-defined mutation operators that either mimic typical programming errors (such as using the wrong operator or variable name) or force the creation of valuable tests (such as dividing each expression by zero). The purpose is to help the tester develop effective tests or locate weaknesses in the test data used for the program or in sections of the code that are seldom or never accessed during execution. Mutation testing is a form of white-box testing.

Introduction

Most of this article is about "program mutation", in which the program is modified. A more general definition of mutation analysis is using well-defined rules defined on syntactic structures to make systematic changes to software artifacts.[2] Mutation analysis has been applied to other problems, but is usually applied to testing. So mutation testing is defined as using mutation analysis to design new software tests or to evaluate existing software tests.[2] Thus, mutation analysis and testing can be applied to design models, specifications, databases, tests, XML, and other types of software artifacts, although program mutation is the most common.

Overview

Tests can be created to verify the correctness of the implementation of a given software system, but the creation of tests still poses the question whether the tests are correct and sufficiently cover the requirements that have originated the implementation. (This technological problem is itself an instance of a deeper philosophical problem named "Quis custodiet ipsos custodes?" ["Who will guard the guards?"].) The idea is that if a mutant is introduced without being detected by the test suite, this indicates either that the code that had been mutated was never executed (dead code) or that the test suite was unable to locate the faults represented by the mutant.

For this to function at any scale, a large number of mutants are usually introduced, leading to the compilation and execution of an extremely large number of copies of the program. This problem of the expense of mutation testing had reduced its practical use as a method of software testing. However, the increased use of object oriented programming languages and unit testing frameworks has led to the creation of mutation testing tools that test individual portions of an application.

Goals

The goals of mutation testing are multiple:

• identify weakly tested pieces of code (those for which mutants are not killed)[1]
• identify weak tests (those that never kill mutants)[3]
• compute the mutation score[2]
• learn about error propagation and state infection in the program[4]

History

Mutation testing was originally proposed by Richard Lipton as a student in 1971,[5] and first developed and published by DeMillo, Lipton and Sayward.[1] The first implementation of a mutation testing tool was by Timothy Budd as part of his PhD work (titled Mutation Analysis) in 1980 from Yale University.[6]

Recently, with the availability of massive computing power, there has been a resurgence of mutation analysis within the computer science community, and work has been done to define methods of applying mutation testing to object oriented programming languages and non-procedural languages such as XML, SMV, and finite state machines.

In 2004 a company called Certess Inc. (now part of Synopsys) extended many of the principles into the hardware verification domain. Whereas mutation analysis only expects to detect a difference in the output produced, Certess extends this by verifying that a checker in the testbench will actually detect the difference. This extension means that all three stages of verification, namely: activation, propagation and detection are evaluated. They called this functional qualification.

Fuzzing can be considered to be a special case of mutation testing. In fuzzing, the messages or data exchanged inside communication interfaces (both inside and between software instances) are mutated to catch failures or differences in processing the data. Codenomicon[7] (2001) and Mu Dynamics (2005) evolved fuzzing concepts to a fully stateful mutation testing platform, complete with monitors for thoroughly exercising protocol implementations.

Mutation testing overview

Mutation testing is based on two hypotheses. The first is the competent programmer hypothesis. This hypothesis states that most software faults introduced by experienced programmers are due to small syntactic errors.[1] The second hypothesis is called the coupling effect. The coupling effect asserts that simple faults can cascade or couple to form other emergent faults.[8][9]

Subtle and important faults are also revealed by higher-order mutants, which further support the coupling effect.[10][11][3][12][13] Higher-order mutants are enabled by creating mutants with more than one mutation.

Mutation testing is done by selecting a set of mutation operators and then applying them to the source program one at a time for each applicable piece of the source code. The result of applying one mutation operator to the program is called a mutant. If the test suite is able to detect the change (i.e. one of the tests fails), then the mutant is said to be killed.

For example, consider the following C++ code fragment:

if (a && b) {
    c = 1;
} else {
    c = 0;
}

The condition mutation operator would replace && with || and produce the following mutant:

if (a || b) {
    c = 1;
} else {
    c = 0;
}

Now, for the test to kill this mutant, the following three conditions should be met:

1. A test must reach the mutated statement.
2. Test input data should infect the program state by causing different program states for the mutant and the original program. For example, a test with a = 1 and b = 0 would do this.
3. The incorrect program state (the value of 'c') must propagate to the program's output and be checked by the test.

These conditions are collectively called the RIP model.[5]

Weak mutation testing (or weak mutation coverage) requires that only the first and second conditions are satisfied. Strong mutation testing requires that all three conditions are satisfied. Strong mutation is more powerful, since it ensures that the test suite can really catch the problems. Weak mutation is closely related to code coverage methods. It requires much less computing power to ensure that the test suite satisfies weak mutation testing than strong mutation testing.

However, there are cases where it is not possible to find a test case that could kill this mutant. The resulting program is behaviorally equivalent to the original one. Such mutants are called equivalent mutants.

Equivalent mutants detection is one of biggest obstacles for practical usage of mutation testing. The effort needed to check if mutants are equivalent or not can be very high even for small programs.[14] A systematic literature review of a wide range of approaches to overcome the Equivalent Mutant Problem (presented by [15]) identified 17 relevant techniques (in 22 articles) and three categories of techniques: detecting (DEM); suggesting (SEM); and avoiding equivalent mutant generation (AEMG). The experiment indicated that Higher Order Mutation in general and JudyDiffOp strategy in particular provide a promising approach to the Equivalent Mutant Problem.

Mutation operators

Many mutation operators have been explored by researchers. Here are some examples of mutation operators for imperative languages:

• Statement deletion
• Statement duplication or insertion, e.g. goto fail;[16]
• Replacement of boolean subexpressions with true and false
• Replacement of some arithmetic operations with others, e.g. + with *, - with /
• Replacement of some boolean relations with others, e.g. > with >=, == and <=
• Replacement of variables with others from the same scope (variable types must be compatible)

mutation score = number of mutants killed / total number of mutants

These mutation operators are also called traditional mutation operators. There are also mutation operators for object-oriented languages,[17] for concurrent constructions,[18] complex objects like containers,[19] etc. Operators for containers are called class-level mutation operators. For example, the muJava tool offers various class-level mutation operators such as Access Modifier Change, Type Cast Operator Insertion, and Type Cast Operator Deletion. Mutation operators have also been developed to perform security vulnerability testing of programs [20]

See also

• Bebugging (or fault seeding)
• Sanity testing
• Fault injection

Further reading

• Dasso, Aristides; Funes, Ana (2007). Verification, Validation and Testing in Software Engineering. Idea Group Inc. ISBN 1591408512. See Ch. VII Test-Case Mutation for overview on mutation testing.
• Ammann, Paul; Offutt, Jeff (2008). Introduction to Software Testing. Cambridge University Press. ISBN 978-0-521-88038-1. See Ch. V Syntax Testing for an overview of mutation testing.
• Jia, Yue; Harman, Mark (September 2009). "An Analysis and Survey of the Development of Mutation Testing" (PDF). CREST Centre, King's College London, Technical Report TR-09-06.
• Madeyski, Lech; Radyk, Norbert (2010). "Judy – A Mutation Testing Tool for Java" (PDF). IET Software. pp. 32–42.

References

1. Richard A. DeMillo, Richard J. Lipton, and Fred G. Sayward. Hints on test data selection: Help for the practicing programmer. IEEE Computer, 11(4):34-41. April 1978.
2. Paul Ammann and Jeff Offutt. Introduction to Software Testing. Cambridge University Press, 2008.
3. Smith B., "On Guiding Augmentation of an Automated Test Suite via Mutation Analysis," 2008
4. Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (2016). "Mutation-Based Graph Inference for Fault Localization". doi:10.1109/SCAM.2016.24. Cite journal requires |journal= (help)
5. Mutation 2000: Uniting the Orthogonal by A. Jefferson Offutt and Roland H. Untch.
6. Tim A. Budd, Mutation Analysis of Program Test Data. PhD thesis, Yale University New Haven CT, 1980.
7. Kaksonen, Rauli. A Functional Method for Assessing Protocol Implementation Security (Licentiate thesis). Espoo. 2001.
8. A. Jefferson Offutt. 1992. Investigations of the software testing coupling effect. ACM Trans. Softw. Eng. Methodol. 1, 1 (January 1992), 5-20.
9. A. T. Acree, T. A. Budd, R. A. DeMillo, R. J. Lipton, and F. G. Sayward, "Mutation Analysis," Georgia Institute of Technology, Atlanta, Georgia, Technique Report GIT-ICS-79/08, 1979.
10. Yue Jia; Harman, M., "Constructing Subtle Faults Using Higher Order Mutation Testing," Source Code Analysis and Manipulation, 2008 Eighth IEEE International Working Conference on , vol., no., pp.249,258, 28-29 Sept. 2008
11. Maryam Umar, "An Evaluation of Mutation Operators For Equivalent Mutants," MS Thesis, 2006
12. Polo M. and Piattini M., "Mutation Testing: practical aspects and cost analysis," University of Castilla-La Mancha (Spain), Presentation, 2009
13. Anderson S., "Mutation Testing", the University of Edinburgh, School of Informatics, Presentation, 2011
14. P. G. Frankl, S. N. Weiss, and C. Hu. All-uses versus mutation testing: An experimental comparison of effectiveness. Journal of Systems and Software, 38:235–253, 1997.
15. Overcoming the Equivalent Mutant Problem: A Systematic Literature Review and a Comparative Experiment of Second Order Mutation by L. Madeyski, W. Orzeszyna, R. Torkar, M. Józala. IEEE Transactions on Software Engineering
16. Apple's SSL/TLS bug by Adam Langley.
17. MuJava: An Automated Class Mutation System by Yu-Seung Ma, Jeff Offutt and Yong Rae Kwo.
18. Mutation Operators for Concurrent Java (J2SE 5.0) by Jeremy S. Bradbury, James R. Cordy, Juergen Dingel.
19. Mutation of Java Objects by Roger T. Alexander, James M. Bieman, Sudipto Ghosh, Bixia Ji.
20. Mutation-based Testing of Buffer Overflows, SQL Injections, and Format String Bugs by H. Shahriar and M. Zulkernine.