Obfuscation and Disassembly of Object Files

“Obfuscation of Executable Code to improve Resistance to Static Disassembly” - Linn, Debray

* * * * *

“Static Disassembly of Obfuscated Binaries” - Kruegel, Robertson, Valeur, Vigna

Why Obfuscate?

GOOD:

Protect intellectual property

Prevent software piracy

BAD:

Hide malicious functionality

Fool anti-virus software

What to Obfuscate?

Execution flow

System function calls

Machine instructions

Program structures

Data

Thwarting Linear Sweep Disassembly

Junk insertion - 15%

Branch flipping - 37%

Bcc Addr =>	B!cc L

jmp Addr

L:

Now we can insert junk bytes @ L

Call conversion - 42%

Thwarting Recursive Traversal Disassembly

Branch functions

Given finite map A={a1->b1, ... , an->bn}

Then ai: jmp b1 => a1: call fA

Implementation: lookup table; Better: pass offset b1-(a1+1) as an argument

Even Better: Perfect hashing function + lookup table

Performance degradation – use only on least frequently used code segments.

Call conversion – use branch functions with perfect hashing to determine function address

Opaque predicates

Convert unconditional branches to conditional

jmp Addr => Bcc Addr, where cc is always T or always F

Jump table spoofing – insert artificial jump tables which are unreachable @ run-time

Thwarting Recursive Traversal Disassembly

General Disassembly

Function identification

Importance of determining control flow

Extract targets of calls. Problems:

Calls are not identified

Branching functions

Search for prolog byte sequences

Done for performance

General Disassembly

Intra-procedural control flow graph (CFG)

Directed G(V, E) in which each edge e from u to v represents possible control flow from u to v

V represents a set of basic blocks – each instruction executes before instructions in later positions

Use recursive approach – not sufficient for obfuscated binaries

General Disassembly

Initial Control flow graph

Decode instructions at every byte – due to variable length, misalignment, and overlapping

Identify intra-procedural CTI – target address between the function start & end addresses, or conditional jump

Use special recursive method to determine initial CFG – the real CFG is a subgraph of the initial CFG

General Disassembly

Recursive Algorithm Implementation

Instructions after call or unconditional jump are not valid

Instructions can overlap and eventually merge, then we split the basic block at the point of merging and all edges pointing the the old block are directed to the first sub-block all outgoing edges are linked to the second sub-block

Block conflict resolution

Remove definitely invalid blocks:

If the first instruction of a basic block is valid then the block and all nodes reachable (their address can be statically determined)from the block are also marked valid. Remove conflicts

Erase nodes which lead to conflicting nodes – valid instructions do not overlap. Caused by invalid cond. branches

General Disassembly

Block Conflict resolution (contd.)

Remove likely invalid blocks:

Valid blocks are tightly interconnected in the graph, thus remove blocks from pairs of conflicting nodes by retaining the one with more predecessors/successors

Remove conflicting blocks randomly

Gap Completion

Gap – empty space between blocks in the graph mainly caused by junk bytes; they can also be valid instructions

Algorithm:

Identify all possibly valid sequences:

Last instruction ends in last byte of the gap

General Disassembly

Last instruction is a non intra-procedural CTI – all NIP CTI are included into the initial CFG. If it appears again then it must have been deleted due to conflicts.

Decode the gap instructions linearly until one of the conditions are violated

Calculate sequence score – statistical analysis using tables (built by examining large number of executables)

Heuristics - set the score of an instruction to 0 when:

Operands size mismatch

Certain arithmetic is used with special purpose registers

Unexpected reg to reg moves

Moves of a reg value into mem referenced by the same register

Select the sequence with highest score

Tool-Specific Techniques

Reverse engineer the branch function – tedious and error prone

Branch function simulation

Find the branch function

Input: call instr addr +1

Output: ≠ call instr + 1

Possible due to the static nature of calculation: the table is in the initialized data segment

Invoke the simulator when call is encountered

Results

Questions

Main contributions:

Provide specific information on how to disassemble obfuscated binaries.

Advantages/Disadvantages:

Succeeds in accomplishing the purpose

Not 100% optimal.

Possible improvements:

Implement more features to improve accuracy. Add dynamic disassembly support to their software

2004-11-07T20:26:25