Re: [PATCH bpf-next v3 04/12] bpf: Track low-32 scalar equality across zero-extending movs

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: empty or corrupted range after intersection in sync_linked_regs()
--

commit 05d23d7192de1c6009703f8fbe1537ad78dda89e
Author: Vineet Gupta <vineet.gupta@linux.dev>

bpf: Track low-32 scalar equality across zero-extending movs

This commit extends linked-scalar tracking across zero-extending 32-bit moves
from wide 64-bit source registers using BPF_REG_LINK_ZEXT. Because a wide base
cannot be inverted across all 64 bits, sync_linked_regs() propagates bounds
forward only and intersects the derived bounds with the destination register's
existing state.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b9c20a5cc6d6f..6afd718ede647 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -18749,6 +18798,27 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s
>  			if (reg->link_kind == BPF_REG_LINK_ZEXT ||
>  			    known_reg->link_kind == BPF_REG_LINK_ZEXT)
>  				zext_32_to_64(reg);
> +			/*
> +			 * Intersect rather than overwrite. A BPF_REG_LINK_ZEXT
> +			 * link over a wide base does not propagate back, so the
> +			 * base can be wider than what @reg has already proved
> +			 * about itself; replacing it would lose that.
> +			 */
> +			cnum64_intersect_with(&reg->r64, prev.r64);
> +			cnum32_intersect_with(&reg->r32, prev.r32);
> +			reg->var_off = tnum_intersect(reg->var_off, prev.var_off);
> +			/*
> +			 * An empty intersection means the two sides contradict,
> +			 * so this path is unreachable. Say nothing rather than
> +			 * say it with an empty range: reg_bounds_sync() below
> +			 * refuses to touch one, and the first later
> +			 * reg_bounds_sanity_check() would report it as a
> +			 * verifier bug, which it is not. Keeping the wider
> +			 * pre-intersect state only costs precision on a path
> +			 * that cannot be taken.
> +			 */
> +			if (range_bounds_violation(reg))
> +				*reg = prev;
>  			reg_bounds_sync(reg);
>  		}
>  		if (e->is_reg)

[Severity: Medium]
Can a contradiction in var_off or linear step still leave an empty range on
reg, or corrupt reg into a bogus constant, after sync_linked_regs() finishes?

First, tnum_intersect() in kernel/bpf/tnum.c assumes its arguments overlap:

/* Note that if a and b disagree - i.e. one has a 'known 1' where the other has
 * a 'known 0' - this will return a 'known 1' for that bit.
 */
struct tnum tnum_intersect(struct tnum a, struct tnum b)
{
	u64 v, mu;

	v = a.value | b.value;
	mu = a.mask & b.mask;
	return TNUM(v & ~mu, mu);
}

When reg->var_off and prev.var_off disagree on a known bit without
tnum_overlap(reg->var_off, prev.var_off) being checked first, tnum_intersect()
turns the conflicting bit into a known 1.

Second, range_bounds_violation(reg) only checks cnum32_is_empty(reg->r32) ||
cnum64_is_empty(reg->r64), and is only called before reg_bounds_sync(reg). Any
contradiction between the intersected r64/r32 ranges and var_off (via
__update_reg_bounds()) or base/step (via __update_bounds_from_step()) happens
inside reg_bounds_sync(reg), after the range_bounds_violation(reg) check has
already passed.

For example, in a socket filter:

  w7 = w6;                /* r6 is unknown 64-bit; r7 gets BPF_REG_LINK_ZEXT */
  if w7 < 4 goto out;
  if w7 > 5 goto out;
  if w7 & 2 goto out;     /* r7: r64=[4, 5], var_off=(0x4; 0x1) */
  if r6 & 2 goto l1;

At l1, r6 has var_off=(0x2; ~2ULL), so after zext_32_to_64(reg), reg has
r64=[2, U32_MAX] and var_off=(0x2; 0xfffffffd). Intersecting r64 and r32 with
prev produces [4, 5], which is non-empty, so range_bounds_violation(reg) is
false. However, tnum_intersect() produces (0x6; 0x1) ([6, 7]), and
reg_bounds_sync(reg) then intersects [4, 5] with [6, 7], leaving reg->r64 and
reg->r32 empty and triggering a verifier warning on a subsequent r7 %= r9 (with
r9 = 0).

Worse, if w7 was narrowed to a single constant 4 (r64=[4, 4],
var_off=(0x4; 0x0)) before "if r6 & 2 goto l1", tnum_intersect() fabricates
the constant var_off=(0x6; 0x0). Inside
reg_bounds_sync()->__update_reg_bounds()->__update_reg64_bounds():

	cnum64_intersect_with(&reg->r64, cnum64_from_tnum(reg->var_off));

	/* Check if u64 and tnum overlap in a single value */
	tnum_next = tnum_step(reg->var_off, reg_umin(reg));
	umin_in_tnum = (reg_umin(reg) & ~reg->var_off.mask) == reg->var_off.value;
	tmax = reg->var_off.value | reg->var_off.mask;
	if (umin_in_tnum && tnum_next > reg_umax(reg)) {
		___mark_reg_known(reg, reg_umin(reg));
	} else if (!umin_in_tnum && tnum_next == tmax) {
		___mark_reg_known(reg, tmax);
	}

cnum64_intersect_with() sets reg->r64 to CNUM64_EMPTY, where reg_umin(reg)
returns 0 and reg_umax(reg) returns U64_MAX. That satisfies !umin_in_tnum &&
tnum_next == tmax (6 == 6) and calls ___mark_reg_known(reg, 6), overwriting
r7 == 4 with the contradicted constant r7 == 6.

Even when tnum_overlap(reg->var_off, prev.var_off) holds, reg_bounds_sync(reg)
can still empty r64/r32 if the intersected cnum range and intersected tnum (or
base/step in __update_bounds_from_step()) have no common points.

Should sync_linked_regs() verify tnum_overlap(reg->var_off, prev.var_off)
before calling tnum_intersect(), and also check range_bounds_violation(reg)
after reg_bounds_sync(reg) to restore *reg = prev?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261020161907.2115379-1-vineet.gupta@linux.dev?part=4