Re: [PATCH bpf-next 4/8] bpf: Detect loops that never exit

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] bpf: bpf_throw() in subprogram fails to mark caller's loop as exited
- [Medium] bpf: infinite loops bypass detection due to flawed branches == 0 check
--

commit 62aaae8d61f9848eafade71feeeed8eb13c4f0d6
Author: Alexei Starovoitov <ast@kernel.org>

bpf: Detect loops that never exit

This commit introduces detection of infinite loops in BPF programs by tracking
whether a loop was ever exited during verification. It adds state tracking via
visit->exited and marks states as exited using bpf_scc_mark_exit().

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index 22987ce070e74..39e6052922e59 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
[ ... ]
> @@ -221,6 +232,32 @@ static int maybe_exit_scc(struct bpf_verifier_env *env, struct bpf_verifier_stat
>  	return propagate_backedges(env, visit);
>  }
>  
> +/*
> + * @st left the loop that @insn_idx of its current frame is in. The loop is
> + * left when the frame that bpf_scc_visit is for leaves it. Loops in callees
> + * of that frame are part of one trip around the loop of the caller.
> + */
> +void bpf_scc_mark_exit(struct bpf_verifier_env *env, struct bpf_verifier_state *st, int insn_idx)
> +{
> +	struct bpf_scc_callchain *callchain = &env->callchain_buf;
> +	struct bpf_scc_visit *visit;
> +	u32 i, callsite;
> +
> +	if (st->speculative || !env->insn_aux_data[insn_idx].scc)
> +		return;
> +	memset(callchain, 0, sizeof(*callchain));
> +	for (i = 0; i < st->curframe; i++) {
> +		callsite = bpf_frame_insn_idx(st, i);
> +		if (env->insn_aux_data[callsite].scc)
> +			return;

[Severity: High]
Does this early return prevent caller loops from being marked as exited during
a global stack-unwinding event like bpf_throw()? 

If a BPF program loop calls a subprogram, and the subprogram calls bpf_throw(),
the verifier processes PROCESS_BPF_EXIT in do_check():

    } else if (err == PROCESS_BPF_EXIT) {
        /* exit or bpf_throw() inside of a loop */
        if (env->widen_loops)
            bpf_scc_mark_exit(env, state, env->insn_idx);

This invokes bpf_scc_mark_exit() with the instruction index of bpf_throw().
However, since bpf_scc_mark_exit() returns early here if any caller frame
is in an SCC, it fails to mark the caller's loop as exited.

As a result, when the loop's entry state is fully explored, maybe_exit_scc()
finds visit->exited == false and could falsely reject valid programs.

> +		callchain->callsites[i] = callsite;
> +	}
> +	callchain->scc = env->insn_aux_data[insn_idx].scc;
> +	visit = scc_visit_lookup(env, callchain);
> +	if (visit)
> +		visit->exited = true;
> +}
[ ... ]
> @@ -1462,6 +1499,9 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
>  		if (states_equal(env, &sl->state, cur, loop ? RANGE_WITHIN : NOT_EXACT)) {
>  hit:
>  			sl->hit_cnt++;
> +			/* what follows the old state was seen, it may leave the loop */
> +			if (env->widen_loops && !sl->state.branches)
> +				bpf_scc_mark_exit(env, cur, insn_idx);

[Severity: Medium]
Does this logic correctly handle paths that only loop back and prune?

The assumption here seems to be that an explored state (branches == 0) must
have successfully left the loop. However, a state can reach branches == 0
simply because all its paths looped back to the widened loop head and pruned.

If an infinite loop explores such a path, and a subsequent path hits one of
the first path's intermediate states, this logic will prematurely set
visit->exited = true. Will this bypass the verifier's static infinite loop
detection and incorrectly accept the program?

>  
>  			/* if previous state reached the exit with precision and
>  			 * current state is equivalent to it (except precision marks)

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