Mutation Testing

Created Feb 27, 2023

Mutation analysis, mutation testing

Mutation

A mutation is a small modification to a piece of code

The term is inspired by "biological mutation"
done by applying mutation operators

A mutation operator is a rule that specifies a valid syntactic modification

A mutant is the modified (i.e., mutated) code after applying a mutation operator.

Example:

// original code 
int index = 0; while(true) {
	index++;
    // control flow branching
    if (index == 10)
          break;
}

// mutated code
int index = 0;
while (true) { 
	index++;
	// mutating
	if (index <= 10)
		break;
}

Mutation Testing

Mutating a piece of code to generate a set of mutants
"Kill" all the (or as many as possible) mutants.

Mutation Testing: Assume $M$ is the set of all mutants for a given piece of code $P$ . Test $t$ is said to "kill" $m \in M$ if and only if the output of $t$ on $P$ is different from the output of $t$ on $m$ .

Example:

// Program P
int min (int a, int b) {
	if (a < b) {
		return a;
	}
	return b;
}

// Mutant m
int min (int a, int b) {
	if (a > b) {
		return a;
	} 
	return b;
}

In test t1: a = 10, b = 12 kills m
In test t2: a = 10, b = 10 does not kill m

The number of test requirements for mutation depends on two things:

the syntax of the artifact being mutated
the mutation operators

Mutation testing is difficult to apply by hand, is effective ("gold standard" of testing), and is often used to evaluate other crtierias.

Help the test engineer to strengthen the quality of the tests

At least one test case in the test suite to kill mutant $m$

Designing effective mutation operators is the key.

Mutation Operators are designed to:

mimic typical programmer mistakes
encourage the test engineer to write fault-revealing tests

Coupling effective. The mutation testing premise is that:

"Test data that distinguishes all programs differing from a correct one by only simple errors is so sensitive that it also implicitly distinguishes more complex errors.”

If mutation operators are designed well, the resulting tests will be very powerful

Different operators must be defined for different programming languages and different goals.

Testers can keep adding tests until all the mutanta have been killed. Some terms:

Dead mutant: a test case has killed it
Stillborn mutant: syntatically illegal
Trivial mutant: almost every test can kill it
Equivalent mutant: no test case can kill it (same behavior as original)
- This is a mutant that is functionally equivalent to the orignal code. Thus, no test case can kill an equivalent mutant -> infeasible test requirement
- In general, an undecidable problem to identify an equivalent mutant.

Example for equivalent mutant:

// # original code
int index = 0;

while(true) {
	index++;
    // control flow branching
    if (index == 10)
          break;
}

// # an equivalent mutant

int index = 0;

while (true) {
	index++;
	// mutating
   if (index >= 10)
        break;
}

RIPR Model

The RIPR model discussed earlier in class:

Reachability: the test causes the faulty statement to be reached (in mutation - the mutated statement)
Infection: the test causes the faulty statement to result in an incorrect state
Propagation: the incorrect state propagates to incorrect output
Revealability: the tester must observe part of the incorrect output.

This leads to two variants of muation coverage.

Mutation Coverage

Mutation Coverage (MC): for each $m \in M$ , $TR$ contains exactly one requirement, to kill $m$ .

Coverage in mutation equates to number of mutants killed MC level is also called mutation score, which is: (number of mutants killed)/(total number of mutants).

Mutation Operator Coverage (MOC): for each mutant operator, $TR$ contains exactly one requirement, to create a mutant that is derived using the mutant operator.

RIPR model has two variants of mutation coverage

Strongly killing mutants: given a mutant $m \in M$ for a program $P$ and a test $t$ , $t$ is said to strongly kill $m$ if and only if the output of $t$ on $P$ is different from the output of $t$ on $m$ .
Weakly killling mutants: given a mutant $m \in M$ $m \in M$ that modifies a location $l$ $l$ in a program $P$ $P$ , and a test $t$ $t$ , $t$ $t$ is said to weakly kill $m$ $m$ if and only if the state of the execution of $P$ $P$ on $t$ $t$ is different from the state of the execution of $m$ $m$ on $t$ $t$ immediately after $l$ $l$ .
1. Weakly killing satisfies reachability and infection, but not propagation.

