Computational Intelligence - May 2017 - 47

Han Huang, Fangqing Liu, and Xiaoyan Zhuo
School of Software Engineering, South China University of Technology,
Guangzhou, China

Zhifeng Hao
School of Mathematics and Big Data, Foshan University, Foshan, China

every logic path of a given program should be covered (checked)
through testing. Path testing can significantly strengthen the process of identification of software bugs.The key is to find test cases
that can cover as many paths as possible (i.e., path coverage).
Automated test case generation for path coverage (ATCG-PC)
has attracted much research attention in the field of software
engineering since it was proposed [9].
The goal of ATCG-PC is to achieve path coverage by using
automated test case generation in a cost-efficient way. The cost
can be evaluated by the number of generated test cases and is
proportional to the computational effort of testing. It is known
[2], [3] that ATCG-PC can be modeled as an NP-complete
combinatorial optimization problem, which minimizes the
number of test cases while satisfying the path coverage requirement. Due to its NP-completeness, the ATCG-PC problem is
hard to solve. In particular, the difficulty in solving ATCG-PC
comes from two aspects. First, with regard to path coverage, the
relationship between the input (test case) and output (path) is
usually unknown, which means that it may require many
attempts before finding a test case suitable for covering a logic
path. Second, the relationship between the covered and uncovered paths is unclear, which means that it is difficult to figure
out uncovered paths with the covered ones. Intuitively, the process of test case generation (i.e., solving ATCG-PC) would be
efficient, if some heuristic information can be extracted from
the covered paths and used to guide generated test cases for
uncovered paths. However, due to the above-mentioned two
aspects, it is challenging to design an efficient algorithm for
ATCG-PC. This motivates our work.
Our study is summarized as follows.
1) We propose a self-adaptive fitness function and design a
modified differential evolution (DE) [4] algorithm for
ATCG-PC. The proposed self-adaptive fitness function
can reveal more information about the relationship
between the covered paths and uncovered paths.

Corresponding Author: Han Huang (E-mail: hhan@scut.edu.cn).

2) We conduct experimental analysis on eight benchmark
problems of ATCG-PC and verify that our proposed
algorithm can outperform the state-of-the-art solutions
for ATCG-PC.
The remainder of this paper is organized as follows. Section II
introduces the problem, followed by a brief review of ATCGPC. Section III presents the proposed self-adaptive fitness
function. Section IV introduces the modified DE algorithm.
Section V presents the results of the experiment. Section VI is
the conclusion.
II. Automated Test Case Generation

Given a system under test (SUT), software testing mainly aims
to detect as many faults as possible [5]. To measure the quality of
software testing, this study adopts path coverage as the adequacy
criteria, which will be defined first in this section. Then, based
on the path coverage, we formulate the optimization problem of
ATCG-PC in Subsection II.A. Furthermore, the related research
on ATCG-PC is briefly reviewed in Subsection II.B.
A. Problem Description

Given an SUT, we define the testing related concepts of path
and path coverage in Definition 1 and Definition 2, respectively according to [22].
Definition 1 (path): A path is a sequence of vertices, starting at some initial vertex and ending at some final vertex, where
each vertex is the branch condition of the tested program.
Definition 2 (path coverage): Path p is covered by test case x,
which means that p is generated by the execution of x.
Notice that, there may be a large number of candidate test
cases which need to be checked for a given SUT [7]. During
generation of test cases for path coverage, a tester needs to
select an optimal set of test cases at a reasonable cost and ensure
that the selected test cases meet certain coverage criteria (e.g.,
complete path coverage [22] meaning that 100% of paths are
covered by the test cases). Therefore, generating test cases for
path coverage can be modeled as a search or optimization
problem [6], which is to pick a minimal number of test cases

may 2017 | IEEE ComputatIonal IntEllIgEnCE magazInE

Table of Contents for the Digital Edition of Computational Intelligence - May 2017