Detecting and eliminating memory leaks using cyclic memory allocation

ABSTRACT

We present and evaluate a new technique for detecting and eliminating memory leaks in programs with dynamic memory allocation. This technique observes the execution of the program on a sequence oftraining inputs to find m-bounded allocation sites, which have the property that at any time during the execution of the program, the program accesses at most only the last m objects allocated at that site. If the difference between the number of allocated and deallocated objects from the site grows above m throughout the computation, there is a memory leak at that site. To eliminate the leak, the technique transforms the program to use cyclic memory allocation at that site: it preallocates a buffer containing m objects of the type allocated at that site, with each allocation returning the next object in the buffer. At the end of the buffer the allocations wrap back around to the first object. Cyclic allocationeliminates any memory leak at the allocation site -- the total amountof memory required to hold all of the objects ever allocated at the site is simply m times the object size. We evaluate our technique by applying it to several widely-used open source programs. Our results show that it is able to successfully detect and eliminate important memory leaks in these programs. Apotential concern is that the estimated bounds m may be too small, causing the program to overlay live objects in memory. Our results indicate that our bounds estimation technique is quite accurate in practice, providing incorrect results for only one of the 160 m-bounded sites that it identifies. To evaluate the potential impact of overlaying live objects, we artificially reduce the bounds at m-bounded sites and observe the resulting behavior. The resulting overlaying of live objects often does not affect the functionality ofthe program at all; even when it does impair part of the functionality, the program does not fail and is still able to acceptably deliver the remaining functionality.

REFERENCES

• 1: CVE--2002--0069. http://cve.mitre.org/cgi--bin/cvename.cgi?name=CVE--2002--0069.
• 2: Freeciv website. http://www.freeciv.org/.
• 3: Pine website. http://www.washington.edu/pine/.
• 4: Squid Web Proxy Cache website. http://www.squid--cache.org/.
• 5: Valgrind website. http://www.valgrind.org/.
• 6: K. Arkoudas and M. Rinard. Deductive runtime certification. In Proceedings of the 2004 Workshop on Runtime Verification (RV all2004), Barcelona, Spain, April 2004.
• 7: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 8: M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
• 9: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 10: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 11: 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
• 12: Brian Demsky , Martin Rinard, Data structure repair using goal-directed reasoning, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062499]
• 13: 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]
• 14: 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
• 15: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 16: Andy Chow Chou , Dawson Engler, Static analysis for bug finding in systems software, Stanford University, Stanford, CA, 2003
• 17: D. Detlefs, A. Dosser, and B. Zorn. Memory Allocation Costs in Large C and C++ Programs. Technical Report CU--CS--665--93, University of Colorado, Boulder, August 1993.
• 18: Octavian--Daniel Dumitran. Fixing file descriptor leaks. Master's thesis, Massachusetts Institute of Technology, June 2007.
• 19: Cal Erickson, Memory leak detection in C++, Linux Journal, v.2003 n.110, p.8, June 2003
• 20: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 21: Ovidiu Gheorghioiu , Alexandru Salcianu , Martin Rinard, Interprocedural compatibility analysis for static object preallocation, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, January 15-17, 2003, New Orleans, Louisiana, USA
• 22: 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
• 23: R. Hastings and B. Joyce. Purify: Fast detection of memory leaks and access errors. In Proceedings of the Winter USENIX Conference, December 1992.
• 24: 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
• 25: Maria Jump , Kathryn S. McKinley, Cork: dynamic memory leak detection for garbage-collected languages, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 26: Martin Rinard , Cristian Cadar , Daniel Dumitran , Daniel M. Roy , Tudor Leu , William S. Beebee, Jr., Enhancing server availability and security through failure-oblivious computing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.21-21, December 06-08, 2004, San Francisco, CA
• 27: Ran Shaham, Eran Yahav, Elliot K. Kolodner, and Mooly Sagiv. Establishing Local Temporal Heap Safety Properties with Applications to Compile--Time Memory Management. In The 10th Annual International Static Analysis Symposium (SAS '03), June 2003.
• 28: Ran Shaham , Elliot K. Kolodner , Shmuel Sagiv, Automatic Removal of Array Memory Leaks in Java, Proceedings of the 9th International Conference on Compiler Construction, p.50-66, March 25-April 02, 2000
• 29: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 30: Yichen Xie , Alex Aiken, Context- and path-sensitive memory leak detection, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 31: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

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

General Terms:
Design, Experimentation, Reliability, Security

Keywords:
cyclic memory allocation, failure-oblivious computing, memory leaks