Detection of memory-related errors in computer programs

• US 6,823,507 B1
• Filed: 06/06/2000
• Issued: 11/23/2004
• Est. Priority Date: 06/06/2000
• Status: Expired due to Fees

• Current Assignee: International Business Corporation (Kleangas Energy Technologies, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Srinivasan, Ravi, Kiran, Usha, Sinha, Navin Kumar
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Nahar, Qamrun
• Application Number:
  US09/587,924
• Time in Patent Office: 1,631 Days
• Field of Search: 717/146, 717/140, 717/152, 717/151, 717/154, 717/158, 395/708, 395/705
• US Class Current: 717/152
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method, an apparatus, and a computer program product are disclosed for 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. One or more conditions in the computer program are computed based on the static analysis. Each condition is a test for checking a memory access in the computer program and can be either a pre- or post-condition. The validity of each condition in the computer program is then evaluated. If the evaluation is determinate during compiling, the presence or absence of memory-related errors in the computer program is reported. A condition is determinate if the condition is valid or invalid during compiling. Otherwise, computer code based on the condition is generated for incorporation in the computer program for run-time detection of memory-related errors.

Claims

1. A method of detecting memory-related errors in a computer program during compiling of said computer program, said method including the steps of:

performing static analysis upon a computer program, wherein the static analysis is performed concurrently with performance of compiler optimization and includes the steps of;

assigning pre-conditions for respective statements in said computer program, wherein such a pre-condition must be satisfied in order for the computer program to execute without producing memory-related errors; and

evaluating whether said pre-conditions are satisfied in said computer program, wherein the static analysis uses certain data structures and analysis also used in the concurrent performance of the compiler optimization;

reporting, during compiling of said computer program, presence or absence of a memory-related error in said computer program if said evaluation is successful in determining whether such a pre-condition is satisfied;

generating computer code, during compiling of said computer program, wherein the generated computer code includes a test for run-time detection of a memory-related error in said computer program if said evaluation of such a pre-condition is indeterminate; and

producing compiled object code responsive to the computer program and the generated computer code including the test, so that execution of the compiled object code performs the test for run-time detection of a memory-related error and so that if the evaluation indicates one of the pre-conditions is satisfied the reporting of the presence or absence of a memory-related error reduces the run-time detection of memory-related errors in the compiled object code.

2. The method according to claim 1, wherein at least one of said pre-conditions is a test for checking a memory access in said computer program.

3. The method according to claim 2, further including the step of determining an interrelationship between two or more memory accesses using said static analysis.

4. The method according to claim 3, further including the step of generating a single condition in said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

5. The method according to claim 2, wherein said memory access is made in statically allocated memory or dynamically allocated memory.

6. The method according to claim 1, wherein the step of evaluating whether the pre-conditions are satisfied includes the steps of:

determining post-conditions, wherein such a post-condition includes an effect generated by a respective program statement on memory space; and

verifying for one such program statement whether any precondition of that one program statement is satisfied in a context of the post-conditions determined for program statements preceding the one program statement.

7. The method according to claim 6, wherein such a pre-condition depends on one of the following:

a memory-related operation in a statement in said computer program;

a language restriction imposed on said memory-related operation;

a predetermined error capable of being tested for; and

a set of pre-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

8. The method according to claim 6, where said post-condition depends on one of the following:

a memory-related operation at said statement of said computer program;

the effect of said memory-related operation on said memory space defined by language semantics; and

a set of post-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

9. The method according to claim 1, wherein such a pre-condition is indeterminate if a determination cannot be made based on compile-time information as to whether the pre-condition is satisfied.

10. An apparatus for detecting memory-related errors in a computer program during compiling of said computer program, said apparatus including:

means for performing static analysis upon a computer program, wherein the static analysis is performed concurrently with performance of compiler optimization and includes the steps of;

means for assigning pre-conditions for respective statements in said computer program, wherein such a pre-condition must be satisfied in order for the computer program to execute without producing memory-related errors; and

means for evaluating whether said pre-conditions are satisfied in said computer program, wherein the static analysis uses certain data structures and analysis also used in the concurrent performance of the compiler optimization;

means for reporting, during compiling of said computer program, presence or absence of a memory-related error in said computer program if said evaluation is successful in determining whether such a pre-condition is satisfied;

means for generating computer code, during compiling of said computer program, wherein the generated computer code includes a test for run-time detection of a memory-related error in said computer program if said evaluation of such a pre-condition is indeterminate; and

means for producing compiled object code responsive to the computer program and the generated computer code including the test, so that execution of the compiled object code performs the test for run-time detection of a memory-related error and so that if the evaluation indicates one of the pre-conditions is satisfied the reporting of the presence or absence of a memory-related error reduces the run-time detection of memory-related errors in the compiled object code.

11. The apparatus according to claim 10, wherein at least one of said pre-conditions is a test for checking a memory access in said computer program.

12. The apparatus according to claim 11, further including means for determining an interrelationship between two or more memory accesses using said static analysis.

13. The apparatus according to claim 12, further including means for generating a single condition in said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

14. The apparatus according to claim 11, wherein said memory access is made in statically allocated memory or dynamically allocated memory.

15. The apparatus according to claim 10, wherein the means for evaluating whether the pre-conditions are satisfied includes:

means for determining post-conditions, wherein such a post-condition includes an effect generated by a respective program statement on memory space; and

means for verifying for one such program statement whether any precondition of that one program statement is satisfied in a context of the post-conditions determined for program statements preceding the one program statement.

16. The apparatus according to claim 15, wherein such a pre-condition depends on one of the following:

a memory-related operation in a statement in said computer program;

a language restriction imposed on said memory-related operation;

a predetermined error capable of being tested for; and

a set of pre-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

17. The apparatus according to claim 15, where said post-condition depends on one of the following:

a memory-related operation at said statement of said computer program;

the effect of said memory-related operation on said memory space defined by language semantics; and

a set of post-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

18. The apparatus according to claim 10, wherein such a pre-condition is indeterminate if a determination cannot be made based on compile-time information as to whether the pre-condition is satisfied.

19. A computer program product having a computer readable medium having a computer program recorded therein for detecting memory-related errors in a computer program during compiling of said computer program, said computer program product including:

computer program code means for performing static analysis upon a computer program, wherein the static analysis is performed concurrently with performance of compiler optimization and includes the steps of;

computer program code means for assigning pre-conditions for respective statements in said computer program, wherein such a pre-condition must be satisfied in order for the computer program to execute without producing memory-related errors; and

computer program code means for evaluating whether said pre-conditions are satisfied in said computer program, wherein the static analysis uses certain data structures and analysis also used in the concurrent performance of the compiler optimization;

computer program code means for reporting, during compiling of said computer program, the presence or absence of a memory-related error in said computer program if said evaluation is successful in determining whether such a pre-condition is satisfied;

computer program code means for generating computer code, during compiling of said computer program, wherein the generated computer code includes a test for run-time detection of a memory-related error in said computer program if said evaluation of such a pre-condition is indeterminate; and

computer program code means for producing compiled object code responsive to the computer program and the generated computer code including the test, so that execution of the compiled object code performs the test for run-time detection of a memory-related error and so that if the evaluation indicates one of the pre-conditions is satisfied the reporting of the presence or absence of a memory-related error reduces the run-time detection of memory-related errors in the compiled object code.

20. The computer program product according to claim 19, wherein at least one of said pre-conditions is a test for checking a memory access in said computer program.

21. The computer program product according to claim 20, further including computer program code means for determining an interrelationship between two or more memory accesses using said static analysis.

22. The computer program product according to claim 21, further including computer program code means for generating a single condition in said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

23. The computer program product according to claim 20, wherein said memory access is made in statically allocated memory or dynamically allocated memory.

24. The computer program product according to claim 19, wherein the computer program code means for evaluating whether the pre-conditions are satisfied includes:

computer program code means for determining post-conditions, wherein such a post-condition includes an effect generated by a respective program statement on memory space; and

computer program code means for verifying for one such program statement whether any pre-condition of that one program statement is satisfied in a context of the post-conditions determined for program statements preceding the one program statement.

25. The computer program product according to claim 24, wherein such a pre-condition depends on one of the following:

a memory-related operation in a statement in said computer program;

a language restriction imposed on said memory-related operation;

a predetermined error capable of being tested for; and

a set of pre-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

26. The computer program product according to claim 24, where said post-condition depends on one of the following:

a memory-related operation at said statement of said computer program;

the effect of said memory-related operation on said memory space defined by language semantics; and

a set of post-conditions for a procedure call, said set being derived from static analysis of source code for said called procedure or being defined by a user.

27. The computer program product according to claim 19, wherein such a pre-condition is indeterminate if a determination cannot be made based on compile-time information as to whether the pre-condition is satisfied.

28. A method of compiling a computer program, said method including the steps of:

converting source code of said computer program into intermediate code of said computer program;

optimizing said intermediate code of said computer program, said optimizing step including the steps of;

detecting memory-related errors in said intermediate code of said computer program using static analysis;

reporting any memory-related errors in said computer program that are determinate during compiling of said computer program;

generating computer code to test for any memory-related errors in said computer program that are indeterminate during compiling of said computer program;

incorporating said generated computer code in optimized intermediate code of said computer program; and

converting said optimized intermediate code into compiled machine executable code of said computer program.

29. The method according to claim 28, wherein said detecting step further includes the steps of:

performing static analysis upon said intermediate code of said computer program;

computing at least one condition in said intermediate code of said computer program dependent upon said static analysis; and

evaluating the validity of said at least one condition in said intermediate code of said computer program.

30. The method according to claim 28, wherein said at least one condition checks for a memory access in said computer program.

31. The method according to claim 30, further including the step of determining an interrelationship between two or more memory accesses using said static analysis.

32. The method according to claim 31, further including the step of generating a single condition in said intermediate code of said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

33. The method according to claim 28, wherein said at least one condition is selected from the group consisting of a pre-condition, a post-condition, and a combination of a pre-condition and a post-condition.

34. The method according to claim 33, further including the step of assigning to each statement in said computer program at least one pre-condition that must be satisfied for said computer program to execute without said memory-related errors.

35. The method according to claim 33, wherein said post-condition is a check on the effect of a statement of said computer program on a memory space.

36. The method according to claim 28, wherein a condition is determinate if said condition is valid or invalid.

37. An apparatus for compiling a computer program, said apparatus including:

means for converting source code of said computer program into intermediate code of said computer program;

means for optimizing said intermediate code of said computer program, said optimizing means including;

means for detecting memory-related errors in said intermediate code of said computer program using static analysis;

means for reporting any memory-related errors in said computer program that are determinate during compiling of said computer program; and

means for generating computer code to test for any memory-related errors in said computer program that are indeterminate during compiling of said computer program;

means for incorporating said generated computer code in optimized intermediate code of said computer program; and

means for converting said optimized intermediate code into compiled machine executable code of said computer program.

38. The apparatus according to claim 37, wherein said detecting means further includes:

means for performing static analysis upon said intermediate code of said computer program;

means for computing at least one condition in said intermediate code of said computer program dependent upon said static analysis; and

means for evaluating the validity of said at least one condition in said intermediate code of said computer program.

39. The apparatus according to claim 37, wherein said at least one condition checks for a memory access in said computer program.

40. The apparatus according to claim 39, further including means for determining an interrelationship between two or more memory accesses using said static analysis.

41. The apparatus according to claim 40, further including means for generating a single condition in said intermediate code of said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

42. The apparatus according to claim 37, wherein said at least one condition is selected from the group consisting of a pre-condition, a post-condition, and a combination of a pre-condition and a post-condition.

43. The apparatus according to claim 42, further including means for assigning to each statement in said computer program at least one pre-condition program that must be satisfied for said computer program to execute without said memory-related errors.

44. The apparatus according to claim 42, wherein said post-condition is a check on the effect of a statement of said computer program on a memory space.

45. The apparatus according to claim 37, wherein a condition is determinate if said condition is valid or invalid.

46. A computer program product having a computer readable medium having a computer program recorded therein for compiling a computer program, said computer program product including:

computer program code means for converting source code of said computer program into intermediate code of said computer program;

computer program code means for optimizing said intermediate code of said computer program, said optimizing means including;

computer program code means for detecting memory-related errors in said intermediate code of said computer program using static analysis;

computer program code means for reporting any memory-related errors in said computer program that are determinate during compiling of said computer program; and

computer program code means for generating computer code to test for any memory-related errors in said computer program that are indeterminate during compiling of said computer program;

computer program code means for incorporating said generated computer code in optimized intermediate code of said computer program; and

computer program code means for converting said optimized intermediate code into machine executable code of said computer program.

47. The computer program product according to claim 46, wherein said computer program code means for detecting further includes:

computer program code means for performing static analysis upon said intermediate code of said computer program;

computer program code means for computing at least one condition in said intermediate code of said computer program dependent upon said static analysis; and

computer program code means for evaluating the validity of said at least one condition in said intermediate code of said computer program.

48. The computer program product according to claim 46, wherein said at least one condition checks for a memory access in said computer program.

49. The computer program product according to claim 48, further including computer program code means for determining an interrelationship between two or more memory accesses using said static analysis.

50. The computer program product according to claim 49, further including computer program code means for generating a single condition in said intermediate code of said computer program for two or more related memory accesses to minimize the number of conditions to be evaluated.

51. The computer program product according to claim 46, wherein said at least one condition is selected from the group consisting of a pre-condition, a post-condition, and a combination of a pre-condition and a post-condition.

52. The computer program product according to claim 51, further including computer program code means for assigning to each statement in said computer program at least one pre-condition that must be satisfied for said computer program to execute without said memory-related errors.

53. The computer program product according to claim 51, wherein said post-condition is a check on the effect of a statement of said computer program on a memory space.

54. The computer program product according to claim 46, wherein a condition is determinate if said condition is valid or invalid.