DieHard optionally uses replication to increase the probability of successful execution. In this mode, it broadcasts
inputs to a number of replicas of the application process,
each initialized with a different random seed. A voter intercepts and compares outputs across the replicas, and only
actually generates output agreed on by a plurality of the replicas. The independent randomization of each replica’s heap
makes the probabilities of memory errors independent.
Replication thus exponentially decreases the likelihood of
a memory error affecting output, since the probability of an
error corrupting a majority of the replicas is low.
3. 2. exterminator’s heap layout
Figure 2 presents Exterminator’s heap layout, which includes
five fields per object for error isolation and correction: an
object id, allocation and deallocation sites, deallocation
time, which records when the object was freed, and a canary
An object id of n means that the object is the nth object
allocated. Exterminator uses object ids to identify objects
across heaps in multiple program executions. These ids are
needed because object addresses cannot be used to identify
them across differently randomized heaps. The site information fields capture the calling context for allocations and
deallocations: a 32-bit hash of the least significant bytes of
the five most-recent return addresses. The canary bit indicates if the object was filled with canaries (see Section 3. 3).
All of these metadata are initialized when an object is allocated and persist after the object is freed until a new object is
allocated in its place.
The space overhead of this out-of-band metadata plus the
allocation bit is 16 bytes plus 2 bits of space overhead per
object. This amount is comparable to that of typical freelist-based memory managers like the Lea allocator, which
prepend an 8- or 16-byte header (on 32- or 64-bit systems) to
figure 2: an abstract view of exterminator’s heap layout. metadata
below the horizontal line contains information used for error
isolation and correction (see section 3. 2).
10 . . . Allocation bitmap
00… Canary bitset
3. 3. a probabilistic debugging allocator
Exterminator uses a new, probabilistic debugging allocator
that we call DieFast. DieFast uses the same randomized heap
layout as DieHard, but extends its allocation and deallocation algorithms to detect and expose errors. Unlike previous
debugging allocators, DieFast has a number of unusual characteristics tailored for its use in the context of Exterminator.
3. 3. 1. Implicit Fence-Posts
Many existing debugging allocators pad allocated objects with
fence-posts (filled with canary values) on both sides. They can
thus detect out-of-bound writes that are just beyond the start
or end of an object by checking the integrity of these fence-posts. This approach has the disadvantage of increasing space
requirements. Combined with the already-increased space
requirements of a DieHard-based heap, the additional space
overhead of padding may be unacceptably large.
DieFast exploits two facts to obtain the effect of fence-posts without any additional space overhead. First, because
its heap layout is headerless, one fence-post serves double
duty: a fence-post following an object acts as the one preceding the next object. Second, because allocated objects are
separated by (on average) M − 1 freed objects on the heap, we
use freed space to act as fence-posts.
3. 3. 2. Random Canaries
Traditional debugging canaries include values, such as the
hexadecimal value OxDEADBEEF, that are readily distinguished from normal program data in a debugging session.
However, one drawback of a deterministically chosen canary
is that it is always possible for the program to use the canary
pattern as a data value. Because DieFast uses canaries located
in freed space rather than in allocated space, a fixed canary
would lead to a high false-positive rate if that data value were
common in allocated objects.
DieFast instead uses a random 32-bit value set at startup.
Since both the canary value and heap addresses are random
and differ on every execution, any fixed data value (likewise,
any given pointer) has a low probability of colliding with the
canary; this ensures a low false-positive rate (see Theorem
2). To increase the likelihood of detecting an error, DieFast
always sets the last bit of the canary value to 1. Setting this bit
will cause an alignment error if the canary is dereferenced,
but still keeps the probability of an accidental collision with
the canary low (1/231).
3. 3. 3. Probabilistic Fence-Posts
Intuitively, the most effective way to expose a dangling
pointer error is to fill all freed memory with canary values.
For example, dereferencing a canary value as a pointer will
likely trigger a segmentation violation or alignment error.
Unfortunately, reading random values does not necessarily cause programs to fail. For example, in the espresso
benchmark, some objects hold bitsets. Filling a freed bitset
with a random value does not cause the program to terminate but may affect the correctness of the computation.
When reading from a canary-filled dangled object causes
a program to run awry, it can become difficult to isolate the
error. In the worst case, half of the heap could be filled with