Method using a computer for automatically instrumenting a computer program for dynamic debugging

• US 6,085,029 A
• Filed: 08/21/1996
• Issued: 07/04/2000
• Est. Priority Date: 05/09/1995
• Status: Expired due to Term

• Current Assignee: Parasoft Corporation
• Original Assignee: Parasoft Corporation
• Inventors: Kolawa, Adam K., Salvador, Roman, Strickland, Bryan R., Hicken, Wendell T.
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US08/701,097
• Time in Patent Office: 1,413 Days
• Field of Search: 395/183.14, 395/500, 395/183.13, 395/183.01, 395/701-708, 364/267, 364/267.2, 364/267.91, 364/267.8, 364/268.1
• US Class Current: 714/38.13
• CPC Class Codes: G06F 11/3624 by performing operations on the source code, e.g. via a compiler

Abstract

A method for automatically instrumenting a computer program for dynamic debugging. Such a computer program comprising source code written in a programming language for executing instructions on the computer. The source code is provided as a sequence of statements in a storage device to the computer. Each of the statements are separated into tokens representing either an operator or at least one operand. A parse tree is built according to a set of rules using the set of tokens. The parse tree is instrumented to create an instrumented parse tree for indicating that an error condition occurred in the computer program during execution. Object code is generated from the instrumented parse tree and stored in a secondary storage device for later execution using an error-checking engine that indicates error conditions present in the computer program.

Claims

1. A method using a computer for instrumenting in real time a computer program source code to facilitate the detection of runtime errors, the computer program being represented by a parse tree, each such runtime error having at least one instrumentation rountine for communicating an occurence of the associated runtime error to an error-checking engine, each such instrumentation routine being represented by a parse tree fragment, comprising the steps of:

performing a real time flow analysis on the parse tree for the computer program to determine an appropriate instrumentation routine for detecting the runtime errors;

instrumenting in real time the parse tree for the computer program by grafting the parse tree fragment for each such instrumentation routine onto the parse tree for the computer program;

generating executable object code from the grafted parse tree containing references to the instrumentation routines; and

executing the generated object code on a computer by transferring the runtime errors to the error-checking engine and linking the error-checking engine with the computer program to determine errors.

2. A method according to claim 1, wherein the runtime error comprises a read operation to an uninitialized memory variable, further comprising the steps of:

retrieving a memory address for a memory variable from a stack frame represented as interconnected nodes stored in the parse tree and augumenting the parse tree with the instrumentation nodes for indicating that the memory variable is possibly uninitialized;

identifying such a read operation to the memory address and augmenting the parse tree with the instrumentation nodes for indicating that the possibly unintialized memory variable is being read by the read operation; and

identifying a write operation to the memory address and augmenting the parse tree with the instrumentation nodes for indicating that the possibly unintialized memory variable is initialized.

3. A method according to claim 1, wherein the runtime error comprises a write operation to an invalid memory address for a complex memory variable, further comprising the steps of:

identifying a declaration operation of the complex memory variable comprising an identifier operand and a dimension operand that defines a memory address range and augmenting the parse tree with the instrumentation nodes for storing the identifier operand and the dimension operand; and

identifying such a write operation using the complex memory variable and augmenting the parse tree with instrumentation nodes for indicating an access by the write operation to at least one of such a memory address indentified by the indentifier operand that is invalid or such a memory address that falls outside of the memory address range defined by the dimension operand.

4. A method according to claim 1, wherein the runtime error comprises a runtime memory allocation operation using a pointer memory variable, further comprising the steps of:

identifying a declaration operation for such a pointer memory variable comprising an indentifier operand and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable and a corresponding memory address;

identifying such a runtime memory allocation operation for allocating a memory block to the pointer memory variable and augmenting the parse tree with instrumentation nodes for storing an allocation record for the memory block indentified by the indentifier operand;

identifying an assignment operation assigning the corresponding memory address to the pointer memory variable and augmenting the parse tree with instrumentation nodes for storing the corresponding memory address into the pointer record; and

