Browse Prior Art Database

AN APPROACH TO CONCURRENT CONTROL FLOW CHECKING

IP.com Disclosure Number: IPCOM000128155D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 19 page(s) / 57K

Publishing Venue

Software Patent Institute

Related People

Stephen S. Yau: AUTHOR [+4]

Abstract

A control flow checking scheme capable of detecting control flow errors of programs resulted from software coding errors, hardware mal-functions, or memory mutilation during the execution of the program is presented. In this approach, the program is partitioned into intervals and a data base containing the feasible path information in each of the intervals is derived from the detailed design. The path in each interval actually traversed at run time is recorded and then checked against the information provided in the data base, and any discrepancy indicates an error. This approach is general, and can detect all uncompensated illegal branches. Any uncompensated error occurred during the execution of an interval that manifests itself as a wrong branch within the interval or right after the completion of execution of the interval are also detect-able. The approach can also be used to check the control flow in the testing phase of program development. Examples are given and the overhead of using this approach is discussed. Index Terms ' : Control flow checking, concurrency, program design, data base, control errors, algorithms, path representation, overhead. This work was supported by the U.S. Army Research Office Grant No. DAAG29-76-G-0183.

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

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN APPROACH TO CONCURRENT CONTROL FLOW CHECKING

Stephen S. Yau and Fu-Chung Chen Department of Electrical Engineering and and Computer Science Northwestern University Evanston, Illinois- 60201 A. UV

No. 79-04-CS-01

Abstract

A control flow checking scheme capable of detecting control flow errors of programs resulted from software coding errors, hardware mal-functions, or memory mutilation during the execution of the program is presented. In this approach, the program is partitioned into intervals and a data base containing the feasible path information in each of the intervals is derived from the detailed design. The path in each interval actually traversed at run time is recorded and then checked against the information provided in the data base, and any discrepancy indicates an error. This approach is general, and can detect all uncompensated illegal branches. Any uncompensated error occurred during the execution of an interval that manifests itself as a wrong branch within the interval or right after the completion of execution of the interval are also detect-able. The approach can also be used to check the control flow in the testing phase of program development. Examples are given and the overhead of using this approach is discussed.

Index Terms ' : Control flow checking, concurrency, program design, data base, control errors, algorithms, path representation, overhead.

This work was supported by the U.S. Army Research Office Grant No. DAAG29-76-G-0183.

INTRODUCTION

Errors may be introduced at each stage of software development process, such as specification errors, design errors and coding errors. Before a program is actually put into operation, it must go through a series of tests in the testing phase of program development. Most design errors and coding errors are found and corrected at this stage. However, there exists no testing strategy which can guarantee that once a program passes that test, the program is error-free. Consequently, dormant errors which are design or coding errors not detected by the testing scheme are likely to be present in most large-scale programs, and can be awakened at run time by some special combinations of inputs. Besides these dormant errors, other sources that can make a program unreliable are hardware malfunctions and memory mutilation. Unless some run-time checking is performed, the erroneous program outputs may not be detected and serious damages may result therefrom. For real-time systems, such as missile defense systems, air traffic control systems, patient monitoring systems, process control systems, electronic switching systems, etc., where high reliability is required, it is necessary to monitor the program run-time behavior and take appropriate actions when-ever any abnormality in data or control flow is detected.

Northwestern University Page 1 Dec 31, 1979

Page 2 of 19

AN APPROACH TO CONCURRENT CONTROL FLOW CHECKING

Sev...