The idea: plant a bug and see if the tests notice

Green tests do not prove much on their own. Maybe they would also be green if the code were wrong. Mutation testing checks this directly. A tool makes many copies of the code, each with one small change, such as - turned into +. Each copy is a mutant. Then it runs the whole test suite against every mutant.

The function fare on the left. Arrows go to six mutants M1 to M6, each with one operator changed. Each mutant is run against the suite T1, T2, T3. Results: M1 killed by T1, M2 equivalent, M3 killed by T2, M4 survived, M5 killed by T3, M6 survived. Mutation score 3 killed out of 6 minus 1 equivalent, 3 / 5 = 60%
Six mutants, one suite: three are killed, two survive, one can never be killed.
  • If at least one test fails, the mutant is killed. The tests noticed the change.
  • If every test passes, the mutant survived. A real bug of that kind would get past the tests too.

The code here is fare(from, to), a bus fare: 2 per stop, but never more than 15, which is reached from 8 stops on. The suite starts with three tests. All three pass, and together they run every line. Demo 1: one mutant, killed.

int fare(int from, int to) {
1   int d = to - from;
2   if (d < 0)
3       d = -d;
4   if (d >= 8)
5       return 15;
6   return 2 * d;
}

Mutation operators

A mutation operator is a rule for one kind of small change. The changes copy typical slips a programmer makes. The six mutants on the page:

MutantChangeOperatorWith T1, T2, T3
M1to - from → to + fromarithmetic✓ killed by T1
M2d < 0 → d <= 0boundaryequivalent
M3d = -d → d = dnegation✓ killed by T2
M4d >= 8 → d > 8boundary✗ survived
M5return 15 → return 0return value✓ killed by T3
M62 * d → 2 + darithmetic✗ survived

Each mutant has exactly one change. The idea behind it is the coupling effect: tests that catch every simple slip tend to catch bigger bugs made of several slips too.

Killed or survived: reach, infect, propagate

A test kills a mutant only if four things happen in the same run:

  1. Reach: the test runs the changed line.
  2. Infect: the changed code gives a different value there.
  3. Propagate: the difference reaches the result.
  4. Check: an assertion compares the result with the expected value.
Four stages in a row: reach, infect, propagate, check. Under each, an example that stops there: T3 on M6 returns at line 5 and never reaches line 6; T1 on M6 has d = 2 and 2 + 2 = 2 × 2 = 4; d = 0 on M2 flips the if but d = -0 = 0; T5 on M6 returns 5 instead of 6, the test fails and the mutant is killed
Each survivor stops at one of the stages; a kill needs all four.

Demo 2: a survivor at 100% line coverage runs M4. Every test reaches line 4. T1 and T2 reach it with d = 2, where d >= 8 and d > 8 are both false. T3 has d = 20, where both are true. No test has d = 8, the one value where they differ. M6 survives by coincidence: T1 and T2 both have d = 2, and 2 + 2 happens to equal 2 × 2.

Mutation score versus line coverage

The mutation score is the share of mutants the suite kills:

mutation score = killed / (mutants − equivalent mutants)

For T1, T2, T3 it is 3 / (6 − 1) = 60%, while line coverage is 6/6 = 100% (Demo 3: whole suite, score 60%). Coverage says which lines ran. The score says whether the tests would have noticed if those lines were wrong.

The clearest case is a test without an assertion. Demo 7: no assertions: 100% lines, 0% keeps the same three calls but checks nothing. Every line still runs, and not one mutant is killed.

Bars for four suites. Line coverage is 100% for all of them. Mutation score: T1 to T3 without asserts 0%, T1 to T3 60%, T1 to T4 80%, T1 to T5 100%
Line coverage stays at 100% while the mutation score goes 0%, 60%, 80%, 100%.

Equivalent mutants

M2 changes d < 0 to d <= 0. The two only disagree when d = 0. Then the mutant runs line 3, d = -d, and minus zero is zero. The result is the same for every input, so no test can ever kill M2. It is an equivalent mutant. Demo 4: an equivalent mutant.

