Adaptive Path Selection

Random testing is a simple and well-known technique [3] which can be effective at finding software bugs. The family of algorithms around the work of Chen et al. on Adaptive Random Testing [1] attempt to maintain the be-nefit of random testing while increasing its efficiency. This method generates candidate inputs randomly, and at every step selects from them the best one. The best candidate is the test datum that is as far as possible than the already se-lected test data given some metric (Euclidean measure [1] for example). However, adaptive random testing may have some difficulties in providing high code coverage. For in-stance, the probability to select a candidate that activates the true branch of the conditional statement if (x==0) is equal to 1232 if x is a 32-bit integer program input. This paper presents preliminary work on adaptive path selection. Our approach aims at guiding the test data selec-tion such that a new test datum activates a path that is “as far as possible ” from already tested paths. Test datum selection is performed in three steps: 1) building the set of candidate paths, 2) selection of the best candidate given a set of al-ready tested paths and 3) generation of a test datum that ac-tivates the selected path. In this paper, we present a metric, called the path selector distance, that allows us to achieve the second step. The path selector distance aims at diver-sifying the set of tested path during the test data selection. For each step of the test datum selection, this distance per-mits us to select a path that activates some part of the source code as different as possible than the already tested path. In our future work, the combination of search-based [5] and constraint-based [2] approach will be used to achieve the first and the third step of the test data selection. Section 2 introduces the adaptive selection of paths on an example. Section 3 introduces the definition of the path se-lector distance. Section 4 concludes the paper and presents our future work. 2 Illustrating example Consider a program foo represented by its control flow graph in FIG. 1. The test data selection begins by uni