Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2015, Vol. 9 Issue (1) : 34-54    https://doi.org/10.1007/s11704-014-3460-8
RESEARCH ARTICLE
Melton: a practical and precise memory leak detection tool for C programs
Zhenbo XU1, Jian ZHANG2(), Zhongxing XU2
1. Department of Computer Science and Technology, University of Science and Technology of China, Anhui 230027, China
2. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
 Download: PDF(1025 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Jian ZHANG   
Issue Date: 09 February 2015
 Cite this article:   
Zhenbo XU,Jian ZHANG,Zhongxing XU. Melton: a practical and precise memory leak detection tool for C programs[J]. Front. Comput. Sci., 2015, 9(1): 34-54.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3460-8
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I1/34
1 D Evans. Static detection of dynamic memory errors. In: Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design an Implementation. 1996, 44−53
https://doi.org/10.1145/231379.231389
2 W R Bush, J D Pincus, D J Sielaff. A static analyzer for finding dynamic programming errors. Software-Practice and Experience, 2000, 30(7): 775−802
https://doi.org/10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H
3 D L Heine, M S Lam. 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
https://doi.org/10.1145/781131.781150
4 Y Xie, A Aiken. 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 M Orlovich, R Rugina. Memory leak analysis by contradiction. In: International Static Analysis Symposium. 2006, 405−424
https://doi.org/10.1007/11823230_26
6 S Cherem, L Princehouse, R Rugina. 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
https://doi.org/10.1145/1250734.1250789
7 Z Xu, J Zhang. Path and context sensitive inter-procedural memory leak detection. In: Proceedings of the 2008 International Conference on Quality Software. 2008, 412−420
https://doi.org/10.1109/QSIC.2008.12
8 Y Jung, K Yi. Practical memory leak detector based on parameterized procedural summaries. In: Proceedings of the 2008 International Symposium on Memory Management. 2008, 131−140
9 J Wang, X D Ma, W Dong, H F Xu, W W Liu. Demand-driven memory leak detection based on flow and context-sensitive pointer analysis. Journal of Computer Science and Technology, 2009, 347−356
https://doi.org/10.1007/s11390-009-9229-0
10 Y Sui, D Ye, J Xue. 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 Z Xu, T Kremenek, J Zhang. 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
https://doi.org/10.1007/978-3-642-16558-0_44
12 R Hastings, B Joyce. Purify: fast detection of memory leaks and access errors. In: Proceedings of the Winter USENIX Conference. 1992, 125−138
13 N Mitchell, G Sevitsky. 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
https://doi.org/10.1007/978-3-540-45070-2_16
14 M Hauswirth, T M Chilimbi. 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 M D Bond, K S McKinley. 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 M Jump, K S McKinley. 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
https://doi.org/10.1145/1190216.1190224
17 G Xu, A Rountev. Precise memory leak detection for java software using container profiling. In: Proceedings of the 2008 International Conference on Software Engineering. 2008, 151−160
18 D Distefano, I Filipovic. Memory leaks detection in java by bi-´ abductive inference. In: Proceedings of Fundamental Approaches to Software Engineering. 2010, 278−292
19 P Godefroid, N Klarlund, K Sen. DART: Directed automated random testing. In: Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and Implementation. 2005, 213−223
https://doi.org/10.1145/1065010.1065036
20 K Sen, D Marinov, G Agha. 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 C Cadar, V Ganesh, P M Pawlowski, D L Dill, D R Engler. EXE: Automatically generating inputs of death. In: Proceedings of the 2006 Conference on Computer and Communications Security. 2006, 322−335
22 Y Xie, A Aiken. 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 G A Kildall. A unified approach to global program optimization. In: Proceedings of Principles of Programming Languages. 1973, 194−206
24 J Clause, A Orso. Leakpoint: pinpointing the causes of memory leaks. In: Proceedings of the 2010 International Conference on Software Engineering. 2010, 515−524
25 W Landi, B G Ryder. A safe approximate algorithm for interprocedural aliasing. In: Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation. 1992, 235−248
https://doi.org/10.1145/143095.143137
26 Clang: a C language family frontend for LLVM.
27 Clang static analyzer.
28 Z Xu, J Zhang, Z Xu. Memory leak detection based on memory state transition graph. In: Proceedings of the 2011 Asia-Pacific Software Engineering Conference. 2011, 33−40
https://doi.org/10.1109/APSEC.2011.22
29 V Ganesh, D L Dill. A decision procedure for bit-vectors and arrays. Lecture Notes in Computer Science, 2007, 4590, 519−531
https://doi.org/10.1007/978-3-540-73368-3_52
[1] Supplementary Material Download
[1] Ningnan ZHOU, Xiao ZHANG, Shan WANG. Timestamp reassignment: taming transaction abort for serializable snapshot isolation[J]. Front. Comput. Sci., 2019, 13(6): 1282-1295.
[2] Anil Kumar KARNA, Jinbo DU, Haihao SHEN, Hao ZHONG, Jiong GONG, Haibo YU, Xiangning MA, Jianjun ZHAO. Tuning parallel symbolic execution engine for better performance[J]. Front. Comput. Sci., 2018, 12(1): 86-100.
[3] Mingsong LV, Nan GUAN, Qingxu DENG, Ge YU, Wang Yi, . Static worst-case execution time analysis of the &#956; C/OS-II real-time kernel[J]. Front. Comput. Sci., 2010, 4(1): 17-27.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed