Rahul Gopinath
University of Sydney

Email<EMAIL_ADDRESS>Philipp Görz
CISPA Helmholtz Center

for Information Security

Email<EMAIL_ADDRESS>
Mutation analysis is one of the most effective, but costly means of assessing
the ability of software test suites to prevent bugs.
Traditional mutation
analysis involves producing and evaluating syntactic variants of the original to
check whether the test suite under evaluation is capable of distinguishing
between the variant and the original in terms of behavior.

Evaluating each mutant separately means a large amount of redundant computation,
both between the original program and mutants, and also between different

Previous work explored numerous means of removing redundancy. However,
some amount of redundancy has remained especially in the post-mutation phase.

In this paper, we propose execution taints – A novel technique that
repurposes dynamic data-flow taints for mutation analysis. Our
technique is the only technique that can remove the redundancy in post-mutation
phase, achieving better efficiency in mutation analysis.
We further leverage memoization to eliminate redundant execution between
program variants.

§ INTRODUCTION

Mutation analysis is the gold standard for evaluating the quality of software
test suites. It is one of the very few techniques that can actually evaluate the
quality of oracles provided by software test suites.
Unfortunately, mutation analysis is also
one of the most costly methods for test suite evaluation.
The problem is that traditional mutation analysis requires generation
and independent evaluation of each syntactic variant (mutant) by the
test suite [1].
This means that one needs to execute the entire test suite as many times as the
number of mutants at worst. This can be reduced to some extent by running each
test case only on those mutants whose mutation site is covered by the
test case [2].
However, this still leaves a large number of mutants to evaluate independently.
For example, <Ref> includes four possible mutations:
1 in <Ref>, 2 and
3 in <Ref> and 4 in <Ref>. With
traditional mutation analysis (<Ref>),
this would require five executions including the execution of original to
determine coverage of the test suite, and four from each of the four mutants
We use
x to denote a mutation where $x$ is the mutation id. The
corresponding mutant is x. We refer to the original as 0.

Numerous previous researchers have noticed that traditional mutation analysis
is highly redundant, and significant execution cost savings can be achieved if
one can eliminate some of these redundancies.
Researchers have focused on eliminating these redundancies to make mutation
analysis more efficient.
Just and Fraser [3] showed that not all the mutants need
to be executed independently. Some mutants result in the same value, and hence
the same infected state, and only some of these are propagated.
Hence, one can partition states resulting from mutations, and only those
resulting in unique propagated states need to be evaluated independently.
For example,
in <Ref>, when INPUT=1>, execution of 1 results in the
same state as the original. Hence, the partitioned state execution
(<Ref>) skips the execution of 1.

In split-stream execution [4, 5, 6],
a mutant is forked when the mutation is executed at runtime, which shares
the execution path until the execution of the mutation.
For example, when one executes the program (<Ref>) with say INPUT=1>,
at each mutation, a new process is spawned. This results in a total of four
new processes at the end (<Ref>), but with the initial
execution until the mutation
shared with the original.

The equivalence-modulo state approach [7] is the latest
such technique, and it combines the advantages of state-partitioning and
split-stream executions. The idea is to fork only if the mutation leads to a new
unique state. This technique is even more efficient, skipping 1
and sharing the execution path between original and also between
mutants (<Ref>).

Two different strategies exist to reduce the computational expenditure in
mutation analysis. The first one involves using intelligent execution tracking
runtimes that is able to identify shared execution paths between mutants,
forking and merging.

The second strategy is to use approximate techniques such as weak mutation,
firm mutation, checked coverage etc.

The problem with the first strategy is that it requires extensive support from
the language runtime and infrastructure. The heavy engineering investment
required puts such strategies out of reach for many languages.

Secondly, we find that all such frameworks split the execution

The problem with weak mutation is that it has proved difficult to implement.
None of the most popular off-the-shelf mutation analysis frameworks implement
weak mutation. The second problem is that weak mutation score disregards the
most important part of mutation analysis – evaluation of oracles. Without
oracle evaluation, mutation score becomes another coverage score.

node distance = 12mm,
start chain = going below,
box/.style = draw,rounded corners,blur shadow,fill=white, on chain,align=center]
[box] (b1)
$x\leftarrow 1$

$s\leftarrow 0$

$K\leftarrow 1$;
[box] (b2)
[box] (b3)
$s\leftarrow s+x$

$x\leftarrow x+1$;
[box] (b4)    $\vdash s$ == $\frac{1}{2}K(K-1)$ ;
[rounded corners,-latex]
(b2.-40) edge[bend left=60] (b4.40)
(b1) edge (b2) (b2) edge (b3);
(b3.230) – ++(0,-0.3) -| ([xshift=-5mm]b2.west) |-
([yshift=3mm]b2.130) – (b2.130);

Main line

node distance = 12mm,
start chain = going below,
box/.style = draw,rounded corners,blur shadow,fill=white, on chain,align=center]
[box] (b1)
$x_0\leftarrow 1$

$s_0\leftarrow 0$

$K_0\leftarrow 1$;
[box] (b2)
[box] (b3)
$s_1\leftarrow s_{0}-x_0$

$x_0\leftarrow x_0+1$;
[box] (b4)     $\vdash s_1$ == $\frac{1}{2}K_0(K_0-1)$ ;
[rounded corners,-latex]
(b2.-40) edge[bend left=70] (b4.40)
(b1) edge (b2) (b2) edge (b3);
(b3.230) – ++(0,-0.3) -| ([xshift=-5mm]b2.west) |-
([yshift=3mm]b2.130) – (b2.130);

Execution shadow

Sum of integers

[style=Python, escapechar=|]
def partitioned_process(a: int) -> int:
i:int = 0
res: int = 0
a = a + 1 # m1: a << 1                 ||
counts = get_counts()                  ||
while i < counts:
a = a/2 # m2: a + 2 m3: a * 2        ||
res += process(i)        ||
i += 1
return res

def process(i: int):
if i < 0: # m4: i < 1        ||
return 0
return time_consuming(i)

def test_process():
assert partitioned_process(INPUT) == OUTPUT

The partitioned_process()> program

= 1;
= 0;
= ;

pics/mygrid/.style n args=0code=

[thick,white,->] (0,0) – (5,0);

[thick,white,->] (0,0) – (0,10);

pics/singlestepF/.style n args=5code=

[draw,circle,fill=gray!20,inner sep=0pt,minimum size=14pt] (.) at (,);

pics/singlestep/.style n args=5code=

[thick,-latex] (,+) – (,+);
[draw,circle,inner sep=0pt,fill=white,minimum size=14pt] (.) at (,);
pics/singleline/.style n args=4code=

