research-article

AutoFix: an automated approach to memory leak fixing on value-flow slices for C programs

Authors:

Jingling XueAuthors Info & Claims

ACM SIGAPP Applied Computing Review, Volume 16, Issue 4

Pages 38 - 50

https://doi.org/10.1145/3040575.3040579

Published: 13 January 2017 Publication History

Abstract

C is the most widely used programming language for developing embedded software, operating systems, and device drivers. Unlike programs written in managed languages like Java, C programs rely on explicit memory management, and are therefore prone to memory leaks. Existing (static or dynamic) debugging tools only report leaks, but fixing them often requires considerable manual effort by inspecting a list of reported true and false alarms. How to develop on-demand lightweight techniques for automated leak fixing without introducing new memory errors remains challenging.

In this paper, we introduce AutoFix, a fully automated leak-fixing approach for C programs by combining static and dynamic program analyses. Given a leaky allocation site reported by a static memory leak detector, AutoFix performs a graph reachability analysis to identify leaky paths on the value-flow slices of the program, and then conducts a liveness analysis to locate the program points for inserting fixes (i.e., the missing free calls) on the identified leaky paths. We have implemented AutoFix in LLVM-3.5.0 and evaluated it using five SPEC2000 benchmarks and three open-source applications. Experimental results show that AutoFix can safely fix all the memory leaks reported by a state-of-the-art static memory leak detector with small instrumentation overhead.

References

[1]

A. Arcuri and X. Yao. A novel co-evolutionary approach to automatic software bug fixing. In IEEE World Congress on Computational Intelligence, pages 162--168, 2008.

[2]

H.-J. Boehm. Bounding space usage of conservative garbage collectors. In POPL '02, pages 93--100, 2002.

Digital Library

[3]

M. D. Bond and K. S. McKinley. Tolerating memory leaks. In OOPSLA '08, pages 109--126, 2008.

Digital Library

[4]

D. Bruening and Q. Zhao. Practical memory checking with dr. memory. In CGO '11, pages 213--223, 2011.

Digital Library

[5]

S. Calman and J. Zhu. Increasing the scope and resolution of interprocedural static single assignment. In SAS'09, pages 154--170, 2009.

Digital Library

[6]

S. Cherem, L. Princehouse, and R. Rugina. Practical memory leak detection using guarded value-flow analysis. In PLDI '07, pages 480--491, 2007.

Digital Library

[7]

F. Chow, S. Chan, S. Liu, R. Lo, and M. Streich. Effective representation of aliases and indirect memory operations in SSA form. In CC '96, pages 253--267, 1996.

[8]

J. Clause and A. Orso. Leakpoint: pinpointing the causes of memory leaks. In ICSE '10, pages 515--524, 2010.

Digital Library

[9]

V. Dallmeier, A. Zeller, and B. Meyer. Generating fixes from object behavior anomalies. In ASE '09, pages 550--554, 2009.

Digital Library

[10]

Q. Gao, Y. Xiong, Y. Mi, L. Zhang, W. Yang, Z. Zhou, B. Xie, and H. Mei. Safe memory-leak fixing for C programs. In ICSE'15, pages 459--470, 2015.

[11]

C. L. Goues, T. Nguyen, S. Forrest, and W. Weimer. Genprog: A generic method for automatic software repair. IEEE Trans. on Software Engineering, 38(1):54--72, 2012.

Digital Library

[12]

B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. In CGO '11, pages 289--298, 2011.

[13]

M. Hauswirth and T. M. Chilimbi. Low-overhead memory leak detection using adaptive statistical profiling. In ASPLOS '04, pages 156--164, 2004.

Digital Library

[14]

M. Hirzel, A. Diwan, and J. Henkel. On the usefulness of type and liveness accuracy for garbage collection and leak detection. ACM Transactions on Programming Languages and Systems, 24(6):593--624, 2002.

Digital Library

[15]

G. Jin, W. Zhang, D. Deng, B. Liblit, and S. Lu. Automated concurrency-bug fixing. In OSDI '12, pages 221--236, 2012.