Strong Mutation Coverage (SMC): for each $m \in M$ , $TR$ contains one requirement: to strongly kill $m$ .

Weak Mutation Coverage (WMC): for each $m \in M$ , $TR$ contains exactly one requirement, to weakly kill $m$ .

Named "weak mutation" because it is easier to kill mutants under this assumption (also requires less analysis)
A few mutants can be killed under weak mutation but not under strong mutation (no propagation)

"studies have found that test sets that weakly kill all mutants also strongly kills most mutants".

Compare these two:

int gcd (int x, int y) {
	int tmp;
	while (y != 0) {
		tmp = x % y; // weak mutation
		x = y;
		y = tmp;
	}
	return x; // strong mutation here
}

int gcd (int x, int y) {
	int tmp;
	while (y != 0) {
		tmp = x * y; // weak mutation (operator!)
		x = y;
		y = tmp;
	}
	return x; // strong mutation here
}

Mutation Operators

Some mutation operators for java:

ABS: Absolute Value Insertion - each arithmetic expression (and subexpression) is modified by the functions abs(), negAbs(), and failOnZero().

a = m * (o + p);
a =  abs(m * (o + p)); // ∆1
a = m * abs ((o + p)); // ∆2
a = failOnZerl(m * (o + 0)); // ∆3

ROR: Relational Order Replacement

each occurence of the relational operators is replaced by each of the other operators by falseOp and trueOp

if (x <= y)
if (x > y) // ∆1
if (x < y) // ∆2
if (x falseOp y) // ∆3, always returns false

LOR: Logical Operator Replacement

each occurence of the logical operators is replaced by each of the other operators. In addition, each is replaced by falseOp, trueOp, leftOp, rightOp.

if (x <= y && a > 0)
if (x <= y || a > 0) // ∆1
if (x <= y leftOp a > 0) // ∆2. returns result of left clause

SOR: shift operator replacement

each occurence of one of the shift operators is replaced by each of the other operators. In addition, each is replaced by the special mutation operator leftOp.

byte b = (byte) 16;

b = b >> 2;
b = b << 2;  // ∆1
b = b leftOp 2; // ∆2, result is b

BOR: Bitwise Operator Replacement

Each occurrence of one of the bitwise operators is replaced by each of the other operators. In addition, each is replaced by leftOp and rightOp.

int a = 60;
int b = 13;

int c = a & b;
int c = a | b; // ∆1 
int c = a rightOp b; // ∆2, result is b

ASR: Assignment Operator Replacement

each occurence of one of the assignment operators is replaced by each of the other operators

a = m * (o + p)
a += m * (o + p); // ∆1
a *= m * (o + p); // ∆2

UOI: Unary Operator Insertion:

each unary operator is inserted in front of each espression of the correct type

a = m * (o + p);
a = m * -(o + p); // ∆1 
a = -(m * (o + p)); // ∆2

UOD: Unary Operator Deletion

each unary operator is deleted

if !(X <= Y && !Z)
if (X > Y && !Z) // ∆1 
if !(X < Y && Z) // ∆2

SVR: Scalar Variable Replacement

Each variable reference is replaced by every other variable of the appropriate type that is declared in the current scope.

a = m * (o + p);
a = o * (o + p);  // ∆1
a = m * (m + p);  // ∆2
a = m * (o + o);  // ∆3
p = m * (o + p);  // ∆4

BSR: Bomb Statement Replacement

Each statement is replaced by a special Bomb() function.

a = m * (o + p);
Bomb() // ∆1, Raises exception when reached

Ways to Improve Mutation Testing Efficiency

Should more than one mutation operator be applied at the same time to produce a mutant?

