nordisk/heimdall

Part 1 of 5 of docs/v2/graph-filter.md (generated; edit the source)

The graph filter (v2)

Heimdall is a defensive sandbox. This is a design for review. Only section 2 is built. The document changes no code. It replaces docs/plan/pledge-budgets.md and docs/plan/probe-graph-tooling.md, which are deleted; their history is in git (last present at 9c4659d).

Every file:line is from these commits. Paths are repo-relative.

1. The core idea

There is one filter model and one place where it is checked.

decide(position, call) → (allow, next position) | deny

Every system call of the program is checked at the kernel's system-call entry, through seccomp. That holds for both modes. The only difference between the modes is state.

• Static mode is the model with ONE position that never changes. A decision that depends on nothing but the call compiles fully into a stateless BPF program. This is what Heimdall 0.4.2 does.
• Graph mode is the model with a position per thread: where the thread is in the graph of the program. More exactly it is a stack of positions per thread, because a signal handler that runs on the thread gets its own position on top (section 3). The static filter stays on as the floor, and a small program in the kernel follows each thread through the graph.

The mode is chosen per workload at start and never changes during a run.

Both modes are made in the same three steps: (1) the profiler, (2) the static analysis, (3) the filter. In static mode the profiler is the source and the analysis is the check. In graph mode the analysis is the source and the profiler is the check.

Three parts at the one check point

Graph mode has three parts, side by side at the system-call entry:

1. The seccomp floor (classic BPF, always on). It is static mode's filter. It answers never → kill, always → ALLOW, brokered → USER_NOTIF. Seccomp stays the gatekeeper that directs traffic: only seccomp can hand a call to user space.
2. The graph follower (new; eBPF in the kernel). It holds each thread's stack of positions and runs decide for every call the floor let through. "Allowed by the floor" and "position checked" are separate things: an always call is still followed.
3. The supervisor (user space). It is the broker for the brokered set: it inspects the call, opens the file or socket itself and injects the descriptor. It also signs the record. It holds no positions.

This was the open question of the first version of this document. It is decided; section 8 gives the reasons, the invariants, and what a host must have. Where a host cannot load eBPF, the workload runs in static mode.

Words and sets

Σ         call classes: a syscall plus conditions on its register arguments, (arg & mask) == value
I         the kernel-implied base set: restart_syscall, rt_sigreturn, exit, exit_group
M ⊆ Σ     the measured set: the classes the profiler saw in at least one run
G ⊆ Σ     the possible set: the classes some path of the code can reach
B         boundary sites: the places where the program's code calls C or the kernel
λ(s) ⊆ Σ  the calls a site s can make
First(e)  ⊆ B: the sites that can make the first call of entry e (main, a thread, a handler)
Next      ⊆ B × B: "after site s, the next call of the same thread can come from site s'"

The base set, in both modes

decide allows I at every position, and no profile or graph can remove it. Every BPF program Heimdall builds allows it first, right after the arch check (crates/heimdall-seccomp/src/bpf.rs:188-198, base.rs:34). The reason, in three lines:

1. On 2026-11-06 gunnar.rs crash-looped. Its allowlist lacked restart_syscall.
2. io_uring task_work interrupted a timed futex wait. The kernel resumed the wait through restart_syscall, the filter answered SIGSYS, and PID 1 died (base.rs:15-19).
3. No code names these four calls, and a quiet probe run never makes them. So neither a measurement nor a code graph can find them; they must be a rule.

Allowing them widens nothing: restart_syscall resumes a call the filter already let through, rt_sigreturn restores registers, and the other two end the task (base.rs:19-22).

2. Static mode: what exists today (0.4.2)

Step 1. The profiler measures (heimdall-probe)

• Learning mode. The program runs under a filter whose default is SECCOMP_RET_USER_NOTIF (crates/heimdall-probe/src/learn.rs:110-114). One probe thread records each call and answers CONTINUE (learn.rs:140-169). clone3 gets ENOSYS, so libc falls back to clone; the base set is allowed in BPF and never seen (facts.rs:124-131).
• Argument facts. A call is its name plus the register arguments of eleven calls: socket, socketpair, open, openat, ioctl, mmap, mprotect, pkey_mprotect, clone, prctl, fcntl (facts.rs:36-103).
• What is kept. Each distinct call with the runs that made it: no counts, no order, no thread (observe.rs:50-60). The file is <arch>-<libc>.probe.json.
• The corpus. workload.toml names the runs and marks the error paths (workload.rs:82-128). A program that runs elsewhere is learned live (probe-exec, probe-container; crates/heimdall-cli/src/profile.rs:39-51).
• Merge and minimise. The runs are united (observe.rs:81-100), and minimise::generate writes one rule per syscall (minimise.rs:99-240): a mask of the bits seen for flags, exact tuples for other facts, a bare allow above 16 tuples. Writable-and-executable mappings are left out and reported.
• Review and codegen. A person reviews the runs, the calls seen only on error paths ("near misses") and the bare allows (minimise.rs:45-66), and commits the generated .rs, .json and .oci.json. They are the same bytes for the same input (codegen.rs:4-8).
• Drift check. heimdall profile check probes again. A call outside the checked-in profile fails, naming the call and the runs that made it (check.rs:41-70).

