Faster Mutation Analysis via Equivalence Modulo States ISSTA’17, July 10-14, 2017, Santa Barbara, CA, USA
test as a dierent input data, we can parallelize the execution of
dierent tests on one mutant on a SIMD machine.
Finally, in the application of evaluating a test, several papers [
28
,
65
,
66
] propose to prioritize the tests for each mutation so that this
mutation shall be killed quicker. e works are orthogonal to ours
and can be used together with AccMut.
3 BASIC FRAMEWORK OF ACCMUT
3.1 Overview
We rst describe the redundant execution that AccMut avoids with
an example in the following code snippet and in Figure 1. In func-
tion
foo
, the line 6 is a computation intensive function without
side-eects. e test driver function is
test foo
, which sets the
parameter
a
to
1
and then judges the result. Let us assume that
three mutants are generated in the function
foo
. Mutant 1 (M1)
changes
a = a + 1
at line 3 into
a = a << 1
. Mutant 2 (M2) and
Mutant 3 (M3) change
a = a / 2
at line 5 into
a = a + 2
and
a = a
* 2, respectively.
In standard mutation analysis, we execute all mutants for each
test and obtain their testing results. We show the execution of the
three mutants in Figure 1(b), (c) and (d), and the execution of the
original program in Figure 1(a) as a reference.
1 i n t foo ( i n t a ) {
2 i n t i , r e s ;
3 a = a + 1 ; / / M1 : a << 1
4 f o r ( i = 0 ; i < 2 ; i ++){
5 a = a / 2 ; / / M2 : a + 2 , M3 : a ∗ 2
6 r e s += tim e cons u m i n g ( a ) ;
7 }
8 r e t u r n r e s ;
9 }
10 void t e s t f o o ( ) {
11 a s s e r t ( f o o ( 1 ) == RESULT ) ;
12 }
e circles represent system states and the states with the same
number are the same. e states are captured at the program point
listed on the le of Figure 1. e arrows represent the transition
of states aer the executions of statements. And the length of
the arrows means the execution eort during the transition. If
two transitions have the same starting state and the same ending
state, the two transitions are redundant. To show the redundancy
between states and transitions, we use the brightness of circles
and the thickness of arrows respectively. e darker a circle is, or
the thicker an arrow is, the more redundant the state/transition
is. As we can see from Figure 1(b), (c) and (d), there are several
redundant transitions among the three mutant executions. First, as
the parameter
a
of
f oo
is set to 1 in this test (State 1), the results of
a = a +
1 and
a = a <<
1 both equal to 2 (State 2). As a result, the
transitions before entering the loop, i.e., transitions to State 1 and
transitions between States 1 and 2, are redundant among the three
mutants. Second, during the rst loop
a =
2, the states of
a = a +
2
and
a = a ∗
2 are the same, and thus the transitions between States
2 and 5 in M2 and M3 are also redundant. Note that these two
transitions involve the call to a time-consuming function which
can induce high cost of redundancy, so the length of the arrows
during the loop is much longer.
Figure 1(e) exhibits the execution of the mutants in split-stream
execution. In split-stream execution, all mutants start as one main
process, and are later split from the main process at the rst mutated
statements. e main process of our example is shown in the rst
column in Figure 1(e). M1 is split as a new process aer State 1,
and later M2 and M3 are split as new processes aer State 2. We
need to keep the main process as more mutants may be split from it.
Some of the redundancy is removed in split-stream execution. For
example, the transition to State 1 is shared among all the mutants
as well as the main process. However, two types of redundancy
still exists. First, the transitions between State 1 and 2 are the same
between the main process and M1, and thus it is not necessary to
split M1 from the main process. Second, although it is necessary
to split M2 and M3 aer State 2, the transitions between State 2
and State 5, which involve calling the time-consuming function,
are still redundant among the two split processes.
Our approach, AccMut, tries to further reduce the redundancy
in execution by exploiting the equivalence modulo the current
state. An execution of the three mutants in AccMut is shown in
Figure 1(f). Dierent from split-stream execution, AccMut rst
classies the next statements in dierent mutants into equivalent
classes modulo the current state, and uses one process to represent
each equivalent class. As a result, rst, since the mutated statement
in M1 is equivalent to the original statement modulo State 1, we
would not split a new process for M1. Second, the two mutated
statements in M2 and M3 are equivalent modulo State 2, so we split
only one process for them. As a result, the redundant transitions in
Figure 1(e) are all removed in Figure 1(f).
More concretely, at each state of each process, we conduct a
trial execution of the statements and collect their changes to the
system state. en we cluster their changes to the system state into
equivalence classes. If the number of equivalence classes is more
than one, say
n
, we split
n −
1 new processes. Each forked process
represents the mutants in one equivalence class, and we apply the
change from the equivalence class to the state of the forked process.
Finally, the change from the remaining equivalent class is applied
to the original process, and the original process now represents
only the mutants in the remaining class. is process continues for
each process until all processes terminate.
However, in practice it may be expensive to store and cluster
the changes, especially when a statement makes a large set of
changes. For example, if a statement calls a procedure with a large
side eects, i.e., changing many memory locations, it may not be
ecient to record the changes of all memory locations and compare
the changes from dierent mutants.
To solve this problem, in AccMut we record abstract changes
rather than concrete changes. An abstract change stores oen much
less information than a concrete change, but nevertheless allows
the application of the change to the system state. For example, the
change of a procedure call can be represented abstractly by the
address of the procedure and all arguments passed to the procedure,
rather than all concrete changes produced by the procedure. When
we need to apply the change to system, we just actually invoke the
method with the arguments. In this way, we record only a small
amount of information allowing us to eciently store and cluster
the changes.
297