More Web Proxy on the site http://driver.im/

Article

Practical memory leak detection using guarded value-flow analysis

Authors:

Sigmund Cherem,

Lonnie Princehouse,

Radu RuginaAuthors Info & Claims

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 480 - 491

https://doi.org/10.1145/1250734.1250789

Published: 10 June 2007 Publication History

Abstract

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 of a value flow graph that captures def-use relations and value flows via program assignments. Edges in the graph are annotated with guards that describe branch conditions in the program. The memory leak analysis is reduced to a reachability problem over the guarded value flowgraph. Our implemented tool has been effective at detecting more than 60 memory leaks in the SPEC2000 benchmarks and in two open-source applications, bash and sshd, while keeping the false positive rate below 20%. The sparse program representation makes the tool efficient in practice, and allows it to report concise error messages.

References

[1]

Thomas Ball, Rupak Majumdar, Todd Millstein, and Sriram K. Rajamani. Automatic predicate abstraction of C programs. In Proceedings of the ACM Conference on Program Language Design and Implementation, Snowbird, Utah, June 2001.

Digital Library

[2]

Thomas Ball and Sriram K. Rajamani. The SLAM project: debugging system software via static analysis. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, Portland, OR, January 2002.

Digital Library

[3]

Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, and F. Kenneth Zadeck. An efficient method of computing static single assignment form. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, Austin, TX, June 1989.

Digital Library

[4]

Manuvir Das, Sorin Lerner, and Mark Seigle. ESP: Path-sensitive program verification in polynomial time. In Proceedings of the ACM Conference on Program Language Design and Implementation, Berlin, Germany, June 2002.

Digital Library

[5]

Nurit Dor, Michael Rodeh, and Mooly Sagiv. Checking cleanness in linked lists. In Proceedings of the International Static Analysis Symposium, Santa Barbara, CA, July 2000.

Digital Library

[6]

Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the Symposium on Operating System Design and Implementation, San Diego, CA, October 2000.

Digital Library

[7]

Jeffrey S. Foster, Robert Johnson, John Kodumal, and Alex Aiken. Flow-insensitive type qualifiers. ACM Transactions on Programming Languages and Systems, 28(6):1035--1087, November 2006.

Digital Library

[8]

Emden R. Gansner and Stephen C. North. An open graph visualization system and its applications to software engineering. Software -- Practice and Experience, 30(11):1203--1233, 2000.

Digital Library

[9]

Brian Hackett and Radu Rugina. Shape analysis with tracked locations. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, Long Beach, CA, January 2005.

Digital Library

[10]

David L. Heine and Monica S. Lam. A practical flow-sensitive and context-sensitive C and C++ memory leak detector. In Proceedings of the ACM Conference on Program Language Design and Implementation, San Diego, CA, June 2003.

Digital Library

[11]

David L. Heine and Monica S. Lam. Static detection of leaks in polymorphic containers. In Proceeding of the International Conference on Software Engineering (ICSE), Shanghai, China, May 2006.

Digital Library

[12]

Gerard J. Holzmann. UNO: Static source code checking for userdefined properties. In Proceedings of the World Conference on Integrated Design and Process Technology, Pasadena, CA, June 2002.

[13]

V. Benjamin Livshits and Monica S. Lam. Tracking pointers with path and context sensitivity for bug detection in C programs. In ACM SIGSOFT Symposium on the Foundations of Software Engineering, Helsinki, Finland, September 2003.

Digital Library

[14]

Maksim Orlovich and Radu Rugina. Memory leak analysis by contradition. In Proceedings of the International Static Analysis Symposium, Seoul, Korea, August 2006.

Digital Library

[15]

Daniel Le Berre (project leader). SAT4J: A satisfiability library for java. http://www.sat4j.org/, January 2006.

[16]

Thomas Reps, Susan Horowitz, and Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, San Francisco, CA, January 1995.

Digital Library

[17]

Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. Parametric shape analysis via 3-valued logic. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, San Antonio, TX, January 1999.

Digital Library

[18]

Gregor Snelting, Torsten Robschink, and Jens Krinke. Efficient path conditions in dependence graphs for software safety analysis. ACM Transactions on Software Engineering and Methodology, 15(4):410--457, October 2006.

Digital Library

[19]

Bjarne Steensgaard. Points-to analysis in almost linear time. In Proceedings of the Annual ACM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, January 1996.

Digital Library

[20]

Peng Tu and David Padua. Efficient building and placing of gating functions. In Proceedings of the ACM Conference on Program Language Design and Implementation, La Jolla, CA, June 1995.

Digital Library

[21]

J. Uniejewski. SPEC Benchmark Suite: Designed for today's advanced systems. SPEC Newsletter Volume 1, Issue 1, SPEC, Fall 1989.

[22]

Yichen Xie and Alex Aiken. Context- and path-sensitive memory leak detection. In ACM SIGSOFT Symposium on the Foundations of Software Engineering, Lisbon, Portugal, September 2005.

Digital Library