= -;

pic singlestep=1 ;
pic singlestep=4 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;
pic singlestep=19 ;
[thick,-latex] (,+) – (,) node [below=1pt] #4;
pics/traditionalM/.style n args=3code=

pic singleline=M0;
pic singleline=+1 M1;
pic singleline=+2 M2;
pic singleline=+3 M3;
pic singleline=+4 M4;
pics/partitionM/.style n args=3code=

pic singleline=M0;
pic singleline=+1 M2;
pic singleline=+2 M3;
pic singleline=+3 M4;
pics/splitstreamM/.style n args=3code=

= -;

pic singlestep=1 ;
pic singlestep=4 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;

pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;

pic singlestep=19 ;

[thick,-latex] (,+) – (,) node [below=1pt] M0;

pic singlestepF=+4 4 ;
pic singlestep=+4 7 ;
pic singlestep=+4 13 ;
pic singlestep=+4 8 ;

pic singlestep=+4 7 ;
pic singlestep=+4 13 ;
pic singlestep=+4 8 ;

pic singlestep=+4 19 ;

[thick,-latex] (+4,+) – (+4,) node [below=1pt] M4;

[thick,-] (+,) – (+4-,);

pic singlestepF=+2 7 ;
pic singlestep=+2 13 ;
pic singlestep=+2 8 ;

pic singlestep=+2 7 ;
pic singlestep=+2 13 ;
pic singlestep=+2 8 ;

pic singlestep=+2 19 ;

[thick,-latex] (+2,+) – (+2,) node [below=1pt] M2;

[thick,-] (+,) – (+2-,);

pic singlestepF=+3 7 ;
pic singlestep=+3 13 ;
pic singlestep=+3 8 ;

pic singlestep=+3 7 ;
pic singlestep=+3 13 ;
pic singlestep=+3 8 ;

pic singlestep=+3 19 ;

[thick,-latex] (+3,+) – (+3,) node [below=1pt] M3;

[thick,-] (+2+,) – (+3-,);

pic singlestepF=+1 13 ;
pic singlestep=+1 8 ;

pic singlestep=+1 7 ;
pic singlestep=+1 13 ;
pic singlestep=+1 8 ;

pic singlestep=+1 19 ;

[thick,-latex] (+1,+) – (+1,) node [below=1pt] M1;

[thick,-] (+,) – (+1-,);
pics/modulostateM/.style n args=3code=

= -;

pic singlestep=1 ;
pic singlestep=4 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;

pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;

pic singlestep=19 ;

[thick,-latex] (,+) – (,) node [below=1pt] M0;

pic singlestepF=+2 7 ;
pic singlestep=+2 13 ;
pic singlestep=+2 8 ;

pic singlestep=+2 7 ;
pic singlestep=+2 13 ;
pic singlestep=+2 8 ;

pic singlestep=+2 19 ;

[thick,-latex] (+2,+) – (+2,) node [below=1pt] M3;

[thick,-] (+,) – (+2-,);

pic singlestepF=+3 7 ;
pic singlestep=+3 13 ;
pic singlestep=+3 8 ;
pic singlestep=+3 19 ;

[thick,-latex] (+3,+) – (+3,) node [below=1pt] M4;

[thick,-] (+2+,) – (+3-,);

pic singlestepF=+1 13 ;
pic singlestep=+1 8 ;
pic singlestep=+1 7 ;
pic singlestep=+1 13 ;
pic singlestep=+1 8 ;
pic singlestep=+1 19 ;

[thick,-latex] (+1,+) – (+1,) node [below=1pt] M2;

[thick,-] (+,) – (+1-,);
pics/taintedM/.style n args=3code=

= -;

pic singlestep=1 ;
pic singlestep=4 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;
pic singlestep=7 ;
pic singlestep=13 ;
pic singlestep=8 ;
pic singlestep=19 ;

[thick,-latex] (,+) – (,) node [below=1pt] M*;

pic singlestepF=+1 13 ;

[thick,-] (+,) – (+1-,);

[thick,-latex] (+1,-) –(+1,) – (+, );

pic singlestepF=+1 13 ;

[thick,-] (+,) – (+1-,);
[thick,-latex] (+1,-) –(+1,) – (+, );

[thick,-] (+,) edge [loop right,min distance=10mm,in=-30,out=30] (+, );

[thick,-] (+,) edge [loop right,min distance=10mm,in=-30,out=30] (+, );

pic mygrid=;
pic traditionalM=1 9 1;

pic mygrid=;
pic partitionM=1 9 1;

pic mygrid=;
pic splitstreamM=1 9 1;

pic mygrid=;
pic modulostateM=1 9 1;

pic mygrid=;
pic taintedM=1 9 1;

The execution flows in the considered mutation analysis algorithms. The numbers correspond to
line numbers in <Ref>. Horizontal lines represent split execution,
and the loops represent operations within execution taints. 0 is the
original execution.

That is, the current state of the art [7] is very efficient in
eliminating the causes of redundant execution until the point where mutations
cause a divergence in state. However, the biggest cause of redundancy of
execution is not the pre-divergence execution. There is no solution yet for
avoiding redundant execution in the post-divergence execution phase when a forked
execution restarts following the execution of the original.

For example, the modulo-state execution (<Ref>) forks
a new mutant process from the original after executing <Ref> and this
mutant process forks again in the second loop when 3 and 4
diverge. However, in each of these processes, the function process(i)> is
called with exactly the same arguments because i> is never mutated in these

In this paper, we propose mutation analysis with execution taints as a way to
achieve much lower redundancy than previously known methods.
Our proposal is based on three observations:

The first observation is that many mutants
do not produce a change in the control-flow from the original. For example,
in <Ref>, the line <Ref> is mutated in mutants
$M2$ and $M3$ resulting in different values for $a$.

Even though the value of $a$ is different
in the original and mutants, since $a$ never influences the control-flow,
the actual execution flow of the original and the mutant is exactly the same.
That is,
except for the values affected by the mutation, the
other steps of execution are the same. Hence, one can reduce the cost
of mutation analysis if such common execution steps can be shared between
such mutants and the original program.

Our second observation is that for such mutations that does not change control
flow, one can consider the mutation to have introduced a unique taint in
the computation, and this taint can be propagated dynamically to any values
using the results of the computation using standard taint propagation through
dynamic data-flow[
We note that tainting values is a remarkably light weight operation in many
languages. For example, many languages [8, 9, 10]
already has runtime support for tainting, which can be repurposed for execution
taints.]. Such taints can be propagated using standard techniques in most
languages even if the language runtime does not have direct support for taint
propagation [11, 12].

