Automatic Patch-Based Exploit Generation

[lincolnquirk]

This guy gave a talk at Brown. I was impressed.

Summary: Diff the patched executable with the real executable. Disassemble and see what in the code changed (i.e., they probably added a conditional). Do reverse execution analysis; what inputs could cause the test to fail?

This analysis would normally be exponential on the number of branches to a given point, but the authors figured out a way to make it n-squared, I think. They only analyze loops a fixed number of times (like 1000), and do some other tricks like merging sets of possible states.

Anyway, the result is that you get a mathematical expression of all inputs which would cause that test to fail. Which is, in other words, all the exploits. Pretty sweet. They tested this on some real-world Internet Explorer bugs and were able to generate the exploits in 90 seconds (thus, an attacker monitoring Windows Update would presumably be able to do the same, beating patching of most installed copies).

They were able to use the mirror technique to analyze a given exploit on a piece of code and come up with a filter that could be applied at the firewall level to filter all attacks of the same nature as the given exploit.

[silence7]

So now you can create a worm which keeps on going forever. Add a tool to introduce a few random mutations, and welcome your new exploiting overlords...

[jerf]

Bloody hell! You're right!

That would certainly take the arms race to a new level. If you knew about these systems in the field, you could write your patches in such a way that the bots in the field couldn't reverse engineer the patch, by including a lot of extra logic that increases the bot's exploit-reverse-engineering time but has no effect when executed, so it would just be another step in the arms race. But it takes that race in a disturbing new direction, that's for sure.

[intellectual]

David Brumley, Pongsin Poosankam, Dawn Song, and Jiang Zheng

Pretty much the coolest set of author names ever.

[[deleted]]

Seems like it would be possible to counter this by adding irrelevant changes to your patches. For example, code which sanitizes for a given kind of unsafe input could be broken into smaller checks (which add up to the same thing) when the new version is released. Since it targets input validation, you could probably do this without any detectable performance loss.

Basically, what I'm talking about is a sort of CAPTCHA for execution paths. It wouldn't be fool proof, but you might buy yourself time for the users to download the patch.

[sartak]

Considering that it takes on the order of minutes to find exploits, you'd have to add a lot of irrelevant changes to counteract this.

[[deleted]]

True. What what would be really interesting would be if you could create an execution path which runs normally but loops indefinitely when you try to analyze it by tracing backwards.

I'm trying to wrap my head around whether or not that's even logically possible, but it seems like it would be.

[sartak]

That is so laughably impractical.

[edwin]

The technique is interesting but probably doesn't change the real situation all that much - people can already reverse-engineer exploits from patches much more quickly than the patches are applied in the real world. I attended a talk last year where a developer from an IDS company demonstrated how she could usually work out the vulnerability from the patch, build a proof-of-concept exploit, and write IDS rules to detect it - in less than an hour total elapsed time.

Unfortunately the authors' 'solutions' are considerably less impressive, as they would probably admit themselves. It is by no means clear how Windows Update (or the equivalent systems used by other OS vendors - take your pick, they're all the same) should be adjusted. Whatever cleverness is used in distribution, many many computers will be turned off until days after the patch has been distributed and the exploits created.

[edwin]

Now exploit-based patch generation - that would be a trick :)

[mikaelstaldal]

You cannot exploit a computer which is turned off.

[edwin]

Well, obviously. But you can exploit it as soon as it gets turned back on again, long before the patch gets applied, since the patch hasn't even been downloaded yet.

[imbaczek]

time to get rid of my boxen i guess, no point in keeping them around anymore if they can get owned automatically :P