errors. Because the size of patch files is limited by the number of allocation sites in a program, we expect these files to be
compact and practical to transmit. For example, the size of
the runtime patches that Exterminator generates for injected
errors in espresso was just 130K (17K when compressed
with gzip).
7. ResuLts
Our evaluation answers the following questions: ( 1) What is
the runtime overhead of using Exterminator? ( 2) How effective is Exterminator at finding and correcting memory errors,
both for injected and real faults?
7. 1. exterminator runtime overhead
We evaluate Exterminator’s performance with the
SPECint2000 suite16 running reference workloads, as well as
a suite of allocation-intensive benchmarks. We use the latter
suite of benchmarks both because they are widely used in
memory management studies and because their high alloca-tion-intensity stresses memory management performance.
For all experiments, we fix Exterminator’s heap multiplier
(value of M) at 2.
All results are the average of five runs on a quiescent, dual-processor Linux system with 3GB of RAM, with each 3.06 GHz
Intel Xeon processor (hyperthreading active) equipped with
512K L2 caches. Our observed experimental variance is below
1%.
We focus on the nonreplicated mode (iterative/cumulative),
which we expect to be a key limiting factor for Exterminator’s
performance and the most common usage scenario.
We compare the runtime of Exterminator (DieFast plus the
correcting allocator) to the GNU libc allocator. This allocator
is based on the Lea allocator,
8 which is among the fastest available. 5 Figure 4 shows that, versus this allocator, Exterminator
degrades performance by from 0% (
186.crafty) to
132% (cfrac), with a geometric mean of 25.1%. While
Exterminator’s overhead is substantial for the allocation-
figure 4: Runtime overhead for exterminator across a suite of
benchmarks, normalized to the performance of Gnu libc (Linux)
allocator.
2. 5
Allocation-intensive
Exterminator overhead
GNU libc Exterminator
SPECint2000
Normalized execution time
2
1. 5
1
0.5
1
6
4
g
p
z
.
i
1
7
55
v
p
r
.
1
6
g
7
c
c
.
m
1
8
1
c
f
.
1
8
6
c
a
y
r
f
t
.
1
9
7
p
a
s
e
r
r
.
2
5
2
e
o
n
.
m
3
2
55
p
e
b
k
r
.
l
5
4
2
g
a
p
.
5
2
55
e
v
o
r
t
x
.
5
6
2
2
b
p
z
.
i
w
0
o
t
f
.
l
m
m
G
a
n
e
o
e
c
e
t
r
i
3
0
0
c
a
c
f
r
e
s
p
e
s
s
o
r
n
d
s
a
y
l
i
p
2
c
o
b
o
o
p
r
94 communications of the acm | dEcEmbEr 2008 | voL. 51 | No. 12
intensive suite (geometric mean: 81.2%), for which the cost of
computing allocation and deallocation contexts dominates,
its overhead is significantly less pronounced across the SPEC
benchmarks (geometric mean: 7.2%).
7. 2. memory error correction
7. 2. 1. Injected Faults
To measure Exterminator’s effectiveness at isolating and
correcting bugs, we used the fault injector that accompanies
the DieHard distribution to inject buffer overflows and dangling pointer errors. For each data point, we run the injector
using a random seed until it triggers an error or divergent
output. We next use this seed to deterministically trigger a
single error in Exterminator, which we run in iterative mode.
We then measure the number of iterations required to isolate and generate an appropriate runtime patch. The total
number of images (iterations plus the first run) corresponds
to the number of replicas that would be required when running Exterminator in replicated mode.
Note that Exterminator’s approach to correcting memory
errors does not impose additional execution time overhead
in the presence of patches. However, it can consume additional space, either by padding allocations or by deferring
deallocations.
Buffer overflows: We triggered 10 different buffer overflows
each of three different sizes ( 4, 20, and 36 bytes) by intentionally undersizing objects in the espresso benchmark. In every
case, three images were required to isolate and correct these
errors. Notice that this result is substantially better than the
analytical worst case: for three images, Theorem 2 bounds the
worst-case likelihood of missing an overflow to 42% (Section
4. 1), but we observed a 0% false-negative rate. The most space
overhead we observe is a total increase of 2816 bytes.
Dangling pointer errors : We then triggered 10 dangling pointer
faults in espresso with Exterminator running in iterative and in cumulative modes. Recall that in iterative mode,
Exterminator always fills freed objects with canaries, while it
does so probabilistically when running in cumulative mode
(see Section 3. 3).
In iterative mode, Exterminator succeeds in isolating the
error in only four runs. In another four runs, espresso does
not write through the dangling pointer. Instead, it reads a
canary value through the dangled pointer, treats it as valid data,
and either crashes or aborts. Since no corruption is present in
the heap, Exterminator cannot isolate the source of the error.
In the remaining two runs, writing canaries into the dangled
object triggers a cascade of errors that corrupt large segments
of the heap. In these cases, the corruption destroys the information that Exterminator requires to isolate the error.
However, in cumulative mode, probabilistic canary-filling
enables Exterminator to isolate all injected errors, including the read-only dangling pointer errors. For runs where no
large-scale heap corruption occurs, Exterminator requires
between 22 and 30 executions to isolate and correct the
errors. In each case, 15 failures must be observed before the
erroneous site pair crosses the likelihood threshold. Because
objects are overwritten randomly, the number of runs
required to yield 15 failures varies. Where writing canaries
corrupts a large fraction of the heap, Exterminator requires