ARM static analysis engine internals, Part 3: Control flow construction basics

2026-10-08

Translated by DeepSeek Flash.

Originally published in Chinese on Kanxue Forum.

Once the disassembly engine is done, the next step is building control flow for the elf.

A complete ELF control flow analysis engine usually breaks down into a few parts:

Binary loader: parse the ELF and identify the initial analysis entries.
Recursive descent: start from known entries and recursively build control flow.
Special control structure recognition: handle the control flow structures that plain recursive descent struggles to cover, such as jumptables and indirect br jumps.

The first step decides where we start analysing, the second walks the control flow outward, and the third handles the special control structures that are everywhere in real-world binaries.

I. Identifying ELF entries

Android apps contain all sorts of ELFs.

Besides the standard ELF produced by GCC/Clang, you’ll run into ELFs generated by large runtimes and game engines — Dart VM, Cocos2d, Unity3D, and so on.

The “ELF entry” here really means the analysis entry, so in Rosemary I abstract all of them under one name: analysis entry.

Entries are defined like this:

typedef enum jd_entry_type {
    ENTRY_POINT_ENTER = 0,
    ENTRY_POINT_INIT,          // .init
    ENTRY_POINT_FINI,          // .fini
    ENTRY_POINT_INIT_ARRAY,    // .init_array / .fini_array
    ENTRY_POINT_SYMBOL,        // function symbols in the symbol table
    ENTRY_POINT_IFUNC_RESOLVER,// IFUNC resolver
    ENTRY_POINT_PLT,           // .plt
    ENTRY_POINT_EH_FRAME,      // .eh_frame
    ENTRY_POINT_VTABLE,        // C++ vtable
    ENTRY_POINT_PROLOGUE_SCAN, // prologue scan
    ENTRY_POINT_ASSEMBLY_BL,   // entries discovered while decoding
    ENTRY_POINT_ASSEMBLY_BLR,  // entries discovered during analysis
} jd_entry_type;

BL and BLR are discovered while recursive descent is decoding assembly instructions.

II. Building control flow with recursive descent

Building control flow by recursive descent is the modelling step of a static analysis tool.

The things involved are the control flow node, edge, end instruction, branch instruction, and trap function.

2.1 The helper methods control flow construction needs

Taking ARM64 again: the helpers you need to build control flow are really just an understanding of ARM assembly, like this:

#ifndef GARLIC_JD_ARM_INSTRUCTION_H
#define GARLIC_JD_ARM_INSTRUCTION_H

// jump target of an ARM instruction
static inline u8 jd_arm_a64_ins_target(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);

    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_B:
        case JD_ARM_A64_INS_BC:
        case JD_ARM_A64_INS_BL: {
            jd_arm_imm_operand *imm = jd_arm_get_oprand(ins, tpl->oprands[0]);
            u8 addr = jd_arm_value_to_u8(ins, imm->imm_value_index);
            return addr;
        }
        case JD_ARM_A64_INS_CBZ:
        case JD_ARM_A64_INS_CBNZ:
        {
            jd_arm_imm_operand *imm = jd_arm_get_oprand(ins, tpl->oprands[1]);
            u8 addr = jd_arm_value_to_u8(ins, imm->imm_value_index);
            return addr;
        }
        case JD_ARM_A64_INS_TBNZ:
        case JD_ARM_A64_INS_TBZ: {
            jd_arm_imm_operand *imm = jd_arm_get_oprand(ins, tpl->oprands[2]);
            u8 addr = jd_arm_value_to_u8(ins, imm->imm_value_index);
            return addr;
        }
        default: return 0;
    }
}

