Automatic generation of path covers

Arnong the fundarnentai problems computer program testing must deal with, there is that of selecting a significant sarnple of executions out of the potentially infinite execution domain. In this paper, structural testing is treated and, precisely, an algorithm is presented which finds a subset of prograrn control flow paths satisfying the branch testing criterion, i.e. every program' s branch is covered at least once. The minimal number of paths is found for acyclic structured programs. Being recursive, the algorithm is very simple. The analysis is based on a reduced flowgraph representation of programs, called ddgraph, and uses two relationships, dominance and implication, defined between the arcs of a ddgraph. Specifically, these relationships make it possible to identify a subset of arcs, called unconstrained, having the property that, when the unconstrained arcs are exercised, the coverage of all the other arcs in the ddgraph is also guaranteed. Properties of ddgraph arcs are extensively discussed. A proof of correctness and a theoretical evaluation of the algorithm are given. Application to the structural testing of real programs is straightforward and has been experimented in a prototype too1.