CS 5154

Mutation Testing

Owolabi Legunsen

The following are modified versions of the publicly-available slides for Chapter 9
in the Ammann and Offutt Book, “Introduction to Software Testing”
([Link]
 Some announcements
• All assigned work so far has been graded
– See scores on CMS
– Daniel (TA): announce office hours for questions/requests on Ed
• The scores so far represent ~35% of your course grade
– ~5 out of 40 percentage points for project
– ~30 out of 50 percentage points for homework
• There is still a LOT more points to work for in the course
– At least 2 more homework (~20%)
– Course project gets in full swing today (~35%)
– Keep working to participate in class and in your group (~10%)
• Past performance is not necessarily a good predictor of
future performance
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 2
 Food for thought…
• You have written test that satisfy “strong” coverage criteria

• But, how do you know how good those tests are in terms
of their fault-detection capability?

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 3

 Applying Syntax-based Testing to
Programs

• Syntax-based criteria originated with programs and have

been used mostly with programs

• BNF criteria are most commonly used to test compilers

• Mutation testing criteria are most commonly used for

unit testing and integration testing of classes

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 4

 Instantiating Grammar-Based
Testing
Grammar-Based Testing

Program-based Integration Model-Based Input-Based

String String String
mutation mutation String
mutation
• Program mutation mutation
• FSMs
Grammar • Valid strings • Input validation
• Model checking
• Mutants are not tests testing
• Valid strings
• Tests must kill mutants • XML and others
• Traces are tests
• Invalid strings
• Compiler testing • No ground strings
• Test how classes interact
• Valid and invalid strings Grammar • Mutants are tests
• Valid strings
• Mutants are not tests • Input validation testing
• Must kill mutants • XML and others
• Includes OO • Valid strings
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 5
 BNF Testing for Compilers

• Testing compilers is very complicated

– Millions of correct programs !
– Compilers must recognize and reject incorrect programs

• BNF criteria can be used to generate programs to test all

language features that compilers must process

• A very specialized application; not discussed in CS5154

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 6

 Some work on compiler testing

• Articles should be available for FREE @ Cornell Library

• Do NOT pay to read these articles
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 7
 Program-based Grammars
• The original and most common application of syntax-based
testing is to modify programs
• Operators modify a ground string (program under test) to
create mutant programs

• Mutant programs must compile correctly (valid strings)

• Mutants are not tests, but used to find or evaluate tests

• Once mutants are defined, tests must be found to cause

mutants to fail when executed
• This is called “killing mutants”

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 8

 Killing Mutants
Given a mutant m  M for a ground string program P
and a test t, t is said to kill m if and only if the output
of t on P is different from the output of t on m.

• 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 mutants are killed

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 9

 Some types of Mutants
• Dead mutant : A test case has killed it

• Stillborn mutant : Syntactically illegal

• Trivial mutant : Almost every test can kill it

• Equivalent mutant : No test can kill it (same behavior as

original)

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 10

 Program-based Grammars
Original Method With Embedded Mutants

int Min (int A, int B) int Min (int A, int B) Replace one variable
{ { with another
int minVal; int minVal;
minVal = A;
minVal = A; Replaces operator
if (B < A) ∆ 1 minVal = B;
if (B < A)
{ Immediate runtime
∆ 2 if (B > A)
minVal = B; failure … if reached
∆ 3 if (B < minVal)
}
{
return (minVal); minVal = B; Immediate runtime
} // end Min ∆4 Bomb (); failure if B==0, else
∆5 minVal = A; does nothing

6 mutants ∆6 minVal = failOnZero (B);

}
Each represents a return (minVal);
separate program } // end Min

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 11

 Syntax-Based Coverage Criteria
Mutation Coverage (MC) : For each m  M,TR contains
exactly one requirement, to kill m.

• The RIPR model from chapter 2:

• 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
• The RIPR model leads to two variants of mutation coverage …

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 12

 Syntax-Based Coverage Criteria

1) Strongly Killing Mutants:

Given a mutant m  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

2) Weakly Killing Mutants:

Given a mutant m  M that modifies a location l in a program P,
and a test t, t is said to weakly kill m if and only if the state of the
execution of P on t is different from the state of the execution of m
on t immediately after l
• Weakly killing satisfies reachability and infection, but not
propagation

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 13

 Weak Mutation
Weak Mutation Coverage (WMC) : For each m  M,TR
contains exactly one requirement, to weakly kill m.

• “Weak mutation” is so named because it is easier to kill mutants

under this assumption

