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 suite¹⁶ 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, ⁸ which is among the fastest available. ⁵ 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