Re: [PATCH bpf-next v2 20/29] bpf: Find a copy of an induction variable without scalar ids

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [High] bpf: type confusion between pointer and scalar bounds in
  is_iv_at_header()
--

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

bpf: Find a copy of an induction variable without scalar ids

This commit replaces COPY_SCEV and scalar ID checks for induction variable
copies with untyped expression comparisons via const_diff_at_header().

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> index 98a05f97196a6..28fd06c16fe4d 100644
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c

[ ... ]

> @@ -4585,6 +4518,19 @@ static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count,
>  	out->r32 = r32;
>  }
>  
> +/*
> + * Is @r the induction variable that the latch tests, or congruent to it: equal to it at the header
> + * of the loop at @h in every iteration? Then the range of the one is the range of the other.
> + */
> +static bool is_iv_at_header(struct bpf_verifier_env *env, int h, int iv_reg, u32 r)
> +{
> +	s64 delta;
> +
> +	if (iv_reg < 0)
> +		return false;
> +	return r == iv_reg || (const_diff_at_header(env, h, iv_reg, r, &delta) && !delta);
> +}
> +
>  static void iv_bounds(struct bounds *bounds, struct cnum64 iv_range)
>  {
>  	struct cnum64 r64 = cnum64_intersect(bounds->r64, iv_range);

[ ... ]

> @@ -5128,7 +5074,7 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state
>  			if (err)
>  				return err;
>  			linear_bounds(reg, iters->max_header_count, &coefs, &bounds);
> -			if (coefs.base_reg == iters->iv_reg)
> +			if (is_iv_at_header(env, insn_idx, iters->iv_reg, coefs.base_reg))
>  				iv_bounds(&bounds, iters->iv_range);
>  			if (log->level & BPF_LOG_LEVEL2) {
>  				bpf_log(log, "loop header at %d, widening ", insn_idx);

[ ... ]

> @@ -5251,7 +5196,11 @@ 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 (coefs.base_reg == entry->iv_reg && !moved)
> +		/*
> +		 * iv_range is the range at the header. After the latch @r can be the zero extension
> +		 * of its header value. @reg went through that insn and has what holds of the range.
> +		 */
> +		if (!behind && is_iv_at_header(env, insn_idx, entry->iv_reg, coefs.base_reg))
>  			iv_bounds(&bounds, entry->iv_range);
>  		if (moved) {
>  			/* a sum that can wrap has another residue, see scalar_step_add() */

[Severity: High]
Can is_iv_at_header() apply a pointer induction variable's offset range
(iv_range) to a congruent SCALAR_VALUE register?

const_diff_at_header() compares untyped SCEV expressions without checking
that iv_reg and r have the same register type in the loop-entry state.  In
transfer(), a no-op 64-bit BPF_ALU | BPF_END (such as le64 on a
little-endian host) leaves reg2expr[dst] unchanged:

kernel/bpf/scev.c:transfer() {
    ...
			need_bswap = class == BPF_ALU64 || ((x_or_k == BPF_TO_LE) != little_endian);
			switch (insn->imm) {
			case 16: op = need_bswap ? BSWAP16 : ZEXT16; break;
			case 32: op = need_bswap ? BSWAP32 : ZEXT32; break;
			case 64: op = need_bswap ? BSWAP64 : 0; break;
    ...
			id = reg2expr[dst];
			if (op)
				id = expr1(scev, op, reg2expr[dst]);

			return replace_reg(scev, e, dst, id);
}

When env->allow_ptr_leaks is enabled, check_alu_op() degrades a pointer
register passed to that instruction to an unknown SCALAR_VALUE while the
instruction preserves the raw 64-bit pointer value at runtime.

If iv_reg is a pointer induction variable (for example PTR_TO_MAP_VALUE
with offset in [1, 10]) and r is copied from iv_reg and passed through a
64-bit no-op BPF_END both before the loop and on the backedge,
compute_header_scevs() and is_iv_at_header() treat r as congruent to
iv_reg.  bpf_widen_scev_regs() and bpf_clamp_scev_regs() then intersect
r's scalar bounds with iv_range, causing the verifier to bound a register
holding a raw 64-bit kernel pointer to the small scalar range [1, 10] and
allowing out-of-bounds memory access.

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