nordisk/nornir

Binary to graph: mimir-bin

nornir-mimir-bin (library mimir_bin, crate crates/mimir-bin) is Mímir's binary graph builder. It reads linked ELF programs, shared libraries, relocatable ELF objects and static archives without executing them, and writes functions, basic blocks, control flow, calls and unresolved sites as Arrow tables. The library and its command line (mimir-bin, feature cli; Heimdall's heimdall graph bin / graph show call the same code) are implemented for little-endian x86_64 and AArch64.

It was written in Heimdall (crates/heimdall-bingraph, by Andreas Persson, then the bingraph/clean round) and moved here on 2026-11-08 with its history: nornir is the home of every graph builder. Heimdall uses the release on crates.io.

The implementation includes symbol, unwind and DWARF discovery; init/fini roots; PLT/GOT imports and symbol versions; bounded x86 and AArch64 jump tables; constant IFUNC return sets; dependency traversal; and exact linker-symbol matching with source instances. Unresolved control flow remains visible. A successful analysis is not proof of complete call or syscall coverage.

Status: experimental. bin, show and stats of a bin dir are this library's (mimir_bin::cli); graph src, graph stats of a graph src dir and graph check are heimdall-cli's own (Heimdall CLI.md). graph src runs Mímir's driver (cargo-mimir-dump 0.2.3 from crates.io, under its nightly-2026-10-05) and executor (mimir-exec, from nornir-mimir-exec on crates.io) and keeps their exec tables and possible sets.

The node, edge, source, assembly and unresolved-site tables all come from nornir-mimir-schema (crates/mimir-schema, 0.2.2 on crates.io); the assembly tables are its code_asm module (code_asm, bin_unresolved, mimir.asm.version = 1). nornir's binary layer (nornir-mimir-binary 0.2.0) calls this library for an artifact and its libraries, the lake keeps the blocks (code_asm_events, nornir-mimir-ingest 0.2.0) and the viewer reads them (Graph.Get with asm:<repo>:<function>); the executor does not read them yet. See the validation record for tests and remaining checks.

Commands

heimdall graph src <cargo workspace> [--bin <name>]... --out <dir> [--tools <dir>]
                   [--build] [--target-dir <dir>]
heimdall graph bin <ELF> --out <new-dir> [--arch detect|x86_64|aarch64]
                   [--libs <dir>]... [--follow-needed]
                   [--with-source <source-dump>] [--max-instructions <N>]
heimdall graph show <dir> [--function <name|0xaddr>]
heimdall graph stats <dir>

• graph src wraps Mímir's driver (cargo-mimir-dump, on crates.io: pass 1, --exec and --std) and executor (mimir-exec) and writes the source graph: per program <program>.exec.{nodes,edges,marks}.arrow and <program>.possible.json in --out, the dumps under <out>/mimir/. It checks every tool and the driver's nightly before anything runs and names what is missing with its install line. All graph verbs share the exit-code table below.
• Both write the same format: Mímir's graph tables (nodes, edges, and per-function blocks with their successors). The lake, the room, the executor and the viewer read either one, or both together.
• graph bin only reads input files. --with-source merges an existing source dump (a directory of the driver's .arrow tables), preserving MIR and instance tables alongside machine-code bodies. show accepts both binary reports and source Arrow dumps; stats reads a graph bin dir (it has report.json) with this library and a graph src dir with heimdall-cli.

For a graph src --out src-out result, pass src-out/mimir/src to --with-source, not src-out (executor tables) or src-out/mimir (a parent directory). The bridge reads .arrow files directly in the supplied directory; it does not recurse. To also include the instance-pass or standard-library tables, collect the desired driver .arrow files into one flat directory without overwriting shards.

Dump and binary timestamps need not agree. Matching requires compatible linker identities; Rust's crate disambiguator may differ between cargo check and cargo build, or between build configurations. graph src --build opts into the driver's build mode for both application passes, leaving the default check-only behavior unchanged. This produces binaries alongside their dumps:

heimdall graph src ./program --build --out ./src-out --target-dir ./target/source
heimdall graph bin ./target/source/mimir/debug/program \
  --with-source ./src-out/mimir/src --out ./merged

The checked-in tests/fixtures/real-source fixture was generated with cargo-mimir-dump 0.2.3, nornir-mimir-exec 0.1.0 and nightly-2026-10-05 (rustc 28221559263a3976766cf305940e80e30cf9ba8a). It contains the small bingraph-real program, its built ELF and unmodified application driver tables. Its regression verifies one source_function node with provenance both, its MIR and assembly bodies, and no leftover binary-only identity for that function. The real CLI run wrote the graph with explicit refusals in unrelated standard library code; it is not evidence of complete control-flow recovery.

The source driver does not yet call this library automatically when it encounters binary dependencies. That part of the original integration design remains open; --with-source is the explicit merge path implemented here.

Exit status for every verb: 0 success; 1 rejected input, graph-check failure or graph written with explicit refusals; 2 usage; 3 host, tool or I/O failure. See Heimdall's shared table. Ordinary unresolved indirect calls or jumps do not themselves cause status 1. Inspect coverage and unresolved reasons even when status is 0. Output directories must be new; existing data is never overwritten. Files are deterministic Arrow IPC with zstd; report.json is the last file written and contains diagnostics and coverage.

Heimdall's CLI targets Linux. The crate's own frontend (mimir-bin) also builds on macOS and analyzes Linux ELF files there:

cargo install --locked nornir-mimir-bin --features cli     # or, in nornir: cargo run -p nornir-mimir-bin --features cli --
mimir-bin bin ./program.elf --out ./graph
mimir-bin stats ./graph
mimir-bin show ./graph --function _start
cargo test -p nornir-mimir-bin --features cli

Library

nornir-mimir-bin is licensed MIT OR Apache-2.0. It returns Arrow record batches; it does not execute the input, invoke a process or write output unless the caller requests write.

use mimir_bin::{graph_of, Arch, BinOpts};
use std::path::Path;

let opts = BinOpts {
    arch: Arch::Detect,
    libs: vec!["/path/to/sysroot/usr/lib/x86_64-linux-gnu".into()],
    follow_needed: true,
    ..Default::default()
};
let graph = graph_of(Path::new("/path/to/program.elf"), &opts)?;
graph.write(Path::new("/path/to/new-graph-directory"))?;

graph_bytes(bytes, opts) analyzes one module without resolving filesystem dependencies, or all members of an archive. merge_source(graph, source_dir) joins a source dump in memory. MimirBatches carries code_nodes, code_edges, code_asm, unresolved, retained source_tables, and a diagnostic report. Arrow buffers are reference counted; consumers can share batches without serializing them.

Source bridging accepts mimir.schema 8 and later additive versions: known fields must retain their names and types, but field order and producer metadata may differ. Missing, duplicate or incompatible required fields are rejected. Merged nodes and edges use the published schema; original source tables with additional columns or metadata are retained as source-*.arrow without loss.

Downstream Cargo workspaces use the published nornir-mimir-schema 0.2.2; no vendored schema or workspace patch is required.

Analysis

1. Validate linked ELF architecture, section headers, and executable PT_LOAD mappings. Refuse writable/compressed executable sections and known packed section markers. Module identities are SHA-256 hashes of complete input files.
2. Seed functions from symbols, exports, entry point, init/fini metadata, .eh_frame FDE ranges and DWARF subprogram ranges. Retain range evidence, linker/demangled names, source locations, build IDs and sonames.
3. Recursively decode reachable instructions. Direct calls discover more functions; branch targets split blocks. Transfers to other known function starts become tail calls. Overlapping instructions, undecodable targets, invalid function ranges and exhausted budgets are reported as refusals.
4. Recover loader-bound PLT/GOT calls, including versioned imports. Ordinary relocation-backed pointer variables retain candidates and remain unresolved; their initial values are not assumed to survive runtime writes. Recover x86 absolute-pointer and PIC relative-offset jump tables only with a full-width index bound, read-only mapped table bytes, and a guard that dominates every known entry. Revalidate recovered tables after discovery reaches its final instruction/entry set. AArch64 recovers signed relative-offset tables from an adjacent full-width CMP/B.HI guard, ADRP/ADD (or relaxed NOP/ADR) table address, LDRSW, ADD and BR sequence. Index, table and target registers must be distinct; no entry or edge may bypass the guard; the table must be immutable. Its import tracing uses bounded ADRP/LDR analysis respecting independent function and call entries. Unrecognized forms remain unresolved.
5. Explore IFUNC resolver return values for supported constant-producing instructions. Unknown writes, memory-base writeback and calls invalidate values. Keep resolver calls and known implementation candidates; report unknown return sets.
6. With --follow-needed, visit DT_NEEDED modules breadth first, deduplicated by hash. Resolve imports to the first eligible export in that fixed load order, respecting versions; absent weak definitions are optional. Search explicit --libs directories, expanded $ORIGIN RPATH/RUNPATH entries, and the referring directory, then conventional architecture-specific system paths on Linux. Missing/incompatible libraries and missing required exports cause refusals.
7. With source input, match only unique exact linker symbols from code_symbols, source node linkage, or Rust instance hashes in code_instances, backed by an owning source definition. One matched node retains source identity and columns with provenance = both, both bodies, and match evidence. Owning definitions take precedence over reference stubs. Ambiguous or merely similar names are not merged. DWARF assists discovery; it is not an independent source-identity proof.

The default decode budget is 1,000,000 instructions per module; dependency traversal is limited to 256 distinct modules. Neither limit silently truncates a successful graph.

Output contract

Basic blocks live in code_asm, not as graph nodes connected through code_edges. CFG successors are local block IDs in code_asm; they are not dangling CFG_SUCC edges in code_edges. Addresses are u64, block IDs and counts u32, terminators u8, and successors are Arrow lists. Candidate lists use an Arrow dictionary shared across sites; the report stores address-taken evidence once per module rather than repeating it for each unresolved site. Binary-only function IDs are bin:<module-sha256>@<hex-address>.

Relocatable objects use section-relative addresses: (section index + 1) << 32 plus the section offset, not final load addresses. Function symbols and global assembly labels in executable sections seed discovery. x86_64 PC32/PLT32 and AArch64 CALL26/JUMP26 control-flow relocations identify in-object calls or external import declarations. Unhandled code relocations are explicit refusals; their placeholder operands never become asserted call targets. Object analysis does not run a linker or predict symbol interposition in a future linked image.

An archive has a container module and one contained module per member. Member identities include the archive hash and member index as well as the member hash, so even identical members remain distinct. The diagnostic report retains member names and raw member hashes. Known CRT object names (crt1.o, Scrt1.o, rcrt1.o, crti.o, crtn.o, and the usual crtbegin/crtend variants) have origin lang; ordinary root objects and archive members are local. Followed DT_NEEDED libraries are library, regardless of entry point.

The object regression fixtures include both architectures and tests/fixtures/libblake3-build.a, copied from the blake3 1.8.7 build script's libblake3_sse2_sse41_avx2_assembly.a under target/debug/build/*/out. It contains upstream BLAKE3 assembly, used under its Apache-2.0 option (upstream source); the crate's LICENSE-APACHE supplies that license. The other object fixtures are reproduced by tests/fixtures/build.sh.

The assembly tables leave the source schemas unchanged, carry mimir.schema = 8, and version assembly independently with mimir.asm.version = 1. Their exact fields and terminator codes are mimir_schema::code_asm in nornir-mimir-schema 0.2.2 (nornir crates/mimir-schema/src/code_asm.rs). Existing Nornir consumer releases do not read the assembly tables yet.

Limits

• Supported inputs are 64-bit little-endian x86_64/AArch64 ELF executables, shared libraries and relocatable .o files, plus regular .a archives of such objects. PE, Mach-O, 32-bit targets, thin archives, mixed-architecture archives and non-object members are rejected. Archives are bounded to 256 members. Object sections must be smaller than 4 GiB.
• Object discovery currently uses symbols, not relocated DWARF/unwind data. Object jump tables, IFUNC implementation sets and data relocations are not recovered; external calls remain imports, including across archive members. Analyze the linked artifact for final addresses, bindings and these metadata recovery paths. CRT classification requires an object/member filename; linked code without object-origin evidence is not guessed to be CRT code.
• Indirect calls/jumps retain address-taken candidates, not asserted edges. Candidates are evidence from the analyzed image, not a proven exhaustive upper bound. Unknown jump tables and IFUNC return sets remain unresolved.
• Coverage counts decoded bytes against all executable section bytes, including refused sections. Padding can reduce coverage; stripped code without symbols or unwind/debug ranges can hide entire indirectly reached functions.
• Dynamic loading, JIT, self-modifying code and arbitrary packing/obfuscation cannot be recovered statically. Known packed markers and writable code are refused; detection of all packing is not claimed.
• Library search is a deterministic fixed-image policy, not a complete emulator of the Linux loader. It does not reproduce LD_PRELOAD, namespaces, audit modules, ld.so.cache, hardware-capability directory selection or runtime dlopen.
• Jump-table recovery covers the documented x86 and AArch64 patterns. Other table forms and narrow-register guards remain unresolved; proving zero-extension for narrower guards is not implemented. IFUNC analysis and register tracing deliberately support bounded patterns rather than general symbolic execution.

Squashing functions, extracting system calls, reducing the graph and enforcing sandbox policies are later stages, outside this analyzer.

Related designs: exec graph, binary graph plan, Heimdall graph filter.