nordisk/nornir

The binary graph: plan

Mímir reads Rust programs from their MIR (code_mir, code_instances, exec-graph.md). This plan adds the layer that reads the COMPILED program: the machine code of an ELF file and of the shared libraries it loads. Programs written in C (iperf3, busybox, nginx, the C library itself) then get what Rust programs have: a call graph, per-function control flow, the system-call boundary, and the executor's order graph and possible set.

What it is for: defensive tooling for Heimdall's sandbox filters. Static binary analysis derives and checks seccomp profiles, as in sysfilter (DeMarinis et al., RAID 2020), Confine (Ghavamnia et al., RAID 2020) and B-Side (Thévenon et al., Middleware 2024). The graph says which system calls a program CAN make; Heimdall's probe says which ones it DID make; the cross-check (dwarves-tune-graph) names the difference. The graph never widens a filter on its own.

Words: a module is one ELF file (the program, libc.so.6, ld.so). A machine function is one function of a module's code. A block is a basic block of machine instructions. A site is one instruction that matters to the graph: a call, a jump out of the function, a syscall.

0. Decisions

D1. ONE graph. The binary layer EXTENDS the Rust graph. It is not a second graph format, a second store or a second executor.

• The same node ids. A Rust fn's machine code and its MIR are ONE node: the machine row of a Rust instance carries that instance's key. A C function, a libc function and an assembly routine become new nodes of the existing kinds (fn for a function with a body, ffi for an import the program names).
• The same edge kinds: CALLS (function to function, imports resolved to the library that defines them), SYSCALLS (a function to the @syscall node of each call its syscall instruction can make), CFG_SUCC (block level). As for code_mir, these are a DERIVED view of the lossless rows (code_asm::legacy, beside code_mir::legacy), not stored twice.
• The same lake, room and executor. The rows sit beside code_mir in the same schema family (mimir-schema, schema 8, mimir.table metadata). The lake keeps them under owners like the dump's. mimir-exec loads machine bodies next to MIR bodies and runs them with the same reach, values, order and entry passes. It writes the same exec.nodes, exec.edges, exec.marks and mimir.possible-syscalls/1.

D2. The curated C-library map stays, as the fallback and as the oracle. When the machine body of a C function is loaded, the executor walks it. When it is not (no library given), libc_map answers as today. A test compares the two on glibc and musl: every map entry against the machine graph of that function. A difference is a finding in one of them.

D3. Pure Rust, stable. No C disassembler (no capstone, no Binary Ninja code), no rayon, no petgraph. The producer is a library; the CLI is a thin front end.

D4. Per-module rows, keyed by build id. A shared library is analysed ONCE per build id (like the toolchain dump --std) and its rows are reused by every program that loads it. Linking (which import goes to which library) is a per-program step of the executor's load, not stored per module.

D5. Schema additions go through the exec-graph lane (it owns mimir-schema and mimir-exec): proposed and agreed in /work/exec-graph/out/FOR-BINARY.md before they merge.

1. What exists in Rust, and what we use

Surveyed 2026-11-07 (crates.io, docs.rs, the papers).

What is missing in Rust, so we build it: a function and block model keyed to Mímir ids, PLT/GOT/IFUNC import resolution across modules, a small value analysis for system-call numbers and function-pointer arguments (wrappers in glibc and musl), jump-table recovery for GCC and Clang code, and the rows plus their derived view.

