Is it possible to take a buggy program along with a patched version of that same program, and then automatically generate an exploit? Some people think it is, and they're out to prove their point.

David Brumley, Pongsin Poosankam, Dawn Song, and Jiang Zheng of Carnegie Mellon University put their theory in writing in a new whitepaper that will appear in the Proceedings of the 2008 IEEE Security and Privacy Symposium.

According to abstract:

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 ?xed 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 ?rst to compromise the signi?cant fraction of vulnerable hosts who have not yet received the patch.

Download a copy in PDF format at David Brumley's home page.