HeapMD: identifying heap-based bugs using anomaly detection

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: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 2: William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
• 3: Matthias Hauswirth , Trishul M. Chilimbi, Low-overhead memory leak detection using adaptive statistical profiling, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 4: Brian Demsky , Martin Rinard, Role-based exploration of object-oriented programs, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581379]
• 5: Brian Demsky , Martin Rinard, Automatic detection and repair of errors in data structures, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 6: Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 7: EDWARDS, A., SRIVASTAVA, A., AND VO, H. Vulcan: Binary transformation in a distributed environment. Tech. Rep. 2001-50, Microsoft Research, April 2001.
• 8: Michael Dean Ernst , David Notkin, Dynamically discovering likely program invariants, 2000
• 9: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 10: Brian Hackett , Radu Rugina, Region-based shape analysis with tracked locations, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.310-323, January 12-14, 2005, Long Beach, California, USA
• 11: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 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: Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 15: Ted Kremenek , Ken Ashcraft , Junfeng Yang , Dawson Engler, Correlation exploitation in error ranking, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 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.
• 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.
• 18: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 19: NETHERCOTE, N., AND SEWARD, J. Valgrind: A program supervision framework. Elec. Notes in Theor. Comp. Sci. (ENTCS) 89, 2 (2003).
• 20: Shuvendu K. Lahiri , Shaz Qadeer, Verifying properties of well-founded linked lists, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.115-126, January 11-13, 2006, Charleston, South Carolina, USA
• 21: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 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.
• 23: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon
• 24: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.3, p.217-298, May 2002 [doi>10.1145/514188.514190]
• 25: R. Sekar , M. Bendre , D. Dhurjati , P. Bollineni, A Fast Automaton-Based Method for Detecting Anomalous Program Behaviors, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.144, May 14-16, 2001
• 26: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 27: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 28: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 29: David Wagner , Drew Dean, Intrusion Detection via Static Analysis, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.156, May 14-16, 2001
• 30: Eran Yahav , G. Ramalingam, Verifying safety properties using separation and heterogeneous abstractions, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 31: Pin Zhou , Wei Liu , Long Fei , Shan Lu , Feng Qin , Yuanyuan Zhou , Samuel Midkiff , Josep Torrellas, AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.269-280, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.3]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Debuggers

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

General Terms:
Experimentation, Measurement, Reliability

Keywords:
anomaly detection, bugs, debugging, heap, metrics