Re: [PATCH bpf-next 25/36] bpf: use SCEV to widen bounded loops

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] bpf: verifier bypass due to signed algebraic inversion of unsigned loop conditions
--

commit 457e66d0b00c63117d606a731e93743130f1e826
Author: Eduard Zingerman <eddyz87@gmail.com>
Subject: bpf: use SCEV to widen bounded loops

This commit introduces scalar evolution (SCEV) to the BPF verifier to
estimate loop iteration bounds and widen induction variables. This allows
the verifier to support bounded loops with linear latches and bounds.

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c
[ ... ]
> +static bool compute_max_iters(struct bpf_verifier_env *env,
> +			      struct bpf_func_state *st,
> +			      struct linear_latch *latch,
> +			      struct bpf_loop_iters *iters)
> +{
[ ... ]
> +	if (step == 0)
> +		return false;
> +	if ((s64)step == S64_MIN)
> +		return false;
> +	if ((s64)step < 0) {
> +		/* Multiply both sides of the equation by -1, e.g. -2*i > -3 becomes 2*i < 3 */
> +		op = bpf_flip_opcode(op);
> +		step = -step;
> +		swap(bound, initial);
> +	}

[Severity: Critical]
Does this logic improperly apply a signed algebraic identity to unsigned
comparisons?

Looking at compute_max_iters() in kernel/bpf/scev.c, if a BPF program
constructs a loop with an unsigned continuation condition, initializes
the register to a positive value, and decrements it, the algebraic
inversion treats the counter as if it crosses into negative space.

Could this incorrectly calculate a small iteration count, while at runtime
the unsigned subtraction wraps around to U64_MAX and allows the loop to
continue?

If this wraps, it appears the verifier might widen the register bounds to a
narrow range and prune branches targeting the wrapped values as dead code,
potentially allowing unverified payloads to execute.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260926-scev-minimal-rebase-v1-0-c8e5ab5ba79f@gmail.com?part=25