article

HeapMD: identifying heap-based bugs using anomaly detection

Authors:

Trishul M. Chilimbi,

Vinod GanapathyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 41, Issue 11

Pages 219 - 228

https://doi.org/10.1145/1168918.1168885

Published: 20 October 2006 Publication History

Abstract

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.

References

[1]

ARNOLD, M., AND RYDER, B.G. A framework for reducing the cost of instrumented code. In Proc. PLDI (May 2001), ACM, pp. 168--179.

Digital Library

[2]

BUSH, W., PINCUS, J.D., AND SIELAFF, D.J. A static analyzer for finding dynamic programming errors. Software-Practice and Experience 30, 7 (2000), 775--802.

Digital Library

[3]

CHILIMBI, T.M., AND HAUSWIRTH, M. Low-overhead memory leak detection using adaptive statistical profiling. In Proc. ASPLOS (October 2004), ACM, pp. 156--164.

Digital Library

[4]

DEMSKY, B., AND RINARD, M. Role-based exploration of objectoriented programs. In Proc. ICSE (May 2002), IEEE/ACM, pp. 313--334.

Digital Library

[5]

DEMSKY, B., AND RINARD, M. Automatic detection and repair of errors in data structures. In Proc. OOPSLA (October 2003), ACM, pp. 78--95.

Digital Library

[6]

DING, C., AND ZHONG, Y. Predicting whole-program locality with reuse distance analysis. In Proc. PLDI (June 2003), ACM, pp. 245--257.

Digital Library

[7]

EDWARDS, A., SRIVASTAVA, A., AND VO, H. Vulcan: Binary transformation in a distributed environment. Tech. Rep. 2001-50, Microsoft Research, April 2001.

[8]

ERNST, M.D. Dynamically Discovering Likely Program Invariants. PhD thesis, University of Washington, Seattle, WA, August 2000.

Digital Library

[9]

GHIYA, R., AND HENDREN, L. Is it a Tree, a DAG or a Cyclic Graph? A shape analysis for heap-directed pointers in C. In Proc. POPL (January 1996), ACM, pp. 1--15.

Digital Library

[10]

HACKETT, B., AND RUGINA, R. Region-based shape analysis with tracked locations. In Proc. POPL (January 2005), ACM, pp. 310--323.

Digital Library

[11]

HANGAL, S., AND LAM, M.S. Tracking down software bugs using automatic anomaly detection. In Proc. ICSE (May 2002), IEEE/ACM, pp. 291--301.

Digital Library

[12]

HASTINGS, R., AND JOYCE, B. Purify: Fast detection of memory leaks and access errors. In Winter USENIX Conference (January 1992).

[13]

HIRZEL, M., AND CHILIMBI, T.M. Bursty tracing: A framework for low-overhead temporal profiling. In Proc. Wkshp. on Feedback-Directed and Dynamic Optimization (December 2001).

[14]

HIRZEL, M., HENKEL, J., DIWAN, A., AND HIND, M. Understanding the connectivity of heap objects. In Proc. ISMM (June 2002), ACM, pp. 143--156.

Digital Library

[15]

KREMENEK, T., ASHCRAFT, K., YANG, J., AND ENGLER, D. Correlation exploitation in error ranking. In Proc. SIGSOFT FSE (November 2004), ACM, pp. 83--93.

Digital Library

[16]

KREMENEK, T., AND ENGLER, D. Z-Ranking: Using statistical analysis to counter the impact of static analysis approximations. In Proc. Intl. Static Analysis Symp. (SAS) (June 2003), pp. 295--315.

Digital Library

[17]

LI, Z., LU, S., MYAGMAR, S., AND ZHOU, Y. Cp-miner: A tool for finding copy-paste and related bugs in operating system code. In Proc. OSDI (Dec. 2004), ACM/USENIX, pp. 289--302.

Digital Library

[18]

LIBLIT, B., AIKEN, A., ZHENG, A.X., AND JORDAN, M.I. Bug isolation via remote program sampling. In Proc. PLDI (June 2003), ACM, pp. 141--154.

Digital Library

[19]

NETHERCOTE, N., AND SEWARD, J. Valgrind: A program supervision framework. Elec. Notes in Theor. Comp. Sci. (ENTCS) 89, 2 (2003).

[20]

QADEER, S., AND LAHIRI, S. Verifying properties of well-founed linked lists. In Proc. POPL (Jan. 2006), ACM.

Digital Library

[21]

QIN, F., TUCEK, J., SUNDARESAN, J., AND ZHOU, Y. Rx: Treating bugs as allergies-a safe method to survive software failures. In Proc. SOSP (Oct 2005), ACM, pp. 235--248.

Digital Library

[22]

RINARD, M., CADAR, C., DUMITRAN, D., ROY, D., LEU, T., AND BEEBEE, W. Enhancing server availability and security through failure-oblivious computing. In Proc. OSDI (December 2004), pp. 303--316.

Digital Library

[23]

RUBIN, S., BODIK, R., AND CHILIMBI, T.M. An efficient profileanalysis framework for data-layout optimizations. In Proc. POPL (January 2002), ACM, pp. 140--153.

Digital Library

[24]

SAGIV, M., REPS, T.W., AND WILHELM, R. Parametric shape analysis via 3-valued logic. ACM TOPLAS 24, 3 (May 2002), 217--298.

