nordisk/heimdall

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).

For a reader with a size limit: the same text is in parts of under 14 KB each, starting at graph-filter-parts/part-1.md (raw: https://www.gunnar.rs/nordisk/heimdall/raw/docs/v2/graph-filter-parts/part-1.md). They are generated from this file by docs/v2/split-parts.sh. This file is the one source.

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.

3. Graph mode (new)

Step 2. The static analysis gives the graph

The graph is Mímir's lossless graph, and this design assumes it exists. It is defined in the graph plan (nornir docs/v2/mimir/exec-graph-plan.md at 03662cb4). This design uses:

• Nodes: the boundary sites B, one per call of a foreign function or raw syscall, per instance of the code (plan §4.1, §8). λ(s) comes from the libc map. Arguments are given where the code fixes them, for the same eleven calls the profiler records (plan §4.4).
• Edges: Next, with First(e) per entry (plan §4.3; files exec.nodes, exec.edges).
• Entries: main, each thread and task body, each signal handler (plan §4.5). The async executor is ordinary code in the graph, and a coroutine keeps its yield points (plan D2). So where two futures can run in either order, Next holds both orders.
• The projection { λ(s) : s reached } has the shape of today's graph.json (plan §4.6). Static mode's step 2 reads it unchanged. One graph serves both modes.

"1:1 with the code" means the Rust code. A C function is one node whose λ is a set (plan D4); section 10 says what follows from that.

Step 1. The profiler checks the graph

The profiler runs the program as today and also records, per thread, which call follows which (section 7). A pair (a, b) means: b is the next call after a in the same thread. Base-set and vDSO calls are not seen and are in no pair. Two numbers, on nodes and on pairs:

Obs  = classes observed          Static  = ⋃ λ(s) over reached sites
Obs₂ = pairs observed            Static₂ = { (a, b) : ∃ (s, s') ∈ Next, a ∈ λ(s), b ∈ λ(s') }
                                           ∪ { (a, b) : a, b ∈ λ(s), s can make several calls }

soundness   S  = |Obs  ∩ Static|  / |Obs|       S₂ = |Obs₂ ∩ Static₂| / |Obs₂|     must be 1.0
precision   P  = |Obs  ∩ Static|  / |Static|    P₂ = |Obs₂ ∩ Static₂| / |Static₂|  rises with coverage

An empty denominator is "no data", never 1. "Before anywhere in the run" would not work as the definition of a pair: in a loop, every call comes before every other after one round.

Every difference is a finding:

The goal: the static analysis gets so good that profiling only confirms it, 100 %. S = S₂ = 1.0 is required before a graph is enforced. P and P₂ reach 1.0 only for code the runs fully cover.

Step 3. The graph filter

The three parts.

The floor is the filter of section 2: always = I ∪ F, never = everything else. The brokered set is what the broker serves today: the open calls (openat, openat2, and on x86_64 open and creat), socket, connect, bind, listen, accept, accept4, io_uring_setup, sends with MSG_FASTOPEN, and exec (crates/heimdall-broker/src/filter.rs:27-44, 64-96). Today the broker opens files and sockets itself, lets exec continue, and refuses the others (broker.rs:409-427).

The decision. A position is the set of sites the thread's last call can have come from. It is a set because the kernel side sees a call's class and not its site, and two sites can make the same call. A thread's state is a stack of positions: its own entry at the bottom, and one frame on top for each signal handler that is running on it.

frame f = (e, P, last)     an entry e, the position P on it, the class of the frame's last call
state of thread t          ⟨f₀ … f_k⟩, at most 8 frames;  f₀ = (the thread's entry, {ε}, none)
H                          the signal-handler entries of the graph

step_e(P, c) = { s' : c ∈ λ(s') ∧ ( (ε ∈ P ∧ s' ∈ First(e)) ∨ ∃ s ∈ P : (s, s') ∈ Next
                                    ∨ (s' ∈ P ∧ s' can make several calls) ) }

decide(⟨f₀ … f_k⟩, event), on the top frame f_k:
  call c ∈ I                     valid; no position moves; rt_sigreturn pops f_k when k > 0
  call c, step(P_k, c) ≠ ∅       valid; P_k := step(P_k, c), last_k := c             (next)
  call c = last_k                valid; nothing moves             (again: the self-edge s → s)
  signal delivered, handler h    h ∈ H and k < 7: push (h, {ε}, none);  otherwise invalid
  thread created                 the parent's clone is a next step to a spawn site of the graph;
                                 the child starts as ⟨(the entry that site spawns, {ε}, none)⟩
  anything else                  an INVALID STEP

allowed(stack) = I ∪ { c : decide(stack, call c) is valid }

• Every call the floor lets through is followed, the always calls too. So the order of all calls is checked, at the cost of one small program run per call and no context switch.
• Brokered calls are followed too. Seccomp ends a brokered call that the supervisor answers itself, so it never reaches the entry tracepoint. The follower steps it at the exit tracepoint, which the kernel runs for every call (section 8, kernel facts).
• Again. The kernel can restart an interrupted call: the same call enters the kernel a second time, or restart_syscall does for a timed wait. A program can also retry after EINTR. So the same call again from the same position is always valid. A restart needs no handler; a stop or io_uring task_work is enough (crates/heimdall-seccomp/src/base.rs:10).
• Signals. A handler can start between any two calls of a thread. The follower sees the kernel's signal-delivery tracepoint, which carries the handler's address, and pushes that handler's entry on top of the interrupted position. Calls inside the handler follow the handler's part of the graph. A second signal nests one more frame. rt_sigreturn pops, and the thread continues from the interrupted position, where the interrupted call may come again. restart_syscall and rt_sigreturn are base-set calls: never invalid, and they move no position, except that rt_sigreturn pops.
• The stack is bounded: 8 frames, the thread's own and 7 handlers. A ninth is an invalid step. So is a handler the graph does not have.
• Threads. A new thread's first frame is the entry the graph gives for its spawn site (the plan's spawn marks, §2.3, §4.5). The parent must be at a position with an edge to that site. A spawn the graph does not have is an invalid step.
• Async. Position is per kernel thread. A worker thread's entry is the executor's loop, and each task's poll body is a callee of it, so at a scheduling point allowed is the union over the tasks that can run. That is sound and costs precision. Task tags written by the program are not used: an attacker in the process can write them.
• Widening. Only dyn and fn-pointer call sites are widened, and only to the vtables and pointers the reached code creates (plan §3.3). A reached C function that the boundary map has no answer for is not widened to every call. It is a finding that blocks graph mode for that program, which stays in static mode.
• In the kernel, the stack lives in task-local storage (a hash map keyed by thread where a kernel lacks it), and Next in a map. eBPF cannot walk a set of sites, so the loader makes the graph deterministic first: one state id per reachable position, and a map from (state, class) to state. A graph that outgrows the map is refused at load. The loader also maps each handler's address to its entry, from the program's symbols.

