Skip to contentSkip to conversation

Range tracking for BPF_NEG

PATCH Superseded Song Liu 3 participants 8 messages Jun 24, 2025

Subsystems (4)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Song Liu

author reviewer
#0 lore raw

v2 cover Range tracking for BPF_NEG

Add range tracking for BPF_NEG. Please see commit log of 1/2 for more details.

---

Changes v1 => v2:
1. Split new selftests to a separate patch. (Eduard)
2. Reset reg id on BPF_NEG. (Eduard)
3. Use env->fake_reg instead of a bpf_reg_state on the stack. (Eduard)
4. Add __msg for passing selftests.

v1: https://lore.kernel.org/bpf/[email protected]/

Song Liu (2):
bpf: Add range tracking for BPF_NEG selftests/bpf: Add tests for BPF_NEG range tracking logic

 include/linux/tnum.h                          |  2 +
 kernel/bpf/tnum.c                             |  5 ++
 kernel/bpf/verifier.c                         | 17 ++++-
 .../bpf/progs/verifier_bounds_deduction.c     | 17 -----
 .../selftests/bpf/progs/verifier_precision.c  | 70 +++++++++++++++++++
 .../bpf/progs/verifier_value_ptr_arith.c      |  8 +--
 6 files changed, 95 insertions(+), 24 deletions(-)

--
2.47.1

author reviewer
#1 lore raw

PATCH v2 1/2 bpf: Add range tracking for BPF_NEG

Add range tracking for instruction BPF_NEG. Without this logic, a trivial program like the following will fail

    volatile bool found_value_b;
    SEC("lsm.s/socket_connect")
    int BPF_PROG(test_socket_connect)
    {
        if (!found_value_b)
                return -1;
        return 0;
    }

with verifier log:

"At program exit the register R0 has smin=0 smax=4294967295 should have been in [-4095, 0]".

This is because range information is lost in BPF_NEG:

0: R1=ctx() R10=fp0
; if (!found_value_b) @ xxxx.c:24

0: (18) r1 = 0xffa00000011e7048       ; R1_w=map_value(...)
2: (71) r0 = *(u8 *)(r1 +0)           ; R0_w=scalar(smin32=0,smax=255)
3: (a4) w0 ^= 1                       ; R0_w=scalar(smin32=0,smax=255)
4: (84) w0 = -w0                      ; R0_w=scalar(range info lost)

Note that, the log above is manually modified to highlight relevant bits.

Fix this by maintaining proper range information with BPF_NEG, so that the verifier will know:

4: (84) w0 = -w0 ; R0_w=scalar(smin32=-255,smax=0)

Also updated selftests based on the expected behavior.

---
 include/linux/tnum.h                            |  2 ++
 kernel/bpf/tnum.c                               |  5 +++++
 kernel/bpf/verifier.c                           | 17 ++++++++++++++++-
 .../bpf/progs/verifier_bounds_deduction.c       | 17 -----------------
 .../bpf/progs/verifier_value_ptr_arith.c        |  8 ++------
 5 files changed, 25 insertions(+), 24 deletions(-)
include/linux/tnum.h +2 -0
index 3c13240077b8..57ed3035cc30 100644
@@ -40,6 +40,8 @@ struct tnum tnum_arshift(struct tnum a, u8 min_shift, u8 insn_bitness);
 struct tnum tnum_add(struct tnum a, struct tnum b);
 /* Subtract two tnums, return @a - @b */
 struct tnum tnum_sub(struct tnum a, struct tnum b);
+/* Neg of a tnum, return  0 - @a */
+struct tnum tnum_neg(struct tnum a);
 /* Bitwise-AND, return @a & @b */
 struct tnum tnum_and(struct tnum a, struct tnum b);
 /* Bitwise-OR, return @a | @b */
kernel/bpf/tnum.c +5 -0
index 9dbc31b25e3d..fa353c5d550f 100644
@@ -83,6 +83,11 @@ struct tnum tnum_sub(struct tnum a, struct tnum b)
 	return TNUM(dv & ~mu, mu);
 }
 
+struct tnum tnum_neg(struct tnum a)
+{
+	return tnum_sub(TNUM(0, 0), a);
+}
+
 struct tnum tnum_and(struct tnum a, struct tnum b)
 {
 	u64 alpha, beta, v;
kernel/bpf/verifier.c +16 -1
index 279a64933262..ef5ed37e03b6 100644
@@ -15146,6 +15146,7 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	switch (BPF_OP(insn->code)) {
 	case BPF_ADD:
 	case BPF_SUB:
+	case BPF_NEG:
 	case BPF_AND:
 	case BPF_XOR:
 	case BPF_OR:
@@ -15214,6 +15215,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		scalar_min_max_sub(dst_reg, &src_reg);
 		dst_reg->var_off = tnum_sub(dst_reg->var_off, src_reg.var_off);
 		break;
+	case BPF_NEG:
+		env->fake_reg[0] = *dst_reg;
+		__mark_reg_known(dst_reg, 0);
+		scalar32_min_max_sub(dst_reg, &env->fake_reg[0]);
+		scalar_min_max_sub(dst_reg, &env->fake_reg[0]);
+		dst_reg->var_off = tnum_neg(env->fake_reg[0].var_off);
+		break;
 	case BPF_MUL:
 		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
 		scalar32_min_max_mul(dst_reg, &src_reg);
@@ -15437,7 +15445,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		}
 
 		/* check dest operand */
-		err = check_reg_arg(env, insn->dst_reg, DST_OP);
+		if (opcode == BPF_NEG) {
+			err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
+			err = err ?: adjust_scalar_min_max_vals(env, insn,
+							 &regs[insn->dst_reg],
+							 regs[insn->dst_reg]);
+		} else {
+			err = check_reg_arg(env, insn->dst_reg, DST_OP);
+		}
 		if (err)
 			return err;
 
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -17
index c506afbdd936..8d886c15fdcc 100644
@@ -151,21 +151,4 @@ l0_%=:	r0 -= r1;					\
 "	::: __clobber_all);
 }
 
-SEC("socket")
-__description("check deducing bounds from const, 10")
-__failure
-__msg("math between ctx pointer and register with unbounded min value is not allowed")
-__failure_unpriv
-__naked void deducing_bounds_from_const_10(void)
-{
-	asm volatile ("					\
-	r0 = 0;						\
-	if r0 s<= 0 goto l0_%=;				\
-l0_%=:	/* Marks reg as unknown. */			\
-	r0 = -r0;					\
-	r0 -= r1;					\
-	exit;						\
-"	::: __clobber_all);
-}
-
 char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c +2 -6
index fcea9819e359..799eccd181b5 100644
@@ -225,9 +225,7 @@ l2_%=:	r0 = 1;						\
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (lt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_lt(void)
 {
 	asm volatile ("					\
@@ -265,9 +263,7 @@ l2_%=:	r0 = 1;						\
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (gt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_gt(void)
 {
 	asm volatile ("					\
Signature · 1 line
2.47.1
maintainer
#2 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add range tracking for BPF_NEG

On Tue, 2025-06-24 at 15:00 -0700, Song Liu wrote:

[...]

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -3
index c506afbdd936..8d886c15fdcc 100644
@@ -151,21 +151,4 @@ l0_%=:	r0 -= r1;					\
 "	::: __clobber_all);
 }
 
-SEC("socket")
-__description("check deducing bounds from const, 10")
-__failure

tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c l0_%=: r0 -= r1; \ · line 166

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -10
-__msg("math between ctx pointer and register with unbounded min value is not allowed")
-__failure_unpriv
-__naked void deducing_bounds_from_const_10(void)
-{
-	asm volatile ("					\
-	r0 = 0;						\
-	if r0 s<= 0 goto l0_%=;				\
-l0_%=:	/* Marks reg as unknown. */			\
-	r0 = -r0;					\
-	r0 -= r1;					\

It looks like rX = -rX was used in a few tests as a source of unbound scalar values. It is probably not safe to throw these tests away or convert failure->success, unless we are sure the logic is tested elsewhere.

One option to keep the tests is to call bpf_get_prandom_u32() and obtain an unbound value in r0 as a result.

Quoted 31 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -4
-	exit;						\
-"	::: __clobber_all);
-}
-
 char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c +2 -6
index fcea9819e359..799eccd181b5 100644
@@ -225,9 +225,7 @@ l2_%=:	r0 = 1;						\
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (lt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_lt(void)
 {
 	asm volatile ("					\
@@ -265,9 +263,7 @@ l2_%=:	r0 = 1;						\
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (gt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_gt(void)
 {
 	asm volatile ("					\
#3 lore raw

Re: [PATCH v2 bpf-next 1/2] bpf: Add range tracking for BPF_NEG

Quoted 35 lines · Eduard Zingerman

On Tue, 2025-06-24 at 15:00 -0700, Song Liu wrote:

[...]

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -3
index c506afbdd936..8d886c15fdcc 100644
@@ -151,21 +151,4 @@ l0_%=: r0 -= r1; \
 " ::: __clobber_all);
 }
 
-SEC("socket")
-__description("check deducing bounds from const, 10")
-__failure

tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c l0_%=: r0 -= r1; \ · line 166

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -10
-__msg("math between ctx pointer and register with unbounded min value is not allowed")
-__failure_unpriv
-__naked void deducing_bounds_from_const_10(void)
-{
- asm volatile (" \
- r0 = 0; \
- if r0 s<= 0 goto l0_%=; \
-l0_%=: /* Marks reg as unknown. */ \
- r0 = -r0; \
- r0 -= r1; \

It looks like rX = -rX was used in a few tests as a source of unbound scalar values. It is probably not safe to throw these tests away or convert failure->success, unless we are sure the logic is tested elsewhere.

Quoted 2 lines

One option to keep the tests is to call bpf_get_prandom_u32() and obtain an unbound value in r0 as a result.

I thought this test was to verify BPF_NEG turns known const into unknown, so I removed it. But I guess we still need a test to trigger "math between ctx pointer and register with unbounded min value"

Let me add it back.

Thanks,
Song

Quoted 32 lines
Quoted 32 lines
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -4
- exit; \
-" ::: __clobber_all);
-}
-
 char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c +2 -6
index fcea9819e359..799eccd181b5 100644
@@ -225,9 +225,7 @@ l2_%=: r0 = 1; \
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (lt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_lt(void)
 {
 asm volatile (" \
@@ -265,9 +263,7 @@ l2_%=: r0 = 1; \
 
 SEC("socket")
 __description("map access: known scalar += value_ptr unknown vs unknown (gt)")
-__success __failure_unpriv
-__msg_unpriv("R1 tried to add from different maps, paths or scalars")
-__retval(1)
+__success __success_unpriv __retval(1)
 __naked void ptr_unknown_vs_unknown_gt(void)
 {
 asm volatile (" \
author reviewer
#4 lore raw

PATCH v2 2/2 selftests/bpf: Add tests for BPF_NEG range tracking logic

In reply to Song Liu

BPF_REG now has range tracking logic. Add selftests for BPF_NEG. Specifically, return value of LSM hook lsm.s/socket_connect is used to show that the verifer tracks BPF_NEG(1) falls in the [-4095, 0] range; while BPF_NEG(100000) does not fall in that range.

---
 .../selftests/bpf/progs/verifier_precision.c  | 70 +++++++++++++++++++
 1 file changed, 70 insertions(+)
tools/testing/selftests/bpf/progs/verifier_precision.c +70 -0
index 9fe5d255ee37..b6aca92e592f 100644
@@ -231,4 +231,74 @@ __naked void bpf_cond_op_not_r10(void)
 	::: __clobber_all);
 }
 
+SEC("lsm.s/socket_connect")
+__success __log_level(2)
+__msg("0: (b7) r0 = 1")
+__msg("1: (84) w0 = -w0")
+__msg("mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1")
+__msg("mark_precise: frame0: regs=r0 stack= before 1: (84) w0 = -w0")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 1")
+__naked int bpf_neg_2(void)
+{
+	/*
+	 * lsm.s/socket_connect requires a return value within [-4095, 0].
+	 * Returning -1 is allowed
+	 */
+	asm volatile (
+	"r0 = 1;"
+	"w0 = -w0;"
+	"exit;"
+	::: __clobber_all);
+}
+
+SEC("lsm.s/socket_connect")
+__failure __msg("At program exit the register R0 has")
+__naked int bpf_neg_3(void)
+{
+	/*
+	 * lsm.s/socket_connect requires a return value within [-4095, 0].
+	 * Returning -10000 is not allowed.
+	 */
+	asm volatile (
+	"r0 = 10000;"
+	"w0 = -w0;"
+	"exit;"
+	::: __clobber_all);
+}
+
+SEC("lsm.s/socket_connect")
+__success __log_level(2)
+__msg("0: (b7) r0 = 1")
+__msg("1: (87) r0 = -r0")
+__msg("mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1")
+__msg("mark_precise: frame0: regs=r0 stack= before 1: (87) r0 = -r0")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 1")
+__naked int bpf_neg_4(void)
+{
+	/*
+	 * lsm.s/socket_connect requires a return value within [-4095, 0].
+	 * Returning -1 is allowed
+	 */
+	asm volatile (
+	"r0 = 1;"
+	"r0 = -r0;"
+	"exit;"
+	::: __clobber_all);
+}
+
+SEC("lsm.s/socket_connect")
+__failure __msg("At program exit the register R0 has")
+__naked int bpf_neg_5(void)
+{
+	/*
+	 * lsm.s/socket_connect requires a return value within [-4095, 0].
+	 * Returning -10000 is not allowed.
+	 */
+	asm volatile (
+	"r0 = 10000;"
+	"r0 = -r0;"
+	"exit;"
+	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
maintainer
#5 lore raw

Re: [PATCH v2 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic

On Tue, 2025-06-24 at 15:00 -0700, Song Liu wrote:

[...]

tools/testing/selftests/bpf/progs/verifier_precision.c __naked void bpf_cond_op_not_r10(void) · line 237

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +4 -0
+SEC("lsm.s/socket_connect")
+__success __log_level(2)
+__msg("0: (b7) r0 = 1")
+__msg("1: (84) w0 = -w0")

Sorry, my previous comment probably was ambiguous.
What I meant is that you can match verifier output for "w0 = -w0 ; R0=-1", thus checking that inferred value for "w0".

Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +15 -0
+__msg("mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1")
+__msg("mark_precise: frame0: regs=r0 stack= before 1: (84) w0 = -w0")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 1")
+__naked int bpf_neg_2(void)
+{
+	/*
+	 * lsm.s/socket_connect requires a return value within [-4095, 0].
+	 * Returning -1 is allowed
+	 */
+	asm volatile (
+	"r0 = 1;"
+	"w0 = -w0;"
+	"exit;"
+	::: __clobber_all);
+}

[...]

#6 lore raw

Re: [PATCH v2 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic

Quoted 8 lines · Eduard Zingerman

On Tue, 2025-06-24 at 15:00 -0700, Song Liu wrote:

[...]

Quoted 8 lines

tools/testing/selftests/bpf/progs/verifier_precision.c __naked void bpf_cond_op_not_r10(void) · line 237

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +4 -0
+SEC("lsm.s/socket_connect")
+__success __log_level(2)
+__msg("0: (b7) r0 = 1")
+__msg("1: (84) w0 = -w0")

Sorry, my previous comment probably was ambiguous.
What I meant is that you can match verifier output for "w0 = -w0 ; R0=-1", thus checking that inferred value for "w0".

Ah, I removed that part because I found some other __msg doesn’t have the whole line. Let me add it back.

Thanks,
Song

Quoted 18 lines
Quoted 16 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +15 -0
+__msg("mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1")
+__msg("mark_precise: frame0: regs=r0 stack= before 1: (84) w0 = -w0")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 1")
+__naked int bpf_neg_2(void)
+{
+ /*
+ * lsm.s/socket_connect requires a return value within [-4095, 0].
+ * Returning -1 is allowed
+ */
+ asm volatile (
+ "r0 = 1;"
+ "w0 = -w0;"
+ "exit;"
+ ::: __clobber_all);
+}

[...]

maintainer
#7 lore raw

Re: [PATCH v2 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic

Quoted 16 lines · Song Liu
Quoted 7 lines · Eduard Zingerman

On Tue, 2025-06-24 at 15:00 -0700, Song Liu wrote:

[...]

Quoted 8 lines

tools/testing/selftests/bpf/progs/verifier_precision.c __naked void bpf_cond_op_not_r10(void) · line 237

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +4 -0
+SEC("lsm.s/socket_connect")
+__success __log_level(2)
+__msg("0: (b7) r0 = 1")
+__msg("1: (84) w0 = -w0")

Sorry, my previous comment probably was ambiguous.
What I meant is that you can match verifier output for "w0 = -w0 ; R0=-1", thus checking that inferred value for "w0".

Quoted 2 lines

Ah, I removed that part because I found some other __msg doesn’t have the whole line. Let me add it back.

Note: if you need to shorten the matched line you can use regexs

      inside __msg strings: __msg("... {{regex-here}} ...")
Quoted 21 lines

Thanks,
Song

Quoted 18 lines
Quoted 16 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +15 -0
+__msg("mark_precise: frame0: last_idx 2 first_idx 0 subseq_idx -1")
+__msg("mark_precise: frame0: regs=r0 stack= before 1: (84) w0 = -w0")
+__msg("mark_precise: frame0: regs=r0 stack= before 0: (b7) r0 = 1")
+__naked int bpf_neg_2(void)
+{
+ /*
+ * lsm.s/socket_connect requires a return value within [-4095, 0].
+ * Returning -1 is allowed
+ */
+ asm volatile (
+ "r0 = 1;"
+ "w0 = -w0;"
+ "exit;"
+ ::: __clobber_all);
+}

[...]