Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 28

that the Pareto front is dominantly produced by NSGA-II. Solutions generated
by NSGA-II form the widest Pareto front that represents the trade-off between
the cost and the expected profit (score).

8.3 Case Study: Structural Test Data Generation

Since the costs of manual software testing are extremely high, the software en-
gineering community has devoted a lot of attention to researching methods of
automating the process. The problem of generating structural test data, i.e. test
data that attempts to execute all of a program's paths, program statements or
true and false decisions, is one area that has attracted a lot of interest, particu-
larly with respect to branch coverage; motivated by the prevalence of its variants
in software testing standards.
To motivate the use of Search Based Software Engineering in this context, the
program of Figure 15 will be studied, with the aim of generating a test suite that
covers each of its individual branches. It is a program for evaluating a Chemical
Abstracts Service (CAS) registry number assigned to chemicals. Each number
is a string of digits separated by hyphens, with the final digit serving as a check
digit. The routine takes a pointer to the first character of the string, processes
it, and returns zero if the number is valid. An error code is returned in the case
the number is not valid.

Definition. Let I =( i 1 ,i 2 , ...i len ) be a vector of the input variables of a program
under test, p . The domain D i n of the input variable i n is the set of all values that
i n can hold, 1

.The input domain of p is a cross product of
the domains of each of the individual input variables: D = D i 1 ×

≤ n ≤ len ; len = | I |

D i 2 ... × D i len .

An input to the function under test is a specific element of the function's input

domain, that is,

i

D .
Given a target structure t in p , the problem is to find an input vector

i ∈

I ∈ D

such that t is executed.

Representation. Defining a representation for structural test data generation
simply involves a method of encoding the input vector to a program. This is
straightforward for program units such as functions involving primitive types
such as integers, reals or characters, as the input vector can be manipulated
directly by the search algorithm or trivially encoded into a binary format. How-
ever, programs involving arrays or dynamic data structures require more careful
handling. In order to avoid a multi-length encoding, the size and shape of the
data structure may need to be fixed. However research has been undertaken to
remove this restriction [60]. For the CAS check routine, the representation is a
sequence of integer values in the range 0-255, fixed to a length of 15. In this
case, the whole range of the char type is used. For primitive types with large
domains, however, the tester may wish to restrict the domains to sensible limits
or a legal range of values.