• Weak mutation 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 kill most mutants

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 14

 Weak Mutation In-class Exercise
Mutant 1 in the Min( ) example is:

int Min (int A, int B)

In your breakout room :
{ 1. Find a test that weakly kills the
int minVal;
minVal = A;
mutant, but not strongly
∆ 1 minVal = B; 2. Generalize : What must be true to
if (B < A)
{
weakly kill the mutant, but not
minVal = B; strongly?
}
return (minVal); 3. Try to write down the conditions
} // end Min needed to (i) reach the mutated
statement, (ii) infect the program
state, and (iii) propagate to output

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 15

 Weak Mutation In-class Exercise
minVal = A;
∆ 1 minVal = B;
1. Find a test that weakly kills the
if (B < A) mutant, but not strongly
minVal = B;
A = 5, B = 3
2. Generalize : What must be true to weakly kill the
mutant, but not strongly?
B < A // minVal is set to B for both
3. RIP conditions
Reachability : true // we always reach
Infection : A ≠ B // minVal has a different value
Propagation : (B < A) = false // Take a different branch
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 16
Equivalent Mutation In-class Exercise
Mutant 3 in the Min() example is equivalent:

int Min (int A, int B)

{
With one or two partners
int minVal; 1. Convince yourselves that this
minVal = A;
if (B < A)
mutant is equivalent
∆ 3 if (B < minVal) 2. Briefly explain why
{
minVal = B; 3. Try to prove the equivalence
} Hint : Think about what must be
return (minVal);
} // end Min true to kill the mutant

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 17

Equivalent Mutation In-class Exercise
minVal = A;
if (B < A)
∆ 3 if (B < minVal)

1. Convince yourselves that this mutant is equivalent

2. Briefly explain why
A and minVal have the same value at the
mutated statement
3. Try to prove the equivalence
Hint : Think about what must be true to kill the mutant
Infection : (B < A) != (B < minVal)
Previous statement : minVal = A
Substitute : (B < A) != (B < A)
Contradiction … therefore, equivalent
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 18
 Strong Versus Weak Mutation
1 boolean isEven (int X)
2 { Reachability : X < 0
3 if (X < 0)
4 X = 0 - X; Infection : X != 0
∆4 X = 0;
5 if (double) (X/2) == ((double) X) / 2.0 (X = -6) will kill mutant 4
6 return (true); under weak mutation
7 else
Propagation :
8 return (false);
9 } ((double) ((0-X)/2) == ((double) 0-X) / 2.0)
!= ((double) (0/2) == ((double) 0) / 2.0)
That is, X is not even …
Thus (X = -6) does not kill the mutant under
strong mutation
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 19
 Testing Programs with Mutation
Prog Input test Create Run Generate Run T
method mutants equivalence test cases on P
detector

Run mutants:
Define
threshold • schema-based
Automated
steps • weak
no • selective

Eliminate
Threshold
ineffective
reached ?
TCs

P (T)
Fix no yes
correct
P
?
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 20
Industry is using mutation testing

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 21

 Why Mutation Works
Fundamental Premise of Mutation Testing
If the software contains a fault, there will usually
be a set of mutants that can only be killed by a
test case that also detects that fault
• This is not an absolute !
• The mutants guide the tester to an effective set of tests
• A very challenging problem :
– Find a fault and a set of mutation-adequate tests that do not find
the fault
• Of course, this depends on the mutation operators …

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 22

 Designing Mutation Operators
• At the method level, mutation operators for different
programming languages are similar
• Mutation operators do one of two things :
– Mimic typical programmer mistakes ( incorrect variable name )
– Encourage common test heuristics ( cause expressions to be 0 )
• Researchers design lots of operators, then experimentally
select the most useful
Effective Mutation Operators
If tests that are created specifically to kill mutants
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
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 23
 Mutation Operators for Java
1. ABS –– Absolute Value Insertion
2. AOR –– Arithmetic Operator Replacement
3. ROR –– Relational Operator Replacement
4. COR –– Conditional Operator Replacement
5. SOR –– Shift Operator Replacement
6. LOR –– Logical Operator Replacement
7. ASR –– Assignment Operator Replacement
8. UOI –– Unary Operator Insertion
9. UOD –– Unary Operator Deletion Full
10. SVR –– Scalar Variable Replacement definitions …

11. BSR –– Bomb Statement Replacement

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 24
 Mutation Operators for Java