We do not simply propagate a taint flag.
As long as there is no control-flow divergence, we propagate the
results of computations involving mutations in the same taint.
We call such
taints value taints of corresponding values.
The computations involving such value taints
are called execution taints of the main computation.

Our third observation is that even when there is a control-flow divergence, it
is possible to limit the impact of diverged control-flow to the function
containing the mutation using merge-back of execution and judicious
use of memoization.

Using these three observations, our technique (<Ref>) can perform
extremely efficient mutation analysis limiting both pre and post mutation
redundancies .

§.§ Contributions

* We propose a complete framework for avoiding redundancy in mutant execution
including both pre-divergence and post-divergence stages.

* Our execution taints is a lightweight mechanism that repurposes
dynamic data-flow taints for mutation analysis.

* We propose a novel memoization strategy for sharing computational results
across mutants.

* We propose a comprehensive solution to the problem of sharing single-use
resources by mutants during forking.

§ APPROACH

We now discuss our approach in detail. There are two cases that we need to
discuss in detail. The first is when there is no control-flow divergence between
the mutant and the original. The essential idea is that values resulting from
mutated expressions are stored as dynamic taints of the resulting values.

§.§ Taint Schemata

Given a program and test suite that needs to be evaluated, we first transform
the program to a meta-mutant containing all mutants.
For example, below is the code fragment from <Ref>.
[style=Python, escapechar=|,firstnumber=6]
while i < counts:
a = a/2
res += process(i)
i += 1

This gets transformed into the following meta-mutant[The chevrons ($<$,$>$) indicate
lambdas, which are also passed the mutation id.]
[style=Python, escapechar=|,firstnumber=6]
while i < counts:
a = @T(<M0: a/2>, <M2: a+2>, <M3: a*2>)
res += process(i)
i += 1

where 0 is the key for original value, 2 is the key for second
mutant, and 3 is the key for the third mutant.
During the execution of the meta-mutant,
the function @T> is called and passed the different possible variants of
<Ref>. The function @T> collects the results of each, and these are
stored in the dynamic taint of a> as a key-value map.

§.§ Execution Taints and Transmission Rules

As we specified in <Ref>, We use x to denote a mutation where
$x$ is the mutation id. The corresponding mutant is x.
We refer to the original as 0.

The single taint value corresponding to a single mutant is called an execution
taint of that value for that mutant, and the list of taints from different mutations
that is attached to a value (or equivalently, a variable at a point in
execution) is called the taint map for that value.
That is, after the execution of <Ref>, if we started with a value
$a=2$, then the resulting $a$ will have a value given by the taint map:
{01, 24, 34}. Here, 4 is an execution taint corresponding
to both 2 and 3 attached to the original value. 1 is the execution
taint of the original (0) – i.e. the non-mutated value.

When two values are used in an operation, the following rules are used for taint
propagation. We use the $A$, $B$, and $C$ for indicating the variables involved
in an expression. We further use $\otimes$ to indicate an operation.

We use $A^{x}$ to indicate the value taint of x stored in $A$.
If $A$ does not have a value taint of x, the original value, that is,
the value taint of 0 is returned instead.

If a
variable is tainted, it annotated with its taint map. For example,
A0A^0,1A^1 means that $A$ carries an execution
taint of mutation 1.
It is equivalent to A1A^1 eliding the original 0 value.

That is, given $M^x \subset M$, $M^y \subset M$, and
$M_o$ is an operator mutation in $M$, where $M$ is the set of mutants, after
the execution of

\[
A_{\{M_i:A^i \; \mid \; M_i \in M^x \}} \; \otimes_{M_o:\odot} \; B_{\{M_j:B^j \; \mid \; M_j \in M^y \}}
\]

the result will be stored as

\[
C_{\{M_i:(A^i\otimes{}B^i) \; \mid \; M_i \in (M^x \cup M^y) \}\;\cup\;\{M_o:A\odot{}B\}}
\]

We discuss a few clarifications of this equation next. We elide the braces in
the taint map when there is no ambiguity in the context.

* If neither value has a taint, and the operation is not a mutation,
then the resulting value will not have a mutation execution taint. That is, given the operation

\[
A \otimes B
\]

where the result is stored in $C$, $C$ will not have a taint.
The above equation is equivalent to

\[
A_{M_0:A} \otimes B_{M_0:B}
\]

with $C_{M_0:A\otimes{}B}$ as the result.

* An operation can also be tainted when it itself is mutated. In that
case, the operation will be associated with a single mutant.
E.g. $\otimes_{M_x:\odot}$ indicates that $\otimes$ was mutated by
x changing $\otimes$ to $\odot$.

* If neither value has a taint, but the operation is a mutation, the
resulting value will have the taint of the mutation as the single element
in its taint map.
That is, given the equation

\[
A \otimes_{M_x:\odot} B
\]

the result will be stored as $C_{M_x:A\odot{}B}$.
For example, given $a + b$ as the original expression,
with $a=1$, $b=1$, and we have mutation 1 that mutates this expression to
$a - b$, the resulting value will have
{0:1, 1:0} as the taint map.

* If both values have x in their taint map, and the operation
is not mutated, then the operation will be performed between the values
corresponding to x in both values' taint map.
That is, given the equation

\[
A_{M_x:A^x} \otimes B_{M_x:B^x}
\]

the result will be stored as CXA^x⊗B^x.
For example, given a01,12 and
b03,14, $c = a + b$
will result in c04, 16.

* If both values have x in their taint map, and the operation
is also mutated, then the mutated operation will be performed between the
values corresponding to x in both values' taint map.
That is, given the equation

\[
A_{M_x:A^x} \otimes_{M_x:\odot} B_{M_x:B^x}
\]

the result will be stored as CxA^x⊙B^x

* If one of the values is missing the taint x in their taint map,
and the other has x in their taint map, the value of 0 will be
used instead, and the resulting value will be placed as execution taint
corresponding to x in the taint map.
That is, given the equation

\[
A_{M_x:A^x} \otimes B
\]

the result will be stored as CxA^x⊗B^0.

* In the case of multiple execution taints, each taint is evaluated separately.
That is, given the equation

\[
A_{M_x:A^x, M_y:A^y} \otimes_{M_z:\odot} B_{M_x:B^x, M_y:B^y}
\]

the result will be stored as CxA^x⊗B^x, yA^y⊗B^y, zA⊙B.
Note that different mutants never interact.
For example, given a01,12 and b03,25, $c = a + b$
will result in c04,15,26.

For example, the a> after <Ref> in the first iteration of  is
annotated a01,24,34.
This corresponds to the value of $a=1$ in the
original and $a=4$ in both 2 and 3.