2. Dataflow

 mimir-binary --asm <elf> [--root <image root>]          once per module (build id); a library once per toolchain/image
   object: sections, symtab+dynsym, .rela.plt/.rela.dyn, DT_NEEDED, .init_array, e_entry
   gimli:  .eh_frame FDEs (function bounds), .debug_line (file:line)
   iced-x86: recursive descent per function ─► blocks, sites
   value pass (per function, §5) ─► syscall numbers, wrapper params, fn-pointer args
   ─────────────────────────────────────────► <module>.asm.arrow        code_asm       (1 row / machine function)
                                              <module>.asmmod.arrow     code_asm_mods  (1 row / module)
 program load (mimir_store::program)                                   per program
   DT_NEEDED breadth first, the loader's search order ─► the module set
   imports → the first module that exports the symbol (version-aware) ─► link table
   code_asm.inst = a code_instances key (Rust fn, by demangled symbol) ─► ONE instance, two bodies
 mimir-exec                                                            the same executor
   reach → values → order → entries over MIR bodies AND machine bodies
   exec.nodes  exec.edges  exec.marks   <bin>.possible.json  (mimir.possible-syscalls/1)
 derived view (code_asm::legacy)                                       on demand, for the room and the lenses
   fn / ffi nodes, CALLS, SYSCALLS → @syscall@<arch>.r1, CFG_SUCC

3. The tables

