[PATCH bpf-next v2 0/2] bpf: Fix tnum_overlap to check for zero mask intersection

[PATCH bpf-next v2 0/2] bpf: Fix tnum_overlap to check for zero mask intersection

[KaFai Wan]

This small patchset is about avoid verifier bug warning when tnum_overlap()
is called with zero mask intersection.

v2:
 - fix runtime error

v1:
 https://lore.kernel.org/all/20251026163806.3300636-1-kafai.wan@linux.dev/
---
KaFai Wan (2):
  bpf: Fix tnum_overlap to check for zero mask intersection
  selftests/bpf: Range analysis test case for JEQ

 kernel/bpf/tnum.c                             |  2 ++
 .../selftests/bpf/progs/verifier_bounds.c     | 23 +++++++++++++++++++
 2 files changed, 25 insertions(+)

-- 
2.43.0

[PATCH bpf-next v2 1/2] bpf: Fix tnum_overlap to check for zero mask intersection

[KaFai Wan]

Syzbot reported a kernel warning due to a range invariant violation in
the BPF verifier. The issue occurs when tnum_overlap() fails to detect
that two tnums don't have any overlapping bits.

The problematic BPF program:
   0: call bpf_get_prandom_u32
   1: r6 = r0
   2: r6 &= 0xFFFFFFFFFFFFFFF0
   3: r7 = r0
   4: r7 &= 0x07
   5: r7 -= 0xFF
   6: if r6 == r7 goto <exit>

After instruction 5, R7 has the range:
   R7: u64=[0xffffffffffffff01, 0xffffffffffffff08] var_off=(0xffffffffffffff00; 0xf)

R6 and R7 don't overlap since they have no agreeing bits. However,
is_branch_taken() fails to recognize this, causing the verifier to
refine register bounds and trigger range bounds violation:

   6: if r6 == r7 goto <exit>
   true_reg1: u64=[0xffffffffffffff01, 0xffffffffffffff00] var_off=(0xffffffffffffff00, 0x0)
   true_reg2: u64=[0xffffffffffffff01, 0xffffffffffffff00] var_off=(0xffffffffffffff00, 0x0)

The root cause is that tnum_overlap() doesn't properly handle the case
where the masks have no overlapping bits.

Fix this by adding an early check for zero mask intersection in tnum_overlap().

Reported-by: syzbot+c950cc277150935cc0b5@syzkaller.appspotmail.com
Fixes: f41345f47fb2 ("bpf: Use tnums for JEQ/JNE is_branch_taken logic")
Signed-off-by: KaFai Wan <kafai.wan@linux.dev>
---
 kernel/bpf/tnum.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index f8e70e9c3998..1a75b7c9a73a 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -163,6 +163,8 @@ bool tnum_overlap(struct tnum a, struct tnum b)
 {
 	u64 mu;
 
+	if (a.mask && b.mask && !(a.mask & b.mask))
+		return false;
 	mu = ~a.mask & ~b.mask;
 	return (a.value & mu) == (b.value & mu);
 }
-- 
2.43.0

Re: [PATCH bpf-next v2 1/2] bpf: Fix tnum_overlap to check for zero mask intersection

[bot+bpf-ci]

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


```
commit 16cbc4520eb13d2065d145c76b97fb93035d81e8
Author: KaFai Wan <kafai.wan@linux.dev>

bpf: Fix tnum_overlap to check for zero mask intersection

This patch adds an early return check in tnum_overlap() to detect
non-overlapping tnums when their masks have no overlapping bits. The
fix addresses a syzbot report where the verifier failed to recognize
that two tnums couldn't represent the same value.

Reported-by: syzbot+c950cc277150935cc0b5@syzkaller.appspotmail.com

> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> index f8e70e9c3..1a75b7c9a 100644
> --- a/kernel/bpf/tnum.c
> +++ b/kernel/bpf/tnum.c
> @@ -163,6 +163,8 @@ bool tnum_overlap(struct tnum a, struct tnum b)
>  {
>  	u64 mu;
>
> +	if (a.mask && b.mask && !(a.mask & b.mask))
> +		return false;
                              ^^^^^

Does this logic correctly detect non-overlapping tnums? Consider this
counter-example:

  a = (value=0x5, mask=0xA)  // binary: value=0101, mask=1010
  b = (value=0xA, mask=0x5)  // binary: value=1010, mask=0101

The masks are disjoint: (0xA & 0x5) == 0, so the new check returns
false (no overlap).

However, these tnums actually represent overlapping sets:
  a represents: {5, 7, 13, 15}  // 0b0101, 0b0111, 0b1101, 0b1111
  b represents: {10, 11, 14, 15} // 0b1010, 0b1011, 0b1110, 0b1111

Both sets contain 15, so they do overlap. Can this cause incorrect
verifier behavior when is_branch_taken() calls tnum_overlap() to
determine if JEQ/JNE branches are reachable?

>  	mu = ~a.mask & ~b.mask;
>  	return (a.value & mu) == (b.value & mu);
>  }


```

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

