Re: [PATCH bpf 1/2] bpf: Keep the valid bytes of a packet pointer in scalar evolution

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Critical] bpf: out-of-bounds packet range in sync_widened_reg() when r64 crosses zero
- [Critical] bpf: missing range reset in bpf_clamp_scev_regs() corrupts packet range
- [High] bpf: verifier_bug() in bpf_reg_union() when sync_widened_reg() mutates range
--

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

bpf: Keep the valid bytes of a packet pointer in scalar evolution

This patch updates sync_widened_reg() in bpf_set_reg_range() and
bpf_reg_union() to reduce reg->range when reg_bounds_sync() lowers umax on a
widened packet pointer, and clears negative pkt_end marks in
bpf_widen_scev_regs().

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> index 04d4962448e27..f28eddd17d78f 100644
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c
> @@ -2838,6 +2838,9 @@ int bpf_widen_scev_regs(struct bpf_verifier_env *env, struct bpf_verifier_state
>  				bpf_log(log, "\n");
>  			}
>  			scratch_widened_reg_id(env, reg);
> +			/* "at pkt_end" and "beyond pkt_end" are not valid in all iterations */
> +			if (type_is_pkt_pointer(reg->type))
> +				reg->range = max(reg->range, 0);
>  			err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32,
>  						bounds.base, bounds.step);

[Severity: Critical]
Should bpf_clamp_scev_regs() also reset reg->range from entry_reg (i.e.
max(entry_reg->range, 0)) before calling bpf_set_reg_range()?

On every loop backedge, do_check() -> handle_loop_entry_exit() ->
maybe_clamp_scev_regs() -> bpf_clamp_scev_regs() recomputes bounds from the
pre-widen loop-entry register entry_reg and calls bpf_set_reg_range() ->
sync_widened_reg(reg) on the current state's reg without resetting
reg->range:

kernel/bpf/scev.c:bpf_clamp_scev_regs() {
    ...
		linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
		...
		scratch_widened_reg_id(env, reg);
		err = bpf_set_reg_range(env, reg, bounds.r64, bounds.r32,
					bounds.base, bounds.step);
    ...
}

This appears to cause two regressions on loop backedges:

1. Stale loop-body range leading to out-of-bounds packet access:
Suppose before a 2-iteration loop r6 = pkt has r64 = [0, 0] and range = 0
(widened at the header to r64 = [0, 8], range = 0), and inside the loop body
r6 += 8 advances r6 to r64 = [8, 16] followed by if r6 > pkt_end goto exit.
find_good_pkt_pointers() sets r6->range = reg_umax(r6) = 16 (representing 0
valid bytes past r6, since iteration 0 only proved pkt + 8 <= pkt_end).

When the backedge returns to the loop header, bpf_clamp_scev_regs() resets
r6->r64 back to [0, 8] (umax = 8) while leaving r6->range = 16 from the loop
body. If the backedge state is not pruned at the header (for example, when
another register or stack slot changes), iteration 1 executes at the header
with r6 having umax = 8 and range = 16 (8 valid bytes), allowing
*(u64 *)(r6 + 0) to read 8 bytes past pkt_end when r6 == pkt + 8 == pkt_end.
Similarly, negative AT_PKT_END or BEYOND_PKT_END marks set inside the loop
body are not cleared by bpf_clamp_scev_regs().

2. Repeated range subtraction preventing loop convergence:
When entry_reg has range = R > 0 before the loop and sync_widened_reg()
lowers umax by d = 2 (for instance, 58 -> 56), bpf_widen_scev_regs() at loop
entry sets the header checkpoint state's rold->range = R - 2. When the
backedge reaches the loop header, the current state's reg enters
bpf_clamp_scev_regs() with reg->range already equal to R - 2.

Because bpf_clamp_scev_regs() recomputes bounds.r64 = [0, 58] from entry_reg
and calls bpf_set_reg_range() -> sync_widened_reg(reg), umax drops from 58
to 56 a second time and sync_widened_reg() subtracts 2 again, setting
rcur->range = R - 4. In kernel/bpf/states.c:regsafe(), rold->range >
rcur->range returns false, preventing state pruning at the loop header and
shrinking reg->range on each pass.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a0a5f075d2018..66d008166f169 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -17768,6 +17768,20 @@ bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a,
>  	}
>  }
>  
> +/*
> + * 'range - umax' bytes from a packet pointer are in the packet. reg_bounds_sync() can make umax
> + * smaller: with a step of 8, or with 3 zero bits in var_off, 58 becomes 56. Make the range
> + * smaller by the same number, so that the number of bytes does not grow.
> + */
> +static void sync_widened_reg(struct bpf_reg_state *reg)
> +{
> +	u64 umax = reg_umax(reg);
> +
> +	reg_bounds_sync(reg);
> +	if (type_is_pkt_pointer(reg->type) && reg->range > 0)
> +		reg->range = max_t(s64, reg->range - (s64)(umax - reg_umax(reg)), 0);
> +}

[Severity: Critical]
Can sync_widened_reg() corrupt reg->range when reg->r64 spans negative and
non-negative offsets (smin < 0 && smax >= 0)?

