VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 28-38
Generating Test Data for Software Structural Testing using
Particle Swarm Optimization
Dinh Ngoc Thi*
VNU University of Engineering and Technology, 144 Xuan Thuy, Cau Giay, Hanoi, Vietnam
Abstract
Search-based test data generation is a very popular domain in the field of automatic test data generation.
However, existing search-based test data generators suffer fromsome problems. By combining static program
analysis and search-based testing, our proposed approach overcomesone of these problems. Considering the
automatic ability and the path coverage as the test adequacycriterion, this paper proposes using Particle Swarm
Optimization, an alternative search technique, for automating the generation of test data for evolutionary
structural testing. Experimental results demonstrate that our test data generator can generate suitable test data
with higher path coverage than the previous one.
Received 26 Jun 2017; Revised 28 Nov 2017; Accepted 20 Dec 2017
Keywords:Automatic test data generation, search-based software testing, Particle Swarm Optimization.
1. Introduction*
as an efficient and necessary method in order to
Software is amandatory part of today's life,
and has become more and more important in
current information society. However, its
failure may lead to significanteconomic loss or
threat to life safety. As a consequence, software
qualityhas become a top concern today. Among
the methods of software quality assurance,
software testing has been proven as one of the
effective approachesto ensure and improve
software quality over the past threedecades.
However, as most of the software testing is
being done manually, the workforce and cost
required are accordingly high [1]. In general,
about 50 percent of workforce and cost in the
software development process is spent on
software testing [2]. Considering those reasons,
automated software testing has been evaluated
reduce those efforts and costs.
Automated structural test data generation is
becoming the research topic attracting much
interest in automated software testingbecause it
enhances the efficiency while reducing
considerably costs of software testing. In our
paper, we will focus on path coverage test data
generation, considering that almost all structural
test data generation problems can be transformed
to the path coverage test datageneration one.
Moreover, Kernighan and Plauger [3] also pointed
out that path coverage test data generation can
find out more than 65 percent of bugs in the given
program under test (PUT).
Although path coverage test data generation
is the major unsolved problem [20], various
approaches have been proposed by researchers.
These approaches can be classified into two
_______
* E-mail.: dinhngocthi@gmail.com
https://doi.org/10.25073/2588-1086/vnucsce.165
types: constraint-based test data generation
(CBTDG) or search-based test data generation
(SBTDG).
28
D.N. Thi / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 28-38
29
Symbolic execution (SE) is the state-of-the-
maxDay=30;
art of CBTDG approaches [21]. Even though
else //bch6: branch 6
there have been significant achievements, SE
maxDay=31;
still faces difficulties in handling infinite loops,
}
array, procedure calls and pointer references in
else //bch7: branch 7
each PUT [22].
maxDay=-1;
There are also random testing, local search
return maxDay;
[10], and evolutionary methods [23, 24, 25] in
}
SBTDG
approaches.
As
the
value
of
input
Regarding this PUT, Mao [9] used PSO to
variables is assigned when a program executes,
generate test data through building the one and
problems encountered in CBTDG approaches
only
fitness
function
which
was
the
can be avoided in SBTDG.
combination
of
Korel
formula
[10]
and
the
Being an automated searching method in a
branch
weights.
This
proposal
has
two
predefined space, genetic algorithm (GA) was
weaknesses:
the
branch
weight
function
is
applied to test data generation since 1992 [26].
entirely performed manually and some PUTs
Micheal et al [22], Levin and Yehudai [25],
are not able to generate test data to cover all test
Joachim
et
al
[27]
indicated
that
GA
paths. To overcome these weaknesses, we still
outperforms other SBTDG methods e.g. local
use
PSO to
generate test data for the given
search or random testing.However eventhough
PUT. However, unlike Mao, our approach is to
they
can
generate
test
data
with
appropriate
assign one fitness function for each test path.
fault-prone ability [4, 5], they fail to produce
Then we will use simultaneous multithreading
them quickly due to their slowly evolutionary
of
PSO
to
simultaneously
find
the
solution
speed.
Recently,
as
a
swarm
intelligence
corresponding to this fitness function, which is
technique, Particle Swarm Optimization (PSO)
also the one able to generate test data for this
[6, 7, 8] has become a hot research topic in the
test path.
area
of
intelligent
computing.
Its
significant
The
rest
of
this
paper
is
organized
as
feature is its simplicity and fast convergence
follows:
Section
2
gives
some
theoretical
speed.
backgroundon
fitness
function
and
particle
Even so, there are still certain limitations in
swarm
optimization
algorithm.
Section
3
current
research
on
PSO
usage
in
test
data
summarizes some related works, and Section 4
generation.
For
example,
consider
one
PUT
presents
the
proposed
approach
in
detail.
which was used in Mao’s paper [9] as below:
Section 5 shows the experimental results and
int getDayNum(int year, int month) {
discussions. Section 6 concludes the paper.
int maxDay=0;
if(month≥1 && month≤12){
//bch1: branch 1
if(month=2){ //bch2: branch 2
if(year%400=0||
(year%4=0&&year%100=0))
2. Background
This section describes the theoretical
background being used in our proposed
approach.
//bch3: branch 3
maxDay=29;
else //bch4: branch 4
maxDay=28;
}
else if(month=4||month=6||
month=9||month=11)
//bch5: branch 5
2.1. Fitness function
When using PSO, a test path coverage test
data generation is transformed into an
optimization problem. To cover a test path
during execution, we must find appropriate
values for the input variables which satisfy
related branch predicates. The usual way is to
30
D.N. Thi / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 33, No. 2 (2017) 28-38
use Korel’s branch distance function [10]. As a
then
it
searches
for
optima
by
updating
result, generating test data for a desired branch
generations. In every iteration, each particle is
is
transformed
into
searching
input
values
updated by the following two "best" values. The
which optimizes the return value of its Korel
first one is the best solution (fitness) achieved
function. Table 1 gives some common formulas
so far (the fitness value is also stored). This
which are used in branch distance functions. To
value
is
called
pbest.
Another
"best"
value
generate
test
data
for
a
desired
path
P,
we
tracked by the particle swarm optimizer is the
define a fitness function F(P) as the total values
best value, obtained so far by any particle in the
of
all
related
branch
distance
functions.
For
population. This best value is a global best and
these
reasons,
generating
path
coverage
test
called gbest.
data
can
be
converted
into
searching
input
After
finding
the
two
best
values,
the
values which can minimize the return value of
particle updates its velocity and positions with
function F(P).
the following equation (1) and (2).
Table 1. Korel’s branch functions for severalkinds of
branch predicates
Relational Branch distance function f(bchi)
predicate
Boolean if true then 0 else k
¬a negation is propagated over a
a = b if abs(a b)= 0 then 0 else abs(a
b)+ k
a b if abs(a b)0 then 0 else k
a<b if a b <0 then 0 else
abs(a b)+ k
[] = [] + 1 × () × ( [] −
[]) + 2 × () × ( [] −
[])(1)
[] = [] + [](2)
v[] is the particle velocity, persent[] is the
current particle (currentsolution). pbest[] and
gbest[] are defined as stated before. rand() is a
random number between (0,1). c1, c2 are
learning factors, usually c1 = c2 = 2.
The PSO algorithm is described by pseudo
code as shown below:
a b
a>b
a b
a and b
a or b
if a b ≤ 0 then 0 else
abs(a b)+ k
if b a >0 then 0 else
abs(b a)+ k
if b a ≥ 0 then 0 else
abs(b a)+ k
f (a)+ f(b)
min(f(a), f(b))
Algorithm 1: Particle Swarm Optimization (PSO)
Input: F: Fitness function
Output: gBest: The best solution
1: for each particle
2: initialize particle
3: end for
4: do
5: for each particle
Similar to Mao [9], we also set up the
punishment factor k = 0.1. Basing on this
formula, we will develop a function calculating
6: calculate fitness value
7: if the fitness value is better than the
best fitness value (pBest) in history
then
values at branch predication, which is will be
explained in the next part.
2.2. Particle Swarm Optimization
8: set current value as the new pBest
9: end if
10: end for
11: choose the particle with the best fitness
Particle Swarm Optimization (PSO) was
first introduced in 1995 by Kennedy and
Eberhart [11], and is now widely applied in
optimization problems. Compared to other
optimal search algorithms such as GA or SA,
PSO has the strength of faster convergent speed
and easier coding. PSO is initialized with a
group of random particles (initial solutions) and
value of all the particles as the gBest
12: for each particle
13: calculate particle velocity according
equation (1)
14: update particle position according
equation (2)
15: end for
16: while maximum iterations or minimum
criteria is not attained

Generating Test Data for Software Structural Testing using Particle Swarm Optimization

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 11 | FileSize: M | File type: PDF
0 lần xem

Generating Test Data for Software Structural Testing using Particle Swarm Optimization. This paper proposes using Particle Swarm Optimization, an alternative search technique, for automating the generation of test data for evolutionary structural testing. Experimental results demonstrate that our test data generator can generate suitable test data with higher path coverage than the previous one.. Cũng như các giáo án bài giảng khác được bạn đọc chia sẽ hoặc do tìm kiếm lại và giới thiệu lại cho các bạn với mục đích nâng cao trí thức , chúng tôi không thu tiền từ người dùng ,nếu phát hiện tài liệu phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho chúng tôi,Ngoài thư viện tài liệu này, bạn có thể download đề thi, giáo trình phục vụ nghiên cứu Một số tài liệu tải về sai font không xem được, thì do máy tính bạn không hỗ trợ font củ, bạn download các font .vntime củ về cài sẽ xem được.

Nội dung


1134941

Tài liệu liên quan