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

• US 5,581,696 A
• Filed: 05/09/1995
• Issued: 12/03/1996
• Est. Priority Date: 05/09/1995
• Status: Expired due to Term

• Current Assignee: Parasoft Corporation
• Original Assignee: Parasoft Corporation
• Inventors: Kolawa, Adam K., Hicken, Wendell T., Salvador, Roman, Strickland, Bryan R.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Snyder, Glenn
• Application Number:
  US08/435,759
• Time in Patent Office: 574 Days
• Field of Search: 395/183.14
• US Class Current: 714/38.1
• 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 automatically instrumenting a computer program for dynamic debugging, such a computer program comprising source code written in a programming language for executing instructions on said computer, said programming language having a grammar comprising operations having an operator and at least one operand and a set of rules for relating said operations to said at least one operand, comprising the steps of:

providing said source code as a sequence of statements in a storage device to said computer, each such statement representing a desired instruction expressed in said programming language as one or more operations with at least one operand each;

separating each such statement into tokens representing either said operator or said at least one operand;

building a parse tree according to said set of rules using said tokens, said parse tree being a directed acyclic graph and comprising a plurality of nodes connected by paths organized into a hierarchy of parent nodes representing operators connected using said paths to children nodes representing operands of said operators;

providing additional nodes to said computer for instrumenting the computer program comprising instrumentation operations required to communicate runtime conditions to an error-checking engine, said additional nodes comprising a further plurality of nodes connected by paths organized into a hierarchy of parent nodes representing instrumentation operators connected using said paths to children nodes representing instrumentation operands of said instrumentation operators;

instrumenting said computer program by augmenting said parse tree with said additional nodes to create an instrumented parse tree for indicating that an error condition occurred in said computer program during execution using said instrumentation operations; and

generating object code from said instrumented parse tree and storing said object code in the storage device for later execution using the error-checking engine that indicates error conditions in said computer program.

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

determining a memory address from a stack frame corresponding to a memory variable sought to be checked, said stack frame having a corresponding node in said parse tree;

performing a flow analysis on said source code to identify a read operation to said memory address for which it cannot be determined that said memory variable has been previously initialized, said read operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said stack frame node corresponding to such an instrumentation operation for setting an indication that said memory variable is uninitialized;

inserting said additional nodes into said parse tree before said read operation corresponding to such an instrumentation operation for indicating that said memory variable is being read by a read operation and is either initialized or uninitialized as indicated by said indication;

performing a flow analysis on said source code to identify a write operation to said memory address, said write operation having a corresponding node in said parse tree; and

inserting said additional nodes into said parse tree after said write operation node corresponding to such an instrumentation operation for setting an indication that said memory variable is initialized.

3. A method according to claim 1, wherein said error condition comprises a memory access operation to an invalid memory address for a complex memory variable comprising a plurality of elements, each such element comprising a constant value, a simple memory variable or a complex memory variable, said instrumenting step further comprising the steps of:

performing a flow analysis on said source code to identify a declaration operation for a complex memory variable comprising an identifier operand for identifying said complex memory variable and a dimension operand for declaring a memory block size for said complex memory variable, said declaration operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said declaration operation node corresponding to such an instrumentation operation for storing said identifier operand and said dimension operand;

performing a flow analysis on said source code to identify said memory access operation using said complex memory variable, said memory access operation having a corresponding node in said parse tree; and

inserting said additional nodes into said parse tree before said memory access operation node corresponding to such an instrumentation operation for indicating whether said memory access operation is accessing an invalid memory address identified by said identifier operand and falling outside of a memory address range defined by said stored dimension operand.

4. A method according to claim 3, wherein said memory access operation is a write operation for writing a data value into said invalid memory address.

5. A method according to claim 3, wherein said memory access operation is a read operation for reading a data value from said invalid memory address.

6. A method according to claim 3, wherein said error condition comprises an array access violation and said complex memory variable is an array comprising a fixed number of identical elements, each such identical element being identified by an index and comprising a constant value, a simple memory variable or a complex memory variable, said second inserting step further comprising the step of:

inserting said additional nodes into said parse tree before said memory access operation node corresponding to such an instrumentation operation for indicating whether said memory access operation is accessing an invalid memory address identified by said identifier operand and using an index identifying an identical element falling outside of a memory address range defined by said stored dimension operand.

7. A method according to claim 6, wherein said memory access operation is a write operation for writing a data value into said invalid memory address.

8. A method according to claim 6, wherein said memory access operation is a read operation for reading a data value from said invalid memory address.

9. A method according to claim 1, wherein said error condition comprises a dynamic memory manipulation error using a pointer memory variable, said instrumenting step further comprising the steps

performing a flow analysis on said source code identify a declaration operation for a pointer memory variable comprising an identifier operand for identifying said pointer memory variable, said declaration operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said declaration operation node corresponding to such an instrumentation operation for storing a pointer record for said pointer memory variable identified by said identifier operand and containing a value field for a memory address;

