verify scalar ids mapping in regsafe()
Subsystems (4)
Eduard Zingerman
maintainerv3 cover verify scalar ids mapping in regsafe()
Update regsafe() to use check_ids() for scalar values. Otherwise the following unsafe pattern is accepted by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = Y
This example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
Currently regsafe() does not call check_ids() for scalar registers, thus from POV of regsafe() states (I) and (II) are identical.
The change is split in two parts:
- patches #1,2: update for mark_chain_precision() to propagate precision marks through scalar IDs.
- patches #3,4: update for regsafe() to use check_ids() for precise scalar values.
Changelog:
- V2 -> V3:
- u32_hashset for IDs used for range transfer is removed;
- mark_chain_precision() is updated as discussed with Andrii in [2].
- V1 -> v2:
- 'rold->precise' and 'rold->id' checks are dropped as unsafe
(thanks to discussion with Yonghong);
- patches #3,4 adding tracking of ids used for range transfer in order to mitigate performance impact.
- RFC -> V1:
- Function verifier.c:mark_equal_scalars_as_read() is dropped, as it was an incorrect fix for problem solved by commit [3].
- check_ids() is called only for precise scalar values.
- Test case updated to use inline assembly.
[V1] https://lore.kernel.org/bpf/[email protected]/
[V2] https://lore.kernel.org/bpf/[email protected]/T/
[RFC] https://lore.kernel.org/bpf/[email protected]/
[1] https://gist.github.com/eddyz87/a32ea7e62a27d3c201117c9a39ab4286
[2] https://lore.kernel.org/bpf/[email protected]/T/#mc21009dcd8574b195c1860a98014bb037f16f450
Eduard Zingerman (4):
bpf: use scalar ids in mark_chain_precision() selftests/bpf: check if mark_chain_precision() follows scalar ids
bpf: verify scalar ids mapping in regsafe() using check_ids() selftests/bpf: verify that check_ids() is used for scalars in
regsafe()
include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 148 ++++- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 508 ++++++++++++++++++ .../bpf/progs/verifier_search_pruning.c | 3 +- .../testing/selftests/bpf/verifier/precise.c | 8 +- 6 files changed, 669 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Signature · 1 line
2.40.1
Eduard Zingerman
maintainerPATCH v3 1/4 bpf: use scalar ids in mark_chain_precision()
Change mark_chain_precision() to track precision in situations like below:
r2 = unknown value
...
--- state #0 ---
...
r1 = r2 // r1 and r2 now share the same ID
...
--- state #1 {r1.id = A, r2.id = A} ---
...
if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1
...
--- state #2 {r1.id = A, r2.id = A} ---
r3 = r10
r3 += r1 // need to mark both r1 and r2At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise.
This property would be used by a follow-up change in regsafe().
--- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)
include/linux/bpf_verifier.h +9 -1
@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct reg_id_scratch { +u32 count; +u32 ids[BPF_ID_MAP_SIZE ]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */
@@ -590,7 +595,10 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +union { +struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct reg_id_scratch precise_ids_scratch; + };struct {int *insn_state;int *insn_stack;
kernel/bpf/verifier.c +114 -0
126 lines not on this page · raw message
tools/testing/selftests/bpf/verifier/precise.c +4 -4
@@ -46,7 +46,7 @@ mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 19 first_idx 10\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: regs=r0,r9 stack= before 15\
@@ -106,10 +106,10 @@ mark_precise: frame0: regs=r2 stack= before 22\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ - mark_precise: frame0: regs=r2 stack= before 20\ - mark_precise: frame0: parent state regs=r2 stack=:\ + mark_precise: frame0: regs=r2,r9 stack= before 20\ + mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 17\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: parent state regs= stack=:",
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 48 lines · Eduard Zingerman
Change
mark_chain_precision()to track precision in situations like below:r2 = unknown value
...
--- state #0 ---... r1 = r2 // r1 and r2 now share the same ID ... --- state #1 {r1.id = A, r2.id = A} --- ... if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 ... --- state #2 {r1.id = A, r2.id = A} --- r3 = r10 r3 += r1 // need to mark both r1 and r2At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise.
This property would be used by a follow-up change in
regsafe().Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)include/linux/bpf_verifier.h +5
-0@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct reg_id_scratch { +u32 count; +u32 ids[BPF_ID_MAP_SIZE ]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */
include/linux/bpf_verifier.h struct bpf_verifier_env { · line 600
Quoted 7 lines
include/linux/bpf_verifier.h +3
-1@@ -590,7 +595,10 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +union { +struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct reg_id_scratch precise_ids_scratch;
naming nit: "ids_scratch" or "idset_scratch" to stay in line with "idmap_scratch"?
Quoted 18 lines
include/linux/bpf_verifier.h +1
-0+ };struct {int *insn_state;int *insn_stack;kernel/bpf/verifier.c +6
-0@@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static inline bool reg_id_scratch_contains (struct reg_id_scratch *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i) +if (s->ids[i] == id)
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3797
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+return true; + +return false; +} + +static inline int reg_id_scratch_push (struct reg_id_scratch *s,u32 id) +{ +if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) +return -1 ; + s->ids[s->count++] = id;
this will allow duplicated IDs to be added? Was it done in the name of speed?
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3799
Quoted 2 lines
kernel/bpf/verifier.c +2
-0+WARN_ONCE (s->count >64 , +"reg_id_scratch.count is unreasonably large (%d)" , s->count);
do we need this one? Especially that it's not _ONCE variant? Maybe the first WARN_ON_ONCE is enough?
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3803
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+return 0 ; +} + +static inline void reg_id_scratch_reset (struct reg_id_scratch *s)
we probably don't need "inline" for all these helpers?
Quoted 28 lines
kernel/bpf/verifier.c +28
-0+{ + s->count =0 ; +} + +/* Collect a set of IDs for all registers currently marked as precise in env->bt. +* Mark all registers with these IDs as precise. +*/ +static void mark_precise_scalar_ids (struct bpf_verifier_env *env,struct bpf_verifier_state *st) +{ +struct reg_id_scratch *precise_ids = &env->precise_ids_scratch; +struct backtrack_state *bt = &env->bt; +struct bpf_func_state *func; +struct bpf_reg_state *reg; +DECLARE_BITMAP (mask,64 ); +int i, fr; + +reg_id_scratch_reset (precise_ids); + +for (fr = bt->frame; fr >=0 ; fr--) { + func = st->frame[fr]; + +bitmap_from_u64 (mask,bt_frame_reg_mask (bt, fr)); +for_each_set_bit (i, mask,32 ) { + reg = &func->regs[i]; +if (!reg->id || reg->type !=SCALAR_VALUE ) +continue ; +if (reg_id_scratch_push (precise_ids, reg->id)) +return ;
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3841
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+ } + +bitmap_from_u64 (mask,bt_frame_stack_mask (bt, fr)); +for_each_set_bit (i, mask,64 ) { +if (i >= func->allocated_stack /BPF_REG_SIZE ) +break ; +if (!is_spilled_scalar_reg (&func->stack[i])) +continue ; + reg = &func->stack[i].spilled_ptr; +if (!reg->id || reg->type !=SCALAR_VALUE )
is_spilled_scalar_reg() already ensures reg->type is SCALAR_VALUE
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3831
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+continue ; +if (reg_id_scratch_push (precise_ids, reg->id)) +return ;
if push fails (due to overflow of id set), shouldn't we propagate error back and fallback to mark_all_precise?
Quoted 91 lines
kernel/bpf/verifier.c +51
-0+ } + } + +for (fr =0 ; fr <= st->curframe; ++fr) { + func = st->frame[fr]; + +for (i =BPF_REG_0 ; i <BPF_REG_10 ; ++i) { + reg = &func->regs[i]; +if (!reg->id) +continue ; +if (!reg_id_scratch_contains (precise_ids, reg->id)) +continue ; +bt_set_frame_reg (bt, fr, i); + } +for (i =0 ; i < func->allocated_stack /BPF_REG_SIZE ; ++i) { +if (!is_spilled_scalar_reg (&func->stack[i])) +continue ; + reg = &func->stack[i].spilled_ptr; +if (!reg->id) +continue ; +if (!reg_id_scratch_contains (precise_ids, reg->id)) +continue ; +bt_set_frame_slot (bt, fr, i); + } + } +} +/* * __mark_chain_precision() backtracks BPF program instruction sequence and * chain of verifier states making sure that register *regno* (if regno >= 0) @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) bt->frame, last_idx, first_idx, subseq_idx); } +/* If some register with scalar ID is marked as precise, +* make sure that all registers sharing this ID are also precise. +* This is needed to estimate effect of find_equal_scalars(). +* Do this at the last instruction of each state, +* bpf_reg_state::id fields are valid for these instructions. +* +* Allows to track precision in situation like below: +* +* r2 = unknown value +* ... +* --- state #0 --- +* ... +* r1 = r2 // r1 and r2 now share the same ID +* ... +* --- state #1 {r1.id = A, r2.id = A} --- +* ... +* if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 +* ... +* --- state #2 {r1.id = A, r2.id = A} --- +* r3 = r10 +* r3 += r1 // need to mark both r1 and r2 +*/ +mark_precise_scalar_ids (env, st); +if (last_idx <0 ) {/* we are at the entry into subprog, which * is expected for global funcs, but only if tools/testing/selftests/bpf/verifier/precise.c +4
-5@@ -46,7 +46,7 @@ mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 19 first_idx 10\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: regs=r0,r9 stack= before 15\@@ -106,10 +106,10 @@ mark_precise: frame0: regs=r2 stack= before 22\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ - mark_precise: frame0: regs=r2 stack= before 20\ - mark_precise: frame0: parent state regs=r2 stack=:\ + mark_precise: frame0: regs=r2,r9 stack= before 20\ + mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 17\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: parent state regs= stack=:", --2.40.1
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 51 lines · Andrii Nakryiko
Quoted 50 lines · Eduard Zingerman
Change
mark_chain_precision()to track precision in situations like below:r2 = unknown value
...
--- state #0 ---... r1 = r2 // r1 and r2 now share the same ID ... --- state #1 {r1.id = A, r2.id = A} --- ... if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 ... --- state #2 {r1.id = A, r2.id = A} --- r3 = r10 r3 += r1 // need to mark both r1 and r2At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise.
This property would be used by a follow-up change in
regsafe().Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)include/linux/bpf_verifier.h +5
-0@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct reg_id_scratch { +u32 count; +u32 ids[BPF_ID_MAP_SIZE ]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */ @@ -590,7 +595,10 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;
Quoted 8 lines
include/linux/bpf_verifier.h struct bpf_verifier_env { · line 600
Quoted 5 lines
include/linux/bpf_verifier.h +3
-1struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +union { +struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct reg_id_scratch precise_ids_scratch;naming nit: "
ids_scratch" or "idset_scratch" to stay in line with "idmap_scratch"?
Makes sense, will change to "idset_scratch".
Quoted 23 lines
Quoted 23 lines
include/linux/bpf_verifier.h +1
-0+ };struct {int *insn_state;int *insn_stack;kernel/bpf/verifier.c +10
-0@@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static inline bool reg_id_scratch_contains (struct reg_id_scratch *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i) +if (s->ids[i] == id) +return true; + +return false; +}
Quoted 8 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3797
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+ +static inline int reg_id_scratch_push (struct reg_id_scratch *s,u32 id) +{ +if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) +return -1 ; + s->ids[s->count++] = id;this will allow duplicated IDs to be added? Was it done in the name of speed?
tbh, it's an artifact from bsearch/sort migration of a series. While doing test veristat runs I found that maximal value of s->count is 5, so looks like it would be fine the way it is now and it would be fine if linear scan is added to avoid duplicate ids. Don't think I have a preference.
Quoted 6 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3799
Quoted 3 lines
kernel/bpf/verifier.c +2
-0+WARN_ONCE (s->count >64 , +"reg_id_scratch.count is unreasonably large (%d)" , s->count);do we need this one? Especially that it's not
_ONCEvariant? Maybe the firstWARN_ON_ONCEis enough?
We make an assumption that linear scans of this array are ok, and it would be scanned often. I'd like to have some indication if this assumption is broken. The s->ids array is large (10 regs + 64 spills) * 8 frames. If you think that this logging is not necessary I'll remove it.
Quoted 7 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3803
Quoted 5 lines
kernel/bpf/verifier.c +4
-0+return 0 ; +} + +static inline void reg_id_scratch_reset (struct reg_id_scratch *s)we probably don't need "inline" for all these helpers?
Ok, will remove "inline".
Quoted 33 lines
Quoted 33 lines
kernel/bpf/verifier.c +32
-0+{ + s->count =0 ; +} + +/* Collect a set of IDs for all registers currently marked as precise in env->bt. +* Mark all registers with these IDs as precise. +*/ +static void mark_precise_scalar_ids (struct bpf_verifier_env *env,struct bpf_verifier_state *st) +{ +struct reg_id_scratch *precise_ids = &env->precise_ids_scratch; +struct backtrack_state *bt = &env->bt; +struct bpf_func_state *func; +struct bpf_reg_state *reg; +DECLARE_BITMAP (mask,64 ); +int i, fr; + +reg_id_scratch_reset (precise_ids); + +for (fr = bt->frame; fr >=0 ; fr--) { + func = st->frame[fr]; + +bitmap_from_u64 (mask,bt_frame_reg_mask (bt, fr)); +for_each_set_bit (i, mask,32 ) { + reg = &func->regs[i]; +if (!reg->id || reg->type !=SCALAR_VALUE ) +continue ; +if (reg_id_scratch_push (precise_ids, reg->id)) +return ; + } + +bitmap_from_u64 (mask,bt_frame_stack_mask (bt, fr)); +for_each_set_bit (i, mask,64 ) {
Quoted 8 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3841
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+if (i >= func->allocated_stack /BPF_REG_SIZE ) +break ; +if (!is_spilled_scalar_reg (&func->stack[i])) +continue ; + reg = &func->stack[i].spilled_ptr; +if (!reg->id || reg->type !=SCALAR_VALUE )
is_spilled_scalar_reg()already ensuresreg->typeisSCALAR_VALUE
Yes, my bad.
Quoted 7 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3831
Quoted 4 lines
kernel/bpf/verifier.c +3
-0+continue ; +if (reg_id_scratch_push (precise_ids, reg->id)) +return ;if push fails (due to overflow of id set), shouldn't we propagate error back and fallback to
mark_all_precise?
In theory this push should never fail, as we pre-allocate enough slots in the scratch. I'll propagate error to __mark_chain_precision() and exit from that one with -EFAULT.
Quoted 93 lines
Quoted 93 lines
kernel/bpf/verifier.c +51
-0+ } + } + +for (fr =0 ; fr <= st->curframe; ++fr) { + func = st->frame[fr]; + +for (i =BPF_REG_0 ; i <BPF_REG_10 ; ++i) { + reg = &func->regs[i]; +if (!reg->id) +continue ; +if (!reg_id_scratch_contains (precise_ids, reg->id)) +continue ; +bt_set_frame_reg (bt, fr, i); + } +for (i =0 ; i < func->allocated_stack /BPF_REG_SIZE ; ++i) { +if (!is_spilled_scalar_reg (&func->stack[i])) +continue ; + reg = &func->stack[i].spilled_ptr; +if (!reg->id) +continue ; +if (!reg_id_scratch_contains (precise_ids, reg->id)) +continue ; +bt_set_frame_slot (bt, fr, i); + } + } +} +/* * __mark_chain_precision() backtracks BPF program instruction sequence and * chain of verifier states making sure that register *regno* (if regno >= 0) @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) bt->frame, last_idx, first_idx, subseq_idx); } +/* If some register with scalar ID is marked as precise, +* make sure that all registers sharing this ID are also precise. +* This is needed to estimate effect of find_equal_scalars(). +* Do this at the last instruction of each state, +* bpf_reg_state::id fields are valid for these instructions. +* +* Allows to track precision in situation like below: +* +* r2 = unknown value +* ... +* --- state #0 --- +* ... +* r1 = r2 // r1 and r2 now share the same ID +* ... +* --- state #1 {r1.id = A, r2.id = A} --- +* ... +* if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 +* ... +* --- state #2 {r1.id = A, r2.id = A} --- +* r3 = r10 +* r3 += r1 // need to mark both r1 and r2 +*/ +mark_precise_scalar_ids (env, st); +if (last_idx <0 ) {/* we are at the entry into subprog, which * is expected for global funcs, but only if tools/testing/selftests/bpf/verifier/precise.c +4
-5@@ -46,7 +46,7 @@ mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 19 first_idx 10\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: regs=r0,r9 stack= before 15\@@ -106,10 +106,10 @@ mark_precise: frame0: regs=r2 stack= before 22\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ - mark_precise: frame0: regs=r2 stack= before 20\ - mark_precise: frame0: parent state regs=r2 stack=:\ + mark_precise: frame0: regs=r2,r9 stack= before 20\ + mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 17\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: parent state regs= stack=:", --2.40.1
Re: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 96 lines · Eduard Zingerman
Quoted 51 lines · Andrii Nakryiko
Quoted 50 lines · Eduard Zingerman
Change
mark_chain_precision()to track precision in situations like below:r2 = unknown value
...
--- state #0 ---... r1 = r2 // r1 and r2 now share the same ID ... --- state #1 {r1.id = A, r2.id = A} --- ... if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 ... --- state #2 {r1.id = A, r2.id = A} --- r3 = r10 r3 += r1 // need to mark both r1 and r2At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise.
This property would be used by a follow-up change in
regsafe().Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)include/linux/bpf_verifier.h +5
-0@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct reg_id_scratch { +u32 count; +u32 ids[BPF_ID_MAP_SIZE ]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */ @@ -590,7 +595,10 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;Quoted 8 lines
include/linux/bpf_verifier.h struct bpf_verifier_env { · line 600
Quoted 5 lines
include/linux/bpf_verifier.h +3
-1struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +union { +struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct reg_id_scratch precise_ids_scratch;naming nit: "
ids_scratch" or "idset_scratch" to stay in line with "idmap_scratch"?Makes sense, will change to "
idset_scratch".Quoted 23 lines
Quoted 23 lines
include/linux/bpf_verifier.h +1
-0+ };struct {int *insn_state;int *insn_stack;kernel/bpf/verifier.c +10
-0@@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static inline bool reg_id_scratch_contains (struct reg_id_scratch *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i) +if (s->ids[i] == id) +return true; + +return false; +}Quoted 8 lines
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3797
Quoted 6 lines
kernel/bpf/verifier.c +6
-0+ +static inline int reg_id_scratch_push (struct reg_id_scratch *s,u32 id) +{ +if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) +return -1 ; + s->ids[s->count++] = id;this will allow duplicated IDs to be added? Was it done in the name of speed?
Quoted 4 lines
tbh, it's an artifact from bsearch/sort migration of a series. While doing test veristat runs I found that maximal value of
s->countis 5, so looks like it would be fine the way it is now and it would be fine if linear scan is added to avoid duplicate ids. Don't think I have a preference.
Maybe return -EFAULT for count > 64 and print a verifier error message ? If/when syzbot/human manages to craft such a program we'll know that this is something to address.
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 97 lines · Alexei Starovoitov
Quoted 96 lines · Eduard Zingerman
Quoted 51 lines · Andrii Nakryiko
Quoted 50 lines · Eduard Zingerman
Change
mark_chain_precision()to track precision in situations like below:r2 = unknown value
...
--- state #0 ---... r1 = r2 // r1 and r2 now share the same ID ... --- state #1 {r1.id = A, r2.id = A} --- ... if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 ... --- state #2 {r1.id = A, r2.id = A} --- r3 = r10 r3 += r1 // need to mark both r1 and r2At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise.
This property would be used by a follow-up change in
regsafe().Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)include/linux/bpf_verifier.h +5
-0@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct reg_id_scratch { +u32 count; +u32 ids[BPF_ID_MAP_SIZE ]; +}; +/* single container for all structs * one verifier_env per bpf_check() call */ @@ -590,7 +595,10 @@ struct bpf_verifier_env {const struct bpf_line_info *prev_linfo;struct bpf_verifier_log log;Quoted 8 lines
include/linux/bpf_verifier.h struct bpf_verifier_env { · line 600
Quoted 5 lines
include/linux/bpf_verifier.h +3
-1struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ]; -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +union { +struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct reg_id_scratch precise_ids_scratch;naming nit: "
ids_scratch" or "idset_scratch" to stay in line with "idmap_scratch"?Makes sense, will change to "
idset_scratch".Quoted 31 lines
Quoted 19 lines
include/linux/bpf_verifier.h +1
-0+ };struct {int *insn_state;int *insn_stack;kernel/bpf/verifier.c +6
-0@@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static inline bool reg_id_scratch_contains (struct reg_id_scratch *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i) +if (s->ids[i] == id)kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3797
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+return true; + +return false; +} + +static inline int reg_id_scratch_push (struct reg_id_scratch *s,u32 id) +{ +if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) +return -1 ; + s->ids[s->count++] = id;this will allow duplicated IDs to be added? Was it done in the name of speed?
Quoted 8 lines
Quoted 4 lines
tbh, it's an artifact from bsearch/sort migration of a series. While doing test veristat runs I found that maximal value of
s->countis 5, so looks like it would be fine the way it is now and it would be fine if linear scan is added to avoid duplicate ids. Don't think I have a preference.Maybe return
-EFAULTfor count > 64 and print a verifier error message ? If/when syzbot/human manages to craft such a program we'll know that this is something to address.
Sounds a bit heavy-handed.
Should the same logic apply to idmap?
I did some silly testing, 1'000'000 searches over u32 array of size (10+64)*8:
- linear search is done in 0.7s
- qsort/bsearch is done in 23s
It looks like my concerns are completely overblown. I'm inclined to remove the size warning and just check for array overflow.
Eduard Zingerman
maintainerPATCH v3 2/4 selftests/bpf: check if mark_chain_precision() follows scalar ids
In reply to Eduard ZingermanCheck __mark_chain_precision() log to verify that scalars with same IDs are marked as precise. Use several scenarios to test that precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.
--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
@@ -50,6 +50,7 @@#include "verifier_regalloc.skel.h" #include "verifier_ringbuf.skel.h" #include "verifier_runtime_jit.skel.h" +#include "verifier_scalar_ids.skel.h" #include "verifier_search_pruning.skel.h" #include "verifier_sock.skel.h" #include "verifier_spill_fill.skel.h"
@@ -150,6 +151,7 @@ void test_verifier_ref_tracking(void) { RUN(verifier_ref_tracking); }void test_verifier_regalloc (void ) {RUN (verifier_regalloc); }void test_verifier_ringbuf (void ) {RUN (verifier_ringbuf); }void test_verifier_runtime_jit (void ) {RUN (verifier_runtime_jit); } +void test_verifier_scalar_ids (void ) {RUN (verifier_scalar_ids); }void test_verifier_search_pruning (void ) {RUN (verifier_search_pruning); }void test_verifier_sock (void ) {RUN (verifier_sock); }void test_verifier_spill_fill (void ) {RUN (verifier_spill_fill); }
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +324 -0
324 lines not on this page · raw message
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
Quoted 10 lines · Eduard Zingerman
Check
__mark_chain_precision()log to verify that scalars with same IDs are marked as precise. Use several scenarios to test that precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.
Quoted 7 lines
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Great set of tests! I asked for yet another one, but this could be easily a follow up. Looks great.
[...]
Quoted 24 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +24
-0+ +/* Same as precision_same_state_broken_link, but with state / +* parent state boundary. +*/ +SEC("socket") +__success __log_level(2) +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10") +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0") +__msg("frame0: parent state regs=r0,r2 stack=:") +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0") +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255") +__msg("frame0: parent state regs=r0 stack=:") +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_cross_state_broken_link(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ + "r1 = r0;"
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 147
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+"r2 = r0;" +/* force checkpoint, although link between r1 and r{0,2} is +* broken by the next statement current precision tracking +* algorithm can't react to it and propagates mark for r1 to +* the parent state. +*/ +"goto +0;" +/* break link for r1, this is the only line that differs +* compared to the previous test +*/
not really the only line, goto +0 is that different line ;)
Quoted 20 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +20
-0+"r1 = 0;" +/* force r0 to be precise, this immediately marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r3 = r10;" +"r3 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that precision marks propagate through scalar IDs. +* Use the same scalar ID in multiple stack frames, check that +* precision information is propagated up the call stack. +*/ +SEC("socket") +__success __log_level(2) +/* bar frame */
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 177
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10") +__msg ("frame2: regs=r1 stack= before 8: (85) call pc+1" ) +/* foo frame */ +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1") +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1") +__msg ("frame1: regs=r1 stack= before 4: (85) call pc+1" ) +/* main frame */ +__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg ("frame0: regs=r0 stack= before 1: (57) r0 &= 255" )
nice test! in this case we discover r6 and r7 during instruction backtracking. Let's add another variant of this multi-frame test with a forced checkpoint to make sure that all this works correctly between child/parent states with multiple active frames?
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +8
-0+__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_many_frames(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" + /* tie r0.id == r1.id == r6.id */
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 195
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+ "r1 = r0;" + "r6 = r0;" + "call precision_many_frames__foo;" + "exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +static __naked __noinline __attribute__((used))
nit: bpf_misc.h has __used macro defined, we can use that everywhere
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +13
-0+void precision_many_frames__foo (void ) +{ + asmvolatile ( +/* conflate one of the register numbers (r6) with outer frame, +* to verify that those are tracked independently +*/ +"r6 = r1;" +"r7 = r1;" +"call precision_many_frames__bar;" +"exit" + ::: __clobber_all); +} +
[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
Quoted 19 lines · Andrii Nakryiko
Quoted 10 lines · Eduard Zingerman
Check
__mark_chain_precision()log to verify that scalars with same IDs are marked as precise. Use several scenarios to test that precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.Quoted 7 lines
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Quoted 2 lines
Great set of tests! I asked for yet another one, but this could be easily a follow up. Looks great.
Thanks.
Quoted 33 lines
Acked-by Andrii Nakryiko <[email protected]>[...]
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +28
-0+ +/* Same as precision_same_state_broken_link, but with state / +* parent state boundary. +*/ +SEC("socket") +__success __log_level(2) +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10") +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0") +__msg("frame0: parent state regs=r0,r2 stack=:") +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0") +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255") +__msg("frame0: parent state regs=r0 stack=:") +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_cross_state_broken_link(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ +"r1 = r0;" +"r2 = r0;" +/* force checkpoint, although link between r1 and r{0,2} is +* broken by the next statement current precision tracking +* algorithm can't react to it and propagates mark for r1 to
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +6
-0+* the parent state. +*/ +"goto +0;" +/* break link for r1, this is the only line that differs +* compared to the previous test +*/ not really the only line, goto +0 is that different line ;)
My bad, the comment should be "... this is the only line that differs compared to precision_cross_state_broken()".
Quoted 28 lines
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +27
-0+"r1 = 0;" +/* force r0 to be precise, this immediately marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r3 = r10;" +"r3 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that precision marks propagate through scalar IDs. +* Use the same scalar ID in multiple stack frames, check that +* precision information is propagated up the call stack. +*/ +SEC("socket") +__success __log_level(2) +/* bar frame */ +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10") +__msg ("frame2: regs=r1 stack= before 8: (85) call pc+1" ) +/* foo frame */ +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1") +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1") +__msg ("frame1: regs=r1 stack= before 4: (85) call pc+1" ) +/* main frame */
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 177
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +3
-0+__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg ("frame0: regs=r0 stack= before 1: (57) r0 &= 255" )nice test! in this case we discover r6 and r7 during instruction backtracking. Let's add another variant of this multi-frame test with a forced checkpoint to make sure that all this works correctly between child/parent states with multiple active frames?
Because of BPF_F_TEST_STATE_FREQ new state is created at each prune point. Prune points are marked for each conditional target and sub-program entry. I skipped a lot of log lines for brevity, here is a bigger portion of the log:
8: (85) call pc+1
caller:
frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0
callee:
frame2: R1=scalar(id=1,...) R10=fp0 10: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
11: (0f) r2 += r1
frame2: last_idx 11 first_idx 10 subseq_idx -1 <- current state
frame2: regs=r1 stack= before 10: (bf) r2 = r10
frame2: parent state regs=r1 stack=
frame1: parent state regs=r6,r7 stack= <- (I)
frame0: parent state regs=r6 stack=
frame2: last_idx 8 first_idx 8 subseq_idx 10 <- parent state
frame2: regs=r1 stack= before 8: (85) call pc+1
frame1: parent state regs=r1,r6,r7 stack= <- (II)
frame0: parent state regs=r6 stack=
frame1: last_idx 7 first_idx 6 subseq_idx 8 <- parent state
frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
frame1: parent state regs=r1 stack=
frame0: parent state regs=r6 stack=
frame1: last_idx 4 first_idx 4 subseq_idx 6 <- parent state
frame1: regs=r1 stack= before 4: (85) call pc+1
frame0: parent state regs=r1,r6 stack=
frame0: last_idx 3 first_idx 1 subseq_idx 4 <- parent state
frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
frame0: regs=r0 stack= before 1: (57) r0 &= 255
At (I) frame1.r{6,7} are marked because mark_precise_scalar_ids() looks for all registers with frame2.r1.id in the current state. At (II) frame1.r1 is marked because of backtracking of call instruction. It looks like both baсktracking and cross-state propagation are tested. Maybe I miss-understand your comment.
Quoted 37 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +8
-0+__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_many_frames(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" + /* tie r0.id == r1.id == r6.id */tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 195
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+ "r1 = r0;" + "r6 = r0;" + "call precision_many_frames__foo;" + "exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +static __naked __noinline __attribute__((used))nit:
bpf_misc.hhas__usedmacro defined, we can use that everywhereQuoted 13 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +13
-0+void precision_many_frames__foo (void ) +{ + asmvolatile ( +/* conflate one of the register numbers (r6) with outer frame, +* to verify that those are tracked independently +*/ +"r6 = r1;" +"r7 = r1;" +"call precision_many_frames__bar;" +"exit" + ::: __clobber_all); +} +[...]
Re: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
Quoted 146 lines · Eduard Zingerman
Quoted 19 lines · Andrii Nakryiko
Quoted 10 lines · Eduard Zingerman
Check
__mark_chain_precision()log to verify that scalars with same IDs are marked as precise. Use several scenarios to test that precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.Quoted 7 lines
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.cQuoted 2 lines
Great set of tests! I asked for yet another one, but this could be easily a follow up. Looks great.
Thanks.
Quoted 33 lines
Acked-by Andrii Nakryiko <[email protected]>[...]
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +28
-0+ +/* Same as precision_same_state_broken_link, but with state / +* parent state boundary. +*/ +SEC("socket") +__success __log_level(2) +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10") +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0") +__msg("frame0: parent state regs=r0,r2 stack=:") +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0") +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255") +__msg("frame0: parent state regs=r0 stack=:") +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_cross_state_broken_link(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ +"r1 = r0;" +"r2 = r0;" +/* force checkpoint, although link between r1 and r{0,2} is +* broken by the next statement current precision tracking +* algorithm can't react to it and propagates mark for r1 to Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +6
-0+* the parent state. +*/ +"goto +0;" +/* break link for r1, this is the only line that differs +* compared to the previous test +*/ not really the only line, goto +0 is that different line ;)
My bad, the comment should be "... this is the only line that differs compared to
precision_cross_state_broken()".Quoted 28 lines
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +27
-0+"r1 = 0;" +/* force r0 to be precise, this immediately marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r3 = r10;" +"r3 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that precision marks propagate through scalar IDs. +* Use the same scalar ID in multiple stack frames, check that +* precision information is propagated up the call stack. +*/ +SEC("socket") +__success __log_level(2) +/* bar frame */ +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10") +__msg ("frame2: regs=r1 stack= before 8: (85) call pc+1" ) +/* foo frame */ +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1") +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1") +__msg ("frame1: regs=r1 stack= before 4: (85) call pc+1" ) +/* main frame */ Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 177
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +3
-0+__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg ("frame0: regs=r0 stack= before 1: (57) r0 &= 255" )nice test! in this case we discover r6 and r7 during instruction backtracking. Let's add another variant of this multi-frame test with a forced checkpoint to make sure that all this works correctly between child/parent states with multiple active frames?
Because of
BPF_F_TEST_STATE_FREQnew state is created at each prune point. Prune points are marked for each conditional target and sub-program entry. I skipped a lot of log lines for brevity, here is a bigger portion of the log:8: (85) call pc+1
caller:frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0 callee: frame2: R1=scalar(id=1,...) R10=fp010: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
11: (0f) r2 += r1
frame2:last_idx11first_idx10subseq_idx-1 <- current state
frame2: regs=r1 stack= before 10: (bf) r2 = r10
frame2: parent state regs=r1 stack=
frame1: parent state regs=r6,r7 stack= <- (I)
frame0: parent state regs=r6 stack=frame2:
last_idx8first_idx8subseq_idx10 <- parent state
frame2: regs=r1 stack= before 8: (85) call pc+1
frame1: parent state regs=r1,r6,r7 stack= <- (II)
frame0: parent state regs=r6 stack=frame1:
last_idx7first_idx6subseq_idx8 <- parent state
frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
frame1: parent state regs=r1 stack=
frame0: parent state regs=r6 stack=frame1:
last_idx4first_idx4subseq_idx6 <- parent state
frame1: regs=r1 stack= before 4: (85) call pc+1
frame0: parent state regs=r1,r6 stack=frame0:
last_idx3first_idx1subseq_idx4 <- parent state
frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
frame0: regs=r0 stack= before 1: (57) r0 &= 255
Quoted 6 lines
At (I) frame1.r{6,7} are marked because
mark_precise_scalar_ids()looks for all registers with frame2.r1.id in the current state. At (II) frame1.r1 is marked because of backtracking of call instruction. It looks like both baсktracking and cross-state propagation are tested. Maybe I miss-understand your comment.
From the set of __msg() tests it's not obvious that (I) is happening. So just maybe let's messages like below:
__msg("frame1: parent state regs=r6,r7 stack=")
to make it more explicit?
Either way, it's minor. You are right about checkpoint after each helper call and subprog call.
Quoted 38 lines
Quoted 37 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +8
-0+__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_many_frames(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" + /* tie r0.id == r1.id == r6.id */tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 195
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+ "r1 = r0;" + "r6 = r0;" + "call precision_many_frames__foo;" + "exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +static __naked __noinline __attribute__((used))nit:
bpf_misc.hhas__usedmacro defined, we can use that everywhereQuoted 13 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +13
-0+void precision_many_frames__foo (void ) +{ + asmvolatile ( +/* conflate one of the register numbers (r6) with outer frame, +* to verify that those are tracked independently +*/ +"r6 = r1;" +"r7 = r1;" +"call precision_many_frames__bar;" +"exit" + ::: __clobber_all); +} +[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 2/4] selftests/bpf: check if mark_chain_precision() follows scalar ids
Quoted 154 lines · Andrii Nakryiko
Quoted 146 lines · Eduard Zingerman
Quoted 19 lines · Andrii Nakryiko
Quoted 10 lines · Eduard Zingerman
Check
__mark_chain_precision()log to verify that scalars with same IDs are marked as precise. Use several scenarios to test that precision marks are propagated through:
- registers of scalar type with the same ID within one state;
- registers of scalar type with the same ID cross several states;
- registers of scalar type with the same ID cross several stack frames;
- stack slot of scalar type with the same ID;
- multiple scalar IDs are tracked independently.Quoted 7 lines
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 324 ++++++++++++++++++ 2 files changed, 326 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.cQuoted 2 lines
Great set of tests! I asked for yet another one, but this could be easily a follow up. Looks great.
Thanks.
Quoted 33 lines
Acked-by Andrii Nakryiko <[email protected]>[...]
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +28
-0+ +/* Same as precision_same_state_broken_link, but with state / +* parent state boundary. +*/ +SEC("socket") +__success __log_level(2) +__msg("frame0: regs=r0,r2 stack= before 6: (bf) r3 = r10") +__msg("frame0: regs=r0,r2 stack= before 5: (b7) r1 = 0") +__msg("frame0: parent state regs=r0,r2 stack=:") +__msg("frame0: regs=r0,r1,r2 stack= before 4: (05) goto pc+0") +__msg("frame0: regs=r0,r1,r2 stack= before 3: (bf) r2 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg("frame0: regs=r0 stack= before 1: (57) r0 &= 255") +__msg("frame0: parent state regs=r0 stack=:") +__msg("frame0: regs=r0 stack= before 0: (85) call bpf_ktime_get_ns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_cross_state_broken_link(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* tie r0.id == r1.id == r2.id */ +"r1 = r0;" +"r2 = r0;" +/* force checkpoint, although link between r1 and r{0,2} is +* broken by the next statement current precision tracking +* algorithm can't react to it and propagates mark for r1 to Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +6
-0+* the parent state. +*/ +"goto +0;" +/* break link for r1, this is the only line that differs +* compared to the previous test +*/ not really the only line, goto +0 is that different line ;)
My bad, the comment should be "... this is the only line that differs compared to
precision_cross_state_broken()".Quoted 28 lines
Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +27
-0+"r1 = 0;" +/* force r0 to be precise, this immediately marks r1 and r2 as +* precise as well because of shared IDs +*/ +"r3 = r10;" +"r3 += r0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that precision marks propagate through scalar IDs. +* Use the same scalar ID in multiple stack frames, check that +* precision information is propagated up the call stack. +*/ +SEC("socket") +__success __log_level(2) +/* bar frame */ +__msg("frame2: regs=r1 stack= before 10: (bf) r2 = r10") +__msg ("frame2: regs=r1 stack= before 8: (85) call pc+1" ) +/* foo frame */ +__msg("frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1") +__msg("frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1") +__msg ("frame1: regs=r1 stack= before 4: (85) call pc+1" ) +/* main frame */ Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 177
Quoted 3 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +3
-0+__msg("frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0") +__msg("frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0") +__msg ("frame0: regs=r0 stack= before 1: (57) r0 &= 255" )nice test! in this case we discover r6 and r7 during instruction backtracking. Let's add another variant of this multi-frame test with a forced checkpoint to make sure that all this works correctly between child/parent states with multiple active frames?
Because of
BPF_F_TEST_STATE_FREQnew state is created at each prune point. Prune points are marked for each conditional target and sub-program entry. I skipped a lot of log lines for brevity, here is a bigger portion of the log:8: (85) call pc+1
caller:frame1: R6=scalar(id=1,...) R7=scalar(id=1,...) R10=fp0 callee: frame2: R1=scalar(id=1,...) R10=fp010: (bf) r2 = r10 ; frame2: R2_w=fp0 R10=fp0
11: (0f) r2 += r1
frame2:last_idx11first_idx10subseq_idx-1 <- current state
frame2: regs=r1 stack= before 10: (bf) r2 = r10
frame2: parent state regs=r1 stack=
frame1: parent state regs=r6,r7 stack= <- (I)
frame0: parent state regs=r6 stack=frame2:
last_idx8first_idx8subseq_idx10 <- parent state
frame2: regs=r1 stack= before 8: (85) call pc+1
frame1: parent state regs=r1,r6,r7 stack= <- (II)
frame0: parent state regs=r6 stack=frame1:
last_idx7first_idx6subseq_idx8 <- parent state
frame1: regs=r1,r6,r7 stack= before 7: (bf) r7 = r1
frame1: regs=r1,r6 stack= before 6: (bf) r6 = r1
frame1: parent state regs=r1 stack=
frame0: parent state regs=r6 stack=frame1:
last_idx4first_idx4subseq_idx6 <- parent state
frame1: regs=r1 stack= before 4: (85) call pc+1
frame0: parent state regs=r1,r6 stack=frame0:
last_idx3first_idx1subseq_idx4 <- parent state
frame0: regs=r0,r1,r6 stack= before 3: (bf) r6 = r0
frame0: regs=r0,r1 stack= before 2: (bf) r1 = r0
frame0: regs=r0 stack= before 1: (57) r0 &= 255Quoted 6 lines
At (I) frame1.r{6,7} are marked because
mark_precise_scalar_ids()looks for all registers with frame2.r1.id in the current state. At (II) frame1.r1 is marked because of backtracking of call instruction. It looks like both baсktracking and cross-state propagation are tested. Maybe I miss-understand your comment.
Quoted 6 lines
From the set of
__msg()tests it's not obvious that (I) is happening. So just maybe let's messages like below:
__msg("frame1: parent state regs=r6,r7 stack=")to make it more explicit?
Yes good point,
I'll add a few __msg lines and a comment to make this thing clear.
Quoted 43 lines
Either way, it's minor. You are right about checkpoint after each helper call and subprog call.
Quoted 38 lines
Quoted 37 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +8
-0+__flag (BPF_F_TEST_STATE_FREQ) +__naked void precision_many_frames(void) +{ + asmvolatile ( +/* r0 = random number up to 0xff */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" + /* tie r0.id == r1.id == r6.id */tools/testing/selftests/bpf/progs/verifier_scalar_ids.c line 195
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +10
-0+ "r1 = r0;" + "r6 = r0;" + "call precision_many_frames__foo;" + "exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +static __naked __noinline __attribute__((used))nit:
bpf_misc.hhas__usedmacro defined, we can use that everywhereQuoted 13 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c new file +13
-0+void precision_many_frames__foo (void ) +{ + asmvolatile ( +/* conflate one of the register numbers (r6) with outer frame, +* to verify that those are tracked independently +*/ +"r6 = r1;" +"r7 = r1;" +"call precision_many_frames__bar;" +"exit" + ::: __clobber_all); +} +[...]
Eduard Zingerman
maintainerPATCH v3 3/4 bpf: verify scalar ids mapping in regsafe() using check_ids()
In reply to Eduard ZingermanMake sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = Y
This example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.
Currently regsafe() does not call check_ids() for scalar registers, thus from POV of regsafe() states (I) and (II) are identical. If the path 1-6 is taken by verifier first, and checkpoint is created at (6) the path [1-4, 6] would be considered safe.
This commit updates regsafe() to call check_ids() for precise scalar registers.
To minimize the impact on verification performance, avoid generating bpf_reg_state::id for constant scalar values when processing BPF_MOV in check_alu_op(). Scalar IDs are utilized by find_equal_scalars() to propagate information about value ranges for registers that hold the same value. However, there is no need to propagate range information for constants.
Still, there is some performance impact because of this change. Using veristat to compare number of processed states for selftests object files listed in tools/testing/selftests/bpf/veristat.cfg and Cilium object files from [1] gives the following statistics:
$ ./veristat -e file,prog,states -f "states_pct>10" \
-C master-baseline.log current.log
File Program States (DIFF)
----------- ------------------------------ --------------
bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%)
bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%)
bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%)
loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)Also test case verifier_search_pruning/allocated_stack has to be updated to avoid conflicts in register ID assignments between cached and new states.
[1] [email protected]:anakryiko/cilium.git
--- kernel/bpf/verifier.c | 34 ++++++++++++++++--- .../bpf/progs/verifier_search_pruning.c | 3 +- 2 files changed, 32 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +30 -4
@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)if (BPF_SRC (insn->code) ==BPF_X ) {struct bpf_reg_state *src_reg = regs + insn->src_reg;struct bpf_reg_state *dst_reg = regs + insn->dst_reg; +bool need_id = (src_reg->type ==SCALAR_VALUE && !src_reg->id && + !tnum_is_const (src_reg->var_off));if (BPF_CLASS (insn->code) ==BPF_ALU64 ) {/* case: R1 = R2 * copy register state to dest reg */ -if (src_reg->type ==SCALAR_VALUE && !src_reg->id) +if (need_id)/* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range.
@@ -12957,7 +12959,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) }else if (src_reg->type ==SCALAR_VALUE ) {bool is_src_reg_u32 = src_reg->umax_value <=U32_MAX ; -if (is_src_reg_u32 && !src_reg->id) +if (is_src_reg_u32 && need_id) src_reg->id = ++env->id_gen;copy_register_state (dst_reg, src_reg);/* Make sure ID is cleared if src_reg is not in u32 range otherwise
@@ -15289,9 +15291,33 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return false;if (!rold->precise)return true; -/* new val must satisfy old val knowledge */ +/* Why check_ids() for scalar registers? +* +* Consider the following BPF code: +* 1: r6 = ... unbound scalar, ID=a ... +* 2: r7 = ... unbound scalar, ID=b ... +* 3: if (r6 > r7) goto +1 +* 4: r6 = r7 +* 5: if (r6 > X) goto ... +* 6: ... memory operation using r7 ... +* +* First verification path is [1-6]: +* - at (4) same bpf_reg_state::id (b) would be assigned to r6 and r7; +* - at (5) r6 would be marked <= X, find_equal_scalars() would also mark +* r7 <= X, because r6 and r7 share same id. +* Next verification path is [1-4, 6]. +* +* Instruction (6) would be reached in two states: +* I. r6{.id=b}, r7{.id=b} via path 1-6; +* II. r6{.id=a}, r7{.id=b} via path 1-4, 6. +* +* Use check_ids() to distinguish these states. +* --- +* Also verify that new value satisfies old value range knowledge. +*/ return range_within (rold, rcur) && -tnum_in (rold->var_off, rcur->var_off); +tnum_in (rold->var_off, rcur->var_off) && +check_ids (rold->id, rcur->id, idmap);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM :
tools/testing/selftests/bpf/progs/verifier_search_pruning.c +2 -1
@@ -271,7 +271,7 @@ l2_%=: r0 = 0; \ SEC("socket") __description("allocated_stack") -__success __msg("processed 15 insns") +__success __msg("processed 16 insns") __success_unpriv __msg_unpriv("") __log_level(1) __retval(0)__naked void allocated_stack (void ) {
@@ -279,6 +279,7 @@ __naked void allocated_stack(void) r6 = r1; \ call %[bpf_get_prandom_u32]; \ r7 = r0; \ + call %[bpf_get_prandom_u32]; \ if r0 == 0 goto l0_%=; \ r0 =0 ; \ *(u64 *)(r10 -8 ) = r6; \
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 51 lines · Eduard Zingerman
Make sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = YThis example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.Currently
regsafe()does not callcheck_ids()for scalar registers, thus from POV ofregsafe()states (I) and (II) are identical. If the path 1-6 is taken by verifier first, and checkpoint is created at (6) the path [1-4, 6] would be considered safe.This commit updates
regsafe()to callcheck_ids()for precise scalar registers.To minimize the impact on verification performance, avoid generating
bpf_reg_state::idfor constant scalar values when processingBPF_MOVincheck_alu_op(). Scalar IDs are utilized byfind_equal_scalars()to propagate information about value ranges for registers that hold the same value. However, there is no need to propagate range information for constants.Still, there is some performance impact because of this change. Using veristat to compare number of processed states for selftests object files listed in
tools/testing/selftests/bpf/veristat.cfgand Cilium object files from [1] gives the following statistics:$ ./veristat -e file,prog,states -f "states_pct>10" \ -C master-baseline.log current.log File Program States (DIFF) ----------- ------------------------------ -------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%) bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%) loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)Also test case verifier_search_pruning/allocated_stack has to be updated to avoid conflicts in register ID assignments between cached and new states.
Quoted 5 lines
[1] [email protected]:anakryiko/cilium.git
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>---
So I checked it also on our internal BPF object files, and it looks mostly good. Here are the only regressions:
Program States (A) States (B)
States (DIFF)
---------------------------------------- ---------- ----------
---------------balancer_ingress 29219 34531
+5312 (+18.18%)syar_bind6_protect6 3257 3599
+342 (+10.50%)syar_bind4_protect4 2590 2931
+341 (+13.17%)on_alloc 415 526
+111 (+26.75%)on_free 406 517
+111 (+27.34%)
pycallcount 395 506
+111 (+28.10%)resume_context 405 516
+111 (+27.41%)on_py_event 395 506
+111 (+28.10%)on_event 284 394
+110 (+38.73%)handle_cuda_event 268 378
+110 (+41.04%)handle_cuda_launch 276 386
+110 (+39.86%)handle_cuda_malloc_ret 272 382
+110 (+40.44%)handle_cuda_memcpy 270 380
+110 (+40.74%)handle_cuda_memcpy_async 270 380
+110 (+40.74%)handle_pytorch_allocate_ret 271 381
+110 (+40.59%)handle_pytorch_malloc_ret 272 382
+110 (+40.44%)on_event 284 394
+110 (+38.73%)on_event 284 394
+110 (+38.73%)syar_task_enter_execve 309 329
+20 (+6.47%)kprobe__security_inode_link 968 986
+18 (+1.86%)kprobe__security_inode_symlink 838 854
+16 (+1.91%)tw_twfw_egress 249 251
+2 (+0.80%)tw_twfw_ingress 250 252
+2 (+0.80%)tw_twfw_tc_eg 248 250
+2 (+0.81%)tw_twfw_tc_in 250 252
+2 (+0.80%)raw_tracepoint__sched_process_exec 136 139
+3 (+2.21%)kprobe_ret__do_filp_open 869 871
+2 (+0.23%)read_erlang_stack 572 573
+1 (+0.17%)
They are mostly on small-ish programs. The only mild concern from my side is balancer_ingress, which is one of Katran BPF programs. It add +18% of states (which translates to about 70K more instructions verified, up from 350K). I think we can live with this, but would be nice to check why it's happening.
I suspect that dropping SCALAR IDs as we discussed (after fixing register fill/spill ID generation) might completely mitigate that.
Overall, LGTM:
Quoted 9 lines
kernel/bpf/verifier.c | 34 ++++++++++++++++--- .../bpf/progs/verifier_search_pruning.c | 3 +- 2 files changed, 32 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12938
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)if (BPF_SRC (insn->code) ==BPF_X ) {struct bpf_reg_state *src_reg = regs + insn->src_reg;struct bpf_reg_state *dst_reg = regs + insn->dst_reg; +bool need_id = (src_reg->type ==SCALAR_VALUE && !src_reg->id && + !tnum_is_const (src_reg->var_off));
nit: unnecessary outer ()
Quoted 9 lines
kernel/bpf/verifier.c +1
-1if (BPF_CLASS (insn->code) ==BPF_ALU64 ) {/* case: R1 = R2 * copy register state to dest reg */ -if (src_reg->type ==SCALAR_VALUE && !src_reg->id) +if (need_id)/* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range.
[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 123 lines · Andrii Nakryiko
Quoted 51 lines · Eduard Zingerman
Make sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = YThis example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.Currently
regsafe()does not callcheck_ids()for scalar registers, thus from POV ofregsafe()states (I) and (II) are identical. If the path 1-6 is taken by verifier first, and checkpoint is created at (6) the path [1-4, 6] would be considered safe.This commit updates
regsafe()to callcheck_ids()for precise scalar registers.To minimize the impact on verification performance, avoid generating
bpf_reg_state::idfor constant scalar values when processingBPF_MOVincheck_alu_op(). Scalar IDs are utilized byfind_equal_scalars()to propagate information about value ranges for registers that hold the same value. However, there is no need to propagate range information for constants.Still, there is some performance impact because of this change. Using veristat to compare number of processed states for selftests object files listed in
tools/testing/selftests/bpf/veristat.cfgand Cilium object files from [1] gives the following statistics:$ ./veristat -e file,prog,states -f "states_pct>10" \ -C master-baseline.log current.log File Program States (DIFF) ----------- ------------------------------ -------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%) bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%) loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)Also test case verifier_search_pruning/allocated_stack has to be updated to avoid conflicts in register ID assignments between cached and new states.
Quoted 5 lines
[1] [email protected]:anakryiko/cilium.git
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>---
So I checked it also on our internal BPF object files, and it looks mostly good. Here are the only regressions:
Program States (A) States (B)
States (DIFF)
---------------------------------------- ---------- ----------
---------------balancer_ingress29219 34531
+5312 (+18.18%)syar_bind6_protect63257 3599
+342 (+10.50%)syar_bind4_protect42590 2931
+341 (+13.17%)on_alloc415 526
+111 (+26.75%)on_free406 517
+111 (+27.34%)
pycallcount 395 506
+111 (+28.10%)resume_context405 516
+111 (+27.41%)on_py_event395 506
+111 (+28.10%)on_event284 394
+110 (+38.73%)handle_cuda_event268 378
+110 (+41.04%)handle_cuda_launch276 386
+110 (+39.86%)handle_cuda_malloc_ret272 382
+110 (+40.44%)handle_cuda_memcpy270 380
+110 (+40.74%)handle_cuda_memcpy_async270 380
+110 (+40.74%)handle_pytorch_allocate_ret271 381
+110 (+40.59%)handle_pytorch_malloc_ret272 382
+110 (+40.44%)on_event284 394
+110 (+38.73%)on_event284 394
+110 (+38.73%)syar_task_enter_execve309 329
+20 (+6.47%)kprobe__security_inode_link968 986
+18 (+1.86%)kprobe__security_inode_symlink838 854
+16 (+1.91%)tw_twfw_egress249 251
+2 (+0.80%)tw_twfw_ingress250 252
+2 (+0.80%)tw_twfw_tc_eg248 250
+2 (+0.81%)tw_twfw_tc_in250 252
+2 (+0.80%)raw_tracepoint__sched_process_exec136 139
+3 (+2.21%)kprobe_ret__do_filp_open869 871
+2 (+0.23%)read_erlang_stack572 573
+1 (+0.17%)
Quoted 5 lines
They are mostly on small-ish programs. The only mild concern from my side is
balancer_ingress, which is one of Katran BPF programs. It add +18% of states (which translates to about 70K more instructions verified, up from 350K). I think we can live with this, but would be nice to check why it's happening.
Thank you for reviewing this series.
I looked at the logs that you've shared, the difference is indeed caused by some scalar registers having a unique ID in cached state and no ID in current state or vice versa. The !rold->id trick that we discussed for V2 helps :)
What do you think about an alternative way to exclude unique scalars as in the patch below? (on top of this patch-set):
--- 8< -------------------------
kernel/bpf/verifier.c +8 -1
@@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_verifier_env *env) +{ + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; +return check_ids (old_id, cur_id, env->idmap_scratch); +} +static void clean_func_state (struct bpf_verifier_env *env,struct bpf_func_state *st) {
@@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_scalar_ids (rold->id, rcur->id, env);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM :
------------------------- >8 ---
For me this patch removes all veristat differences compared to the master. If doing it for real, I'd like to reset env->id_gen at exit from states_equal() to the value it had at entry (to avoid allocating too many ids).
Quoted 37 lines
I suspect that dropping SCALAR IDs as we discussed (after fixing register fill/spill ID generation) might completely mitigate that.
Overall, LGTM:
Acked-by Andrii Nakryiko <[email protected]>Quoted 9 lines
kernel/bpf/verifier.c | 34 ++++++++++++++++--- .../bpf/progs/verifier_search_pruning.c | 3 +- 2 files changed, 32 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +0
-0kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12938
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)if (BPF_SRC (insn->code) ==BPF_X ) {struct bpf_reg_state *src_reg = regs + insn->src_reg;struct bpf_reg_state *dst_reg = regs + insn->dst_reg; +bool need_id = (src_reg->type ==SCALAR_VALUE && !src_reg->id && + !tnum_is_const (src_reg->var_off));nit: unnecessary outer ()
Quoted 9 lines
kernel/bpf/verifier.c +1
-1if (BPF_CLASS (insn->code) ==BPF_ALU64 ) {/* case: R1 = R2 * copy register state to dest reg */ -if (src_reg->type ==SCALAR_VALUE && !src_reg->id) +if (need_id)/* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range. [...]
Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 173 lines · Eduard Zingerman
Quoted 123 lines · Andrii Nakryiko
Quoted 51 lines · Eduard Zingerman
Make sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = YThis example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.Currently
regsafe()does not callcheck_ids()for scalar registers, thus from POV ofregsafe()states (I) and (II) are identical. If the path 1-6 is taken by verifier first, and checkpoint is created at (6) the path [1-4, 6] would be considered safe.This commit updates
regsafe()to callcheck_ids()for precise scalar registers.To minimize the impact on verification performance, avoid generating
bpf_reg_state::idfor constant scalar values when processingBPF_MOVincheck_alu_op(). Scalar IDs are utilized byfind_equal_scalars()to propagate information about value ranges for registers that hold the same value. However, there is no need to propagate range information for constants.Still, there is some performance impact because of this change. Using veristat to compare number of processed states for selftests object files listed in
tools/testing/selftests/bpf/veristat.cfgand Cilium object files from [1] gives the following statistics:$ ./veristat -e file,prog,states -f "states_pct>10" \ -C master-baseline.log current.log File Program States (DIFF) ----------- ------------------------------ -------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%) bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%) loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)Also test case verifier_search_pruning/allocated_stack has to be updated to avoid conflicts in register ID assignments between cached and new states.
Quoted 5 lines
[1] [email protected]:anakryiko/cilium.git
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>---
So I checked it also on our internal BPF object files, and it looks mostly good. Here are the only regressions:
Program States (A) States (B)
States (DIFF)
---------------------------------------- ---------- ----------
---------------balancer_ingress29219 34531
+5312 (+18.18%)syar_bind6_protect63257 3599
+342 (+10.50%)syar_bind4_protect42590 2931
+341 (+13.17%)on_alloc415 526
+111 (+26.75%)on_free406 517
+111 (+27.34%)
pycallcount 395 506
+111 (+28.10%)resume_context405 516
+111 (+27.41%)on_py_event395 506
+111 (+28.10%)on_event284 394
+110 (+38.73%)handle_cuda_event268 378
+110 (+41.04%)handle_cuda_launch276 386
+110 (+39.86%)handle_cuda_malloc_ret272 382
+110 (+40.44%)handle_cuda_memcpy270 380
+110 (+40.74%)handle_cuda_memcpy_async270 380
+110 (+40.74%)handle_pytorch_allocate_ret271 381
+110 (+40.59%)handle_pytorch_malloc_ret272 382
+110 (+40.44%)on_event284 394
+110 (+38.73%)on_event284 394
+110 (+38.73%)syar_task_enter_execve309 329
+20 (+6.47%)kprobe__security_inode_link968 986
+18 (+1.86%)kprobe__security_inode_symlink838 854
+16 (+1.91%)tw_twfw_egress249 251
+2 (+0.80%)tw_twfw_ingress250 252
+2 (+0.80%)tw_twfw_tc_eg248 250
+2 (+0.81%)tw_twfw_tc_in250 252
+2 (+0.80%)raw_tracepoint__sched_process_exec136 139
+3 (+2.21%)kprobe_ret__do_filp_open869 871
+2 (+0.23%)read_erlang_stack572 573
+1 (+0.17%)Quoted 5 lines
They are mostly on small-ish programs. The only mild concern from my side is
balancer_ingress, which is one of Katran BPF programs. It add +18% of states (which translates to about 70K more instructions verified, up from 350K). I think we can live with this, but would be nice to check why it's happening.Thank you for reviewing this series.
I looked at the logs that you've shared, the difference is indeed caused by some scalar registers having a unique ID in cached state and no ID in current state or vice versa. The !rold->id trick that we discussed for V2 helps :)
What do you think about an alternative way to exclude unique scalars as in the patch below? (on top of this patch-set):
--- 8< -------------------------
kernel/bpf/verifier.c +8
-2@@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_verifier_env *env) +{ + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; +return check_ids (old_id, cur_id, env->idmap_scratch); +} +static void clean_func_state (struct bpf_verifier_env *env,struct bpf_func_state *st) {@@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_scalar_ids (rold->id, rcur->id, env);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM : ------------------------- >8 ---
Quoted 4 lines
For me this patch removes all veristat differences compared to the master. If doing it for real, I'd like to reset
env->id_genat exit fromstates_equal()to the value it had at entry (to avoid allocating too many ids).
Hm.. It's clever and pretty minimal, I like it. We are basically allocating virtual ID for SCALAR that doesn't have id, just to make sure we get a conflict if the SCALAR with ID cannot be mapped into two different SCALARs, right?
The only question would be if it's safe to do that for case when old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified) state we have r6.id = r7.id = 123, and in new state we have r6.id = 0 and r7.id = 0, then your implementation above will say that states are equivalent. But are they, given there is a link between r6 and r7 that might be required for correctness. Which we don't have in current state.
So with this we are getting to my original concerns with your !rold->id approach, which tries to ignore the necessity of link between registers.
What if we do this only for old registers? Then, (in old state) r6.id = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be rejected because first we'll map 123 to newly allocated X for r6.id, and then when we try to match r7.id=123 to another allocated ID X+1 we'll get a conflict, right?
Quoted 39 lines
Quoted 38 lines
I suspect that dropping SCALAR IDs as we discussed (after fixing register fill/spill ID generation) might completely mitigate that.
Overall, LGTM:
Acked-by Andrii Nakryiko <[email protected]>Quoted 9 lines
kernel/bpf/verifier.c | 34 ++++++++++++++++--- .../bpf/progs/verifier_search_pruning.c | 3 +- 2 files changed, 32 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +0
-0kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12938
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)if (BPF_SRC (insn->code) ==BPF_X ) {struct bpf_reg_state *src_reg = regs + insn->src_reg;struct bpf_reg_state *dst_reg = regs + insn->dst_reg; +bool need_id = (src_reg->type ==SCALAR_VALUE && !src_reg->id && + !tnum_is_const (src_reg->var_off));nit: unnecessary outer ()
Quoted 9 lines
kernel/bpf/verifier.c +1
-1if (BPF_CLASS (insn->code) ==BPF_ALU64 ) {/* case: R1 = R2 * copy register state to dest reg */ -if (src_reg->type ==SCALAR_VALUE && !src_reg->id) +if (need_id)/* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range. [...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 184 lines · Andrii Nakryiko
Quoted 173 lines · Eduard Zingerman
Quoted 123 lines · Andrii Nakryiko
Quoted 51 lines · Eduard Zingerman
Make sure that the following unsafe example is rejected by verifier:
1: r9 = ... some pointer with range X ...
2: r6 = ... unbound scalar ID=a ...
3: r7 = ... unbound scalar ID=b ...
4: if (r6 > r7) goto +1
5: r6 = r7
6: if (r6 > X) goto ...
--- checkpoint ---
7: r9 += r7
8: *(u64 *)r9 = YThis example is unsafe because not all execution paths verify r7 range. Because of the jump at (4) the verifier would arrive at (6) in two states:
I. r6{.id=b}, r7{.id=b} via path 1-6;
II. r6{.id=a}, r7{.id=b} via path 1-4, 6.Currently
regsafe()does not callcheck_ids()for scalar registers, thus from POV ofregsafe()states (I) and (II) are identical. If the path 1-6 is taken by verifier first, and checkpoint is created at (6) the path [1-4, 6] would be considered safe.This commit updates
regsafe()to callcheck_ids()for precise scalar registers.To minimize the impact on verification performance, avoid generating
bpf_reg_state::idfor constant scalar values when processingBPF_MOVincheck_alu_op(). Scalar IDs are utilized byfind_equal_scalars()to propagate information about value ranges for registers that hold the same value. However, there is no need to propagate range information for constants.Still, there is some performance impact because of this change. Using veristat to compare number of processed states for selftests object files listed in
tools/testing/selftests/bpf/veristat.cfgand Cilium object files from [1] gives the following statistics:$ ./veristat -e file,prog,states -f "states_pct>10" \ -C master-baseline.log current.log File Program States (DIFF) ----------- ------------------------------ -------------- bpf_xdp.o tail_handle_nat_fwd_ipv6 +155 (+23.92%) bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +102 (+27.20%) bpf_xdp.o tail_rev_nodeport_lb4 +83 (+20.85%) loop6.bpf.o trace_virtqueue_add_sgs +25 (+11.06%)Also test case verifier_search_pruning/allocated_stack has to be updated to avoid conflicts in register ID assignments between cached and new states.
Quoted 5 lines
[1] [email protected]:anakryiko/cilium.git
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>---
So I checked it also on our internal BPF object files, and it looks mostly good. Here are the only regressions:
Program States (A) States (B)
States (DIFF)
---------------------------------------- ---------- ----------
---------------balancer_ingress29219 34531
+5312 (+18.18%)syar_bind6_protect63257 3599
+342 (+10.50%)syar_bind4_protect42590 2931
+341 (+13.17%)on_alloc415 526
+111 (+26.75%)on_free406 517
+111 (+27.34%)
pycallcount 395 506
+111 (+28.10%)resume_context405 516
+111 (+27.41%)on_py_event395 506
+111 (+28.10%)on_event284 394
+110 (+38.73%)handle_cuda_event268 378
+110 (+41.04%)handle_cuda_launch276 386
+110 (+39.86%)handle_cuda_malloc_ret272 382
+110 (+40.44%)handle_cuda_memcpy270 380
+110 (+40.74%)handle_cuda_memcpy_async270 380
+110 (+40.74%)handle_pytorch_allocate_ret271 381
+110 (+40.59%)handle_pytorch_malloc_ret272 382
+110 (+40.44%)on_event284 394
+110 (+38.73%)on_event284 394
+110 (+38.73%)syar_task_enter_execve309 329
+20 (+6.47%)kprobe__security_inode_link968 986
+18 (+1.86%)kprobe__security_inode_symlink838 854
+16 (+1.91%)tw_twfw_egress249 251
+2 (+0.80%)tw_twfw_ingress250 252
+2 (+0.80%)tw_twfw_tc_eg248 250
+2 (+0.81%)tw_twfw_tc_in250 252
+2 (+0.80%)raw_tracepoint__sched_process_exec136 139
+3 (+2.21%)kprobe_ret__do_filp_open869 871
+2 (+0.23%)read_erlang_stack572 573
+1 (+0.17%)Quoted 5 lines
They are mostly on small-ish programs. The only mild concern from my side is
balancer_ingress, which is one of Katran BPF programs. It add +18% of states (which translates to about 70K more instructions verified, up from 350K). I think we can live with this, but would be nice to check why it's happening.Thank you for reviewing this series.
I looked at the logs that you've shared, the difference is indeed caused by some scalar registers having a unique ID in cached state and no ID in current state or vice versa. The !rold->id trick that we discussed for V2 helps :)
What do you think about an alternative way to exclude unique scalars as in the patch below? (on top of this patch-set):
--- 8< -------------------------
kernel/bpf/verifier.c +8
-2@@ -15149,6 +15149,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +static bool check_scalar_ids (u32 old_id,u32 cur_id,struct bpf_verifier_env *env) +{ + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; +return check_ids (old_id, cur_id, env->idmap_scratch); +} +static void clean_func_state (struct bpf_verifier_env *env,struct bpf_func_state *st) {@@ -15325,7 +15332,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_scalar_ids (rold->id, rcur->id, env);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM : ------------------------- >8 ---Quoted 4 lines
For me this patch removes all veristat differences compared to the master. If doing it for real, I'd like to reset
env->id_genat exit fromstates_equal()to the value it had at entry (to avoid allocating too many ids).Hm.. It's clever and pretty minimal, I like it. We are basically allocating virtual ID for SCALAR that doesn't have id, just to make sure we get a conflict if the SCALAR with ID cannot be mapped into two different SCALARs, right?
Quoted 7 lines
The only question would be if it's safe to do that for case when
old_reg->id!= 0 andcur_reg->id== 0? E.g., if in old (verified) state we have r6.id = r7.id = 123, and in new state we have r6.id = 0 and r7.id = 0, then your implementation above will say that states are equivalent. But are they, given there is a link between r6 and r7 that might be required for correctness. Which we don't have in current state.
You mean the other way around, rold.id == 0, rcur.id != 0, right? (below 0/2 means: original value 0, replaced by new id 2).
(1) old cur
r6.id 0/2 1
r7.id 0/3 1 check_ids returns true
(2) old cur
r6.id 1 0/2
r7.id 1 0/3 check_ids returns false
Also, (1) is no different from (3):
(3) old cur
r6.id 1 3
r7.id 2 3 check_ids returns true
Current check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_ids(rold->id, rcur->id, idmap);
Will reject (1) and (2), but will accept (3).
New check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_scalar_ids(rold->id, rcur->id, idmap);
Will reject (2), but will accept (1) and (3).
And modification of check_scalar_ids() to generate IDs only for rold or only for rcur would not reject (3) either.
(3) would be rejected only if current check is used together with elimination of unique scalar IDs from old states.
My previous experiments show that eliminating unique IDs from old states and not eliminating unique IDs from cur states is *very* bad for performance.
Quoted 50 lines
So with this we are getting to my original concerns with your !rold->id approach, which tries to ignore the necessity of link between registers.
What if we do this only for old registers? Then, (in old state) r6.id = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be rejected because first we'll map 123 to newly allocated X for r6.id, and then when we try to match r7.id=123 to another allocated ID X+1 we'll get a conflict, right?
Quoted 39 lines
Quoted 38 lines
I suspect that dropping SCALAR IDs as we discussed (after fixing register fill/spill ID generation) might completely mitigate that.
Overall, LGTM:
Acked-by Andrii Nakryiko <[email protected]>Quoted 9 lines
kernel/bpf/verifier.c | 34 ++++++++++++++++--- .../bpf/progs/verifier_search_pruning.c | 3 +- 2 files changed, 32 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +0
-0kernel/bpf/verifier.c static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) · line 12938
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -12933,12 +12933,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)if (BPF_SRC (insn->code) ==BPF_X ) {struct bpf_reg_state *src_reg = regs + insn->src_reg;struct bpf_reg_state *dst_reg = regs + insn->dst_reg; +bool need_id = (src_reg->type ==SCALAR_VALUE && !src_reg->id && + !tnum_is_const (src_reg->var_off));nit: unnecessary outer ()
Quoted 9 lines
kernel/bpf/verifier.c +1
-1if (BPF_CLASS (insn->code) ==BPF_ALU64 ) {/* case: R1 = R2 * copy register state to dest reg */ -if (src_reg->type ==SCALAR_VALUE && !src_reg->id) +if (need_id)/* Assign src and dst registers the same ID * that will be used by find_equal_scalars() * to propagate min/max range. [...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
[...]
Quoted 53 lines
Quoted 5 lines
Hm.. It's clever and pretty minimal, I like it. We are basically allocating virtual ID for SCALAR that doesn't have id, just to make sure we get a conflict if the SCALAR with ID cannot be mapped into two different SCALARs, right?
Quoted 7 lines
The only question would be if it's safe to do that for case when
old_reg->id!= 0 andcur_reg->id== 0? E.g., if in old (verified) state we have r6.id = r7.id = 123, and in new state we have r6.id = 0 and r7.id = 0, then your implementation above will say that states are equivalent. But are they, given there is a link between r6 and r7 that might be required for correctness. Which we don't have in current state.You mean the other way around, rold.id == 0, rcur.id != 0, right? (below 0/2 means: original value 0, replaced by new id 2).
(1) old cur
r6.id 0/2 1
r7.id 0/3 1check_idsreturns true(2) old cur
r6.id 1 0/2
r7.id 1 0/3check_idsreturns falseAlso, (1) is no different from (3):
(3) old cur
r6.id 1 3
r7.id 2 3check_idsreturns trueCurrent check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_ids(rold->id, rcur->id, idmap);Will reject (1) and (2), but will accept (3).
New check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_scalar_ids(rold->id, rcur->id, idmap);Will reject (2), but will accept (1) and (3).
And modification of
check_scalar_ids()to generate IDs only for rold or only for rcur would not reject (3) either.
Quoted 17 lines
(3) would be rejected only if current check is used together with elimination of unique scalar IDs from old states.
My previous experiments show that eliminating unique IDs from old states and not eliminating unique IDs from cur states is *very* bad for performance.
Quoted 10 lines
So with this we are getting to my original concerns with your !rold->id approach, which tries to ignore the necessity of link between registers.
What if we do this only for old registers? Then, (in old state) r6.id = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be rejected because first we'll map 123 to newly allocated X for r6.id, and then when we try to match r7.id=123 to another allocated ID X+1 we'll get a conflict, right?
[...]
Ok, here is what I think is the final version:
a. for each old or cur ID generate temporary unique ID;
b. for scalars use modified check_ids that forbids mapping same 'cur'
ID to several different 'old' IDs.
(a) allows to reject situations like:
(1) old cur (2) old cur r6.id 0 1 r6.id 1 0 r7.id 0 1 r7.id 1 0
(b) allows to reject situations like:
(3) old cur
r6.id 1 3
r7.id 2 3
And whether some scalar ID is unique or not does not matter for the algorithm.
Tests are passing, katran example is fine (350k insns, 29K states), minor veristat regression:
File Program States (DIFF) --------- ------------------------------ ------------- bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +3 (+0.80%) bpf_xdp.o tail_rev_nodeport_lb4 +2 (+0.50%)
--- 8< -----------------------------
kernel/bpf/verifier.c +26 -1
@@ -15149,6 +15149,31 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +static bool check_scalar_ids (struct bpf_verifier_env *env,u32 old_id,u32 cur_id, +struct bpf_id_pair *idmap) +{ +unsigned int i; + + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; + +for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { +if (!idmap[i].old) { +/* Reached an empty slot; haven't seen this id before */ + idmap[i].old = old_id; + idmap[i].cur = cur_id; +return true; + } +if (idmap[i].old == old_id) +return idmap[i].cur == cur_id; +if (idmap[i].cur == cur_id) +return false; + } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +return false; +} +static void clean_func_state (struct bpf_verifier_env *env,struct bpf_func_state *st) {
@@ -15325,7 +15350,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_scalar_ids (env, rold->id, rcur->id, idmap);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM :
----------------------------- >8 ---
Re: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 18 lines · Eduard Zingerman
On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
[...]Quoted 15 lines
Quoted 5 lines
Hm.. It's clever and pretty minimal, I like it. We are basically allocating virtual ID for SCALAR that doesn't have id, just to make sure we get a conflict if the SCALAR with ID cannot be mapped into two different SCALARs, right?
Quoted 7 lines
The only question would be if it's safe to do that for case when
old_reg->id!= 0 andcur_reg->id== 0? E.g., if in old (verified) state we have r6.id = r7.id = 123, and in new state we have r6.id = 0 and r7.id = 0, then your implementation above will say that states are equivalent. But are they, given there is a link between r6 and r7 that might be required for correctness. Which we don't have in current state.You mean the other way around, rold.id == 0, rcur.id != 0, right? (below 0/2 means: original value 0, replaced by new id 2).
no, I actually meant what I wrote, but I didn't realize that check_ids() is kind of broken... Because it shouldn't allow the same ID from cur state to be mapped to two different IDs in old state, should it?
Quoted 4 lines
Quoted 4 lines
(1) old cur
r6.id 0/2 1
r7.id 0/3 1check_idsreturns true
I think this should be rejected.
Quoted 4 lines
Quoted 4 lines
(2) old cur
r6.id 1 0/2
r7.id 1 0/3check_idsreturns false
And this should be rejected.
Quoted 6 lines
Quoted 6 lines
Also, (1) is no different from (3):
(3) old cur
r6.id 1 3
r7.id 2 3check_idsreturns true
And this definitely should be rejected.
The only situation that might not be rejected would be:
old cur r6.id 0/1 3 r7.id. 0/2 4
And perhaps this one is ok as well?
old cur r6.id 3 0/1 r7.id. 4 0/2
And my assumption was that that's what you are trying to do. But weirdly check_ids() is enforcing only that old ID has to have a unique mapping, which seems like a bug.
Quoted 91 lines
Quoted 24 lines
Current check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_ids(rold->id, rcur->id, idmap);Will reject (1) and (2), but will accept (3).
New check:
if (!rold->precise) return true; return range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off) && check_scalar_ids(rold->id, rcur->id, idmap);Will reject (2), but will accept (1) and (3).
And modification of
check_scalar_ids()to generate IDs only for rold or only for rcur would not reject (3) either.Quoted 17 lines
(3) would be rejected only if current check is used together with elimination of unique scalar IDs from old states.
My previous experiments show that eliminating unique IDs from old states and not eliminating unique IDs from cur states is *very* bad for performance.
Quoted 10 lines
So with this we are getting to my original concerns with your !rold->id approach, which tries to ignore the necessity of link between registers.
What if we do this only for old registers? Then, (in old state) r6.id = 0, r7.id = 0, (in new state) r6.id = r7.id = 123. This will be rejected because first we'll map 123 to newly allocated X for r6.id, and then when we try to match r7.id=123 to another allocated ID X+1 we'll get a conflict, right?
[...]
Ok, here is what I think is the final version:
a. for each old or cur ID generate temporary unique ID;
b. for scalars use modifiedcheck_idsthat forbids mapping same 'cur'
ID to several different 'old' IDs.(a) allows to reject situations like:
(1) old cur (2) old cur r6.id 0 1 r6.id 1 0 r7.id 0 1 r7.id 1 0(b) allows to reject situations like:
(3) old cur
r6.id 1 3
r7.id 2 3And whether some scalar ID is unique or not does not matter for the algorithm.
Tests are passing, katran example is fine (350k insns, 29K states), minor veristat regression:
File Program States (DIFF) --------- ------------------------------ ------------- bpf_xdp.o tail_nodeport_nat_ingress_ipv4 +3 (+0.80%) bpf_xdp.o tail_rev_nodeport_lb4 +2 (+0.50%)--- 8< -----------------------------
kernel/bpf/verifier.c +9
-0@@ -15149,6 +15149,31 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +static bool check_scalar_ids (struct bpf_verifier_env *env,u32 old_id,u32 cur_id, +struct bpf_id_pair *idmap) +{ +unsigned int i; + + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; + +for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) {
kernel/bpf/verifier.c static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap) · line 15170
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!idmap[i].old) { +/* Reached an empty slot; haven't seen this id before */ + idmap[i].old = old_id; + idmap[i].cur = cur_id; +return true; + } +if (idmap[i].old == old_id) +return idmap[i].cur == cur_id; +if (idmap[i].cur == cur_id) +return false;
I think this should just be added to existing check_ids(), I think it's a bug that we don't check this condition today in check_ids().
But I'd say let's land fixes you have right now. And then work on fixing and optimizing scala ID checks separately. We are doing too many things at the same time :(
Quoted 20 lines
kernel/bpf/verifier.c +7
-2+ } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +return false; +} +static void clean_func_state (struct bpf_verifier_env *env,struct bpf_func_state *st) {@@ -15325,7 +15350,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap); +check_scalar_ids (env, rold->id, rcur->id, idmap);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM : ----------------------------- >8 ---
Eduard Zingerman
maintainerRe: [PATCH bpf-next v3 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 17 lines · Andrii Nakryiko
Quoted 16 lines · Eduard Zingerman
On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
[...]Quoted 13 lines
Quoted 12 lines
Hm.. It's clever and pretty minimal, I like it. We are basically allocating virtual ID for SCALAR that doesn't have id, just to make sure we get a conflict if the SCALAR with ID cannot be mapped into two different SCALARs, right?
The only question would be if it's safe to do that for case when
old_reg->id!= 0 andcur_reg->id== 0? E.g., if in old (verified) state we have r6.id = r7.id = 123, and in new state we have r6.id = 0 and r7.id = 0, then your implementation above will say that states are equivalent. But are they, given there is a link between r6 and r7 that might be required for correctness. Which we don't have in current state.
Quoted 7 lines
Quoted 2 lines
Quoted 2 lines
You mean the other way around, rold.id == 0, rcur.id != 0, right? (below 0/2 means: original value 0, replaced by new id 2).
no, I actually meant what I wrote, but I didn't realize that
check_ids()is kind of broken... Because it shouldn't allow the same ID from cur state to be mapped to two different IDs in old state, should it?
IDs are used for several things, and it looks like the answer might vary.
For example, I looked at mark_ptr_or_null_regs():
- it is called when conditional of form (ptr == NULL) is checked;
- it marks every register with pointer having same ID as ptr as null/non-null;
- when register is marked not null ID is removed (not for locks but ignore it for now).
Assume r6 and r7 are both PTR_MAYBE_NULL and ID assignments look as follows:
old cur
r6.id 1 3
r7.id 2 3
'old' is safe, which means the following:
- either r6 was not accessed or it was guarded by (r6 == NULL)
- either r7 was not accessed or it was guarded by (r7 == NULL)
In both cases it should be ok, if r6 and r7 are in fact the same pointer. It would be checked to be not NULL two times but that's fine. So, I'd say that 'cur' is a special case of 'old' and check_ids() is correct for it. But this is the same argument I used for scalars and you were not convinced :)
Need to examine each use case carefully.
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
(1) old cur
r6.id 0/2 1
r7.id 0/3 1check_idsreturns trueI think this should be rejected.
That's what we agreed upon when decided not to do !rold->id, so yes.
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
(2) old cur
r6.id 1 0/2
r7.id 1 0/3check_idsreturns falseAnd this should be rejected.
For sure.
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines
Also, (1) is no different from (3):
(3) old cur
r6.id 1 3
r7.id 2 3check_idsreturns trueAnd this definitely should be rejected.
Same as (1).
Quoted 11 lines
The only situation that might not be rejected would be:
old cur r6.id 0/1 3 r7.id. 0/2 4And perhaps this one is ok as well?
old cur r6.id 3 0/1 r7.id. 4 0/2
I think these two should be accepted.
[...]
Quoted 23 lines
Quoted 9 lines
kernel/bpf/verifier.c +9
-0+static bool check_scalar_ids (struct bpf_verifier_env *env,u32 old_id,u32 cur_id, +struct bpf_id_pair *idmap) +{ +unsigned int i; + + old_id = old_id ? old_id : env->id_gen++; + cur_id = cur_id ? cur_id : env->id_gen++; + +for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) {kernel/bpf/verifier.c static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap) · line 15170
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!idmap[i].old) { +/* Reached an empty slot; haven't seen this id before */ + idmap[i].old = old_id; + idmap[i].cur = cur_id; +return true; + } +if (idmap[i].old == old_id) +return idmap[i].cur == cur_id; +if (idmap[i].cur == cur_id) +return false;I think this should just be added to existing
check_ids(), I think it's a bug that we don't check this condition today incheck_ids().
Quoted 3 lines
But I'd say let's land fixes you have right now. And then work on fixing and optimizing scala ID checks separately. We are doing too many things at the same time :(
Ok, will post V4 with these changes and examine other cases later. Thanks again for the discussion.
[...]
Eduard Zingerman
maintainerPATCH v3 4/4 selftests/bpf: verify that check_ids() is used for scalars in regsafe()
In reply to Eduard ZingermanVerify that the following example is rejected by verifier:
r9 = ... some pointer with range X ...
r6 = ... unbound scalar ID=a ...
r7 = ... unbound scalar ID=b ...
if (r6 > r7) goto +1
r7 = r6
if (r7 > X) goto exit
r9 += r6
*(u64 *)r9 = Y
Also add test cases to check that check_alu_op() for BPF_MOV instruction does not allocate scalar ID if source register is a constant.
--- .../selftests/bpf/progs/verifier_scalar_ids.c | 184 ++++++++++++++++++ 1 file changed, 184 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +184 -0
@@ -321,4 +321,188 @@ __naked void precision_two_ids(void) : __clobber_all); } +/* Verify that check_ids() is used by regsafe() for scalars. +* +* r9 = ... some pointer with range X ... +* r6 = ... unbound scalar ID=a ... +* r7 = ... unbound scalar ID=b ... +* if (r6 > r7) goto +1 +* r6 = r7 +* if (r6 > X) goto exit +* r9 += r7 +* *(u8 *)r9 = Y +* +* The memory access is safe only if r7 is bounded, +* which is true for one branch and not true for another. +*/ +SEC("socket") +__failure __msg("register with unbounded min value") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void check_ids_in_regsafe(void) +{ + asmvolatile ( +/* Bump allocated stack */ +"r1 = 0;" +"*(u64*)(r10 - 8) = r1;" +/* r9 = pointer to stack */ +"r9 = r10;" +"r9 += -8;" +/* r7 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r7 = r0;" +/* r6 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r6 = r0;" +/* if r6 > r7 is an unpredictable jump */ +"if r6 > r7 goto l1_%=;" +"r7 = r6;" +"l1_%=:" +/* if r6 > 4 exit(0) */ +"if r7 > 4 goto l2_%=;" +/* Access memory at r9[r7] */ +"r9 += r6;" +"r0 = *(u8*)(r9 + 0);" +"l2_%=:" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Similar to check_ids_in_regsafe. +* The l0 could be reached in two states: +* +* (1) r6{.id=A}, r7{.id=A}, r8{.id=B} +* (2) r6{.id=B}, r7{.id=A}, r8{.id=B} +* +* Where (2) is not safe, as "r7 > 4" check won't propagate range for it. +* This example would be considered safe without changes to +* mark_chain_precision() to track scalar values with equal IDs. +*/ +SEC("socket") +__failure __msg("register with unbounded min value") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void check_ids_in_regsafe_2(void) +{ + asmvolatile ( +/* Bump allocated stack */ +"r1 = 0;" +"*(u64*)(r10 - 8) = r1;" +/* r9 = pointer to stack */ +"r9 = r10;" +"r9 += -8;" +/* r8 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r8 = r0;" +/* r7 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r7 = r0;" +/* r6 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r6 = r0;" +/* scratch .id from r0 */ +"r0 = 0;" +/* if r6 > r7 is an unpredictable jump */ +"if r6 > r7 goto l1_%=;" +/* tie r6 and r7 .id */ +"r6 = r7;" +"l0_%=:" +/* if r7 > 4 exit(0) */ +"if r7 > 4 goto l2_%=;" +/* Access memory at r9[r7] */ +"r9 += r6;" +"r0 = *(u8*)(r9 + 0);" +"l2_%=:" +"r0 = 0;" +"exit;" +"l1_%=:" +/* tie r6 and r8 .id */ +"r6 = r8;" +"goto l0_%=;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that scalar IDs *are not* generated on register to register +* assignments if source register is a constant. +* +* If such IDs *are* generated the 'l1' below would be reached in +* two states: +* +* (1) r1{.id=A}, r2{.id=A} +* (2) r1{.id=C}, r2{.id=C} +* +* Thus forcing 'if r1 == r2' verification twice. +*/ +SEC("socket") +__success __log_level(2) +__msg("11: (1d) if r3 == r4 goto pc+0") +__msg("frame 0: propagating r3,r4") +__msg("11: safe") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void no_scalar_id_for_const(void) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +/* unpredictable jump */ +"if r0 > 7 goto l0_%=;" +/* possibly generate same scalar ids for r3 and r4 */ +"r1 = 0;" +"r1 = r1;" +"r3 = r1;" +"r4 = r1;" +"goto l1_%=;" +"l0_%=:" +/* possibly generate different scalar ids for r3 and r4 */ +"r1 = 0;" +"r2 = 0;" +"r3 = r1;" +"r4 = r2;" +"l1_%=:" +/* predictable jump, marks r3 and r4 precise */ +"if r3 == r4 goto +0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Same as no_scalar_id_for_const() but for 32-bit values */ +SEC("socket") +__success __log_level(2) +__msg("11: (1e) if w3 == w4 goto pc+0") +__msg("frame 0: propagating r3,r4") +__msg("11: safe") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void no_scalar_id_for_const32(void) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +/* unpredictable jump */ +"if r0 > 7 goto l0_%=;" +/* possibly generate same scalar ids for r3 and r4 */ +"w1 = 0;" +"w1 = w1;" +"w3 = w1;" +"w4 = w1;" +"goto l1_%=;" +"l0_%=:" +/* possibly generate different scalar ids for r3 and r4 */ +"w1 = 0;" +"w2 = 0;" +"w3 = w1;" +"w4 = w2;" +"l1_%=:" +/* predictable jump, marks r1 and r2 precise */ +"if w3 == w4 goto +0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v3 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe()
Quoted 20 lines · Eduard Zingerman
Verify that the following example is rejected by verifier:
r9 = ... some pointer with range X ...
r6 = ... unbound scalar ID=a ...
r7 = ... unbound scalar ID=b ...
if (r6 > r7) goto +1
r7 = r6
if (r7 > X) goto exit
r9 += r6
*(u64 *)r9 = YAlso add test cases to check that
check_alu_op()forBPF_MOVinstruction does not allocate scalar ID if source register is a constant.Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/progs/verifier_scalar_ids.c | 184 ++++++++++++++++++ 1 file changed, 184 insertions(+)
[...]
Quoted 37 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +37
-0+/* Similar to check_ids_in_regsafe. +* The l0 could be reached in two states: +* +* (1) r6{.id=A}, r7{.id=A}, r8{.id=B} +* (2) r6{.id=B}, r7{.id=A}, r8{.id=B} +* +* Where (2) is not safe, as "r7 > 4" check won't propagate range for it. +* This example would be considered safe without changes to +* mark_chain_precision() to track scalar values with equal IDs. +*/ +SEC("socket") +__failure __msg("register with unbounded min value") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void check_ids_in_regsafe_2(void) +{ + asmvolatile ( +/* Bump allocated stack */ +"r1 = 0;" +"*(u64*)(r10 - 8) = r1;" +/* r9 = pointer to stack */ +"r9 = r10;" +"r9 += -8;" +/* r8 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r8 = r0;" +/* r7 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r7 = r0;" +/* r6 = ktime_get_ns() */ +"call %[bpf_ktime_get_ns];" +"r6 = r0;" +/* scratch .id from r0 */ +"r0 = 0;" +/* if r6 > r7 is an unpredictable jump */ +"if r6 > r7 goto l1_%=;" +/* tie r6 and r7 .id */ + "r6 = r7;"
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c __naked void precision_two_ids(void) · line 419
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +10
-0+"l0_%=:" +/* if r7 > 4 exit(0) */ +"if r7 > 4 goto l2_%=;" +/* Access memory at r9[r7] */ +"r9 += r6;" +"r0 = *(u8*)(r9 + 0);" +"l2_%=:" +"r0 = 0;" +"exit;" +"l1_%=:"
complete offtopic, feel free to ignore:
I must say that this "l0_%=" pattern is so ugly that I instead choose to use local labels and specify forward/backward mark:
goto 1f; /* forward */
1:
...
goto 1b; /* backward */I can see why _%= is good for the code generation approach (and even then it probably is not hard to determine this b/f mark during codegen), but for manual code I'm not convinced it's worth it :)
Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +14
-0+/* tie r6 and r8 .id */ + "r6 = r8;" + "goto l0_%=;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that scalar IDs *are not* generated on register to register +* assignments if source register is a constant. +* +* If such IDs *are* generated the 'l1' below would be reached in +* two states: +*
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c __naked void precision_two_ids(void) · line 443
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +10
-0+* (1) r1{.id=A}, r2{.id=A} +* (2) r1{.id=C}, r2{.id=C} +* +* Thus forcing 'if r1 == r2' verification twice. +*/ +SEC("socket") +__success __log_level(2) +__msg("11: (1d) if r3 == r4 goto pc+0") +__msg("frame 0: propagating r3,r4") +__msg ("11: safe" )
would this detect that if r1 == r2 happens twice, if it did?
maybe we should check the number of verified states instead? We control branching and checkpointing, so this should be stable, right?
Quoted 29 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +29
-0+__flag (BPF_F_TEST_STATE_FREQ) +__naked void no_scalar_id_for_const(void) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +/* unpredictable jump */ +"if r0 > 7 goto l0_%=;" +/* possibly generate same scalar ids for r3 and r4 */ +"r1 = 0;" +"r1 = r1;" +"r3 = r1;" +"r4 = r1;" +"goto l1_%=;" +"l0_%=:" +/* possibly generate different scalar ids for r3 and r4 */ +"r1 = 0;" +"r2 = 0;" +"r3 = r1;" +"r4 = r2;" +"l1_%=:" +/* predictable jump, marks r3 and r4 precise */ +"if r3 == r4 goto +0;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} +
[...]