David Brumley

Analysis and Defense of Vulnerabilities in Binary Code Degree Type: Ph.D. in Computer Science
Advisor(s): Dawn Song
Graduated: December 2008

Abstract:

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 restrictions on the input filtering language. We demonstrate our techniques by automatically generating input filters from vulnerable binary programs.

Thesis Committee:
Dawn Song (Chair)
Randal E. Bryant
Peter Lee
Monica Lam (Stanford University)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

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