Computer Science Department
School of Computer Science, Carnegie Mellon University


Analysis and Defense of Vulnerabilities
in Binary Code

David Brumley

September 2008

Ph.D. Thesis


Keywords: Vine, binary analysis, patch-based exploit generation, vulnerability filter generation

In this thesis, we develop techniques for vulnerability analysis and defense that only require access to vulnerable programs in binary form. Our approach does not use or require source code. We focus on a binary-centric approach since everyone typically has access to the binary code for the programs they run. Thus, our approach is applicable to a wider audience than previous approaches that require or utilize source code. In addition, the binary itself is often the most faithful encoding of security-relevant details since it is what is actually executed on hardware.

In order to demonstrate the benefits of binary-centric vulnerability analysis and defense, we first develop binary analysis techniques. We have implemented our techniques as part of a binary analysis architecture called Vine. We then demonstrate the utility of our approach, and Vine, in two typical applications of vulnerability analysis and defense.

First, we develop binary analysis techniques for reverse engineering a patched vulnerability. More specifically, our techniques enable an attacker to reverse engineer exploits from software patches that fix program bugs and vulnerabilities. We call this automatic patch-based exploit generation. We demonstrate automatic patch-based exploit generation on real vulnerabilities using Vine. In our experiments, it only takes a few minutes to generate an exploit from the patched program. We argue one consequence of our results is that current delayed patch distribution architectures (e.g., Windows Automatic Update) may hurt security.

Second, we propose methods and techniques for generating input filters based upon vulnerability analysis. An input filter is a recognizer for inputs that exploit a vulnerability. We develop the first automatic techniques for generating input filters with accuracy guarantees even when there may be re- strictions on the input filtering language. We demonstrate our techniques by automatically generating input filters from vulnerable binary programs.

155 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by