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(+)
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); }
``` 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
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
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: *
linux-kselftest-mirror@lists.linaro.org
-
bot+bpf-ci＠kernel.org -
Eduard Zingerman -
KaFai Wan