// which instructions must stop recursive descent
static inline bool jd_arm_a64_ins_dfs_stop(jd_arm_ins *ins) {
    jd_arm_tpl *tpl = INS_TPL(ins);
    if (tpl == NULL)
        return true;
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_UDF:
        case JD_ARM_A64_INS_RET:
        case JD_ARM_A64_INS_RETAA:
        case JD_ARM_A64_INS_RETAB:
        case JD_ARM_A64_INS_RETAASPPC:
        case JD_ARM_A64_INS_RETABSPPC:
        case JD_ARM_A64_INS_RETAASPPCR:
        case JD_ARM_A64_INS_RETABSPPCR:
        case JD_ARM_A64_INS_ERET:
        case JD_ARM_A64_INS_ERETAA:
        case JD_ARM_A64_INS_ERETAB:
        case JD_ARM_A64_INS_DRPS:
        case JD_ARM_A64_INS_BRAA:
        case JD_ARM_A64_INS_BRAB:
        case JD_ARM_A64_INS_BLRAA:
        case JD_ARM_A64_INS_BLRAB:
        case JD_ARM_A64_INS_SVC:
        case JD_ARM_A64_INS_HVC:
        case JD_ARM_A64_INS_SMC:
        case JD_ARM_A64_INS_HLT:
        case JD_ARM_A64_INS_DCPS1:
        case JD_ARM_A64_INS_DCPS2:
        case JD_ARM_A64_INS_DCPS3:
        case JD_ARM_A64_INS_BR:
        case JD_ARM_A64_INS_BRAAZ:
        case JD_ARM_A64_INS_BRABZ:
        case JD_ARM_A64_INS_WFET:
        case JD_ARM_A64_INS_WFIT:
        case JD_ARM_A64_INS_WFE:
        case JD_ARM_A64_INS_WFI:
            return true;
        case JD_ARM_A64_INS_BRK: {
            if (ins->code == 0xd4200000) {
                return false;
            }
            return true;
        }
        default: return false;
    }
}

// which instructions have a fallthrough
static inline bool jd_arm_a64_ins_has_fallthrough(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_B: {
            // b.<cond>
            if (_lrs_eq(ins->code, 24, 8, 0x54))
                return true;
            return false;
        }
        case JD_ARM_A64_INS_BC: {
            if (_lrs_eq(ins->code, 24, 8, 0x54))
                return true;
            return false;
        }
        case JD_ARM_A64_INS_BR:
        case JD_ARM_A64_INS_BRAA:
        case JD_ARM_A64_INS_BRAB:
        case JD_ARM_A64_INS_BRAAZ:
        case JD_ARM_A64_INS_BRABZ:
        case JD_ARM_A64_INS_RET:
        case JD_ARM_A64_INS_RETAA:
        case JD_ARM_A64_INS_RETAB:
        case JD_ARM_A64_INS_RETAASPPC:
        case JD_ARM_A64_INS_RETABSPPC:
        case JD_ARM_A64_INS_RETAASPPCR:
        case JD_ARM_A64_INS_RETABSPPCR:
        case JD_ARM_A64_INS_ERET:
        case JD_ARM_A64_INS_ERETAA:
        case JD_ARM_A64_INS_ERETAB:
            return false;
        case JD_ARM_A64_INS_BL: {
            u8 target = jd_arm_a64_ins_target(ins);
            if (jd_bitmap_test(ins->region->noreturn_bitmap, target)) {
                return false;
            }
            return true;
        }
        default:
            return true;
    }
}

// which instructions have a target
static inline bool jd_arm_a64_ins_has_target(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_B:
        case JD_ARM_A64_INS_BC:
        case JD_ARM_A64_INS_BL:
        case JD_ARM_A64_INS_CBZ:
        case JD_ARM_A64_INS_CBNZ:
        case JD_ARM_A64_INS_TBZ:
        case JD_ARM_A64_INS_TBNZ:
            return true;
        default:
            return false;
    }
}

static inline bool jd_arm_a64_ins_is_jump(jd_arm_ins *ins) {
    jd_arm_tpl *tpl = INS_TPL(ins);
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_B:
        case JD_ARM_A64_INS_BC:
        case JD_ARM_A64_INS_BL:
        case JD_ARM_A64_INS_CBZ:
        case JD_ARM_A64_INS_CBNZ:
        case JD_ARM_A64_INS_TBZ:
        case JD_ARM_A64_INS_TBNZ:
            return true;
        default:
            return false;
    }
}

// unconditional jump
static inline bool jd_arm_a64_ins_is_unconditional_jump(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);
    if (tpl->mnemonic_index == JD_ARM_A64_INS_B &&
        !_lrs_eq(ins->code, 24, 8, 0x54))
        return true;

    return false;
}

// conditional jump
static inline bool jd_arm_a64_ins_is_condtional_jump(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_B: {
            // b.<cond>
            if (_lrs_eq(ins->code, 24, 8, 0x54))
                return true;
            return false;
        }
        case JD_ARM_A64_INS_BC: {
            if (_lrs_eq(ins->code, 24, 8, 0x54))
                return true;
            return false;
        }
        case JD_ARM_A64_INS_CBZ:
        case JD_ARM_A64_INS_CBNZ:
        case JD_ARM_A64_INS_TBZ:
        case JD_ARM_A64_INS_TBNZ:
            return true;
        default:
            return false;
    }
}

