Melton: a practical and precise memory leak detection tool for C programs

Abstract

Memory leaks are a common type of defect that is hard to detect manually. Existing memory leak detection tools suffer from lack of precise interprocedural analysis and path-sensitivity. To address this problem, we present a static interprocedural analysis algorithm, that performs fully pathsensitive analysis and captures precise function behaviors, to detect memory leak in C programs. The proposed algorithm uses path-sensitive symbolic execution to track memory actions in different program paths guarded by path conditions. A novel analysis model called memory state transition graph (MSTG) is proposed to describe the tracking process and its results. In order to do interprocedural analysis, the proposed algorithm generates a summary for each procedure from MSTG and applies the summary at the procedure’s call sites. A prototype tool called Melton is implemented for this procedure. Melton was applied to five open source C programs and 41 leaks were found. More than 90% of these leaks were subsequently confirmed and fixed by their maintainers. For comparison with other tools, Melton was also applied to some programs in standard performance evaluation corporation (SPEC) CPU 2000 benchmark suite and detected more leaks than the state of the art approaches.

Keywords

memory leak / bug finding / static analysis / symbolic execution

References

[1] Evans D. Static detection of dynamic memory errors. In: Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design an Implementation. 1996, 44−53

[2] Bush W R, Pincus J D, Sielaff D J. A static analyzer for finding dynamic programming errors. Software-Practice and Experience, 2000, 30(7): 775−802

[3] Heine D L, Lam M S. A practical flow-sensitive and context-sensitive C and C++ memory leak detector. In: Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. 2003, 168−181

[4] Xie Y, Aiken A. Context- and path-sensitive memory leak detection. In: Proceedings of the 2005 Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. 2005, 115−125

[5] Orlovich M, Rugina R. Memory leak analysis by contradiction. In: International Static Analysis Symposium. 2006, 405−424

[6] Cherem S, Princehouse L, Rugina R. Practical memory leak detection using guarded value-flow analysis. In: Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation. 2007, 480−491

[7] Xu Z, Zhang J. Path and context sensitive inter-procedural memory leak detection. In: Proceedings of the 2008 International Conference on Quality Software. 2008, 412−420

[8] Jung Y, Yi K. Practical memory leak detector based on parameterized procedural summaries. In: Proceedings of the 2008 International Symposium on Memory Management. 2008, 131−140

[9] Wang J, Ma X D, Dong W, Xu H F, Liu W W. Demand-driven memory leak detection based on flow and context-sensitive pointer analysis. Journal of Computer Science and Technology, 2009, 347−356

[10] Sui Y, Ye D, Xue J. Static memory leak detection using full-sparse value-flow analysis. In: Proceedings of the 2012 International Symposium on Software Testing and Analysis. 2012, 254−264

[11] Xu Z, Kremenek T, Zhang J. A memory model for static analysis of C programs. In: Proceedings of the 2010 International Symposium on Leveraging Applications of Formal Methods, Verification and Validation. 2010, 535−548

[12] Hastings R, Joyce B. Purify: fast detection of memory leaks and access errors. In: Proceedings of the Winter USENIX Conference. 1992, 125−138

[13] Mitchell N, Sevitsky G. Leakbot: an automated and lightweight tool for diagnosing memory leaks in large java applications. In: Proceedings of the 2003 European Conference on Object-Oriented Programming. 2003, 351−377

[14] Hauswirth M, Chilimbi T M. Low-overhead memory leak detection using adaptive statistical profiling. In: Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems. 2004, 156−164

[15] Bond M D, McKinley K S. Bell: bit-encoding online memory leak detection. In: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems. 2006, 61−72

[16] Jump M, McKinley K S. Cork: dynamic memory leak detection for garbage-collected languages. In: Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2007, 31−38

[17] Xu G, Rountev A. Precise memory leak detection for java software using container profiling. In: Proceedings of the 2008 International Conference on Software Engineering. 2008, 151−160

[18] Distefano D, Filipovic I. Memory leaks detection in java by bi-´ abductive inference. In: Proceedings of Fundamental Approaches to Software Engineering. 2010, 278−292

[19] Godefroid P, Klarlund N, Sen K. DART: Directed automated random testing. In: Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation. 2005, 213−223

[20] Sen K, Marinov D, Agha G. CUTE: a concolic unit testing engine for c. In: Proceedings of the 2005 Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. 2005, 263−272

[21] Cadar C, Ganesh V, Pawlowski P M, Dill D L, Engler D R. EXE: Automatically generating inputs of death. In: Proceedings of the 2006 Conference on Computer and Communications Security. 2006, 322−335

[22] Xie Y, Aiken A. Scalable error detection using Boolean satisfiability. In: Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. 2005, 351−363

[23] Kildall G A. A unified approach to global program optimization. In: Proceedings of Principles of Programming Languages. 1973, 194−206

[24] Clause J, Orso A. Leakpoint: pinpointing the causes of memory leaks. In: Proceedings of the 2010 International Conference on Software Engineering. 2010, 515−524

[25] Landi W, Ryder B G. A safe approximate algorithm for interprocedural aliasing. In: Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation. 1992, 235−248

[26] Clang: a C language family frontend for LLVM.

[27] Clang static analyzer.

[28] Xu Z, Zhang J, Xu Z. Memory leak detection based on memory state transition graph. In: Proceedings of the 2011 Asia-Pacific Software Engineering Conference. 2011, 33−40

[29] Ganesh V, Dill D L. A decision procedure for bit-vectors and arrays. Lecture Notes in Computer Science, 2007, 4590, 519−531

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg