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.
3 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 application4 (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).
Object size
4
36
8
inUse
6
Allocation space
12
inUse
2
Bitmap
5
inUse
4
inUse
16
1
1
inUse
1