Mutation testing

For the biological term, see: Gene mutation analysis.

Software Testing portal

Mutation testing (or Mutation analysis or Program mutation) is a method of software testing, which involves modifying programs' source code or byte code in small ways.^[1] A test suite that does not detect and reject the mutated code is considered defective. These so-called mutations, 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 driving each expression to 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.

Aim

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?"].) In this context, mutation testing was pioneered in the 1970s to locate and expose weaknesses in test suites. The theory was that if a mutation was introduced without the behavior (generally output) of the program being affected, this indicated either that the code that had been mutated was never executed (redundant code) or that the testing suite was unable to locate the injected fault. In order for this to function at any scale, a large number of mutations had to be introduced into a large program, 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, but the increased use of object oriented programming languages and unit testing frameworks has led to the creation of mutation testing tools for many programming languages as a means to test individual portions of an application.

Historical overview

Mutation testing was originally proposed by Richard Lipton as a student in 1971,^[2] and first developed and published by DeMillo, Lipton and Sayward. 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.

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. 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 have called this functional qualification.

Fuzzing is a special area of mutation testing. In fuzzing, the messages or data exchanged inside communication interfaces (both inside and between software instances) are mutated, in order to catch failures or differences in processing the data. Codenomicon^[3] (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 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 condition should be met:

• Test input data should cause different program states for the mutant and the original program. For example, a test with a = 1 and b = 0 would do this.
• The value of 'c' should be propagated to the program's output and checked by the test.

Weak mutation testing (or weak mutation coverage) requires that only the first condition is satisfied. Strong mutation testing requires that both 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.

Equivalent mutants

Many mutation operators can produce equivalent mutants. For example, consider the following code fragment:

int index = 0;
 
while (…)
{
    …; 
    index++;
 
    if (index == 10) {
        break;
    }
}

Boolean relation mutation operator will replace == with >= and produce the following mutant:

int index = 0;
 
while (…)
{
    …; 
    index++;
 
    if (index >= 10) {
        break;
    }
}

However, it is not possible to find a test case that could kill this mutant. The resulting program is 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.^[4]

Mutation operators

A variety of mutation operators were explored by researchers. Here are some examples of mutation operators for imperative languages:

• Statement deletion.
• Replace each boolean subexpression with true and false.
• Replace each arithmetic operation with another one, e.g. + with *, - and /.
• Replace each boolean relation with another one, e.g. > with >=, == and <=.
• Replace each variable with another variable declared in the same scope (variable types should be the same).

These mutation operators are also called traditional mutation operators. Beside this, there are mutation operators for object-oriented languages^[5] , for concurrent constructions^[6], complex objects like containers^[7] etc. They 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, Type Cast Operator Deletion. Moreover, mutation operators have been developed to perform security vulnerability testing of programs ^[8]

References

1. ^ A Practical System for Mutation Testing: Help for the Common Programmer by A. Jefferson Offutt.
2. ^ Mutation 2000: Uniting the Orthogonal by A. Jefferson Offutt and Roland H. Untch.
3. ^ Kaksonen, Rauli. A Functional Method for Assessing Protocol Implementation Security (Licentiate thesis). Espoo. 2001.
4. ^ 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.
5. ^ MuJava: An Automated Class Mutation System by Yu-Seung Ma, Jeff Offutt and Yong Rae Kwo.
6. ^ Mutation Operators for Concurrent Java (J2SE 5.0) by Jeremy S. Bradbury, James R. Cordy, Juergen Dingel.
7. ^ Mutation of Java Objects by Roger T. Alexander, James M. Bieman, Sudipto Ghosh, Bixia Ji.
8. ^ Mutation-based Testing of Buffer Overflows, SQL Injections, and Format String Bugs by H. Shahriar and M. Zulkernine.

Further reading

• Aristides Dasso, Ana Funes (2007). Verification, Validation and Testing in Software Engineering. Idea Group Inc. ISBN 1591408512.  See Ch. VII Test-Case Mutation for overview on mutation testing.
• Paul Ammann, Jeff Offutt (2008). Introduction to Software Testing. Cambridge University Press. ISBN 0-52188-038-1.  See Ch. V Syntax Testing for an overview of mutation testing.
• Yue Jia, Mark Harman (September 2009). "An Analysis and Survey of the Development of Mutation Testing" (PDF). CREST Centre, King's College London, Technical Report TR-09-06. http://www.dcs.kcl.ac.uk/pg/jiayue/repository/TR-09-06.pdf. 

See also

• Bebugging (or fault seeding)
• Sanity testing

External links

• Mutation testing list of tools and publications by Jeff Offutt.
• Mutation Testing Repository A publication repository that aims to provide a full coverage of the publications in the literature on Mutation Testing.
• Bacterio Mutation testing tool for multi-class Java systems.
• Jumble Bytecode based mutation testing tool for Java
• PIT Bytecode based mutation testing tool for Java
• Jester Source based mutation testing tool for Java
• Heckle Mutation testing tool for Ruby
• Nester Mutation testing tool for C#
• Mutagenesis Mutation testing tool for PHP