Re: [PATCH bpf-next v3 19/45] bpf: Verify programs as a fixpoint over the control flow graph

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 6 potential issue(s) to consider:
- [High] bpf: missing bpf_head_guard_target() edge in update_insn() and need_const
- [High] bpf: missing loop_stack refs update in release_reference_state()
- [Medium] bpf: join_func() and func_states_equal() reject post-call stack arg states
- [Medium] bpf: unreset loop_guard flag and ignored fatal errors in do_check_all()
- [Medium] bpf: do_check_block() mishandles nospec ordering with check_loop_guard()
- [Medium] bpf: check_loop_guard() rejects offloaded progs during patience walk
--

commit 2c82419db13e7e33be1c8b05f84811e97169e868
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Verify programs as a fixpoint over the control flow graph

This commit replaces path-by-path exploration in the BPF verifier with a
fixpoint iteration over the control flow graph that joins states at merge
points. It also adds loop guard injection and bounded patience walks for
loops without statically known trip counts.

> diff --git a/kernel/bpf/flow.c b/kernel/bpf/flow.c
> index c4a6384d34bce..62115e396635a 100644
> --- a/kernel/bpf/flow.c
> +++ b/kernel/bpf/flow.c
> @@ -1024,7 +1024,7 @@ static int flow_compute_need_const(struct bpf_verifier_env *env, struct flow_nee
>  		if (jump)
>  			gen[i] = flow_tested_regs(env, i);
>  		else if (flag)
> -			gen[i] = flow_flag_regs(env, i);
> +			gen[i] = bpf_flow_flag_regs(env, i);

[Severity: High]
As reported by Sashiko on v2 [1], when a loop has no dominating exit
condition and flow_place_guards() places a guard at the loop header h with
aux[h].guard_at_header = true and aux[h].guard_to = t, check_loop_guard()
pushes the state at h along a synthetic BPF_GUARD_LEAVES_LOOP edge to t when
aux->guard_no_unwind is true (for example, when a lock, reference, or RCU
read lock is held across the loop).

While bpf_compute_const_regs(), analyze_subprog(), bpf_flow_compute_kinds(),
and bpf_compute_live_registers() account for t = bpf_head_guard_target(env,
idx), update_insn() in kernel/bpf/liveness.c and flow_compute_need_const() in
kernel/bpf/flow.c only propagate across bpf_insn_successors(env, idx):

kernel/bpf/liveness.c:update_insn() {
	succ = bpf_insn_successors(env, insn_idx);
	if (succ->cnt == 0)
		return false;

	/* All instructions of one frame array share the same mask width */
	for (s = 0; s < succ->cnt; ++s) {
		unsigned long *succ_live;

		succ_live = rel_mask(fm, relative_idx(instance, succ->items[s]), FM_LIVE_BEFORE);
		for (w = 0; w < fm->words; w++)
			new_after[w] |= succ_live[w];
	}
}

If a stack slot holds a value or spilled kernel pointer before entering loop
header h, is overwritten on all normal in-loop CFG paths to t (setting
FM_MUST_WRITE), and is read at or after t, update_insn() does not union
FM_LIVE_BEFORE from t = bpf_head_guard_target(env, h) into new_before at h,
leaving the slot marked dead at h.

When a state arrives at h in bpf_flow_deliver() -> flow_arrive(),
bpf_clean_verifier_state() clears the dead slot's spilled_ptr to NOT_INIT and
marks slot_type as STACK_POISON before check_loop_guard() pushes that state
from h to t. At t, reading the slot fails with a false-positive poisoned slot
error when !env->allow_uninit_stack, or if env->allow_uninit_stack is true
and the header guard state joins at t with a normal loop-exit state where the
slot was overwritten with a scalar, join_slot() in kernel/bpf/join.c turns
STACK_MISC/STACK_ZERO + STACK_POISON into STACK_INVALID. Can this allow
check_stack_read_fixed_off() at t to read back the unoverwritten kernel
pointer spilled before h as an unbounded SCALAR_VALUE when the header
may_goto guard triggers at runtime, and should update_insn() and
flow_compute_need_const() also propagate from bpf_head_guard_target()?

[ ... ]

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 9d3a86b5820e9..4b2506f3e3e27 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c

[ ... ]

> @@ -999,9 +1026,19 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
>  	if (!old->no_stack_arg_load && cur->no_stack_arg_load)
>  		return false;

[Severity: Medium]
As reported by Sashiko on v2 [2], every function frame starts with
no_stack_arg_load = false and out_stack_arg_cnt = 0, and do_check_insn() only
calls end_stack_arg_loads() on BPF_CALL when bpf_in_stack_arg_cnt() is
non-zero.

When a path writes an outgoing stack argument in check_stack_arg_write(),
end_stack_arg_loads() sets state->no_stack_arg_load = true and
grow_stack_arg_slots() increases state->out_stack_arg_cnt. After the call
finishes, invalidate_outgoing_stack_args() resets all state->stack_arg_regs[i]
to NOT_INIT, but state->out_stack_arg_cnt remains at its grown value.

When this post-call state arrives at a loop header or merge point where an
earlier pre-call state (with fa->out_stack_arg_cnt == 0 and
fa->no_stack_arg_load == false) is stored:

1. func_states_equal() rejects !old->no_stack_arg_load &&
   cur->no_stack_arg_load even when the subprogram has no incoming stack
   arguments.
2. join_func() in kernel/bpf/join.c rejects fa->out_stack_arg_cnt <
   fb->out_stack_arg_cnt:

kernel/bpf/join.c:join_func() {
	if (fa->out_stack_arg_cnt < fb->out_stack_arg_cnt)
		return false;
}

Does this prevent joining, widening, and state subsumption whenever a call
with stack arguments occurs inside a loop or on one side of a branch?

[ ... ]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5af42d2dcab94..4801e9ac0089d 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -1605,9 +1617,14 @@ static int acquire_irq_state(struct bpf_verifier_env *env, int insn_idx)
>  
>  static void release_reference_state(struct bpf_verifier_state *state, int idx)
>  {
> -	int last_idx;
> +	int last_idx, fr;
>  	size_t rem;
>  
> +	/* the frames that were entered with it don't hold it ever since */
> +	for (fr = 0; fr <= state->curframe; fr++)
> +		if (idx < state->frame[fr]->entry_refs)
> +			state->frame[fr]->entry_refs--;

[Severity: High]
As reported by Sashiko on v2 [3], loop_stack_push() records
env->cur_state->acquired_refs in loop_stack[cnt].refs when entering a loop,
and check_refs_taken_in_loop() scans from i = entry->refs to
st->acquired_refs at loop backedges to ensure references acquired inside the
loop are still held in a register or stack slot.

When release_reference_state() removes state->refs[idx] and shifts the
remaining entries down with memmove(), it decrements
state->frame[fr]->entry_refs if idx < entry_refs, but it does not decrement
state->frame[fr]->loop_stack[l].refs when idx < loop_stack[l].refs.

If a program acquires a reference before entering a loop, releases that
pre-loop reference inside the loop, and then acquires a new reference inside
the loop and leaks it before taking the backedge, memmove() shifts the
in-loop reference down to index entry->refs - 1 while entry->refs stays
unchanged. Can this cause check_refs_taken_in_loop() to miss the leaked
in-loop reference at the backedge, and should loop_stack_safe() in
kernel/bpf/states.c also check old_stack[i].refs == cur_stack[i].refs to
match join_loop_stack()?

[ ... ]

> @@ -21581,14 +21663,174 @@ int bpf_flow_loop_enter(struct bpf_verifier_env *env, bool *backedge, bool *drop

[ ... ]

> +static int check_loop_guard(struct bpf_verifier_env *env)
> +{
> +	struct bpf_insn_aux_data *aux = &env->insn_aux_data[env->insn_idx];
> +	struct bpf_verifier_state *branch;
> +	struct bpf_func_state *frame = cur_func(env);
> +	struct loop_stack_entry *entry;
> +	struct bpf_loop *loop;
> +	int h, err;
> +
> +	h = bpf_loop_at_index(env, env->insn_idx);
> +	/* The callback came back to the helper that calls it: the program is not in front of it. */
> +	if (h < 0 || !frame->loop_stack_cnt || frame->callback_depth)
> +		return 0;
> +	loop = env->insn_aux_data[h].loop;
> +	entry = &frame->loop_stack[frame->loop_stack_cnt - 1];
> +	if (loop->rt_bounded || !env->insn_aux_data[env->insn_idx].guard_place ||
> +	    entry->loop_id != h)
> +		return 0;
> +	if (verifier_bug_if(!entry->terminates && !entry->guarded, env,
> +			    "nothing stops the loop at %d", h))
> +		return -EFAULT;
> +	if (!entry->guarded && !bpf_loop_walk_may_give_up(entry))
> +		return 0;
> +
> +	/* the device runs the insns that the driver was given, without may_goto */
> +	if (bpf_prog_is_offloaded(env->prog->aux)) {
> +		verbose(env, "loop at insn %d has no known bound in an offloaded program\n", h);
> +		return -EINVAL;
> +	}

[Severity: Medium]
As reported by bot+bpf-ci@kernel.org on v2 [4], when bpf_compute_loop_iters()
returns 0 and bpf_flow_loop_enter() starts a patience walk via
flow_try_walk(), entry->apart = true, entry->terminates = true,
entry->counted = false, and entry->guarded remains false unless the walk later
gives up.

Because bpf_loop_walk_may_give_up(entry) is true during the walk, doesn't
check_loop_guard() reject offloaded programs with -EINVAL on the very first
iteration of the walk, before the walk has a chance to reach the end of the
loop without needing may_goto?

[ ... ]

> @@ -21747,6 +21937,10 @@ static int do_check(struct bpf_verifier_env *env)
>  		if (state->speculative && insn_aux->nospec)
>  			goto process_bpf_exit;
>  
> +		err = check_loop_guard(env);
> +		if (err)
> +			return err;
> +
>  		err = do_check_insn(env, &do_print_state);
>  		if (error_recoverable_with_nospec(err) && state->speculative) {
>  			/* Prevent this speculative path from ever reaching the
> @@ -21768,19 +21962,9 @@ static int do_check(struct bpf_verifier_env *env)
>  		}
>  
>  		if (state->speculative && insn_aux->nospec_result) {
> -			/* If we are on a path that performed a jump-op, this
> -			 * may skip a nospec patched-in after the jump. This can
> -			 * currently never happen because nospec_result is only
> -			 * used for the write-ops
> -			 * `*(size*)(dst_reg+off)=src_reg|imm32` and helper
> -			 * calls. These must never skip the following insn
> -			 * (i.e., bpf_insn_successors()'s opcode_info.can_jump
> -			 * is false). Still, add a warning to document this in
> -			 * case nospec_result is used elsewhere in the future.
> -			 *
> -			 * All non-branch instructions have a single
> -			 * fall-through edge. For these, nospec_result should
> -			 * already work.
> +			/*
> +			 * All non-branch instructions have a single fall-through
> +			 * edge. For these, nospec_result should already work.
>  			 */
>  			if (verifier_bug_if((BPF_CLASS(insn->code) == BPF_JMP ||
>  					     BPF_CLASS(insn->code) == BPF_JMP32) &&
> @@ -21790,23 +21974,40 @@ static int do_check(struct bpf_verifier_env *env)
>  process_bpf_exit:
>  			account_current_path(env);
>  			mark_verifier_state_scratched(env);
> -			err = bpf_update_branch_counts(env, env->cur_state);
> -			if (err)
> -				return err;
> -			err = pop_stack(env, &prev_insn_idx, &env->insn_idx,
> -					pop_log);
> -			if (err < 0) {
> -				if (err != -ENOENT)
> -					return err;
> -				break;
> -			} else {
> -				do_print_state = true;
> -				continue;
> -			}
> +			bpf_free_verifier_state(state, false);
> +			memset(state, 0, sizeof(*state));
> +			return flow_drain(env);
> +		}

[Severity: Medium]
As reported by bot+bpf-ci@kernel.org on v2 [5], when bpf_insert_loop_guards()
prepends a may_goto sequence in front of a guarded instruction,
patch_list_adj_aux() in kernel/bpf/fixups.c copies old->nospec onto the last
instruction of the patch (the original instruction after may_goto), so at
runtime the injected may_goto executes before the BPF_ST_NOSPEC() barrier.

In do_check_block(), however, the early exit on state->speculative &&
insn_aux->nospec runs before check_loop_guard(env), and do_check_all() does
not clear insn_aux->nospec across rounds. Once insn_aux->nospec is set on the
guarded instruction, won't subsequent speculative states reaching it jump to
process_bpf_exit before check_loop_guard() and skip verifying the speculative
may_goto branch?

Conversely, when insn_aux->nospec is not yet set and do_check_insn() fails
with a recoverable error on a speculative path, jumping to process_bpf_exit
calls flow_drain(env), which delivers any states pushed onto env->head by the
failed do_check_insn() call (such as other_branch pushed in
check_cond_jmp_op() before regs_bounds_sanity_check_branches() fails, or
callback states pushed in push_callback_call() before a later check fails).
Shouldcheck_loop_guard() run before the insn_aux->nospec check, and should
states pushed by a failed speculative do_check_insn() be discarded instead of
drained?

[ ... ]

> @@ -23196,6 +23400,44 @@ static int do_check_main(struct bpf_verifier_env *env)
>  	return ret;
>  }
>  
> +/*
> + * What stops a loop is assumed before the main pass and checked in it, see flow_is_bound(). The
> + * main prog and global functions may get to the same loop. It has may_goto for all of them or
> + * for none, so all are done again when the assumption doesn't hold, whatever came out.
> + * The same when a loop gets may_goto, or its may_goto gets another way out, and what went through
> + * the loop before is not there any more, see bpf_flow_loop_gets_guards().
> + *
> + * A round that is dropped counts as paths that never run. What it found out about the insns, the
> + * subprogs and the prog stays. Each of these is made for more than one state that gets to an insn:
> + * it grows to the safe side, or another value is refused, or the last one that gets there sets it.
> + * Where the round got to is dropped with its verdict: the passes that follow take an insn that was
> + * seen for one that passed its checks, and a function that is called has to be safe.
> + */
> +static int do_check_all(struct bpf_verifier_env *env)
> +{
> +	struct bpf_func_info_aux *sub_aux;
> +	u64 log_pos = env->log.end_pos;
> +	int i, ret;
> +
> +	for (;;) {
> +		bpf_flow_new_round(env);
> +		ret = do_check_main(env);
> +		ret = ret ?: do_check_subprogs(env);
> +		if (!(env->restart && bpf_flow_loops_lost_bound(env)) && !env->guards_late)
> +			return ret;
> +		/* the log is dropped when a function is found to be safe */
> +		bpf_vlog_reset(&env->log, min(log_pos, env->log.end_pos));
> +		for (i = 0; i < env->prog->len; i++)
> +			env->insn_aux_data[i].seen = 0;
> +		for (i = 1; env->prog->aux->func_info && i < env->subprog_cnt; i++) {
> +			sub_aux = subprog_aux(env, i);
> +			memset(sub_aux->called, 0, sizeof(sub_aux->called));
> +			memset(sub_aux->verified, 0, sizeof(sub_aux->verified));
> +			sub_aux->called_with_pkt_ptrs = false;
> +		}
> +	}
> +}

[Severity: Medium]
As reported by Sashiko on v2 [6], when do_check_all() restarts verification
for a new round, it clears env->insn_aux_data[i].seen = 0 and calls
bpf_flow_new_round(env), which resets guard_edge_dropped and no_guard_edges,
but neither resets env->insn_aux_data[i].loop_guard = false (or
env->total_states).

If bpf_flow_guard_edge() sets aux[i].loop_guard = true during round 1 on a
path or static subprogram that becomes unreachable in round 2,
bpf_insert_loop_guards() and append_budget_exit() in kernel/bpf/fixups.c will
still see aux[i].loop_guard == true even though aux[i].seen == 0, patching
may_goto at a dead instruction and setting seen = 1 on the appended budget
exit instructions of an otherwise dead subprogram.

In addition, if a fatal error such as -EAGAIN, -ENOMEM, -EFAULT, or -E2BIG
occurs after env->guards_late or env->restart was set earlier in the round,
won't do_check_all() ignore ret, reset the verifier log, and start another
round instead of returning the error immediately?

[1] https://lore.kernel.org/r/20261105204513.2230344-20-alexei.starovoitov@gmail.com
[2] https://lore.kernel.org/r/20261105204513.2230344-20-alexei.starovoitov@gmail.com
[3] https://lore.kernel.org/r/20261105204513.2230344-20-alexei.starovoitov@gmail.com
[4] https://lore.kernel.org/r/30511ed9caaa7fab02343ad6adbd72f0c7d689b7ae89d4b0c37bdf2beb45a414@mail.kernel.org
[5] https://lore.kernel.org/r/30511ed9caaa7fab02343ad6adbd72f0c7d689b7ae89d4b0c37bdf2beb45a414@mail.kernel.org
[6] https://lore.kernel.org/r/20261105204513.2230344-20-alexei.starovoitov@gmail.com

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261106035111.3315285-1-alexei.starovoitov@gmail.com?part=19