Digital Library

[16]

Y. Jung and K. Yi. Practical memory leak detector based on parameterized procedural summaries. In ISMM'08, pages 131--140, 2008.

Digital Library

[17]

C. Le Goues, S. Forrest, and W. Weimer. Current challenges in automatic software repair. Software Quality Journal, 21(3):421--443, 2013.

Digital Library

[18]

L. Li, C. Cifuentes, and N. Keynes. Boosting the performance of flow-sensitive points-to analysis using value flow. In FSE '11, pages 343--353.

Digital Library

[19]

L. Li, C. Cifuentes, and N. Keynes. Precise and scalable context-sensitive pointer analysis via value flow graph. In ISMM'13, pages 85--96, 2013.

Digital Library

[20]

D. Mezzatto. Sentinel 2.8 branch memory leak in redis, https://github.com/antirez/redis/issues/2012, 2014.

[21]

N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. In PLDI '07, pages 89--100, 2007.

Digital Library

[22]

H. D. T. Nguyen, D. Qi, A. Roychoudhury, and S. Chandra. Semfix: Program repair via semantic analysis. In ICSE '13, pages 772--781, 2013.

Digital Library

[23]

G. Novark, E. D. Berger, and B. G. Zorn. Plug: automatically tolerating memory leaks in C and C++ applications. Technical Report UM-CS-2008-009, University of Massachusetts, 2008.

[24]

J. H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, et al. Automatically patching errors in deployed software. In SOSP '09, pages 87--102, 2009.

Digital Library

[25]

J. Rafkind, A. Wick, J. Regehr, and M. Flatt. Precise garbage collection for c. In ISMM '09, pages 39--48, 2009.

Digital Library

[26]

D. Rayside and L. Mendel. Object ownership profiling: a technique for finding and fixing memory leaks. In ASE'07, pages 194--203, 2007.

Digital Library

[27]

K. Serebryany, D. Bruening, A. Potapenko, and D. Vyukov. AddressSanitizer: A fast address sanity checker. In USENIX Annual Technical Conference, pages 309--318, 2012.

Digital Library

[28]

M. Sridharan, S. J. Fink, and R. Bodik. Thin slicing. In PLDI '07, pages 112--122, 2007.

Digital Library

[29]

Y. Sui, P. Di, and J. Xue. Sparse flow-sensitive pointer analysis for multithreaded C programs. In CGO'16.

Digital Library

[30]

Y. Sui and J. Xue. On-demand strong update analysis via value-flow refinement. In FSE'16, pages 460--473, 2016.

Digital Library

[31]

Y. Sui, D. Ye, Y. Su, and J. Xue. Eliminating redundant bounds checks in dynamic buffer overflow detection using weakest preconditions. IEEE Transactions on Reliability, 65(4):1682--1699, 2016.

[32]

Y. Sui, D. Ye, and J. Xue. Static memory leak detection using full-sparse value-flow analysis. In ISSTA '12, pages 254--264, 2012.

Digital Library

[33]

Y. Sui, D. Ye, and J. Xue. Detecting memory leaks statically with full-sparse value-flow analysis. IEEE Transactions on Software Engineering, 40(2):107--122, 2014.

Digital Library

[34]

Y. Sui, S. Ye, J. Xue, and P. Yew. SPAS: Scalable path-sensitive pointer analysis on full-sparse SSA. In APLAS '11, pages 155--171.

[35]

Y. Sui, S. Ye, J. Xue, and J. Zhang. Making context-sensitive inclusion-based pointer analysis practical for compilers using parameterised summarisation. Software: Practice and Experience, 44(12):1485--1510, 2014.

Digital Library

[36]

Y. Tang, Q. Gao, and F. Qin. Leaksurvivor: towards safely tolerating memory leaks for garbage-collected languages. In USENIX Annual Technical Conference, pages 307--320, 2008.

Digital Library

[37]