augmenting the parse tree with instrumentation nodes for performing a runtime memory manipulation check using the pointer record and the allocation record.

5. A method according to claim 1, wherein the runtime error comprises an inappropriate use of a pointer memory variable, further comprising the steps of:

identifying a declaration operation for such a pointer memory variable and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable and a corresponding memory address;

identifying an operation using the pointer memory variable and augmenting the parse tree with instrumentation nodes for indicating whether at least one of the operation is using the pointer memory variable when the corresponding memory address is equal to null, the operation is using the pointer memory variable when the corresponding memory address is unintialized, the operation is using the corresponding memory address not pointing to valid data, the operation is comparing the pointer memory variable not pointing to identical types of data or the operation is making a function call using the pointer memory variable not containing a valid function address.

6. A method according to claim 1, wherein the runtime error comprises a memory leak, further comprising the steps of:

identifying a declaration operation for a pointer memory variable and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable; and

identifying an exit from scope operation and augmenting the parse tree with instrumentation nodes for checking for memory leaks using the scope operation and the pointer record.

7. A system for instrumenting a computer program to facilitate the detection of runtime errors, the computer program being represented by a parse tree, each such runtime error having at least one instrumentation routine for communicating an occurrence of the associated runtime error to an error-checking engine, each such instrumentation routine being represented by a parse tree fragment, comprising:

means for performing a real time flow analysis on the parse tree for the computer program to determine an appropriate instrumentation routine for detecting the runtime errors;

means for instrumenting in real time the parse tree for the computer program by grafting the parse tree fragment for each such instrumentation routine onto the parse tree for the computer program;

means for generating executable object code from the grafted parse tree containing references to the instrumentation routines; and

means for executing the generated object code by transferring the runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

8. A method using a computer for instrumenting an intermediate representation of a computer program for dynamic debugging, comprising the steps of:

creating in real time the intermediate representation of the computer program in the computer by translating source code comprising the computer program into an equivalent intermediate form;

analyzing in real time the intermediate representation of the computer program for instruction flow for determining an appropriate type of instrumentation for use in dynamic debugging;

augmenting in real time the intermediate representation of the computer program with at least one further intermediate representation wherein the at least one further intermediate representation comprises the appropriate type of instrumentation translated into the equivalent intermediate form;

generating executable object code from the augmented intermediate representation of the computer program containing references to the instrumentation routines and storing the executable code in the computer; and

executing the executable object code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

9. A method according to claim 8, wherein the step of creating the intermediate representation of the computer program further comprises the step of:

building a parse tree as the equivalent intermediate form.

10. A method according to claim 9, further comprising the steps of:

lexically analyzing the source code of the computer program to form a sequence of tokens;

parsing the sequence of tokens to form grammatical phrases;

semantically analyzing the grammatical phrases to form the parse tree.

11. A method according to claim 8, wherein the step of augmenting the intermediate representation of the computer program further comprises the steps of:

inserting such intermediate representations of instrumentation for checking functionality of the source code of the computer program and communicating the functionality to the error-checking engine; and

inserting such intermediate representations of instrumentation for communicating non-functional information regarding the source code of the computer program to the error-checking engine.

12. A method according to claim 11, further comprising the steps of:

communicating at least one of a declaration of variables, pointer addresses and pointer sizes;

communicating assignments of pointers;

communicating at least one of function entry and exit point indicators; and

communicating memory allocation indicators.

13. A method according to claim 11, further comprising the steps of:

detecting a read operation to an uninitialized memory variable;

detecting a write operation to an invalid memory address for a complex memory variable;

detecting a dynamic memory manipulation error using a pointer memory variable;

detecting an inappropriate use of a pointer memory variable;

detecting a memory leak error;

inserting a user-defined instrumentation routine; and

inserting an automatic test case generation routine.

14. A method using a computer for instrumenting an intermediate representation of a computer program for dynamic debugging, comprising the steps of:

creating the intermediate representation of the computer program in the computer by translating source code comprising the computer program into an equivalent intermediate form consisting of at least an additional sequence of code instructions;

