[PATCH RFC bpf-next 0/7] bpf: Fix reg_bounds' slow mode and improve verifier refinement

[PATCH RFC bpf-next 0/7] bpf: Fix reg_bounds' slow mode and improve verifier refinement

[Paul Chaignon]

This patchset fixes several failing test cases in the slow-mode
reg_bounds selftests. It also includes an improvement to the verifier
u32->*64 refinement logic, to help better align it with reg_bounds'
refinement logic.

I'm sending as an RFC because it needs [1] to be merged first. The two
patches from [1] are included here, before my fixes.

Patch "bpf: Improve 64bits bounds refinement from u32 bounds" also
happens to address the refinement shortcomings discussed at [2]. To
demonstrate that, I included the new selftests from [2] at the end of
this series.

1: https://lore.kernel.org/all/20260415160728.657270-1-harishankar.vishwanathan@gmail.com/
2: https://lore.kernel.org/all/20260410124035.297632-1-koike@igalia.com/

Harishankar Vishwanathan (1):
  bpf/verifier: Use intersection checks when simulating to detect dead
    branches

Paul Chaignon (5):
  selftests/bpf: Test for empty intersection of tnum and u64
  selftests/bpf: Fix reg_bounds to prune on range violations
  bpf: Improve 64bits bounds refinement from u32 bounds
  bpf: Remove dead code from u32->*64 refinement logic
  selftests/bpf: Hardcode insteresting 32->64 refinement cases

Eduard Zingerman (1):
  selftests/bpf: new cases handled by 32->64 range refinements

 kernel/bpf/verifier.c                         | 299 +++++++++++++++---
 .../selftests/bpf/prog_tests/reg_bounds.c     |  38 ++-
 .../selftests/bpf/progs/verifier_bounds.c     | 202 ++++++++++++
 3 files changed, 482 insertions(+), 57 deletions(-)

-- 
2.43.0

[PATCH RFC bpf-next 1/7] bpf/verifier: Use intersection checks when simulating to detect dead branches

[Paul Chaignon]

From: Harishankar Vishwanathan <harishankar.vishwanathan@gmail.com>

This commit introduces checks to detect if the ranges and/or tnums have
intersections between them, and uses the checks in
simulate_both_branches_taken and reg_bounds_sync.

The verifier is known to evolve the reg_states correctly (i.e. soundly)
on a live branch. In a previous commit [1], we used the ill-formedness
of a range (e.g. umin > umax), identified by range_bounds_violation, to
detect dead branches and prune the branch along which the ill-formedness
occurs.

Another opportunity to prune branches is when the ranges and/or tnums
have don't intersect. When the verifier evolves the reg_state along a
dead branch, it is possible that abstract value in one domain (e.g tnum)
doesn't match with the abstract value in the other domain (e.g. u64), so
that there is no single value x, that is contained in both the abstract
values.

First, we introduce intersection checks for each of the 5 domains (for a
total of 10 domain pairs), and wrap it in reg_bounds_intersect.

Next, in simulate_both_branches_taken, we use reg_bounds_intersect
instead of the existing range_bounds_violation to detect dead branches.
Because the new check in reg_bounds_intersect also checks for
range_bounds_violation, we are strictly increasing the detection of dead
branches when using the new check.

Finally, this commit also replaces the early exit in reg_bounds_sync. In
an older commit [2] we detected invalid inputs to reg_bounds_sync using
range_bounds_violation, i.e. checking for ill-formed ranges (e.g. umin >
umax), and exited early. If the inputs to reg_bounds_sync do not have
any intersection, they are also invalid. This way, we ensure that
subsequent operations in reg_bounds_sync don't inadvertently "fix" the
reg_state to become valid. This is important for example, when we
simulate_both_branches_taken; the call to reg_bounds_sync won't fix the
reg_state bounds, so we can still detect dead branches using
reg_bounds_intersect.

[1] commit b254c6d816e5 ("bpf: Simulate branches to prune based on range violations")
[2] commit a2a14e874b4e ("bpf: Exit early if reg_bounds_sync gets invalid inputs")

Signed-off-by: Harishankar Vishwanathan <harishankar.vishwanathan@gmail.com>
---
 kernel/bpf/verifier.c | 213 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 208 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9e4980128151..1d5d2b7e5140 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2345,12 +2345,15 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
 	reg->var_off = tnum_or(tnum_clear_subreg(var64_off), var32_off);
 }
 
-static bool range_bounds_violation(struct bpf_reg_state *reg);
+static bool reg_bounds_intersect(struct bpf_reg_state *reg);
 
 static void reg_bounds_sync(struct bpf_reg_state *reg)
 {
-	/* If the input reg_state is invalid, we can exit early */
-	if (range_bounds_violation(reg))
+	/* If the input reg_state has no intersection between abstract values, it is
+	 * invalid. We can exit early, ensuring that subsequent operations don't
+	 * inadvertently fix the reg_state.
+	 */
+	if (!reg_bounds_intersect(reg))
 		return;
 	/* We might have learned new bounds from the var_off. */
 	__update_reg_bounds(reg);
@@ -2397,6 +2400,206 @@ static bool const_tnum_range_mismatch_32(struct bpf_reg_state *reg)
 	       reg->s32_min_value != sval32 || reg->s32_max_value != sval32;
 }
 
