Heap-based bug identification using anomaly detection

• US 7,770,153 B2
• Filed: 05/20/2005
• Issued: 08/03/2010
• Est. Priority Date: 05/20/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ganapathy, Vinod, Chilimbi, Trishul
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): Coyer; Ryan D
• Application Number:
  US11/134,812
• Publication Number:
  US 20060265694A1
• Time in Patent Office: 1,901 Days
• Field of Search: 717124-136, 714/38, 714/100
• US Class Current: 717/127
• 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 heap behavior for a program executing on a computer comprising physical memory devices such that at least some memory storage for the program on the memory devices is managed as a heap, the building occurring by observing heap behavior of the program during execution, the model comprising a suite of numerical metrics, the numerical metrics measuring structure of a heap-graph which represents objects and pointers between objects in the heap;

calculating a rate of change of the numerical metrics across one or more execution runs and comparing the rate of change to a threshold rate;

identifying slowly-changing numerical metrics from the suite whose rate of change remains lower than the threshold rate to be globally stable;

detecting anomalous heap behavior deviating from the model, wherein the detecting comprises computing the globally stable metrics from a subsequent execution of the program and detecting anomalies where the globally stable metrics deviate from predefined acceptable ranges, wherein the detecting ignores startup and shutdown of the program; and

reporting information of the anomalous heap behavior as 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 single 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; and

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 the suite of numerical metrics for the heap-graph, the numerical metrics representing the program'"'"'s heap behavior; and

determining which of the numerical metrics remain stable.

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

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

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

9. The method of claim 5 further comprising determining numerical ranges in which the metrics for the heap-graph remain stable.

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

periodically computing the metrics for the heap-graph 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 for the heap-graph are locally stable.

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

a processor;

memory devices, the memory devices containing memory storage for a program executing on the processor, the memory storage managed as a heap;

the processor configured to perform;

detecting phases of execution of the program;

building a model of heap behavior for the program, the model comprising a set of numerical metrics, the numerical metrics measuring properties of a heap-graph which represents objects and pointers between objects in the heap and which is modified as the heap changes;

calculating a rate of change of the numerical metrics across one or more execution runs and comparing the rate of change to a threshold rate;

identifying slowly-changing numerical metrics from the set whose rate of change remains lower than the threshold rate within a detected phase of execution to be locally stable; and

detecting anomalies occurring in an execution of the program in which heap behavior of the program deviates from the model wherein the detecting comprises computing the locally stable metrics from a subsequent execution of the program and detecting anomalies where the locally stable metrics deviate from predefined acceptable ranges, wherein the detecting ignores startup and shutdown of the program; and

reporting information of the anomalies as indicative of a heap-based bug in the program.

13. The computer system of claim 12 wherein building a model comprises:

adding instrumentation to a program to produce data representative heap usage of the program; and

executing the program for a training set of inputs, and analyzing the data thereby produced by the instrumentation to identify a set of stable, heap-related metrics.

14. The computer system of claim 13 wherein executing the program comprises:

adaptively modifying the heap-graph tracking heap usage of the program during execution of the training set, and periodically computing the set of numerical metrics based on the heap-graph; and

identifying which of the numerical metrics remain stable.

15. The computer system of claim 13 wherein the set of metrics for the heap-graph comprise connectivity-based, degree-based and value-based metrics.

16. The computer system of claim 13 wherein detecting anomalies occurring in the execution of the program comprises:

computing the set of numerical metrics for the heap-graph for an execution of the instrumented program; and

detecting anomalies in the stable, heap-related metrics.

17. The computer system of claim 16, wherein the processor is further configured to perform:

based on the phases detected, identify identifying metrics for the heap-graph that remain locally stable for at least one of the phases; and

detecting anomalies in the locally stable, metrics for the heap-graph occurring in their respective locally stable phases.

18. A set of one or more computer-readable software-storing media having computer-executable instructions of a dynamic program analysis tool stored thereon, the computer-executable instructions causing a computer to perform:

computing a suite of numerical heap-related metrics from one or more execution runs of a program on a training set of inputs, the program executing on a computer comprising physical memory devices such that at least some memory storage for the program on the memory devices is managed as a heap, and the numerical heap-related metrics measure structure of a heap-graph which represents pointers between objects in the heap during the one or more execution runs;

recording an instruction that causes a write to a location of the heap;

calculating a rate of change of the heap-related metrics across the one or more execution runs;

comparing the rate of change to a threshold rate;

identifying phases in the program;

identifying slowly changing heap-related metrics from the suite whose rate of change remains lower than the threshold rate to be globally stable or locally stable metrics, wherein the identifying ignores startup and shutdown of the program for purposes of evaluating globally stable metrics;

establishing ranges of the globally stable or locally stable metrics;

computing the globally stable or locally stable metrics from a subsequent execution of the program, wherein the computing restricts attention to data members of a particular type; and

detecting anomalies where the globally stable or locally stable metrics deviate from their respective ranges.

19. The set of one or more computer-readable software-storing media of claim 18 wherein the computer-executable instructions further comprise computer-executable instructions causing the computer to perform:

correlating the detected anomalies with an instruction in the program that caused a respective anomaly.

20. The set of one or more computer-readable software-storing media of claim 18 wherein the numerical heap-related metrics comprise:

number of connected components;

number of strongly connected components;

ratio of edges to vertices in the heap-graph; and

ratio of heap locations that, during their lifetime, store only a value NULL.