09 Mutation Testing - skylerto/Software-Testing GitHub Wiki
Mutation Testing
What is Mutation Testing?
Mutation Testing is a testing technique that focuses on measuring the adequacy of test cases
Mutation Testing is NOT a testing strategy like Boundary Value or Data Flow Testing. It does not outline test data selection criteria
Mutation Testing should be used in conjunction with traditional testing techniques, not instead of them
Goal:
Mimic (and hence test for) typical mistakes
Encode knowledge about specific kinds of effective tests in practice
Mutation Testing
Faults are introduced into the program by creating many versions of the program called mutants
Each mutant contains a single fault
Test cases are applied to the original program
and to the mutant program
The goal is to cause the mutant program to fail, thus demonstrating the effectiveness of the test suite
Test Case Adequacy
A test case is adequate if it is useful in detecting faults in a program.
A test case can be shown to be adequate by finding at least one mutant program that generates a different output than does the original program for that test case.
If the original program and all mutant programs generate the same output, the test case is inadequate.
Mutant Programs
Mutation testing involves the creation of a set of mutant programs of the program being tested
Each mutant differs from the original program by one mutation
A mutation is a single syntactic change that is made to a program statement
Mutation Operators
Operand Replacement Operators:
Replace a single operand with another operand or constant. E.g.,
if (5 > y) - if(x>5) - if (y > x)
Replacing y by constant 5. Replacingxbyy.
Replacing x and y with each other.
E.g., if all operators are {+,-,*,**,/} then the following expression a = b * (c - d) will generate 8 mutants:
4 by replacing * - 4 by replacing -.
Expression Modification Operators:
Replace an operator or insert new operators. E.g.,
if(x==y)
if (x >= y) Replacing == by >=. - if (x == ++y) Inserting ++.
Statement Modification Operators:
Delete the else part of an if-else statement. - Delete the entire if-else statement.
Replace line 3 by a return statement.
The Mothra mutation system (A Fortran Language System for Mutation-Based Software Testing by Offutt et al. 1987) for FORTRAN77 supports 22 mutation operators
Absolute value insertion
Constant for array reference replacement - GOTO label replacement
Statement deletion
Unary operator insertion
Logical connector replacement
Why Does Mutation Testing Work?
The operators are limited to simple single syntactic changes on the basis of the competent programmer hypothesis
The Competent Programmer Hypothesis
Programmers are generally very competent and
do not create “random” programs.
For a given problem, a programmer, if mistaken, will create a program that is very close to a correct program.
An incorrect program can be created from a correct program by making some minor change to the correct program.
Mutation Testing Costs
The FORTRAN 77 version of the max() program generated 44 mutants using Mothra.
Most efforts on mutation testing have focused on reducing its cost by reducing the number of mutants while maintaining the effectiveness of the technique.
Mutation Testing Algorithm
Generate program test cases
Run each test case against the original program
If the output is incorrect, the program must be modified and re- tested
If the output is correct go to the next step ...
Construct mutants using a mutation testing tool
Execute each test case against each alive mutant
If the output of the mutant differs from the output of the original
program, the mutant is considered incorrect and is killed - “Good test cases kill the mutants"
Once we find a test case that kills a mutant, we can forget the mutant and keep the test case. The mutant is dead
Two kinds of mutants survive:
Functionally equivalent to the original program: Cannot be
killed
Killable: Test cases are insufficient to kill the mutant. New test cases must be created.
Some mutants can be uninteresting
Three kinds of mutants are uninteresting: - Stillborn: such mutants cannot compile (or
immediately crash)
Trivial: killed by almost any test case;
Equivalent: indistinguishable from original program
Mutation Coverage Criteria
Mutation Coverage (MC)
For each mutant m, test requirements (TR) contain a requirement to “kill m”
Mutation score is the percentage of mutants killed
The mutation score for a set of test cases is the percentage of non-equivalent mutants killed by the test data
Mutation Score = 100 * D / (N - E) - D: Dead mutants
N: Number of mutants
E: Number of equivalent mutants
A set of test cases is mutation adequate if its mutation score is 100%.
Strong and weak mutation
Strong mutation: a fault must be reachable, infect the state, and propagate to output
Weak mutation: a fault which kills a mutant need only be reachable and infect the state
Experiments show that weak and strong mutation require almost the same number of test cases to satisfy them
Strong mutation coverage (SMC)
Strongly killing mutants
Given a mutant m for a program P and a test case t, t is said to strongly kill m iff the output of t on P is different from the output of t on m
Strong mutation coverage (SMC)
For each mutant m in M, the test requirements (TR) contains a test case which strongly kills m
Weak mutation coverage
Weakly killing mutants
Given a mutant m that modifies a source location L in program P and a test case t, t is said to weakly kill m iff the state of the execution of P on t is different from the state of the execution of m on t, immediately after some execution of L
Weak mutation coverage (WMC)
For each mutant m in M, TR contains a test case which weakly kills m
Evaluation
Theoretical and experimental results have shown that mutation testing is an effective approach to measuring the adequacy of test cases.
The major drawback of mutation testing is the cost of generating the mutants and executing each test case against them.
