Method for detecting computer memory access errors

• US 5,644,709 A
• Filed: 04/21/1994
• Issued: 07/01/1997
• Est. Priority Date: 04/21/1994
• Status: Expired due to Fees

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Austin, Todd Michael
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/237,041
• Time in Patent Office: 1,167 Days
• Field of Search: 395/185.06, 395/185.08, 395/185.07, 395/185.02, 395/411, 395/427, 395/481, 395/494
• US Class Current: 714/53
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence

Abstract

A method for detecting memory access errors which occur while executing a computer program. Spatial and temporal attributes are provided for a data object and these attributes are associated with each pointer to that data object. On a dereference to a pointer, a memory access check is performed which determines (a) whether the dereference falls outside the address range within which valid accesses may be made to the data object, and (b) whether the dereference falls outside the time period within which valid accesses may be made to the data object. If the dereference falls outside the valid address range, a spatial error is flagged. If the dereference falls outside the valid time period, a temporal error is flagged. In addition, a method is described for converting a preexisting source-language program file into a safe program and a method is described for optimizing memory-access checks.

Claims

1. A method for detecting memory access errors which occur while executing a computer program, wherein the computer program includes a pointer to a data object, said method comprising the steps of:

providing a spatial attribute for said data object, said spatial attribute defining an address space within which valid accesses may be made to said data object;

associating said spatial attribute with said pointer;

providing a temporal attribute for said data object, said temporal attribute defining a period of time within which valid accesses may be made to said data object, wherein the step of providing said temporal attribute comprises the steps of;

providing a temporal validity number having a temporal validity number location; and

providing a temporal capability number;

associating said temporal capability number with said pointer;

providing a dereference to said pointer;

determining if said dereference falls outside said address space;

if said dereference falls outside said address space, flagging a spatial error;

determining from said temporal capability number and said temporal validity number whether a temporal error has occurred; and

if a temporal error has occurred, flagging said temporal error.

2. The method according to claim 1, wherein the step of providing a spatial attribute comprises the step of providing a size attribute indicative of said address space.

3. The method according to claim 2, wherein the step of providing a spatial attribute further comprises the step of providing an address attribute indicative of a base address.

4. The method according to claim 1, wherein said address space has a lower bound and an upper bound and wherein the step of providing a spatial attribute comprises the steps of:

providing a low-end address attribute indicative of said lower bound; and

providing a high-end address attribute indicative of said higher bound.

5. The method according to claim 1, wherein the step of providing a temporal attribute further comprises the step of providing a storage class attribute.

6. The method according to claim 5, wherein the step of providing a storage class attribute comprises the step of specifying storage classes which distinguish heap and local data objects.

7. The method according to claim 6, wherein the step of providing a spatial attribute comprises the step of providing a size attribute indicative of the address space.

8. The method according to claim 7, wherein the step of providing a spatial attribute further comprises the step of providing an address attribute indicative of a base address.

9. The method according to claim 6, wherein said address space has a lower bound and an upper bound and wherein the step of providing a spatial attribute comprises the steps of:

providing a low-end address attribute indicative of said lower bound; and

providing a high-end address attribute indicative of said higher bound.

10. A method of detecting a memory access error encountered when executing program code including a pointer pointing to a variable, the method comprising the steps of:

assigning temporal attributes defining temporal status for said pointer, wherein the step of assigning temporal attributes comprises the steps of;

providing a temporal validity number associated with said variable;

providing a temporal capability number; and

associating said temporal capability number with said pointer;

assigning spatial attributes defining an address space valid for said pointer;

executing a memory access check on a memory access, wherein the step of executing a memory access check comprises the steps of;

determining from said temporal capability number and said temporal validity number whether a temporal error has occurred; and

determining whether said memory access is to an address within said valid address space;

if a temporal status has occurred, flagging said temporal error; and

if said memory access is to an address outside said valid address space, flagging a spatial error.

11. The method according to claim 10 wherein the step of determining whether a temporal error has occurred comprises the step of accessing said temporal validity number through a hash table.

12. The method according to claim 10 wherein the temporal validity number has a temporal validity number location;

wherein the step of assigning temporal attributes further comprises the steps of;

providing a backpointer specifying said temporal validity number location; and

associating said backpointer with said pointer; and

wherein the step of determining whether a temporal error has occurred comprises the step of accessing said temporal validity number via said backpointer.

13. A method for detecting memory access errors which occur while executing a computer program, wherein the computer program includes a pointer to a data object, the method comprising the steps of:

providing a counter having a count for tracking memory deallocations;

providing a spatial attribute for said data object, said spatial attribute defining an address space within which valid accesses may be made to said data object;

associating said spatial attribute with said pointer;

associating said temporal attribute with said pointer;

providing a temporal attribute for said data object, wherein the step of providing said temporal attribute comprises the steps of;

providing a temporal validity number having a temporal validity number location; and

providing a temporal capability number;

associating said temporal capability number with said pointer;

providing a first dereference and a second dereference to said pointer wherein said first dereference occurs prior to said second dereference;

determining if said second dereference falls outside said address space;

if said second dereference falls outside said address space, flagging a spatial error;

determining if said count has changed since said fast dereference; and

if said count has changed since said first dereference, verifying said temporal attributes, wherein the step of verifying said temporal attributes comprises the steps of;

determining from said temporal capability number and said temporal validity number whether a temporal error has occurred; and

if a temporal error has occurred, flagging said temporal error.

14. The method according to claim 13 wherein the step of providing a temporal attribute further comprises the step of providing a storage class attribute which distinguishes heap and local data objects.

15. A system for detecting a memory access error in a computer program executing on a computer, the system comprising:

means for assigning object attributes to a pointer, wherein said object attributes comprise;

a temporal capability number; and

a spatial attribute defining an address space valid for said pointer;

means for assigning a temporal validity number;

means for adding memory access check instructions to said computer program, wherein said memory access check instructions comprise;

instructions which determine from said temporal capability number and said temporal validity number whether a temporal error has occurred; and

instructions which determine whether a memory access made within said computer program is to an address within said valid address space.

16. The system according to claim 15 wherein the instructions for determining whether a temporal error has occurred comprise an instruction for accessing said temporal validity number through a hash table.

17. The system according to claim 15 wherein:

the temporal validity number has a temporal validity number location;

the temporal attributes further include a backpointer specifying said temporal validity number location, wherein said backpointer is associated with said pointer; and

the instructions for determining whether a temporal error has occurred comprise an instruction for accessing said temporal validity number via said backpointer.

18. The system according to claim 15 wherein the instructions for determining whether a temporal error has occurred comprise an instruction for determining whether a temporal memory access check can be elided.

19. The system according to claim 15 wherein the instructions for determining whether a spatial error has occurred comprise an instruction for determining whether a spatial memory access check can be elided.

20. The system according to claim 15 wherein the means for adding memory access check instructions to said computer program comprise means for determining whether a memory access check can be elided.