Re: [PATCH bpf-next 14/36] bpf: representation for intervals with steps

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] bpf: verifier linear equation tracking ignores integer wrap-around leading to OOB access
--

commit e753188b2ce55741938a6a63ee79699c312fb712
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: representation for intervals with steps

Extend scalar register tracking with a linear base + step * k description
to allow the verifier to reason about strided values, updating scalar
ALU operations to maintain these constraints.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 79aa924861548..89b1a0aa3a25b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -2165,10 +2173,16 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
>  	reg->r64 = cnum64_cnum32_intersect(reg->r64, reg->r32);
>  }
>  
> +static void deduce_bounds_64_from_step(struct bpf_reg_state *reg)
> +{
> +	reg->r64 = cnum64_intersect_linear(reg->r64, reg->base, reg->step);
> +}

[Severity: Critical]
If the base and step variables become desynchronized from the true runtime
value during ALU operations, could this intersection incorrectly shrink the
register bounds?

If the linear representation is mathematically flawed due to integer
wrap-around, the verifier might deduce bounds that exclude the actual runtime
value.

Is it possible this leads to out-of-bounds accesses bypassing checks?

[ ... ]

> @@ -15589,6 +15615,50 @@ static int sanitize_check_bounds(struct bpf_verifier_env *env,
>  	return 0;
>  }
>  
> +static void scalar_step_add(struct bpf_reg_state *dst_reg,
> +			    const struct bpf_reg_state *a,
> +			    const struct bpf_reg_state *b)
> +{
> +	u16 base, step;
> +
> +	/* If either 'a' or 'b' is a constant, update the base/step for the counterpart. */
> +	if (tnum_is_const(b->var_off)) {
> +		step = a->step;
> +		base = imod((s64)a->base + (s64)b->var_off.value, step);
> +	} else if (tnum_is_const(a->var_off)) {
> +		step = b->step;
> +		base = imod((s64)b->base + (s64)a->var_off.value, step);

[Severity: Critical]
Does this computation account for 32-bit or 64-bit integer wrap-around?

If a register is initialized with a non-power-of-2 stride (for example, base=0
and step=3), and then undergoes an addition that wraps around 32 bits, the
true remainder modulo 3 changes because 2^32 is not divisible by 3.

Since this computes imod() on the 64-bit sum, the tracking might blindly
ignore boundary wrap-around, leading to an inaccurate linear representation.

Furthermore, in adjust_scalar_min_max_vals(), when alu32 is true, the function
calls zext_32_to_64() which zero-extends the 32-bit result without
invalidating the 64-bit base and step tracking.

Could this allow a crafted BPF program to bypass bounds checks?

> +	} else {
> +		step = 1;
> +		base = 0;
> +	}
> +	dst_reg->base = base;
> +	dst_reg->step = step;
> +}
> +
> +static void scalar_step_mul(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg)
> +{
> +	u64 amount = src_reg->var_off.value;
> +
> +	if (tnum_is_const(src_reg->var_off) && (s64)amount >= 0 &&
> +	    !check_mul_overflow(dst_reg->step, amount, &dst_reg->step) &&

[Severity: Critical]
This code checks if the step value overflows a u16, but it does not appear to
verify if the register actual value multiplication wraps around 64 bits or
32 bits.

If the underlying integer multiplication wraps, the linear equation might
no longer accurately reflect the actual value of the register.

Could this also lead to an incorrect linear equation being propagated?

> +	    dst_reg->step != 0)
> +		dst_reg->base = (dst_reg->base * amount) % dst_reg->step;
> +	else
> +		reg_step_reset(dst_reg);
> +}

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