PDF 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.

Google Online Preview   Download