On program path analysis

Path analysis is widely used in software engineering, e.g. for structural complexity measurement and white-box testing. We propose a novel approach to path analysis, in which the ddgraph model is used to represent program control flow, and the dominance and the implication relationships, defined between ddgraph's arcs, are exploited to analyze program structural properties. Dominance and implication form two trees of ddgraph arcs, the dominator tree and the implied tree, respectively, which allow us to design very simple, recursive algorithms. In this paper, we present the algorithm ALL-1-PATHS, which enumerates all possible paths through a program with zero and one iteration of every cycle, and the algorithm I-PATHS-NUMBER, which calculates their number. Our approach 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.