Heap-based bug identification using anomaly detection

• US 20060265694A1
• 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, Ganapathy, Vinod
• Granted Patent: US 7,770,153 B2
• Time in Patent Office: Days
• US Class Current: 717/124
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 11/3616 using software metrics

Abstract

A dynamic analysis tool uses anomaly detection to find heap-based bugs. In spite of the evolving nature of the heap, programs generally exhibit several of properties of their heap usage that remain stable. Periodically, during the execution of the program, the analysis tool computes a suite of metrics which are sensitive to the state of the heap. These metrics track heap behavior, and the stability of the heap reflects quantitatively in the values of these metrics. The ranges of stable metrics, obtained by running a program on a multiple input training set, are then treated as indicators of correct behavior, and are used in conjunction with an anomaly detector to find heap-based bugs.

Claims

1. A method of identifying heap-based bugs, comprising:

building a model of the program'"'"'s heap behavior from observing heap behavior of the program during execution;

detecting anomalous heap behavior deviating from the model; and

reporting information of the anomalous heap behavior indicative of a heap-based bug in the program.

2. The method of claim 1 further comprising:

adaptively building the model and detecting anomalous heap behavior concurrently during a same execution of the program.

3. The method of claim 1 further comprising:

performing said detecting anomalous behavior in on-line fashion during execution of the program.

4. The method of claim 1 wherein detecting anomalous behavior comprises:

recording an execution trace of the program'"'"'s execution;

performing said detecting anomalous behavior in an off-line fashion based on the execution trace.

5. The method of claim 1 wherein said building the model comprises:

causing the program to execute on a training set of inputs;

computing a suite of metrics of the program'"'"'s heap behavior;

determining which of the metrics remain stable.

6. The method of claim 5 further wherein the suite of metrics comprise at least one connectivity-based metric.

7. The method of claim 5 further wherein the suite of metrics comprise at least one degree-based metric.

8. The method of claim 5 further wherein the suite of metrics comprise at least one value-based metric.

9. The method of claim 5 further comprising determining ranges in which the metrics remain stable.

10. The method of claim 9 wherein said detecting anomalous behavior comprises:

periodically computing the metrics during a further execution of the program; and

detecting that the metrics have gone outside of the determined ranges.

11. The method of claim 5 further comprising determining which of the metrics are globally stable.

12. The method of claim 5 further comprising determining which of the metrics are locally stable.

13. A computer system programmed as a dynamic analysis tool for identifying heap-based bugs in programs, comprising:

a model constructor for building a model of a program'"'"'s heap behavior; and

an execution checker for detecting anomalies occurring in an execution of the program in which the program'"'"'s heap behavior deviates from the model.

14. The computer system of claim 13 wherein the model constructor comprises:

a binary instrumenter for adding instrumentation to a program to produce data representative of the program'"'"'s heap usage;

a metric analyzer for causing the program to execute for a training set of inputs, and analyze the data thereby produced by the instrumentation to identify a set of stable, heap-related metrics.

15. The computer system of claim 14 wherein the metric analyzer comprises:

an execution logger operating to adaptively modify a heap-graph tracking the program'"'"'s heap usage during execution of the training set, and to periodically compute a set of metrics based on the heap graph; and

a metric summarizer for identifying which of the metrics computed by the execution logger remain stable.

16. The computer system of claim 14 wherein the set of metrics comprise connectivity-based, degree-based and value-based metrics.

17. The computer system of claim 14 wherein the execution checker comprises:

an execution logger for computing the metrics for an execution of the instrumented program; and

an anomaly detector for detecting anomalies in the stable, heap-related metrics.

18. The computer system of claim 17 further comprising:

a program phase detector for detecting phases of execution of the program;

the metric analyzer further operating based on the phases detected by the program phase detector to identify heap-related metrics that remain locally stable for at least one of the phases; and

the anomaly detector further operating to detect anomalies in the locally stable, heap-related metrics occurring in their respective locally stable phases.

19. A set of computer-readable software-storing media having computer-executable software of a dynamic program analysis tool stored thereon, the dynamic program analysis tool comprising:

executable code for computing a suite of heap-related metrics from one or more execution runs of a program on a training set of inputs;

executable code for calculating a rate of change of the heap-related metrics across the execution runs;

executable code for comparing the rate of change to a threshold rate;

executable code for identifying slowly changing heap-related metrics from the suite whose rate of change remains lower than the threshold rate to be stable metrics;

executable code for establishing ranges of the stable metrics;

executable code for computing the stable metrics from a subsequent execution of the program; and

executable code for detecting anomalies where the stable metrics deviate from their respective ranges.

20. The set of computer-readable software-storing media of claim 19 wherein the dynamic program analysis tool further comprises:

executable code for correlating the detected anomalies with an instruction in the program that caused the anomaly.