nordisk/nornir

Binary graph validation

Moved (2026-11-08). This record was written in Heimdall, where the crate was nordisk-heimdall-bingraph in crates/heimdall-bingraph. It is now nornir's nornir-mimir-bin (library mimir_bin, binary mimir-bin) in crates/mimir-bin; the commands below use the new names, the results are as recorded under the old ones.

Linux follow-up (2026-11-08)

The original record below is historical. The follow-up adds a checked-in matrix of C and Rust programs for x86_64/AArch64, dynamically linked glibc and statically linked musl. None of the input binaries is executed during analysis.

The matrix is built by tests/fixtures/build.sh with BUILD_MATRIX_ONLY=1 inside crates/mimir-bin/tests/fixtures/Containerfile: Rust 1.85.0, Debian bookworm cross GCC, musl-tools, and a checksum-verified musl 1.2.5 build for AArch64. Run container builds with one stage/job and capped resources:

podman build --jobs 1 --cpu-quota 300000 --memory 16g \
  -t localhost/bingraph-fixtures \
  -f crates/mimir-bin/tests/fixtures/Containerfile \
  crates/mimir-bin/tests/fixtures
podman run --rm --cpus 3 --memory 16g --pids-limit=65536 \
  --network none --userns=keep-id -v "$PWD":/src:rw localhost/bingraph-fixtures

On the shared host these commands used separate --root, --runroot and --tmpdir locations under /home/rickard/lanes/bingraph/podman, not shared container storage. All build/test commands ran at nice 10 in a 3-CPU/16-GiB scope with CARGO_BUILD_JOBS=3 and RUST_TEST_THREADS=3.

The matrix regression checks architecture, recovered application functions, decoded bytes, dynamic libc requirements and static-musl dependency absence. AArch64 relative-table fixtures cover both ADRP/ADD and linker-relaxed NOP/ADR; narrow comparisons, an independent guard entry and writable tables are rejected. The existing final-discovery revalidation also applies to the AArch64 recognizer.

cargo +1.85.0 check -p nornir-mimir-bin --locked --offline passed inside that Rust 1.85.0 container, with the current workspace lockfile. The portable fuzz workspace at crates/mimir-bin/fuzz avoids building the unrelated sandbox while fuzzing the ELF/object/archive parser:

CARGO_BUILD_JOBS=3 RUST_TEST_THREADS=3 nice -n 10 cargo +nightly-2026-10-05 fuzz run \
  --fuzz-dir crates/mimir-bin/fuzz --sanitizer address binary_graph \
  /path/to/corpus -- -runs=2000 -max_len=65536 -rss_limit_mb=8192 -timeout=10

With cargo-fuzz 0.13.1 and AddressSanitizer, 2,000 iterations completed without a crash (coverage 8,124, feature count 19,864, peak reported RSS 476 MB). Seeds included linked ELF, both object architectures, an AArch64 table and the real BLAKE3 archive. This bounded smoke run is not exhaustive fuzz coverage.

Original validation

Validated on macOS ARM with Rust 1.99.1 (58cf8f9c3, 2026-10-13), on 2026-11-07. This records the portable analyzer's checks, not a Linux workspace release certification.

Automated checks

• cargo test -p nornir-mimir-bin --features cli --locked: 36 tests passed (2 unit, 34 integration), including three property tests.
• cargo clippy -p nornir-mimir-bin --all-targets --features cli --locked -- -D warnings: passed.
• cargo fmt --all -- --check and git diff --check: passed.
• The optimized portable executable was built with cargo build -p nornir-mimir-bin --features cli --release --locked; its AArch64 dependency-linking fixture completed with exit 0 and readable show/stats output.
• The actual fuzz/fuzz_targets/binary_graph.rs compiled in a temporary workspace containing only the portable library and libfuzzer-sys. A 2,000-run smoke test with three checked-in ELF seeds completed without a crash. This stable build had no coverage or sanitizer instrumentation; it is not a substitute for the nightly cargo-fuzz run in Linux CI.

The tests cover recursive function/call discovery, backward edges, block splits, tail calls, overlapping instructions, invalid/packed/writable input, instruction budgets, deterministic IPC, CLI exit statuses, source-driver argument forwarding, source dump inspection, and exact Rust-instance matching without ambiguous joins. Real compiled x86_64 and AArch64 fixtures exercise DWARF, stripped unwind discovery, constructors, PLT/GOT calls, symbol versions, dependency resolution, address-taken candidates and IFUNCs. Regression tests check IFUNC register clobbers, referential integrity of graph edges, and compact candidate-set storage through an IPC round trip.

The compact-storage regression represents 10,000 sites sharing 10,000 candidates. It stays below 5 MB of Arrow array memory; repeating the candidate strings per site would exceed Arrow's 32-bit string-offset limit. Candidate sets are dictionary values, and reports retain address-taken evidence once per module.

Review regressions

The six review findings are covered by regressions: mutable function pointers, full-width jump-table bounds, AArch64 import-slice entries, AArch64 IFUNC memory writeback, code_symbols matching, and owning-source-definition precedence. Related tests cover imported pointer relocations, writable tables, entering a guard without its compare, and entries discovered after initial table recovery. The original regressions were observed failing before the fixes. Source merge checks also assert that binary metadata does not replace the source node's crate, version, name or nullable columns. The rebuilt release executable was also checked against the original review binaries: false pointer/import/IFUNC targets are absent, the affected sites remain unresolved, and the independent source-bridge reproduction retains the owning definition and source identity fields.