analyzing in real time the additional sequence of code instructions to determine an appropriate type of instrumentation for use in the dynamic debugging;

augmenting in real time the additional sequence of code instructions with further code instructions to invoke the appropriate type of instrumentation;

generating executable object code containing references to the instrumentation routines using the augmented sequence of additional code and storing the executable code in the computer, and

executing the executable code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

15. A method according to claim 14 wherein the appropriate type of instrumentation includes code directed to detecting a read operation to an uninitialized memory variable.

16. A method according to claim 14 wherein the appropriate type of instrumentation includes code directed to detecting a write operation to an invalid memory address for a complex memory variable.

17. A method according to claim 14 wherein the appropriate type of instrumentation includes code directed to detecting an inappropriate use of a pointer memory variable.

18. A method according to claim 14 wherein the appropriate type of instrumentation includes code directed to detecting dynamic memory manipulation error using a pointer memory variable.

19. A method according to claim 14 wherein the appropriate type of instrumentation includes code directed to detecting a memory leak error.

20. A method according to claim 14 wherein the appropriate type of instrumentation includes code corresponding to a user defined instrumentation routine.

21. A method according to claim 14 wherein the appropriate type of instrumentation includes code corresponding to an automatic test case generation routine.

22. A method using a computer for dynamic debugging, comprising the steps of:

initiating compilation of a computer program;

interrupting the compilation of a computer program in order to capture the intermediate representation of the computer program created by the compilation process;

augmenting in real time the intermediate representation of the computer program to add instrumentation for use in dynamic debugging;

reinitiating the compilation process to generate executable object code containing references to the instrumentation routines;

executing the object code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

23. A method using a computer for instrumenting in real time a computer program source code to facilitate the detection of runtime errors, the computer program being represented by a parse tree, each such runtime error having at least one instrumentation routine for communicating an occurrence of the associated runtime error to an error-checking engine, each such instrumentation routine being represented by a parse tree fragment, comprising the steps of:

performing a real time flow analysis on the parse tree for the computer program to determine an appropriate instrumentation routine for detecting the runtime errors;

instrumenting in real time the parse tree for the computer program by grafting the parse tree fragment for each such instrumentation routine onto the parse tree for the computer program;

generating executable object code from the grafted parse tree containing references to the instrumentation routines; and

continuously executing the generated object code on the computer by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

24. A method according to claim 23, wherein the runtime error comprises a read operation to an uninitialized memory variable, further comprising the steps of:

retrieving a memory address for a memory variable from a stack frame represented as interconnected nodes stored in the parse tree and augmenting the parse tree with the instrumentation nodes for indicating that the memory variable is possibly uninitialized;

identifying such a read operation to the memory address and augmenting the parse tree with the instrumentation nodes for indicating that the possibly uninitialized memory variable is being read by the read operation; and

identifying a write operation to the memory address and augmenting the parse tree with the instrumentation nodes for indicating that the possibly uninitialized memory variable is initialized.

25. A method according to claim 23, wherein the runtime error comprises a write operation to an invalid memory address for a complex memory variable, further comprising the steps of:

identifying a declaration operation for the complex memory variable comprising an identifier operand and a dimension operand that defines a memory address range and augmenting the parse tree with the instrumentation nodes for storing the identifier operand and the dimension operand; and

identifying such a write operation using the complex memory variable and augmenting the parse tree with instrumentation nodes for indicating an access by the write operation to at least one of such a memory address identified by the identifier operand that is invalid or such a memory address that falls outside of the memory address range defined by the dimension operand.

26. A method according to claim 23, wherein the runtime error comprises a runtime memory allocation operation using a pointer memory variable, further comprising the steps of:

identifying a declaration operation for such a pointer memory variable comprising a identifier operand and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable and a corresponding memory address;

identifying such a runtime memory allocation operation for allocating a memory block to the pointer memory variable and augmenting the parse tree with instrumentation nodes for storing an allocation record for the memory block identified by the identifier operand;

