A Practical Flow-Sensitive and Context-Sensitive C and C++ Memory Leak Detector

Author(s): David L. Heine, Monica S. Lam
Date: 2003


Language: C/C++
Defect Types: Memory leaks
Uses Annotations: No
Requires Annotations: No
Sound: Yes
Flow-sensitive: Yes
Context-sensitive: Yes

This paper presents a new technique for finding memory leaks and double-free errors in C and C++ programs. The method works by tracking pointers that refer to an object and assigning each object a single owning pointer. This owning pointer must be freed to avoid memory leaks, and any free() calls on non-owning pointers are assumed to result in a double-free error. The method analyzes functions and function calls and creates an ownership signature for each pointer. The authors point out that even though their method does use ownership signature annotations, these annotations are automatically inferred from source code rather than manually specified by the programmer. The method also prioritizes ownership constraints when inferring ownership of objects. For instance, in C++, the inference method assumes that an object owns all of its pointer members, so pointers passed into an instance method relinquish ownership of their referent object. The method also fails to handle certain C constructs such as double pointers and function pointers, but it does report a warning when these features are encountered. The tool the authors implemented also writes the ownership signatures it infers to source code, which helps programmers figure out why certain constructs caused the warnings they did.

The authors tested their method against 3 C programs and 3 C++ programs, all open source, ranging from 23 KLOC to 147 KLOC. The tool's execution time varied widely between 13 and 528 seconds and did not seem to correspond to the KLOC count. The tool reported 1529 errors total for all of the software packages, 1167 of which were escape warnings, which indicate that the tool was unable to determine ownership for a pointer. Of the 362 remaining warnings, 85 were found to be genuine bugs, resulting in a false positive rate of 77%. This high false positive rate can be explained by the method's soundness, which reports all possible errors and does not attempt to reduce the false positive rate. The authors also noted that some of the escape warnings found non-memory-related errors, such as calling the wrong function and having a pointer actually point to the middle of an object rather than the beginning. This method seems quite adept at finding memory-related errors, as long as you avoid the language constructs it can't handle. The many false positives are a major downside, however, and could require more programmer time to sort through than a project allows.