bpf: add DAG fast-path in verifier to skip redundant state pruning
Subsystems (4)
RFC PATCH 1/1 bpf: add DAG fast-path in verifier to skip redundant state pruning
bpf: add DAG fast-path in verifier to skip redundant state pruning
The BPF verifier's state-equivalence loop (is_state_visited / states_equal) dominates load time for programs with acyclic control flow graphs (DAGs). In a DAG, every instruction is reached via exactly one path: no state is ever revisited, making state-pruning comparisons mathematically vacuous.
This RFC proposes three components:
1. compute_dag_topo() -- replaces a simple is_acyclic_dag() bool. Uses Kahn's algorithm (O(V+E), O(V) space, no recursion) to detect back-edges AND preserve the topological visit order for use in (2). Handles BPF_JMP32, BPF_LD_IMM64 wide instructions, and falls back conservatively on BPF-to-BPF subprogram calls.
2. do_check_dag() -- fast-path verifier for confirmed-DAG programs. Critical correctness property: maintains a per-instruction state table (states[insn_cnt]) and, at every join point (in_degree > 1), calls merge_verifier_state() to conservatively merge all incoming paths BEFORE processing the instruction. This ensures the verifier never sees a register as initialized when any predecessor path left it NOT_INIT.
Skips is_state_visited() / states_equal() entirely; provably safe because topological order guarantees each instruction is processed exactly once.
3. Full fallback: if compute_dag_topo() returns NULL (cyclic program, subprog, or allocation failure), or if do_check_dag() returns an error, the unmodified do_check() runs unchanged.
Register-state correctness at join points
-----------------------------------------
When paths A and B converge at instruction N, the verifier must hold the least precise state that is safe for both paths.
Path A arrives at insn N: R2 = scalar [0, 5] Path B arrives at insn N: R2 = NOT_INIT merge_verifier_state() result: R2 = NOT_INIT -> verifier correctly rejects any use of R2 at N
Without this merge (a flaw in naive linear-scan approaches), the verifier would see only the state from whichever path was processed last in memory order, potentially accepting a program that dereferences an uninitialized register at runtime.
RFC design question:
--------------------
do_check_dag()'s inner per-instruction verification step requires calling into do_check()'s inner loop logic, which is not currently factored as a callable sub-function. We propose two integration options and request maintainer guidance:
Option A: Extract a verify_one_insn() helper from do_check()'s
inner loop; do_check_dag() calls it per topological step.
Option B: Add env->dag_mode flag to do_check(); when set,
do_check() uses pre-populated env->dag_states[] and skips is_state_visited() comparisons (~20 lines added to do_check(), no code duplication).
The state merge logic, DAG detection, and topological traversal are independent of this choice and are presented in full below.
Benchmark data will be included in v1 once the integration approach is confirmed. Timing will be measured at BPF_PROG_LOAD syscall level with verifier-only isolation.
---
Open Questions for Maintainers
===============================
Q1 (Critical): Integration with do_check() inner loop
Option A or B as described above?
Q2: Scope
Should this apply to all program types, or only XDP/TC where DAG programs (e.g., Cilium policy programs) are most common?
Q3: Kconfig guard
Is a CONFIG_BPF_DAG_OPT Kconfig symbol appropriate, or should this be unconditional given the O(V+E) overhead is negligible?
Q4: Subprogram handling
Current RFC falls back to full verifier for BPF_PSEUDO_CALL programs. Is per-subprog DAG analysis worth adding in a follow-up?
---
include/linux/bpf.h | 3 + include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 215 ++++++++++++++++++ tools/testing/selftests/bpf/test_dag_verify.c | 230 +++++++++++++++++++ 4 files changed, 454 insertions(+)
include/linux/bpf.h +0 -0
@@ -... @@struct bpf_prog_aux {/* ... existing fields ... */ +unsigned int cfg_is_acyclic :1 ;/* CFG has no back-edges (DAG) */ /* ... */ };
include/linux/bpf_verifier.h +0 -0
@@ -... @@ +/* +* bpf_dag_info - output of compute_dag_topo(). +* +* @topo_order: topological visit order; topo_order[i] is the insn index +* of the i-th instruction in topological order. +* @in_degree: snapshot of original in-degree per instruction slot, +* taken before Kahn's traversal. Used by do_check_dag() +* to detect join points (in_degree[n] > 1). +* @insn_cnt: env->prog->len at computation time. +*/ +struct bpf_dag_info { +int *topo_order; +int *in_degree; +int insn_cnt; +};
kernel/bpf/verifier.c +0 -0
@@ -... @@ +static void free_dag_info (struct bpf_dag_info *dag) +{ +if (!dag) +return ; +kfree (dag->topo_order); +kfree (dag->in_degree); +kfree (dag); +} + +/* +* compute_dag_topo() - detect acyclic CFG and return topological order. +* +* Implements Kahn's algorithm: repeatedly remove zero-in-degree nodes. +* If all nodes are processed (visited == insn_cnt), CFG has no back-edges. +* +* Returns allocated bpf_dag_info on success; caller must free_dag_info(). +* Returns NULL if cyclic, contains BPF-to-BPF calls, or on alloc failure. +* All NULL paths are safe: caller falls back to unmodified do_check(). +* +* Handles BPF_JMP, BPF_JMP32, BPF_LD_IMM64 wide instructions. +* Assumes check_cfg() has already run. +*/ +static struct bpf_dag_info *compute_dag_topo (struct bpf_verifier_env *env) +{ +struct bpf_insn *insns = env->prog->insnsi; +int insn_cnt = env->prog->len; +struct bpf_dag_info *dag =NULL ; +int *in_degree =NULL , *queue =NULL ; +bool *is_dummy =NULL ; +int head =0 , tail =0 , visited =0 , i; + + dag =kzalloc (sizeof (*dag),GFP_KERNEL ); + in_degree =kcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); + queue =kcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); + is_dummy =kcalloc (insn_cnt,sizeof (bool ),GFP_KERNEL ); +if (!dag || !in_degree || !queue || !is_dummy) + goto fail; + +/* Pass 1: compute in-degrees for each instruction slot. */ +for (i =0 ; i < insn_cnt; i++) { +struct bpf_insn *insn = &insns[i]; +u8 cls =BPF_CLASS (insn->code); +u8 op; + +/* +* BPF_LD_IMM64: two-slot wide instruction. +* The second (dummy) slot has no real edges; fall-through +* skips to slot i+2. +*/ +if (insn->code == (BPF_LD |BPF_IMM |BPF_DW )) { +if (i +1 < insn_cnt) + is_dummy[i +1 ] = true; +if (i +2 < insn_cnt) + in_degree[i +2 ]++; + i++; +continue ; + } + +if (cls !=BPF_JMP && cls !=BPF_JMP32 ) { +if (i +1 < insn_cnt) + in_degree[i +1 ]++; +continue ; + } + + op =BPF_OP (insn->code); + +if (op ==BPF_EXIT ) +continue ; + +/* BPF-to-BPF subprog call: fall back to full verifier. */ +if (op ==BPF_CALL && insn->src_reg ==BPF_PSEUDO_CALL ) + goto fail; + + { +int tgt = i +1 + insn->off; +if (tgt >=0 && tgt < insn_cnt) + in_degree[tgt]++; + } + +if (op !=BPF_JA && i +1 < insn_cnt) + in_degree[i +1 ]++; + } + +/* Snapshot in-degrees before Pass 3 modifies them. */ + dag->in_degree =kcalloc (insn_cnt,sizeof (int ),GFP_KERNEL ); +if (!dag->in_degree) + goto fail; +memcpy (dag->in_degree, in_degree, insn_cnt *sizeof (int )); + +/* Pass 2: seed queue with zero-in-degree nodes. */ +for (i =0 ; i < insn_cnt; i++) +if (in_degree[i] ==0 ) + queue[tail++] = i; + +/* Pass 3: Kahn's topological traversal. */ +while (head < tail) { +int node = queue[head++]; +struct bpf_insn *insn = &insns[node]; +u8 cls =BPF_CLASS (insn->code); +u8 op; + + visited++; + +if (is_dummy[node]) +continue ; + + op = (cls ==BPF_JMP || cls ==BPF_JMP32 ) ? +BPF_OP (insn->code) :0xff ; + +if (op ==BPF_EXIT ) +continue ; + +if (cls ==BPF_JMP || cls ==BPF_JMP32 ) { +int tgt = node +1 + insn->off; +if (tgt >=0 && tgt < insn_cnt) +if (--in_degree[tgt] ==0 ) + queue[tail++] = tgt; +if (op !=BPF_JA && node +1 < insn_cnt) +if (--in_degree[node +1 ] ==0 ) + queue[tail++] = node +1 ; + }else if (insn->code == (BPF_LD |BPF_IMM |BPF_DW )) { +if (node +2 < insn_cnt) +if (--in_degree[node +2 ] ==0 ) + queue[tail++] = node +2 ; + }else { +if (node +1 < insn_cnt) +if (--in_degree[node +1 ] ==0 ) + queue[tail++] = node +1 ; + } + } + +if (visited != insn_cnt) + goto fail; + + dag->topo_order = queue; + dag->insn_cnt = insn_cnt; +kfree (in_degree); +kfree (is_dummy); +return dag; + +fail: +kfree (queue); +kfree (in_degree); +kfree (is_dummy); +if (dag) { +kfree (dag->in_degree); +kfree (dag); + } +return NULL ; +} + +/* +* dag_merge_state() - propagate verifier state to a successor instruction. +* +* First predecessor: copy state (establishes the baseline). +* Subsequent predecessors: conservative merge via merge_verifier_state(). +* +* If path A has R2 = scalar [0,5] and path B has R2 = NOT_INIT, +* the merged result is R2 = NOT_INIT. +* +* merge_verifier_state() is reused unchanged; no new merge semantics. +*/ +static int dag_merge_state (struct bpf_verifier_env *env, +struct bpf_verifier_state **states, +int succ, +const struct bpf_verifier_state *from) +{ +if (succ <0 || succ >= env->prog->len) +return -EINVAL ; + +if (!states[succ]) { + states[succ] =kzalloc (sizeof (*states[succ]),GFP_KERNEL ); +if (!states[succ]) +return -ENOMEM ; +return copy_verifier_state (states[succ], from); + } + +return merge_verifier_state (env, states[succ], from); +} + +/* +* do_check_dag() - verifier fast-path for acyclic BPF programs. +* +* PRESERVES: all register type/bounds propagation, memory access checks, +* stack depth tracking, pointer type validation. +* SKIPS: is_state_visited() / states_equal() equivalence loop. +* +* Processes instructions in topological order (dag->topo_order[]). +* Maintains a per-instruction state table (states[insn_cnt]). +* At join points (dag->in_degree[node] > 1), conservatively merges +* all incoming states via dag_merge_state() BEFORE processing the +* instruction. +*/ +static int do_check_dag (struct bpf_verifier_env *env, +const struct bpf_dag_info *dag) +{ +int insn_cnt = env->prog->len; +struct bpf_verifier_state **states; +int err =0 , i; + + states =kcalloc (insn_cnt,sizeof (*states),GFP_KERNEL ); +if (!states) +return -ENOMEM ; + + states[0 ] =kzalloc (sizeof (*states[0 ]),GFP_KERNEL ); +if (!states[0 ]) { + err = -ENOMEM ; + goto out; + } + err =init_verifier_state (env, states[0 ]); +if (err) + goto out; + +for (i =0 ; i < insn_cnt; i++) { +int node = dag->topo_order[i]; +struct bpf_verifier_state *cur = states[node]; +struct bpf_insn *insn = &env->prog->insnsi[node]; +u8 cls =BPF_CLASS (insn->code); +u8 op = (cls ==BPF_JMP || cls ==BPF_JMP32 ) ? +BPF_OP (insn->code) :0xff ; + +if (!cur) +continue ; + +/* +* RFC integration point (Open Question Q1). +* +* This is where the per-instruction verification call goes +* once the integration approach is confirmed by maintainers. +* The state merge logic above and below is independent of +* which option is chosen. +* +* Option A: extract verify_one_insn() from do_check(). +* Option B: add env->dag_mode; do_check() uses dag_states[] +* and skips is_state_visited() when flag is set. +*/ + env->cur_state = cur; +if (err) + goto out; + +if (op ==BPF_EXIT ) +continue ; + +if (cls ==BPF_JMP || cls ==BPF_JMP32 ) { +if (op ==BPF_JA ) { + err =dag_merge_state (env, states, + node +1 + insn->off, cur); + }else { + err =dag_merge_state (env, states, + node +1 + insn->off, cur); +if (!err) + err =dag_merge_state (env, states, + node +1 , cur); + } + }else if (insn->code == (BPF_LD |BPF_IMM |BPF_DW )) { + err =dag_merge_state (env, states, node +2 , cur); + }else { + err =dag_merge_state (env, states, node +1 , cur); + } + +if (err) + goto out; + } + +out: +for (i =0 ; i < insn_cnt; i++) +if (states[i]) +free_verifier_state (states[i], false); +kfree (states); +return err; +} + +/* DAG fast-path hook in do_check_main() */ + { +struct bpf_dag_info *dag =compute_dag_topo (env); +if (dag) { + env->prog->aux->cfg_is_acyclic =1 ; + ret =do_check_dag (env, dag); +free_dag_info (dag); +if (ret ==0 ) + goto out; + env->prog->aux->cfg_is_acyclic =0 ; + ret =0 ; + } + } + ret =do_check (env); +out:
tools/testing/selftests/bpf/test_dag_verify.c +145 -0
145 lines not on this page · raw message
+#undef LOAD
+}
Quoted 54 lines · Seunghyeon Lee
bpf: add DAG fast-path in verifier to skip redundant state pruning
The BPF verifier's state-equivalence loop (
is_state_visited/states_equal) dominates load time for programs with acyclic control flow graphs (DAGs). In a DAG, every instruction is reached via exactly one path: no state is ever revisited, making state-pruning comparisons mathematically vacuous.This RFC proposes three components:
1.
compute_dag_topo()-- replaces a simpleis_acyclic_dag()bool. Uses Kahn's algorithm (O(V+E), O(V) space, no recursion) to detect back-edges AND preserve the topological visit order for use in (2). HandlesBPF_JMP32,BPF_LD_IMM64wide instructions, and falls back conservatively on BPF-to-BPF subprogram calls.2.
do_check_dag()-- fast-path verifier for confirmed-DAG programs. Critical correctness property: maintains a per-instruction state table (states[insn_cnt]) and, at every join point (in_degree> 1), callsmerge_verifier_state()to conservatively merge all incoming paths BEFORE processing the instruction. This ensures the verifier never sees a register as initialized when any predecessor path left itNOT_INIT.Skips
is_state_visited()/states_equal()entirely; provably safe because topological order guarantees each instruction is processed exactly once.3. Full fallback: if
compute_dag_topo()returns NULL (cyclic program, subprog, or allocation failure), or ifdo_check_dag()returns an error, the unmodifieddo_check()runs unchanged.Register-state correctness at join points
-----------------------------------------
When paths A and B converge at instruction N, the verifier must hold the least precise state that is safe for both paths.Path A arrives at insn N: R2 = scalar [0, 5] Path B arrives at insn N: R2 =
NOT_INITmerge_verifier_state()result: R2 =NOT_INIT-> verifier correctly rejects any use of R2 at NWithout this merge (a flaw in naive linear-scan approaches), the verifier would see only the state from whichever path was processed last in memory order, potentially accepting a program that dereferences an uninitialized register at runtime.
RFC design question:
--------------------
do_check_dag()'s inner per-instruction verification step requires calling into do_check()'s inner loop logic, which is not currently factored as a callable sub-function. We propose two integration options and request maintainer guidance:
Quoted 2 lines
Option A: Extract a
verify_one_insn()helper from do_check()'s
inner loop;do_check_dag()calls it per topological step.
Specializing the verifier for DAG only case is not interesting. Almost all programs now contain loops.
But the approach to use do_check_insn() as a transfer function in the data flow analysis is totally viable.
I've been prototyping such transfer + join verifier for some time. Will share soon. What merge_verifier_state() does is a key.
Alexei,
Agreed — DAG-only is the narrow case. The general case is the right direction.
On merge_verifier_state():
I've been looking at this from two angles:
Transfer-function approach (your direction): merge_verifier_state() as the join operator in a dataflow lattice. The key question: what's the minimal state representation that preserves safety without full state enumeration?
Proof-carrying approach (longer-term): If a compiler can prove properties about the transfer function before loading, the verifier only needs to check the proof, not simulate the lattice. This is essentially PCC (Necula 1997) applied to BPF.
These two converge at merge_verifier_state(): the join operator defines the abstract domain. If the domain is finite and the transfer functions are monotone, you get termination for free — proof becomes a byproduct.
Looking forward to seeing your prototype. What representation are you using for the abstract state?
- Seunghyeon
Alexei,
I know you're deep in the review backlog and the prototype share is still pending. Rather than waiting, I'm sending this ahead -- apologies for jumping the queue.
You said the DAG specialization isn't interesting (fair -- loops are everywhere now), but that do_check_insn() as a transfer function in the dataflow analysis is viable, and that merge_verifier_state() is the key. I agree it's the key, and it's where I started -- one level down. A join is only as sound as the domain it operates on, so before the join itself I pinned down that domain: the scalar state merge_verifier_state() combines, tnum x cnum, as it stands in bpf-next (a975094bf).
I built a small, self-contained Rust model of it -- the tnum bit domain (tnum.c), the cnum circular-number range domain (cnum.c / cnum_defs.h), and the reduced-product reduction in reg_bounds_sync(). Three results, all machine-checked (10 harnesses, Kani 0.67.0 / CBMC):
1. Soundness. Each harness states the abstraction is sound -- for every concrete x in gamma(a) and y in gamma(b), f(x,y) lies in gamma(f#(a,b)) -- and Kani discharges it over the full bit-vector input space (not sampled). Covered: tnum add/sub/and/or/xor, tnum_in, the cnum subset order, and cnum64_cnum32_intersect.
2. Faithfulness. The differential test links the *unmodified* kernel tnum.c + cnum.c against userspace stub headers (the .c is byte-for-byte bpf-next, no kernel build needed) and fuzzes them against the Rust model, N=2000 x 11 ops, 0 mismatch. So (1) carries over to the C, not just the model.
3. A question this raised (for Eduard/Paul as much as anyone). On the model Kani proves the cross-width reduction idempotent -- one __reg_deduce_bounds() pass reaches the fixpoint over all inputs -- which surprised me, since 9e5fcb003aec ("bpf: Avoid one round of bounds deduction") established two rounds as the minimum, with verifier_bounds/"cross sign boundary, negative overlap" failing at one.
But that analysis predates the circular-number refactor (256f0071f9b6), which collapsed the four deduce sub-steps into two. So the honest question:
did cnum make the second __reg_deduce_bounds() in reg_bounds_sync() (verifier.c:2082) redundant, or does the cross-sign case still rely on it and my isolated model simply misses that state? I haven't built the tree to run that selftest at one call yet -- curious whether the round count was revisited after cnum landed.
Scope, honestly: this is only the scalar tnum/cnum transfer and reduction math, not the whole verifier, and I'm not claiming any over-conservative (false-reject) bug -- none turned up here. The security boundary (regsafe/stacksafe) stays in the kernel; this is a verification model, the PCC split we talked about -- a checker that produces a proof, not a replacement for the kernel's check.
Everything is in one ~600-line crate and reproduces from scratch with a single script -- ./reproduce.sh runs the 11 unit tests, the differential, and all 10 Kani proofs:
https://github.com/hyeon3125-dev/bpf-verifier-rs (against bpf-next a975094bf)
so you can re-run the soundness checks and the diff against C directly, rather than taking my word for any of it.
And when you share the transfer + join prototype, the part I'd most like to compare is exactly the representation it uses for the abstract state, and how merge_verifier_state() joins it.
- Seunghyeon
Quoted 65 lines · Alexei Starovoitov
Quoted 54 lines · Seunghyeon Lee
bpf: add DAG fast-path in verifier to skip redundant state pruning
The BPF verifier's state-equivalence loop (
is_state_visited/states_equal) dominates load time for programs with acyclic control flow graphs (DAGs). In a DAG, every instruction is reached via exactly one path: no state is ever revisited, making state-pruning comparisons mathematically vacuous.This RFC proposes three components:
1.
compute_dag_topo()-- replaces a simpleis_acyclic_dag()bool. Uses Kahn's algorithm (O(V+E), O(V) space, no recursion) to detect back-edges AND preserve the topological visit order for use in (2). HandlesBPF_JMP32,BPF_LD_IMM64wide instructions, and falls back conservatively on BPF-to-BPF subprogram calls.2.
do_check_dag()-- fast-path verifier for confirmed-DAG programs. Critical correctness property: maintains a per-instruction state table (states[insn_cnt]) and, at every join point (in_degree> 1), callsmerge_verifier_state()to conservatively merge all incoming paths BEFORE processing the instruction. This ensures the verifier never sees a register as initialized when any predecessor path left itNOT_INIT.Skips
is_state_visited()/states_equal()entirely; provably safe because topological order guarantees each instruction is processed exactly once.3. Full fallback: if
compute_dag_topo()returns NULL (cyclic program, subprog, or allocation failure), or ifdo_check_dag()returns an error, the unmodifieddo_check()runs unchanged.Register-state correctness at join points
-----------------------------------------
When paths A and B converge at instruction N, the verifier must hold the least precise state that is safe for both paths.Path A arrives at insn N: R2 = scalar [0, 5] Path B arrives at insn N: R2 =
NOT_INITmerge_verifier_state()result: R2 =NOT_INIT-> verifier correctly rejects any use of R2 at NWithout this merge (a flaw in naive linear-scan approaches), the verifier would see only the state from whichever path was processed last in memory order, potentially accepting a program that dereferences an uninitialized register at runtime.
RFC design question:
--------------------
do_check_dag()'s inner per-instruction verification step requires calling into do_check()'s inner loop logic, which is not currently factored as a callable sub-function. We propose two integration options and request maintainer guidance:Quoted 2 lines
Option A: Extract a
verify_one_insn()helper from do_check()'s
inner loop;do_check_dag()calls it per topological step.Specializing the verifier for DAG only case is not interesting. Almost all programs now contain loops.
But the approach to usedo_check_insn()as a transfer function in the data flow analysis is totally viable.
I've been prototyping such transfer + join verifier for some time. Will share soon. Whatmerge_verifier_state()does is a key.
Alexei, Daniel, Eduard,
A brief ping on the follow-up below. I may have missed newer work: has the transfer + join prototype been posted somewhere public, and would the tnum x cnum Kani model be useful to compare against it?
A one-line pointer, or "already covered / not useful", would be enough for me to decide whether to continue or stop here.
Thanks,
Seunghyeon