Digital Library

[25]

SEKAR, R., BENDRE, M., DHURJATI, D., AND BOLLINENI, P. A fast automaton-based method for detecting anomalous program behaviors. In Symp. on Security and Privacy (May 2001), IEEE, pp. 144--155.

Digital Library

[26]

SHEN, X., ZHONG, Y., AND DING, C. Locality phase prediction. In Proc. ASPLOS (October 2004), ACM, pp. 165--176.

Digital Library

[27]

SHERWOOD, T., PERELMAN, E., HAMERLY, G., AND CALDER, B. Automatically characterizing large scale program behaviour. In Proc. ASPLOS (October 2002), ACM, pp. 45--57.

Digital Library

[28]

SHERWOOD, T., SAIR, S., AND CALDER, B. Phase tracking and prediction. In Proc. ISCA (June 2003), pp. 288--299.

Digital Library

[29]

WAGNER, D., AND DEAN, D. Intrusion detection via static analysis. In Symp. on Security and Privacy (May 2001), IEEE, pp. 156--169.

Digital Library

[30]

YAHAV, E., AND RAMALINGAM, G. Verifying safety properties using separation and heterogenous abstractions. In Proc. PLDI (June 2004), ACM, pp. 25--34.

Digital Library

[31]

ZHOU, P., LIU, W., LONG, F., LU, S., QIN, F., ZHOU, Y., MIDKIFF, S., AND TORRELLAS, J. AccMon: Automatically detecting memoryrelated bugs via program counter-based invariants. In Proc. MICRO (December 2004), IEEE/ACM, pp. 269--280.

Digital Library

Cited By

Zhou TJantz MKulkarni PDoshi KSarkar VAmaral JKulkarni M(2019)Valence: variable length calling context encodingProceedings of the 28th International Conference on Compiler Construction10.1145/3302516.3307351(147-158)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3302516.3307351
Zheng WHua B(2024)WASMDYPA: Effectively Detecting WebAssembly Bugs via Dynamic Program Analysis2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00037(296-307)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00037
Lehmann DPradel MBahar IHerlihy MWitchel ELebeck A(2019)WasabiProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304068(1045-1058)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304068
Show More Cited By

Index Terms

HeapMD: identifying heap-based bugs using anomaly detection
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

HeapMD: identifying heap-based bugs using anomaly detection
Proceedings of the 2006 ASPLOS Conference

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 ...
HeapMD: identifying heap-based bugs using anomaly detection
ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems

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 ...
HeapMD: identifying heap-based bugs using anomaly detection
Proceedings of the 2006 ASPLOS Conference

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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 41, Issue 11

Proceedings of the 2006 ASPLOS Conference

November 2006

425 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1168918

Issue’s Table of Contents

ASPLOS XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems
October 2006
440 pages
ISBN:1595934510
DOI:10.1145/1168857
General Chair:
John Paul Shen
Intel Corp.
,
Program Chair:
Margaret R. Martonosi
Princeton University

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 October 2006

Published in SIGPLAN Volume 41, Issue 11

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
605
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhou TJantz MKulkarni PDoshi KSarkar VAmaral JKulkarni M(2019)Valence: variable length calling context encodingProceedings of the 28th International Conference on Compiler Construction10.1145/3302516.3307351(147-158)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3302516.3307351
Zheng WHua B(2024)WASMDYPA: Effectively Detecting WebAssembly Bugs via Dynamic Program Analysis2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00037(296-307)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00037
Lehmann DPradel MBahar IHerlihy MWitchel ELebeck A(2019)WasabiProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304068(1045-1058)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304068
Barowy DBerger EZorn B(2018)ExceLint: automatically finding spreadsheet formula errorsProceedings of the ACM on Programming Languages10.1145/32765182:OOPSLA(1-26)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276518
Murali VChaudhuri SJermaine CBodden ESchäfer WDeursen AZisman A(2017)Bayesian specification learning for finding API usage errorsProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106284(151-162)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106284
Zeng QRhee JZhang HArora NJiang GLiu P(2014)DeltaPathProceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization10.1145/2581122.2544150(109-119)Online publication date: 15-Feb-2014
https://dl.acm.org/doi/10.1145/2581122.2544150
Zeng QRhee JZhang HArora NJiang GLiu P(2014)DeltaPathProceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization10.1145/2544137.2544150(109-119)Online publication date: 15-Feb-2014
https://dl.acm.org/doi/10.1145/2544137.2544150
or VOü PTreier TSrirama S(2013)Improving Statistical Approach for Memory Leak Detection Using Machine LearningProceedings of the 2013 IEEE International Conference on Software Maintenance10.1109/ICSM.2013.92(544-547)Online publication date: 22-Sep-2013
https://dl.acm.org/doi/10.1109/ICSM.2013.92
Sumner WZheng YWeeratunge DZhang X(2012)Precise Calling Context EncodingIEEE Transactions on Software Engineering10.1109/TSE.2011.7038:5(1160-1177)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1109/TSE.2011.70
Yang JEvans D(2011)Automatic Inference and Effective Application of Temporal SpecificationsMining Software Specifications10.1201/b10928-9(241-307)Online publication date: 28-Jul-2011
https://doi.org/10.1201/b10928-9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents