[PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[Paul Chaignon]

Syzbot reported a kernel warning due to a range invariant violation on
the following BPF program.

  0: call bpf_get_netns_cookie
  1: if r0 == 0 goto <exit>
  2: if r0 & Oxffffffff goto <exit>

The issue is on the path where we fall through both jumps.

That path is unreachable at runtime: after insn 1, we know r0 != 0, but
with the sign extension on the jset, we would only fallthrough insn 2
if r0 == 0. Unfortunately, is_branch_taken() isn't currently able to
figure this out, so the verifier walks all branches. The verifier then
refines the register bounds using the second condition and we end
up with inconsistent bounds on this unreachable path:

  1: if r0 == 0 goto <exit>
    r0: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0xffffffffffffffff)
  2: if r0 & 0xffffffff goto <exit>
    r0 before reg_bounds_sync: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0)
    r0 after reg_bounds_sync:  u64=[0x1, 0] var_off=(0, 0)

Improving the range refinement for JSET to cover all cases is tricky. We
also don't expect many users to rely on JSET given LLVM doesn't generate
those instructions. So instead of reducing false positives due to JSETs,
Eduard suggested we forget the ranges whenever we're narrowing tnums
after a JSET. This patch implements that approach.

Reported-by: syzbot+c711ce17dd78e5d4fdcf@syzkaller.appspotmail.com
Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 53007182b46b..e2fcea860755 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16208,6 +16208,10 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
 		if (!is_reg_const(reg2, is_jmp32))
 			break;
 		val = reg_const_value(reg2, is_jmp32);
+		/* Forget the ranges before narrowing tnums, to avoid invariant
+		 * violations if we're on a dead branch.
+		 */
+		__mark_reg_unbounded(reg1);
 		if (is_jmp32) {
 			t = tnum_and(tnum_subreg(reg1->var_off), tnum_const(~val));
 			reg1->var_off = tnum_with_subreg(reg1->var_off, t);
-- 
2.43.0

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

[Paul Chaignon]

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 (false_reg1): range bounds
  violation u64=[0x0, 0x0] s64=[0x0, 0x0] u32=[0x1, 0x0] s32=[0x0, 0x0]
  var_off=(0x0, 0x0)(1)

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

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 6f986ae5085e..2232bce1bdce 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -2,6 +2,7 @@
 /* Converted from tools/testing/selftests/bpf/verifier/bounds.c */
 
 #include <linux/bpf.h>
+#include <../../../include/linux/filter.h>
 #include <bpf/bpf_helpers.h>
 #include "bpf_misc.h"
 
@@ -1532,4 +1533,22 @@ __naked void sub32_partial_overflow(void)
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("dead branch on jset, does not result in invariants violation error")
+__success __log_level(2)
+__retval(0) __flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void jset_range_analysis(void)
+{
+	asm volatile ("						\
+	call %[bpf_get_netns_cookie];				\
+	if r0 == 0 goto l0_%=;					\
+	.8byte %[jset]; /* if r0 & 0xffffffff goto +0 */	\
+l0_%=:	r0 = 0;							\
+	exit;							\
+"	:
+	: __imm(bpf_get_netns_cookie),
+	  __imm_insn(jset, BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 0xffffffff, 0))
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.43.0

Re: [PATCH bpf-next 2/2] selftests/bpf: Range analysis test case for JSET

[Yonghong Song]

On 7/9/25 3:27 PM, Paul Chaignon wrote:
> 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 (false_reg1): range bounds
>    violation u64=[0x0, 0x0] s64=[0x0, 0x0] u32=[0x1, 0x0] s32=[0x0, 0x0]
>    var_off=(0x0, 0x0)(1)
>
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---
>   .../selftests/bpf/progs/verifier_bounds.c     | 19 +++++++++++++++++++
>   1 file changed, 19 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index 6f986ae5085e..2232bce1bdce 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -2,6 +2,7 @@
>   /* Converted from tools/testing/selftests/bpf/verifier/bounds.c */
>   
>   #include <linux/bpf.h>
> +#include <../../../include/linux/filter.h>
>   #include <bpf/bpf_helpers.h>
>   #include "bpf_misc.h"
>   
> @@ -1532,4 +1533,22 @@ __naked void sub32_partial_overflow(void)
>   	: __clobber_all);
>   }
>   
> +SEC("socket")
> +__description("dead branch on jset, does not result in invariants violation error")
> +__success __log_level(2)
> +__retval(0) __flag(BPF_F_TEST_REG_INVARIANTS)
> +__naked void jset_range_analysis(void)
> +{
> +	asm volatile ("						\
> +	call %[bpf_get_netns_cookie];				\
> +	if r0 == 0 goto l0_%=;					\
> +	.8byte %[jset]; /* if r0 & 0xffffffff goto +0 */	\

why not just use 'if r0 & 0xffffffff goto +0'? It will be equivelant to
BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 0xffffffff, 0).

> +l0_%=:	r0 = 0;							\
> +	exit;							\
> +"	:
> +	: __imm(bpf_get_netns_cookie),
> +	  __imm_insn(jset, BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 0xffffffff, 0))
> +	: __clobber_all);
> +}
> +
>   char _license[] SEC("license") = "GPL";

Re: [PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[Eduard Zingerman]

On Thu, 2025-07-10 at 00:26 +0200, Paul Chaignon wrote:
> Syzbot reported a kernel warning due to a range invariant violation on
> the following BPF program.
> 
>   0: call bpf_get_netns_cookie
>   1: if r0 == 0 goto <exit>
>   2: if r0 & Oxffffffff goto <exit>
> 
> The issue is on the path where we fall through both jumps.
> 
> That path is unreachable at runtime: after insn 1, we know r0 != 0, but
> with the sign extension on the jset, we would only fallthrough insn 2
> if r0 == 0. Unfortunately, is_branch_taken() isn't currently able to
> figure this out, so the verifier walks all branches. The verifier then
> refines the register bounds using the second condition and we end
> up with inconsistent bounds on this unreachable path:
> 
>   1: if r0 == 0 goto <exit>
>     r0: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0xffffffffffffffff)
>   2: if r0 & 0xffffffff goto <exit>
>     r0 before reg_bounds_sync: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0)
>     r0 after reg_bounds_sync:  u64=[0x1, 0] var_off=(0, 0)
> 
> Improving the range refinement for JSET to cover all cases is tricky. We
> also don't expect many users to rely on JSET given LLVM doesn't generate
> those instructions. So instead of reducing false positives due to JSETs,
> Eduard suggested we forget the ranges whenever we're narrowing tnums
> after a JSET. This patch implements that approach.
> 
> Reported-by: syzbot+c711ce17dd78e5d4fdcf@syzkaller.appspotmail.com
> Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

Re: [PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[Yonghong Song]

On 7/9/25 3:26 PM, Paul Chaignon wrote:
> Syzbot reported a kernel warning due to a range invariant violation on
> the following BPF program.
>
>    0: call bpf_get_netns_cookie
>    1: if r0 == 0 goto <exit>
>    2: if r0 & Oxffffffff goto <exit>
>
> The issue is on the path where we fall through both jumps.
>
> That path is unreachable at runtime: after insn 1, we know r0 != 0, but
> with the sign extension on the jset, we would only fallthrough insn 2
> if r0 == 0. Unfortunately, is_branch_taken() isn't currently able to
> figure this out, so the verifier walks all branches. The verifier then
> refines the register bounds using the second condition and we end
> up with inconsistent bounds on this unreachable path:
>
>    1: if r0 == 0 goto <exit>
>      r0: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0xffffffffffffffff)
>    2: if r0 & 0xffffffff goto <exit>
>      r0 before reg_bounds_sync: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0)
>      r0 after reg_bounds_sync:  u64=[0x1, 0] var_off=(0, 0)
>
> Improving the range refinement for JSET to cover all cases is tricky. We
> also don't expect many users to rely on JSET given LLVM doesn't generate
> those instructions. So instead of reducing false positives due to JSETs,
> Eduard suggested we forget the ranges whenever we're narrowing tnums
> after a JSET. This patch implements that approach.
>
> Reported-by: syzbot+c711ce17dd78e5d4fdcf@syzkaller.appspotmail.com
> Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> ---
>   kernel/bpf/verifier.c | 4 ++++
>   1 file changed, 4 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 53007182b46b..e2fcea860755 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -16208,6 +16208,10 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
>   		if (!is_reg_const(reg2, is_jmp32))
>   			break;
>   		val = reg_const_value(reg2, is_jmp32);
> +		/* Forget the ranges before narrowing tnums, to avoid invariant
> +		 * violations if we're on a dead branch.
> +		 */
> +		__mark_reg_unbounded(reg1);
>   		if (is_jmp32) {
>   			t = tnum_and(tnum_subreg(reg1->var_off), tnum_const(~val));
>   			reg1->var_off = tnum_with_subreg(reg1->var_off, t);

The CI reports some invariant violation:
   https://github.com/kernel-patches/bpf/actions/runs/16182458904/job/45681940946?pr=9283

[ 283.030177] ------------[ cut here ]------------ [ 283.030517] 
verifier bug: REG INVARIANTS VIOLATION (false_reg2): range bounds 
violation u64=[0x8000000000000010, 0x800000000000000f] 
s64=[0x8000000000000010, 0x800000000000000f] u32=[0x10, 0xf] s32=[0x10, 
0xf] var_off=(0x8000000000000000, 0x1f)(1)
[ 283.032139] WARNING: CPU: 0 PID: 103 at kernel/bpf/verifier.c:2689 
reg_bounds_sanity_check+0x1dd/0x1f0 ... Probably this change triggered 
some other violations. Please take a look.

Re: [PATCH bpf-next 2/2] selftests/bpf: Range analysis test case for JSET

[Paul Chaignon]

On Wed, Jul 09, 2025 at 04:09:41PM -0700, Yonghong Song wrote:
> 
> 
> On 7/9/25 3:27 PM, Paul Chaignon wrote:

[...]

> > +SEC("socket")
> > +__description("dead branch on jset, does not result in invariants violation error")
> > +__success __log_level(2)
> > +__retval(0) __flag(BPF_F_TEST_REG_INVARIANTS)
> > +__naked void jset_range_analysis(void)
> > +{
> > +	asm volatile ("						\
> > +	call %[bpf_get_netns_cookie];				\
> > +	if r0 == 0 goto l0_%=;					\
> > +	.8byte %[jset]; /* if r0 & 0xffffffff goto +0 */	\
> 
> why not just use 'if r0 & 0xffffffff goto +0'? It will be equivelant to
> BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 0xffffffff, 0).

I was having issues with some older versions of LLVM. Some didn't
recognize jset instructions, some simply crashed. That said, the CI
seems to be fine, so let me switch this back to the simpler syntax.

> 
> > +l0_%=:	r0 = 0;							\
> > +	exit;							\
> > +"	:
> > +	: __imm(bpf_get_netns_cookie),
> > +	  __imm_insn(jset, BPF_JMP_IMM(BPF_JSET, BPF_REG_0, 0xffffffff, 0))
> > +	: __clobber_all);
> > +}
> > +
> >   char _license[] SEC("license") = "GPL";
> 