Deciding whether a mutant is equivalent cannot be done by a program in general, so a person has to look at each survivor. Equivalent mutants are left out of the score; counting M2 would make the best possible score 5/6 = 83%.

Turning a survivor into a test

A survivor points at the test that is missing:

SurvivorWhy it livedNew testMutant gives
M4 d > 8no test at the boundary d = 8T4: fare(0, 8), expect 1516 ✗ killed
M6 2 + devery short trip had d = 2T5: fare(1, 4), expect 65 ✗ killed

Demo 5: add the boundary test, 80% adds T4 and the score goes to 4/5. Demo 6: kill the last survivor, 100% adds T5 and reaches 5/5. T4 is just the test that boundary value analysis would ask for; see Boundary Value Testing for how to pick such inputs.

Tools and cost

PIT (PITest) does this for Java, Stryker for JavaScript, C# and Scala, and mutmut for Python. PIT calls the operators here Math, Conditionals Boundary, Invert Negatives and Primitive Returns. A mutant that crashes or runs too long also counts as killed.

The cost is the problem: every mutant runs the suite again. A thousand mutants and a one-minute suite would take 17 hours. Tools cut this down. They run only the tests that cover the changed line, stop at the first failing test (as the page does), and run in parallel.

See also Control-Flow Coverage for statement, branch and path coverage, the numbers a mutation score goes beyond, and Test Doubles for what a unit test asserts and how it isolates the code under test.

See also Condition Coverage and MC/DC for choosing tests so that each condition of a decision is shown to matter on its own.

What the page leaves out

Higher-order mutants (several changes at once), the full operator sets (for example Offutt's operators for Java), mutants that crash or loop and are killed by a timeout, weak versus strong mutation, test selection and incremental analysis in real tools, mutation of the tests themselves, and condition coverage or MC/DC for compound conditions are left out.

On the mind map

Open the Software Design mind mapSoftware DesignPrinciples: keep each change localPrinciplesDesign patterns: named fixes for common designsDesign patternsArchitecture: the shape of a whole appArchitectureEnterprise app patterns: logic, SQL, locks, money (PoEAA)Enterprise app patternsGit storage: content named by its hashGit storageGit branches & merging: pointers to commits, then mergeGit branches & mergingTesting: check code in isolationTestingSOLIDSOLIDfive rules so one change hits one classInheritance vs compositionInheritance vs compositionis-a locks the tree; has-a mixes partsVirtual calls, vtableVirtual calls, vtableobject → vptr → vtable slot → functionOverloading vs overridingOverloading vs overridingjavac: static types; JVM: receiver's classCoupling and cohesionCoupling and cohesionOne change should touch one moduleControl-flow coverageControl-flow coverage100% statements can still miss a bugBoundary Value TestingBoundary Value TestingBugs sit at class edges: test min−1 … max+1Condition Coverage and MC/DCCondition Coverage and MC/DCEach condition flips D alone: N+1 testsMutation testingCoverage runs code; mutants test the assertsOpen the Software Design mind mapSoftware Designkeep each change localPrinciplesSOLIDSOLIDfive rules so one change hits one classInheritance vs compositionInheritance vs compositionis-a locks the tree; has-a mixes partsVirtual calls, vtableVirtual calls, vtableobject → vptr → vtable slot → functionOverloading vs overridingOverloading vs overridingjavac: static types; JVM: receiver's classCoupling and cohesionCoupling and cohesionOne change should touch one moduleControl-flow coverageControl-flow coverage100% statements can still miss a bugBoundary Value TestingBoundary Value TestingBugs sit at class edges: test min−1 … max+1Condition Coverage and MC/DCCondition Coverage and MC/DCEach condition flips D alone: N+1 testsMutation testingCoverage runs code; mutants test the asserts
This page on the Software Design mind map · 38 pages in 7 branches · open it to see the whole map and test yourself in recall mode.