Path analysis and experimentation on path coverage via minimum test covers

This paper consists of two parts. In the first part we introduce our approach to program path analysis, in which the dominance and the implication relationships, defined between the arcs of a ddgraph, are exploited to analyse program structural properties. Dominance and implication form two trees of ddgraph's arcs, the dominator tree and the implied tree, respectively, which allow to design recursive, and thus very simple, algorithms for path analysis. For brevity, we shall present, as an example of the approach, one algorithm which derives a path expression representing all ddgraph's entry-exit paths. Path analysis is widely used for structural complexity measurement and white-box testing. In the second part of this paper, a recursive algorithm is presented which finds a subset of program paths satisfying the branch testing criterion, i.e. every program's branch is covered at least once. The (theoretical) minimal number of paths is found for acyclic structured programs. Application of our approach to the analysis and testing of programs is straightforward and is currently being experimented within a prototype tool, called BAT, which performs the static analysis of C programs for use in reverse engineering and in coverage testing.