Low-overhead memory leak detection using adaptive statistical profiling

ABSTRACT

Sampling has been successfully used to identify performance optimization opportunities. We would like to apply similar techniques to check program correctness. Unfortunately, sampling provides poor coverage of infrequently executed code, where bugs often lurk. We describe an adaptive profiling scheme that addresses this by sampling executions of code segments at a rate inversely proportional to their execution frequency. To validate our ideas, we have implemented SWAT, a novel memory leak detection tool. SWAT traces program allocations/ frees to construct a heap model and uses our adaptive profiling infrastructure to monitor loads/stores to these objects with low overhead. SWAT reports 'stale' objects that have not been accessed for a 'long' time as leaks. This allows it to find all leaks that manifest during the current program execution. Since SWAT has low runtime overhead (‹5%), and low space overhead (‹10% in most cases and often less than 5%), it can be used to track leaks in production code that take days to manifest. In addition to identifying the allocations that leak memory, SWAT exposes where the program last accessed the leaked data, which facilitates debugging and fixing the leak. SWAT has been used by several product groups at Microsoft for the past 18 months and has proved effective at detecting leaks with a low false positive rate (‹10%).

REFERENCES

• 1: Erwin Andreasen and Henner Zeller. LeakTracer. August 2003. http://www.andreasen.org/LeakTracer/
• 2: 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
• 3: Hans Boehm, Alan Demers, and Mark Weiser. A garbage collector for C and C++. http://www.hpl.hp.com/personal/ Hans_Boehm/gc/
• 4: Borland OptimizeIt Profiler. http://www.borland.com/optimizeit/optimizeit_profiler/index.html
• 5: 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]
• 6: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 7: Jeremy Dion and Louis Monier. ThirdDegree. http://research.compaq.com/wrl/projects/om/third.html
• 8: EJ-technologies' JProfiler. http://www.ej-technologies.com/products/jprofiler/overview.html
• 9: GreatCircle. http://www.geodesic.com/
• 10: R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the Winter USENIX Conference, pages 125--136, 1992.
• 11: David L. Heine , Monica S. Lam, A practical flow-sensitive and context-sensitive C and C++ memory leak detector, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 12: Martin Hirzel , Amer Diwan , Antony L. Hosking, On the Usefulness of Liveness for Garbage Collection and Leak Detection, Proceedings of the 15th European Conference on Object-Oriented Programming, p.181-206, June 18-22, 2001
• 13: Martin Hirzel , Amer Diwan, On the type accuracy of garbage collection, Proceedings of the 2nd international symposium on Memory management, p.1-11, October 15-16, 2000, Minneapolis, Minnesota, United States
• 14: Martin Hirzel and Trishul M. Chilimbi. Bursty Tracing: A Framework for Low-Overhead Temporal Profiling. In 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO), pages 117--126, December 2001.
• 15: 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
• 16: Paul Moeller. Win32 Java Heap Inspector. 1998. http://www.geocities.com/moellep/debug/HeapInspector.html
• 17: Parasoft Insure++. http://www.parasoft.com/products/insure/
• 18: Quest jProbe Memory Debugger. http://www.quest.com/jprobe/debugger.asp
• 19: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 20: A. Srivastava, A. Edwards, and H. Vo. Vulcan: Binary transformation in a distributed environment. In Microsoft Research Tech Report, MSR-TR-2001-50, 2001.
• 21: Benjamin Zorn and Paul Hilfinger. A memory allocation profiler for C and Lisp programs. In Proceedings of the Summer USENIX Conference, pages 223--237, 1988.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Statistical methods

General Terms:
Measurement, Performance, Reliability, Verification

Keywords:
low-overhead monitoring, memory leaks, runtime analysis