Skip to contentSkip to conversation

bpf: Fix reg_bounds' slow mode and improve verifier refinement

RFC PATCH New Paul Chaignon 3 participants 14 messages Apr 16

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover bpf: Fix reg_bounds' slow mode and improve verifier refinement

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/[email protected]/
2: https://lore.kernel.org/all/[email protected]/

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(-)
Signature · 1 line
2.43.0
#1 lore raw

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

From: Harishankar Vishwanathan <[email protected]>

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")

---
 kernel/bpf/verifier.c | 213 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 208 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +208 -5
index 9e4980128151..1d5d2b7e5140 100644
@@ -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. */
Signature · 1 line
2.43.0
#2 lore raw

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

Should this multi-line comment have the opening /* on its own line, per the BPF comment style?
Quoted 6 lines
kernel/bpf/verifier.c +0 -0
index 9e4980128151..1d5d2b7e5140 100644
@@ -2345,12 +2345,15 @@ static void __reg_bound_offset(struct bpf_reg_state *reg)
 

kernel/bpf/verifier.c static void __reg_bound_offset(struct bpf_reg_state *reg) · line 2353

Quoted 10 lines
kernel/bpf/verifier.c +5 -2
 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. */

[ ... ]

kernel/bpf/verifier.c static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode, · line 15702

Quoted 9 lines
kernel/bpf/verifier.c +1 -1
@@ -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?

[ ... ]

kernel/bpf/verifier.c static int simulate_both_branches_taken(struct bpf_verifier_env *env, u8 opcode, · line 15712

Quoted 8 lines
kernel/bpf/verifier.c +1 -1
 	/*
 	 * 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

#3 lore raw

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

In reply to Paul Chaignon
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…

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 <[email protected]>

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.

Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index 9e4980128151b..1d5d2b7e5140b 100644

[ ... ]

kernel/bpf/verifier.c static void __reg_bound_offset(struct bpf_reg_state *reg) · line 2352

Quoted 11 lines
kernel/bpf/verifier.c +5 -2
@@ -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?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#4 lore raw

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

In reply to 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

---
 .../selftests/bpf/progs/verifier_bounds.c     | 25 +++++++++++++++++++
 1 file changed, 25 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +25 -0
index c1ae013dee29..151c7a479a6b 100644
@@ -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";
Signature · 1 line
2.43.0
#5 lore raw

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

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:
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +0 -0
index c1ae013dee29..151c7a479a6b 100644
@@ -2184,4 +2184,29 @@ __naked void tnums_equal_impossible_constant(void *ctx)

[ ... ]

tools/testing/selftests/bpf/progs/verifier_bounds.c __naked void tnums_equal_impossible_constant(void *ctx) · line 2200

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +4 -0
+	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?

tools/testing/selftests/bpf/progs/verifier_bounds.c __naked void tnums_equal_impossible_constant(void *ctx) · line 2203

Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +3 -0
+	/* 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

#6 lore raw

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

In reply to Paul Chaignon
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…

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 <[email protected]>

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.

Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +0 -0
index c1ae013dee29c..151c7a479a6b8 100644
@@ -2184,4 +2184,29 @@ __naked void tnums_equal_impossible_constant(void *ctx)

[ ... ]

tools/testing/selftests/bpf/progs/verifier_bounds.c __naked void tnums_equal_impossible_constant(void *ctx) · line 2197

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +11 -0
+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?

tools/testing/selftests/bpf/progs/verifier_bounds.c __naked void tnums_equal_impossible_constant(void *ctx) · line 2200

Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +3 -0
+	/* 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.

tools/testing/selftests/bpf/progs/verifier_bounds.c __naked void tnums_equal_impossible_constant(void *ctx) · line 2203

Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +3 -0
+	/* 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.

Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +7 -0
+	exit;										\
+	r10 = 0;									\
+	exit;										\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
#7 lore raw

RFC PATCH 3/7 selftests/bpf: Fix reg_bounds to prune on range violations

In reply to 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")
---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 21 +++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +19 -2
index 71f5240cc5b7..c0b3a357a0f4 100644
@@ -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");
Signature · 1 line
2.43.0
#8 lore raw

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

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. --

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 <[email protected]>

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.

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -0
index 71f5240cc5b7e..c0b3a357a0f4c 100644

[ ... ]

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static void reg_state_cond(enum num_t t, struct reg_state *x, struct reg_state * · line 854

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +2 -0
@@ -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?

Quoted 3 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -0
 		if (newx) {
 			snprintf(buf, sizeof(buf), "%s R1", ctx);
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
#9 lore raw

RFC PATCH 4/7 bpf: Improve 64bits bounds refinement from u32 bounds

In reply to 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".

---
 kernel/bpf/verifier.c                         | 50 ++++++++++++++++---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 10 ++--
 2 files changed, 47 insertions(+), 13 deletions(-)
kernel/bpf/verifier.c +42 -8
index 1d5d2b7e5140..bcf8a38a4d72 100644
@@ -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.
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +5 -5
index c0b3a357a0f4..d38550fc1624 100644
@@ -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);
 		}
 	}
 
Signature · 1 line
2.43.0
#10 lore raw

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

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…

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 <[email protected]>

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.

Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index 1d5d2b7e5140b..bcf8a38a4d720 100644

[ ... ]

Quoted 1 line
kernel/bpf/verifier.c +0 -0
@@ -2273,17 +2273,51 @@ static void deduce_bounds_64_from_32(struct bpf_reg_state *reg)

[ ... ]

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+	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;

[ ... ]

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+		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;

[ ... ]

Quoted 2 lines
kernel/bpf/verifier.c +2 -0
+		reg->umax_value = new_umax;
+	}

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -0
index c0b3a357a0f4c..d38550fc16240 100644

[ ... ]

Quoted 12 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +2 -2
@@ -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

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 534

Quoted 9 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +2 -2
@@ -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?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
#11 lore raw

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

In reply to 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")
---
 kernel/bpf/verifier.c | 38 --------------------------------------
 1 file changed, 38 deletions(-)
kernel/bpf/verifier.c +0 -38
index bcf8a38a4d72..7ce3d979cd6f 100644
@@ -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)
Signature · 1 line
2.43.0
#12 lore raw

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

In reply to 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.

---
 tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 7 +++++++
 1 file changed, 7 insertions(+)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +7 -0
index d38550fc1624..dda5745e583d 100644
@@ -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
Signature · 1 line
2.43.0
#13 lore raw

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

In reply to Paul Chaignon

From: Eduard Zingerman <[email protected]>

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.

---
 .../selftests/bpf/progs/verifier_bounds.c     | 177 ++++++++++++++++++
 1 file changed, 177 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +177 -0
index 151c7a479a6b..6dd9574fd0c3 100644
@@ -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";
Signature · 1 line
2.43.0