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 one 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.
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 de allocates 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 and time consuming. 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 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. 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. As an alternative to debugging memory errors, researchers have proposed a number of systems that either detect or tolerate them. Fail-stop systems are compiler-based approaches that require access to source code, and abort programs when they performs illegal operations like buffer overflows. They rely either on conservative garbage collection or pool allocation to prevent or detect dangling pointer errors. Failure- oblivious systems are also compiler-based, but manufacture read values and drop or cache illegal writes for later reuse. Finally, fault-tolerant systems mask the effect of errors, either by logging and replaying inputs in an environment that pads allocation requests and defers deallocations, or through randomization and optional voting-based replication that reduces the odds that an error will have any effect (e.g., DieHard ).
This paper presents Exterminator, a runtime system that not only tolerates but also detects and corrects heap-based memory errors. 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 then processes one or more heap images to locate the source and size of buffer overflows and dangling pointer errors. This error isolation algorithm has provably low false positive and false negative rates.
Once Exterminator locates a buffer overflow, it determines the allocation site of the overflowed object, and the size of the over flow. For dangling pointer errors, Exterminator determines both the allocation and deletion sites of the dangled object, and computes how prematurely the object was freed. With this information in hand, Exterminator corrects the errors by generating runtime patches. These patches operate in the context of a correcting allocator. The correcting allocator prevents overflows by padding objects, and prevents dangling pointer errors by deferring object deallocations. These actions impose little space overhead because Exterminator’s runtime patches are tailored to the specific allocation and deallocation sites of each error.