Reproducing fixtures

Fixtures are built from the adjacent C, Rust and assembly sources. No target binary is executed. The C fixtures are freestanding, avoiding a host libc requirement; real musl/glibc programs are checked separately below.

CLANG=clang RUST_LLD=/path/to/rust-lld LLVM_STRIP=/path/to/llvm-strip \
  RUSTC=rustc sh crates/mimir-bin/tests/fixtures/build.sh

This requires Clang cross compilation for x86_64/AArch64 ELF, LLVM's ELF linker and stripper, and Rust's x86_64-unknown-linux-gnu standard library. The recorded fixtures used Apple Clang 21.0.0 and Rust's bundled LLVM linker. Binaries are included so normal tests do not need these cross-build tools.

Real-program corpus

Only package files were downloaded and extracted; no package scripts, loaders or target programs were run. Measurements aggregate the root and all discovered DT_NEEDED dependencies. Coverage is decoded bytes divided by executable section bytes, not proof of complete control flow. All three runs wrote graphs and exited 2, retaining their explicit refusals. These measurements were refreshed after the review fixes; the stricter table proofs deliberately leave more sites unresolved.

Unresolved/refused site counts by reason:

• busybox: direct-call-outside-executable-sections 2, indirect-jump 3.
• nginx: branch-outside-function-range 179, indirect-call 2,328, indirect-jump 864.
• iperf: branch-outside-function-range 3,616, ifunc-return-set 94, indirect-call 2,335, indirect-jump 1,041, overlapping-instruction 8, target-outside-executable-sections 3, undecoded-target 8, unsupported-control-flow 3.

Both dependency closures resolved all declared required imports. The refusals above concern recovered machine control flow, not missing libraries. BusyBox has neither the symbols nor usable unwind ranges needed to discover most indirectly reached functions. Its two out-of-section calls target address zero. Many library range refusals are branches into shared/cold code outside the current function range; these transfers are not silently treated as complete CFGs.

Root input SHA-256 values:

a477b4c1b332bb9b5d926dbfc75e0efc9b53193708d8be83295bfbb376fa9839  busybox
b7936e0228bbfb89aaaa77b1e8d629b0c402d4f72c296a4b0cd4975bd1f7d257  nginx
99f9d5671165caf4e0bbf1ad37d652b0b74b73cee6cf20635398b1eb505c3d30  iperf

Inputs came from Alpine v3.22 x86_64 (BusyBox 1.37.0-r20; nginx 1.28.3-r7; musl 1.2.5-r13; pcre2 10.46-r1; OpenSSL 3.5.9-r0; zlib 1.4-r0) and Debian amd64 (iperf3/libiperf 3.18-2+deb13u2; glibc 2.41-12+deb13u4; OpenSSL 3.5.9-1~deb13u1; libsctp 1.0.21+dfsg-1; zlib 1.3.dfsg+really1.3.1-1+deb13u1; zstd 1.5.7+dfsg-1). These external binaries are not added to this repository.

Reproduce against extracted images using:

mimir-bin bin <alpine>/bin/busybox.static --out <new-busybox-graph>
mimir-bin bin <alpine>/usr/sbin/nginx --follow-needed \
  --libs <alpine>/lib --libs <alpine>/usr/lib --out <new-nginx-graph>
mimir-bin bin <debian>/usr/bin/iperf3 --follow-needed \
  --libs <debian>/usr/lib/x86_64-linux-gnu --out <new-iperf-graph>
mimir-bin stats <graph-dir>

Checks that remain outside this validation

• scripts/ci.sh reaches existing Linux-only seccomp code and fails to compile on macOS (for example libc::SYS_seccomp). The Docker socket was inaccessible in this session. Full workspace, kernel/container tests and cargo-deny remain Linux CI release gates.
• The actual cargo-mimir-dump compiler pass was not installed/run. The bridge tests use a real compiled Rust binary plus schema-generated source/MIR/instance tables; the CLI wrapper is tested with a controlled driver executable. End-to-end testing against the real driver and its supported nightly is still required.
• The assembly schema was a local proposal when this record was written. It is now code_asm in nornir-mimir-schema 0.2.2 on crates.io (the same file, unchanged); consumer ingestion in Nornir is still not implemented.
• Full nightly sanitizer/coverage-guided fuzzing and MSRV testing were not run.

Remaining design scope

Passing Linux CI will not by itself complete the original integration design. The source driver still needs to invoke binary analysis automatically for binary dependencies, and Nornir consumers need to ingest the agreed assembly schema. Source matching currently uses linker identities; independent DWARF identity matching is not implemented. Object/archive inputs from the original library examples are rejected, while its scope table specifies linked ELF inputs; that scope discrepancy needs agreement rather than silently dropping those examples.

The requested fixture matrix is also broader than the current one: the checked-in C fixtures are freestanding for both architectures, the Rust fixture is x86_64, and the real musl/glibc corpus is x86_64. Static-musl and dynamic-glibc C/Rust fixtures across both architectures, plus a run with the real Mímir driver, remain to be added.