Range tracking for BPF_NEG
Subsystems (4)
Song Liu
reviewerv2 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
Song Liu
reviewerPATCH 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
@@ -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
@@ -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
@@ -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;
tools/testing/selftests/bpf/progs/verifier_bounds_deduction.c +0 -17
@@ -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 ) -{ - asmvolatile (" \ -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
@@ -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
Eduard Zingerman
maintainerRe: [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@@ -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@@ -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 (" \
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@@ -151,21 +151,4 @@ l0_%=: r0 -= r1; \ " ::: __clobber_all); } -SEC("socket") -__description ("check deducing bounds from const, 10" ) -__failuretools/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@@ -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 (" \
Song Liu
reviewerPATCH v2 2/2 selftests/bpf: Add tests for BPF_NEG range tracking logic
In reply to Song LiuBPF_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
@@ -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 +*/ + asmvolatile ( +"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. +*/ + asmvolatile ( +"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 +*/ + asmvolatile ( +"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. +*/ + asmvolatile ( +"r0 = 10000;" +"r0 = -r0;" +"exit;" + ::: __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
Eduard Zingerman
maintainerRe: [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 +*/ + asmvolatile ( +"r0 = 1;" +"w0 = -w0;" +"exit;" + ::: __clobber_all); +}
[...]
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 +*/ + asmvolatile ( +"r0 = 1;" +"w0 = -w0;" +"exit;" + ::: __clobber_all); +}[...]
Eduard Zingerman
maintainerRe: [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
__msgdoesn’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,
SongQuoted 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 +*/ + asmvolatile ( +"r0 = 1;" +"w0 = -w0;" +"exit;" + ::: __clobber_all); +}[...]