PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertolino A., Marre' M. Automatic generation of path covers. Internal note IEI-B4-59, 1992.
 
 
Abstract
(English)
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.
Subject Algorithmic complexity
Automated testing tools
Ddgraph
Path cover
Program testing
S1-structured programs
Uncostrained arcs
Weakly incomparable arcs


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional