Leveraging garbage collection to dynamically infer heap invariants

• US 20060265438A1
• Filed: 05/20/2005
• Published: 11/23/2006
• Est. Priority Date: 05/20/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Shankar, Ajeet
• Granted Patent: US 7,912,877 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/0718 in an object-oriented system
• CPC Class Codes: G06F 11/073 in a memory management context, e.g. virtual memory or cache management memory management G06F12/00; testing of static memory units G11C29/00
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

A program analysis tool leverages the garbage collection process to dynamically infer invariants of objects or data structures created by a program on the heap during execution. During execution of the program in a garbage-collected execution environment, the program analysis tool tracks object allocations made by the program, and records some meta data relating to invariants tracked for the type of the object, which are initially assumed satisfied by the object. Whenever a garbage collection pass visits the object, the tool checks whether the object still satisfies the invariants, and updates the meta data accordingly. The tool finally reports the invariants reflected by the meta data upon the object'"'"'s death or at termination of the program. The invariants can then be used to annotate the program source code and/or detect bugs that violate the invariants.

Claims

1. A method of inferring heap invariants for program objects maintained by a program in heap memory, comprising:

causing the program to execute over a period in an execution environment having a heap memory managed using garbage collection;

creating meta data to track invariants of the program objects created by the program in the heap memory;

upon a vitality check of the program objects in a garbage collection pass, checking the invariants of the program objects and updating the meta data based on results of the checking; and

producing data reporting the invariants satisfied by the program objects over the period of execution of the program.

2. The method of claim 1, further comprising:

when creating the meta data, initializing the meta data of the program objects to indicate the invariants are satisfied by the program objects; and

when the checking determines that an invariant is not satisfied by a program object, updating the meta data to indicate the invariant was not satisfied by said program object.

3. The method of claim 1 further comprising tracking a set of invariants that are generic to all the program objects.

4. The method of claim 1 further comprising tracking a set of type-specific invariants of the program objects according to their respective types.

5. The method of claim 1 further comprising tracking a set of invariants of the program objects based on allocation site.

6. The method of claim 1 further comprising tracking a set of type-wide invariants applicable across all program objects of a same type.

7. The method of claim 1, further comprising adding annotations to source code of the program based on the invariants reported to be satisfied by at least some of the program objects.

8. The method of claim 1 further comprising:

performing said causing, creating, checking and producing actions for a first period of execution of the program to thereby discover normative invariants of the program objects; and

in a subsequent period of execution of the program, detecting occurrence of any anomalies in which the normative invariants are violated by the program.

9. The method of claim 8 wherein the subsequent period of execution of the program is a separate debugging run after the program has been modified.

10. The method of claim 8 further comprising identifying code in the program that produced an occurrence of an anomaly as a bug.

11. The method of claim 1 further comprising identifying code in the program associated with a program object having an invariant indicative of likely inefficient behavior for possible optimization.

12. A computer-readable computer program-carrying storage medium having software for a program analysis tool carried thereon, which is executable on a computer system to perform analysis of a program under test to infer heap invariants of program objects maintained by said program under test in heap memory, the program analysis tool comprising:

a heap executive providing a heap allocator application programming interface service to allocate memory space in heap memory upon request from said program under test, and a garbage collector operating to periodically perform a garbage collection pass over program objects created by said program under test in heap memory in which the garbage collector tests the program objects'"'"' liveness; and

an invariant inference service operating across an execution of said program under test to maintain meta data tracking a set of invariants per program object, the invariant inference service operating when the garbage collector tests liveness of a program object to also check that the program object continues to satisfy the invariants tracked for the respective object, the invariant inference service producing a report indicating the invariants satisfied by the program objects across the execution of said program under test.

13. The computer-readable computer program-carrying storage medium of claim 12 wherein the invariant inference service further operates to:

when creating the meta data, initialize the meta data of the program objects to indicate the invariants are satisfied by the program objects; and

when its check determines that an invariant is not satisfied by a program object, updating the meta data to indicate the invariant was not satisfied by said object.

14. The computer-readable computer program-carrying storage medium of claim 12 wherein the invariant inference service further operates to track a set of invariants that include at least some of generic invariants, type-specific invariants, allocation-site based invariants, type-wide invariants, and behavioral invariants.

15. The computer-readable computer program-carrying storage medium of claim 12 wherein the program analysis tool further comprises:

programming code operating to add annotations to source code of said program under test based on the invariants reported to be satisfied by at least some of the program objects.

16. The computer-readable computer program-carrying storage medium of claim 12 wherein the program analysis tool further comprises:

programming code operating to cause said invariant inference service to report a set of normative invariants of the program objects for a first execution period of said program under test; and

an anomaly detection code operating, in a subsequent period of execution of said program under test, to detect occurrence of any anomalies in which the normative invariants are violated by said program under test.

17. The computer-readable computer program-carrying storage medium of claim 16 wherein the program analysis tool further comprises:

programming code operating to identify code in said program under test that produced an occurrence of an anomaly as a bug.

18. A dynamic program analysis system for inferring heap invariants of program objects maintained by a program in heap memory, the system comprising:

means for causing the program to execute over a period in an execution environment having a heap memory managed using garbage collection;

means for creating meta data to track invariants of the program objects created by the program in the heap memory;

means responsive to a vitality check of the program objects in a garbage collection pass for checking the invariants of the program objects and updating the meta data based on results of the checking; and

means for producing data reporting the invariants satisfied by the program objects over the period of execution of the program.

19. The system of claim 18, further comprising:

means for, when creating the meta data, initializing the meta data of the program objects to indicate the invariants are satisfied by the program objects; and

means for, when the checking determines that an invariant is not satisfied by a program object, updating the meta data to indicate the invariant was not satisfied by said program object.

20. The system of claim 18, further comprising means for adding annotations to source code of the program based on the invariants reported to be satisfied by at least some of the program objects.