Should we try each and every possible mutation operator on any program

To improve:

parallelize
mutate bytecode instead of source code (no need to recompile)
selective mutation
- only a subset of mutation operators
strong vs weak killing
- use weak killing

Mutation testing is expensive (lots of mutants):

sample from the set of all mutants
selectively use mutation operators that are (more) effective.

If tests that are created to kill mutants produced by mutation operator $o_1$ also kill mutants produced by mutation operator $o_2$ , we say that $o_1$ is more effective than $o_2$ .

Effective Mutation Operators: if tests that are created specifically to kill mutant created by a collection of mutation operators $O = {o1, o2, ...}$ also kill mutants created by all remaining mutation operators with very high probability, then $O$ defines an effective set of mutation operators.

Researchers have concluded that the collection of operators that insert unary operators and that modify unary and binary operators are effective.

Integration Mutation Testing

Integration Testing: Testing multiple units together. Specifically, testing connections among units.

In Java, testing the way classes, packages, and modules are connected. For example, which methods of class A calls which methods of class B and vice versa.

Integration testing is often based on the existing couplings – the explicit and implicit relationships among software components

Faults related to integrations often depend on a mismatch of assumptions

Callee thought a list was sorted, caller did not
Callee thought all fields were initialized, caller only initialized some of the fields
Caller sent values in kilometers, callee thought they were miles
etc.

Integration Mutation Operators: In general, there are four kinds:

change a calling method by modifying values that are sent to a called method
change a calling method by modifying the call change a called method by modifying values that enter and leave a method
- includes parameters as well as variables from higher scopes (class level, package, public, etc.)
change a called method by modifying return statements from the method

IPVR: Integration Parameter Variable Replacement

Each parameter in a method call is replaced by each other variable in the scope of the method call that is of compatible type

int a, b;
callMethod(a);
callMethod(b); // ∆

IPEX: Integration Parameter Exchange

Each parameter in a method call is exchanged with each parameter of compatible types in that method call

max (a, b);
max (b, a);  // ∆

IUOI: Integration Unary Operator insertion

Each expression in a method call is modified by inserting all possible unary operators in front and behind it

callMethod (a);

callMethod (a++);  // ∆
callMethod (++a);  // ∆
callMethod (a--);  // ∆
callMethod (--a);  // ∆

IMCD: Integration Method Call Deletion

Each method call is deleted. If the method returns a value and it is used in an expression, the method call is replaced with an appropriate constant value

Max (a, b);  
X = new Integer (0);  // ∆

IREM: Integration Return Expression Modification Each expression in each return statement in a method is modified by applying the UOI and AOR operators

int myMethod () { 
	return a + b; 
	return ++a + b; // ∆
	return a – b;   // ∆
}

Object-Oriented Mutation

eSo far, we only mutated method bodies. Class level mutation operators can be utilized too.

public class test {
	// ...
	protected void do() {
		// ...
	}
}

public class test {
	// ...
	public void do() { // emphasis on public!
		// ...
	}
}

There's a lot of objected-oriented mutation operators.

Summary

Mutation testing is

widely considered the strongest test criterion
a high-end type of testing i.e., more effective, also more expensive, i.e., by far the most test requirements
- It's expensive to: generate mutants + recompilations + running all test cases of the test suite on each generated mutant
Mutation Analysis is assessing the quality of a test suite
Mutation Testing is used to improve the test suite quality by leveraging mutation analysis
Can be applied to any syntax, hence aka syntax-based testing:
- have been applied to formal specification languages such as SVM
- have been applied to markup languages such as XML, HTML etc

Tools to use:

Java : muJava, PIT, Javalanche, etc.
Javascript : Stryker Mutator, etc.
C++: MuCPP, Mutate++, etc.
Python: Cosmic Ray, mutmut, etc.
Ruby: Heckle
PHP: Infection PHP, Humbug
C#: Nester, VisualMutator

Linked from Software Testing and Debugging