Automatic patch based exploit generation is possible: Techniques and implications

From Practical Software Verification

Jump to: navigation, search

Document: File:Apeg.pdf

Methods used: Weakest preconditions, guarded command language, hybrid dynamic and static analysis

Other tools used: STP for constraint solving

Working implementation: Yes

Open source/public demo: Neither

Contents

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 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 five Microsoft programs based upon patches provided via Windows Update. Although our techniques may not work in all cases, a fundamental tenant 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.

Main points

  • Exploit generation uses weakest preconditions, dynamic, and static analysis
  • A binary diff between the patched and unpatched version of a program is used. New constraints added in the patched version are used to generate an input for the unpatched version that results in a crash
  • Dynamic analysis gives a straight line trace up to an instruction i and static analysis describes all paths from i to n, the vulnerability point.
  • The ability to vary the value of i allows one to select new paths to the vulnerability point by lowering the value of i. When i is moved backwards then more of the trace is generated via static analysis which describes all possible paths. This could be useful in the case where adding the constraints related to the exploit results in an unsatisfiable formula. In this case we would need to consider new paths through the program and this could be done by decreasing the value of i which would result in more of the program being considered by static analysis and thus a selection of new paths.
  • The suggested technique for selecting a value of i is to start off at the vulnerability point and move it back in steps that encompass procedures instead of by instruction or basic block.

Reader comments

  • Seems like they created a working tool that could generate inputs to cause crashes. Quite annoying that no PoC code is released though.

Bibtex 

@inproceedings{brumley08,
	author = {Brumley, David   and Poosankam, Pongsin   and Song, Dawn   and Zheng, Jiang  },
	booktitle = {Security and Privacy, 2008. SP 2008. IEEE Symposium on},
	citeulike-article-id = {2863702},
	doi = {http://dx.doi.org/10.1109/SP.2008.17},
	journal = {Security and Privacy, 2008. SP 2008. IEEE Symposium on},
	keywords = {defects, dynamic\_analysis, static\_analysis, vulnerabilities},
	pages = {143--157},
	posted-at = {2008-11-06 17:24:47},
	priority = {0},
	title = {Automatic Patch-Based Exploit Generation is Possible: Techniques and Implications},
	url = {http://dx.doi.org/10.1109/SP.2008.17},
	year = {2008}
}
Retrieved from "http://www.unprotectedhex.com/psv/index.php/Automatic_patch_based_exploit_generation_is_possible:_Techniques_and_implications"
Personal tools