Automatic Generation of Path Covers Based on the Control Flow Analysis of Computer Programs

Branch testing a program involves: 1) generating a set of paths that will cover every arc in the program flowgraph, called a path cover; 2) finding a set of program inputs that will execute every path in the path cover. The generation of path covers can be performed through the analysis of program control flow and can be automated, but, inevitably, statically generated path covers may include infeasible paths. The method used for path generation should attempt to reduce the incidence of this problem. The paper presents a generalized algorithm that finds a path cover for a given program flowgraph. The analysis is conducted on a reduced flowgraph, called a ddgraph, and uses graph theoretic principles differently than previous approaches. In particular, the relations of dominance and implication which form two trees of the arcs of the ddgraph are exploited. These relations make it possible to identify immediately a subset of ddgraph arcs, called unconstrained arcs, having the property that a set of paths exercising all the unconstrained arcs will also cover all the arcs in the ddgraph. In fact, the algorithm has been designed to cover all the unconstrained arcs of a given ddgraph: The paths are derived one at a time, each path covering at least one as yet uncovered unconstrained arc. The greatest merits of the algorithm are its simplicity and its flexibility. It consists in just visiting recursively in combination the dominator and the implied trees and is flexible in the sense that it can derive a path cover to satisfy different requirements, according to the strategy adopted for the selection of the unconstrained arc to be covered at each recursive iteration. This feature of the algorithm can be employed to address the problem of infeasible paths, by adopting the most suitable selection strategy for the problem at hand. Embedding of the algorithm into a software analysis and testing tool is recommended. © 1994 IEEE