HeapMD: Identifying Heap-based Bugs using Anomaly Detection

Trishul M. Chilimbi, Vinod Ganapathy.

Proceedings of the Twelfth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2006); pages 219--228; San Jose, California; October 21-25, 2006.

We present the design, implementation, and evaluation of HeapMD, a dynamic analysis tool that finds heap-based bugs using anomaly detection. HeapMD is based upon the observation that, in spite of the evolving nature of the heap, several of its properties remain stable. HeapMD uses this observation in a novel way: periodically, during the execution of the program, it 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 "normal" ranges of stable metrics, obtained by running a program on multiple inputs, are then treated as indicators of correct behaviour, and are used in conjunction with an anomaly detector to find heap-based bugs. Using HeapMD, we were able to find 40 heap-based bugs, 31 of them previously unknown, in 5 large, commercial applications.

Paper: [ PDF ] (© ACM)
Erratum: [ Link ] (minor error in the Proceedings version; fixed in the web version)
Slides: [ Powerpoint | PDF ]
Patent: [ US Patent 7,770,153 B2 ]
DOI: [ 10.1145/1168857.1168885 ]

Papers page