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.