Title :
It Does Matter How You Normalise the Branch Distance in Search Based Software Testing
Author_Institution :
Simula Res. Lab., Lysaker, Norway
Abstract :
The use of search algorithms for test data generation has seen many successful results. For structural criteria such as branch coverage, heuristics have been designed to help the search. The most common heuristic is the use of approach level (usually represented with an integer) to reward test cases whose executions get close (in the control flow graph)to the target branch. To solve the constraints of the predicates in the control flow graph, the branch distance is commonly employed. These two measures are linearly combined. Because the approach level is more important, the branch distance is normalised, often in the range. In this paper, we analyse different types of normalising functions. We found out that the one that is usually employed in the literature has several flaws. We hence propose a different normalizing function that is very simple and that does not suffer of these limitations. We carried out empirical and analytical analyses to compare these two functions. In particular, we studied their effect on two commonly used search algorithms, namely Simulated Annealing and Genetic Algorithms.
Keywords :
genetic algorithms; program testing; simulated annealing; tree searching; branch coverage; branch distance; control flow graph; genetic algorithm; heuristics; normalizing function; search algorithm; search based software testing; simulated annealing; structural criteria; test data generation; Application software; Automatic control; Data flow computing; Flow graphs; Genetic algorithms; Laboratories; Simulated annealing; Software algorithms; Software engineering; Software testing; Branch Distance; Genetic Algorithms; Search Based Software Testing; Simulated Annealing; Test Data Generation; Theory;
Conference_Titel :
Software Testing, Verification and Validation (ICST), 2010 Third International Conference on
Conference_Location :
Paris
Print_ISBN :
978-1-4244-6435-7
DOI :
10.1109/ICST.2010.17