Browse Prior Art Database

Criteria for Finite Sets of Paths that Characterize Control Flow Disclosure Number: IPCOM000148438D
Original Publication Date: 1985-Jul-31
Included in the Prior Art Database: 2007-Mar-29
Document File: 22 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Baker, Albert L.: AUTHOR [+4]


Albert L. ~ake?

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 22

Criteria for Finite Sets of Paths that Characterize Control Flow

Albert L. ~ake?

James W. Howattt

James M. Bieman

Technical Report #85- 1 9
July 1985


   "Paths" is a frequently used terrn in software measures research. It is tacitly understood that a path is a possible execution sequence through a pro- gram or its corresponding flowgraph. For purposes of defining measures the usually infinite set of all paths through a program is clearly of little value, and so we must have finite sets that are related to the infinite set.

   We present a formal analysis of the possible relationships between finite sets of execution paths and the corresponding infinite set. In the analysis, we define the concept of path subset criterion and describe five desirable properties of criteria. We review several published criteria and find each approach to be in some sense deficient. The analysis leads to a new path subset criterion. In derivin the new criterion, we define the conctyt of flowgraph loop (as opposed lo cycle 3 and a path tree characterization of loop structure.

   We find that the new criterion has four of the five desirable properties; the remaining property is shown to be unobtainable. The new criterion can serve as a rigorous basis for future path-based complexity measures and testing metho- dologies.

* ~ r .

      Baker is currently a Shell Faculty Fellow, supported in part by the Shell Companies Foundation, Inc.

    apt. Howatt is attending lowa State University under the sponso~ship of the Department of Electrical Engineering. Air Force Institule of Technology, Wright-Patterson AFB. OH.

[This page contains 1 picture or other non-text object]

Page 2 of 22

[This page contains 1 picture or other non-text object]

Page 3 of 22

1. Introduction

   The number of' execution paths through a program has been the subject of considerable software measures research. The major stumbling block in this research is that programs containing loops have a possibly infinite number of such paths. Thus measures based on "path counts'' must, in fact, be based on finite subsets of the exhaustive set of all execution paths. Often published cri- teria for defining these subsets are informally described, and rarely is the rela- tionship of the subset to the exhaustive set carefully analyzed.

   We present a formal definition of a path subset criterion and several pro- perties which are possible relationships between the finite subsets of execution paths and the corresponding exhaustive set. Several subset characterizations from the published literature are reviewed in the context of this definition of criterion and these properties.

   From this review the authors observe an important difference between the programmers notion of loop and the graph-theoretic notion of cycle. We define "loop" for arbitrary flowgraphs and use loops to define a new path subset cri-...