* [PATCH v3 bpf-next 0/2] Range tracking for BPF_NEG
@ 2025-06-24 23:33 Song Liu
2025-06-24 23:33 ` [PATCH v3 bpf-next 1/2] bpf: Add range " Song Liu
2025-06-24 23:33 ` [PATCH v3 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic Song Liu
0 siblings, 2 replies; 5+ messages in thread
From: Song Liu @ 2025-06-24 23:33 UTC (permalink / raw)
To: bpf; +Cc: kernel-team, andrii, eddyz87, ast, daniel, martin.lau, Song Liu
Add range tracking for BPF_NEG. Please see commit log of 1/2 for more
details.
---
Changes v2 => v3:
1. Minor changes in the selftests. (Eduard)
v2: https://lore.kernel.org/bpf/20250624220038.656646-1-song@kernel.org/
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/20250624172320.2923031-1-song@kernel.org/
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 | 11 +--
.../selftests/bpf/progs/verifier_precision.c | 70 +++++++++++++++++++
.../bpf/progs/verifier_value_ptr_arith.c | 8 +--
6 files changed, 102 insertions(+), 11 deletions(-)
--
2.47.1
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH v3 bpf-next 1/2] bpf: Add range tracking for BPF_NEG
2025-06-24 23:33 [PATCH v3 bpf-next 0/2] Range tracking for BPF_NEG Song Liu
@ 2025-06-24 23:33 ` Song Liu
2025-06-25 0:29 ` Eduard Zingerman
2025-06-24 23:33 ` [PATCH v3 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic Song Liu
1 sibling, 1 reply; 5+ messages in thread
From: Song Liu @ 2025-06-24 23:33 UTC (permalink / raw)
To: bpf; +Cc: kernel-team, andrii, eddyz87, ast, daniel, martin.lau, 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:
4: (84) w0 = -w0 ; R0_w=scalar(smin32=-255,smax=0)
Also updated selftests based on the expected behavior.
Signed-off-by: Song Liu <song@kernel.org>
---
include/linux/tnum.h | 2 ++
kernel/bpf/tnum.c | 5 +++++
kernel/bpf/verifier.c | 17 ++++++++++++++++-
.../bpf/progs/verifier_bounds_deduction.c | 11 +++++++----
.../bpf/progs/verifier_value_ptr_arith.c | 8 ++------
5 files changed, 32 insertions(+), 11 deletions(-)
diff --git a/include/linux/tnum.h b/include/linux/tnum.h
index 3c13240077b8..57ed3035cc30 100644
--- a/include/linux/tnum.h
+++ b/include/linux/tnum.h
@@ -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 */
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 9dbc31b25e3d..fa353c5d550f 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -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;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 279a64933262..ef5ed37e03b6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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,
+ ®s[insn->dst_reg],
+ regs[insn->dst_reg]);
+ } else {
+ err = check_reg_arg(env, insn->dst_reg, DST_OP);
+ }
if (err)
return err;
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c b/tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c
index c506afbdd936..260a6df264e3 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c
@@ -159,13 +159,16 @@ __failure_unpriv
__naked void deducing_bounds_from_const_10(void)
{
asm volatile (" \
+ r6 = r1; \
r0 = 0; \
if r0 s<= 0 goto l0_%=; \
-l0_%=: /* Marks reg as unknown. */ \
- r0 = -r0; \
- r0 -= r1; \
+l0_%=: /* Marks r0 as unknown. */ \
+ call %[bpf_get_prandom_u32]; \
+ r0 -= r6; \
exit; \
-" ::: __clobber_all);
+" :
+ : __imm(bpf_get_prandom_u32)
+ : __clobber_all);
}
char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
index fcea9819e359..799eccd181b5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
+++ b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
@@ -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 (" \
--
2.47.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH v3 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic
2025-06-24 23:33 [PATCH v3 bpf-next 0/2] Range tracking for BPF_NEG Song Liu
2025-06-24 23:33 ` [PATCH v3 bpf-next 1/2] bpf: Add range " Song Liu
@ 2025-06-24 23:33 ` Song Liu
1 sibling, 0 replies; 5+ messages in thread
From: Song Liu @ 2025-06-24 23:33 UTC (permalink / raw)
To: bpf; +Cc: kernel-team, andrii, eddyz87, ast, daniel, martin.lau, 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.
Signed-off-by: Song Liu <song@kernel.org>
---
.../selftests/bpf/progs/verifier_precision.c | 70 +++++++++++++++++++
1 file changed, 70 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_precision.c b/tools/testing/selftests/bpf/progs/verifier_precision.c
index 9fe5d255ee37..73fee2aec698 100644
--- a/tools/testing/selftests/bpf/progs/verifier_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_precision.c
@@ -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 ; R0_w=1")
+__msg("1: (84) w0 = -w0 ; R0_w=0xffffffff")
+__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 ; R0_w=1")
+__msg("1: (87) r0 = -r0 ; R0_w=-1")
+__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";
--
2.47.1
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v3 bpf-next 1/2] bpf: Add range tracking for BPF_NEG
2025-06-24 23:33 ` [PATCH v3 bpf-next 1/2] bpf: Add range " Song Liu
@ 2025-06-25 0:29 ` Eduard Zingerman
2025-06-25 3:31 ` Song Liu
0 siblings, 1 reply; 5+ messages in thread
From: Eduard Zingerman @ 2025-06-25 0:29 UTC (permalink / raw)
To: Song Liu, bpf; +Cc: kernel-team, andrii, ast, daniel, martin.lau
On Tue, 2025-06-24 at 16:33 -0700, Song Liu wrote:
[...]
> diff --git a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
> index fcea9819e359..799eccd181b5 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
> @@ -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 (" \
Apologies for not being clear in previous messages.
Could you please avoid flipping these tests from __failure_unpriv to __success_unpriv?
Instead, the tests should be rewritten to conjure an unbound scalar
value in some different way. For example like below:
diff --git a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
index fcea9819e359..3593b15d11af 100644
--- a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
+++ b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
@@ -231,6 +231,10 @@ __retval(1)
__naked void ptr_unknown_vs_unknown_lt(void)
{
asm volatile (" \
+ r8 = r1; \
+ call %[bpf_get_prandom_u32]; \
+ r9 = r0; \
+ r1 = r8; \
r0 = *(u32*)(r1 + %[__sk_buff_len]); \
r1 = 0; \
*(u64*)(r10 - 8) = r1; \
@@ -244,12 +248,10 @@ l1_%=: call %[bpf_map_lookup_elem]; \
if r0 == 0 goto l2_%=; \
r4 = *(u8*)(r0 + 0); \
if r4 == 1 goto l3_%=; \
- r1 = 6; \
- r1 = -r1; \
+ r1 = r9; \
r1 &= 0x3; \
goto l4_%=; \
-l3_%=: r1 = 6; \
- r1 = -r1; \
+l3_%=: r1 = r9; \
r1 &= 0x7; \
l4_%=: r1 += r0; \
r0 = *(u8*)(r1 + 0); \
@@ -259,7 +261,8 @@ l2_%=: r0 = 1; \
: __imm(bpf_map_lookup_elem),
__imm_addr(map_array_48b),
__imm_addr(map_hash_16b),
- __imm_const(__sk_buff_len, offsetof(struct __sk_buff, len))
+ __imm_const(__sk_buff_len, offsetof(struct __sk_buff, len)),
+ __imm(bpf_get_prandom_u32)
: __clobber_all);
}
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v3 bpf-next 1/2] bpf: Add range tracking for BPF_NEG
2025-06-25 0:29 ` Eduard Zingerman
@ 2025-06-25 3:31 ` Song Liu
0 siblings, 0 replies; 5+ messages in thread
From: Song Liu @ 2025-06-25 3:31 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Song Liu, bpf@vger.kernel.org, Kernel Team, andrii@kernel.org,
ast@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev
> On Jun 24, 2025, at 5:29 PM, Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2025-06-24 at 16:33 -0700, Song Liu wrote:
>
> [...]
>
>> diff --git a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
>> index fcea9819e359..799eccd181b5 100644
>> --- a/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
>> +++ b/tools/testing/selftests/bpf/progs/verifier_value_ptr_arith.c
>> @@ -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 (" \
>
> Apologies for not being clear in previous messages.
> Could you please avoid flipping these tests from __failure_unpriv to __success_unpriv?
> Instead, the tests should be rewritten to conjure an unbound scalar
> value in some different way.
I see. This is indeed the right approach.
Thanks,
Song
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2025-06-25 3:31 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2025-06-24 23:33 [PATCH v3 bpf-next 0/2] Range tracking for BPF_NEG Song Liu
2025-06-24 23:33 ` [PATCH v3 bpf-next 1/2] bpf: Add range " Song Liu
2025-06-25 0:29 ` Eduard Zingerman
2025-06-25 3:31 ` Song Liu
2025-06-24 23:33 ` [PATCH v3 bpf-next 2/2] selftests/bpf: Add tests for BPF_NEG range tracking logic Song Liu
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.