Enforce and Audit are a field of the policy.

• Enforce. An invalid step kills the process (bpf_send_signal).
• Audit. An invalid step is written to a ring buffer and counted, and the call runs. Audit never returns an error to the program, because that would change its behaviour. Audit is how a new graph is tried on a real workload first.

The kill is late by at most one call. At the entry tracepoint the follower cannot stop the call. The invalid call itself runs, and the thread never returns to user space. The floor guarantees that this one call is a call the static filter allows anyway. Where an LSM hook exists for the operation (open, connect, bind, exec, mmap), the refusal comes before the call: the follower marks the thread at the entry, and the hook refuses while the mark is set.

Four properties, each a property test:

(G1) every run of the code is valid: each frame's calls follow its entry's graph (pairs ⊆ Static₂),
     while handlers start between any two calls, nest and return, and an interrupted call comes again
(G2) graph mode is never wider than static mode: the floor answers first, and allowed(stack) ⊆ I ∪ Static
(G3) the base set is never invalid, at any stack, and it moves no position (rt_sigreturn only pops)
(G4) Audit changes nothing in the program: no call fails, and no call waits for user space

What falls out of the graph.

• Phases are regions of the graph: before the entry's serving loop, the loop, after it (plan §4.5). Once the position is in the loop no path leads back, so setup calls are no longer in allowed.
• Budgets are sites outside every loop. A site on no cycle of Next that makes one call can be passed once per path, plus the same call again in place. "io_uring_setup at most N times" is the number of such sites on the longest path. A site in a setup loop can repeat while the position is in that loop, and never after.

