CPR:PLDI07

Summary

Practical Memory Leak Detection using Guarded Value-Flow Analysis . Sigmund Cherem, Lonnie Princehouse, and Radu Rugina. In Proceedings of the ACM Conference on Program Language Design and Implementation (PLDI 2007), San Diego, CA, June 2007.
(PDF) (Slides)

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 flow graph. 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.

Bibtex entry

@INPROCEEDINGS { CPR:PLDI07,
    AUTHOR = { Sigmund Cherem and Lonnie Princehouse and Radu Rugina },
    TITLE = { Practical Memory Leak Detection using Guarded Value-Flow Analysis },
    BOOKTITLE = { Proceedings of the ACM Conference on Program Language Design and Implementation (PLDI 2007) },
    ADDRESS = { San Diego, CA },
    MONTH = { June },
    YEAR = { 2007 },
    URL = { http://www.cs.cornell.edu/w8/~siggi/getfile.php?pldi07.pdf },
    SLIDES = { http://www.cs.cornell.edu/w8/~siggi/getfile.php?pldi07.ppt },
    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 flow graph. 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. },
}