In kernel/bpf/scev.c:linear_bounds(), when a packet pointer is decremented in
a loop (slope < 0) or starts at a negative offset before the loop,
bounds.r64 = cnum64_from_srange(min_val, max_val) can have min_val < 0 and
max_val >= 0.

In kernel/bpf/cnum_defs.h:cnum64_umax():

ut FN(umax)(struct cnum_t cnum)
{
	return FN(urange_overflow)(cnum) ? UT_MAX : cnum.base + cnum.size;
}

any cnum64 that crosses the U64_MAX/0 boundary returns U64_MAX from
reg_umax(reg). Using reg_umax(reg) in sync_widened_reg() leads to two cases
where check_packet_access() can allow out-of-bounds packet reads or writes
past pkt_end:

1. Range inflation when reg_bounds_sync() rounds smin up to >= 0:
Suppose before a 2-iteration loop:

    r4 &= 0x38
    if r4 < 2 goto exit
    if r4 > 50 goto exit
    r6 = pkt
    r6 += r4
    r5 = r6
    r5 += 8
    if r5 > pkt_end goto exit

so r6 has r64 = [2, 50], var_off = (0; 0x38), range = 58. If the loop body
decrements r6 by 8 (r6 += -8), linear_bounds() produces r64 = [-6, 50],
base = 0, step = 8.

In sync_widened_reg(), umax before reg_bounds_sync(reg) is U64_MAX because
[-6, 50] crosses zero. Then reg_bounds_sync(reg) intersects r64 with step = 8
via __update_bounds_from_step(), narrowing r6->r64 to [0, 48] with
reg_umax(r6) = 48. As a result, (s64)(umax - reg_umax(reg)) evaluates to
(s64)(U64_MAX - 48) = -49, and reg->range - (s64)(umax - reg_umax(reg))
increases r6->range from 58 to 107 instead of reducing it to 56.

2. Failure to shrink range when smin remains < 0:
If the if r4 < 2 goto exit check is omitted above, linear_bounds() produces
r64 = [-8, 50], step = 8, and reg_bounds_sync(reg) tightens r6->r64 to
[-8, 48]. Because smin is still negative, reg_umax(reg) is U64_MAX both
before and after reg_bounds_sync(reg), so umax - reg_umax(reg) is 0 and
r6->range remains 58 instead of shrinking to 56. Inside the loop body,
r5 = r6; r5 += 8 yields r5->r64 = [0, 56] with r5->range = 58, allowing a
2-byte read at r5 + 0 past pkt_end when r4 = 48 and pkt_end = pkt + 56.

>  
>  int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
>  		      struct cnum64 r64, struct cnum32 r32, u16 base, u16 step)
> @@ -17776,7 +17790,7 @@ int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
>  	reg->step = step;
>  	reg->base = base;
>  	reg->var_off = tnum_unknown;
> -	reg_bounds_sync(reg); /* this should infer the tnum alignment */
> +	sync_widened_reg(reg); /* this should infer the tnum alignment */
>  	return reg_bounds_sanity_check(env, reg, "bpf_set_reg_range");
>  }
>  
> @@ -17821,7 +17835,7 @@ int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc,
>  		acc->base = base;
>  		acc->step = step;
>  	}
> -	reg_bounds_sync(acc);
> +	sync_widened_reg(acc);
>  	return reg_bounds_sanity_check(env, acc, "bpf_reg_union");
>  }

[Severity: High]
Does calling sync_widened_reg(acc) inside bpf_reg_union() trigger
verifier_bug(env, "union of incompatible registers") when union_any_reg()
iterates over multiple leaves?

In kernel/bpf/scev.c:union_any_reg(), bpf_reg_union(env, acc, leaf_reg) is
called in a loop for each leaf of an ANY expression. On each call,
bpf_reg_union() checks bpf_reg_union_compatible(acc, src):

kernel/bpf/verifier.c:bpf_reg_union_compatible() {
	if (a->type != b->type)
		return false;
	if (a->type == SCALAR_VALUE)
		return true;
	return !memcmp(a, b, offsetof(struct bpf_reg_state, var_off)) &&
	       a->id == b->id && a->parent_id == b->parent_id && a->map_uid == b->map_uid;
}

which compares a->range and b->range via memcmp().

For example, if at loop entry r6 has id = 1, r64 = [0, 50],
var_off = (0; 0x38), range = 58 and r5 = r6 + 8 has id = 1, r64 = [8, 58],
var_off = (0; 0x78), range = 58, and the loop body sets r5 = r6 so r5 has
SCEV (any r5 r6):

1. is_widenable_any() succeeds because both leaves have id = 1 and
   range = 58.
2. In union_any_reg(), the first leaf (entry_r5) is unioned into acc.
   sync_widened_reg(acc) lowers umax from 58 to 56 via var_off and changes
   acc->range from 58 to 56.
3. On the second leaf (entry_r6, which still has range = 58),
   bpf_reg_union_compatible(acc, entry_r6) sees acc->range (56) !=
   entry_r6->range (58), triggering verifier_bug(env, "union of incompatible
   registers") and returning -EFAULT.

In addition, calling sync_widened_reg(acc) on each leaf in union_any_reg()
can subtract umax reductions multiple times across intermediate leaves, and
the is_any() branch in bpf_widen_scev_regs() does not clear negative
pkt_end marks on reg->range before unioning.

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