performing a flow analysis on said source code to identify a memory allocation operation for allocating a memory block to said pointer memory variable, said memory allocation operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said memory allocation operation node corresponding to such an instrumentation operation for storing an allocation record for said memory block identified by said identifier operand and containing a size field storing said memory block size, a starting address field storing said memory block starting address, a pointer address field storing memory addresses of further pointer memory variables that point to said memory block, a pointer list field storing pointer memory variables contained in said memory block, and a state field storing state information regarding said memory block;

performing a flow analysis on said source code to identify an assignment operation assigning a memory address to said pointer memory variable, said assignment operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said assignment operation node corresponding to such an instrumentation operation for storing a memory address into said value field in said pointer record; and

inserting said additional nodes into said parse tree corresponding to such an instrumentation operation for performing a dynamic memory manipulation check using said pointer record and said allocation record.

10. A method according to claim 9, wherein said dynamic memory manipulation check comprises checking for an operation using a pointer memory variable containing a memory address for a freed memory block, said method further comprising the steps of:

performing a flow analysis on said source code to identify a read operation or a write operation using said pointer memory variable, said read operation or said write operation each having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree before said read operation node and before said write operation node corresponding to such an instrumentation operation for indicating whether said value field contains a memory address equal to said memory address for said freed memory block;

performing a flow analysis on said source code to identify a function call operation using said pointer memory variable, said function call operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree before said function call operation node corresponding to such an instrumentation operation for indicating whether said function call operation is calling a function using said value field containing a memory address equal to said memory address for said freed memory block;

performing a flow analysis on said source code to identify a function call return operation using said pointer memory variable, said function call return operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree before said function call return operation node corresponding to such an instrumentation operation for indicating whether said function call return operation is returning said value field containing a memory address equal to said memory address for said freed memory block to a calling function in said computer program;

performing a flow analysis on said source code to identify a free memory block operation using said pointer memory variable, said free memory block operation having a corresponding node in said parse tree; and

inserting said additional nodes into said parse tree before said free memory block operation node corresponding to such an instrumentation operation for indicating whether said free memory block operation is attempting to free a further memory block using said value field containing a memory address equal to said memory address for said freed memory block or is attempting to free a stack frame or is attempting to free said memory block whereby said memory address for said freed memory block does not equal said starting memory address.

11. A method according to claim 1, wherein said error condition comprises an inappropriate use of a pointer memory variable, said instrumenting step further comprising the steps

performing a flow analysis on said source code to identify a declaration operation for a pointer memory variable comprising an identifier operand for identifying said pointer memory variable, said declaration operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said declaration operation node corresponding to such instrumentation operation for storing a pointer record for said pointer memory variable identified by said identifier operand and containing a value field for a memory address;

performing a flow analysis on said source code to identify an operation using said pointer memory variable, said operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree before said operation node corresponding to such an instrumentation operation for indicating whether said operation is attempting to use said pointer memory variable when said value field is equal to said null;

inserting said additional nodes into said parse tree before said operation node corresponding to such an instrumentation operation for indicating whether said operation is attempting to use said pointer memory variable when said value field is uninitialized;

inserting said additional nodes into said parse tree before said operation node corresponding to such an instrumentation operation for indicating whether said operation is attempting to use a memory address contained in said value field that does not point to valid data;

inserting said additional nodes into said parse tree before said operation node corresponding to such an instrumentation operation for indicating whether said operation is attempting to compare or relate a plurality of pointer memory variables not pointing to identical types of data; and

inserting said additional nodes into said parse tree before said operation node corresponding to such an instrumentation operation for indicating whether said operation is attempting to make a function call using a pointer memory variable not containing a valid function address.

12. A method according to claim 1, wherein said error condition comprises a memory leak error, said instrumenting step further comprising the steps of:

performing a flow analysis on said source code to identify a declaration operation for a pointer memory variable comprising an identifier operand for identifying said point memory variable, said declaration operation having a corresponding node in said parse tree;

inserting said additional nodes into said parse tree after said declaration operation node corresponding to such an instrumentation operation for storing a pointer record for said pointer memory variable identified by said identifier operand and containing a value field for a memory address;

performing a flow analysis on said source code to identify an exit from scope operation, said operation having a corresponding node in said parse tree; and

inserting said additional nodes into said parse tree before said exit from scope operation corresponding to such an instrumentation operation for checking for memory leaks.

13. A method according to claim 1, wherein said error condition comprises an interface routine for performing a user-definable function during execution, said instrumenting step further comprising the steps of:

preprocessing said interface routine for creating an intermediate form and storing said intermediate form in a database;

performing a flow analysis on said source code to identify a function call having a corresponding interface description in said data base;

removing said function call from said parse tree;

reading said stored intermediate form for said corresponding interface from said database;

inserting said stored intermediate form as interface nodes in said parse tree;

substituting function call arguments into placeholders in said interface nodes; and

replacing a return statement in said interface node with an assignment of a result of said interface to an actual call to said function call.