Skip to contentSkip to conversation

bpf: Add range tracking for BPF_NEG

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

Subsystems (4)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Song Liu

author reviewer
#0 lore raw

PATCH 1/1 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 add selftests to make sure the logic works as expected.

---
 include/linux/tnum.h                          |  2 ++
 kernel/bpf/tnum.c                             |  5 ++++
 kernel/bpf/verifier.c                         | 18 ++++++++++-
 .../selftests/bpf/progs/verifier_precision.c  | 30 +++++++++++++++++++
 4 files changed, 54 insertions(+), 1 deletion(-)
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 +17 -1
index 279a64933262..93512596a590 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,14 @@ 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:
+		struct bpf_reg_state dst_reg_copy = *dst_reg;
+
+		___mark_reg_known(dst_reg, 0);
+		scalar32_min_max_sub(dst_reg, &dst_reg_copy);
+		scalar_min_max_sub(dst_reg, &dst_reg_copy);
+		dst_reg->var_off = tnum_neg(dst_reg_copy.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 +15446,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_precision.c +30 -0
index 9fe5d255ee37..bcff70f8cebb 100644
@@ -231,4 +231,34 @@ __naked void bpf_cond_op_not_r10(void)
 	::: __clobber_all);
 }
 
+SEC("lsm.s/socket_connect")
+__success
+__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);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
maintainer
#1 lore raw
Quoted 31 lines · Song Liu

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:

Quoted 6 lines

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

Also add selftests to make sure the logic works as expected.

---

I double-checked and backtrack_insn operates as expected indeed.

Note, bpf_reg_state->id has to be reset on BPF_NEG otherwise the following is possible:

4: (bf) r2 = r1 ; R1_w=scalar(id=2,...) R2_w=scalar(id=2,...)
5: (87) r1 = -r1 ; R1_w=scalar(id=2,...)

On the master the id is reset by mark_reg_unknown.
This id is used to transfer range knowledge over all scalars with the same id.

[...]

Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index 279a64933262..93512596a590 100644

[...]

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 15219

Quoted 6 lines
kernel/bpf/verifier.c +2 -0
@@ -15214,6 +15215,14 @@ 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:
+		struct bpf_reg_state dst_reg_copy = *dst_reg;

Nit: there might be a concern regarding stack usage.
In struct bpf_verifier_env there are a few 'fake_reg' scratch registers defined for similar purpose.
Also clangd warns me that declaration after label is a c23 extension.

Quoted 9 lines
kernel/bpf/verifier.c +6 -0
+
+		___mark_reg_known(dst_reg, 0);
+		scalar32_min_max_sub(dst_reg, &dst_reg_copy);
+		scalar_min_max_sub(dst_reg, &dst_reg_copy);
+		dst_reg->var_off = tnum_neg(dst_reg_copy.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);

[...]

tools/testing/selftests/bpf/progs/verifier_precision.c

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +0 -0
index 9fe5d255ee37..bcff70f8cebb 100644

Nit: tests are usually a separate patch.

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

Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +3 -0
@@ -231,4 +231,34 @@ __naked void bpf_cond_op_not_r10(void)
 	::: __clobber_all);
 }
 
+SEC("lsm.s/socket_connect")
+__success
+__naked int bpf_neg_2(void)

Nit: I'd match __log_level(2) output to check the actual range
inferred by verifier.

Maybe add a test that operates on 64-bit registers?

[...]

#2 lore raw

Hi Eduard,

Thanks for your kind review!

Quoted 1 line · Eduard Zingerman

[...]

Quoted 7 lines
Quoted 1 line

---

I double-checked and backtrack_insn operates as expected indeed.

Note, bpf_reg_state->id has to be reset on BPF_NEG otherwise the following is possible:

Quoted 6 lines

4: (bf) r2 = r1 ; R1_w=scalar(id=2,...) R2_w=scalar(id=2,...)
5: (87) r1 = -r1 ; R1_w=scalar(id=2,...)

