Context- and Path-Sensitive Memory Leak Detection

Author(s): Yichen Xie, Alex Aiken
Date: 2005


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

This paper presents a new method for finding memory leak errors in C programs. This method like many others uses unsound reasoning principles, which means that it may miss some errors in an attempt to keep the false positive rate to a minimum. This method specifically targets errors where programmers allocate a block of memory and then forget to free it before all references to the block go out of scope (for instance, early function termination in the event of an error). The method is implemented in the Saturn static analysis tool, which provides data structures for this algorithm to work with. The method uses Guarded Location Sets to track the memory locations that a pointer could refer to at all points in a program, and polymorphic locations to account for the possibility of multiple pointer types referring to the same location (which is what happens in a pointer typecast, for instance). Since this method also analyzes each procedure independently, the authors have created a parallelized version of their algorithm to distribute the analysis across multiple computers.

The authors validated their method by analyzing 6 open source programs: Samba, OpenSSL, postfix, binutils, and OpenSSH. They also used their method on the Linux kernel, which they treated as a separate test. The 5 programs range between ~40 and ~1,000 KLOC, and the Linux kernel has roughly 5,000 KLOC. The sequential runtimes for the prototype tool range bewteen 30 minutes and 4 hours for the group of 5 programs, but the Linux kernel took about 23 hours. When the authors ran the analyzer distributed over 80 processors, the runtime was cut down to 6 – 15 minutes and 51 minutes for the group of 5 programs and the Linux kernel respectively. The false positive rates were very good, however, and were even better than some sound analysis techniques. The 5 programs had a false positive rate of only 3.62%, and the kernel 33%. The authors conclude that the increased false positive rate in the kernel was due to function pointers and pointer arithmetic, which this method is unable to handle well. The long runtimes suggest that this tool would be better to use before a release, since running it every compile would mean a lot of programmer downtime. This tool is very effective at finding the bugs it targets, though, and would be a good addition to most projects' toolchain.