Software Engineering
Testing
Mutation Testing, Differential Testing, Metamorphic Testing, Intramorphic Testing
CUHK Shenzhen
Pinjia He
1. Mutation Testing
2. Differential Testing
3. Metamorphic Testing
4. Intramorphic Testing
5. Retromorphic Testing
6. Examples
Pinjia He @ CUHK Shenzhen
Mutation Testing
• Coverage metric
• How good the test cases are?
• How many bugs detected?
Pinjia He @ CUHK Shenzhen
Mutation Testing
• How about we inject some faults?
Pinjia He @ CUHK Shenzhen
Mutation Testing
5
Killing a Mutant
6
How to calculate coverage then?
Pinjia He @ CUHK Shenzhen
Why Mutation Testing?
8
Example
9
Equivalent Mutant Example
10
Mutation Coverage Criteria
11
Strong versus Weak Mutants
12
Strong versus Weak Mutants
13
Testing Program with Mutation
14
Designing Mutation Operators
15
Mutation Operators
16
Mutation Operators
17
Mutation Operators
18
Mutation Operators
19
Mutation Operators
20
Mutation Operators
21
Subsumption of Other Criteria
22
1. Mutation Testing
2. Differential Testing
3. Metamorphic Testing
4. Intramorphic Testing
5. Retromorphic Testing
6. Examples
Pinjia He @ CUHK Shenzhen
Motivating Example
Is this program
correct?
def bubble_sort(arr):
length = len(arr)
for i in range(length):
for j in range(0, length - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[i]
Motivating Example
Is this program
correct?
def bubble_sort(arr):
length = len(arr)
for i in range(length):
for j in range(0, length - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[i]
Unit Testing
Let’s write a unit test!
arr = [3, 1, 2]
bubble_sort(arr)
assert arr == [1, 2, 3]
Unit Testing
Let’s write a unit test!
arr = [3, 1, 2]
bubble_sort(arr)
assert arr == [1, 2, 3]
AssertionError: [1, 2, 1]
Unit Testing
Can we automate the
testing process?
arr = [3, 1, 2]
bubble_sort(arr)
assert arr == [1, 2, 3]
Automated Testing Challenges
Test Case Test Oracle
Test Oracle
Incorrect result!
“a test oracle (or just oracle) is a mechanism for
determining whether a test has passed or failed”
Automated Testing
Can we automate the
testing process?
Test Case
arr = [3, 1, 2]
bubble_sort(arr)
assert arr == [1, 2, 3]
Automated Testing
Can we automate the
testing process?
arr = [3, 1, 2]
bubble_sort(arr)
assert arr == [1, 2, 3] Test Oracle
Test Oracle Problem
33
Non-Testable Programs
34
Non-Testable Programs
Machine Translation Service:
Structure-Invariant Testing for Machine Translation. He et al., International
Conference on Software Engineering, 2020.
Database System:
Finding Bugs in Database Systems via Query Partitioning. Rigger et al.,
International Conference on Object-Oriented Programming Systems,
Languages, and Applications, 2020.
SMT Solver:
Validating SMT Solvers via Semantic Fusion. Winterer et al., International
Conference on Programming Language Design and Implementation, 2020.
Compiler:
Compiler Validation via Equivalence Modulo Inputs. Le et al., International
Conference on Programming Language Design and Implementation, 2014.
35
P O
Differential Testing I
P' O''
Modified program
Differential Testing Metam
P1 O1
I
Oracle
I P2 O2 for each
other
P3 O3 I'
Interchangeable programs: P1(I) = P2(I) = P3(I) Derived follow
Differential Testing
Many sorting algorithms and
implementations exist, so we can validate
that they produce the same results
Differential Testing
bubble_sort [1, 2, 3]
Oracle
[3, 1, 2] merge_sort [1, 2, 3] for each
other
insertion_sort [1, 2, 3]
Interchangeable programs: P 1(I) = P2(I) = P3(I)
Differential testing is a black-box technique that works
well when systems implement the same behavior
Differential Testing
sorting_algorithms = [bubble_sort, merge_sort, insertion_sort]
while True:
arr = get_random_array() # e.g., [3, 1, 2]
sorted_arrays = [alg(arr) for alg in sorting_algorithms]
all_same = all(sorted_arr == sorted_arrays[0]
for sorted_arr in sorted_arrays)
assert all_same
Differential Testing
sorting_algorithms = [bubble_sort, merge_sort, insertion_sort]
while True:
arr = get_random_array() # e.g., [3, 1, 2]
sorted_arrays = [alg(arr) for alg in sorting_algorithms]
all_same = all(sorted_arr == sorted_arrays[0]
for sorted_arr in sorted_arrays)
assert all_same
Differential Testing
sorting_algorithms = [bubble_sort, merge_sort, insertion_sort]
while True:
arr = get_random_array() # e.g., [3, 1, 2]
sorted_arrays = [alg(arr) for alg in sorting_algorithms]
all_same = all(sorted_arr == sorted_arrays[0]
for sorted_arr in sorted_arrays)
assert all_same
Differential Testing
sorting_algorithms = [bubble_sort, merge_sort, insertion_sort]
while True:
arr = get_random_array() # e.g., [3, 1, 2]
sorted_arrays = [alg(arr) for alg in sorting_algorithms]
all_same = all(sorted_arr == sorted_arrays[0]
for sorted_arr in sorted_arrays)
assert all_same
Differential Testing
sorting_algorithms = [bubble_sort, merge_sort, insertion_sort]
while True:
arr = get_random_array() # e.g., [3, 1, 2]
sorted_arrays = [alg(arr) for alg in sorting_algorithms]
all_same = all(sorted_arr == sorted_arrays[0]
for sorted_arr in sorted_arrays)
assert all_same
AssertionError: [[1, 2, 1], [1, 2, 3], [1, 2, 3]]
Differential Testing Applications
• C/C++ compilers [Yang et al., PLDI 2011]
• Java Virtual Machines (JVMs) [Chen et al., PLDI 2016 and
ICSE 2019]
• Database Engines [Slutz, VLDB 1998]
• Debuggers [Lehmann et al., ESEC/FSE 2018]
• Code coverage tools [Yang et al., ICSE 2019]
• SMT solvers [Winterer, Zhang, et al., OOPSLA 2020]
• Object Relational Mappers (ORMs) [Sotiropoulos et al.,
ICSE 2021]
• …
1. Mutation Testing
2. Differential Testing
3. Metamorphic Testing
4. Intramorphic Testing
5. Retromorphic Testing
6. Examples
Pinjia He @ CUHK Shenzhen
Metamorphic Testing
Metamorphic Testing
I O
Oracle
P for each
other
I' O'
Derived follow-up input
Test Oracle Problem
47
Test Oracle Problem: Example
48
Test Oracle Problem: Example
49
Metamorphic Testing
50
Metamorphic Testing
The relative order of sorted elements is
maintained when an element is removed
from an input array
Metamorphic Testing
Sort Remove 2
[3, 1, 2] [1, 2, 3] [1, 3]
Oracles
For each
Remove 2 Sort other
[3, 1, 2] [3, 1] [1, 3]
Metamorphic Testing
while True:
arr = get_random_array()
if len(arr) >= 1:
sorted_arr = bubble_sort(arr)
random_elem = random.choice(sorted_arr)
arr.remove(random_elem)
sorted_smaller_arr = bubble_sort(arr)
sorted_arr.remove(random_elem)
assert sorted_arr == sorted_smaller_arr
Metamorphic Testing
while True:
arr = get_random_array()
if len(arr) >= 1:
sorted_arr = bubble_sort(arr)
random_elem = random.choice(sorted_arr)
arr.remove(random_elem)
sorted_smaller_arr = bubble_sort(arr)
sorted_arr.remove(random_elem)
assert sorted_arr == sorted_smaller_arr
AssertionError: [2, 1] [2, 3]
Metamorphic Testing
Metamorphic Testing Applications
• Compilers [Le et al., PLDI 2014]
• Database engines [Rigger et al., ESEC/FSE 2020 and OOPSLA
2020]
• SMT solvers [Winterer, Zhang, et al., PLDI 2020]
• Android apps [Su et al., OOPSLA 2021]
• Object detection systems [Wang et al., ASE 2020]
• …
1. Mutation Testing
2. Differential Testing
3. Metamorphic Testing
4. Intramorphic Testing
5. Retromorphic Testing
6. Examples
Pinjia He @ CUHK Shenzhen
Problem: No Whitebox Technique
Intramorphic Testing
?
P O
Oracle
I
for each
other
P' O''
Modified program
Differential Testing Metamorphic Testing
P1 O1
I O
Oracle Oracle
I P2 O2 for each P for each
other other
I' O'
P3 O3
Interchangeable programs: P1(I) = P2(I) = P3(I) Derived follow-up input
Intramorphic Testing
Intramorphic Testing
P O
Oracle
I
for each
other
P' O''
Modified program
Intramorphic Testing is a white-box methodology aiming
to complement differential testing and metamorphic
testing
General Methodologies
Intramorphic Testing
P O
Oracle
I
for each
other
P' O''
Modified program
Differential Testing Metamorphic Testing
P1 O1
I O
Oracle Oracle
I P2 O2 for each P for each
other other
I' O'
P3 O3
Interchangeable programs: P1(I) = P2(I) = P3(I) Derived follow-up input
General Methodologies
Intramorphic Testing
P O
I
Oracle General methodologies
for each
other whose concrete
P' O''
realizations require
domain-specific insights
Modified program
Differential Testing Metamorphic Testing
P1 O1
I O
Oracle Oracle
I P2 O2 for each P for each
other other
I' O'
P3 O3
Interchangeable programs: P1(I) = P2(I) = P3(I) Derived follow-up input
Intramorphic Testing
P
C1 Ci
It is intuitive to think of a program P
consisting of individual components C1 to Cn
Cn-1 Cn
O
Intramorphic Testing
P P' = P[Ci'/Ci]
C1 Ci
Intramorphic C1 Ci'
transformation
Ci'/Ci
Cn-1 Cn Cn-1 Cn
Test oracles
for each other
O O'
Replacing a specific component in a system
might have an anticipated effect on the overall
system
Intramorphic Testing
Implementing a reverse sorting function and
reversing either function’s output should yield
the same result as the original sorting function
Intramorphic Testing
bubble_sort
[3, 1, 2] [1, 2, 3]
Oracles
bubble_sort_reverse Reverse For each
other
[3, 1, 2] [3, 2, 1] [1, 2, 3]
Intramorphic Testing
while True:
arr = get_random_array()
sorted_arr = bubble_sort(arr.copy())
reverse_sorted_arr = bubble_sort_reverse(arr.copy())
assert sorted_arr.reverse() == reverse_sorted_arr
Intramorphic Testing
while True:
arr = get_random_array()
sorted_arr = bubble_sort(arr.copy())
reverse_sorted_arr = bubble_sort_reverse(arr.copy())
assert sorted_arr.reverse() == reverse_sorted_arr
AssertionError: [1, 2, 1] [3, 2, 3]
Pinjia He @ CUHK Shenzhen
Discussion: Characteristics
• Granularity (operator, system, …)
• Format (source code, binary, …)
• Transformation realization (adding new
component, replacing it, …)
• Completeness (applicable to any input)
• False alarms
•…
Future research could explore their
strengths and weaknesses
Discussion: Domain
• Compilers
• Database systems
• SMT solvers
•…
Similar to differential testing and metamorphic
testing, domain-specific insights will be
necessary to realize effective approaches
Discussion: Practicality
Users Developers
Discussion: Practicality
I can apply metamorphic testing and
differential testing without deep knowledge on
the system’s internals
Users Developers
Discussion: Practicality
I can use intramorphic testing to incorporate my
application knowledge into the testing process
Users Developers
Discussion: Practicality
How should I maintain multiple versions?
How can the IDE support me? …
We hope that future research will
propose approaches to lower the
cost of using intramorphic testing
Developers
1. Mutation Testing
2. Differential Testing
3. Metamorphic Testing
4. Intramorphic Testing
5. Retromorphic Testing
6. Examples
Pinjia He @ CUHK Shenzhen
Retromorphic Testing
Idea: We can create a dual-program architecture for testing
the target software by developing an auxiliary program
that mirrors the program under examination.
Retromorphic Testing
P O I O M1 P M2
Oracle between Modify Oracle between Oracle between Modify
I O and O' I to I' P O and O' M1 and M1' M2 to M2'
M1
P' O' I' O' Q M2'
'
P, P': Different program I, I': Input and derived input P: A program that transforms M1 to M2
with same functionality Q: A program that transforms M2' to M1'
(a) Differential Testing (b) Metamorphic Testing (c) Retromorphic Testing
Test Traditional Software
M1: A pivot row generated by random selection P: A program to produce a SQL
query that should yield the pivot row.
t0.c0 t0.c1 t1.c0
P
3 TRUE -5
Test oracle: Result rows (M1') must SELECT t0.c0, t0.c1, t1.c0 FROM t1, t2
contain the pivot row (M1) WHERE NOT (NOT t0.c1 OR (t1.c0 > 3))
t0.c0 t0.c1 t1.c0
4 TRUE 2 Q
3 TRUE -5
5 TRUE -7
Test AI Software
M1: An input English text P: Google Translate (EN to ZH)
Mike would leave the bloc
if Jack leaves the city
Test oracle: The two English M2: The Chinese text 如果杰克离开这座城市，
texts (M1 and M1') should contain translated by Google 迈克就会离开欧盟
the same proper nouns
If Jack leaves the city,
Mike leaves the EU
M1': The translarted English text Q: Google translate (ZH to EN)
Pinjia He @ CUHK Shenzhen
