Identification of Potentially Infeasible Program Paths 
by Monitoring the Search for Test Data






unfeasibility, genetic algorithms


Structural testing criteria are used to 
select program structural components to be exercised 
by the tester. To satisfy a criterion 
means to exercise all the structural components 
required by the criterion through execution of 
the program. Selecting test data to exercise 
structural components is an extremely complex task 
as it requires a careful analysis of 
the program code, mental effort and knowledge 
of the underlying concepts of the testing 
criterion. Hence, automation of test data generation 
may provide a significant cost reduction in 
software testing. The presence of infeasible paths 
in a program is a crucial issue 
in structural testing. Infeasible paths in a 
program may mean that some required elements 
are also infeasible. The automatic determination of 
infeasible in paths as well as of 
infeasible required elements is an undecidable question. 
Solutions are partial, allowing the identification of 
unfeasibility in particular cases only. Commonly used 
approaches are: symbolic execution; theorem proving and 
static data flow analysis or numerical analysis. 
We present a tool and techniques for 
the automation of test data generation and 
infeasible paths identification. Korel's dynamic technique (test 
data generation based on the program's real 
execution and function optimization methods) and search 
based on Genetic Algorithms are used for 
test data generation. A dynamic heuristic is 
proposed for infeasible path identification. Genetic Algorithms 
are search algorithms based on evolution, natural 
selection and genetic mechanisms. Our Genetic Algorithm 
works with a population of input data. 
It repeatedly combines and selects previous inadequate 
input data with the objective of improving 
them. Better input data are selected using 
a fitness function based on control and 
data flow dynamic information to drive the 
search with a high precision. In our 
approach the Genetic Algorithm's search progress is 
monitored to address the unfeasibility issue. A 
heuristics identifies search progress absence by computing 
values of fitness improvements of successive generations 
of the Genetic Algorithm's search. If a 
persistent lack of progress is detected is 
the tester is warned about probable path 
unfeasibility. The major characteristics of our work 
are: use of a new fitness function 
that combines control and data flow information 
in the Genetic Algorithm to generate test 
data to execute program paths; and identification 
of probable unfeasibility of a given path 
through a new dynamic heuristics which monitors 
the Genetic Algorithm. A case study is 
presented detailing the heuristics proposed for unfeasibility 
treatment; results from the case study indicate 
that further effort is worthwhile.