Return Oriented Programming for the ARM Architecture

[Nytro]

Return Oriented Programming for the ARM

Architecture

Tim Kornau

December 22, 2009

Contents
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. Definition of objective 7
2.1. Protection mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1. Stack cookies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.2. Address space layout randomisation . . . . . . . . . . . . . . . . . . . . . . 7
2.1.3. Code and data separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. The evolution of return-oriented programming . . . . . . . . . . . . . . . . . . . . . 8
2.2.1. The evolution time line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1.1. Buffer overflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1.2. Return-into-library technique . . . . . . . . . . . . . . . . . . . . . 9
2.2.1.3. Borrowed code chunks technique . . . . . . . . . . . . . . . . . . 9
2.2.1.4. Return-oriented Programming on x86 . . . . . . . . . . . . . . . . 9
2.2.1.5. Return-oriented programming on SPARC . . . . . . . . . . . . . . 10
2.2.1.6. DEPlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1.7. Return-oriented programming on Harvard-type architectures . . . 11
2.3. Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1. Problem approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3. Technical details 13
3.1. architecture and operating system details . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1. The ARM architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1.1. History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1.2. Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.1.3. Instruction set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.1.4. ARM and THUMB . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.1.5. Endianness of memory . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1.6. Stack modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1.7. Subroutine calling convention . . . . . . . . . . . . . . . . . . . . . 18
3.1.2. Operating system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2.1. Operating system overview . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2.2. Memory architecture . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.2.3. XIP DLLs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2.4. DLL loading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2.5. Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2.6. The stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2.7. ARM prologue and epilogue . . . . . . . . . . . . . . . . . . . . . 22
3.1.2.8. Function calling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2.9. System calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.2.10. Cache synchronisation and buffers . . . . . . . . . . . . . . . . . . 25
viii Contents
3.1.2.11. Dumping ROM and XIP . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.2.12. Debugging Windows Mobile . . . . . . . . . . . . . . . . . . . . . 27
3.2. The REIL meta-language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1. A brief description of REIL cornerstones . . . . . . . . . . . . . . . . . . . . 30
3.2.2. REIL architecture and instruction set . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2.1. The REIL VM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2.2. REIL instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.3. Limitations of REIL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3. Return-Oriented Programming on ARM . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1. A note on Turing-completeness . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2. Finding ARM Instruction Sequences in libraries . . . . . . . . . . . . . . . . 36
3.3.3. Construction of ARM Gadgets . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.4. Crafting a Return-Oriented Program . . . . . . . . . . . . . . . . . . . . . . 37
3.3.5. Generating a return oriented program with a compiler . . . . . . . . . . . . 37
3.4. ARM gadget catalogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.1. Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4.2. Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3. Memory gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3.1. Gadget: memory to register . . . . . . . . . . . . . . . . . . . . . 40
3.4.3.2. Gadget: memory to memory . . . . . . . . . . . . . . . . . . . . . 41
3.4.3.3. Memory arithmetic operation gadget . . . . . . . . . . . . . . . . . 42
3.4.3.4. Memory bitwise operation gadgets . . . . . . . . . . . . . . . . . . 43
3.4.4. Memory dereference gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.4.1. Gadget: register to memory dereference (pointer read) . . . . . . 44
3.4.4.2. Gadget: memory to memory dereference (pointer read) . . . . . . 45
3.4.4.3. Gadget: memory dereference to memory or register (pointer write) 46
3.4.5. Register gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.5.1. Gadget: Register to register . . . . . . . . . . . . . . . . . . . . . 48
3.4.5.2. Gadget: Register to constant . . . . . . . . . . . . . . . . . . . . . 49
3.4.5.3. Gadget: register to memory . . . . . . . . . . . . . . . . . . . . . 49
3.4.5.4. Register arithmetic gadgets . . . . . . . . . . . . . . . . . . . . . . 50
3.4.5.5. Register bitwise operation gadgets . . . . . . . . . . . . . . . . . . 52
3.4.5.6. Shift gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.6. Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.7. Control Flow gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.7.1. Gadget: branch Always . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.7.2. Gadget: branch conditionally . . . . . . . . . . . . . . . . . . . . . 56
3.4.8. Function call gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.8.1. Gadget: normal function call . . . . . . . . . . . . . . . . . . . . . 57
3.4.8.2. Gadget: leaf function call . . . . . . . . . . . . . . . . . . . . . . . 58
3.4.9. System Call gadget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4. Algorithms for automatic gadget searching 61
4.1. Stage I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.1. Reverse walker algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.1.2. Algorithm: Expression tree extraction . . . . . . . . . . . . . . . . . . . . . 61
4.1.2.1. Instruction handler . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.2.2. Algorithm to update the operand tree map . . . . . . . . . . . . . 67
4.1.2.3. Example for a single native instruction . . . . . . . . . . . . . . . . 67
4.1.3. Path extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2. Stage II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1. Algorithm to merge expression trees with path information . . . . . . . . . . 69
4.2.1.1. Merging example . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1.2. Jump condition determination algorithm . . . . . . . . . . . . . . . 70
Contents ix
4.2.1.3. Traverse and update operand tree map algorithm . . . . . . . . . 70
4.2.2. Algorithm to simplify expression tree . . . . . . . . . . . . . . . . . . . . . . 72
4.3. Stage III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.0.1. Locate gadgets core function . . . . . . . . . . . . . . . . . . . . . 73
4.3.0.2. Gadget locator functions . . . . . . . . . . . . . . . . . . . . . . . 73
4.3.0.3. Gadget complexity calculation . . . . . . . . . . . . . . . . . . . . 74
5. System implementation 75
5.1. Integration into BinNavi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2. Initial data extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3. Extracting information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3.1. Extracting instruction information callback . . . . . . . . . . . . . . . . . . . 76
5.3.2. Extracting path information callback . . . . . . . . . . . . . . . . . . . . . . 77
5.4. Merging of extracted information . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4.1. Updating the expression tree in a path . . . . . . . . . . . . . . . . . . . . . 77
5.4.2. Simplification of expression trees . . . . . . . . . . . . . . . . . . . . . . . . 78
5.5. Using the extracted information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.5.1. Finding suitable sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.5.2. Evaluating suitable sequences . . . . . . . . . . . . . . . . . . . . . . . . . 79
6. Experimental results 81
6.1. Testing environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.2. Library comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.3. Exploit example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.1. Vulnerable service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.2. Shellcode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7. Conclusion and further work 87
7.1. Automatic gadget compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2. Gadget description language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.3. Live system scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.4. Partial function reconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.5. Attack vector broadening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.6. Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
A. Bibliography i
B. List of Figures v

Download:

http://www.handgrep.se/repository/ebooks/Security/Reversing/kornau-tim--diplomarbeit--rop.pdf