Lecture
Mutation testing (or mutation analysis, or program mutation ) is used to design new software tests and to evaluate the quality of existing software tests. Mutation testing involves making small changes to a program. Each mutated version is called a mutant, and tests detect and reject mutants by causing the behavior of the original version to differ from that of the mutant. This is called killing the mutant. Test suites are measured by the percentage of mutants they kill. New tests can be designed to kill additional mutants. Mutants are based on well-defined mutation operatorsthat either mimic typical programming errors (for example, using the wrong operator or variable name), or force the creation of valuable tests (for example, dividing every expression by zero). The goal is to help the tester develop effective tests or find weak spots in the test data used for the program, or in parts of the code that are rarely or never exercised at run time . Mutation testing is a kind of white-box testing .
Much of this article is devoted to «program mutation», in which the program itself is modified. A more general definition of mutation analysis is the use of well-defined rules, defined for syntactic structures, to make systematic changes to software artifacts. Mutation analysis has been applied to other tasks, but it is usually applied to testing. Thus, mutation testing is defined as the use of mutation analysis to design new software tests or to evaluate existing software tests. Thus, mutation analysis and testing can be applied to design models, specifications, databases, tests, XML and other types of software artifacts, although program mutations are the most common.
Tests can be created to verify that a given software system has been implemented correctly, but creating tests still raises the question of whether the tests themselves are correct and whether they adequately cover the requirements that motivated the implementation. (This engineering problem is itself an instance of the deeper philosophical problem called « Quis custodiet ipsos custodes? » [«Who will guard the guards themselves?»].) The idea is that if a mutant is introduced without being detected by the test suite, this means either that the changed code was never executed (dead code), or that the test suite failed to detect the errors introduced by the mutant.
For this to work at any scale, a large number of mutants is usually introduced, which leads to compiling and running an extremely large number of copies of the program. This cost problem of mutation testing has reduced its practical use as a software testing method. However, the wider use of object-oriented programming languages and unit-testing frameworks has led to the creation of mutation testing tools that test individual parts of an application.
The goals of mutation testing are numerous:
Mutation testing was originally proposed by Richard Lipton, a student, in 1971 , and was first developed and published by DeMillo, Lipton and Sayward. The first implementation of a mutation testing tool was carried out by Timothy Budd as part of his doctoral work (titled « Mutation Analysis» ) in 1980 at Yale University .
More recently, with the advent of enormous computing power, interest in mutation analysis has been revived within the computer science community, and work has been done to define methods for applying mutation testing to object-oriented programming languages and non-procedural languages such as XML , SMV and finite automata .
In 2004, Certess Inc. (now part of Synopsys ) extended many of these principles to the field of hardware verification. Whereas mutation analysis only involves detecting a difference in the resulting output, Certess extends this by checking whether a checker in the test environment would actually detect the difference. This extension means that all three stages of verification are assessed, namely: activation, propagation and detection. They called this functional qualification.
Fuzzing can be regarded as a special case of mutation testing. In fuzzing, messages or data exchanged within communication interfaces (both within and between instances of software) are mutated in order to reveal crashes or differences in data handling. Codenomicon (2001) and Mu Dynamics (2005) evolved fuzzing concepts into a fully stateful mutation testing platform, complete with monitors for thoroughly testing protocol implementations.
Mutation testing is based on two hypotheses. The first is the competent programmer hypothesis. This hypothesis states that most software errors introduced by experienced programmers result from small syntactic mistakes. The second hypothesis is called the coupling effect . The coupling effect states that simple faults can cascade, or combine, to form other emergent faults.
Subtle and important defects are also revealed by higher-order mutants, which further supports the coupling effect. Higher-order mutants become possible through the creation of mutants with more than one mutation.
Mutation testing is performed by selecting a set of mutation operators and then applying them to the source program one at a time for each applicable fragment of the source code. The result of applying a single mutation operator to a 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 considered to have died .
For example, consider the following C++ code fragment:
if ( a && b ) { c = 1 ; } else { c = 0 ; }
The condition mutation operator will replace &&with ||and produce the following mutant:
if ( a || b ) { c = 1 ; } else { c = 0 ; }
Now, in order to exercise this mutant, the following three conditions must be met:
a = 1and b = 0will do this.These conditions together are called the RIP model .
Weak mutation testing (or weak mutation coverage ) requires that only the first and second conditions hold. Strong mutation testing requires that all three conditions hold. Strong mutation is more effective because it guarantees that the test suite can actually reveal problems. Weak mutation is closely related to code coverage methods . Much less computing power is required to guarantee that a test suite satisfies weak mutation testing than strong mutation testing.
However, there are cases when it is impossible to find a test case that could kill a given mutant. The resulting program is behaviorally equivalent to the original one. Such mutants are called equivalent mutants .
Detecting equivalent mutants is one of the biggest obstacles to the practical use of mutation testing. The effort required to verify the equivalence of mutants can be very high even for small programs. A systematic literature review of a wide range of approaches to the equivalent mutant problem identified 17 relevant methods (in 22 papers) and three categories of methods: detection (DEM); suggestion (SEM); and avoidance of equivalent mutant generation (AEMG). The experiment showed that higher-order mutation in general and the JudyDiffOp strategy in particular provide a promising approach to the equivalent mutant problem.
Many mutation operators have been studied by researchers. Here are a few examples of mutation operators for imperative languages:
goto fail; +with *, -with/>with >=, ==and<=These mutation operators are also called traditional mutation operators. There are also mutation operators for object-oriented languages, for concurrent constructs, for complex objects such as containers, and so on. Operators for containers are called class-level mutation operators . For example, the muJava tool offers various class-level mutation operators, such as changing the access modifier, inserting a type cast operator, and removing a type cast operator. Mutation operators have also been developed for testing programs for vulnerabilities
What metrics does mutation testing give us? It adds three more to code coverage, which we'll talk about now.
But first, let's sort out the terminology.
There is the notion of killed mutants: these are the mutants that our tests have «killed» (that is, they caught them).
There is the notion of an escaped mutant (a surviving mutant). These are mutants that managed to escape punishment (that is, the tests did not catch them).
And there is the notion of a covered mutant — a mutant covered by tests, and its opposite, an uncovered mutant, which is not covered by any test at all (that is, we have code, it has business logic, we can change it, but no test checks these changes).
The main metric that mutation testing gives us — MSI (mutation score indicator), the ratio of the number of killed mutants to their total number.
The second metric — is mutation code coverage. It is precisely a qualitative rather than a quantitative one, because it shows what volume of business logic, which can be broken and this done on a regular basis, our tests catch.
And the last metric — is covered MSI, that is, a softer MSI. In this case we calculate MSI only for those mutants that were covered by tests.
Why have fewer than half of programmers heard of this tool? Why isn't it used everywhere?
The first problem (one of the main ones) — is the execution speed of mutation testing. In the code, if we have dozens of mutation operators, even for the simplest class we can generate hundreds of mutations. Tests will need to be run for each mutation. If we, say, have 5000 unit tests that run for ten minutes, mutation testing can take hours.
What can be done to mitigate this? Run tests in parallel, in several threads. Spread the threads across several machines. This works.
The second way — is incremental runs. There's no need to calculate mutation metrics for the whole branch every time — you can take a branch diff. If you use feature branches, this will be easy to do: run tests only for the files that changed, and see what's currently happening in master, compare, analyze.
The next thing you can do — is tuning the mutations. Since mutation operators can be modified, you can set certain rules by which they work, so you can stop the execution of some mutations if they obviously lead to problems.
An important point: mutation testing is suitable only for unit tests. Although it can also be run for integration tests, this is a deliberately doomed idea, because integration (like end-to-end) tests run much more slowly and touch much more code. You simply will never get results in time. In principle, this mechanism was invented and designed exclusively for unit testing.
The second problem that can arise with mutation tests — is the so-called infinite mutants. For example, there's simple code, a simple for loop:
If you replace i++ with i--, the loop turns into an infinite one. Your code will hang for a long time. And mutation testing quite often generates such mutations.
The first thing you can do — is tuning the mutation. Obviously, changing i++ to i-- in a for loop — is a very bad idea: in 99% of cases we will end up with an infinite loop. That's why we've forbidden doing this in our tool.
The second and main thing that will protect you from such problems — is a timeout for the run. For example, PHPUnit has the ability to terminate a test by timeout regardless of where it got stuck. PHPUnit hangs callbacks via PCNTL and counts the time itself. If a test doesn't complete within a certain period, it simply kills it and such a case is considered a killed mutant, because the code that generated the mutations is indeed checked by a test that indeed catches the problem, indicating that the code has become non-functional.
This problem exists in the theory of mutation testing. In practice it is not encountered very often, but you need to know about it.
Let's consider a classic example illustrating this. We have multiplying variable A by -1 and dividing A by -1. In the general case these operations lead to the same result. We change the sign of A. Accordingly, we have a mutation that allows the two signs to be interchanged. The program's logic is not broken by such a mutation. The tests aren't supposed to catch it, aren't supposed to fail. Because of such identical mutants, certain difficulties arise.
There's no universal solution — everyone solves this problem in their own way. Perhaps some kind of mutant registration system would help. We at Badoo are currently thinking about something like this, we'll be muting them.
Code coverage — is an important metric, it needs to be tracked. But this indicator doesn't guarantee anything: it doesn't say that you're safe.
Mutation testing will help make your unit tests better, and tracking code coverage — more meaningful. There's already a tool for your programming language and IDE, so if you have a small project without complications, go ahead and try it today.
Start by at least running mutation tests manually. Take this simple step and see what it gives you. I'm sure you'll like it
Comments