This replaces the earlier design of the two deleted plans: named phases, a stacked filter per mark, and counted "pledge budgets", with no order inside a phase. That design was a workaround for a lossy graph that had no order. With the 1:1 graph, phases and budgets are not separate mechanisms. They fall out of following the graph.

Dataflow, graph mode

 code ─► Mímir (lossless MIR, instances) ─► mimir-exec ─► (2) THE GRAPH  exec.nodes, exec.edges
                                                               │   B, λ, First, Next; arg facts
                    ┌──────────────────────────────────────────┤
                    ▼                                          ▼
 runs ─► (1) PROFILER  per thread: pairs (a, b)        import + validate, digest
              │  Obs, Obs₂                                     │
              ▼                                                ▼
         graph check: S, P, S₂, P₂, findings ─────►  accepted only with S = S₂ = 1.0
              │ findings                                       │ loader: states, maps
              ▼                                                ▼
   analyzer fix + test  /  add a run        (3) AT THE SYSTEM-CALL ENTRY, for every call
   (back to Mímir or to the runs)
                                             seccomp floor (static mode's filter)
                                                never    → KILL
                                                brokered → USER_NOTIF ─► supervisor: open, inject fd
                                                always   → ALLOW
                                                    │ every call the floor let through
                                                    ▼
                                             graph follower (eBPF): stack(t), decide
                                                valid   → the position advances
                                                invalid → Enforce: kill    Audit: log, count, run
                                                    │
                                                    ▼
                    signed record: mode, Enforce or Audit, floor digest, graph digest, violations

4. The worked example: A { B C D }* F

The program is the graph plan's own fixture (plan §5), on one tokio thread: A opens a file (openat), then a loop: B (getpid), then join! of two futures C (getuid) and D (getgid), whose order varies; then F closes the file (close). A real run prints A (B C D | B D C)* F.

In static mode. The profiler's runs give M ⊇ {openat, getpid, getuid, getgid, close} plus the runtime's calls. The cross-check confirms all five. There is one position, and decide allows I ∪ F from the first instruction to the last. The order of C and D is invisible and does not matter. An attacker who takes over in the loop can call openat again, any number of times, on any path Landlock allows.

In graph mode. The graph (plan §5):

First(main) = {A}
Next = { A→B, A→F,  B→C, B→D,  C→D, D→C,  C→B, D→B,  C→F, D→F,  B→F }
regions:  setup {A}    serve {B, C, D} (one cycle)    shutdown {F}

A lies on no cycle, so once the thread has moved on, a second openat is an invalid step: a budget of one, with no counter. An openat injected in the loop is an invalid step too, because no position of the loop allows it.

What it costs here. The floor answers all five calls in BPF (openat goes to the broker where the job has one). The follower then checks each call in the kernel, in the calling thread. No call of the loop leaves the kernel for the check, and the order of B, C and D is enforced. The price is one small program run per call (section 8).

The profiler finding "C and D were seen in another order". Suppose an early analyzer models join! as "C, then D". Its graph is Next₁ = { A→B, A→F, B→C, C→D, D→B, D→F }. One profiled run is A B C D B D C B C D F:

Obs₂ = { (A,B), (B,C), (C,D), (D,B), (B,D), (D,C), (C,B), (D,F) }           8 pairs
nodes:  S = 5/5 = 1.0     P = 5/5 = 1.0
pairs:  S₂ = |Obs₂ ∩ Next₁| / |Obs₂| = 5/8 = 0.625     findings: (B,D), (D,C), (C,B)
        P₂ = 5/6                                        never observed: A→F

S₂ < 1, so this graph is not enforced. The three findings have one cause: both futures are polled inside one poll, and each can be pending, so either can call first. That is in the code, so the graph must say it. The resolution is an analyzer fix, with this fixture as its test (plan §7 lists it). Nobody declares "C and D are unordered" by hand. With the fixed graph (Next above):

S₂ = 8/8 = 1.0        P₂ = 8/11       never observed: A→F, C→F, B→F

A→F needs a run with zero rounds, and C→F a run whose last round is B D C: two runs to add. B→F cannot happen in any run (the join always makes both calls). It is analyzer imprecision and stays listed until the analysis is sharper.

5. The trait

Where it sits. There is no trait today, but the code has one choke point too: every BPF program Heimdall builds goes through heimdall_seccomp::bpf::build_rules (crates/heimdall-seccomp/src/bpf.rs:176). Its callers assemble their rules themselves:

The trait replaces the enforcing assemblies (the first two rows, and the worker's use of the third). The broker filter and the learning filters stay outside: they broker and record.

The trait is the model, in a new module heimdall_seccomp::filter:

pub trait CallFilter: Send + Sync {
    fn name(&self) -> &'static str;                             // "static" | "graph"
    fn start(&self, entry: EntryId) -> Position;                // static: the one position; graph: a stack
    fn decide(&self, at: &Position, event: &Event) -> Decision; // Valid(next) | Invalid
    fn floor(&self) -> &[Rule];                                 // the floor's rules: static mode's profile
    fn digests(&self) -> FilterDigests;                         // what the signed record names
}

/// The pipeline, OUTSIDE the trait. It builds the floor as ONE program with build_rules, so
/// the arch check, the x32 kill and the base set are outside every implementation. For a
/// graph filter it also builds the follower's tables: the states and the (state, class) map.
pub fn compile(f: &dyn CallFilter, arch: Arch) -> Result<Compiled, FilterError>;
pub struct Compiled { pub floor: Program, pub wants_listener: bool,
                      pub follower: Option<FollowerTables>, pub digests: FilterDigests }

decide in Rust is the reference. The eBPF follower must agree with it on every run of the tests.

Names, against the code. heimdall_core::Protection already exists. It is the signed statement of what protected a run: None | Default | Generated { profile_digest } (crates/heimdall-core/src/types.rs:757-765). Mode and FilterMode are taken too (crates/heimdall-seccomp/src/bpf.rs:141, crates/heimdall-broker/src/filter.rs:48). So:

• The request. Today a job names a profile in Policy.seccomp (types.rs:263). It becomes one choice, CallProtection::Static(profile) | CallProtection::Graph { profile, graph, enforce }, and a plain seccomp field reads as Static.
• The record. Protection::Generated is static mode. It keeps its name and wire tag, so old results verify. Graph mode adds, under the next wire version, Protection::Graph { floor_digest, graph_digest, enforce, violations }.

The signed record says: the mode (static or graph), Enforce or Audit, the digest of the floor's program, the digest of the graph, and the number of invalid steps. The digests are SHA-256, the hash the code already uses for profiles and outputs (Sha256Digest::of, crates/heimdall-core/src/types.rs:108-113). The graph digest is over the bytes of exec.nodes and then exec.edges. The mode and the digests are known at start; the violation count is in the result. A service has no signed record after its start today (crates/heimdall-core/src/service.rs:250-276), so its end record is new work. A consumer should give full trust only to Enforce with 0 violations. That is the consumer's policy; the record only states the facts. A signature proves what Heimdall installed and saw, not that the kernel held.

The first build step is static mode behind the trait, as a pure refactor. Its test: for every profile in heimdall_profiles::ALL (profiles/src/lib.rs:31), the program from compile(StaticFilter) equals today's program instruction for instruction, and the signed result and signed start bytes are unchanged. This step does not need the graph.

6. How it plugs into a container runtime (youki)

A container runtime compiles the OCI seccomp section into one program and loads it. The runtime-side trait gives the user the choice of who does that: libseccomp (the default), Firecracker's seccompiler, or Heimdall. Whoever picks Heimdall replaces the default fully. The trait is small, and it stays small:

pub trait SeccompBackend: Send + Sync {
    fn name(&self) -> &'static str;                 // "libseccomp" | "seccompiler" | "heimdall"
    fn compile(&self, spec: &LinuxSeccomp, arch: Arch) -> Result<CompiledSeccomp>;
}
pub struct CompiledSeccomp { pub program: Vec<sock_filter>, pub flags: SeccompFlags, pub wants_listener: bool }

• Both Heimdall modes plug in the same way, because in both the floor is one seccomp program that goes through compile. With Heimdall as the backend the user sets the mode in one place: static, or graph.
• The brokered set: wants_listener is true when the profile has one. youki already hands a seccomp notify listener to an external process (the OCI listenerPath). That is how Heimdall's supervisor gets the brokered calls. No extra hook is needed.
• The follower is attached by Heimdall on the host when the container starts. It needs nothing from the runtime.
• Static mode needs no change in youki to be used today. Heimdall's tooling already writes the OCI seccomp profile (.oci.json, crates/heimdall-probe/src/codegen.rs:163), and youki loads it with its default backend. The trait adds the choice of backend. It changes no behaviour by default.
• Heimdall does not read Firecracker's hand-written rule format. Its profiles come from the profiler and are checked by static analysis.

Graph mode uses no filter code of youki, libseccomp or Firecracker. The runtime only loads the program and passes the listener.

7. What the profiler must record for graph mode

Today it keeps call → runs (crates/heimdall-probe/src/observe.rs:56). The thread id arrives in every notification (crates/heimdall-seccomp/src/notif.rs:67-69), but call_of drops it (crates/heimdall-probe/src/learn.rs:69-94), and the live probe uses it only to skip other processes (live.rs:130). Graph mode needs, per run:

per thread, in memory only (tids differ between runs):   last = the class of its previous call
pairs[(a, b)]   count of "b is the next call after a in one thread"     → Obs₂, S₂, P₂
count[c]        calls per class                              → Obs, and how hot a class is
thread starts   which entry a new thread belongs to, as far as the profiler can tell

• Pairs, not traces. A trace grows with the run. Pairs grow with the number of classes.
• Per-thread order is exact. A thread is stopped until its notification is answered, so its calls arrive in its own order. Order across threads means nothing and is not kept.
• A new file beside probe.json, which stays byte-identical: edda and dwarves read it.
• Node ids. The profiler sees classes, not sites, and so does the filter. The check is therefore at the class level, which is what enforcement needs: S₂ = 1.0 means no observed run would be invalid. The exact id form comes from the graph plan (§8).
• Signals. The profiler runs on USER_NOTIF and sees neither a handler's start nor its return. A handler run splits a pair (a, b) into (a, f) … (l, b). The graph check accepts (a, f) when f is a handler's first call, and (l, b) when l can be its last.

8. The decision: where the position lives, and why

Decided by the owner, with the outside review: the three parts of section 1. The position lives in the kernel, in the eBPF graph follower. This section gives the reasons, the invariants, what a host must have, and the fallback.

Why three parts.

• Seccomp must stay. Classic BPF has no memory between calls, so it cannot hold a position. But seccomp stops a call before it runs, without privileges, and only seccomp can hand a call to user space. An eBPF program can do neither. So the floor and the brokering stay in seccomp.
• The position goes into the kernel. A supervisor that holds the positions costs a round trip to user space per checked call. Then only a few calls can be checked, and the others lose their order. The follower runs in the calling thread with no context switch, so every call is followed.
• The supervisor shrinks to what needs user space: opening beneath a path, injecting the descriptor, signing.

The invariants.

1. Enforce or Audit, a field of the policy. Enforce: an invalid step kills. Audit: it is logged and counted and the call runs; Audit never returns an error.
2. The kill is late by at most one call on the tracepoint path, and the floor allows that call anyway. Where an LSM hook exists for the operation, the refusal is before it.
3. Thread creation. A new thread starts on the entry of its spawn site. A spawn the graph does not have is an invalid step.
4. Async. Per kernel thread, the union over the tasks that can run. Sound; it costs precision. Task tags written by the program are not used.
5. Widening. dyn and fn-pointer sites only, limited to what the reached code creates. A C function without a map entry blocks graph mode for that program.
6. The signed record names the mode, Enforce or Audit, the floor's program digest, the graph digest (SHA-256) and the violation count (section 5).

What it needs.

• Privileges. A loader on the host side of the runner, with CAP_BPF and CAP_PERFMON in the initial user namespace. The job itself gets no new privilege.
• Kernel. BTF; task-local storage (a thread-keyed hash map where it is missing); BPF LSM in lsm= for the refusals before the call. The options: CONFIG_BPF_SYSCALL, CONFIG_BPF_JIT, CONFIG_BPF_EVENTS, CONFIG_DEBUG_INFO_BTF, CONFIG_BPF_LSM, and bpf in CONFIG_LSM or lsm=. Heimdall's kernel needs name none of them today (crates/heimdall-container/src/kernel.rs:73-109); they become rows there.
• Code. Rust eBPF with aya, pure Rust. The loader attaches the follower when the job or container starts, selects the workload by cgroup, and detaches it at the end.

The fallback, plainly. Graph mode does not work out of the box. Not every host has these kernel options, and a rootless runner cannot load eBPF. There the workload runs in static mode, and the record says static.

One slow variant stays documented for hosts without eBPF: positions held by the supervisor. It is never chosen by default, only by name in the policy, and the record names it. The seccomp program then has three answers: never → kill; a call that is allowed at every position → ALLOW; a call whose answer depends on the position → USER_NOTIF, and the supervisor answers CONTINUE or an errno before the call runs. Its limits:

• every position-dependent call pays a round trip to user space;
• a call left in ALLOW is not order-checked, and the supervisor follows the graph with those calls' sites skipped;
• signals are inferred: seccomp sees neither signal delivery nor rt_sigreturn (the base set is allowed in BPF first), so a call that matches a handler's first call pushes, and a call that fits the frame below pops. Every handler's first calls are then accepted at every position;
• a filter chain can have one listener (crates/heimdall-trace/src/tracer.rs:241), so in a job the positions and the broker share one process.

Cost: to measure. None of these numbers is measured for Heimdall yet. Build step 10 measures them.

followed workload, per call:    t_bpf (the floor, as today)  +  t_follow (one eBPF run, one map lookup)
other processes on the host:    t_idle per call  (the tracepoint is host-wide; a thread with no stack
                                                  returns at once)
supervisor-held variant:        t_rt per position-dependent call  (a notify round trip)

Kernel facts, with sources.

• Order at the entry: ptrace, then seccomp, then the sys_enter tracepoint. A call that seccomp ends does not reach sys_enter. sys_exit runs whether or not the call was skipped (kernel/entry/common.c: syscall_trace_enter, syscall_exit_work; read at v6.6).
• A restarted call enters again. The kernel sets regs->ax = regs->orig_ax and regs->ip -= 2, so the syscall instruction runs a second time, through seccomp and the tracepoint. A timed wait comes back as restart_syscall. With a handler and without SA_RESTART the call returns EINTR (arch/x86/kernel/signal.c: arch_do_signal_or_restart, handle_signal; v6.6).
• Signal delivery has a tracepoint, signal:signal_deliver, with the fields sig, sa_handler and sa_flags (include/trace/events/signal.h; read in the 7.0 headers).
• bpf_send_signal sends a signal "to the process of the current task" (include/uapi/linux/bpf.h). A tracepoint program cannot change the call's result.
• BPF LSM programs can return an error from a security hook. Hooks exist per security operation, not per system call (https://docs.kernel.org/bpf/prog_lsm.html).
• To verify in build step 6: the same restart path on arm64; task-local storage in tracing programs on the kernels we ship; the call number at sys_exit for a call that seccomp ended.

9. Against Firecracker's seccompiler

seccompiler compiles hand-written JSON rules into BPF at build time. It is a good compiler, long in production, and it is not a way to find the rules.

seccompiler is ahead today on two rows: comparison operators and per-thread filters.

10. Limits

• Mimicry. An attacker inside the process can follow any path of the graph from the current position, with any value for arguments the graph does not fix.
• Memory arguments (paths, addresses, buffers) are checked by neither mode. They belong to Landlock, the namespaces and the broker.
• The late kill. On the tracepoint path one invalid call runs before the process dies. Other threads finish the call they are in.
• The same call again is always valid, so any call can be repeated in place, also by an attacker. A once-only site is once plus such repeats.
• Signals. A handler that leaves by siglongjmp never pops its frame, and such a jump is not in the graph (plan §9).
• The C boundary. A libc function is one node with a set of calls; the order inside it is not in the graph. The allocator and the locks put mmap and futex into almost every position.
• io_uring. Ring operations are not system calls, so neither seccomp nor the follower sees them. Heimdall jobs get no ring today (crates/heimdall-container/src/profile.rs:156-169).
• Hosts. Graph mode needs eBPF and host privileges. Elsewhere it is static mode.
• Outside any graph: dlopen, a syscall number computed at run time, a second program started with exec (plan §9).
• Coverage. A path no run drove is in the graph, so the follower accepts it. The floor still kills any call on it that was never measured.

11. Prior art

• Wagner and Dean, "Intrusion Detection via Static Analysis", IEEE S&P 2001. Call sequences derived from the code, as automata, checked at run time: graph mode's model. The mimicry attack (Wagner and Soto, CCS 2002) applies here too.
• SFIP, Canella, Dorn, Gruss, Schwarz, https://arxiv.org/abs/2202.13716. Syscall transitions and call origins, enforced in a modified kernel. Graph mode wants the transitions on a stock kernel, which is why the state lives in eBPF beside seccomp.
• Temporal System Call Specialization, Ghavamnia et al., USENIX Security 2020. A smaller filter for the serving phase. Here that is a region of the graph.
• Forrest et al., "A Sense of Self for Unix Processes", IEEE S&P 1996. Short call sequences learned from runs. The profiler's pairs are their windows of length two, used to check a graph, not to be the model.
• OpenBSD pledge(2): promises that only shrink. Seccomp user notification (seccomp_unotify(2)): the mechanism of the profiler and the broker. Landlock (https://docs.kernel.org/userspace-api/landlock.html): paths and TCP ports checked at use time, which neither mode can do. Firecracker seccompiler: section 9.

12. Build order

Test-first: each step is a branch whose tests are red first, then green.

1. Static mode behind the trait (section 5). Needs no graph and can start now. Byte-identical programs and records. The runtime backend of section 6 builds on it.

The rest starts only when the 1:1 graph exists: the graph plan's fixtures are green and exec.nodes / exec.edges are written for a real program.

1. Graph import, pinned by its SHA-256. Tests: a round trip; an unknown schema or call name is refused by name; a C function without a map entry blocks graph mode.
2. The pair recorder (section 7). Tests on the A { B C D }* F fixture: exactly the pairs of section 4; probe.json byte-identical.
3. The graph check. Tests: section 4's numbers, 0.625 on the wrong graph and 1.0 on the right one; an empty denominator prints "no data".
4. decide in Rust, the reference, no kernel. Property tests for G1 to G4, with handlers that start anywhere, nest and return, restarted calls, and spawns.
5. The follower's tables. The loader makes the graph deterministic. Tests: the tables agree with decide on random runs; the state count is reported; a graph past the map's size is refused.
6. The follower: the aya program and its maps, on the entry, exit, signal-delivery and thread-creation tracepoints. Audit first. Tests in a privileged test machine: the fixture runs with 0 violations; an openat injected in the loop is counted; a signal handler runs between two calls of the fixture and the run is still valid; a call that is in no handler and not next is still invalid; a restarted call is valid; a ninth frame is invalid. The kernel facts marked "to verify" are checked here.
7. The loader on the runner's host side: attach by cgroup at start, detach at the end. Tests: a host without the kernel options or the privileges gets static mode, and the record says so. The options become rows of heimdall kernel needs.
8. Enforce. Tests: an invalid step kills; the invalid call is the last one the thread makes; with BPF LSM and no broker, an invalid openat or connect is refused before it runs; Audit returns no error on the same runs.
9. Records: Protection::Graph and the end record. Old results still verify.
10. Measure t_bpf, t_follow and t_idle, on the fixture and on the wasm host worker, and the round trip of the supervisor-held variant on the same runs. The numbers go into section 8 with date and kernel.
11. Real programs, in Audit first and then Enforce: the wasm host worker (our own code), then Holger's scan worker.

13. Questions for the reviewer

1. Async. Position is per kernel thread, and tasks on one thread give the union. How much precision is left on a real executor, where almost any task can run next?
2. The C boundary. Is a libc function as one unordered node acceptable, or does graph mode need the order inside libc before it says more than static mode?
3. io_uring. For ring-heavy programs, is "syscall position + ring opcode restrictions + LSM hooks" a sound answer, or must Heimdall own the ring to follow its operations?
4. The numbers. Are S, P, S₂, P₂ on next-call pairs the right gates? Would longer windows find analyzer errors that pairs miss?
5. The cost. Which measurements should decide whether the follower is cheap enough: t_follow on a busy server, t_idle on the host's other processes, the size of the deterministic graph? What would make the result unacceptable?