+/*
+ * Check if a reg_state's bounds in all domains (u64, s64, u32, s32, tnum)
+ * intersect. This ensures that for every pair of abstract values, there is
+ * *at least one* value x, such that x is a member of both abstract values.
+ * If there is no intersection between *any* pair of abstract values (10 pairs
+ * from the five domains), return false. Otherwise, return true.
+ */
+static bool reg_bounds_intersect(struct bpf_reg_state *reg)
+{
+	u64 umin = reg->umin_value, umax = reg->umax_value;
+	s64 smin = reg->smin_value, smax = reg->smax_value;
+	u32 u32_min = reg->u32_min_value, u32_max = reg->u32_max_value;
+	s32 s32_min = reg->s32_min_value, s32_max = reg->s32_max_value;
+	struct tnum t = reg->var_off;
+	struct tnum t32 = tnum_subreg(t);
+	u64 tmin = t.value, tmax = t.value | t.mask;
+	u32 t32_min = t32.value, t32_max = t32.value | t32.mask;
+
+	/*
+	 * If the min > max, then the range itself is ill-formed, so there can be no
+	 * intersection in abstract values across domains.
+	 */
+	if (range_bounds_violation(reg))
+		return false;
+
+	/*
+	 * If the var_off is ill-formed, there can be no intersection in abstract
+	 * values across domains.
+	 */
+	if ((t.value & t.mask) != 0)
+		return false;
+
+	/*
+	 * Intersect u64 with s64. We map the s64 range to u64 domain and check if
+	 * there is an intersection. If s64 range does not cross the -1/0 sign
+	 * boundary, then we can treat it as a u64 range and check if its bounding
+	 * values are outside the u64 range. If s64 range crosses the sign boundary,
+	 * then it spans the u64 intervals [0, smax] and [smin, U64_MAX].
+	 * Intersection exists if the u64 range overlaps either of these components.
+	 */
+	if ((u64)smin <= (u64)smax) { /* s64 does not cross the sign boundary */
+		if ((u64)smax < umin || umax < (u64)smin)
+			return false;
+	} else {
+		if ((u64)smin > umax && (u64)smax < umin)
+			return false;
+	}
+
+	/*
+	 * Intersect u64 with tnum. If the bounding values of tnum when mapped to
+	 * the u64 domain are outside the bounding values of u64, there is no
+	 * intersection. However, it is also possible that the tnum "jumps over" the
+	 * u64, making the u64 range lie entirely "in-between" the tnum:
+	 *
+	 * u64:  ----[xxxxxx]------
+	 * tnum: -x-----------x----
+	 *
+	 * In this case, if the next tnum value after umin is beyond umax, there is
+	 * no intersection.
+	 */
+	if (tmax < umin || tmin > umax)
+		return false;
+	if (t.value != (umin & ~t.mask)) {
+		if (tnum_step(t, umin) > umax)
+			return false;
+	}
+
+	/*
+	 * Intersect s64 with tnum. Similar to u64-tnum, but we map s64 to u64
+	 * domain and check if there is an intersection with tnum. If s64 range does
+	 * not cross the -1/0 sign boundary, we can treat it as a normal u64 range
+	 * and check intersection with the tnum as above. If s64 range crosses
+	 * the sign boundary, it spans the u64 intervals [0, smax] and [smin,
+	 * U64_MAX]. Intersection exists if the tnum overlaps either of these
+	 * components. The tnum cannot "jump over" either of these two intervals,
+	 * because they contain endpoints 0 and U64_MAX respectively. So it is
+	 * sufficient to check if the bounding values of tnum are outside the
+	 * bounding values of the mapped s64.
+	 */
+	if ((u64)smin <= (u64)smax) { /* s64 does not cross the sign boundary */
+		if (tmax < (u64)smin || tmin > (u64)smax)
+			return false;
+		if (t.value != ((u64)smin & ~t.mask)) {
+			if (tnum_step(t, (u64)smin) > (u64)smax)
+				return false;
+		}
+	} else { /* s64 crosses the sign boundary */
+		if (tmin > (u64)smax && tmax < (u64) smin)
+			return false;
+	}
+
+	/* Intersect u32 with s32. This case is similar to u64-s64 */
+	if ((u32)s32_min <= (u32)s32_max) {
+		if ((u32)s32_max < u32_min || u32_max < (u32)s32_min)
+			return false;
+	} else {
+		if ((u32)s32_min > u32_max && (u32)s32_max < u32_min)
+			return false;
+	}
+
+	/* Intersect u32 with tnum. This case is similar to u64-tnum */
+	if (t32_min > u32_max || t32_max < u32_min)
+		return false;
+	if ((t32.value != (u32_min & ~t32.mask)) && (tnum_step(t32, u32_min) > u32_max))
+		return false;
+
+	/* Intersect s32 with tnum. This case is similar to s64-tnum */
+	if ((u32)s32_min <= (u32)s32_max) {
+		if (t32_min > (u32)s32_max || t32_max < (u32)s32_min)
+			return false;
+		if (t32.value != ((u32)s32_min & ~t32.mask)) {
+			if (tnum_step(t32, (u32)s32_min) > (u32)s32_max)
+				return false;
+		}
+	} else {
+		if (t32_min > (u32)s32_max && t32_max < (u32)s32_min)
+			return false;
+	}
+
+	/*
+	 * Intersect u64 with u32. If the u64 range spans >=U32_MAX values then an
+	 * intersection is guaranteed, so we skip that case. Otherwise, we map the
+	 * u64 bounds to the u32 domain and check if the new u32 range intersects
+	 * with the u32 bounds. When mapped, the u64 range might cross the U32_MAX
+	 * boundary. If it doesn't cross the boundary, it forms a single contiguous
+	 * range: [(u32)umin, (u32)umax] that we can check intersection with u32
+	 * bounds. If it does cross the U32_MAX boundary, we get two contiguous
+	 * ranges: [0, (u32)umax] and [(u32)umin, U32_MAX]. We check if any part of
+	 * the u32 bounds overlaps with either segment, which is equivalent to
+	 * ensuring the u32 bounds are not trapped between (u32)umax and (u32)umin.
+	 */
+	if (umax - umin < U32_MAX) { /* u64 range does not span the entire 32-bit domain */
+		if ((u32)umin <= (u32)umax) { /* mapped u32 range is a single contiguous range */
+			if ((u32)umax < u32_min || u32_max < (u32)umin)
+				return false;
+		} else { /* mapped u32 range crosses the U32_MAX boundary */
+			if ((u32)umin > u32_max && (u32)umax < u32_min)
+				return false;
+		}
+	}
+
+	/*
+	 * Intersect u64 with s32. This case is similar to u64-u32, but the u64
+	 * range is mapped to the s32 domain, where it might cross the
+	 * S32_MIN/S32_MAX boundary. If it doesn't cross the S32_MIN/S32_MAX
+	 * boundary (it might still cross the -1/0 sign boundary), we check for
+	 * overlap in the standard way. Otherwise, we get two contiguous ranges (one
+	 * of which crosses the S32_MIN/S32_MAX boundary, and might also cross the
+	 * -1/0 sign boundary): [S32_MIN, (s32)umax] and [(s32)umin, S32_MAX].
+	 * Intersection exists if the s32 bounds overlap with either segment, which
+	 * is equivalent to ensuring the s32 bounds are not trapped between
+	 * (s32)umax and (s32)umin.
+	 */
+	if (umax - umin < U32_MAX) { /* u64 range does not span the entire 32-bit domain */
+		if ((s32)umin <= (s32)umax) { /* mapped s32 range is a single contiguous range */
+			if ((s32)umax < s32_min || s32_max < (s32)umin)
+				return false;
+		} else { /* mapped s32 range crosses the S32_MIN/S32_MAX boundary */
+			if ((s32)umin > s32_max && (s32)umax < s32_min)
+				return false;
+		}
+	}
+
+	/*
+	 * Intersect s64 with u32. This case is similar to u64-u32, but the s64
+	 * range is mapped to the u32 domain, where it might cross the U32_MAX
+	 * boundary. If it doesn't, we check for overlap the standard way. If it
+	 * does, we check that the u32 bounds are not trapped between (u32)smax and
+	 * (u32)smin.
+	 */
+	if ((u64)smax - (u64)smin < U32_MAX) { /* s64 range does not span the entire 32-bit domain */
+		if ((u32)smin <= (u32)smax) { /* mapped u32 range is a single contiguous range */
+			if ((u32)smax < u32_min || u32_max < (u32)smin)
+				return false;
+		} else { /* mapped u32 range crosses the U32_MAX boundary */
+			if ((u32)smin > u32_max && (u32)smax < u32_min)
+				return false;
+		}
+	}
+
+	/*
+	 * Intersect s64 with s32. This case is similar to u64-u32, but the s64
+	 * range is mapped to the s32 domain where it might cross the
+	 * S32_MAX/S32_MIN boundary. If it doesn't, we check for overlap the
+	 * standard way. If it does, we check that the s32 bounds are not trapped
+	 * between (s32)smax and (s32)smin.
+	 */
+	if ((u64)smax - (u64)smin < U32_MAX) { /* s64 range does not span the entire 32-bit domain */
+		if ((s32)smin <= (s32)smax) { /* mapped s32 range does not cross S32_MAX/S32_MIN boundary */
+			if ((s32)smax < s32_min || s32_max < (s32)smin)
+				return false;
+		} else { /* mapped s32 range crosses the S32_MAX boundary */
+			if ((s32)smin > s32_max && (s32)smax < s32_min)
+				return false;
+		}
+	}
+
+	return true;
+}
+
 static int reg_bounds_sanity_check(struct bpf_verifier_env *env,
 				   struct bpf_reg_state *reg, const char *ctx)
 {
@@ -15493,7 +15696,7 @@ static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode,
 	 * reg_states in the FALSE branch (i.e. reg1, reg2), the FALSE branch must be dead. Only
 	 * TRUE branch will be taken.
 	 */
-	if (range_bounds_violation(&env->false_reg1) || range_bounds_violation(&env->false_reg2))
+	if (!reg_bounds_intersect(&env->false_reg1) || !reg_bounds_intersect(&env->false_reg2))
 		return 1;
 
 	/* Jump (TRUE) branch */
@@ -15505,7 +15708,7 @@ static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode,
 	 * reg_states in the TRUE branch (i.e. true_reg1, true_reg2), the TRUE branch must be dead.
 	 * Only FALSE branch will be taken.
 	 */
-	if (range_bounds_violation(&env->true_reg1) || range_bounds_violation(&env->true_reg2))
+	if (!reg_bounds_intersect(&env->true_reg1) || !reg_bounds_intersect(&env->true_reg2))
 		return 0;
 
 	/* Both branches are possible, we can't determine which one will be taken. */
-- 
2.43.0

Re: [PATCH RFC bpf-next 1/7] bpf/verifier: Use intersection checks when simulating to detect dead branches

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2527 bytes --]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9e4980128151..1d5d2b7e5140 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2345,12 +2345,15 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
>
>  static void reg_bounds_sync(struct bpf_reg_state *reg)
>  {
> -	/* If the input reg_state is invalid, we can exit early */
> -	if (range_bounds_violation(reg))
> +	/* If the input reg_state has no intersection between abstract values, it is
> +	 * invalid. We can exit early, ensuring that subsequent operations don't
> +	 * inadvertently fix the reg_state.
> +	 */
> +	if (!reg_bounds_intersect(reg))
>  		return;

Should this multi-line comment have the opening /* on its own line, per
the BPF comment style?

    /*
     * If the input reg_state has no intersection between abstract
     * values, it is invalid. We can exit early, ensuring that
     * subsequent operations don't inadvertently fix the reg_state.
     */

[ ... ]

> @@ -15493,7 +15696,7 @@ static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode,
>  	/*
>  	 * If there is a range bounds violation in *any* of the abstract values in either
>  	 * reg_states in the FALSE branch (i.e. reg1, reg2), the FALSE branch must be dead. Only
>  	 * TRUE branch will be taken.
>  	 */
> -	if (range_bounds_violation(&env->false_reg1) || range_bounds_violation(&env->false_reg2))
> +	if (!reg_bounds_intersect(&env->false_reg1) || !reg_bounds_intersect(&env->false_reg2))
>  		return 1;

The comment still says "range bounds violation" but the code now calls
reg_bounds_intersect(), which checks for more than range violations --
it checks pairwise intersection across all domain pairs including tnum.
Should the comment be updated to match the broader check?

[ ... ]

>  	/*
>  	 * If there is a range bounds violation in *any* of the abstract values in either
>  	 * reg_states in the TRUE branch (i.e. true_reg1, true_reg2), the TRUE branch must be dead.
>  	 * Only FALSE branch will be taken.
>  	 */
> -	if (range_bounds_violation(&env->true_reg1) || range_bounds_violation(&env->true_reg2))
> +	if (!reg_bounds_intersect(&env->true_reg1) || !reg_bounds_intersect(&env->true_reg2))
>  		return 0;

Same stale comment here for the true branch.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/24513066291

Re: [PATCH RFC bpf-next 1/7] bpf/verifier: Use intersection checks when simulating to detect dead branches

[sashiko-bot]

Sashiko AI review found 1 potential issue(s):
- [Critical] Returning early from `reg_bounds_sync` on `!reg_bounds_intersect(reg)` masks verifier soundness bugs and turns them into exploitable branch-pruning vulnerabilities.
--

commit 6f55ebe5b292297be4b3fa774e1c6b87de6d0862
Author: Harishankar Vishwanathan <harishankar.vishwanathan@gmail.com>

bpf/verifier: Use intersection checks when simulating to detect dead branches

This commit introduces a new check to detect if register bounds across
domains (u64, s64, u32, s32, tnum) have an intersection. It uses this new
check to prune dead branches and to exit early during register bounds
synchronization.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9e4980128151b..1d5d2b7e5140b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c

[ ... ]

> @@ -2345,12 +2345,15 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
>  static void reg_bounds_sync(struct bpf_reg_state *reg)
>  {
> -	/* If the input reg_state is invalid, we can exit early */
> -	if (range_bounds_violation(reg))
> +	/* If the input reg_state has no intersection between abstract values, it is
> +	 * invalid. We can exit early, ensuring that subsequent operations don't
> +	 * inadvertently fix the reg_state.
> +	 */
> +	if (!reg_bounds_intersect(reg))
>  		return;

Does returning early from reg_bounds_sync() here mask verifier soundness
bugs and potentially turn them into exploitable branch-pruning regressions?

If a buggy arithmetic operation produces a register state with disjoint
domains (e.g., conflicting u32 and u64 bounds) but does not immediately
have a min > max within a single domain, reg_bounds_intersect() will
return false.

This causes reg_bounds_sync() to exit early, explicitly skipping
__update_reg_bounds() and __reg_deduce_bounds().

Before this patch, running those deduction functions on disjoint domains
would cross-constrain the bounds and naturally produce a state with
min > max (range_bounds_violation). This explicit violation would
subsequently trigger a verifier panic in reg_bounds_sanity_check(),
safely rejecting the broken program.

By skipping the deduction, the state retains its logically impossible
disjoint domains but avoids generating a range_bounds_violation. Because
reg_bounds_sanity_check() was not updated to also fail when
!reg_bounds_intersect() is true, the broken state silently passes all
verifier sanity checks.

When this disjoint register is later evaluated at a conditional jump,
simulate_both_branches_taken() will see !reg_bounds_intersect() and
conclude that the branches are dead, pruning them from verification.
This could allow out-of-bounds memory accesses in the unverified branches,
which the verifier assumes are dead but the kernel will still execute at
runtime.

Should reg_bounds_sanity_check() be updated to also fail if
!reg_bounds_intersect(reg) is true?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1776344897.git.paul.chaignon@gmail.com?part=1

[PATCH RFC bpf-next 2/7] selftests/bpf: Test for empty intersection of tnum and u64

[Paul Chaignon]

Thanks to the previous patch, if the tnum and u64 don't intersect on a
branch, we can deduce the branch is dead code. This patch adds a
verifier selftest for that case, with an invalid r10 write on the dead
branch.

Without the previous patch, this selftest fails as follows:

  0: call bpf_get_prandom_u32#7  ; R0=scalar()
  1: r6 = r0                     ; R0=scalar(id=1) R6=scalar(id=1)
  2: r1 = 0xe00000002            ; R1=0xe00000002
  4: r2 = 0xf00000000            ; R2=0xf00000000
  6: if r6 s< r1 goto pc+2       ; R1=0xe00000002 R6=scalar(id=1,smin=umin=0xe00000002,umax=0x7fffffffffffffff,var_off=(0x0; 0x7fffffffffffffff))
  7: if r6 s> r2 goto pc+1       ; R2=0xf00000000 R6=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,var_off=(0xe00000000; 0x1ffffffff))
  8: if w6 == 0x1 goto pc+1      ; R6=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,var_off=(0xe00000000; 0x1ffffffff))
  9: exit

  from 8 to 10: R0=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,smin32=umin32=1,smax32=umax32=1,var_off=(0xe00000001; 0x100000000)) R1=0xe00000002 R2=0xf00000000 R6=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,smin32=umin32=1,smax32=umax32=1,var_off=(0xe00000001; 0x100000000)) R10=fp0
  10: R0=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,smin32=umin32=1,smax32=umax32=1,var_off=(0xe00000001; 0x100000000)) R1=0xe00000002 R2=0xf00000000 R6=scalar(id=1,smin=umin=0xe00000002,smax=umax=0xf00000000,smin32=umin32=1,smax32=umax32=1,var_off=(0xe00000001; 0x100000000)) R10=fp0
  10: (b7) r10 = 0
  frame pointer is read only

Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 25 +++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index c1ae013dee29..151c7a479a6b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -2184,4 +2184,29 @@ __naked void tnums_equal_impossible_constant(void *ctx)
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("dead branch: tnum and u64 don't intersect on true branch")
+__success
+__naked void empty_tnum_u64_intersection(void *ctx)
+{
+	asm volatile("									\
+	call %[bpf_get_prandom_u32];							\
+	r6 = r0;									\
+	r1 = 0xe00000002 ll;								\
+	r2 = 0xf00000000 ll;								\
+	if r6 s< r1 goto +2;								\
+	/* On fallthrough, r6's u64=[0xe00000002;0xf00000000] */			\
+	/*                      tnum=(0xe00000000; 0x1ffffffff) */			\
+	if r6 s> r2 goto +1;								\
+	/* On fallthrough, r6's tnum=(0xe00000001; 0x100000000) */			\
+	/* It doesn't intersect with the u64 so the condition is always false */	\
+	if w6 == 1 goto +1;								\
+	exit;										\
+	r10 = 0;									\
+	exit;										\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

Re: [PATCH RFC bpf-next 2/7] selftests/bpf: Test for empty intersection of tnum and u64

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1878 bytes --]

> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index c1ae013dee29..151c7a479a6b 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -2184,4 +2184,29 @@ __naked void tnums_equal_impossible_constant(void *ctx)

[ ... ]

> +	if r6 s< r1 goto +2;								\
> +	/* On fallthrough, r6's u64=[0xe00000002;0xf00000000] */			\
> +	/*                      tnum=(0xe00000000; 0x1ffffffff) */			\
> +	if r6 s> r2 goto +1;								\

Are the inline comments placed correctly? According to the
verifier log in the commit message itself, on fallthrough of the
"if r6 s< r1" instruction the state is:

    R6=scalar(smin=umin=0xe00000002,
              umax=0x7fffffffffffffff,
              var_off=(0x0; 0x7fffffffffffffff))

The u64 upper bound at this point is 0x7fffffffffffffff, not
0xf00000000. The values u64=[0xe00000002;0xf00000000] and
tnum=(0xe00000000; 0x1ffffffff) only appear after the
"if r6 s> r2" fallthrough. Should these comments be moved below
the "if r6 s> r2 goto +1" instruction?

> +	/* On fallthrough, r6's tnum=(0xe00000001; 0x100000000) */			\
> +	/* It doesn't intersect with the u64 so the condition is always false */	\
> +	if w6 == 1 goto +1;								\

Similarly, tnum=(0xe00000001; 0x100000000) is the state on the
true branch of "if w6 == 1", not on the fallthrough. The commit
message verifier log confirms this:

    from 8 to 10: R6=scalar(...,
        var_off=(0xe00000001; 0x100000000))

Would "on the true branch" be more accurate here than "on
fallthrough"?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/24513066291

Re: [PATCH RFC bpf-next 2/7] selftests/bpf: Test for empty intersection of tnum and u64

[sashiko-bot]

Sashiko AI review found 2 potential issue(s):
- [Medium] Fragile test design relies on verifier's ignorance of `bpf_get_prandom_u32()` bounds, risking silent test decay.
- [Low] Misplaced and factually incorrect inline comments misrepresent verifier state.
--

commit 8da3729bc39d37f67823aa031e7ba1b8b0d69fe0
Author: Paul Chaignon <paul.chaignon@gmail.com>

selftests/bpf: Test for empty intersection of tnum and u64

This patch adds a verifier selftest for the case where tnum and u64
don't intersect on a branch, allowing the verifier to deduce that the
branch is dead code.

> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index c1ae013dee29c..151c7a479a6b8 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -2184,4 +2184,29 @@ __naked void tnums_equal_impossible_constant(void *ctx)

[ ... ]

> +SEC("socket")
> +__description("dead branch: tnum and u64 don't intersect on true branch")
> +__success
> +__naked void empty_tnum_u64_intersection(void *ctx)
> +{
> +	asm volatile("									\
> +	call %[bpf_get_prandom_u32];							\
> +	r6 = r0;									\
> +	r1 = 0xe00000002 ll;								\
> +	r2 = 0xf00000000 ll;								\
> +	if r6 s< r1 goto +2;								\

Will this test silently decay if the verifier improves its tracking of helper
return values? 

bpf_get_prandom_u32() returns a 32-bit unsigned integer. If the verifier is
updated to track that this helper returns a value bounded by 0xffffffff, it
will statically deduce that the condition r6 s< 0xe00000002 is always true. 

This would prune the fallthrough path as dead code, causing the test to
silently pass without ever exercising the complex tnum vs u64 intersection
logic it was explicitly created to test.

Could we use a true 64-bit unknown scalar, such as bpf_ktime_get_ns(), to
ensure the test remains robust?

> +	/* On fallthrough, r6's u64=[0xe00000002;0xf00000000] */			\
> +	/*                      tnum=(0xe00000000; 0x1ffffffff) */			\
> +	if r6 s> r2 goto +1;								\

Are these inline comments misplaced? 

The upper bound of 0xf00000000 is only established after the 
if r6 s> r2 goto +1 instruction falls through, not before it. 

> +	/* On fallthrough, r6's tnum=(0xe00000001; 0x100000000) */			\
> +	/* It doesn't intersect with the u64 so the condition is always false */	\
> +	if w6 == 1 goto +1;								\

Does this tnum state actually exist on the fallthrough? 

According to the verifier log in the commit message, the tnum state of
(0xe00000001; 0x100000000) only exists on the true branch of 
if w6 == 1 goto +1, not on the fallthrough. 

Describing the taken branch as a fallthrough and placing the state annotations
before the instructions that actually establish them might make the test code
confusing for maintainers trying to understand the exact verifier state at
each step.

> +	exit;										\
> +	r10 = 0;									\
> +	exit;										\
> +"	:
> +	: __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1776344897.git.paul.chaignon@gmail.com?part=2

[PATCH RFC bpf-next 3/7] selftests/bpf: Fix reg_bounds to prune on range violations

[Paul Chaignon]

Since commit b254c6d816e5 ("bpf: Simulate branches to prune based on
range violations"), we use range ill-formedness as a signal to detect
dead branches. That logic was however not reflected in the reg_bounds
selftests and can cause test case failures. For example, the
"(s64)[0xffffffff00000002; 0] (u32)<op> S64_MIN+1" test case currently
fails with:

  19: w0 = w6                  ; R6=scalar(smin=0xffffffff00000002,smax=0)
  20: w0 = w7                  ; R7=0x8000000000000001
  21: if w6 == w7 goto pc+3
  21: R6=scalar(smin=0xffffffff00000002,smax=0) R7=0x8000000000000001
  [...]

  ACTUAL   FALSE1: scalar(u64=[0; U64_MAX],u32=[0; 4294967295],s64=[0xffffffff00000002; 0],s32=[S32_MIN; S32_MAX])
  EXPECTED FALSE1: scalar(u64=[0; U64_MAX],u32=[0; 4294967295],s64=[0xffffffff00000002; 0],s32=[S32_MIN; S32_MAX])
  ACTUAL   FALSE2: scalar(u64=0x8000000000000001,u32=1,s64=S64_MIN+1,s32=0x1)
  EXPECTED FALSE2: scalar(u64=0x8000000000000001,u32=1,s64=S64_MIN+1,s32=0x1)
  ACTUAL   TRUE1:  <not found>
  EXPECTED TRUE1:  scalar(u64=[0xffffffff00000002; 0x7fffffffffffffff],u32=[2147483648; 1],s64=[0xffffffff00000002; 0xffffffff00000001],s32=0x1)
  ACTUAL   TRUE2:  <not found>
  EXPECTED TRUE2:  scalar(u64=0x8000000000000001,u32=1,s64=S64_MIN+1,s32=0x1)

The verifier is able to prune the true branch, while reg_bounds tries to
refine the true-branch values. This patch fixes it by marking branches
as invalid in reg_bounds if their ranges are ill-formed.

Fixes: b254c6d816e5 ("bpf: Simulate branches to prune based on range violations")
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 21 +++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index 71f5240cc5b7..c0b3a357a0f4 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -761,6 +761,16 @@ static void print_refinement(enum num_t s_t, struct range src,
 	print_range(d_t, new, "\n");
 }
 
+static bool is_valid_reg(struct reg_state *x)
+{
+	enum num_t t;
+
+	for (t = first_t; t <= last_t; t++)
+		if (!is_valid_range(t, x->r[t]))
+			return false;
+	return true;
+}
+
 static void reg_state_refine(struct reg_state *r, enum num_t t, struct range x, const char *ctx)
 {
 	enum num_t d_t, s_t;
@@ -792,6 +802,9 @@ static void reg_state_refine(struct reg_state *r, enum num_t t, struct range x,
 		}
 	}
 
+	if (!is_valid_reg(r))
+		return;
+
 	/* keep refining until we converge */
 	if (keep_going) {
 		keep_going = false;
@@ -837,6 +850,8 @@ static void reg_state_cond(enum num_t t, struct reg_state *x, struct reg_state *
 		z2 = y->r[t];
 
 		range_cond(t, z1, z2, op, &z1, &z2);
+		if (!is_valid_range(t, z1) || !is_valid_range(t, z2))
+			return;
 
 		if (newx) {
 			snprintf(buf, sizeof(buf), "%s R1", ctx);
@@ -1401,12 +1416,14 @@ static void sim_case(enum num_t init_t, enum num_t cond_t,
 	fr1->valid = fr2->valid = false;
 	tr1->valid = tr2->valid = false;
 	if (*branch_taken != 1) { /* FALSE is possible */
-		fr1->valid = fr2->valid = true;
 		reg_state_cond(cond_t, fr1, fr2, rev_op, fr1, fr2, "FALSE");
+		if (is_valid_reg(fr1) && is_valid_reg(fr2))
+			fr1->valid = fr2->valid = true;
 	}
 	if (*branch_taken != 0) { /* TRUE is possible */
-		tr1->valid = tr2->valid = true;
 		reg_state_cond(cond_t, tr1, tr2, op, tr1, tr2, "TRUE");
+		if (is_valid_reg(tr1) && is_valid_reg(tr2))
+			tr1->valid = tr2->valid = true;
 	}
 	if (env.verbosity >= VERBOSE_VERY) {
 		printf("STEP3 (%s) FALSE R1:", t_str(cond_t)); print_reg_state(fr1, "\n");
-- 
2.43.0

Re: [PATCH RFC bpf-next 3/7] selftests/bpf: Fix reg_bounds to prune on range violations

[sashiko-bot]

Sashiko AI review found 1 potential issue(s):
- [Medium] The early return in `reg_state_cond` silently discards updates, incorrectly preventing mathematically impossible branches from being pruned.
--

commit 9c1398626b454db27a318d8fb3f946b257c46b99
Author: Paul Chaignon <paul.chaignon@gmail.com>

selftests/bpf: Fix reg_bounds to prune on range violations

This patch updates the reg_bounds selftest to correctly detect and prune
dead branches by checking for ill-formed ranges. It marks branches as
invalid if their ranges become ill-formed, matching the verifier logic.

> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index 71f5240cc5b7e..c0b3a357a0f4c 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
[ ... ]
> @@ -837,6 +850,8 @@ static void reg_state_cond(enum num_t t, struct reg_state *x, struct reg_state *
>  		z2 = y->r[t];
>  
>  		range_cond(t, z1, z2, op, &z1, &z2);
> +		if (!is_valid_range(t, z1) || !is_valid_range(t, z2))
> +			return;

Does this early return prevent the invalid ranges from being written back
to newx and newy?

If range_cond() produces an invalid range, the function returns immediately
and bypasses the write-back of xx and yy at the end of the function:

	if (newx)
		*newx = xx;
	if (newy)
		*newy = yy;

This leaves the output registers with their previous valid state.

When sim_case() later checks if the branch is valid:

	reg_state_cond(cond_t, tr1, tr2, op, tr1, tr2, "TRUE");
	if (is_valid_reg(tr1) && is_valid_reg(tr2))
		tr1->valid = tr2->valid = true;

won't it incorrectly evaluate the old valid state and mark the impossible
branch as valid, defeating the pruning logic?

>  
>  		if (newx) {
>  			snprintf(buf, sizeof(buf), "%s R1", ctx);

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1776344897.git.paul.chaignon@gmail.com?part=3

[PATCH RFC bpf-next 4/7] bpf: Improve 64bits bounds refinement from u32 bounds

[Paul Chaignon]

This patch improves the refinement of 64bit bounds from the u32 bounds.

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64:                        xxxxxxx

The above diagram represents a u32 range mapped on the u64 line.
Because the umin64 doesn't match the u32 bounds, it's clear that it
could be tightened to match the next umin32 value:

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64:                             xx

This patch implements the logic for this refinement, for the min and
max bounds of u64 and s64. This refinement only takes place if the 32
lower bits of umin64 are outside of the u32 range. In that case, we
update umin64 to the next matching umin32 value. For the max bounds, we
proceed in the same way, but update umax64 to the previous matching
umax32 value.

Note that when updating the min, we can run into an overflow. It
corresponds to the following case and doesn't require special handling.

u32:     xxx         xxx         xxx         xxx         xxx
     |-----------------------------|-----------------------------|
u64: xxxxxx                                                   xxxx

This patch also updates reg_bounds to implement the same refinement.
That change is small because commit 2fefa9c81a25 ("selftests/bpf: Fix
reg_bounds to match new tnum-based refinement") already implemented
similar logic to the above in reg_bounds.

Together, these changes to the verifier and reg_bounds fix the selftest
"(s64)[0xfffffffe000000ff; 0xffffffff00000000] (u32)<op> S64_MIN+255".

Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 kernel/bpf/verifier.c                         | 50 ++++++++++++++++---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 10 ++--
 2 files changed, 47 insertions(+), 13 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1d5d2b7e5140..bcf8a38a4d72 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2273,17 +2273,51 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
 	 */
 	__u64 new_umin, new_umax;
 	__s64 new_smin, new_smax;
+	__u32 umin_32lower, umax_32lower;
+	__u32 smin_32lower, smax_32lower;
 
 	/* u32 -> u64 tightening, it's always well-formed */
-	new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->umin_value = max_t(u64, reg->umin_value, new_umin);
-	reg->umax_value = min_t(u64, reg->umax_value, new_umax);
+	umin_32lower = reg->umin_value & 0xffffffffULL;
+	if (umin_32lower < reg->u32_min_value || umin_32lower > reg->u32_max_value) {
+		new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
+		if (new_umin < reg->umin_value)
+			/*
+			 * The potential overflow here corresponds to the
+			 * following case and doesn't require special handling.
+			 *
+			 * u32:     xxx        xxx        xxx        xxx
+			 *      |---------------------|---------------------|
+			 * u64: xxxxxx                                   xxxx
+			 */
+			new_umin += 0x100000000;
+		reg->umin_value = new_umin;
+	}
+	umax_32lower = reg->umax_value & 0xffffffffULL;
+	if (umax_32lower < reg->u32_min_value || umax_32lower > reg->u32_max_value) {
+		new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
+		if (new_umax > reg->umax_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_umax -= 0x100000000;
+		reg->umax_value = new_umax;
+	}
+
 	/* u32 -> s64 tightening, u32 range embedded into s64 preserves range validity */
-	new_smin = (reg->smin_value & ~0xffffffffULL) | reg->u32_min_value;
-	new_smax = (reg->smax_value & ~0xffffffffULL) | reg->u32_max_value;
-	reg->smin_value = max_t(s64, reg->smin_value, new_smin);
-	reg->smax_value = min_t(s64, reg->smax_value, new_smax);
+	smin_32lower = reg->smin_value & 0xffffffffULL;
+	if (smin_32lower < reg->u32_min_value || smin_32lower > reg->u32_max_value) {
+		new_smin = (reg->smin_value & ~0xffffffffULL) | reg->u32_min_value;
+		if (new_smin < reg->smin_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_smin += 0x100000000;
+		reg->smin_value = new_smin;
+	}
+	smax_32lower = reg->smax_value & 0xffffffffULL;
+	if (smax_32lower < reg->u32_min_value || smax_32lower > reg->u32_max_value) {
+		new_smax = (reg->smax_value & ~0xffffffffULL) | reg->u32_max_value;
+		if (new_smax > reg->smax_value)
+			/* Cf comment on new_umin for potential overflow. */
+			new_smax -= 0x100000000;
+		reg->smax_value = new_smax;
+	}
 
 	/* Here we would like to handle a special case after sign extending load,
 	 * when upper bits for a 64-bit range are all 1s or all 0s.
diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index c0b3a357a0f4..d38550fc1624 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -500,7 +500,7 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 	    (s64)x.a >= S32_MIN && (s64)x.b <= S32_MAX)
 		return range_intersection(x_t, x, y_cast);
 
-	if (y_t == U32 && x_t == U64) {
+	if (y_t == U32 && !t_is_32(x_t)) {
 		u64 xmin_swap, xmax_swap, xmin_lower32, xmax_lower32;
 
 		xmin_lower32 = x.a & 0xffffffff;
@@ -518,8 +518,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 			 */
 			if (xmin_swap < x.a)
 				xmin_swap += 0x100000000;
-			if (xmin_swap == x.b)
-				return range(x_t, x.b, x.b);
+			if (xmin_swap != x.a)
+				return range(x_t, xmin_swap, x.b);
 		} else if (xmax_lower32 < y.a || xmax_lower32 > y.b) {
 			/* Same for the umax64, but we want to *decrease*
 			 * umax64 to the *maximum* value that matches the u32
@@ -528,8 +528,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 			xmax_swap = swap_low32(x.b, y.b);
 			if (xmax_swap > x.b)
 				xmax_swap -= 0x100000000;
-			if (xmax_swap == x.a)
-				return range(x_t, x.a, x.a);
+			if (xmax_swap != x.b)
+				return range(x_t, x.a, xmax_swap);
 		}
 	}
 
-- 
2.43.0

Re: [PATCH RFC bpf-next 4/7] bpf: Improve 64bits bounds refinement from u32 bounds

[sashiko-bot]

Sashiko AI review found 1 potential issue(s):
- [Medium] The test framework simulator `prog_tests/reg_bounds.c` introduces unconditional early returns, preventing simultaneous refinement of boundaries and causing divergence from the verifier.
--

commit 12b1f0ea2a161fbaa54af860eb0602fc32004fbd
Author: Paul Chaignon <paul.chaignon@gmail.com>

bpf: Improve 64bits bounds refinement from u32 bounds

This commit improves the refinement of 64-bit bounds from u32 bounds in the
BPF verifier, tightening the umin64/umax64 and smin64/smax64 values when
their lower 32 bits fall outside the known u32 range. It also updates the
selftests bounding simulator to match this logic.

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 1d5d2b7e5140b..bcf8a38a4d720 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
[ ... ]
> @@ -2273,17 +2273,51 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
[ ... ]
> +	umin_32lower = reg->umin_value & 0xffffffffULL;
> +	if (umin_32lower < reg->u32_min_value || umin_32lower > reg->u32_max_value) {
> +		new_umin = (reg->umin_value & ~0xffffffffULL) | reg->u32_min_value;
[ ... ]
> +		reg->umin_value = new_umin;
> +	}
> +	umax_32lower = reg->umax_value & 0xffffffffULL;
> +	if (umax_32lower < reg->u32_min_value || umax_32lower > reg->u32_max_value) {
> +		new_umax = (reg->umax_value & ~0xffffffffULL) | reg->u32_max_value;
[ ... ]
> +		reg->umax_value = new_umax;
> +	}

[ ... ]

> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index c0b3a357a0f4c..d38550fc16240 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
[ ... ]
> @@ -518,8 +518,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
>  			 */
>  			if (xmin_swap < x.a)
>  				xmin_swap += 0x100000000;
> -			if (xmin_swap == x.b)
> -				return range(x_t, x.b, x.b);
> +			if (xmin_swap != x.a)
> +				return range(x_t, xmin_swap, x.b);
>  		} else if (xmax_lower32 < y.a || xmax_lower32 > y.b) {
>  			/* Same for the umax64, but we want to *decrease*
>  			 * umax64 to the *maximum* value that matches the u32
> @@ -528,8 +528,8 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
>  			xmax_swap = swap_low32(x.b, y.b);
>  			if (xmax_swap > x.b)
>  				xmax_swap -= 0x100000000;
> -			if (xmax_swap == x.a)
> -				return range(x_t, x.a, x.a);
> +			if (xmax_swap != x.b)
> +				return range(x_t, x.a, xmax_swap);
>  		}
>  	}

Since the actual verifier logic in deduce_bounds_64_from_32() evaluates and
updates umin and umax sequentially, should the simulation logic here allow
both bounds to be refined simultaneously?

By using an "else if" and immediately returning when the lower bound is
refined, won't the simulator skip upper bound refinement entirely and produce
looser expected bounds than the verifier's actual output?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1776344897.git.paul.chaignon@gmail.com?part=4

[PATCH RFC bpf-next 5/7] bpf: Remove dead code from u32->*64 refinement logic

[Paul Chaignon]

This patch fixes an inaccurate refinement in the verifier uncovered by
selftest "(s64)[0x2; 0x100000000] (s32)<op> S64_MIN":

  19: w0 = w6                   ; R6=scalar(smin=umin=2,
                                ;           smax=umax=0x100000000,
                                ;           var_off=(0x0; 0x1ffffffff))
  20: w0 = w7                   ; R7=0x8000000000000000
  21: if w6 s<= w7 goto pc+3    ; R6=scalar(smin=umin=smin32=umin32=1,
                                ;           smax=umax=umax32=0x7fffffff,
                                ;           var_off=(0x0; 0x7fffffff))
                                ; R7=0x8000000000000000
  [...]

  =====================
  ACTUAL   FALSE1: scalar(u64=[1; 2147483647],u32=[1; 2147483647],s64=[0x1; 0x7fffffff],s32=[0x1; S32_MAX])
  EXPECTED FALSE1: scalar(u64=[2; 2147483647],u32=[2; 2147483647],s64=[0x2; 0x7fffffff],s32=[0x2; S32_MAX])
  [...]

Before the conditional jump at instruction 21, R6 has a minimum 64bit
value of 2. After the fallthrough, it's minimum value is 1; the 64bit
ranges grew. That should never happen after a condition: we learn
more information about the register so its ranges should only shrink.

This is happening because of the last refinement in
deduce_bounds_64_from_32(). Under specific conditions, we run

  reg->smin_value = reg->s32_min_value;
  reg->smax_value = reg->s32_max_value;
  reg->umin_value = reg->s32_min_value;
  reg->umax_value = reg->s32_max_value;

The 64bit ranges are thus updated even if the new values are less
precise. We should be using min()/max() instead, as done elsewhere.

Instead of fixing this refinement logic, we can just remove it. Indeed,
it's a special case of the new logic introduced above, in the same
function, by the previous commit ("bpf: Improve 64bits bounds
refinement from u32 bounds"). It corresponds to this case:

    u32:   xx             xx             xx             xx
         |---------------------------|---------------------------|
    u64: xxxx                                                  xxx
               ^                                           ^
               (s64)S32_MAX                                (s64)S32_MIN

Fixes: 9f5469b84577 ("bpf: Get better reg range with ldsx and 32bit compare")
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 kernel/bpf/verifier.c | 38 --------------------------------------
 1 file changed, 38 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index bcf8a38a4d72..7ce3d979cd6f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2318,44 +2318,6 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)
 			new_smax -= 0x100000000;
 		reg->smax_value = new_smax;
 	}
-
-	/* Here we would like to handle a special case after sign extending load,
-	 * when upper bits for a 64-bit range are all 1s or all 0s.
-	 *
-	 * Upper bits are all 1s when register is in a range:
-	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
-	 * Upper bits are all 0s when register is in a range:
-	 *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
-	 * Together this forms are continuous range:
-	 *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
-	 *
-	 * Now, suppose that register range is in fact tighter:
-	 *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
-	 * Also suppose that it's 32-bit range is positive,
-	 * meaning that lower 32-bits of the full 64-bit register
-	 * are in the range:
-	 *   [0x0000_0000, 0x7fff_ffff] (W)
-	 *
-	 * If this happens, then any value in a range:
-	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
-	 * is smaller than a lowest bound of the range (R):
-	 *   0xffff_ffff_8000_0000
-	 * which means that upper bits of the full 64-bit register
-	 * can't be all 1s, when lower bits are in range (W).
-	 *
-	 * Note that:
-	 *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
-	 *  - 0x0000_0000_7fff_ffff == (s64)S32_MAX
-	 * These relations are used in the conditions below.
-	 */
-	if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
-		reg->smin_value = reg->s32_min_value;
-		reg->smax_value = reg->s32_max_value;
-		reg->umin_value = reg->s32_min_value;
-		reg->umax_value = reg->s32_max_value;
-		reg->var_off = tnum_intersect(reg->var_off,
-					      tnum_range(reg->smin_value, reg->smax_value));
-	}
 }
 
 static void __reg_deduce_bounds(struct bpf_reg_state *reg)
-- 
2.43.0

[PATCH RFC bpf-next 6/7] selftests/bpf: Hardcode insteresting 32->64 refinement cases

[Paul Chaignon]

These test cases were part of the slow mode and failing before the
previous fixes to reg_bounds and the verifier. This patch ensures they
run even when SLOW_MODE=0.

Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index d38550fc1624..dda5745e583d 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -2246,6 +2246,13 @@ static struct subtest_case crafted_cases[] = {
 	{S64, U32, {0x0, 0x1f}, {0xffffffff80000000ULL, 0x000000007fffffffULL}},
 	{S64, U32, {0x0, 0x1f}, {0xffffffffffff8000ULL, 0x0000000000007fffULL}},
 	{S64, U32, {0x0, 0x1f}, {0xffffffffffffff80ULL, 0x000000000000007fULL}},
+
+	/* edge cases for 64bit refinement from 32bit bounds */
+	{S64, U32, {0xfffffffe00000002ULL, 0xffffffff00000000ULL}, {S64_MIN + 1, S64_MIN + 1}},
+	{S64, U32, {0xffffffff00000002ULL, 0}, {S64_MIN + 1, S64_MIN + 1}},
+	{S64, U32, {0xfffffffe000000ffULL, 0xffffffff00000000ULL}, {S64_MIN + 255, S64_MIN + 255}},
+	{S64, S32, {0x8000000080000000ULL, 0}, {S64_MIN, S64_MIN}},
+	{S64, S32, {0x2, 0x100000000}, {S64_MIN, S64_MIN}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
-- 
2.43.0

[PATCH RFC bpf-next 7/7] selftests/bpf: new cases handled by 32->64 range refinements

[Paul Chaignon]

From: Eduard Zingerman <eddyz87@gmail.com>

1. u64 range where the lo32 of each endpoint falls outside the u32
   range within its 2^32 block, requiring umin/umax to advance to an
   adjacent block. Three variants:
   - range entirely below S64_MAX;
   - s64 range spanning negative and positive values to exercise
     smin/smax advance;
   - u64 range crossing the sign boundary: smin/smax stay conservative
     at S64_MIN/S64_MAX.

2. 32-bit range crosses the U32_MAX/0 boundary, represented as s32
   range crossing sign boundary.

3. s32-bit range wraps, but u32 has a tighter lower bound from an
   unsigned comparison.

Co-developed-by: Helen Koike <koike@igalia.com>
Signed-off-by: Helen Koike <koike@igalia.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 177 ++++++++++++++++++
 1 file changed, 177 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 151c7a479a6b..6dd9574fd0c3 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -2209,4 +2209,181 @@ __naked void empty_tnum_u64_intersection(void *ctx)
 	: __clobber_all);
 }
 
+/*
+ * 64-bit range is outside the 32-bit range in each 2^32 block.
+ *
+ * This test triggers updates on umin/umax and smin/smax.
+ *
+ * N*2^32                   (N+1)*2^32                (N+2)*2^32                (N+3)*2^32
+ * ||----|=====|--|----------||----|=====|-------------||--|-|=====|-------------||
+ *       |< b >|  |                |< b >|                 | |< b >|
+ *                |                |     |                 |
+ *                |<---------------+- a -+---------------->|
+ *                                 |     |
+ *                                 |< t >| refined r0 range
+ *
+ * a = u64 [0x1'00000008, 0x3'00000001]
+ * b = u32 [2, 5]
+ * t = u64 [0x2'00000002, 0x2'00000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_block_change(void *ctx)
+{
+	asm volatile ("							\
+	call %[bpf_get_prandom_u32];					\
+	r1 = 0x100000008 ll;						\
+	if r0 < r1 goto 2f;						\
+	r1 = 0x300000001 ll;						\
+	if r0 > r1 goto 2f;	/* u64: [0x1'00000008, 0x3'00000001] */	\
+	if w0 < 2 goto 2f;						\
+	if w0 > 5 goto 2f;	/* u32: [2, 5] */			\
+	r2 = 0x200000002 ll;						\
+	r3 = 0x200000005 ll;						\
+	if r0 >= r2 goto 1f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+1:	if r0 <= r3 goto 2f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+2:	exit;								\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * Similar to the deduce64_from_32_block_change test for smin/smax boundaries.
+ *
+ * a = s64 [0x8000000100000008, 0x0000000300000001]  (crosses sign boundary)
+ * b = u32 [2, 5]
+ * t = s64 [0x8000000200000002, 0x0000000200000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_block_change_signed(void *ctx)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r1 = 0x8000000100000008 ll;				\
+	if r0 s< r1 goto 2f;					\
+	r1 = 0x300000001 ll;					\
+	if r0 s> r1 goto 2f;	/* s64: [0x8000000100000008, 0x3'00000001] */ \
+	if w0 < 2 goto 2f;					\
+	if w0 > 5 goto 2f;	/* u32: [2, 5] */		\
+	r2 = 0x8000000200000002 ll;				\
+	r3 = 0x200000005 ll;					\
+	if r0 s>= r2 goto 1f;	/* should be always true */	\
+	r10 = 0;		/* dead code */			\
+1:	if r0 s<= r3 goto 2f;	/* should be always true */	\
+	r10 = 0;		/* dead code */			\
+2:	exit;							\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * Similar to the deduce64_from_32_block_change test, with conservative signed boundaries.
+ *
+ * a = u64 [0x1'00000008, 0x80000003'00000001]
+ *   = s64 [S64_MIN, S64_MAX] (since (s64)umin > (s64)umax)
+ * b = u32 [2, 5]
+ * t = u64 [0x2'00000002, 0x80000002'00000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_block_change_conservative_signed(void *ctx)
+{
+	asm volatile ("						\
+	call %[bpf_get_prandom_u32];				\
+	r1 = 0x100000008 ll;					\
+	if r0 < r1 goto 2f;					\
+	r1 = 0x8000000300000001 ll;				\
+	if r0 > r1 goto 2f;	/* u64: [0x100000008, 0x8000000300000001] */ \
+	if w0 < 2 goto 2f;					\
+	if w0 > 5 goto 2f;	/* u32: [2, 5] */		\
+	r2 = 0x200000002 ll;					\
+	r3 = 0x8000000200000005 ll;				\
+	if r0 >= r2 goto 1f;	/* should be always true */	\
+	r10 = 0;		/* dead code */			\
+1:	if r0 <= r3 goto 2f;	/* should be always true */	\
+	r10 = 0;		/* dead code */			\
+2:	exit;							\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * 32-bit range crossing U32_MAX / 0 boundary.
+ *
+ * N*2^32                   (N+1)*2^32                (N+2)*2^32                (N+3)*2^32
+ * ||===|---------|------|===||===|----------------|===||===|---------|------|===||
+ *  |b >|         |      |< b||b >|                |< b||b >|         |      |< b|
+ *                |      |                                  |         |
+ *                |<-----+----------------- a --------------+-------->|
+ *                       |                                  |
+ *                       |<---------------- t ------------->| refined r0 range
+ *
+ * a = u64 [0x1'00000006, 0x2'FFFFFFEF]
+ * b = s32 [-16, 5] (u32 wrapping [0xFFFFFFF0, 0x00000005])
+ * t = u64 [0x1'FFFFFFF0, 0x2'00000005]
+ */
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_wrapping_32bit(void *ctx)
+{
+	asm volatile ("							\
+	call %[bpf_get_prandom_u32];					\
+	r1 = 0x100000006 ll;						\
+	if r0 < r1 goto 2f;						\
+	r1 = 0x2ffffffef ll;						\
+	if r0 > r1 goto 2f;	/* u64: [0x1'00000006, 0x2'FFFFFFEF] */	\
+	if w0 s< -16 goto 2f;						\
+	if w0 s> 5 goto 2f;	/* s32: [-16, 5] */			\
+	r1 = 0x1fffffff0 ll;						\
+	r2 = 0x200000005 ll;						\
+	if r0 >= r1 goto 1f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+1:	if r0 <= r2 goto 2f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+2:	exit;								\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * s32 range wraps, but u32 has a tighter lower bound from an unsigned
+ * comparison.
+ *
+ * a = u64 [0x7FFFFFFF'00000001, 0x80000002'00000010]
+ * b = s32 [-5, 5] + w0 u>= 2  =>  u32: [2, U32_MAX]
+ * t = u64 [0x7FFFFFFF'00000002, ...]
+ */
+SEC("socket")
+__success __flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void deduce64_from_32_u32_tighter_than_s32(void *ctx)
+{
+	asm volatile ("							\
+	call %[bpf_get_prandom_u32];					\
+	r1 = 0x7fffffff00000001 ll;					\
+	if r0 < r1 goto 2f;						\
+	r1 = 0x8000000200000010 ll;					\
+	if r0 > r1 goto 2f;	/* u64: [0x7FFFFFFF'00000001, 0x80000002'00000010] */	\
+	if w0 s< -5 goto 2f;						\
+	if w0 s> 5 goto 2f;	/* s32: [-5, 5] */			\
+	if w0 < 2 goto 2f;	/* u32_min=2; s32 still wraps */	\
+	r2 = 0x7fffffff00000002 ll;					\
+	if r0 >= r2 goto 2f;	/* should be always true */		\
+	r10 = 0;		/* dead code */				\
+2:	exit;								\
+	"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0