Information Technology Reference
In-Depth Information
It is easy to see that generating each new test case is an optimization process, i.e.,
finding a test case that maximizes the number of newly-covered target combinations.
There are dozens of well-known optimization techniques, such as meta-heuristic
search algorithms and branch-and-bound algorithms. Several one-test-at-a-time al-
gorithms based on heuristic search and optimization techniques have been proposed.
The problem of generating a new test case can also be translated into logic-based
optimization problem. In our CT test generation tool
Cascade
[
12
,
13
], the problem
is translated into a linear pseudo-Boolean optimization (PBO) problem. The linear
pseudo-Boolean optimization problem is identical to the 0-1 integer programming
problem, which has the following elements:
•
A set of Boolean variables, each of which takes the value of 0 or 1.
•
A set of linear pseudo-Boolean (PB) constraints specifying the restrictions the
solutions should conform to.
•
A pseudo-Boolean objective function specifying the goal to optimize.
Here, a PB constraint or a PB function is
linear
if it contains no multiplication of
Boolean variables. An example of linear PBO problem is as follows:
⎧
⎨
min
:
2
∗
x
1
+
3
∗
x
3
−
1
∗
x
5
1
∗
x
1
+
3
∗
x
4
+
1
∗
x
5
≥
2
(3.1)
1
∗
x
2
+
2
∗
x
3
+
1
∗
x
4
=
1
⎩
···
Now we translate the problem of generating each test case into a PBO problem
in the following way:
•
For each parameter
p
and one of its values
v
, we use a variable
A
, which is
(
p
,
v
)
true if and only if parameter
p
takes value
v
.
•
For each target combination
σ
, we use a variable
B
, which is true if and only if
σ
σ
is covered by the test case.
•
For each parameter
p
, suppose its value domain is
. The parameter
can take exactly one value. So we add the following PB constraint:
{
v
1
,
v
2
,...,
v
s
i
}
A
(
p
,
v
1
)
+
A
(
p
,
v
2
)
+···+
A
(
p
,
v
s
i
)
=
1
(3.2)
•
For each combination
σ
={
(
p
i
1
,
v
i
1
), (
p
i
2
,
v
i
2
),...,(
p
i
l
,
v
i
l
)
}
, it is covered if and
≤
≤
only if for 1
j
l
, parameter
p
i
j
takes value
v
i
j
. The following PB constraints
are generated:
−
B
σ
+
A
(
p
i
1
,
v
i
1
)
≥
0
;
−
B
σ
+
A
(
p
i
2
,
v
i
2
)
≥
0
;
···
(3.3)
−
B
σ
+
A
(
p
i
1
,
v
i
l
)
≥
;
0
l
−
A
(
p
i
j
,
v
i
j
)
+
B
σ
≥−
l
+
1
;
1
≤
j
≤
Search WWH ::
Custom Search