bpf: Add range tracking for BPF_NEG
Subsystems (4)
Song Liu
reviewerPATCH 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
@@ -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 +17 -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,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, + ®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_precision.c +30 -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 ) +{ +/* +* 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); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
Eduard Zingerman
maintainerQuoted 31 lines · Song Liu
Add range tracking for instruction
BPF_NEG. Without this logic, a trivial program like the following will failvolatile 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:240: (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.
Signed-off-by Song Liu <[email protected]>---
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
[...]
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
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?
[...]
Hi Eduard,
Thanks for your kind review!
Quoted 1 line · Eduard Zingerman
[...]
Quoted 7 lines
Quoted 1 line
---
I double-checked and
backtrack_insnoperates as expected indeed.Note,
bpf_reg_state->idhas to be reset onBPF_NEGotherwise 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
-0Nit: 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
Eduard Zingerman
maintainerOn Tue, 2025-06-24 at 20:50 +0000, Song Liu wrote:
[...]
Quoted 11 lines
Quoted 9 lines
Note,
bpf_reg_state->idhas to be reset onBPF_NEGotherwise 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_insn0total_states0peak_states0mark_read0
=============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?
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->idhas to be reset onBPF_NEGotherwise 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_insn0total_states0peak_states0mark_read0
=============
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