Re: [PATCH bpf-next v4 32/46] bpf: A loop is one iteration shorter behind the jump that counts it

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [High] bpf: signed overflow and stride corruption on moved in
  bpf_clamp_scev_regs()
--

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

bpf: A loop is one iteration shorter behind the jump that counts it

This commit narrows the SCEV-derived register ranges by one iteration on the
fall-through path behind a loop-counting exit jump, including registers to
which the current iteration has already added a constant offset.

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> index 06f485853df13..4ce8ad5d5a279 100644
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c

[ ... ]

> @@ -3878,8 +3910,22 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
>  			continue;
>  clamp:
>  		linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
> -		if (r == entry->iv_reg)
> +		if (r == entry->iv_reg && !moved)
>  			iv_bounds(&bounds, entry->iv_range);
> +		if (moved) {
> +			bounds.r64 = cnum64_add(bounds.r64, cnum64_from_srange(moved, moved));
> +			bounds.base = imod(bounds.base + moved, bounds.step);
> +		}

[Severity: High]
Can shifting bounds by moved here corrupt bounds.base and bounds.step when
bounds.step is not a power of two?

When entry_reg is a constant scalar, linear_bounds() sets bounds.step to
|slope| (up to S16_MAX) and tracks the signed congruence x mod step == base.
If adding moved to cnum64_smin(bounds.r64) or cnum64_smax(bounds.r64) wraps
s64, 64-bit addition shifts the signed values by +/- 2^64, which is not a
multiple of a non-power-of-two step, so the wrapped range in bounds.r64 no
longer has remainder imod(bounds.base + moved, bounds.step).  Passing the
mismatched bounds.base and bounds.step to bpf_set_reg_range() ->
cnum64_intersect_linear() can then narrow reg to a bogus constant that the
register never holds at runtime, or collapse it to CNUM64_EMPTY and hit
verifier_bug().

In addition, bounds.base + moved is evaluated in signed 64-bit arithmetic and
can overflow s64 when moved is near S64_MAX (with bounds.base > 0), unlike
scalar_step_add():

kernel/bpf/verifier.c:scalar_step_add() {
	...
	if (check_add_overflow(reg_smin(reg), amount, &tmp) ||
	    check_add_overflow(reg_smax(reg), amount, &tmp)) {
		reg_step_reset(dst_reg);
		return;
	}

	dst_reg->base = (reg->base + imod(amount, reg->step)) % reg->step;
	dst_reg->step = reg->step;
}

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