Bertolino A., Marre' M. Automatic generation of path covers based on the control flow analysis of computer programs. In: IEEE Transactions on Software Engineering, vol. 20 (12) pp. 885 - 899. IEEE, 1994. |

Abstract (English) |
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 or 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 tlowgraph. 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 or ddgraph arcs, called unconstrained arcs, having the property that a set or paths exercising all the unconstrained arcs will also cover all the arcs in thc ddgraPh. Infact, 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 are. 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 are 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. | |

Subject | Automated testing tool branch testing ddgraph dominator tree implied tree infeasible path path cover unconstrained arc D.2.5 Testing and Debugging |

1) Download Document PDF |

Open access Restricted Private