Premium
It really does matter how you normalize the branch distance in search‐based software testing
Author(s) -
Arcuri Andrea
Publication year - 2013
Publication title -
software testing, verification and reliability
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.216
H-Index - 49
eISSN - 1099-1689
pISSN - 0960-0833
DOI - 10.1002/stvr.457
Subject(s) - heuristics , hill climbing , simulated annealing , computer science , range (aeronautics) , algorithm , graph , control flow graph , heuristic , control flow , mathematical optimization , mathematics , theoretical computer science , artificial intelligence , materials science , composite material , programming language
SUMMARY The use of search algorithms for test data generation has seen many successful results. For structural criteria like 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. Since the approach level is more important, the branch distance is normalized , often in the range [0, 1]. In this paper, different types of normalizing functions are analyzed. The analyses show that the one that is usually employed in the literature has several flaws. The paper presents a different normalizing function that is very simple and does not suffer from these limitations. Empirical and analytical analyses are carried out to compare these two functions. In particular, their effect is studied on commonly used search algorithms, such as Hill Climbing, Simulated Annealing and Genetic Algorithms. Copyright © 2011 John Wiley & Sons, Ltd.