nordisk/heimdall

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

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.

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