[23]

Junfeng Yang, Paul Twohey, Dawson Engler, and Madanlal Musuvathi. Using model checking to find serious file system errors. In Proceedings of the Symposium on Operating System Design and Implementation, San Francisco, CA, December 2004.

Digital Library

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Xu RPeng HYang KMao X(2024)Exploring Scalability of Value-Flow Graph ConstructionProceedings of the 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing10.1145/3690931.3690951(112-117)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3690931.3690951
Wen CCai YZhang BSu JXu ZLiu DQin SMing ZCong T(2024)Automatically Inspecting Thousands of Static Bug Warnings with Large Language Model: How Far Are We?ACM Transactions on Knowledge Discovery from Data10.1145/365371818:7(1-34)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3653718
Show More Cited By

Index Terms

Practical memory leak detection using guarded value-flow analysis

Recommendations

Static memory leak detection using full-sparse value-flow analysis
ISSTA 2012: Proceedings of the 2012 International Symposium on Software Testing and Analysis

We introduce a static detector, Saber, for detecting memory leaks in C programs. Leveraging recent advances on sparse pointer analysis, Saber is the first to use a full-sparse value-flow analysis for leak detection. Saber tracks the flow of values from ...
Context- and path-sensitive memory leak detection
ESEC/FSE-13: Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering

We present a context- and path-sensitive algorithm for detecting memory leaks in programs with explicit memory management. Our leak detection algorithm is based on an underlying escape analysis: any allocated location in a procedure P that is not ...
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 Conferences

PLDI '07: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2007

508 pages

ISBN:9781595936332

DOI:10.1145/1250734

General Chair:
Jeanne Ferrante
University of California, San Diego, USA
,
Program Chair:
Kathryn S. McKinley
University of Texas at Austin, USA

ACM SIGPLAN Notices Volume 42, Issue 6
Proceedings of the 2007 PLDI conference
June 2007
491 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1273442
Issue’s Table of Contents

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI '07

Sponsor:

PLDI '07: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 10 - 13, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
1,299
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)11

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li TBai JSui YHu S(2024)SPATA: Effective OS Bug Detection with Summary-Based, Alias-Aware, and Path-Sensitive Typestate AnalysisACM Transactions on Computer Systems10.1145/369525042:3-4(1-40)Online publication date: 6-Sep-2024
https://dl.acm.org/doi/10.1145/3695250
Xu RPeng HYang KMao X(2024)Exploring Scalability of Value-Flow Graph ConstructionProceedings of the 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing10.1145/3690931.3690951(112-117)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3690931.3690951
Wen CCai YZhang BSu JXu ZLiu DQin SMing ZCong T(2024)Automatically Inspecting Thousands of Static Bug Warnings with Large Language Model: How Far Are We?ACM Transactions on Knowledge Discovery from Data10.1145/365371818:7(1-34)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3653718
Tang WDong DLi SWang CYao PZhou JZhang C(2024) Octopus: Scaling Value-Flow Analysis via Parallel Collection of Realizable Path ConditionsACM Transactions on Software Engineering and Methodology10.1145/363274333:3(1-33)Online publication date: 24-Jan-2024
https://dl.acm.org/doi/10.1145/3632743
Cheng XWang JSui YRoychoudhury APaiva AAbreu RStorey M(2024)Precise Sparse Abstract Execution via Cross-Domain InteractionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639220(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639220
Wu RHe YHuang JWang CTang WShi QXiao XZhang CRoychoudhury APaiva AAbreu RStorey M(2024)LibAlchemy: A Two-Layer Persistent Summary Design for Taming Third-Party Libraries in Static Bug-Finding SystemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639132(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639132
Sun YWang CFan GShi QZhang X(2024)Fast and Precise Static Null Exception Analysis With Synergistic PreprocessingIEEE Transactions on Software Engineering10.1109/TSE.2024.346655150:11(3022-3036)Online publication date: Nov-2024
https://doi.org/10.1109/TSE.2024.3466551
Cui MXu HTian HZhou Y(2024)rCanary: Detecting Memory Leaks Across Semi-Automated Memory Management Boundary in RustIEEE Transactions on Software Engineering10.1109/TSE.2024.344362450:9(2472-2484)Online publication date: 13-Aug-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3443624
Liu ZYang ZLiao Q(2024)Exploration On Prompting LLM With Code-Specific Information For Vulnerability Detection2024 IEEE International Conference on Software Services Engineering (SSE)10.1109/SSE62657.2024.00049(273-281)Online publication date: 7-Jul-2024
https://doi.org/10.1109/SSE62657.2024.00049
Xu DChen L(2024)A Dynamic Memory Leak Detection Method for Linux Based on eBPF Uprobe and LKM2024 4th International Conference on Computer Systems (ICCS)10.1109/ICCS62594.2024.10795839(192-197)Online publication date: 20-Sep-2024
https://doi.org/10.1109/ICCS62594.2024.10795839
Show More Cited By

View Options

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 Table of Contents