Tuesday, June 14, 2011

Automated Independent Gadget Search

Goal
The goal of this research is to be able to use return-oriented programming platform independently across multiple platforms.

Motivation
-CPU Architecture diversity is increasing.
-We want to execute code on machines despite the presence of non-executable memory, but we do not aim for ASLR.

History


Strategy
-Use only already present code
-No single instruction / return like approach
-Use REIL to be platform independent
-Use "free-branch" instructions rather than ret only
-"Find all first, then filter useful ones" approach
-Keep an eye on side-effects and minimize them

Small RISC instruction set:
-17 instructions for arithmetic, control flow and misc functionality
-Instructions are always side-effect free

Interpreter:
-Virtually unlimited memory and temporary registers
-Implemented as a register machine

No support for:
-Exceptions, floating point instructions, 64Bit instructions yet

Algorithms


Algorithms stage I
Collect data from the binary:
1.Extract expression trees from native instructions
-Handlers for each possible REIL instruction
-Most of the handlers are simple transformations
-Memory store and conditional execution need special treatment

2.Extract path information
-Path is extracted in reverse control flow order
-We want to have all possible outcomes for a conditional execution in a single expression tree


Algorithms stage II
Merge the collected data from stage I:
1.Combine the expression trees for single native instructions along a path
1:  0x00000001 ADD R0, R1, R2  
2:  0x00000002 STR R0, R4  
3:  0x00000003 LDMFD SP! {R4,LR}  
4:  0x00000004 BX LR  

2.Determine jump conditions on the path
3.Simplify the result


Algorithms stage III
Goal of the stage III algorithms:
-Search for useful gadgets in the merged data. Use a tree match handler for each operation.
-Select the simplest gadget for each operation. Use a complexity value to determine the gadget which is least complex (side-effects).

Results
-Algorithms for platform independent return-oriented programming are possible
-We are able to find all necessary gadgets for return-oriented programming using our tool
-Searching for gadgets is not only platform but also very compiler dependent
-Minimizing side-effects is possible if the right approach is chosen

Future work
-Abstract gadget description language
-Automatic gadget compiler for all platforms
-Bring more platforms to REIL
-Better understand the implications of different compilers