The filter is generated from this measurement. It holds only syscalls that were measured. At the argument level it is slightly wider than M, because of the masks and the bare allows.

Step 2. The static analysis is cross-checked against it

• Mímir walks the code graph of the program and its dependencies to the syscall boundary. mimir-room <lake> possible writes graph.json, format mimir.possible-syscalls/1 (nornir crates/mimir-room/src/possible.rs:46, 124). It is a set: one entry per syscall name with one example path (edda crates/nordisk-kernel-evidence/src/graph.rs:68-91). An edge the compiler could not resolve is widened to every target, never dropped (possible.rs:22-27). So G is an upper bound. It has no order and no arguments.
• dwarves compares the two sets. cross_check (dwarves crates/dwarves-tune-graph/src/xcheck.rs:39-114) gives four lists:

confirmed  = M ∩ G                      measured and possible                 (xcheck.rs:46-47)
gap        = M \ G                      measured, not in the graph: a graph gap to review   (48-53)
untested   = G \ M                      possible, no run made it: a test to add             (69-84)
near miss  = { c ∈ M : every run that made c is an error-path run }                         (55-67)

• The report says guides_only: true (xcheck.rs:111). The graph never adds a rule to a filter. It guides review and tests.

Step 3. The fixed filter

• A job or service names a generated profile, pinned by the sha256 of its OCI JSON (crates/heimdall-core/src/types.rs:263, 345-354). genprof::resolve refuses a missing profile, another digest and another arch (crates/heimdall-container/src/genprof.rs:161-189).
• Inside the job, right before the program starts, the executor installs it with TSYNC and starts the program with execveat (crates/heimdall-container/src/shim.rs:344-394, crates/heimdall-seccomp/src/launch.rs:679-691, 723-724). The default action is KILL_PROCESS.
• It sits on top of two other filters, and the kernel takes the strictest answer: the fixed profile that youki compiles from OCI JSON (crates/heimdall-container/src/profile.rs:220), and the broker filter (crates/heimdall-broker/src/filter.rs:64-101). A wasm job's host worker gets its generated profile the same way (crates/heimdall-cli/src/worker.rs:155-178).
• The signed result and the signed start say Protection::Generated { profile_digest } (types.rs:757-765, crates/heimdall-core/src/service.rs:250-266).

In the model, with F = minimise(M):

positions: one, q₀          decide(q₀, c) = (allow, q₀)  if c ∈ I ∪ F
                                            deny          otherwise          (KILL_PROCESS)

Dataflow, static mode

 workload.toml runs ─► (1) PROFILER  learning filter, USER_NOTIF, CONTINUE
                             │ M: call → runs          <arch>-<libc>.probe.json
                             ▼
                       merge ─► minimise ─► review (a person) ─► codegen
                             │                                      │
 code ─► Mímir ─► graph.json (G)                                    ▼
              │              │                     profile .rs / .json / .oci.json, digest
              ▼              ▼                                      │
        (2) CROSS-CHECK  dwarves-tune-graph                         ▼
            confirmed / gap / untested / near miss        (3) FIXED FILTER  one classic-BPF
            guides review and tests; adds no rule             program: arch, x32, I, then F;
                                                              default KILL_PROCESS; whole run
 drift check (CI): probe again; a call outside F fails,              │
 naming the call and the test                                        ▼
                                              signed result / start: Generated { profile_digest }

What one position cannot say: order, counts and threads. A call needed once at start stays allowed for the whole run, for every thread, any number of times.

What else uses this evidence. Our kernel builder (Build Thing, in edda) reads the same two files to decide which kernel options a product's kernel must keep (edda crates/nornir-build-thing/src/syscall_join.rs:615). It is a separate tool, not part of the filter, and a user of the filter does not need it.

Next: part 2 of 5, raw: https://www.gunnar.rs/nordisk/heimdall/raw/docs/v2/graph-filter-parts/part-2.md