On the master the id is reset by mark_reg_unknown.
This id is used to transfer range knowledge over all scalars with the same id.

I think we should use "__mark_reg_known(dst_reg, 0);" here?

[...]

Quoted 6 lines

tools/testing/selftests/bpf/progs/verifier_precision.c

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +0 -0
index 9fe5d255ee37..bcff70f8cebb 100644

Nit: tests are usually a separate patch.

CI found that a few existing tests need updating. I will include fixes to existing tests in the same patch as the kernel changes, and add new tests in a separate patch.

Quoted 10 lines
(quoted diff) +0 -0
@@ -231,4 +231,34 @@ __naked void bpf_cond_op_not_r10(void)
 > ::: __clobber_all);
 > }

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

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_precision.c +3 -0
+SEC("lsm.s/socket_connect")
+__success
+__naked int bpf_neg_2(void)

Nit: I'd match __log_level(2) output to check the actual range
inferred by verifier.

I tried __log_level(2). However, this program is so simple that the verifier log is really simple:

VERIFIER LOG:
=============
processed 3 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
=============

So I didn’t include __log_level(2) here.

Quoted 2 lines

Maybe add a test that operates on 64-bit registers?

Will add that in v2.

Thanks,
Song

maintainer
#3 lore raw

On Tue, 2025-06-24 at 20:50 +0000, Song Liu wrote:

[...]

Quoted 11 lines
Quoted 9 lines

Note, bpf_reg_state->id has to be reset on BPF_NEG otherwise the following is possible:

4: (bf) r2 = r1 ; R1_w=scalar(id=2,...) R2_w=scalar(id=2,...)
5: (87) r1 = -r1 ; R1_w=scalar(id=2,...)

On the master the id is reset by mark_reg_unknown.
This id is used to transfer range knowledge over all scalars with the same id.

I think we should use "__mark_reg_known(dst_reg, 0);" here?

That's an option, yes.

[...]

Quoted 6 lines
Quoted 2 lines

Nit: I'd match __log_level(2) output to check the actual range
inferred by verifier.

I tried __log_level(2). However, this program is so simple that the verifier log is really simple:

Quoted 6 lines

VERIFIER LOG:
=============
processed 3 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
=============

So I didn’t include __log_level(2) here.

When __log_level(2) is specified every instruction visited by verifier should be printed in the log with range info etc.
E.g. see verifier_precision.c:bpf_cond_op_not_r10().

If that is not working for you could you please share a branch on gh or something like that?

#4 lore raw
Quoted 35 lines · Eduard Zingerman

On Tue, 2025-06-24 at 20:50 +0000, Song Liu wrote:

[...]

Quoted 11 lines
Quoted 9 lines

Note, bpf_reg_state->id has to be reset on BPF_NEG otherwise the following is possible:

4: (bf) r2 = r1 ; R1_w=scalar(id=2,...) R2_w=scalar(id=2,...)
5: (87) r1 = -r1 ; R1_w=scalar(id=2,...)

On the master the id is reset by mark_reg_unknown.
This id is used to transfer range knowledge over all scalars with the same id.

I think we should use "__mark_reg_known(dst_reg, 0);" here?

That's an option, yes.

[...]

Quoted 11 lines
Quoted 2 lines

Nit: I'd match __log_level(2) output to check the actual range
inferred by verifier.

I tried __log_level(2). However, this program is so simple that the verifier log is really simple:

VERIFIER LOG:
=============
processed 3 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
=============

Quoted 8 lines
Quoted 1 line

So I didn’t include __log_level(2) here.

When __log_level(2) is specified every instruction visited by verifier should be printed in the log with range info etc.
E.g. see verifier_precision.c:bpf_cond_op_not_r10().

If that is not working for you could you please share a branch on gh or something like that?

Ah, I was assuming "test_progs -vv” is the same as __log_level(2), which is not accurate. Now I can see the log.

Thanks,
Song