[PATCH bpf-next] selftests/bpf: Fix reg_bounds to match new tnum-based refinement

[PATCH bpf-next] selftests/bpf: Fix reg_bounds to match new tnum-based refinement

[Paul Chaignon]

Commit efc11a667878 ("bpf: Improve bounds when tnum has a single
possible value") improved the bounds refinement to detect when the tnum
and u64 range overlap in a single value (and the bounds can thus be set
to that value).

Eduard then noticed that it broke the slow-mode reg_bounds selftests
because they don't have an equivalent logic and are therefore unable to
refine the bounds as much as the verifier. The following test case
illustrates this.

  ACTUAL   TRUE1:  scalar(u64=0xffffffff00000000,u32=0,s64=0xffffffff00000000,s32=0)
  EXPECTED TRUE1:  scalar(u64=[0xfffffffe00000001; 0xffffffff00000000],u32=0,s64=[0xfffffffe00000001; 0xffffffff00000000],s32=0)
  [...]
  #323/1007 reg_bounds_gen_consts_s64_s32/(s64)[0xfffffffe00000001; 0xffffffff00000000] (s32)<op> S64_MIN:FAIL

with the verifier logs:

  [...]
  19: w0 = w6                 ; R0=scalar(smin=0,smax=umax=0xffffffff,
                                          var_off=(0x0; 0xffffffff))
                                R6=scalar(smin=0xfffffffe00000001,smax=0xffffffff00000000,
                                          umin=0xfffffffe00000001,umax=0xffffffff00000000,
                                          var_off=(0xfffffffe00000000; 0x1ffffffff))
  20: w0 = w7                 ; R0=0 R7=0x8000000000000000
  21: if w6 == w7 goto pc+3
  [...]
  from 21 to 25: [...]
  25: w0 = w6                 ; R0=0 R6=0xffffffff00000000
                              ;         ^
                              ;         unexpected refined value
  26: w0 = w7                 ; R0=0 R7=0x8000000000000000
  27: exit

When w6 == w7 is true, the verifier can deduce that the R6's tnum is
equal to (0xfffffffe00000000; 0x100000000) and then use that information
to refine the bounds: the tnum only overlap with the u64 range in
0xffffffff00000000. The reg_bounds selftest doesn't know about tnums
and therefore fails to perform the same refinement.

This issue happens when the tnum carries information that cannot be
represented in the ranges, as otherwise the selftest could reach the
same refined value using just the ranges. The tnum thus needs to
represent non-contiguous values (ex., R6's tnum above, after the
condition). The only way this can happen in the reg_bounds selftest is
at the boundary between the 32 and 64bit ranges. We therefore only need
to handle that case.

This patch fixes the selftest refinement logic by checking if the u32
and u64 ranges overlap in a single value. If so, the ranges can be set
to that value. We need to handle two cases: either they overlap in
umin64...

  u64 values
  matching u32 range:     xxx        xxx        xxx        xxx
                      |--------------------------------------|
  u64 range:          0                xxxxx                 UMAX64

or in umax64:

  u64 values
  matching u32 range:     xxx        xxx        xxx        xxx
                      |--------------------------------------|
  u64 range:          0          xxxxx                       UMAX64

To detect the first case, we decrease umax64 to the maximum value that
matches the u32 range. If that happens to be umin64, then umin64 is the
only overlap. We proceed similarly for the second case, increasing
umin64 to the minimum value that matches the u32 range.

Note this is similar to how the verifier handles the general case using
tnum, but we don't need to care about a single-value overlap in the
middle of the range. That case is not possible when comparing two
ranges.

This patch also adds two test cases reproducing this bug as part of the
normal test runs (without SLOW_TESTS=1).

Fixes: efc11a667878 ("bpf: Improve bounds when tnum has a single possible value")
Reported-by: Eduard Zingerman <eddyz87@gmail.com>
Closes: https://lore.kernel.org/bpf/4e6dd64a162b3cab3635706ae6abfdd0be4db5db.camel@gmail.com/
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 35 +++++++++++++++++++
 1 file changed, 35 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index 569ae09bdd76..71f5240cc5b7 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -500,6 +500,39 @@ 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) {
+		u64 xmin_swap, xmax_swap, xmin_lower32, xmax_lower32;
+
+		xmin_lower32 = x.a & 0xffffffff;
+		xmax_lower32 = x.b & 0xffffffff;
+		if (xmin_lower32 < y.a || xmin_lower32 > y.b) {
+			/* The 32 lower bits of the umin64 are outside the u32
+			 * range. Let's update umin64 to match the u32 range.
+			 * We want to *increase* the umin64 to the *minimum*
+			 * value that matches the u32 range.
+			 */
+			xmin_swap = swap_low32(x.a, y.a);
+			/* We should always only increase the minimum, so if
+			 * the new value is lower than before, we need to
+			 * increase the 32 upper bits by 1.
+			 */
+			if (xmin_swap < x.a)
+				xmin_swap += 0x100000000;
+			if (xmin_swap == x.b)
+				return range(x_t, x.b, 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
+			 * range.
+			 */
+			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);
+		}
+	}
+
 	/* the case when new range knowledge, *y*, is a 32-bit subregister
 	 * range, while previous range knowledge, *x*, is a full register
 	 * 64-bit range, needs special treatment to take into account upper 32
@@ -2145,6 +2178,8 @@ static struct subtest_case crafted_cases[] = {
 	{U64, S64, {0x7fffffff00000001ULL, 0xffffffff00000000ULL}, {0, 0}},
 	{U64, S64, {0, 0xffffffffULL}, {1, 1}},
 	{U64, S64, {0, 0xffffffffULL}, {0x7fffffff, 0x7fffffff}},
+	{U64, S32, {0xfffffffe00000001, 0xffffffff00000000}, {S64_MIN, S64_MIN}},
+	{U64, U32, {0xfffffffe00000000, U64_MAX - 1}, {U64_MAX, U64_MAX}},
 
 	{U64, U32, {0, 0x100000000}, {0, 0}},
 	{U64, U32, {0xfffffffe, 0x300000000}, {0x80000000, 0x80000000}},
-- 
2.43.0

Re: [PATCH bpf-next] selftests/bpf: Fix reg_bounds to match new tnum-based refinement

[Paul Chaignon]

On Wed, Apr 08, 2026 at 10:40:50PM +0200, Paul Chaignon wrote:
> Commit efc11a667878 ("bpf: Improve bounds when tnum has a single
> possible value") improved the bounds refinement to detect when the tnum
> and u64 range overlap in a single value (and the bounds can thus be set
> to that value).
> 
> Eduard then noticed that it broke the slow-mode reg_bounds selftests
> because they don't have an equivalent logic and are therefore unable to
> refine the bounds as much as the verifier. The following test case
> illustrates this.
> 
>   ACTUAL   TRUE1:  scalar(u64=0xffffffff00000000,u32=0,s64=0xffffffff00000000,s32=0)
>   EXPECTED TRUE1:  scalar(u64=[0xfffffffe00000001; 0xffffffff00000000],u32=0,s64=[0xfffffffe00000001; 0xffffffff00000000],s32=0)
>   [...]
>   #323/1007 reg_bounds_gen_consts_s64_s32/(s64)[0xfffffffe00000001; 0xffffffff00000000] (s32)<op> S64_MIN:FAIL
> 
> with the verifier logs:
> 
>   [...]
>   19: w0 = w6                 ; R0=scalar(smin=0,smax=umax=0xffffffff,
>                                           var_off=(0x0; 0xffffffff))
>                                 R6=scalar(smin=0xfffffffe00000001,smax=0xffffffff00000000,
>                                           umin=0xfffffffe00000001,umax=0xffffffff00000000,
>                                           var_off=(0xfffffffe00000000; 0x1ffffffff))
>   20: w0 = w7                 ; R0=0 R7=0x8000000000000000
>   21: if w6 == w7 goto pc+3
>   [...]
>   from 21 to 25: [...]
>   25: w0 = w6                 ; R0=0 R6=0xffffffff00000000
>                               ;         ^
>                               ;         unexpected refined value
>   26: w0 = w7                 ; R0=0 R7=0x8000000000000000
>   27: exit
> 
> When w6 == w7 is true, the verifier can deduce that the R6's tnum is
> equal to (0xfffffffe00000000; 0x100000000) and then use that information
> to refine the bounds: the tnum only overlap with the u64 range in
> 0xffffffff00000000. The reg_bounds selftest doesn't know about tnums
> and therefore fails to perform the same refinement.
> 
> This issue happens when the tnum carries information that cannot be
> represented in the ranges, as otherwise the selftest could reach the
> same refined value using just the ranges. The tnum thus needs to
> represent non-contiguous values (ex., R6's tnum above, after the
> condition). The only way this can happen in the reg_bounds selftest is
> at the boundary between the 32 and 64bit ranges. We therefore only need
> to handle that case.
> 
> This patch fixes the selftest refinement logic by checking if the u32
> and u64 ranges overlap in a single value. If so, the ranges can be set
> to that value. We need to handle two cases: either they overlap in
> umin64...
> 
>   u64 values
>   matching u32 range:     xxx        xxx        xxx        xxx
>                       |--------------------------------------|
>   u64 range:          0                xxxxx                 UMAX64
> 
> or in umax64:
> 
>   u64 values
>   matching u32 range:     xxx        xxx        xxx        xxx
>                       |--------------------------------------|
>   u64 range:          0          xxxxx                       UMAX64
> 
> To detect the first case, we decrease umax64 to the maximum value that
> matches the u32 range. If that happens to be umin64, then umin64 is the
> only overlap. We proceed similarly for the second case, increasing
> umin64 to the minimum value that matches the u32 range.
> 
> Note this is similar to how the verifier handles the general case using
> tnum, but we don't need to care about a single-value overlap in the
> middle of the range. That case is not possible when comparing two
> ranges.
> 
> This patch also adds two test cases reproducing this bug as part of the
> normal test runs (without SLOW_TESTS=1).
> 
> Fixes: efc11a667878 ("bpf: Improve bounds when tnum has a single possible value")
> Reported-by: Eduard Zingerman <eddyz87@gmail.com>
> Closes: https://lore.kernel.org/bpf/4e6dd64a162b3cab3635706ae6abfdd0be4db5db.camel@gmail.com/
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---

Hi Eduard,

This patch fixes the test case you reported and a couple variants:

reg_bounds_gen_consts_s64_u32/(s64)[0xfffffffe00000001; 0xffffffff00000000] (u32)<op> S64_MIN
reg_bounds_gen_consts_s64_s32/(s64)[0xfffffffe00000001; 0xffffffff00000000] (s32)<op> S64_MIN
reg_bounds_gen_consts_s64_u32/(s64)[0xfffffffe00000000; 0xfffffffffffffffe] (u32)<op> 0xffffffffffffffff
reg_bounds_gen_consts_s64_s32/(s64)[0xfffffffe00000000; 0xfffffffffffffffe] (s32)<op> 0xffffffffffffffff

but we're not out of the woods yet. While running reg_bounds* tests, I
noticed a few other unrelated failures.

---

reg_bounds_gen_consts_s64_u32/(s64)[0xfffffffe00000002; 0xffffffff00000000] (u32)<op> S64_MIN+1

This one hits an invariant violation on an impossible branch and the
bounds are set to an incorrect value that doesn't match what the test
expects.

  19: w0 = w6                ; R0=scalar(smin=0,smax=umax=0xffffffff,
                                         var_off=(0x0; 0xffffffff))
                               R6=scalar(smin=0xfffffffe00000002,smax=0xffffffff00000000,
                                         umin=0xfffffffe00000002,umax=0xffffffff00000000,
                                         var_off=(0xfffffffe00000000; 0x1ffffffff))
  20: w0 = w7                ; R0=1 R7=0x8000000000000001
  21: if w6 == w7 goto pc+3  ; [...]
  [...]

  from 21 to 25: R0=1 R1=0x8000000000000001 R2=0x8000000000000001 R6=0xffffffff00000001 R7=0x8000000000000001 R10=fp0
  [...]

  ACTUAL   TRUE1:  scalar(u64=0xffffffff00000001,u32=1,s64=0xffffffff00000001,s32=0x1)
  EXPECTED TRUE1:  scalar(u64=[0xfffffffe00000002; 0xffffffff00000000],u32=1,s64=[0xfffffffe00000002; 0xffffffff00000000],s32=0x1)

W7 is equal to 1 and, given R6's ranges, cannot be equal to W6. The
condition is always false. On the true branch, the verifier thus
incorrectly refines R6's value to 0xffffffff00000001.

This is a new type of invariant violation (i.e., involving the tnum)
that is not detected by range_bounds_violation(). I'm expecting it will
be handled by Hari's followup patchset. I've shared the program with
Hari so it can maybe be used as a selftest. I'm guessing we're fine
waiting for that fix as it's not failing in CI; if not, we could do a
quick fix in the verifier.

---

reg_bounds_gen_consts_s64_u32/(s64)[0xffffffff00000002; 0] (u32)<op> S64_MIN+1

This one fails because reg_bounds' branch detection logic doesn't match
the kernel's.

  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)

It's failing with that error since b254c6d816e5 ("bpf: Simulate branches
to prune based on range violations"), but was already failing before
with a different error (unexpected range). The root cause seems to be
that the test runs into an invariant violation, here as well.

We'll probably need to update reg_bounds's branch prediction logic to
match what the kernel is now doing. I can look into this next.

[...]

Re: [PATCH bpf-next] selftests/bpf: Fix reg_bounds to match new tnum-based refinement

[Harishankar Vishwanathan]

On Wed, Apr 8, 2026 at 4:48 PM Paul Chaignon <paul.chaignon@gmail.com> wrote:
> On Wed, Apr 08, 2026 at 10:40:50PM +0200, Paul Chaignon wrote:
[...]
> This one hits an invariant violation on an impossible branch and the
> bounds are set to an incorrect value that doesn't match what the test
> expects.
> 
>   19: w0 = w6                ; R0=scalar(smin=0,smax=umax=0xffffffff,
>                                          var_off=(0x0; 0xffffffff))
>                                R6=scalar(smin=0xfffffffe00000002,smax=0xffffffff00000000,
>                                          umin=0xfffffffe00000002,umax=0xffffffff00000000,
>                                          var_off=(0xfffffffe00000000; 0x1ffffffff))
>   20: w0 = w7                ; R0=1 R7=0x8000000000000001
>   21: if w6 == w7 goto pc+3  ; [...]
>   [...]
> 
>   from 21 to 25: R0=1 R1=0x8000000000000001 R2=0x8000000000000001 R6=0xffffffff00000001 R7=0x8000000000000001 R10=fp0
>   [...]
> 
>   ACTUAL   TRUE1:  scalar(u64=0xffffffff00000001,u32=1,s64=0xffffffff00000001,s32=0x1)
>   EXPECTED TRUE1:  scalar(u64=[0xfffffffe00000002; 0xffffffff00000000],u32=1,s64=[0xfffffffe00000002; 0xffffffff00000000],s32=0x1)
> 
> W7 is equal to 1 and, given R6's ranges, cannot be equal to W6. The
> condition is always false. On the true branch, the verifier thus
> incorrectly refines R6's value to 0xffffffff00000001.
> 
> This is a new type of invariant violation (i.e., involving the tnum)
> that is not detected by range_bounds_violation(). I'm expecting it will
> be handled by Hari's followup patchset. I've shared the program with
> Hari so it can maybe be used as a selftest. I'm guessing we're fine
> waiting for that fix as it's not failing in CI; if not, we could do a
> quick fix in the verifier.

At 21, after simulate_both_branches(), R6's tnum is var_off=(0xfffffffe00000001;
0x100000000) and u64 is [0xfffffffe00000002; 0xffffffff00000000]. 

The tnum and u64 ranges do not intersect, but in a specific way: the u64 range
is lodged within the tnum, i.e. tmin < umin <= umax < tmax

u64:        [      ]
tnum:  x                   x

When the tnum and u64 don't intersect along a branch, that branch is dead, and
we should prune it. Because simulate_both_branches() currently only checks for
"range bounds" violations, (e.g. umin > umax) it doesn't detect this kind of
"intersection" violation (tnum and u64 ranges don't intersect), and doesn't
prune the branch where the violation occurs.

As Paul mentioned, the follow-up patchset, which implements intersection
detection for all domain pairs, should fix this. This particular case will be
detected using a tnum-u64-intersection check that employs tnum_step, as
mentioned before [1, 2]. 

[1]: https://lore.kernel.org/bpf/CAM=Ch05-XWF-x_VzUZAWhRO9eum-bjdutuwvPXEcOvnx_0omAA@mail.gmail.com/
[2]: https://lore.kernel.org/bpf/20251107192328.2190680-1-harishankar.vishwanathan@gmail.com/

I have tested the idea and it works (able to prune the branch where the
violation occurred). We'll follow up with the intersection patchset, and can
definitely use this as a selftest.

> ---
> 
> reg_bounds_gen_consts_s64_u32/(s64)[0xffffffff00000002; 0] (u32)<op> S64_MIN+1
> 
> This one fails because reg_bounds' branch detection logic doesn't match
> the kernel's.
> 
>   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)
> 
> It's failing with that error since b254c6d816e5 ("bpf: Simulate branches
> to prune based on range violations"), but was already failing before
> with a different error (unexpected range). The root cause seems to be
> that the test runs into an invariant violation, here as well.
> 
> We'll probably need to update reg_bounds's branch prediction logic to
> match what the kernel is now doing. I can look into this next.
> 
> [...]