Browse Prior Art Database

Criteria for Finite Sets of Paths that Characterize Control Flow

IP.com Disclosure Number: IPCOM000128007D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 10 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

Albert L. Baker: AUTHOR [+5]

Abstract

"Paths" is a frequently used term in software measures research. It is tacitly understood that a path is a possible execution sequence through a pro-gram or its corresponding ijowgraph. 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 deriving, new criterion, we define the concept of fiowgraph loop (as opposed to cycle) 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. 'Dr. Baker is currently a Shell Faculty Fellow, supported in part by the Shell Companies Foundation, Inc. :Capt. Howatt is attending Iowa State University under the sponsorship of the Department of Electrical Engineering, Air Force Institute of Technology, Wright-Patterson AFB, OH.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Criteria for Finite Sets of Paths that Characterize Control Flow

by

Albert L. Baker` James W. Howattfi James M. Bieman

Technical Report #85-19

July 1985

ABSTRACT

"Paths" is a frequently used term in software measures research. It is tacitly understood that a path is a possible execution sequence through a pro-gram or its corresponding ijowgraph. 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 deriving, new criterion, we define the concept of fiowgraph loop (as opposed to cycle) 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. 'Dr. Baker is currently a Shell Faculty Fellow, supported in part by the Shell Companies Foundation, Inc. :Capt. Howatt is attending Iowa State University under the sponsorship of the Department of Electrical Engineering, Air Force Institute of Technology, Wright-Patterson AFB, OH.

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-terion. We analyze this new criterion using the same context with favorable results. Also, we argue that one of the seemingly desirable properties is unob-tainable.

Iowa State University Page 1 Dec 31, 1...