ARM static analysis engine internals, Part 2: Implementing the disassembly engine
Translated by DeepSeek Flash.
Originally published in Chinese on Kanxue Forum.
I. How decoding works
Once the instructions are described in the DSL, the engine does not parse the DSL at runtime. Instead it pre-generates a static lookup table, and every node in that table is reduced to a (mask, value) pair. Matching at runtime is then nothing more than a bitwise AND followed by a comparison. Decoding never interprets the DSL, and it never does string matching.
{
patterns: 'xxx100xxxxxxxxxxxxxxxxxxxxxxxxxx',
desc: 'C4.1.92 Data Processing – Immediate',
list: [
# ...... omitted
{
patterns: 'xxx100010xxxxxxxxxxxxxxxxxxxxxxx',
desc: 'C4.1.92.3 Add/subtract (immediate)',
funs: {
fshift: {
return (_lrs_eq(c, 22, 1, 0x0) ? 0 : 12);
},
falias_add_mov_boolean: {
// sh == '0' && imm12 == '000000000000' && (Rd == '11111' || Rn == '11111')
return _lrs_eq(c, 22, 1, 0x0) && _lrs_eq(c, 10, 12, 0x0) && (_lrs_eq(c, 0, 5, 0x1f) || _lrs_eq(c, 5, 5, 0x1f));
}
},
list: [
{
param: '31:0,30:0,29:0',
name: 'add',
grammar: 'ADD <Wd|WSP>, <Wn|WSP>, #<imm>{, <shift>}',
ops_desc: [
{ t: :r_w, v: '0:5', wsp: true },
{ t: :r_w, v: '5:5', wsp: true },
{ t: :imm, v: '10:12', shift: { t: :lsl, v: 'f:fshift' } }
],
aliases: [
{
name: 'mov',
cond: 'f:falias_add_mov_boolean',
ops_desc: [
{ t: :r_w, v: '0:5', wsp: true },
{ t: :r_w, v: '5:5', wsp: true }
],
dataflow: { def: [0] }
}
],
dataflow: { use: [1], def: [0] },
semantic: { op: :add }
},
]
}
# ...... omitted
]
}
Take the add instruction from C4.1.92 Data Processing – Immediate once more: at decode time, a mask and value are generated for each node of this tree.
The lookup logic is simply:
(instruction & mask) == value
For C4.1.92 Data Processing – Immediate (xxx100xxxxxxxxxxxxxxxxxxxxxxxxxx):
- mask:
469762048—00011100000000000000000000000000 - value:
268435456—00010000000000000000000000000000
For C4.1.92.3 Add/subtract (immediate) (xxx100010xxxxxxxxxxxxxxxxxxxxxxx):
- mask:
528482304—00011111100000000000000000000000 - value:
285212672—00010001000000000000000000000000
For the ADD <Wd|WSP>, <Wn|WSP>, #<imm>{, <shift>} instruction:
- mask:
4286578688—11111111100000000000000000000000 - value:
285212672—00010001000000000000000000000000
Take an actual add instruction:
11003108 add w8, w8, #12
The pseudocode then looks like this:
// step 1
uint64_t instruction = 0x11003108;
if ((instruction & 469762048) == 268435456) // match C4.1.92 Data Processing – Immediate
if ((instruction & 528482304) == 285212672) // match C4.1.92.3 Add/subtract (immediate)
if ((instruction & 4286578688) == 285212672) // match ADD <Wd|WSP>, <Wn|WSP>, #<imm>{, <shift>}
II. Operand extraction
Take the operands of the add instruction:
ops_desc: [
{ t: :r_w, v: '0:5', wsp: true },
{ t: :r_w, v: '5:5', wsp: true },
{ t: :imm, v: '10:12', shift: { t: :lsl, v: 'f:f1' } }
],
- The first operand starts at bit 0 and is 5 bits wide.
- The second operand starts at bit 5 and is 5 bits wide.
- The third operand starts at bit 10 and is 12 bits wide. It carries a shift, and the shift logic is
f:f1.
Here f:f1 denotes a function — fshift on the parent node. fshift holds a function written as a string; evaluating it gives the shift value.
Again taking
11003108 add w8, w8, #12
as the example, the instruction’s binary is 0001000100000000001100 01000 01000:
- the first operand,
0:5→01000→ 8 → the register is a 16-bitw→w8 - the second operand,
5:5→01000→ 8 → the register is a 16-bitw→w8 - the third operand,
10:12→000000001100→ 12 → the constant#12, and the shift is computed as 0 by the function
The result is add w8, w8, #12.
fshift: {
return (_lrs_eq(c, 22, 1, 0x0) ? 0 : 12);
},
falias_add_mov_boolean: {
// sh == '0' && imm12 == '000000000000' && (Rd == '11111' || Rn == '11111')
return _lrs_eq(c, 22, 1, 0x0) && _lrs_eq(c, 10, 12, 0x0) && (_lrs_eq(c, 0, 5, 0x1f) || _lrs_eq(c, 5, 5, 0x1f));
}
// These two functions are passed the instruction code, i.e. c
III. Engine implementation
Once the DSL for describing instructions is done, you can write a generator. The generator’s job is to emit data in a concrete language — it can target C, C++, Go, Rust, whatever you like. My engine is written in C, so it should generate C code for me. My C structures look like this:
// A fragment of the code — and don't worry about memory alignment.
typedef uint8_t u1;
typedef uint16_t u2;
typedef uint32_t u4;
typedef uint64_t u8;
struct jd_arm_tpl {
u2 mnemonic_index; // index
u4 eq_mask; // equal mask
u4 eq_val; // equal value
u4 ne_mask; // not equal mask
u4 ne_val; // not equal value
u1 oprand_count; // number of operands
u2 oprands[MAX_OPRAND_SIZE]; // operand array
u2 child_count; // number of children
u2 children_offset; // offset into the array
u1 has_suffix; // A32 instructions can carry a suffix
u2 suffix_index;
u1 alias_count; // number of aliases
u2 alias_offset; // alias offset
u1 condition; // in T32/A32 an instruction can carry a condition
u2 condition_value_index;
u1 thumb;
// 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// | | | | | | | | | | | | | | | |
// it wide
// `it` — whether behaviour differs inside an IT block
// `wide` — whether a Thumb instruction needs the wide modifier
u2 def_use_map; // dataflow bitmap
u4 side_effects; // instruction side effects: n/c/z/v
u2 flags;
u2 semantic; // instruction semantics
};
With this structure in hand, the generator can emit a giant opcode table in C.
Given that table, you can then walk it — by loop or by recursion — to resolve each concrete instruction.
Later I want to write about using this engine to do static analysis of ARM64 binaries.