A Quick Survey on Intermediate Representations for Program Analysis

This is mostly a note to myself, but I guess people interested in automating reverse engineering will be interested at some point in IR suitable for low-level abstractions. I consider top-down IR used by optimizing compilers and bottom-up IR used by decompilers and other reversing tools.

Intermediate Representations for Reverse Engineering

REIL. Used in BinNavi, the Reverse Engineering Intermediate Language defines a very simple RISC architecture (17 instructions), with the nice property that each instruction has at most one side-effect. Thomas Dullien and Sebastian Porst recently presented at CanSecWest an abstract interpretation framework for REIL (paper, slides). It is clearly possible to easily write analyses and transformation passes for REIL without getting into the complexity of the whole x86 architecture, given x86 -> REIL and REIL -> x86 translators.

Here are some sample REIL instructions :

1006E4B00: str edi, , edi
1006E4D00: sub esp, 4, esp
1006E4D01: and esp, 4294967295, esp
1006E4D02: stm ebp, , esp

Language Reference

Hex Rays Microcode. Presented at Black Hat USA 2008 by Ilfak Guilfanov (paper, slides), it is an IR used during decompilation. From the paper: “The microcode language is very detailed and precisely represents how each instruction modifies the memory, registers, and processor condition codes. Typically one CPU instruction is converted into 5-15 microinstructions”. According to the REIL paper, REIL and the microcode language are significantly different, for instance the microinstructions can have a variable number of operands and perform multiple side effects.

Sample microcode:

mov esi.4, eoff.4
mov ds.2, seg.2
add eoff.4, #4.4, eoff.4
ldx seg.2, eoff.4, et1.4
mov et1.4, eax.4

I couldn’t find the language reference.

ELIR. Part of the ERESI project, the goal of ELIR is to simplify static analysis by providing a platform independent abstraction. An overview was presented at Ekoparty08 (slides) and some ideas appeared in Phrack 64, but 30s of Googling didn’t get me to the language reference or a code sample, so that’s all I will say about ELIR for the moment.

Pin Inspection API. PIN, Intel’s Dynamic Binary Instrumentation framework provides a very handy instruction inspection API. This is not an IR but provides the same type of information about complex instructions without having to make giant switch statements. For instance, this is the way to log memory writes with PIN given an instruction:

VOID RecordMemWrite(VOID * addr, UINT32 size) {
    fprintf(trace,",%dW%p", size, addr);
}

// this function is called each time an instruction is encountered
VOID Instruction(INS ins, VOID *v) {
    // isn't that a nice API ?
    if (WRITES && INS_IsMemoryWrite(ins)) {
        INS_InsertPredicatedCall(
            ins, IPOINT_BEFORE, (AFUNPTR)RecordMemWrite,
            IARG_MEMORYWRITE_EA,
            IARG_MEMORYWRITE_SIZE,
            IARG_END);
    }
}

API Documentation

Valgrind IR. On my todo list.

FermaT Transformation System. I’ll have to write something about it someday. Oh lucky you, a wikipedia entry and a bunch of papers!

Optimizing Compilers Intermediate Representations

LLVM Bitcode. This language uses low-level RISC-like instructions in SSA form with type information. It is clean and well defined, and is a very suitable target for platform-independent analysis and optimization. It is designed to convey high-level information in lower level operations, so converting machine code to LLVM bitcode probably requires some intensive work.

Here is the hello world example :

; Declare the string constant as a global constant...
@.LC0 = internal constant [13 x i8] c"hello worldA0"          

; External declaration of the puts function
declare i32 @puts(i8 *)                                           

; Definition of main function
define i32 @main() {
        ; Convert [13 x i8]* to i8  *...
        %cast210 = getelementptr [13 x i8]* @.LC0, i64 0, i64 0 ; i8 *

        ; Call puts function to write out the string to stdout...
        call i32 @puts(i8 * %cast210)
        ret i32 0
}

Language reference

Register Transfer Language. One of the IR used in GCC, it is an architecture-neutral assembly language that represents instructions in a LISP-like form (d’oh), like this:

(insn 2 49 3 test.c:3 (set (mem/c/i:SI (plus:DI (reg/f:DI 6 bp)
                (const_int -20 [0xffffffffffffffec])) [0 argc+0 S4 A32])
        (reg:SI 5 di [ argc ])) 47 {*movsi_1} (nil))

