MSc Computer Science Dissertation
[Pages:110]University of Oxford
Computing Laboratory
MSc Computer Science Dissertation
Automatic Generation of Control Flow Hijacking Exploits for Software Vulnerabilities
Author: Sean Heelan
Supervisor: Dr. Daniel Kroening
September 3, 2009
Contents
List of Figures
v
List of Tables
vii
List of Code Listings
ix
Acknowledgements
xi
Abstract
1
1 Introduction
3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Contributions of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Problem Definition
7
2.1 Operating System and Architecture Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 CPU Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Operating system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Run-time protection mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Address Space Layout Randomisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Non-Executable Memory Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.3 Stack Hardening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.4 Heap Hardening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.5 Protection Mechanisms Considered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Computational Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Security Vulnerabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.1 When is a Bug a Security Vulnerability? . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4.2 Definition of an Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Direct Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.1 Manually Building Direct Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5.2 Components Required to Generate a Direct Exploit . . . . . . . . . . . . . . . . . . . 17
2.6 Indirect Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6.1 Manually Building Indirect Exploits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.2 Components Required to Generate an Indirect Exploit . . . . . . . . . . . . . . . . . . 20
2.7 The Problem we Aim to Solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
i
3 Algorithms for Automatic Exploit Generation
21
3.1 Stage 1: Instrumentation and run-time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.1 Dynamic Binary Instrumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Taint Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3 Building the Path Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Stage 2: Building the Exploit Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 : An Exploit Generation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2 Processing Taint Analysis Information to Find Suitable Shellcode Buffers . . . . . . . 37
3.2.3 Gaining Control of the Programs Execution . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4 Building the Exploit Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Stage 3: Solving the Exploit Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Quantifier-free, Finite-precision, Bit-vector Arithmetic . . . . . . . . . . . . . . . . . . 41
3.3.2 Decision Procedures for Bit-vector Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 System Implementation
45
4.1 Binary Instrumentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1 Hooking System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.2 Hooking Thread Creation and Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.3 Hooking Instructions for Taint Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.4 Hooking Instructions to Detect Potential Vulnerabilities . . . . . . . . . . . . . . . . . 48
4.1.5 Hooking Instructions to Gather Conditional Constraints . . . . . . . . . . . . . . . . . 48
4.2 Run-time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.1 Taint Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.2 Gathering Conditional Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.3 Integrity Checking of Stored Instruction and Function Pointers . . . . . . . . . . . . . 52
4.2.4 Integrity Checking for Write Instructions . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Exploit Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Shellcode and Register Trampolines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.2 Locating Potential Shellcode Buffers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3.3 Controlling the EIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.4 Constructing the Path Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.5 From Formula to Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5 Experimental Results
61
5.1 Testing Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1.1 Shellcode Used . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Stored Instruction Pointer Corruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2.1 Generating an Exploit for a strcpy based stack overflow . . . . . . . . . . . . . . . . 62
5.2.2 Generating an Exploit for the XBox Media Center Application . . . . . . . . . . . . . 64
5.3 Stored Pointer Corruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3.1 Generating an Exploit in the Presence of Arithmetic Modifications . . . . . . . . . . . 66
5.4 Write Operand Corruption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6 Conclusion and Further Work
71
6.1 Automatic Memory-Layout Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.2 Multi-Path Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.3 Identifying Memory Corruption Side-Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.4 Write-N-Bytes-Anywhere Vulnerabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.5 Automatic Shellcode Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.6 Defeating Protection Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.7 Assisted Exploit Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
ii
Bibliography
77
Appendices
85
A Sample Vulnerabilities
85
A.1 Vulnerability 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
A.2 XBMC Vulnerability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
A.3 Function Pointer Vulnerability (No Arithmetic Modification of Input) . . . . . . . . . . . . . 87
A.4 Function Pointer Vulnerability (Arithmetic Modification of Input) . . . . . . . . . . . . . . . 88
A.5 Corrupted Write Vulnerability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
B Sample Exploits
91
B.1 Stack overflow (strcpy) Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
B.2 XBMC Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
B.3 Function Pointer Exploit (No Arithmetic Modification of Input) . . . . . . . . . . . . . . . . . 94
B.4 Function Pointer Exploit (Arithmetic Modification of Input) . . . . . . . . . . . . . . . . . . . 95
B.5 Write Operand Corruption Exploit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
B.6 AXGEN Sample Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
iii
iv
List of Figures
2.1 Stack convention diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Updating M : mov DWORD PTR [eax], 0x00000000 . . . . . . . . . . . . . . . . . . . . . 12 2.3 Updating M : mov DWORD PTR [eax], 0x01020304 . . . . . . . . . . . . . . . . . . . . . 12 2.4 Stack configuration before/after the vulnerable strcpy . . . . . . . . . . . . . . . . . . . . . 15 2.5 Returning to shellcode via a register trampoline . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1 High level algorithm for automatic exploit generation . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 A simple lattice describing taintedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 A taint lattice ordered on arithmetic complexity . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4 A taint lattice ordered on arithmetic and conditional complexity . . . . . . . . . . . . . . . . 31
v
vi
List of Tables
5.1 Run-time Analysis Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Taint Buffer Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.3 Exploit Formula Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.4 Run-time Analysis Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 Taint Buffer Analysis (Top 5 Shellcode Buffers, ordered by size) . . . . . . . . . . . . . . . . . 65 5.6 Exploit Formula Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.7 Run-time Analysis Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.8 Taint Buffer Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.9 Exploit Formula Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.10 Run-time Analysis Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.11 Taint Buffer Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.12 Exploit Formula Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
vii
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- msc computer science dissertation
- master of science in computer science mscs
- master thesis computer science december 2013
- discussion on ph d thesis proposals in computing science
- master thesis in computer science
- bachelor thesis carnegie mellon school of computer science
- thesis topics 5cmcs4900 research topics in computer
- mscs thesis template computer science program
Related searches
- igcse computer science workbooks pdf
- igcse computer science workbook
- igcse computer science workbook answer
- igcse computer science coursebook pdf
- computer science people
- what is computer science like
- computer science revision
- igcse computer science revision notes
- college computer science project ideas
- ideas for computer science project
- computer science projects for students
- computer science final project