Y. Wei, Y. Pei, C. A. Furia, L. S. Silva, S. Buchholz, B. Meyer, and A. Zeller. Automated fixing of programs with contracts. In ISSTA '10, pages 61--72, 2010.

Digital Library

[38]

Y. Xie and A. Aiken. Context- and path-sensitive memory leak detection. In FSE'05, pages 116--125, 2005.

Digital Library

[39]

G. Xu, M. D. Bond, F. Qin, and A. Rountev. Leakchaser: helping programmers narrow down causes of memory leaks. In PLDI '11, pages 270--282, 2011.

Digital Library

[40]

H. Yan, Y. Sui, S. Chen, and J. Xue. Automated memory leak fixing on value-flow slices for C programs. In SAC'16, pages 1386--1393, 2016.

Digital Library

[41]

D. Ye, Y. Su, Y. Sui, and J. Xue. Wpbound: Enforcing spatial memory safety efficiently at runtime with weakest preconditions. In ISSRE'14, pages 88--99, 2014.

Digital Library

[42]

D. Ye, Y. Sui, and J. Xue. Accelerating dynamic detection of uses of undefined variables with static value-flow analysis. In CGO '14, pages 154--164.

[43]

S. Ye, Y. Sui, and J. Xue. Region-based selective flow-sensitive pointer analysis. In SAS '14, pages 319--336. Springer, 2014.

Cited By

Murali AAlfadel MNagappan MXu MSun C(2024)AddressWatcher: Sanitizer-Based Localization of Memory Leak FixesIEEE Transactions on Software Engineering10.1109/TSE.2024.343811950:9(2398-2411)Online publication date: Sep-2024
https://doi.org/10.1109/TSE.2024.3438119
Madhav C HCheramangalath U(2023)Memory leak detection using Heap Object Flow Graph (HOFG)Proceedings of the 16th Innovations in Software Engineering Conference10.1145/3578527.3578528(1-11)Online publication date: 23-Feb-2023
https://dl.acm.org/doi/10.1145/3578527.3578528

Index Terms

AutoFix: an automated approach to memory leak fixing on value-flow slices for C programs
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
    2. Extra-functional properties
      1. Software performance
      2. Software reliability

Recommendations

Automated memory leak fixing on value-flow slices for C programs
SAC '16: Proceedings of the 31st Annual ACM Symposium on Applied Computing

C is the dominant programming language for developing embedded software, operating systems, and device drivers. Unlike programs written in managed languages like Java, C programs rely on explicit memory management and are prone to memory leaks. Existing ...
Practical memory leak detection using guarded value-flow analysis
PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

This paper presents a practical inter-procedural analysis algorithm for detecting memory leaks in C programs. Our algorithm tracks the flow of values from allocation points to deallocation points using a sparse representation of the program consisting ...
Practical memory leak detection using guarded value-flow analysis
Proceedings of the 2007 PLDI conference

This paper presents a practical inter-procedural analysis algorithm for detecting memory leaks in C programs. Our algorithm tracks the flow of values from allocation points to deallocation points using a sparse representation of the program consisting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGAPP Applied Computing Review

ACM SIGAPP Applied Computing Review Volume 16, Issue 4

December 2016

46 pages

ISSN:1559-6915

EISSN:1931-0161

DOI:10.1145/3040575

Editor:
Sung Y. Shin

Issue’s Table of Contents

Copyright © 2017 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 January 2017

Published in SIGAPP Volume 16, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
201
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Murali AAlfadel MNagappan MXu MSun C(2024)AddressWatcher: Sanitizer-Based Localization of Memory Leak FixesIEEE Transactions on Software Engineering10.1109/TSE.2024.343811950:9(2398-2411)Online publication date: Sep-2024
https://doi.org/10.1109/TSE.2024.3438119
Madhav C HCheramangalath U(2023)Memory leak detection using Heap Object Flow Graph (HOFG)Proceedings of the 16th Innovations in Software Engineering Conference10.1145/3578527.3578528(1-11)Online publication date: 23-Feb-2023
https://dl.acm.org/doi/10.1145/3578527.3578528

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents