Download Implementation of a Transformation Algorithm

Kiran Lakhotia
MSc Individual Project Report September 2005
void main(int x)
{
…
if(x==0)
{
/*target branch to execute*/
}
…
}
Figure 2: This example shows a branch which is unlikely to be reached by chance
because the input domain of values leading to an execution of the target is just one
number. The entire input domain ranges from -32767 to 32767
2.2. Metaheuristic Search Techniques
The majority of the work attempting to automate structural testing has focused on
metaheuristic search techniques as a solution to the problem of finding adequate test cases.
By definition those techniques “begin with only an approximate method of solving a problem
within the context of some goal, and then use feedback from the effects of the solution to
improve its own performance.” [36], thus making them well suited to tackle search space
problems.
Metaheuristic searches require solutions, i.e. test cases, to be encoded in a way which allows
the search to manipulate them and order them according to better or worse solutions [17].
This ordering is crucial to any search technique because it effectively guides the search
towards a desired test case. For structural testing the goal is a specific branch of a program
and the solution is a test case leading to an execution of that branch.
The two most popular metaheuristic search techniques used for automated white box testing
are simulated annealing and genetic algorithms [25]. This paper only considers genetic
algorithms used for structural testing.
2.3. Evolutionary Testing
Evolutionary algorithms are based on simulating evolution of nature and the concept “survival
of the fittest” [3]. In terms of testing, evolutionary algorithms are applied to find the ‘fittest’ test
case: one that represents a global optimum in the search landscape. One particular type of
evolutionary
algorithms
are
genetic
algorithms.
These
use
methods
for
reproduction/recombination, mutation and fitness evaluation.
Genetic algorithms encode their solutions into a sequence of components. Often this is done
as a binary string, each bit representing a single chromosome. To begin, an initial population
of individuals is created randomly. The size of the population usually remains constant and its
individuals are replaced during the process of running the genetic algorithm.
Each individual in the population, also known as the genotype from the analogy to nature’s
evolution, gets assigned a fitness value, which is used to rank it within the population. This
value is computed via a fitness function, which forms the backbone to any genetic algorithm.
A robust fitness function distinguishes a genetic algorithm from a random search and
determines the level of performance of a genetic algorithm.
A number of different ways exist for ranking the individuals, for example linear ranking or
tournament selection [17]. Depending on the selection process, usually the fitter individuals
are used to form new ‘parents’ and by recombination create new ‘offspring’. Again, different
techniques such as ‘two point’ crossover exist for this process. Once new offspring have been
formed they are mutated at random, for example by flipping a bit in the binary sequence.
Consequently the genetic algorithm is run again with the newly created population and its
4