crates/mimir-schema/src/code_asm.rs, the same style as code_mir: one row holds a whole function as parallel arrays (Arrow List columns), a per-row string pool strs, content = a hash of the other columns (the lake's delta key).

code_asm, identity fn (the machine function's key, §3.1):

code_asm_mods, identity module: path (as given), soname, build_id, arch, kind (exec, pie, shared, static, static-pie), interp, needed (list), runpath (list), entry, init / fini (lists of function keys from .init_array / .fini_array), exports (function keys, with symbol versions), imports (name, version, PLT or GOT slot), ifunc (symbol → resolver key), address_taken (function keys, §4.4), libc (glibc + version, musl + version, none: read from the module's own strings and sonames), stats (JSON: counts of the ledger, §9).

3.1 Keys

module key    <file name or soname>[elf]@<build id, 16 hex>       libc.so.6[elf]@3a1f0c9e2b7d4410
fn key        <module key>::<symbol, demangled-free>              libc.so.6[elf]@3a1f0c9e2b7d4410::__libc_open64
              <module key>::fn@<hex address>                      a function without a symbol (stripped busybox)
node id       <fn key or instance key>#<block>                    the same form as exec.nodes' node ids

The module key has the def key's shape (<package>[<target>]@<version>), so every reader that splits a def key splits it. A module without a build id uses the SHA-256 of its bytes, cut to 16 hex digits.

4. Calls

4.1 Functions and blocks

Function starts: STT_FUNC symbols of .symtab and .dynsym, the .eh_frame FDE starts, e_entry, the .init_array / .fini_array entries, and every direct call target found (recursive descent adds them). Bounds: the symbol size, else the FDE length, else the next start.

Blocks by recursive descent inside the bounds: a leader is the start, every branch target and every instruction after a branch, return, call of a noreturn function, hlt or ud2. Noreturn: a known list (exit, _exit, _Exit, abort, __stack_chk_fail, __assert_fail, __libc_fatal, __fortify_fail, pthread_exit, longjmp, siglongjmp, _Unwind_Resume) plus every function from which no ret is reachable (a fixed point).

4.2 Direct calls, tail calls

call rel32 → the function at the target. jmp whose target is outside the function's bounds and at a function start = a tail call (a call edge and a return).

4.3 Imports: PLT, GOT, IFUNC

call plt_stub(k)      .plt/.plt.sec slot k ── R_X86_64_JUMP_SLOT ──► import (name, version)
call [rip + got]      (-fno-plt)          ── R_X86_64_GLOB_DAT  ──► import
import (n, v)         resolved per program: the FIRST module in load order that exports n
                      (version v when the import names one, the default version otherwise)
IFUNC symbol n        STT_GNU_IFUNC: the call goes to what the resolver returns:
                      targets(n) = the function addresses the resolver's value pass gives in rax
                      (memcpy, strlen …: every implementation it can pick)

Load order is the dynamic loader's: the program, then DT_NEEDED breadth first, each searched in DT_RPATH (no DT_RUNPATH), LD_LIBRARY_PATH (not used: a filter is made for a fixed environment), DT_RUNPATH, /etc/ld.so.conf and its includes under the image root, then /lib, /usr/lib and the multiarch dirs (glibc), or musl's /etc/ld-musl-<arch>.path and its defaults. $ORIGIN is the module's directory. A library not found is in missing_libs; an import no module exports is in unresolved_imports.

4.4 Indirect calls and jumps

target(s)  = V(s) when the value pass gives a constant set of function addresses      (exact)
           = targets at the callers when V(s) = Param(p)                              (§5.3)
           = AT                                                                       (widened)
AT         = ⋃ over loaded modules of the functions whose address is taken:
               a lea/mov of a function start in REACHED code,
               a pointer to a function start in data (R_X86_64_RELATIVE, R_X86_64_64, absolute words
               in .data/.data.rel.ro of a non-PIE), a GLOB_DAT of a function symbol

A widened call is marked: its reach is direct = false in the possible set (the shape dwarves-tune-graph already reads). This is sysfilter's address-taken rule, cut to what reached code and the data can name, the same rule the Rust graph applies to fn pointers (§5.1 of exec-graph.md).

Jump tables (an indirect jmp inside a function). The GCC/Clang forms:

PIC:     lea rT,[rip+table]; movsxd rX,[rT+rI*4]; add rX,rT; jmp rX        entries: table + i32
non-PIC: jmp [table + rI*8]                                                entries: absolute u64
bound:   cmp rI, N-1; ja default   (the dominating compare on the index)   N entries

Entries are read while they point inside the function. A jump the patterns do not match goes to every block of its function that no other edge reaches and that starts after it (widened, counted in the ledger). This only changes the ORDER inside a function; the possible set is a function-level reach and does not depend on it.

5. The system-call boundary

5.1 Sites

x86-64: syscall (0f 05), number in rax. int 0x80 (the 32-bit ABI, other numbers) and sysenter are sites with the note 32-bit system call ABI and the <indirect> call. aarch64: svc #0, number in x8.

5.2 The value pass

Per function, a forward dataflow over its blocks, to the fixed point:

state      σ : Reg ∪ Slot → V            Reg = the 16 GPRs (31 X regs on aarch64), Slot = [entry rsp + 8k]
V          ⊥ | {c1..cn} (n ≤ 8) | Param(p) | ⊤        join: sets ∪ (a 9th value → ⊤), Param(p) ⊔ Param(q) = ⊤ (p ≠ q),
                                                      Param ⊔ set = ⊤
entry      σ(rdi..r9) = Param(1..6), σ([rsp+8k]) = Param(16+k) (k ≥ 1), σ(rsp) = Sp(0), rest ⊤
mov r, imm             σ(r) = {imm}            (32-bit forms zero-extend: mov eax, 39 → {39})
xor r, r / sub r, r    σ(r) = {0}
mov r, r'              σ(r) = σ(r')
lea r, [rip + d]       σ(r) = {address}
add/sub/and/or/shl r, imm   σ(r) = {op(c, imm)} per c; Param → ⊤
movzx / movsxd / cdqe  as a copy, cut to the width
push x / pop r         Sp(δ) moves by 8; the slot gets / gives σ(x)
sub rsp, n / add rsp, n     Sp(δ) moves by n
mov [rsp + k], x       σ(slot at δ + k) = σ(x);   mov r, [rsp + k]: σ(r) = σ(slot)
call f                 the caller-saved registers (rax rcx rdx rsi rdi r8–r11) = ⊤ after it; callee-saved kept
any other write to r   σ(r) = ⊤;   a write through any other pointer: slots unchanged (the stack is not aliased:
                       stated limit)

At a syscall site s: nr(s) = σ(rax). At an indirect call or jump: V(s) = σ(target operand). At a call of a function that is a wrapper (§5.3) on parameter p: the site's value is σ(p) at the call.

5.3 Wrappers: the number comes from a parameter

W(f) = { p | some site of f (a syscall, or a call of a wrapper g on q with σ(q) = Param(p)) has value Param(p) }

A function with W(f) ≠ ∅ is a wrapper. Its own syscall instruction is not a boundary node; every CALL of it is, with the numbers the caller passes. Wrappers of wrappers are handled by the fixed point over the summaries (a caller whose argument is itself Param(q) is a wrapper on q). The same rule resolves a FUNCTION POINTER handed down as a parameter (an indirect call through Param(p)): __libc_start_main(main, …), pthread_create(t, a, start, arg), qsort(…, cmp).

The wrappers this must find (read from the sources; the fixtures check them):

A number that stays ⊤ (a value from memory, a table, a computation) is a raw door note and the <indirect> call, exactly as in the Rust graph.

5.4 Worked example

tgkill in glibc 2.41, the call the bench lane's across-node iperf3 client died on (pthread_cancel of a stream thread blocked in send):

iperf_client_end            (libiperf.so.0)  call pthread_cancel@plt
  ─JUMP_SLOT─► pthread_cancel@@GLIBC_2.34      (libc.so.6)
    … call __pthread_kill_internal
       __pthread_kill_implementation:  mov edi, pid; mov esi, tid; mov edx, sig; mov eax, 234; syscall
                                       σ(rax) = {234} = tgkill

The site is a node libc.so.6[elf]@…::__pthread_kill_implementation#<b> with syscalls = [tgkill], the path _start → __libc_start_main → main → … → iperf_client_end → pthread_cancel → …, and the acceptance test (step 5) checks that tgkill is in iperf3's possible set.

A wrapper: musl open("f", O_RDONLY) in a static binary:

open:           mov rsi, rdi … mov edi, 2 (SYS_open); call __syscall_cp      σ(rdi) at the call = {2}
__syscall_cp:   jmp __syscall_cp_c                                           W = {rdi}   (tail call, rdi kept)
__syscall_cp_c: … mov rsi, rdi; lea rdi, [cancel]; call __syscall_cp_asm     σ(rsi) = Param(rdi): W = {rdi}
__syscall_cp_asm: mov rax, rsi; … syscall                                    σ(rax) = Param(rsi): W = {rsi}
⇒ the call site in `open` is the node, syscalls = {2 = open}

6. The join with the Rust graph

For a Rust program built with v0 symbols: a machine function whose symbol, demangled with rustc_demangle's {:#} form (hashes cut), equals the demangled symbol of a code_instances row gets that row's key in inst. That instance then has two bodies: the executor runs its MIR (the richer one) and keeps the machine body for what MIR cannot see:

• inline assembly: an asm site of a MIR body (60 sites in Heimdall) takes the numbers of the machine body's syscall instructions whose DWARF line is the asm site's line;
• the C start-up: _start, __libc_start_main and the libc's own start-up become machine bodies of the process entry, and replace the start-up list (libc_map::startup);
• foreign items: a res_kind 3 answer (a link name) goes to the machine function the link table gives for that name, and is walked; libc_map answers only when no module defines it (D2).

Reported per program: machine functions, those joined 1:1, Rust instances without a machine function (inlined, or not linked), machine functions of Rust crates without an instance (the instance pass did not reach them: a finding).

7. The executor

mimir_store::program::Program::load reads *.asm.arrow and *.asmmod.arrow next to the dump's files. Each machine function that is not joined to a Rust instance becomes an instance of its own (key = its fn key, symbol = its ELF symbol, body = a machine body). The executor's build(i) turns a machine body into the same Blk values it builds from MIR: successors from succ, an effect per site (a call of an instance, a boundary site from a syscall instruction or a wrapper call, a widened indirect call, a noreturn). Reach, values (the machine sites carry their own sets from §5), the order relation (§5.3 of exec-graph.md) and the entries run unchanged. New entries: the program's e_entry (process), the loader's e_entry (kind loader: what ld.so does before the program), .init_array (kind init), .fini_array and atexit targets (kind exit), pthread_create's start argument (kind thread).

exec.nodes for a machine site: instance = the fn key (or the joined instance key), block = the machine block, file/line from DWARF (else the module and the offset in file, line 0), callee = syscall or the wrapper's name, symbol = the ELF symbol. No column is added; the schema of exec.nodes / exec.edges / exec.marks is unchanged. The possible set fills modules (one per loaded module with its reached functions), unnamed (constant numbers the table does not name), missing_libs, unresolved_imports, dlopen, indirect_sites.

8. Static and dynamic

9. Limits, said plainly

• Self-modifying code and JIT (a JavaScript or Lua JIT, a wasm compiler at run time): the generated code is not in any module. The graph does not see it. A module that maps memory writable and executable is marked.
• dlopen: a module loaded at run time is not in the graph unless it is named. glibc itself dlopens: NSS (getpwnam → libnss_*.so), iconv (gconv modules), libgcc_s for unwinding in pthread_cancel. The flag dlopen is set and the possible set says it; a list of modules to add can be given (--dlopen <lib>), as B-Side asks for it.
• Obfuscation and hand-written computed jumps: a jump the patterns do not recover is widened to the function (counted); a call is widened to the address-taken set (counted, direct = false).
• Memory values: the value pass follows registers and stack slots only; a number loaded from a table or a struct is ⊤ (a raw door note). Stack slots are assumed not written through other pointers.
• Signal handlers installed through a struct (sigaction): the handler is in the address-taken set, not an entry of its own yet.
• Non-local control flow: longjmp and unwinding. Landing pads from .gcc_except_table are not edges in the first version: the order across an exception is incomplete (the possible set is not affected: the landing pad's function is reached by the call that holds it).
• vDSO: clock_gettime and friends may answer without a system call; the libc's fallback syscall is in the code and is counted (the same note as the cross-check's vdso).
• Kernel ABI: int 0x80 in 64-bit code uses the 32-bit table: noted, <indirect>.

10. Build order (each step RED before GREEN)

1. x86-64, static musl: functions, blocks, direct calls, syscall sites with constant numbers, musl's wrappers. Fixtures: a C program and a Rust program built -static against musl with a known set of system calls; the test records a real run with ptrace (the recorder of mimir-exec/tests/common) and checks: every call of the run is in the possible set, and the set holds no call outside the program's code.
2. dynamic glibc: PLT/GOT/IFUNC, the module set, libc.so.6 and its wrappers (__syscall_cancel). Fixture: the same C program, dynamic.
3. join: a Rust fixture with v0 symbols; count the 1:1 matches.
4. the executor: machine bodies in Program and build; the fixtures' order graphs against the recorded runs (every neighbour pair allowed).
5. real programs: iperf3, busybox, nginx from the bench's pinned images (tunnr scripts/ovn-bench/pods.toml: iperf3 sha256:d8767f28…, busybox 1.37@sha256:66a6306d…, nginx 1.27.4-alpine@sha256:4ff102c5…), and Heimdall's heimdall. Acceptance: tgkill is in iperf3's possible set; every call of the bench's probe evidence (pod-iperf3.json) is in it.
6. the cross-check: dwarves-tune-graph --graph <possible.json> --profile <probe.json> on iperf3: a test in dwarves on the committed output.
7. docs: binary-graph.md as built, linked from the Mímir README.
8. aarch64: svc #0 / x8, adrp+ldr+br x17 PLT stubs, the aarch64 jump-table forms; the same fixtures cross-compiled.

11. Measured, to be reported

Per module: functions (by bound source), blocks, sites by kind, jump tables recovered and widened, indirect calls exact / via parameter / widened, syscall sites with constant / parameter / unknown numbers; time and peak RSS. Per program: modules, reached functions, possible calls (direct / widened), the probe's calls not in the set (must be 0), the set's calls the probe never saw.