static inline bool jd_arm_a64_ins_is_call_fuction(jd_arm_ins *ins) {
    jd_arm_tpl *tpl = INS_TPL(ins);
    return tpl->mnemonic_index == JD_ARM_A64_INS_BL;
}

static inline bool jd_arm_a64_ins_is_bb_end(jd_arm_ins *ins)
{
    jd_arm_tpl *tpl = INS_TPL(ins);
    switch (tpl->mnemonic_index) {
        case JD_ARM_A64_INS_RET:
        case JD_ARM_A64_INS_RETAA:
        case JD_ARM_A64_INS_RETAB:
        case JD_ARM_A64_INS_RETAASPPC:
        case JD_ARM_A64_INS_RETABSPPC:
        case JD_ARM_A64_INS_RETAASPPCR:
        case JD_ARM_A64_INS_RETABSPPCR:
        case JD_ARM_A64_INS_ERET:
        case JD_ARM_A64_INS_ERETAA:
        case JD_ARM_A64_INS_ERETAB:
        case JD_ARM_A64_INS_B:
        case JD_ARM_A64_INS_BC:
        case JD_ARM_A64_INS_CBZ:
        case JD_ARM_A64_INS_CBNZ:
        case JD_ARM_A64_INS_TBZ:
        case JD_ARM_A64_INS_TBNZ:
            return true;
        case JD_ARM_A64_INS_BL: {
            u8 target = jd_arm_a64_ins_target(ins);
            if (jd_bitmap_test(ins->region->noreturn_bitmap, target))
                return true;
            return false;
        }
        default:
            return false;
    }
}


#endif //GARLIC_JD_ARM_INSTRUCTION_H

2.2 noreturn functions

When an instruction calls one of the functions below — say bl 0x1234, where 0x1234 is __stack_chk_fail — that point should end the basic block.

static bool jd_known_noreturn_name(const char *name)
{
    if (!name) return false;

    return strcmp(name, "__stack_chk_fail") == 0 ||
           strcmp(name, "__stack_chk_fail_local") == 0 ||
           strcmp(name, "abort") == 0 ||
           strcmp(name, "__assert_fail") == 0 ||
           strcmp(name, "__cxa_throw") == 0 ||
           strcmp(name, "__cxa_rethrow") == 0 ||
           strcmp(name, "std::terminate") == 0 ||
           strcmp(name, "_ZSt9terminatev") == 0 ||
           strcmp(name, "exit") == 0 ||
           strcmp(name, "_exit") == 0 ||
           strcmp(name, "_Exit") == 0 ||
           strcmp(name, "__fortify_fatal") == 0 ||
           strcmp(name, "__android_log_assert") == 0 ||
           strcmp(name, "pthread_exit") == 0 ||
           strcmp(name, "_Unwind_Resume") == 0;
}

2.3 Construction

The classic way to build control flow is a worklist.

worklist = {data1, data2, ...}

while worklist != NULL:
    x = pop(worklist)
    if y = deal_with(x)
      push(queue, y)

Those three steps are the foundation for building ELF control flow, but there are a great many details. For example:

instruction/cfg storage structure. A .so of roughly 30 MB produces 7–8 million instructions, and the control flow graph’s nodes and edges run into the millions. Since construction needs lookups, the data structures matter enormously.
basic block splitting.
control flow jumping to an already-known node.
function head recognition. Falling through into a function head means you have to stop analysing and end the basic block.
discovering new functions. bl to a PC makes that PC a function by default.

III. Recognizing special structures

In ARM64 there are only a handful of special structures.

jumptable. A jumptable is the codegen the compiler emits for switch/case. With few cases it may be optimized into branches; with many cases you get a jumptable.
vtable. A vtable is the compiled artifact of a C++ class — a list of function pointers. The main work is recognizing the vptr, then using the vptr plus runtime type info to identify C++ member functions.
blr. blr covers a great many cases: function pointer arrays, pointer lists inside structs, and so on. blr cannot be fully resolved — even with IR, it is extremely hard.

Once these special structures have been recognized, feed the PCs you found back into the worklist from step two and keep recursing, until there are no new entries left.