Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-06-06
2004-11-23
Chaki, Kakali (Department: 2124)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S151000, C717S154000, C717S158000
Reexamination Certificate
active
06823507
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer programming techniques, and more particularly to techniques for detecting computer memory access errors of a computer program.
BACKGROUND
Errors arising from improper usage of memory are the most frequently occurring and one of the most intractable class of programming errors. The difficulty in tracking and fixing memory-related errors arises partially because the symptoms of the bug are usually far removed from the actual source of the bug and partially because the symptoms of the bug themselves appear inconsistently. Therefore, debugging of memory management errors requires a systematic, algorithmic approach.
A number of existing tools that aid in the process of debugging of memory-management errors use the technique of inserting run-time tests, either in the source code or in the object code, to validate each memory access during the execution of the program. This straightforward approach implicitly assumes that all memory accesses in the program are independent and unrelated and therefore need to be checked individually, which, unfortunately is not the case in real programs. Also, since most of these techniques tend to validate each memory access in the program, they often slow down the execution of the program by a huge factor; and hence, prove to be very cumbersome to use for industrial-sized programs particularly.
U.S. Pat. No. 5,644,709, issued on 1 Jul. 1997 to Austin describes a method for detecting memory-access errors that occur while executing a computer program (i.e., the errors are only detected at run-time). The method seeks to identify both spatial errors and temporal errors. In the case of a data object, spatial and temporal attributes are associated with a pointer to that data object. On the occurrence of a dereference by a pointer, a memory access check is performed to determine whether the dereference falls outside the valid address range for the data object, or outside a valid time period for the data object. If the dereference falls outside either range, a respective spatial or temporal error is flagged. Thus, U.S. Pat. No. 5,644,709 is concerned with catching memory-access errors only during program code execution (i.e., at run-time).
U.S. Pat. No. 5,644,709 further teaches a necessary preliminary method of taking a source-level program file, which in the normal course of events is compiled, interpreted or translated into object-level code, and adding to that compiling/interpreting/translating process an extended pointer representation. This pointer representation contains the value of the pointer as well as one or more object attributes, which describe the location, size, and lifetime of the pointer reference. This extended form of pointer allows the dereferencing process on occurrence of a memory access to check for spatial and temporal errors.
The approach taught by U.S. Pat. No. 5,644,709 has drawbacks, however, including the fact that errors resulting from source code programming faults are only detected at run-time. While such errors can be detected, the problem of debugging them still exists.
Conventional techniques insert run-time tests in program code (either source code or object code) to perform run-time debugging of memory errors. However, this introduces significant inefficiencies into the debugging process. Thus, a need clearly exists for an improved method of detecting memory-related errors that minimizes detection at run-time of a compiled computer program.
SUMMARY
The aspects of the invention perform a static analysis of program source code in an attempt to validate memory accesses in the program at compile-time, for each given program point. Thus the presence or absence of errors can be reported at compile-time. In cases where no conclusion can be reached by the static analysis (e.g. due to the presence of variables whose values cannot be inferred statically), then supplemental run-time tests are provided for validating such memory accesses at run-time.
The aspects of the invention therefore seek to provide a practical and efficient solution to the automatic detection of memory-related errors, using compile-time program analysis to attempt to reduce the extent of run-time testing.
In accordance with a first aspect of the invention, there is disclosed a method of detecting memory-related errors in a computer program during compiling of the computer program. In the method, static analysis is performed upon a computer program. At least one condition in the computer program is computed dependent upon the static analysis. Preferably, a condition is a test for checking a memory access in the computer program to and can be a pre-condition and/or a post-condition. The validity of each condition in the computer program is then evaluated. If the evaluation of a condition is determinate during compiling of the computer program, the presence or absence of memory-related errors in the computer program is reported. Preferably, a condition is determinate if the condition is valid or invalid. Otherwise, if the evaluation of a condition is indeterminate during compiling of the computer program, computer code based on the condition for incorporation in the computer program is generated for run-time detection of memory-related errors in the computer program. In this manner, generated computer code is minimized for run-time detection of memory-related errors in the computer program.
Preferably, the method includes the steps of determining an interrelationship between two or more memory accesses using the static analysis and generating a single condition in the computer program for two or more related memory accesses to minimize the number of conditions to be evaluated. The memory access can be made in the statically allocated memory or the dynamically allocated memory.
Preferably, the method includes the step of assigning at least one precondition to each statement in the computer program that must be satisfied for the computer program to execute without the memory-related errors. The pre-condition depends on one of the following: a memory-related operation in a statement in the computer program; a language restriction imposed on the memory-related operation; a predetermined error capable of being tested for; and a set of pre-conditions for a procedure call, the set being derived from static analysis of source code for the called procedure or being defined by a user. A post-condition is a check on the effect of a statement of the computer program on a memory space and can depend on one of the following: a memory-related operation at the statement of the computer program; the effect of the memory-related operation on the memory space defined by language semantics; and a set of post-conditions for a procedure call, the set being derived from static analysis of source code for the called procedure or being defined by a user.
In accordance with a second aspect of the invention, there is disclosed an apparatus for detecting memory-related errors in a computer program during compiling of the computer program. The apparatus includes a performing device, a computing device, an evaluating device, a reporting device, and a generating device. The performing device performs static analysis upon a computer program. The computing device computes at least one condition in the computer program dependent upon the static analysis. The evaluating device evaluates the validity of the at least one condition in the computer program. The reporting device reports the presence or absence of memory-related errors in the computer program if the evaluation of a condition is determinate during compiling of the computer program. The generating device generates computer code based on the at least one condition for incorporation in the computer program for run-time detection of memory-related errors in the computer program if the evaluation of a condition is indeterminate during compiling of the computer program. In this manner, the generated computer code is minimized for run-time detection of memory-related errors in th
Kiran Usha
Sinha Navin Kumar
Srinivasan Ravi
Chaki Kakali
Coca T. Rao
England Anthony V.S.
International Business Machines - Corporation
Nahar Qamrun
LandOfFree
Detection of memory-related errors in computer programs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Detection of memory-related errors in computer programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detection of memory-related errors in computer programs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3358373