In-Reply-To-Subject: `bpf: Fix tnum_overlap to check for zero mask intersection`
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/18880108453

Re: [PATCH bpf-next v2 1/2] bpf: Fix tnum_overlap to check for zero mask intersection

[Eduard Zingerman]

On Tue, 2025-10-28 at 15:45 +0000, bot+bpf-ci@kernel.org wrote:
> ```
> commit 16cbc4520eb13d2065d145c76b97fb93035d81e8
> Author: KaFai Wan <kafai.wan@linux.dev>
> 
> bpf: Fix tnum_overlap to check for zero mask intersection
> 
> This patch adds an early return check in tnum_overlap() to detect
> non-overlapping tnums when their masks have no overlapping bits. The
> fix addresses a syzbot report where the verifier failed to recognize
> that two tnums couldn't represent the same value.
> 
> Reported-by: syzbot+c950cc277150935cc0b5@syzkaller.appspotmail.com
> 
> > diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> > index f8e70e9c3..1a75b7c9a 100644
> > --- a/kernel/bpf/tnum.c
> > +++ b/kernel/bpf/tnum.c
> > @@ -163,6 +163,8 @@ bool tnum_overlap(struct tnum a, struct tnum b)
> >  {
> >  	u64 mu;
> > 
> > +	if (a.mask && b.mask && !(a.mask & b.mask))
> > +		return false;
>                               ^^^^^
> 
> Does this logic correctly detect non-overlapping tnums? Consider this
> counter-example:
> 
>   a = (value=0x5, mask=0xA)  // binary: value=0101, mask=1010
>   b = (value=0xA, mask=0x5)  // binary: value=1010, mask=0101
> 
> The masks are disjoint: (0xA & 0x5) == 0, so the new check returns
> false (no overlap).
> 
> However, these tnums actually represent overlapping sets:
>   a represents: {5, 7, 13, 15}  // 0b0101, 0b0111, 0b1101, 0b1111
>   b represents: {10, 11, 14, 15} // 0b1010, 0b1011, 0b1110, 0b1111
> 
> Both sets contain 15, so they do overlap. Can this cause incorrect
> verifier behavior when is_branch_taken() calls tnum_overlap() to
> determine if JEQ/JNE branches are reachable?

This is a legit bug, please address.

> >  	mu = ~a.mask & ~b.mask;
> >  	return (a.value & mu) == (b.value & mu);
> >  }
> 
> 
> ```
> 
> ---
> 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
> 
> In-Reply-To-Subject: `bpf: Fix tnum_overlap to check for zero mask intersection`
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/18880108453

[PATCH bpf-next v2 2/2] selftests/bpf: Range analysis test case for JEQ

[KaFai Wan]

This patch adds coverage for the warning detected by syzkaller and fixed
in the previous patch. Without the previous patch, this test fails with:

  verifier bug: REG INVARIANTS VIOLATION (true_reg1): range bounds
  violation u64=[0xffffffffffffff01, 0xffffffffffffff00]
  s64=[0xffffffffffffff01, 0xffffffffffffff00]
  u32=[0xffffff01, 0xffffff00] s32=[0xffffff00, 0xffffff00]
  var_off=(0xffffffffffffff00, 0x0)
  verifier bug: REG INVARIANTS VIOLATION (true_reg2): range bounds
  violation u64=[0xffffffffffffff01, 0xffffffffffffff00]
  s64=[0xffffffffffffff01, 0xffffffffffffff00]
  u32=[0xffffff01, 0xffffff00] s32=[0xffffff01, 0xffffff00]
  var_off=(0xffffffffffffff00, 0x0)

Signed-off-by: KaFai Wan <kafai.wan@linux.dev>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 23 +++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 0a72e0228ea9..304ab5a07a3b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -1550,6 +1550,29 @@ l0_%=:	r0 = 0;				\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("dead branch on jeq, does not result in invariants violation error")
+__success __log_level(2)
+__retval(0) __flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void jeq_range_analysis(void)
+{
+	asm volatile ("			\
+	call %[bpf_get_prandom_u32];	\
+	r6 = r0;			\
+	r6 &= 0xFFFFFFFFFFFFFFF0;	\
+	r7 = r0;			\
+	r7 &= 0x07;			\
+	r7 -= 0xFF;			\
+	if r6 == r7 goto l1_%=;		\
+l0_%=:  r0 = 0;				\
+	exit;				\
+l1_%=:  r0 = 1;				\
+	exit;				\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 /* This test covers the bounds deduction on 64bits when the s64 and u64 ranges
  * overlap on the negative side. At instruction 7, the ranges look as follows:
  *
-- 
2.43.0