That is, each mutant shares the execution as well as the state until the
mutation is seen, after which it shares the execution and the variables not
tainted in the mutation with the original.

Such taints are checked during test case assertions. Each single execution
taint that correspond to a mutant is executed separately in each assertion.
Any mutant that fail the assertion is marked as killed.

Propagating execution taints works well until the control-flow diverges.
If a tainted value is involved in control-flow, and the control-flow
diverges from the mainline[We call the execution path of the
original program mainline execution path.] the simple data-flow
taint transmission is no longer sufficient for executing mutants that

However, for conditionals, (assuming no return> statements), the
control-flow merges back to the mainline after the conditional branch finishes
execution. Similarly, for loops, the control-flow merges back to the mainline
execution path after all iterations finish. However, the presence of
return> statements can introduce additional complexity.
Hence, we use the procedure boundaries as merge points of diverged

In this case, we have two choices based on whether the platform
has the ability to fork (and is efficient to do so)

§.§ Diverged Control-Flow When Fork is Available

Accounting for diverged control-flow when an efficient fork is available is
accomplished as follows. We first wrap every function in the program with
another function (In Python, this is accomplished using a decorator [13]).
Next, we implement the split-stream execution within the wrapped function,
but rather than splitting on encountering a mutation, we split on control-flow
divergence to as many children as there are diverging mutant executions.

That is, as soon as one of the mutant control-flow paths diverge from the
main, the process forks, with the parent continuing the mainline execution,
and the children following the divergent control-flows. Given that this is
a function call made from a wrapper function, the wrapped function returns
in mainline as well as divergent processes to the wrapper function. Within the
wrapper function, the parent process waits for, and gathers all global variable
changes induced by the divergent processes as well as the return value from the
wrapped function[We call this the merge-back of diverging executions
both for forking and non-forking choices.].
These are updated to the taint maps of variables in the mainline.
The execution continues from the wrapper function returning the
value with the updated taints.

§.§ Diverged Control-Flow When Fork is Unavailable

Accounting for diverged control-flow when fork is unavailable or is too
inefficient to use either because the operating system fork is costly or
the process of merge-back from external process is costly. As before, we
start with a function wrapper for each functions.

Within such a wrapper, we first set the execution path to be followed to
0, that is the mainline. Any mutant that does not follow the execution
path of 0 is marked wounded.

Once the function finishes for the given execution path, it returns to the
wrapper function. Within the wrapper, we look at the mutants that are newly
marked as wounded, and those that are marked as active.
We temporarily remove active mutants from consideration, choose one of the
wounded mutants – say x. For any such mutant, we can determine if
the wound happened due to a mutation within the function (or any child functions
called from the function) or if the function and child functions were
unmodified because for any active taints, we know the location where the taint
was encountered.

Let us take the case when the function and child functions were unmodified.
In this case, we execute the wrapped function
using untainted parameters with values from execution taints from x.
This gives us the return value from the mutant. The return value is merged
back as execution taint of x on to the mainline. The taints of
any globals modified by the function call are similarly updated. We mark
x as no longer wounded. We pick the next wounded mutant, and continue
the process until there are no more wounded mutants.

If on the other hand, the function or one of the child functions called from
it contained the current mutation, we call the mutated function instead for
that function, and collect taints. The remaining process is the same.

Thus at the end of the function call, we have successfully merged the diverged
control-flows into the system state.

§.§ Memoization for Sharing Execution Across Mutants

At this point, we have shown that we can merge back executions from
diverging control-flows at the function boundary where the diverging execution
happened. However, this still leaves some redundancy. Consider
the fragment in <Ref>.

[language=Python, escapechar=|]
def my_fn(v: int) -> int:
if v > 0: # m1: v > 1
r = time_consuming_fn(v)
return r
r = time_consuming_fn(v)
return -r

Memoization Example

Here, the control-flow diverges at 1 when my_fn(1)> is
executed. However, time_consuming_fn(v)> is executed in both original
as well as the mutant with exactly the same parameters. Hence we next see
how to eliminate this redundancy.

The basic intuition here is that given that we already wrap each function,
we can memoize the execution results of each function and specific
parameter values. (This database of memoized function calls are stored
externally for the forking version so that all processes can access it.)

An important constraint for memoization is that we should ensure that it
does not grow out of bounds. Since concern here is ensuring a fast mutation
analysis by sharing similar executions across mutants, we follow the
simple expedient. The memoization cache is maintained only if there are
unmerged mutants. We clear the current cache completely as soon as all
mutants merge. The idea here is that a mutant can make use of the cache
for avoiding redundant execution with the original or another mutant
if and only if there are active unmerged mutants in the first place.
We also ensure that the original process executes first, and the mutant
processes start execution only when the original has returned from the function.
Further, only one mutant process is executing at any time. (If parallel
execution is more important than utilizing memoization, one can start the
mutant-processes in parallel).

There are two cases to consider for updating the memoization cache.
The first is when no mutation is encountered within the function call (or in one
of the child functions called from that function), and the second when a
mutation is encountered within the function call (or its child calls).

New processes update the cache if and only if the mutation was not
encountered after forking. This is because we can't share the execution of
a mutated function with any other mutant.
To implement this, we maintain a stack of current function calls. That is,
each entry in the stack is of the form all:(function, parameter values).

Say we have a function call with a number of active
execution taints in the parameters. We execute the mainline, and at the end
of execution of the mainline, we have a subset of these execution taints in the
return value.
If any mutation was encountered (the execution of taint_t()> call),
we look at the call stack and we produce the following entry for current
call and each parent call — (mutant, call:(function, parameter values)) = mutated>.
This is saved in a mutation cache.

Each execution taint in the return value of the mainline represents a possible
new entry in the memoization cache.
That is, we add a memoization entry with the key
call:(function, parameter values), and the corresponding return value is stored
with this key unless the mutation cache contains the just returned call for this
particular execution taint. If it contains the just returned call, then the
return value is not memoized.

For each child processes, before executing any functions, the memoization is
first checked to see if the call was previously memoized, and the call is not
present in the mutation cache. If so, the result
is retrieved, and used. The memoization cache is updated with the result of
a function if the entry did not previously exist, and the mutation cache does
not contain the current (mutant, call:(function, parameter values)) tuple.

With this technique, we guarantee that any non-mutated function call (that is,
function calls that do not encounter a mutation during the execution of the
current function or its children) within the mainline or the mutants will be
available by other mutants.

If the function call encountered a mutation, then obviously the function being
computed is different, and it is not shareable by other mutants.

§ IMPLEMENTATION

We were motivated by a desire to place our ideas before the mutation analysis
community at an early phase so that the community can build on our ideas, and we
may gain valuable early feedback. Hence, we were motivated to quickly flush out
our initial prototype demonstrating the proof of concept that our ideas can
indeed work.

However, this also meant that we chose a number of techniques based on their
simplicity rather than their efficiency. For example, our prototype is
implemented in Python, and uses a library based taint mechanism.

We wanted to compare each of the previous approaches and identify how they
improved over traditional mutation analysis, and previous state of the art.
Hence, we implemented each of the approaches ourselves. These include the
(1) simple traditional approach, (2) the split-stream approach, and (3) the
equivalence modulo state approach. Further, we wanted to evaluate the
effectiveness of the two different kinds of merge back: with forking and
without forking both without and with memoization.

§.§ Implementation of Taints

As a prototype, our priority was on evaluating the realizability of our proposal
quickly. Hence, the taint transfer is only implemented for the primitive
types int and float, which were sufficient to completely implement mutation
analysis for our subjects. However, as Conti [11] demonstrates,
this approach can be extended to arbitrary data types in Python.
The primitive types are wrapped by a proxy class, providing a proxy object that
behaves like the original, but with the added capability to propagate taints.
The taints are stored as a Python dictionary with the mutation id as the key
and the value corresponding to the mutation as the value.

§.§ Mutation Operators

The following mutation operators are implemented in our mutation framework.

* Comparison operators. We mutate each of the following comparison operators \(==, !=, <, <=, >, >=\) to
each other.