1. ABS –– Absolute Value Insertion:
Each arithmetic expression (and subexpression) is modified by the functions
abs(), negAbs(), and failOnZero().
Examples:
a = m * (o + p);
∆1 a = abs (m * (o + p));
∆2 a = m * abs ((o + p));
∆3 a = failOnZero (m * (o + p));

2. AOR –– Arithmetic Operator Replacement:

Each occurrence of one of the arithmetic operators +,－,*,／, and % is
replaced by each of the other operators. In addition, each is replaced by the
special mutation operators leftOp, and rightOp.
Examples:
a = m * (o + p);
∆1 a = m + (o + p);
∆2 a = m * (o * p);
∆3 a = m leftOp (o + p);
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 25
 Mutation Operators for Java (2)
3. ROR –– Relational Operator Replacement:
Each occurrence of one of the relational operators (<, ≤, >, ≥, =, ≠) is replaced
by each of the other operators and by falseOp and trueOp.
Examples:
if (X <= Y)
∆1 if (X > Y)
∆2 if (X < Y)
∆3 if (X falseOp Y) // always returns false

4. COR –– Conditional Operator Replacement:

Each occurrence of one of the logical operators (and - &&, or - || , and with no
conditional evaluation - &, or with no conditional evaluation - |, not equivalent
- ^) is replaced by each of the other operators; in addition, each is replaced by
falseOp, trueOp, leftOp, and rightOp.
Examples:
if (X <= Y && a > 0)
∆1 if (X <= Y || a > 0)
∆2 if (X <= Y leftOp a > 0) // returns result of left clause
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 26
 Mutation Operators for Java (4)
5. SOR –– Shift Operator Replacement:
Each occurrence of one of the shift operators <<, >>, and >>> is replaced by
each of the other operators. In addition, each is replaced by the special
mutation operator leftOp.
Examples:
byte b = (byte) 16;
b = b >> 2;
∆1 b = b << 2;
∆2 b = b leftOp 2; // result is b

6. LOR –– Logical Operator Replacement:

Each occurrence of one of the logical operators (bitwise and - &, bitwise or
- |, exclusive or - ^) is replaced by each of the other operators; in addition,
each is replaced by leftOp and rightOp.
Examples:
int a = 60; int b = 13;
int c = a & b;
∆1 int c = a | b;
∆2 int c = a rightOp b; // result is b
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 27
 Mutation Operators for Java (5)
7. ASR –– Assignment Operator Replacement:
Each occurrence of one of the assignment operators (=, +=, -=, *=, /=, %=, &=,
|=, ^=, <<=, >>=, >>>=) is replaced by each of the other operators.
Examples:
a = m * (o + p);
∆1 a += m * (o + p);
∆2 a *= m * (o + p);

8. UOI –– Unary Operator Insertion:

Each unary operator (arithmetic +, arithmetic -, conditional !, logical ~) is
inserted in front of each expression of the correct type.
Examples:
a = m * (o + p);
∆1 a = m * -(o + p);
∆2 a = -(m * (o + p));

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 28

 Mutation Operators for Java (6)
9. UOD –– Unary Operator Deletion:
Each unary operator (arithmetic +, arithmetic -, conditional !, logical~) is
deleted.
Examples:
if !(X <= Y && !Z)
∆1 if (X > Y && !Z)
∆2 if !(X < Y && Z)

10. SVR –– Scalar Variable Replacement:

Each variable reference is replaced by every other variable of the appropriate
type that is declared in the current scope.
Examples:
a = m * (o + p);
∆1 a = o * (o + p);
∆2 a = m * (m + p);
∆3 a = m * (o + o);
∆4 p = m * (o + p);

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 29

 Mutation Operators for Java (7)
11. BSR –– Bomb Statement Replacement:
Each statement is replaced by a special Bomb() function.
Example:
a = m * (o + p);
∆1 Bomb() // Raises exception when reached

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 30

 Summary : Subsuming Other
Criteria
• Mutation is widely considered the strongest test criterion
– And most expensive !
– By far the most test requirements (each mutant)
– Usually the most tests
• Mutation subsumes other criteria by including specific
mutation operators
• Subsumption can only be defined for weak mutation –
other criteria only impose local requirements
– Node coverage, Edge coverage, Clause coverage
– General active clause coverage: Yes–Requirement on single tests
– Correlated active clause coverage: No–Requirement on test pairs
– All-defs data flow coverage
Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 31
 Next
• Demo of a tool that does Mutation Testing

• Project Sprint starts today

– Progress report due in ~3 weeks
– There will be one homework in that time span

• The rest of the course…

Introduction to Software Testing, edition 2 (Ch 9) © Ammann & Offutt 32