Automatic Patch-Based Exploit Generation is Possible:
Techniques and Implications
David Brumley, Pongsin Poosankam Dawn Song Jiang Zheng
Carnegie Mellon University UC Berkeley & CMU U. Pittsburgh

The automatic patch-based exploit generation prob-
lem is: given a program P and a patched version of the
program P′, automatically generate an exploit for the
potentially unknown vulnerability present in P but fixed
in P′. In this paper, we propose techniques for auto-
matic patch-based exploit generation, and show that our
techniques can automatically generate exploits for 5 Mi-
crosoft programs based upon patches provided via Win-
dows Update. Although our techniques may not work
in all cases, a fundamental tenet of security is to con-
servatively estimate the capabilities of attackers. Thus,
our results indicate that automatic patch-based exploit
generation should be considered practical. One impor-
tant security implication of our results is that current
patch distribution schemes which stagger patch distri-
bution over long time periods, such as Windows Update,
may allow attackers who receive the patch first to com-
promise the significant fraction of vulnerable hosts who
have not yet received the patch.
1 Introduction
At first glance, releasing a patch that addresses a vulnerability
can only benefit security. We must, however,
consider the entire time line for patch distribution. A
∗This material is based upon work partially supported by the National
Science Foundation under Grants No. 0311808, No. 0433540,
No. 0448452, No. 0627511, and CCF-0424422. Partial support was
also provided by the U.S. Army Research Office under the Cyber-TA
Research Grant No. W911NF-06-1-0316, and under grant DAAD19-
02-1-0389 through CyLab at Carnegie Mellon. The views and conclusions
contained here are those of the authors and should not be
interpreted as necessarily representing the official policies or endorsements,
either expressed or implied, of ARO, NSF, or the U.S. Government
or any of its agencies. This work was also supported in part
by the Korean Ministry of Information and Communication and the
Korean Institute for Information Technology Advancement under program
new patch reveals some information, and having early
access to a patch may confer advantages to an attacker.
From a security standpoint, we should consider a) what
information about a potentially unknown vulnerability is
revealed by a patch, b) how quickly that information can
be derived from the original and patched program, and
c) what advantage that information yields to attackers.
No previous work (such as fuzz testing as discussed in
Section 7) has addressed these questions.
The automatic patch-based exploit generation
(APEG) problem is: given a program P and a patched
version of the program P′, automatically generate
an exploit for the potentially unknown vulnerability
present in P but fixed in P′. Successful APEG would
demonstrate that attackers could use patches to create
exploits. To the best of our knowledge, APEG has not
been previously demonstrated in public literature. Thus,
the question of whether APEG is feasible for real-world
programs was unanswered.
In this paper, we show that automatic patch-based exploit
generation is possible as demonstrated by our experiments
using 5Windows programs that have recently
been patched. We do not claim our techniques work in
all cases or for all vulnerabilities. However, a fundamental
tenet of security is to conservatively estimate the
capabilities of attackers. Under this assumption, APEG
should be considered practical, and those who have received
a patch should be considered armed with an exploit.
One important consequence of our result is that having
access to a patch confers a significant advantage over
those who do not have access to the patch. The security
advantage is important in light of current patch distribution
practices. Current patch distribution practices
stagger patch distribution, usually over hours, days, or
longer. For example, Gkantsidis et al. show that for
Windows Update it takes about 24 hours for 80% of the
unique observed IPs to check for a new patch [18].

15 more pages to read at the URI

-- - Interesting Stuff - Leadership Development in Free Software

So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world - RI Safir 1998 DRM is THEFT - We are the STAKEHOLDERS - RI Safir 2002

"Yeah - I write Free SUE ME"

"The tremendous problem we face is that we are becoming sharecroppers to our own cultural heritage -- we need the ability to participate in our own society."

"> I'm an engineer. I choose the best tool for the job, politics be damned.<
You must be a stupid engineer then, because politcs and technology have been attached at the hip since the 1st dynasty in Ancient Egypt. I guess you missed that one."

© Copyright for the Digital Millennium