* Arithmetic operators. The following arithmetic operations are mutated into each other
\(+, -, *, \%, <<, >>, |, ^, \&, //\).

§.§ Meta Mutant

For implementing our technique, we use AST transformation to embed the different
mutations in the same source code. We show the transformation of the program in <Ref>
in <Ref>.

[style=Python, escapechar=|]
def partitioned_process(a: int) -> int:
i:int = 0
res: int = 0
a = @T(<M0: a+1>, <M1: a<<1>) ||
counts = $get_counts()
while @C(i < counts):
a = @T(<M0: a/2>, <M2: a+2>, <M3: a*2>) |\label{line:m7}|
res += $process(i)
i += 1
return res
$partitioned_process = wrap(partitioned_process)

def process(i: int):
if @C(@T(<M0: i<0>, <M4: i<1>)): |\label{line:m13}|
return 0
return $time_consuming(i)
$process = wrap(process)

def test_process():
@assert $partitioned_process(INPUT) == OUTPUT

The meta-mutant of the partitioned_process()> program

Each mutation point is replaced by a @T()> call with a dictionary as the
parameter. The dictionary contains several key value pairs of the format
$\langle$Mi: expr>$\rangle$. Here, the key for the dictionary is Mi> which
is the mutation id. The expr> is the original or mutated expression wrapped
in lambda> that is evaluated in the context of Mi>.

Each lambda expression is evaluated to generate the corresponding execution taint.
For the evaluation of a lambda> corresponding to a particular mutation, the
corresponding execution taints of that mutation is extracted from the expression.
That is, $\langle$M2:a+2>$\rangle$ indicates that we first extract the
execution taint M2> in the variable a> (if not found, we extract the execution taint M0>
(the original value) from a>), and use it for computing the expression a+2>.
This is then stored under the key M2> the execution taints of the resulting expression.

Any uncaught exception during the evaluation of such a lambda function is counted as a
strong kill of that mutant.

§.§ Implementation of Forking

Forking is performed in the @C(expr)> call when evaluating the expression
expr> results in different values for the mainline and some execution taint
corresponding to a mutant. After forking, the mainline and mutants that follow
the mainline continues in the parent process while the mutants that diverged
continue in the forked child. The forked process (and the parent) can fork again
if the mutants in that process diverge from each other again.

Each function is wrapped in a wrapper function (the wrapped functions are
indicated by a $ in their name) that detects a control-flow divergence within
the function. When there is a control-flow divergence (and hence a forking) the
parent process starts executing (the child processes are immediately suspended)
and finishes first, returning to the wrapper function. The wrapper then
starts the child processes one at a time. Each child process exits when it
reaches the wrapper function after communicating the result of the function call
to the parent process. The wrapper function in the parent process receives
these results, updates the taint of the function return and continues.

§ EVALUATION

For evaluation, we chose the following subjects: (1) , (2) , (3) , (4) , (5) .
The details are given in <Ref>. As our technique is in the
prototype stage, the subjects were chosen for the limited data types, and Python
features that they used. Our subjects are also somewhat small, implementing just
a simple algorithm in each case. Hence, this our evaluation is not a general
empirical validation, but rather a proof of concept that this technique can

Subject           LOC     Mutants

42      55

19      46

19      35

15      39

24      58

30725      31517     22803      2830         2830     988     988

4974       4453      4106       108          108       108      108

3786       3469      2510       1192         1192      140      140

2095       1737      1239       511          511       103      103

5057       4533      3059       2740         2020      931     931

Mean $T\times$       1          0.89      0.68       0.25         0.23      0.07     0.06

The number of lines of code from the program that is executed by various mutation analysis techniques.

0       519532     1102095     4283465     7698959     2346929     3562687

0       131935     313604     255611      264010      248328     256665

0       86980      165647     1999129     2142995     216044     233252

0       420113     783796     4954838     5002992     752975     759959

0       149927     272727     2166888     1600531     688069     715081

The infrastructure code executed to support each technique per program. We note that the infrastructure code is very large due to the prototype nature of our implementation. This can be optimized heavily.

3.38       11.50     15.75     104.73     77.06     103.06     113.75

2.63       5.56     8.83     3.30     3.26     3.29     3.32

1.93       3.98     3.58     19.02     20.53     2.63     2.99

2.21       9.49     10.21     113.75     114.02     8.67     8.84

3.22       7.26     5.17     25.38     18.91     8.42     8.75

The wallclock runtime (seconds) for each technique per program.

We evaluate the following mutation testing optimization approaches:

* Traditional. The traditional mutation analysis method. Each
mutants is generated, and executed separately with no sharing.

* Split-stream. The split-stream execution is an improvement over
the traditional mutation execution. Each mutant shares the execution path
with the original until the mutation is first executed. We use the
topsy-turvy [5] implementation.

* Modulo-equivalent. This is an implementation of the equivalence modulo states
approach [7]. This approach is similar to split-stream,
with the difference that, rather than forking as soon as a mutation is
executed, the forking is performed when the mutation leads to a unique
state. This also means that child processes themselves fork again when two
mutants that initially produced the same state separate at a later point.

* Execution-taints The execution taints approach that we
introduced in this paper. When a control-flow divergence is detected, the
diverged mutants fork and continue in a child process. Any function calls
within the mutants are looked up in the memoization cache so that redundancy
of execution is limited to the function where the mutants diverge.

* Execution-taints-Nf-Nm. The execution taints approach that we
introduced in this paper, but without the memoization, and without forking.
That is, when a control-flow divergence is detected, the mainline is allowed
to proceed, and the function is re-executed with the divergent mutant as the
mainline after the original returns. Further, the function calls are not
cached by mainline, which means no sharing of child functions by mutants
after control-flow divergence.

* Execution-taints-Nf The execution taints approach, but
incorporating memoization of function calls.

* Execution-taints-Nm The execution taints approach, incorporating
forking but not memoization of function calls.

Given that our implementation is a prototype, a number of implementation
decisions we made are simple costly. For example, using a library based taint
approach imposes a rather large overhead on execution. Similarly, wrapping
expressions in a lambda> for evaluation also imposes large overheads.
These techniques are external to the actual utility of our research. However,
they have an impact on the computational expenditure of the prototype.
That is, it is not informative to compare the actual wall-clock execution time.
Hence, for evaluation, we instead focus on the actual number of statements
executed by the Python virtual machine. That is, we track the lines executed
by hooking into the python execution using pdb.settrace()>. We then tabulate
the lines executed by the mutants and the lines executed by the infrastructure

The different mutation analysis techniques are evaluated and presented in <Ref>.
The infrasttucture support required is given in  <Ref>.

§ DISCUSSION

Mutation analysis is the gold standard in evaluating the oracle quality of a
test suite. However, with the advent of automatic test generators such as
fuzzers, the mind share of mutation analysis as the premier tool has steadily
decreased. This is because fuzzers typically generate millions inputs, and
evaluating the fuzzer quality by independently evaluating each input in a mutant
can be impractical. Hence, for making mutation analysis practical for the
emerging world, we need better ways of evaluating mutants.

The interesting fact is that while mutation analysis contains many opportunities
for optimization by eliminating the redundancy in execution, it has remained
rather difficult to achieve it. While recent advances in mutation
analysis [7] manages to eliminate most redundancies in the
pre-divergence phase, it is not yet complete. Indeed, as we show, the mutants can
still share the execution until the control-flow of the mutants diverge.

We note that no previous work has attempted to merge back the mutation execution when
a diverged mutation execution starts following the original program execution
Our technique is the first to achieve this merge-back.

As our results in <Ref> show, we can cut down on the redundant
execution by merging back the execution of mutants at the function boundary.
Our technique achieves an average reduction of $16.7\times$ less execution
($T \times 0.06$) when using traditional execution as a baseline (T).
In comparison, the state of the art Modulo-equivalent approach achieves only
$1.47\times$ less execution ($T \times 0.68$) than traditional.

Considering the impact of individual pieces, memoization seems to have an
impact only on . However, we note that this is an artifact of the
small programs we use which do not call other functions from the mutated
function. However, this is not the case in larger programs where most
functions call other functions for various parts of the functionality.
Hence we expect the memoization to make more difference in the real world.

As <Ref> shows, each advancement over mutation analysis
is supported by more complex infrastructure code. For example, for
, traditional mutation analysis requires no infrastructure support
during the mutation runtime (the program mutants can simply be executed),
while the execution-taints variants requires the largest support (we note that
in most cases, the infrastructure support required by execution-taints is
comparable to the state-of-the-art modulo-equivalent technique). One thing to
keep in mind here is that the infrastructure code in our implementation is not
optimized, and can likely be optimized heavily in a full-fledged implementation.
For example, both tainting and memoization can have language-runtime support,
which can alleviate their execution cost.

§.§ Relaxing Forking Constraints

One of the problems with fork based sharing is that one-shot external resources
cause havoc. To illustrate, consider the following code.
[style=Python, escapechar=|]
res = create_external_resource(my_resource)
# fork here.
if x > 0: # m1: x > 1

Here, forking happens after the external resource is acquired, and hence both
parent as well as child process uses the resource, and at the end, deletes the
resource. The problem here is that if my_resource> can only be used once per
creation, either the parent or the child process will fail for forking but not
for traditional execution.

With our ability to merge the execution back, we can already ensure that the
resource is released only once. Further use_resource(res)> is memoized by
the main program, which means that the actual external resource is only used
once by the main.

However, there is a subtlety here. External resources hold their own state,
and can respond differently based on their state. The program has no way to
access the internal state of the external resource. We instead use a different
technique. The idea is to rely on the sequence of calls from the original as
indicating the internal state. We associate a counter to the external resource
such that each operation to the external resource takes the counter as one of
the inputs to the memoization, and the counter is incremented for each call.
Hence, when retrieving the memoized result, we use the corresponding counter
value, along with the rest of the parameters, which gives us back the right result.

If the counter value + parameters is not present in the memoization cache, then
we mark the mutant as wounded. That is, the mutant needs to be run independently
to verify that it has failed.

For dealing with objects, a similar method is useful. The problem with objects
is that the self> parameter to any object call contains not just the object id,
but also the entirety of the object state.

[style=Python, escapechar=|]
obj = MyClass()
# these two are different calls.

When an object contains a large number
of members, this can become expensive. Hence, we may associate a counter to each
object that increments when the object is updated, which can be used as a cheap
proxy for the object state.

Further, in this research, we provide several novel ideas, each of which are discussed

§.§ Repurposing Taints for Mutation Analysis

Many languages such as Perl [8] Ruby [14],
JVM and .NET runtime [9, 10] either provide
the ability to track dynamic data-flow taints, or make it easy and efficient
to implement it. Even if the language in question does not directly support
dynamic taint tracking, one can retrofit it as a
library [11, 12].
Our research is the first to identify that the dynamic taints
can be repurposed for mutation analysis by making mutations induce taints in
the expressions they operate on.
This allows us to avoid redundant computation in mutants that follow the same
control-flow path as the mainline.
Indeed, simply by keeping the mutation results as execution taints can allow us
to go beyond the state of the art (Equivalence Modulo State) by forking only
when the mutants diverge in control-flow rather than when they lead to a new

§.§ Merge Post-Divergence Execution

While previous researchers investigated techniques to share pre-divergence
computation, our technique is the first to allow sharing of post-mutation
computation. This shared execution can remove a significant amount of redundant
execution from mutation analysis, making it feasible for advanced test
generators such as fuzzers to use mutation analysis.

§.§ Memoization

While memoization to alleviate expensive computations is a well known technique,
our technique shows how to utilize it effectively for mutation analysis. Using
memoization, we are able to effectively limit redundant computation to
intra-function control-flow.

We note that memoization allows us to relax the constraints that were
associated with split-stream and other forking techniques. The main issue can
be demonstrated by considering a test case which involves creating and deleting a file.
Assume that a mutation occurred after creating the file, but before the deletion.
In such case, any forking implementations that fork on the mutation will
fail because a file is created only once, but attempt is made to delete it twice.

With our technique, there are two reasons this can succeed. In the first place,
if the merge back happens before the file deletion, the file will be deleted only
once. Even if the file is deleted before the merge back, the file deletion call
will be memoized, and will be executed only once.

§ RELATED WORK

With the advent of automatic test generators, it has become important to ensure
that the test suites generated are actually effective in revealing and
preventing bugs. Mutation analysis is of course the premier tool for that
purpose [15]. Mutation analysis involves generating
syntactic variants of the program, which are then evaluated against a test
suite. If the test suite successfully induces a failure in the mutant, but no
failure in the original, we consider the mutant to have been killed. The number
of such mutants killed is called the mutation score of the test suite, and is
considered to be a reliable proxy for the effectiveness of the test suite in
revealing faults in the program. Further, the undetected mutants in a program
for a given test suite is considered a reasonable proxy for the residual defects
in the program.

The error model in mutation analysis is that errors are caused during
transcription of the mental model of the programmer to code [16].
This leads to the two axioms of mutation analysis. The
and the . The  states that programmers tend to create near-correct
versions of programs, and the  states that complex faults are coupled to
simple faults such that test cases capable of detecting the simple faults are
also capable of detecting most complex faults.

Combining these pieces, to be effective, mutation analysis needs to exhaustively
generate all possible simple faults, and evaluate them. If the test suite is
able to capture all such simple faults, we can have high confidence that it will
be able to detect all complex faults in the program.

Unfortunately, exhaustively generating and evaluating all simple faults is
costly. Compared to coverage measures, which can be obtained in a single run of
a test suite, mutation analysis (at worst) requires as many runs of the test
suite as there are mutants (because each mutant needs to be independently

Numerous techniques exist to reduce the computational expenditure involved in
traditional mutation analysis [17, 18].
These can broadly classified into approaches
that try to approximate the traditional mutation score
(weak and firm mutation [19, 20, 21, 22, 23],
checked coverage [24]), and those that try to improve the
efficiency or speed of traditional mutation score.

This research focuses on improving the efficiency of evaluation. Hence, we will
take a closer look in this area.
Some of the work in this area involves parallelization of
mutation analysis using MIMD [25] and SIMD [26]
machines, in HPC systems [27], and using Hadoop [28].

Two algorithms try to reduce the number of mutants to be evaluated by
identifying which tests test which mutants. The first called lazy mutation
analysis by Fleyshgakker [29]
which uses weak mutation kills to identify which tests to run on which
mutants. A less stringent approach is to use code coverage for the same purpose [2].

Mutant schemata [30] is a technique that encodes all
mutations into a meta mutant. The particular mutant to be executed is passed to
the meta mutant as a command line argument or an
environment variable.
Just et al. [3] show that not all
mutations result in a unique state, and many mutants can be represented by a
single execution.
Split-stream execution [4, 5, 6]
is another technique that tries to reduce the redundancy in mutation executions.
In this technique, the mutants are forked off from the execution only after
encountering the particular mutation in the original. The equivalence modulo
states approach [7] combines partitioning states with
execution forking to further reduce the redundancy in pre-divergence execution.

§ THREATS TO VALIDITY

§.§ Threats to External Validity

Threats to external validity are factors that may reduce the generalizability of
our findings. Our approach is implemented only as a prototype. Further, the
subjects were chosen such that they were small, contained operations only on
primitive data types such as int> and float>. Hence, the results from our
evaluation is not a proof of generality of our technique, rather that the
technique is a promising direction. Indeed, we accept that any number of
uncontrolled parameters such as the subject type, test suites, the mutation
operators used, all can have an impact on the amount of execution saving
accomplished. We propose to study these in detail in future work.

§.§ Threats to Internal Validity

Threats to internal validity are factors concerning the judgment of cause and
effect relationships. We have used the number of statements executed by the
Python runtime as an indication of the effectiveness of the technique.
However, this assumes that the supporting infrastructure code can be
optimized such that the actual program execution forms the largest chunk.
While we believe that this is a reasonable assumption, it is possible
that the infrastructure code can't be optimized as heavily as we expect, and
this may lead to a lose in efficiency. This is a threat to validity that we
acknowledge. Further, software bugs are a fact of life, and it is possible
that we may have bugs in our implementation leading to faulty measurements.
This is also another threat that we acknowledge. The mitigation of these
threats will also form our future work.

§ LIMITATIONS AND FUTURE WORK

Our implementation is only a prototype. Hence it is subject to a large number of

§.§ Theory

* When control-flow divergence is detected, only mutants in the current
execution path continue. This means that the computations carried out in
execution taints of the wounded mutants are discarded.

* In a function, after the control-flow divergence, we only merge the
execution at the function return. However, there could be other parts
especially after the diverged control-flow structure finishes where
the execution may be shared. This execution path is not currently shared.
(This limitation is true only about the execution path within the function.
As soon as a function call is made from the control-flow with the same
parameters, the computation is shared across mutants.)
Even if one merges the execution flow immediately after the control-flow
structure finishes, there may be parts of control-flow where different
branches are similar, but do not share the execution.

* Shared with split stream and equivalence modulo state: Flow that
requires single-shot initialization can't be handled.

§.§ Prototype

* Only a limited number of mutation primitives are implemented.

* Only integers and floats are implemented.

* We do not consider globals.

* Multi-threaded programs, programs using fork

* Programs using IPC.

Faster Mutation Analysis with Fewer Processes and
Smaller Overheads

§ CONCLUSION

Mutation analysis is an effective but costly method for evaluating test suite
quality. The main problem is that independent evaluation of individual mutants
involve a large amount of redundancy due to similar pre-divergence and
post-mutation executions.
Previous work explored methods to reduce the pre-divergence execution. However,
post-mutation execution has remained unsolved. We describe a novel method based
on execution taints that can merge post-mutation execution, and hence avoid
post-mutation execution redundancy.

[1]
R. Gopinath, “On the limits of mutation analysis,” dissertation, Oregon State
University, 2017. [Online]. Available:

[2]
D. Schuler and A. Zeller, “Javalanche: Efficient mutation testing for java,”
in Proceedings of the 7th joint meeting of the European software
engineering conference and the ACM SIGSOFT symposium on The foundations of
software engineering, 2009, pp. 297–298.

[3]
R. Just, M. D. Ernst, and G. Fraser, “Efficient mutation analysis by
propagating and partitioning infected execution states,” in
Proceedings of the 2014 International Symposium on Software Testing and
Analysis.1em plus 0.5em minus 0.4emACM, 2014, pp. 315–326.

[4]
K. N. King and A. J. Offutt, “A fortran language system for mutation-based
software testing,” Software: Practice and Experience, vol. 21, no. 7,
pp. 685–718, 1991.

[5]
R. Gopinath, C. Jensen, and A. Groce, “Topsy-turvy: a smarter and faster
parallelization of mutation analysis,” in Proceedings of the 38th
International Conference on Software Engineering Companion, 2016, pp.

[6]
S. Tokumoto, H. Yoshida, K. Sakamoto, and S. Honiden, “Muvm: Higher order
mutation analysis virtual machine for c,” in 2016 IEEE International
Conference on Software Testing, Verification and Validation (ICST).1em plus 0.5em minus 0.4emIEEE, 2016, pp. 320–329.

[7]
B. Wang, Y. Xiong, Y. Shi, L. Zhang, and D. Hao, “Faster mutation analysis via
equivalence modulo states,” in Proceedings of the 26th ACM SIGSOFT
International Symposium on Software Testing and Analysis, 2017, pp.

[8]
J. Allen, “Perl version 5.8. 8 documentation-perlsec,”
<http://perldoc.perl.org/perlsec.pdf>, 2006, accessed: 2018-07-30.

[9]
B. Livshits, “Dynamic taint tracking in managed runtimes,”
Microsoft Research Technical Report, Tech. Rep. MSR-TR-2012-114, 2012.

[10]
V. Haldar, D. Chandra, and M. Franz, “Dynamic taint propagation for java,” in
21st Annual Computer Security Applications Conference
(ACSAC'05).1em plus 0.5em minus 0.4emIEEE, 2005, pp. 9–pp.

[11]
J. J. Conti and A. Russo, “A taint mode for python via a library,” in
Nordic Conference on Secure IT Systems.1em plus 0.5em minus
0.4emSpringer, 2010, pp. 210–222.

[12]
A. Zeller, R. Gopinath, M. Böhme, G. Fraser, and C. Holler, “Tracking
information flow,” in The Fuzzing Book.1em plus 0.5em minus
0.4emCISPA Helmholtz Center for Information Security, 2021, retrieved
2021-11-13 17:58:11+01:00. [Online]. Available:

[13]
J. Hunt, “Python properties,” in A Beginners Guide to Python 3
Programming.1em plus 0.5em minus 0.4emSpringer, 2019, pp.

[14]
D. Flanagan and Y. Matsumoto, The Ruby Programming Language: Everything
You Need to Know.1em plus 0.5em minus 0.4em" O'Reilly Media,
Inc.", 2008.

[15]
R. DeMillo, G. I. O. T. A. S. O. INFORMATION, and C. SCIENCE., Mutation
Analysis as a Tool for Software Quality Assurance, ser. GIT-ICS.1em
plus 0.5em minus 0.4emSchool of Information and Computer Science,
Georgia Institute of Technology, 1980. [Online]. Available:

[16]
R. A. DeMillo, R. J. Lipton, and F. G. Sayward, “Hints on test data selection:
Help for the practicing programmer,” Computer, vol. 11, no. 4, pp.
34–41, 1978.

[17]
M. Papadakis, M. Kintis, J. Zhang, Y. Jia, Y. Le Traon, and M. Harman,
“Mutation testing advances: an analysis and survey,” in Advances in
Computers.1em plus 0.5em minus 0.4emElsevier, 2019, vol. 112,
pp. 275–378.

[18]
A. V. Pizzoleto, F. C. Ferrari, J. Offutt, L. Fernandes, and M. Ribeiro, “A
systematic literature review of techniques and metrics to reduce the cost of
mutation testing,” Journal of Systems and Software, vol. 157, p.
110388, 2019.

[19]
A. J. Offutt, G. Rothermel, and C. Zapf, “An experimental evaluation of
selective mutation,” in Proceedings of 1993 15th international
conference on software engineering.1em plus 0.5em minus 0.4emIEEE, 1993, pp. 100–107.

[20]
W. E. Howden, “Weak mutation testing and completeness of test sets,”
IEEE Transactions on Software Engineering, no. 4, pp. 371–379, 1982.

[21]
A. J. Offutt and S. D. Lee, “How strong is weak mutation?” in
Proceedings of the symposium on Testing, analysis, and verification,
1991, pp. 200–213.

[22]
——, “An empirical evaluation of weak mutation,” IEEE Transactions
on Software Engineering, vol. 20, no. 5, pp. 337–344, 1994.

[23]
V. H. Durelli, J. Offutt, and M. E. Delamaro, “Toward harnessing high-level
language virtual machines for further speeding up weak mutation testing,” in
2012 IEEE Fifth International Conference on Software Testing,
Verification and Validation.1em plus 0.5em minus 0.4emIEEE,
2012, pp. 681–690.

[24]
D. Schuler and A. Zeller, “Checked coverage: an indicator for oracle
quality,” Software testing, verification and reliability, vol. 23,
no. 7, pp. 531–551, 2013.

[25]
A. J. Offutt, R. P. Pargas, S. V. Fichter, and P. K. Khambekar, “Mutation
testing of software using mimd computer.” in ICPP (2).1em plus
0.5em minus 0.4emCiteseer, 1992, pp. 257–266.

[26]
E. W. Krauser, A. P. Mathur, and V. J. Rego, “High performance software
testing on simd machines,” IEEE Transactions on Software Engineering,
vol. 17, no. 5, p. 403, 1991.

[27]
P. C. Cañizares, M. G. Merayo, and A. Núñez, “Eminent:
Embarrassingly parallel mutation testing,” Procedia Computer Science,
vol. 80, pp. 63–73, 2016.

[28]
I. Saleh and K. Nagi, “Hadoopmutator: A cloud-based mutation testing
framework,” in International Conference on Software Reuse.1em
plus 0.5em minus 0.4emSpringer, 2015, pp. 172–187.

[29]
V. N. Fleyshgakker and S. N. Weiss, “Efficient mutation analysis: A new
approach,” in Proceedings of the 1994 ACM SIGSOFT international
symposium on Software testing and analysis, 1994, pp. 185–195.

[30]
R. H. Untch, A. J. Offutt, and M. J. Harrold, “Mutation analysis using mutant
schemata,” in Proceedings of the 1993 ACM SIGSOFT international
symposium on Software testing and analysis, 1993, pp. 139–148.