nordisk/heimdall

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

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.

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