The document discusses the process of reverse engineering an unknown binary program by analyzing its machine code instructions. Key steps included:
1) Identifying the RET instruction and using it to find the CALL instruction format and determine the processor uses little-endian 16-bit words.
2) Finding unconditional JMP and relative JMP instruction formats.
3) Identifying common arithmetic and logic instructions like AND, CMP, load, and store by searching for patterns around conditional jump instructions.
4) Gradually decoding the instruction set based on analyses of common patterns and the relationships between different instructions.
The document discusses the process of reverse engineering an unknown binary program by analyzing its machine code instructions. Key steps included:
1) Identifying the RET instruction and using it to find the CALL instruction format and determine the processor uses little-endian 16-bit words.
2) Finding unconditional JMP and relative JMP instruction formats.
3) Identifying common arithmetic and logic instructions like AND, CMP, load, and store by searching for patterns around conditional jump instructions.
4) Gradually decoding the instruction set based on analyses of common patterns and the relationships between different instructions.
The document discusses the process of reverse engineering an unknown binary program by analyzing its machine code instructions. Key steps included:
1) Identifying the RET instruction and using it to find the CALL instruction format and determine the processor uses little-endian 16-bit words.
2) Finding unconditional JMP and relative JMP instruction formats.
3) Identifying common arithmetic and logic instructions like AND, CMP, load, and store by searching for patterns around conditional jump instructions.
4) Gradually decoding the instruction set based on analyses of common patterns and the relationships between different instructions.
The document discusses the process of reverse engineering an unknown binary program by analyzing its machine code instructions. Key steps included:
1) Identifying the RET instruction and using it to find the CALL instruction format and determine the processor uses little-endian 16-bit words.
2) Finding unconditional JMP and relative JMP instruction formats.
3) Identifying common arithmetic and logic instructions like AND, CMP, load, and store by searching for patterns around conditional jump instructions.
4) Gradually decoding the instruction set based on analyses of common patterns and the relationships between different instructions.
• Call graph • Flow-chart • C code Approaches to the analysis
• First thought: to search the code and
data for clues about processor type • To try different disassemblers and check if the disassembled listing looks like a program – IDA Pro supports above 100 “popular” processors (no luck) – Download and try disassemblers for other processors (no luck) Approaches to the analysis
• Fallback: to try to go as far as possible
in binary analysis collecting information about processor • Initial information: – Rough separation of code and data (based on pieces of documentation and “look” of data) – Enough code for statistics to be meaningful (some 30 KiB ) Search space
• Architecture search space:
– Word byte order: LE, BE – Instruction encoding: byte stream/WORD stream/DWORD stream… – Code/data address space: uniform (von Neumann), separate (Harvard) – Code addressing: byte, WORD, … – Register based, stack based
[WORD – 2 bytes, DWORD – 4 bytes]
RET instruction
• Possible instruction encoding: fixed-
width WORD • Expected “Return from subroutine” (RET) instruction properties: – RET instruction has a single fixed opcode and no arguments – RET instruction opcode is statistically among the most frequent 16-bit values in code WORD values frequencies • 20 most frequent 16-bit values: • Reference: most frequent instructions of 0b01 854 5.1 Java bytecode (in the standard libs of jre6) 0800 473 2.8 ALOAD 878565 18 8c0d 432 2.6 DUP 382278 7.9 2b00 401 2.4 INVOKEVIRTUAL 328763 6.8 4e1c 365 2.2 LDC 231162 4.8 0801 277 1.6 GETFIELD 230158 4.8 890f 261 1.6 ILOAD 214427 4.4 8f09 217 1.3 SIPUSH 207427 4.3 0f00 196 1.2 AASTORE 168088 3.5 0b00 195 1.1 INVOKESPECIAL 140387 2.9 0b8f 162 0.97 ICONST_0 132669 2.7 4a01 163 0.97 ASTORE 128835 2.7 0b36 155 0.92 BIPUSH 126262 2.6 0802 149 0.88 ICONST_1 107881 2.2 3ddc 145 0.86 SASTORE 96677 2.0 0b80 132 0.79 PUTFIELD 87405 1.8 990f 131 0.78 NEW 84285 1.7 8afa 125 0.75 GOTO 80815 1.7 1aff 119 0.72 RETURN 70388 1.5 0900 117 0.7 ISTORE 70064 1.4 ARETURN 68054 1.4 All returns: 176860 3.7 Possible code structure
sub1: … CALL subn # absolute address … RET sub2: … # follows RET RET subn: … # follows RET RET CALL heuristics
• Assumption 1: there exists a CALL
instruction taking the absolute address of a subroutine • Assumption 2: a considerable number of subroutines start immediately after RET instruction CALL search • Search space: for each candidate for RET, try all possible CALL candidates with addresses as 16-bit bitmask in 32-bit words, LE/BE, 16-bit/byte addressing • Example: – 4 bytes: 12 34 56 78 – Address bitmask: 00 00 ff ff (4057 different) – Opcode: 12 34 XX XX – Address: 56 78 • LE: 7856 (byte addr), F0AC (WORD addr) • BE: 5678 (byte addr) , ACF0 (WORD addr) CALL search results
• Only one match!
Trying 8c0d as RET After-ret-addr-set-size: 430 Matching call opcodes for 1, ff00ff00, 1: 000b003d: total: 1275, hits: 843 (66%), misses: 432 (33%), coverage: 76%
• 430 – number of positions after RET
candidate • 1275 – total DWORDs with mask 00ff00ff • 843 – calls to addresses right after RET • 432 – calls to somewhere else • 76% positions after RET are covered RET search results
• RET: 8c0d (WORD LE)
• Absolute call to HHLL: 0bHH 3dLL (2 WORD LE) • Confirmation: code areas end with RET: 0000de30 3d88 8c0d 3901 0b24 3daf 2b00 a942 2b00 0000de40 b961 8c0d ???? ???? ???? ???? ???? ???? JMP search heuristics
• Assumption 1: absolute unconditional
JMP has structure similar to call: XXHH YYLL • Assumption 2: there must be no JMP’s to outside of code • Assumption 3: there may be JMP’s to addresses following RETs • Assumption 4: absolute JMPs are not rare JMP search results
– Similarity to CALL encoding – Some code blocks end with this instruction Rel. JMP search heuristics • Set of target addresses: addresses after RET and JMP and first addresses of code segments • Assumption 1: offset occupies one byte • Assumption 2: offset is added to the address of the next instruction • Assumption 3: code is WORD-addressed • Assumption 4: relative jumps rarely cross RET instructions • Assumption 5: no relative jumps to outside of code • Search produces 32 candidates Rel. JMP search first results
• Instructions identified: – CALL – RET – JMP – Conditional JMPs • High-byte extenstion prefix is identified • Control-flow graph can be built and the general structure can be identified Cond. arithmetics heuristics
• Assumption 1: there are instructions
like AND and CMP with immediate arguments preceding conditional jumps • Assumption 2: the opcodes are XXLL or 0bHH XXLL (byte or WORD values) • Build the set of opcodes and the corresponding values Cond. arithm. search results
• Opcodes 3c, 7c: JEQ, JNE • Opcode 1a: AND with immediate argument • Opcode 78: CMP with immediate argument – Opcode 78 always occurs just before conditional jumps 3c and 7c • Opcode f8: also always occurs just before conditional jumps Load-store pattern • Patterns: 0bHH 3fLL 890f 4a01 8f09 0bHH 3fLL 990f 4a01 8f19
Assumption 1: memory load, +1 (or -1), memory
store Assumption 2: registers 0 and 1 are used 4a01 is never used before condjumps -> ADD MOV DP0, HHLL MOV R0, @DP0 ADD ACC, 1 MOV @DP0, R0 Memory clear pattern
Different 16-bit values: 2085, known: 1618 (77%) Top values 0b01 PREFIX 0800 MOV AP, 0 # change the current accumulator 8c0d RET 2b00 PREFIX 4e1c ? 0801 MOV AP, 1 # change the current accumulator 890f MOV R0, @DPO # load from data memory 8f09 MOV @DP0, R0 # store to data memory 0f00 MOV @DP0, 0 # store 0 to data memory 0b00 PREFIX 0b8f PREFIX 4a01 ADD ACC, 1 0b36 PREFIX 0802 MOV AP, 1 3ddc CALL ... 0b80 PREFIX 990f MOV R1, @DP0 8afa ? 1aff AND ACC, ff 0900 MOV R0, 0 Lessons learned
• It is possible to discover – Subroutine structure – Unconditional and conditional jumps – Some arithmetic instructions – Rough register structure • Only by binary analysis of the code without virtual machine (processor) data sheets Limitations
• No obfuscation • Most subroutines follow each other Tool support annotations
• Opcode specifications • Specification of code and data areas • Entry points • Symbolic cell names • Subroutine range and description • Inline and outline specifications SmartDec decompiler
• Demo version is free available at
decompilation.info • Current state: – Alpha-version – Supports limited set of x86/x64 assembly instructions – Supports objdump/dumpbin disassembly backbends – Initial support for C++ exceptions and class hierarchy recovery Thank you for your attention
