18 failures and 34 total runs. In some of the runs, execution
continues long enough for the allocator to reuse the culprit
object, preventing Exterminator from observing that it was
overwritten.
The space overhead of the derived runtime patches ranges
from 32 to 1024 bytes (one 256-byte object is deferred for four
deallocations). This amount constitutes less than 1% of the
maximum memory consumed by the application.
7. 2. 2. Real Faults
We also tested Exterminator with actual bugs in two applications: the Squid Web cache server and the Mozilla Web
browser.
Squid Web cache: Version 2.3s5 of Squid has a buffer overflow;
certain inputs cause Squid to crash with either the GNU libc
allocator or the Boehm–Demers–Weiser collector.
We run Squid three times under Exterminator in iterative mode with an input that triggers a buffer overflow.
Exterminator continues executing correctly in each run, but
the overflow corrupts a canary. Exterminator’s error isolation
algorithm identifies a single allocation site as the culprit and
generates a pad of exactly 6 bytes, fixing the error.
Mozilla Web browser: We also tested Exterminator’s cumulative mode on a known heap overflow in Mozilla 1. 7.3/Firefox
1.0.6 and earlier. This overflow (bug 307259) occurs because
of an error in Mozilla’s processing of Unicode characters in
domain names. Not only is Mozilla multithreaded, leading
to nondeterministic allocation behavior, but even slight differences in moving the mouse cause allocation sequences
to diverge. Thus, neither replicated nor iterative modes can
identify equivalent objects across multiple runs.
We perform two case studies that represent plausible scenarios for using Exterminator’s cumulative mode. In the first
study, the user starts Mozilla and immediately loads a page
that triggers the error. This scenario corresponds to a testing
environment where a proof-of-concept input is available. In
the second study, the user first navigates through a selection
of pages (different on each run), and then visits the error-trig-gering page. This scenario approximates deployed use where
the error is triggered in the wild.
In both cases, Exterminator correctly identifies the overflow
with no false positives. In the first case, Exterminator requires
23 runs to isolate the error. In the second, it requires 34 runs.
We believe that this scenario requires more runs because the
site that produces the overflowed object allocates more correct
objects, making it harder to identify it as erroneous.
8. concLusion
This paper presents Exterminator, a system that automatically
corrects heap-based memory errors in C and C++ programs
with high probability. Exterminator operates entirely at the
runtime level on unaltered binaries, and consists of three key
components: ( 1) DieFast, a probabilistic debugging allocator,
( 2) a probabilistic error isolation algorithm, and ( 3) a correcting memory allocator. Exterminator’s probabilistic error isolation isolates the source and extent of memory errors with
provably low false-positive and false-negative rates. Its correcting memory allocator incorporates runtime patches that the
error isolation algorithm generates to correct memory errors.
Exterminator not only is suitable for use during testing, but
also can automatically correct deployed programs.
acknowledgments
We thank Sam Guyer, Mike Hicks, Erik Learned-Miller,
Sarah Osentoski, Martin Rinard, and Guy Steele for their
valuable feedback. This material is based upon work supported by Intel, Microsoft Research, and the National
Science Foundation under CAREER Award CNS-0347339
and CNS-0615211. Any opinions, findings, and conclusions
or recommendations expressed in this material are those of
the author(s) and do not necessarily reflect the views of the
National Science Foundation.
References
1. austin, T.m., breach, s.E., and sohi, g.s.
Efficient detection of all pointer and
array access errors. in Proceedings of
the 1994 ACM SIGPLAN Conference
on Programming Language Design and
Implementation, acm Press, june
1994, 290–301.
2. avots, d., dalton, m., Livshits, v.b.,
and Lam, m.s. improving software
security with a c pointer analysis.
in Proceedings of the 27th International
Conference on Software Engineering,
acm Press, may 2005, 332–341.
3. berger, E.d. and zorn, b.g. diehard:
Probabilistic memory safety for unsafe
languages. in Proceedings of the
2006 ACM SIGPLAN Conference
on Programming Language Design
and Implementation, acm Press,
june 2006, 158–168.
4. berger, E.d. and zorn, b.g. Efficient
probabilistic memory safety.
Technical report umcs Tr-2007-17,
department of computer science,
university of massachusetts amherst,
mar. 2007.
5. berger, E.d. zorn, b.g., and mckinley,
k.s. composing high-performance
memory allocators. in Proceedings
of the 2001 ACM SIGPLAN
Conference on Programming
Language Design and Implementation,
acm Press, june 2001, 114–124.
6. dhurjati, d., kowshik, s., and adve, v.
safEcode: Enforcing alias analysis
for weakly typed languages. in
Proceedings of the 2006 ACM
SIGPLAN Conference on Programming
Language Design and Implementation,
acm Press, june 2006, 144–157.
7. hastings, r. and joyce, b. Purify:
fast detection of memory leaks and
access errors. in Proceedings of the
Winter 1992 USENIX Conference,
usENiX, jan. 1992, 125–138.
8. Lea, d. a memory allocator. http://
gee.cs.oswego.edu/dl/html/malloc.
html, 1997.
9. Necula, g.c., mcPeak, s., and Weimer,
W. ccured: Type-safe retrofitting
of legacy code. in Proceedings of
the 29th ACM SIGPLAN-SIGACT
Symposium on Principles of
Programming Languages, acm Press,
jan. 2002, 128–139.
Gene Novark ( gnovark@cs.umass.
edu) department of computer science,
university of massachusetts, amherst, ma.
Emery D. Berger ( emery@cs.umass.
edu) department of computer science,
university of massachusetts, amherst, ma.
© acm 0001-0782/08/1200 $5.00
10. Nethercote, N. and seward,
j. valgrind: a framework for
heavyweight dynamic binary
instrumentation. in Proceedings of
2007 ACM SIGPLAN Conference on
Programming Language Design and
Implementation, acm Press, june
2007, 89–100.
11. Novark, g., berger, E.d., and zorn,
b.g. Exterminator: automatically
correcting memory errors with high
probability. in Proceedings of the
2007 ACM SIGPLAN Conference on
Programming Language Design and
Implementation, acm Press, june
2007, 1–11.
12. Qin, f., Tucek, j., sundaresan, j.,
and zhou, y. rx: Treating bugs as
allergies—a safe method to survive
software failures. in Proceedings
of the Twentieth Symposium on
Operating Systems Principles, vol. XX
of Operating Systems Review, acm
Press, oct. 2005, 235–248.
13. rinard, m., cadar, c., dumitran, d.,
roy, d.m., and Leu, T. a dynamic
technique for eliminating buffer
overflow vulnerabilities (and
other memory errors). in Proceedings
of the 20th Annual Computer Security
Applications Conference, iEEE
computer society, dec. 2004, 82–90.
14. rinard, m., cadar, c., dumitran, d.,
roy, d.m., Leu, T., and beebee, W.s.
jr. Enhancing server availability and
security through failure-oblivious
computing. in Sixth Symposium
on Operating Systems Design and
Implementation, usENiX, dec. 2004,
303–316.
15. röjemo, N. and runciman, c. Lag,
drag, void, and use: heap profiling and
space-efficient compilation revisited.
in Proceedings of First International
Conference on Functional
Programming, acm Press, may 1996,
34–41.
16. standard Performance Evaluation
corporation. sPEc2000. http://www.
spec.org.
17. symantec. internet security threat
report. http://www.symantec.com/
enterprise/threatreport/index.jsp,
sept. 2006.
Benjamin G. Zorn ( zorn@microsoft.com)
microsoft research, redmond, Wa.
