Browse Prior Art Database

Data Dependency Analysis

IP.com Disclosure Number: IPCOM000128641D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 10 page(s) / 35K

Publishing Venue

Software Patent Institute

Related People

Richard Bisbey II: AUTHOR [+6]

Abstract

In order to understand the structure of computer programs and to detect certain types of protection errors in computer operating systems, it is often necessary to determine the flow of data both within single programs and among programs. The report describes a simple technique, data dependency analysis, for automatically generating this information from the static source representation of programs. The report also describes an experimental implementation used to determine the data. flow of PL/1 programs taken from the Multics operating system.

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

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Data Dependency Analysis

Richard Bisbey II Jim Carlstedt Dale Chase Dennis Hollingworth

ARPA ORDER NO. 1223 ISIIRR-76-43 February 1976 INFORMATION SCIENCES INSTITUTE

X676 Admiralsy WaylMarinadel Rey/California 90291 (213) 822-1 S 11 UNIVERSITY OF SOUTHERN CALIFORNIA f-T77 THIS RESEARCH IS SUPPORTED BY THE ADVANCED RESEARCH PROJECTS AGENCY UNDER CONTRACT NO. DAHC15 72 C 0306. ARPA ORDER NO. 2223 , PROGRAM CODE NO. 3D30 AND 3P10. VIEWS AND CONCLUSIONS CONTAINED IN THIS STUDY ARE THE AUTHOR'S AND SHOULD NOT BE INTERPRETED AS REPRESENTING THE OFFICIAL OPINION OR POLICY OF ARPA. THE U.S. GOVERNMENT OR ANY OTHER PERSON OR AGENCY CONNECTED WITH THEM.

THIS DOCUMENT APPROVED FOR PUBLIC RELEASE AND SALE: DISTRIBUTION IS UNLIMITED.

ABSTRACT

In order to understand the structure of computer programs and to detect certain types of protection errors in computer operating systems, it is often necessary to determine the flow of data both within single programs and among programs. The report describes a simple technique, data dependency analysis, for automatically generating this information from the static source representation of programs. The report also describes an experimental implementation used to determine the data. flow of PL/1 programs taken from the Multics operating system.

PREFACE

Because of the urgent security requirements of many existing general-purpose operating systems, the large investment committed to such systems, and the large number of protection errors embedded in them, the problem of finding such errors is one of major importance. This report describes a set of programs useful for understanding the structure of programs and for finding operating system protection errors resulting from incorrectly validated operands of critical operators. A discussion of the general error type can be found in Validation o/' Critical Variables [Carlstedt 76].

This work has been performed under Advanced Research Projects Agency Contract DAHC15 72 C 0308. It is part of a larger effort to provide securable operating systems in DOD environments.

1. DETERMINING DATA DEPENDENCIES

In the course of examining an operating system for protection errors, one is presented with two recurring problems:

University of Southern California Page 1 Dec 31, 1976

Page 2 of 10

Data Dependency Analysis

1. To determine, for any given operator in the operating system, if its operands can be affected by user data.

2. To determine all of the operators within the operating system whose operands can be affected by user data.

Operators whose operands are affected by user data must be scrutinized carefully to insure that erroneous or unanticipated data does not result in a protection error. To aid in finding protection errors of this type, one is interested in a practical automatic method for identifying operating system variables so affected" even in cases of many intervening levels of subroutine calls.

Symbo...