Adaptive approaches to structural software testing (abstract only)

Structural testing involves the methodical exercising of a program f according to selected criteria for coverage of the program flowgraph (e.g., branch-coverage or statement-coverage). Conventional strategies rely on the pre-selection of paths sufficient to provide the desired coverage, with input vectors then chosen to execute this collection of paths (Figure 1): While selecting a set P is not difficult, finding X can be most challenging — involving Boolean satisfiability of full path predicates, backward substitution, or symbolic execution of the paths, often composed of numerous decisions and assignments (Prather, 1983). During this process of finding X, however, some of the paths in P may prove to be infeasible (i.e., there are no inputs that will cause traversal of those paths). Then, like it or not, we are forced to return to the development of additional paths for P.With adaptive strategies, on the other hand, we do not require the pre-selection of P; we not only acknowledge the intrinsic interplay between P and X, we exploit it. Adaptive strategies construct P path-by-path using feedback from previous inputs and their paths of execution (Figure 2): X0 = {X0}, Xk = Xk-1∪{xk} P0 = O, Pk = Pk-1∪ {Pk} Here the initial input x0, possibly chosen arbitrarily, will cause the traversal of some path p1. Then at any later stage, G and Pi are compared to find a new input xi to achieve coverage beyond that already attained, leading, of course, to a new path pi+1. Finally, at the conclusion of these iterations, a comparison of G and Pi will indicate that total coverage under the desired criterion has been accomplished.An early adaptive strategy (Kundu, 1979) required a sort of “diagonalization” of all the path predicates available at any stage to find an input x satisfying none of those predicates, thereby assuring a new path generated by f(x). A more recent approach (Prather and Myers, to appear), the path-prefix strategy, makes use of partial paths — “reversible” path prefixes — to find the next input to provide new coverage.That is, in Figure 3 for the case of branch-coverage, if p is a path representative of those already traversed, the reversible prefix q is the part of p to the first decision node that still has an uncovered branch D+. So now an input Xnew is found to traverse q but to deviate from p at D+. At each stage the shortest such prefix among all the paths in Pi is selected for reversal. Of course, additional “collateral” coverage is generally obtained when the resulting full path is traversed.Now, even using conventional means, finding inputs to traverse prefixes is a simpler problem than for traversing entire pre-selected paths. Indeed, work in progress shows that the adaptive approaches in general are less resource-intensive than conventional approaches (Myers, 1986). Moreover, the number of paths finally contained in P is within the theoretical bounds for any path selection procedure available to assure a given type of coverage. The use of a previously traversed prefix and its associated input vector xpray leads to the possibility of employing non-conventional, feedback oriented means to find the input xnew. Having traversed the prefix q, we are “close” to its reversal, allowing for a presumably slight modification of xprev to obtain xnew by such means.But even in the path-prefix strategy, a condition of “relative” infeasibility can occasionally arise. That is, in Figure 3, the branch D+ may be feasible in that some executable path will traverse D+, but not through any of the available prefixes through D. A loosening of the strategy is possible at this point, however, incorporating conventional path/input selection: any partial path traversing D+, and its associated input, will suffice. Working with this partial path to determine xnew will still be easier than with a full pre-selected path.Overcoming any instances of relative infeasibility is one advantage deriving from the interactive nature of adaptive testing. The feedback loop (Figure 2) allows for considerable participation by the user. As another example, the initial input(s) can be chosen to achieve any desired functional (“black box”) testing or to traverse certain paths of particular interest to the user. The resulting coverage is then incorporated in the ensuing iteration of an adaptive strategy.