A. Arcuri (2011)
It Really Does Matter How You Normalise the Branch Distance in Search Based Software Testing
Accepted for publication in Software Testing, Verification and Reliability
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 heuris tic 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 [0,1]. 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 normalising 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 commonly used search algorithms, such as Hill Climbing, Simulated Annealing and Genetic Algorithms.