ARM static analysis engine internals, Part 4: IR design and application
Translated by DeepSeek Flash.
Originally published in Chinese on Kanxue Forum.
The previous article covered the most important part of static analysis — control flow recovery. Every control flow recovery tool faces one major challenge: recovering indirect jumps. In ARM that means br Xn, where the jump target comes from a register whose value is unknown. IDA, Binary Ninja, Ghidra and R2 all have this problem — none of them can recover every indirect jump.
So where does br Xn actually come from? There are several cases.
1. switch/case
Not every switch/case compiles to br Xn. With few cases, like this:
switch (variable) {
case 0: printf("xxx\n") break;
default: printf("default\n"); break;
}
the compiler turns it into branches, because with so few paths it can get away with if/else — ifeq in assembly.
But what if the switch is enormous? Here’s an example from IDA:
.text:0000000000056970 MOV W24, #0x3594A0BB
.text:0000000000056978 ADRL X25, jpt_569A0
.text:0000000000056980 B def_569A0 ; jumptable 00000000000569A0 default case
.text:0000000000056984 ; ---------------------------------------------------------------------------
.text:0000000000056984
.text:0000000000056984 loc_56984 ; CODE XREF: .text:00000000000569A0↓j
.text:0000000000056984 ; .text:0000000000056EAC↓j
.text:0000000000056984 ; DATA XREF: ...
.text:0000000000056984 MOV W8, #0xD ; jumptable 00000000000569A0 case 5
.text:0000000000056988 STR W8, [SP,#8]
.text:000000000005698C
.text:000000000005698C def_569A0 ; CODE XREF: .text:0000000000056980↑j
.text:000000000005698C ; .text:0000000000056994↓j ...
.text:000000000005698C UBFX X9, X8, #0, #0x20 ; ' ' ; jumptable 00000000000569A0 default case
.text:0000000000056990 CMP W8, #0x1B ; switch 28 cases
.text:0000000000056994 B.HI def_569A0 ; jumptable 00000000000569A0 default case
.text:0000000000056998 LDRSW X8, [X25,X9,LSL#2]
.text:000000000005699C ADD X8, X8, X25
.text:00000000000569A0 BR X8 ; switch jump
Here ADRL is shorthand for adrp plus a page offset, and the address jpt_569A0 holds the offsets of all the cases:
.text:0000000000056F18 jpt_569A0 DCD loc_569A4 - 0x56F18 ; DATA XREF: .text:0000000000056978↑o
.text:0000000000056F18 ; jump table for switch statement
.text:0000000000056F1C DCD loc_569D4 - 0x56F18 ; jumptable 00000000000569A0 case 1
.text:0000000000056F20 DCD loc_56D30 - 0x56F18 ; jumptable 00000000000569A0 case 2
.text:0000000000056F20 ; jumptable 0000000000056CEC case 74
..... omitted here
.text:0000000000056F80 DCD loc_56D24 - 0x56F18 ; jumptable 00000000000569A0 case 26
.text:0000000000056F80 ; jumptable 0000000000056CEC case 73
.text:0000000000056F84 DCD loc_56EF8 - 0x56F18 ; jumptable 00000000000569A0 case 27
At this point it’s obvious. The compiler’s job here, put simply, is: first, find every case; second, store their offsets; then compare W8 and load the matching address to jump to the case.
2. C++ vtables
A vtable is the by-product of C++ polymorphism — a list of function pointers. Its C++ structure is rtti (RuntimeTypeInfo), stored behind a pointer named vptr.
To recognize a vtable you first have to recognize rtti. Only once the rtti typeinfo structure is correctly identified can the vtable’s structure be fully inferred.
typeinfo comes in a few flavours:
__si_class_type_info single-inheritance class
__vmi_class_type_info multiple- or virtual-inheritance class
__class_type_info standalone base class, no inheritance
3. Function pointer arrays
A function pointer array is, as the name says, an array full of function pointers.
But this is also the silliest structure of the lot, because it is completely non-standardized.
You can write func_arrs = [0x1234, 0x5679] — func_arrs might hold uint data, or it might hold function addresses, and to the compiler it is all just data.
So recognizing this structure is very much a matter of opinion.
The article is titled “IR design” — so why have I dragged in all this indirect jump material? Because some of these structures can be recognized by pattern matching. Veterans like IDA/BN/Ghidra/R2 have weathered many generations of compiler changes, and their recognition libraries contain a pile of patterns for these jumps. If you’re building something new to handle indirect jumps, the better approach is to do it through IR patterns rather than pattern matching.
I haven’t studied GCC/LLVM IR; I’m only writing about the IR design and development of the Rosemary engine.
I. Assembly language operands
AArch64 assembly has a few kinds of operands: register, immediate (imm), memory (mem), list (vlist), and rbitlist.
Without NEON/SVE/SME, only the first three exist.
vlist is my own term, for describing structures like {v1, v2, v3, v4} and {v2-v3}.
rbitlist is the bit-register array in A32/T32 structures.
So in principle the IR’s base data structures are just these four: register / imm / mem / vlist / rbitlist.
II. Definition and use
I wrote it in C, so the IR’s C definition looks like this:
typedef struct jd_exp {
u1 type; // expression type
union {
struct {
u1 idx; // X4
u1 t; // register type: standard register (X/W) or vector register (V)
u1 size; // vector register width
} reg;
struct {
u4 hi; // high bits
u4 lo; // low bits
u1 is_sign;
u1 is_addr;
u1 is_page;
} imm;
struct {
jd_rid addr;
u1 elane_type;
u1 access_mode; // flags: liner_access, structure_access, scalable_mode
u1 size; // for NEON or SVE/SME this is the struct size; plain linear access has none
u1 orientation; // orientation, for SME
u1 is_signed;
u4 index;
} mem;
struct {
u2 mnemonic;
u1 def_flags;
u1 use_flags;
u1 args_count;
jd_rid args_start_index;
} invoke;
}
} jd_exp;
With this structure we can describe an instruction — adds x1, x2, #1:
jd_exp *x1 = malloc(sizeof(jd_exp));
x1->type = JD_REGISTER;
x1->t = JD_REGISTER_TYPE_X;
x1->idx = 0x1;
jd_exp *x2 = malloc(sizeof(jd_exp));
x2->type = JD_REGISTER;
x2->t = JD_REGISTER_TYPE_X;
x2->idx = 0x2;
jd_exp *imm = malloc(sizeof(jd_exp));
imm->type = JD_IMM;
imm->idx = 0x1;
imm->hi = 0x0;
imm->lo = 0x1;
jd_exp *add_exp = malloc(sizeof(jd_exp));
add_exp->t = JD_INVOKE;
add_exp->mnemonic = JD_MNEMONIC_ADDS;
add_exp->args_count = 3;
add_exp->args_start_index = xxxx; // start position in the big array
add_exp->def_flags = 0xxxx; // marks the def of the adds instruction in the dataflow
add_exp->use_flags = 0xxxx; // marks the use of the adds instruction in the dataflow
With that, every array for an adds instruction is described.
expressions = { exp_x1, exp_x2, exp_imm, exp_invoke_adds };
You can see that this structure is logically nested but stored flat.
III. Extending the IR
With only those four IR types, descriptions would get more and more complicated — reducing any particular kind of structure would only get messier. Take adds above: if it were adds x1, #0x1, 0x2, then simplifying the IR would end up written like this:
if (invoke->mnemonic == JD_JD_MNEMONIC_ADDS) {
if (op1->type == JD_IMM && op2->type == JD_IMM) {
// only here can x1 be simplified into a constant
}
}
So the IR needs these additional types:
struct {
u1 op; // +, -, *, <<
jd_rid left;
jd_rid right;
u1 def_flags;
u1 use_flags;
} binary; // add/sub/mul/div, shifts, and/or/not, etc.
struct {
jd_reg_id reg_id;
jd_rid block_id;
} phi_ref; // the SSA phi
struct {
jd_rid left;
jd_rid right;
} assignment_reg; // register three-address code: x1 = x2 + #0x1
struct {
jd_rid left;
jd_rid right;
} assignment_mem; // memory three-address code
struct {
jd_rid addr_exp_id;
} load_addr; // address load
With these, instructions can be simplified: adds evolves from invoke into binary, and from binary into an assignment_reg.
assigment_reg: left(x1) = right(binary(left(#0x1) + right(#0x2)))
Simplification then becomes straightforward — during constant folding you can reduce it to the constant 3 purely from x1’s def/use.
IV. IR in practice
This is where we can finally answer the question from the start of the article: using IR to recognize structures like jumptable and vtable. Let’s look at the simplest jumptable example. In IDA a jumptable looks like this:
.text:000000000043F6F0 loc_43F6F0 ; CODE XREF: sub_43F4F8+120↑j
.text:000000000043F6F0 ADRL X9, jpt_43F700
.text:000000000043F6F8 LDRSW X8, [X9,X8,LSL#2]
.text:000000000043F6FC ADD X8, X8, X9
.text:000000000043F700 BR X8 ; switch jump
Its real machine code:
adrp x9, #6057984 // decimal here
add x9, x9, #1100
ldrsw x8, [x9, x8, lsl #2]
add x8, x8, x9
br x8
The meaning is simple — this is a standard jumptable structure:
adrp x9, #6057984loads the page containing the jumptable into x9, i.e. x9 is a defadd x9, x9, #1100adds the jumptable’s offset to x9ldrsw x8, [x9, x8, lsl #2]loads the contents of the memory at x9 into x8; thelslhere is the stridebr x8jumps to the specific case
In the IR we defined, the jumptable’s IR expression looks like this:
[BR TRACE #4318474]
instruction px: 0x0043f700
root trace idx: 4318474
trace tree:
[def] call:br((load([((6057984 + 1100) + ((PHI: reg_id: 8, off: 1458453, count: 2) << 2))]) + (6057984 + 1100)))
With an IR description like this, a jumptable can be fully recognized. That is:
- the jumptable is located at 6057984 + 1100
- each case’s stride in the jumptable is
<< 2, i.e. 4 - by walking back up from the jumptable’s IR to find the
cmp, you complete the recognition of the whole jumptable.
This is just one thing IR does; its uses go far beyond it. IR in this form can be lifted further, and once lifted into a minimal structure you can go on to do:
Control structure recognition (if/else/else if/switch/for/while/do while)
Type recognition (uint/int/long)
Local variable recovery
Stack recovery
Stack balancing
Function arguments spilling to the stack
and so on. Right now Rosemary only gets as far as control structure recognition and stack balancing with IR.
V. Engineering the IR
Understanding an IR this simple isn’t hard. The really hard part is engineering it. After assembly is lifted, it doesn’t happen in one shot — the process is more like a spiral, and a narrowing one at that:
decoder -> control flow -> data flow -> lift to ir -> decoder -> control flow -> data flow .....
while (next)
decoder
make control flow
make data flow
lifter to ir
if (find function or entries)
next = true
end
Static analysis is a loop like this: as it runs it keeps discovering new functions and new entries, narrowing the loop each time, until there is nothing new left.
In this process, every data structure definition — even every struct member — has an enormous effect on overall performance.
- Pointers. On a 64-bit system a pointer is 8 bytes; using a
uint32_tinstead of a pointer saves half the memory. - Memory alignment. Reducing padding saves a lot of memory too.
- Storage structure. List versus array. A list looks fast and is simple to develop, but a list actually costs a lot of memory — think of Java’s
ArrayList. - CPU cache. Cache behaviour is also key to data structure design; a flat array is far more cache-friendly than a list.
After a lot of debugging and profiling, Rosemary’s storage structures all ended up on arrays, with no pointers: it saves memory, it’s cache-friendly, and it runs faster.
Rosemary’s profile, on a 6 MB AArch64 ELF:
~/workspace/clang/garlic (main)$ time -v ./build/rosemary
----- elf memory start ------
[elf memory] elf's binary buffer: 7127792, 6 MB
[elf memory] elf's entry points: 27119, size: 32 memory: 0 MB
[elf memory] elf's entry hashmap: 27119 size: 16, memory: 0 MB
[elf memory] elf's jd_pc_addr: 30953, size: 24, memory: 0 MB
[elf memory] elf's jd_addr: 55135, size: 24, memory: 1 MB
[elf region] pc range: 0 -> 69912c
[elf memory] elf's region bitmap: 0 MB
[elf memory] elf's basic block count: 207249, size: 176, memory: 34 MB, includes defs/uses/livein/liveout
[elf memory] basic block's defs count: 207249, size: 16, memory: 3 MB
[elf memory] basic block's uses count: 207249, size: 16, memory: 3 MB
[elf memory] basic block's livein count: 207249, size: 16, memory: 3 MB
[elf memory] basic block's liveout count: 207249, size: 16, memory: 3 MB
[elf memory] elf's edge count: 500304, size: 8, memory: 3 MB
[elf memory] elf's expression count: 4342012, size: 32, memory: 132 MB
[elf memory] elf's jd_elf_func_ins count: 1284442, size: 16, memory: 19 MB
[elf memory] elf's def_exp_ids_arr: 819583, size: 4, memory: 3 MB
[elf memory] elf's use_exp_ids_arr: 681656, size: 4, memory: 2 MB
[elf memory] elf's phi_args_arr: 1483587, size: 4, memory: 5 MB
[elf memory] elf's invoke_args_arr: 1504192, size: 4, memory: 5 MB
[elf memory] elf's pc_map_ins: 3459222, size: 4, memory: 13 MB
[elf memory] elf's functions: 20379, size: 88, memory: 1 MB
[elf memory] elf's jumptable: 332, size: 72, memory: 0 MB
[elf memory] elf's jumptable target: 3018, size: 4, memory: 0 MB
[elf memory] elf's vtable: 1430, size: 40, memory: 0 MB
[elf memory] elf's vtable target: 7779, size: 4, memory: 0 MB
[elf memory] elf's phi_arr: 665071, size: 20, memory: 12 MB
[elf memory] elf's collapsed phi count: 115246
[elf memory] elf's xref: 401952, size: 12, memory: 4 MB
[elf memory] elf's stack event: 126278, size: 24, memory: 2 MB
[elf region] pc range: 69a250 -> 6d515c
[elf memory] elf's region bitmap: 0 MB
[elf memory] elf's basic block count: 0, size: 176, memory: 0 MB, includes defs/uses/livein/liveout
[elf memory] basic block's defs count: 0, size: 16, memory: 0 MB
[elf memory] basic block's uses count: 0, size: 16, memory: 0 MB
[elf memory] basic block's livein count: 0, size: 16, memory: 0 MB
[elf memory] basic block's liveout count: 0, size: 16, memory: 0 MB
[elf memory] elf's edge count: 1, size: 8, memory: 0 MB
[elf memory] elf's expression count: 1, size: 32, memory: 0 MB
[elf memory] elf's jd_elf_func_ins count: 0, size: 16, memory: 0 MB
[elf memory] elf's def_exp_ids_arr: 0, size: 4, memory: 0 MB
[elf memory] elf's use_exp_ids_arr: 0, size: 4, memory: 0 MB
[elf memory] elf's phi_args_arr: 0, size: 4, memory: 0 MB
[elf memory] elf's invoke_args_arr: 0, size: 4, memory: 0 MB
[elf memory] elf's pc_map_ins: 120710, size: 4, memory: 0 MB
[elf memory] elf's functions: 0, size: 88, memory: 0 MB
[elf memory] elf's jumptable: 0, size: 72, memory: 0 MB
[elf memory] elf's jumptable target: 0, size: 4, memory: 0 MB
[elf memory] elf's vtable: 0, size: 40, memory: 0 MB
[elf memory] elf's vtable target: 0, size: 4, memory: 0 MB
[elf memory] elf's phi_arr: 0, size: 20, memory: 0 MB
[elf memory] elf's collapsed phi count: 0
[elf memory] elf's xref: 0, size: 12, memory: 0 MB
[elf memory] elf's stack event: 0, size: 24, memory: 0 MB
[elf memory] elf's instruction: 1192597, size: 24, memory: 27 MB
[elf memory] elf's region: 2, size: 1952, memory: 0 MB
[elf memory] elf's template count: 6000, size: 68, memory: 0 MB
----- elf memory end ------
Command being timed: "./build/rosemary"
User time (seconds): 1.62
System time (seconds): 0.11
Percent of CPU this job got: 72%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:02.39
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 317872
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 218
Minor (reclaiming a frame) page faults: 21039
Voluntary context switches: 290
Involuntary context switches: 253
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 8
Socket messages received: 8
Signals delivered: 0
Page size (bytes): 16384
Exit status: 0