identifying an assignment operation assigning the corresponding memory address to the pointer memory variable and augmenting the parse tree with instrumentation nodes for storing the corresponding memory address into the pointer record; and

augmenting the parse tree with instrumentation nodes for performing a runtime memory manipulation check using the pointer record and the allocation record.

27. A method according to claim 23, wherein the runtime error comprises an inappropriate use of a pointer memory variable, further comprising the steps of:

identifying a declaration operation for such a pointer memory variable and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable and a corresponding memory address;

identifying an operation using the pointer memory variable and augmenting the parse tree with instrumentation nodes for indicating whether at least one of the operation is using the pointer memory variable when the corresponding memory address is equal to null, the operation is using the pointer memory variable when the corresponding memory address is uninitialized, the operation is using the corresponding memory address not pointing to valid data, the operation is comparing the pointer memory variable not pointing to identical types of data or the operation is making a function call using the pointer memory variable not containing a valid function address.

28. A method according to claim 23, wherein the runtime error comprises a memory leak, further comprising the steps of:

identifying a declaration operation for a pointer memory variable and augmenting the parse tree with instrumentation nodes for storing a pointer record for the pointer memory variable; and

identifying an exit from scope operation and augmenting the parse tree with instrumentation nodes for checking for memory leaks using the scope operation and the pointer record.

29. A system for instrumenting in real time a computer program source code to facilitate the detection of runtime errors, the computer program being represented by a parse tree, each such runtime error having at least one instrumentation routine for communicating an occurrence of the associated runtime error to an error-checking engine, each such instrumentation routine being represented by a parse tree fragments comprising:

means for performing a real time flow analysis on the parse tree for the computer program to determine an appropriate instrumentation routine for detecting the runtime errors;

means for instrumenting in real time the parse tree for the computer program by grafting the parse tree fragment for each such instrumentation routine onto the parse tree for the computer program;

means for generating executable object code from the grafted parse tree containing references to the instrumentation routines; and

means for continuously executing the generated object code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

30. A method using a computer for instrumenting in real time an intermediate representation of a computer program for dynamic debugging, comprising the steps of:

creating the intermediate representation of the computer program in the computer by translating source code comprising the computer program into an equivalent intermediate form;

analyzing in real time the intermediate representation of the computer program for instruction flow for determining an appropriate type of instrumentation for use in dynamic debugging;

augmenting in real time the intermediate representation of the computer program with at least one further intermediate representation wherein the at least one further intermediate representation comprises the appropriate type of instrumentation translated into the equivalent intermediate form;

generating executable object code containing references to the instrumentation routines from the augmented intermediate representation of the computer program and storing the executable code in the computer; and

continuously executing the generated object code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

31. A method according to claim 30, wherein the step of creating the intermediate representation of the computer program further comprises the step of:

building a parse tree as the equivalent intermediate form.

32. A method according to claim 31, further comprising the steps of:

lexically analyzing the source code of the computer program to form a sequence of tokens;

parsing the sequence of tokens to form grammatical phrases;

semantically analyzing the grammatical phrases to form the parse tree.

33. A method according to claim 30, wherein the step of augmenting the intermediate representation of the computer program further comprises the steps of:

inserting such intermediate representations of instrumentation for checking functionality of the source code of the computer program and communicating the functionality to the error-checking engine; and

inserting such intermediate representations of instrumentation for communicating non-functional information regarding the source code of the computer program to the error-checking engine.

34. A method according to claim 33, further comprising the steps of:

communicating at least one of a declaration of variables, pointer addresses and pointer sizes;

communicating assignments of pointers;

communicating at least one of function entry and exit point indicators; and

communicating memory allocation indicators.

35. A method according to claim 33, further comprising the steps of:

detecting a read operation to an uninitialized memory variable;

detecting a write operation to an invalid memory address for a complex memory variable;

detecting a dynamic memory manipulation error using a pointer memory variable;

detecting an inappropriate use of a pointer memory variable;

detecting a memory leak error;

inserting a user-defined instrumentation routine; and

inserting an automatic test case generation routine.