It feels a bit old-fashioned and less clean than LLVM bitcode, but this is just a gut feeling. Use gcc -fdump-rtl-all to see what it looks like.

Side note: the idea of dumping RTL to a file, performing transformations on it and giving this back to GCC is quite common, but RMS qualifies it as “not feasible”, even though the creator of RTL says it is not only feasible but quite useful actually.

Advertisements

A Quick Survey on Automatic Unpacking Techniques

This is a non-comprehensive list of papers and tools dealing with automated unpacking. Please let me know if I’ve missed another technique or if I misunderstood any of the techniques below.

Ring0/Ring3 components, using manual unpacking and heuristics

OllyBonE:

OllyBonE (Break on Execution) uses a Windows driver to prevent memory pages from being executed, and an OllyDbg plugin communicating with the driver. As such it is not an automatic unpacker and requires manual tagging of the pages in which the unpacked code is expected to be found.

Technology used: Windows driver to prevent memory page execution, debugger plugin

Handles unknown packers: no.

Drawbacks: requires a priori knowledge of the memory location of the unpacked code, vulnerable to anti-debugging techniques, modification of the integrity of the host operating system due to the driver.

Code Available: yes, http://www.joestewart.org/ollybone/.

Original Site

(Updated) Dream of Every Reverser / Generic Unpacker:

It is a Windows driver used to hook ring 3 memory accesses. It is used in a project called Generic Unpacker by the same author to find the original entrypoint. The tool then tries to find all import references, dumps the file and fixes the imports. It is reported to work against UPX, FSG and AsPack, but not against more complex packers.

Technology used: Windows driver to hook userland memory access

Handles unknown packers: no.

Drawbacks: requires a priori knowledge of the memory location of the unpacked code, modification of the integrity of the host operating system due to the driver.

Code Available: yes, http://deroko.phearless.org/GenericUnpacker.rar.

Original Site

(updated) RL!Depacker

No description for this one, however it looks similar to Dream of Every Reverser / Generic Unpacker.

Code Available: yes,  http://ap0x.jezgra.net/RL!dePacker.rar.

Original Site

(updated) QuickUnpack

Again, no real description, but it looks similar to RL!Depacker and DOER / Generic Unpacker. It is a scriptable engine using a debugging API. It is reported to work against 60+ simple packers.

Code Available: yes, http://www.team-x.ru/guru-exe/?path=Tools/Unpackers/QuickUnpack/

Original Site (in Russian)

Universal PE Unpacker:

This is an IDA Pro plugin, using the IDA Pro Debugger interface. It waits for the packer to call GetProcAddress and then activates single-stepping mode until EIP is in a predefined range (an estimate for the OEP). It only works well against UPX, Morphine, Aspack, FSG and MEW (according to the authors of Renovo).

Technology used: Debugging and heuristics.

Handles unknown packers: no, needs an approximation of the OEP and assumes that the unpacker will call GetProcAddress before calling the original code.

Drawbacks: not fully automatic, very vulnerable to debugger detection, does not necessarily work against all packers or self-modifying code.

Code Available: yes, since IDA Pro 4.9

Original Site

Instruction-level analysis, comparison between written addresses and executed addresses

Renovo:

Built on TEMU (BitBlaze), it uses full system emulation to record memory writes (and mark those memory locations as dirty). Each time a new basic block is executed, if it contains a dirty memory location a hidden layer has been found. Cost: 8 times slower than normal execution. It seems to unpack everything correctly except Armadillon and Obsidium (due to incorrect system emulation ?). It seems to only obtain partial results against Themida with the VM option on.

Technology used: Full system emulation.

Handles unknown packers: yes.

Drawbacks: order of magnitude slowdown, detection of the emulation stage

Code Available: I couldn’t find it.

Original Site, Local Copy

Azure:

Paul Royal’s solution, named after BluePill because it is based on KVM, a Linux-based hypervisor. It uses Intel’s VT extension to trace the target process (at the instruction-level), by setting the trap flag and intercepting the resulting exception. The memory writes are then recorded and compared to the address of the current instruction. According to the paper, it handles every packer correctly (including Armadillo, Obsidium and Themida VM).

Technology used: Hardware assisted virtualization and virtual machine introspection.

Handles unknown packers: yes.

Drawbacks: detection of the hypervisor. Slowdown ?

Code Available: yes, http://blackhat.com/presentations/bh-usa-08/Royal/Royal_Extras.zip.

Original Site, Local Copy

Saffron:

Developed by Danny Quist and Valsmith, a first version uses Intel PIN to dynamically instrument the analyzed code. It actually inserts instructions in the code flow, allowing lightweight fine-grained control (no need for emulation or virtualization), but it modifies the integrity of the packer. A second version modifies the page fault handler of Windows and traps when a written memory page is executed. It has mixed results with Molebox, Themida, Obsidium, and doesn’t handle Armadillo correctly (according to Paul Royal).

Technology used: Dynamic instrumentation, Pagefault handling (with a kernel component in the host operating system).

Handles unknown packers: yes.

Drawbacks: modifies the integrity of the code (with DI) and of the host operating system. It must not work in a virtual machine. The dynamic instrumentation is very slow. The memory monitoring of the pagefault handler is coarse-grained (pages are aligned on a 4k boundary), and therefore some memory access can go unnoticed.

Code Available: dynamic instrumentation available, what about the driver ?

Original Site, Local Copy

(updated) OmniUnpack:

Uses a technique similar to the second version of Saffron: a Windows driver to enforce a W^X policy on memory pages.

Technology used: Pagefault handling  and system call tracing (with a kernel component in the host operating system)

Handles unknown packers: yes.

Drawbacks: modifies the integrity of the host operating system. It must not work in a virtual machine. The memory monitoring of the pagefault handler is coarse-grained, leading to spurious unpacking stages.

Code Available: ?

Original SiteLocal Copy

Pandora’s Bochs:

Developed by Lutz Böhne, it is based on Bochs which is used to monitor memory writes and compare them with branch targets. Interestingly, the assumptions about the program are stated explicitly (which is a GOOD thing) : the unpacking does not involve multiple processes, it does not happen in kernel mode, the unpacked code is reached through a branch instruction (not a fall-through edge), etc… Another interesting point in this approach is that it uses no component in the guest OS (as opposed to Renovo for example), all the information is retrieved from outside the matrix (as with Azure).

Technology used: Full system emulation based on Bochs.

Handles unknown packers: yes.

Drawbacks: As stated in the paper the limitations are speed, compatibility (not all packed samples seemed to run under Bochs), detection of OEP and reconstruction of imports sometimes failed.

Code Available: http://damogran.de/blog/archives/21-To-release,-or-not-to-release-….html

Original Site, Local Copy

Other techniques (comparison with static disassembly or disk image)

Secure and Avanced Unpacking by Sebastien Josse:

The idea developed by Sebastien Josse is to use full system emulation (based on QEMU ?) and to compare the basic blocks that are going to be executed by the virtual CPU with the equivalent address in the file image of the executable. If the memory and the disk version differ, it means that the code has been generated on the fly and therefore a hidden layer has been found. Josse then proposes techniques to rebuild a fully functional executable based on the memory dump. This technique seems to work well (but sometimes requires human intervention) against several packers, including Armadillo, ASProtect, PEtite, UPX, yC…

Technology used:Full system emulation, comparison between memory images and disk images.

Handles unknown packers: yes, manual intervention might be required in some cases.

Drawbacks: slowdown due to the full system emulation, full reconstruction of the unpacked program is not always possible.

Code Available: ?

Original Site

PolyUnpack:

The idea behind PolyUnpack is to address the fundamental nature of unpacking, which is runtime code generation. To identifiy code that has been generated at runtime, PolyUnpack uses a conceptually elegant technique: it first statically analyses the program to build a map of statically accessible code, and then traces the execution of the program. The dynamically intercepted instructions are compared with the static disassembly, if they do not appear in the static disassembly then they have been generated at runtime.

Technology used: comparison between static disassembly and dynamic tracing. The dynamic trace is extracted with single-step debugging APIs.

Handles unknown packers: yes.

Drawbacks: vulnerable to debugger detection. Note that this is a limitation of the implementation, not of the concept.

Code Available: http://polyunpack.cc.gt.atl.ga.us/polyunpack.zip (updated 26/06/2009)

Original Site, Local Copy