More on Automatic Patch Based Exploit Generation

Posted by Tom Cross on April 23, 2008 at 4:32 PM EDT.

I thought I'd follow up on Gunter's post with some technical points about this paper. In essence, I think the authors have demonstrated a powerful tool that could be a useful asset to a vulnerability analyst, but their abstract, and the conclusions they draw, assume solutions to difficult problems that remain unsolved in the open, public security research space.

The paper describes a toolset that produces exploits from patches almost instantly, and goes on to discuss the implications of instant exploit generation from patches, raising the specter of worms propagating in the hours while patch distribution is still taking place.

However, the toolset that is actually described in the technical details of the paper does not provide that sort of capability. The tool does not only require a patch diff, but also either an input that reaches the vulnerable code, or an indication by the tool's user of the specific locations where the attacker controlled data that ultimately exercises the vulnerable code is input into the program. From that information the tool produces a set of inputs that would be rejected by the patched version.

There are two points that I'd like to make about this. The first is that working back from a patch diff, it can take time to determine what inputs reach the vulnerable code, depending on the nature of the vulnerability. Starting with just a patch you might not even know what feature of the program is embodied by the code without spending some time studying the context. If you know where the correct outside interfaces are, the static analysis feature of this tool could be tremendously helpful in finding an input set that gets you to the vulnerability, but it depends on the bug. In many cases bugs are close to the surface, and so an experienced analyst wouldn't need an automated tool to determine the path quickly.

The second point is that the set of inputs that are blocked by a patch are not the same as the set of inputs that could be considered an exploit. If the patch is correct (and they aren't always correct) the later should be a subset of the former, but an attacker is looking to induce a specific behavior. Denial of service conditions are usually easy to induce once you have input that reaches the vulnerable code, but remote code execution can be extremely challenging, as anyone who has read Mark Dowd's recent paper can see.

It is my opinion that most of the time between patch distribution and exploit propagation for serious vulnerabilities is taken up by the work involved in figuring out what interfaces relate to the patched code and the non-trivial task of obtaining remote code execution, particularly if operating system security measures are in play. This toolset does not address either of these problems, and therefore, using the publication of this result as a basis for assuming that attackers can instantly produce working remote code execution exploits from distributed patches is not warranted.

However, history has shown numerous examples of fairly rapid exploit propagation after patch disclosure. An assumption that attackers cannot release exploits instantly is also not warranted regardless of this result. For example, an attacker may have independently discovered a vulnerability and previously developed an exploit for it, which he or she might dump in an open forum once patches are released as the vulnerability would be less useful as a secret at that point. Furthermore, to Gunter's point, there have been numerous examples in the past of automated tools that help analysts discover and exploit certain constrained classes of vulnerabilities in specific repeatable contexts.

Furthermore, I don't mean to disparage the work done by these researchers. This tool could be incredibly useful to an analyst, particularly when input is heavily permutated before reaching a vulnerable operation. I am very impressed with the rigor of this analysis method and I think the tool could be applied to a number of other parts of the vulnerability discovery and analysis problem that aren't discussed here.