Communications - December 2008

Once Exterminator locates a buffer overflow, it determines the allocation site of the overflowed object, and the size of the overflow. 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.

After Exterminator completes patch generation, it both stores the patches to correct the bug in subsequent executions, and triggers a patch update in the running program to fix the bug in the current execution. Exterminator’s patches also compose straightforwardly, enabling collaborative bug correction: users running Exterminator can automatically merge their patches, thus systematically and continuously improving application reliability.

Exterminator can operate in three distinct modes: an iterative mode for runs over the same input, a replicated mode that can correct errors on the fly, and a cumulative mode that corrects errors across multiple runs of the same application.

We experimentally demonstrate that, in exchange for modest runtime overhead (around 25%), Exterminator effectively isolates and corrects both injected and real memory errors, including buffer overflows in the Squid Web cache server and the Mozilla Web browser.

2. memoRy eRRoRs

Incorrect programs exhibit a variety of errors related to heap objects, including dangling pointers, where a heap object is freed while it is still live; invalid frees, where a program deallocates an object that was never returned by the allocator; double frees, where a heap object is deallocated multiple times without an intervening allocation; uninitialized reads, where the program, despite using all pointers correctly, reads memory that has never been initialized; and out-of-bound writes, where the memory address to be written is computed by using a valid pointer to an object but an incorrect offset or index, so that the address computed lies outside the object. We use the term buffer overflow to refer to an out-of-bound write whose offset from a base pointer is positive and too large. ( Out-of-bound writes where the offset is negative appear to be rather less common in practice.)

Errors such as double frees and invalid frees, if not properly handled, can result in inconsistent allocator metadata and are a potential security vulnerability. These errors can lead to heap corruption or abrupt program termination. Out-of-bound writes and dangling pointers may result in corruption of either allocator metadata or application objects. Uninitialized reads, because the values read are not specified by the language semantics, can affect application execution in arbitrary ways. Because good allocator design can mitigate the effect of double frees and invalid frees, buffer overruns and dangling pointer errors are currently the most com-

88 communications of the acm | dEcEmbEr 2008 | voL. 51 | No. 12

monly exploited heap errors, and hence the most important to address.

While DieHard probabilistically tolerates dangling pointers and buffer overflows of heap objects, Exterminator both detects and permanently corrects them. Exterminator’s allocator (DieFast) shares DieHard’s immunity from double frees and invalid frees. Exterminator does not currently address uninitialized reads, reads outside the bounds of an object, or out-of-bound writes with negative offsets.

3. soft WaRe aRchitectuRe

Exterminator’s software architecture extends and modi-fies DieHard to enable its error isolating and correcting properties. This section first describes DieHard, and then shows how Exterminator augments its heap layout to track information needed to identify and remedy memory errors. Second, it presents DieFast, a probabilistic debugging allocation algorithm that exposes errors to Exterminator. Finally, it describes Exterminator’s three modes of operation.

3. 1. Diehard overview

The DieHard system includes a bitmap-based, fully randomized memory allocator that provides probabilistic memory safety. ³ The latest version of DieHard, upon which Exterminator is based, adaptively sizes its heap to be M times larger than the maximum needed by the application⁴ (see Figure 1). This version of DieHard allocates memory from increasingly large chunks that we call miniheaps. Each miniheap contains objects of exactly one size. DieHard allocates new miniheaps to ensure that, for each size, the ratio of allocated objects to total objects is never more than 1/M. Each new miniheap is twice as large, and thus holds twice as many objects, as the previous largest miniheap.

Allocation randomly probes a miniheap’s bitmap for the given size class for a 0 bit, indicating a free object available for reclamation, and sets it to 1. This operation takes O( 1) expected time. Freeing a valid object resets the appropriate bit, which is also a constant-time operation. DieHard’s use of randomization across an over-provisioned heap makes it probabilistically likely that buffer overflows will land on free space, and unlikely that a recently freed object will be reused soon.

figure 1: the adaptive (new) Diehard heap layout, used by exterminator. objects in the same size class are allocated randomly from separate miniheaps, which combined hold M times more memory than required (here, M = 2).