Exterminator: Automatically
Correcting Memory Errors with
High Probability

by Gene novark, Emery d. berger, and benjamin G. Zorn

abstract

Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, which can lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down their location in the source code is difficult, even when the full memory state of the program is available. Once the errors are finally found, fixing them remains challenging: even for critical security-sensitive bugs, the average time between initial reports and the issuance of a patch is nearly 1 month.

We present Exterminator, a system that automatically corrects heap-based memory errors without programmer intervention. Exterminator exploits randomization to pinpoint errors with high precision. From this information, Exterminator derives runtime patches that fix these errors both in current and subsequent executions. In addition, Exterminator enables collaborative bug correction by merging patches generated by multiple users. We present analytical and empirical results that demonstrate Exterminator’s effectiveness at detecting and correcting both injected and real faults.

1. intRoDuction

The use of manual memory management and unchecked memory accesses in C and C++ leaves applications written in these languages susceptible to a range of memory errors. These include buffer overruns, where reads or writes go beyond allocated regions, and dangling pointers, when a program deallocates memory while it is still live. Memory errors can cause programs to crash or produce incorrect results. Worse, attackers are frequently able to exploit these memory errors to gain unauthorized access to systems.

Debugging memory errors is notoriously difficult. Reproducing the error requires an input that exposes it. Since inputs are often unavailable from deployed programs, developers must either concoct such an input or find the problem via code inspection. Once a test input is available, software developers typically execute the application with heap debugging tools like Purify⁷ and Valgrind, ¹⁰ which may slow execution by an order of magnitude. When the bug is ultimately discovered, developers must construct and carefully test a patch to ensure that it fixes the bug without introducing any new ones. This process can be costly and time-consuming. For example, according to Symantec, the average time between the discovery of a critical, remotely

exploitable memory error and the release of a patch for enterprise applications is 28 days. ¹⁷

Because memory errors are so difficult to find and fix, researchers have proposed many solutions that fall roughly into two categories: detection, which prevents errors from being exploited and potentially allows them to be debugged more easily; and toleration, where the effects of errors are mitigated. Fail-stop systems are compiler-based approaches that may require access to source code, and abort programs when they perform illegal operations like buffer overflows. ^{1, 2, 6, 9}

Fault-tolerant runtime systems, which attempt to hide the effect of errors, have also been proposed. Rinard’s failure-oblivious systems are also compiler-based, but manufacture read values and drop or cache illegal writes for later reuse. ^{13, 14} The Rx system¹² uses logging and replay, with potential perturbation, to provide fault tolerance. Our previous work, DieHard, ^{3, 4} uses heap over-provisioning, layout randomization, and optional voting-based replication to reduce the likelihood that an error will have any effect (see Section 3. 1 for an overview). DieHard provides probabilistic memory safety, giving the application the illusion of having an infinite heap with a well-defined probability.

contributions: This paper presents exterminator, a runtime system that not only tolerates but also detects, isolates, and corrects two classes of heap-based memory errors with high probability. Exterminator requires neither source code nor programmer intervention, and fixes existing errors without introducing new ones. To our knowledge, this system is the first of its kind.

Exterminator relies on an efficient probabilistic debugging allocator that we call DieFast. DieFast is based on DieHard’s allocator, which ensures that heaps are independently randomized. However, while DieHard can only probabilistically tolerate errors, DieFast probabilistically detects them.

When Exterminator discovers an error, it dumps a heap image that contains the complete state of the heap. Exterminator’s probabilistic error isolation algorithm processes one or more heap images to try to locate the source of the error. This error isolation algorithm has provably low false-positive and false-negative rates. Buffer overflows and dangling pointer errors can be distinguished because they tend to produce distinct patterns of heap corruption.

A previous version of this article appeared in Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, NY, pp. 1–11.