36. A method using a computer for instrumenting in real time an intermediate representation of a computer program source code for dynamic debugging, comprising the steps of:

creating the intermediate representation of the computer program in the computer by translating source code comprising the computer program into an equivalent intermediate form consisting of at least an additional sequence of code instructions;

analyzing in real time the additional sequence of code instructions to determine an appropriate type of instrumentation for use in the dynamic debugging;

augmenting in real time the additional sequence of code instructions with further code instructions to invoke the appropriate type of instrumentation;

generating executable object code containing references to the instrumentation routines using the augmented sequence of additional code and storing the executable code in the computer; and

continuously executing the executable code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

37. A method according to claim 36 wherein the appropriate type of instrumentation includes code directed to detecting a read operation to an uninitialized memory variable.

38. A method according to claim 36 wherein the appropriate type of instrumentation includes code directed to detecting a write operation to an invalid memory address for a complex memory variable.

39. A method according to claim 36 wherein the appropriate type of instrumentation includes code directed to detecting an inappropriate use of a pointer memory variable.

40. A method according to claim 36 wherein the appropriate type of instrumentation includes code directed to detecting dynamic memory manipulation error using a pointer memory variable.

41. A method according to claim 36 wherein the appropriate type of instrumentation includes code directed to detecting a memory leak error.

42. A method according to claim 36 wherein the appropriate type of instrumentation includes code corresponding to a user defined instrumentation routine.

43. A method according to claim 36 wherein the appropriate type of instrumentation includes code corresponding to an automatic test case generation routine.

44. A method using a computer for dynamic debugging, comprising the steps of:

initiating compilation of a computer program;

interrupting the compilation of a computer program in order to capture the intermediate representation of the computer program created by the compilation process;

augmenting in real time the intermediate representation of the computer program to add instrumentation for use in dynamic debugging;

reinitiating the compilation process to generate executable object code containing references to the instrumentation routines;

continuously executing the object code by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

45. A method using a computer for instrumenting an intermediate representation of a computer program for dynamic debugging, comprising the steps of:

creating the intermediate representation of the computer program in the computer by translating source code comprising the computer program into an equivalent intermediate form;

analyzing in real time the intermediate representation of the computer program for instruction flow for determining an appropriate type of instrumentation for use in dynamic debugging;

augmenting in real time the intermediate representation of the computer program with at least one further intermediate representation wherein the at least one further intermediate representation comprises the appropriate type of instrumentation translated into the equivalent intermediate form;

generating executable object code containing references to the instrumentation routines from the augmented intermediate representation of the computer program and storing the executable code in the computer; and

executing the code executable in real time by transferring runtime errors to an error-checking engine and linking the error-checking engine with the computer program to determine errors.

46. A method according to claim 45, wherein the step of creating the intermediate representation of the computer program further comprises the step of:

building a parse tree as the equivalent intermediate form.

47. A method according to claim 46, further comprising the steps of:

lexically analyzing the source code of the computer program to form a sequence of tokens;

parsing the sequence of tokens to form grammatical phrases;

semantically analyzing the grammatical phrases to form the parse tree.

48. A method according to claim 45, wherein the step of augmenting the intermediate representation of the computer program further comprises the steps of:

inserting such intermediate representations of instrumentation for checking functionality of the source code of the computer program and communicating the functionality to the error-checking engine; and

inserting such intermediate representations of instrumentation for communicating non-functional information regarding the source code of the computer program to the error-checking engine.

49. A method according to claim 48, further comprising the steps of:

communicating at least one of a declaration of variables, pointer addresses and pointer sizes;

communicating assignments of pointers;

communicating at least one of function entry and exit point indicators; and

communicating memory allocation indicators.

50. A method according to claim 48, further comprising the steps of:

detecting a read operation to an uninitialized memory variable;

detecting a write operation to an invalid memory address for a complex memory variable;

detecting a dynamic memory manipulation error using a pointer memory variable;

detecting an inappropriate use of a pointer memory variable;

detecting a memory leak error;

inserting a user-defined instrumentation routine; and

inserting an automatic test case generation routine.