Re: [PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[Paul Chaignon]

On Wed, Jul 09, 2025 at 04:57:28PM -0700, Yonghong Song wrote:
> 
> 
> On 7/9/25 3:26 PM, Paul Chaignon wrote:
> > Syzbot reported a kernel warning due to a range invariant violation on
> > the following BPF program.
> > 
> >    0: call bpf_get_netns_cookie
> >    1: if r0 == 0 goto <exit>
> >    2: if r0 & Oxffffffff goto <exit>
> > 
> > The issue is on the path where we fall through both jumps.
> > 
> > That path is unreachable at runtime: after insn 1, we know r0 != 0, but
> > with the sign extension on the jset, we would only fallthrough insn 2
> > if r0 == 0. Unfortunately, is_branch_taken() isn't currently able to
> > figure this out, so the verifier walks all branches. The verifier then
> > refines the register bounds using the second condition and we end
> > up with inconsistent bounds on this unreachable path:
> > 
> >    1: if r0 == 0 goto <exit>
> >      r0: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0xffffffffffffffff)
> >    2: if r0 & 0xffffffff goto <exit>
> >      r0 before reg_bounds_sync: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0)
> >      r0 after reg_bounds_sync:  u64=[0x1, 0] var_off=(0, 0)
> > 
> > Improving the range refinement for JSET to cover all cases is tricky. We
> > also don't expect many users to rely on JSET given LLVM doesn't generate
> > those instructions. So instead of reducing false positives due to JSETs,
> > Eduard suggested we forget the ranges whenever we're narrowing tnums
> > after a JSET. This patch implements that approach.
> > 
> > Reported-by: syzbot+c711ce17dd78e5d4fdcf@syzkaller.appspotmail.com
> > Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
> > Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
> > ---
> >   kernel/bpf/verifier.c | 4 ++++
> >   1 file changed, 4 insertions(+)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 53007182b46b..e2fcea860755 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -16208,6 +16208,10 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
> >   		if (!is_reg_const(reg2, is_jmp32))
> >   			break;
> >   		val = reg_const_value(reg2, is_jmp32);
> > +		/* Forget the ranges before narrowing tnums, to avoid invariant
> > +		 * violations if we're on a dead branch.
> > +		 */
> > +		__mark_reg_unbounded(reg1);
> >   		if (is_jmp32) {
> >   			t = tnum_and(tnum_subreg(reg1->var_off), tnum_const(~val));
> >   			reg1->var_off = tnum_with_subreg(reg1->var_off, t);
> 
> The CI reports some invariant violation:
>   https://github.com/kernel-patches/bpf/actions/runs/16182458904/job/45681940946?pr=9283

AFAICS, these invariant violations predate this change. They seem to be
expected and caused by selftests crossing_64_bit_signed_boundary_2 and
crossing_32_bit_signed_boundary_2 which are both marked as "known
invariants violation". They look like fairly different violations as
they are not caused by JSET instructions.

I think it's still worth having the above change for JSET because we
lose only the ranges and not the tnums, whereas with an invariant
violation, we lose all info on the register. I'm looking into the two
other invariant violations to see if there's anything we can improve
there.

> 
> [ 283.030177] ------------[ cut here ]------------ [ 283.030517] verifier
> bug: REG INVARIANTS VIOLATION (false_reg2): range bounds violation
> u64=[0x8000000000000010, 0x800000000000000f] s64=[0x8000000000000010,
> 0x800000000000000f] u32=[0x10, 0xf] s32=[0x10, 0xf]
> var_off=(0x8000000000000000, 0x1f)(1)
> [ 283.032139] WARNING: CPU: 0 PID: 103 at kernel/bpf/verifier.c:2689
> reg_bounds_sanity_check+0x1dd/0x1f0 ... Probably this change triggered some
> other violations. Please take a look.
> 

Re: [PATCH bpf-next 1/2] bpf: Forget ranges when refining tnum after JSET

[Yonghong Song]

On 7/10/25 7:51 AM, Paul Chaignon wrote:
> On Wed, Jul 09, 2025 at 04:57:28PM -0700, Yonghong Song wrote:
>>
>> On 7/9/25 3:26 PM, Paul Chaignon wrote:
>>> Syzbot reported a kernel warning due to a range invariant violation on
>>> the following BPF program.
>>>
>>>     0: call bpf_get_netns_cookie
>>>     1: if r0 == 0 goto <exit>
>>>     2: if r0 & Oxffffffff goto <exit>
>>>
>>> The issue is on the path where we fall through both jumps.
>>>
>>> That path is unreachable at runtime: after insn 1, we know r0 != 0, but
>>> with the sign extension on the jset, we would only fallthrough insn 2
>>> if r0 == 0. Unfortunately, is_branch_taken() isn't currently able to
>>> figure this out, so the verifier walks all branches. The verifier then
>>> refines the register bounds using the second condition and we end
>>> up with inconsistent bounds on this unreachable path:
>>>
>>>     1: if r0 == 0 goto <exit>
>>>       r0: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0xffffffffffffffff)
>>>     2: if r0 & 0xffffffff goto <exit>
>>>       r0 before reg_bounds_sync: u64=[0x1, 0xffffffffffffffff] var_off=(0, 0)
>>>       r0 after reg_bounds_sync:  u64=[0x1, 0] var_off=(0, 0)
>>>
>>> Improving the range refinement for JSET to cover all cases is tricky. We
>>> also don't expect many users to rely on JSET given LLVM doesn't generate
>>> those instructions. So instead of reducing false positives due to JSETs,
>>> Eduard suggested we forget the ranges whenever we're narrowing tnums
>>> after a JSET. This patch implements that approach.
>>>
>>> Reported-by: syzbot+c711ce17dd78e5d4fdcf@syzkaller.appspotmail.com
>>> Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
>>> Signed-off-by: Paul Chaignon <paul.chaignon@gmail.com>
>>> ---
>>>    kernel/bpf/verifier.c | 4 ++++
>>>    1 file changed, 4 insertions(+)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 53007182b46b..e2fcea860755 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -16208,6 +16208,10 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
>>>    		if (!is_reg_const(reg2, is_jmp32))
>>>    			break;
>>>    		val = reg_const_value(reg2, is_jmp32);
>>> +		/* Forget the ranges before narrowing tnums, to avoid invariant
>>> +		 * violations if we're on a dead branch.
>>> +		 */
>>> +		__mark_reg_unbounded(reg1);
>>>    		if (is_jmp32) {
>>>    			t = tnum_and(tnum_subreg(reg1->var_off), tnum_const(~val));
>>>    			reg1->var_off = tnum_with_subreg(reg1->var_off, t);
>> The CI reports some invariant violation:
>>    https://github.com/kernel-patches/bpf/actions/runs/16182458904/job/45681940946?pr=9283
> AFAICS, these invariant violations predate this change. They seem to be
> expected and caused by selftests crossing_64_bit_signed_boundary_2 and
> crossing_32_bit_signed_boundary_2 which are both marked as "known
> invariants violation". They look like fairly different violations as
> they are not caused by JSET instructions.

I double checked and that 'REG INVARIANTS VIOLATION' warning is indeed
not related to your patch so your change looks good to me. You can add
my ack like

   Acked-by: Yonghong Song <yonghong.song@linux.dev>

>
> I think it's still worth having the above change for JSET because we
> lose only the ranges and not the tnums, whereas with an invariant
> violation, we lose all info on the register. I'm looking into the two
> other invariant violations to see if there's anything we can improve
> there.

Thanks for looking at this!

>
>> [ 283.030177] ------------[ cut here ]------------ [ 283.030517] verifier
>> bug: REG INVARIANTS VIOLATION (false_reg2): range bounds violation
>> u64=[0x8000000000000010, 0x800000000000000f] s64=[0x8000000000000010,
>> 0x800000000000000f] u32=[0x10, 0xf] s32=[0x10, 0xf]
>> var_off=(0x8000000000000000, 0x1f)(1)
>> [ 283.032139] WARNING: CPU: 0 PID: 103 at kernel/bpf/verifier.c:2689
>> reg_bounds_sanity_check+0x1dd/0x1f0 ... Probably this change triggered some
>> other violations. Please take a look.
>>