Automatic Patch-Based Exploit Generation

Brumley, Poosankam, Song & Zheng, 2008. Automatic Patch-Based Exploit Generation is Possible: Techniques and Implications:
The automatic patch-based exploit generation 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'. In this paper, we propose techniques for automatic patch-based exploit generation, and show that our techniques can automatically generate exploits for 5 Microsoft programs based upon patches provided via Windows Update. Although our techniques may not work in all cases, a fundamental tenet of security is to conservatively estimate the capabilities of attackers. Thus, our results indicate that automatic patch-based exploit generation should be considered practical. One important security implication of our results is that current patch distribution schemes which stagger patch distribution over long time periods, such as Windows Update, may allow attackers who receive the patch first to compromise the significant fraction of vulnerable hosts who have not yet received the patch.
The technique is based on flow analysis, to test code that gets changed for boundaries where safety properties fail. The limitations of the technique they have developed automatically generate vulnerabilities for only a small fraction of propagated updates. Nonetheless I find it astonishing that such a simple analysis can provide such a payoff. Via Bruce Schneier.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.


This is going to be a very painful revelation for a whole lot of software vendors.

Given limited and variable bandwidth, the only effective solution is for auto-patching systems to roll out patches in encrypted form, force all online users to shut down the program, and then roll out the decryption keys to users as they (re)start the program or operating system.

Valve's game distribution system, Steam, employs a similar system for streaming encrypted pre-release software, and then sending out the decryption keys on the release date, to enable staggered rollout without pre-release piracy.

Not really; these techniques

Not really; these techniques are very brittle in practice. If software can take the performance hit, the code probably can be obfuscated. [It is valid to argue automatic exploitation software will get better, but judging by the slow moving field of program analysis, I don't think that's realistic.]

investment v. return

It doesn't matter how hard it is from an intuitive perspective. All that matters is the empirical return on investment.


not all exploits are equal

Finding an input that causes an overflow is not the same thing as finding one that grants root access or leaks sensitive information. This technique does the former.

The assumption is that an

The assumption is that an impact analysis of a security patch reveals the security flaw (and, given the general approaches of the group, synthesizes it).

Approaches like these fit well with the general hacking pipeline. Once a basic exploit type is found, previous exploits that can play off of it are incorporated. Fully automated exploit kits based off of patches may not be happening anytime soon (as you said, triggering a buffer overflow does not directly lead to an escalation of rights) but having a concrete crash-inducing input sequence is significant knowledge for a hacker as it can be traced, classified, and then built upon.

Then again, if we stopped using inappropriate languages, many of these simple exploits would go away, and it's hard to synthesize higher level exploits. It would be interesting to characterize flaws found in bug finding literature with respect to how successful they are on problems that are not already solved with higher level languages of varying popularity.

Disclaimer: I am in the same dept. as some of the authors