verify scalar ids mapping in regsafe()
Subsystems (4)
Eduard Zingerman
maintainerv4 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 a special version of check_ids() for precise scalar values.
Changelog:
- V3 -> V4:
- check_ids() in regsafe() is replaced by check_scalar_ids(), as discussed with Andrii in [3],
Note: I did not transfer Andrii's ack for patch #3 from V3 because
of the changes to the algorithm.
- reg_id_scratch is renamed to idset_scratch;
- mark_precise_scalar_ids() is modified to propagate error from
idset_push();
- test cases adjusted according to feedback from Andrii for V3.
- 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/ [V3] 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 [3] https://lore.kernel.org/bpf/[email protected]/T/#m89da8eeb2fa8c9ca1202c5d0b6660e1f72e45e04
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 | 11 +- kernel/bpf/verifier.c | 192 ++++- .../selftests/bpf/prog_tests/verifier.c | 2 + .../selftests/bpf/progs/verifier_scalar_ids.c | 657 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 5 files changed, 860 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Signature · 1 line
2.40.1
Eduard Zingerman
maintainerPATCH v4 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 | 115 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 128 insertions(+), 5 deletions(-)
include/linux/bpf_verifier.h +9 -1
@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_idset { +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 bpf_idset idset_scratch; + };struct {int *insn_state;int *insn_stack;
kernel/bpf/verifier.c +115 -0
127 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 v4 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 118 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 | 115 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 128 insertions(+), 5 deletions(-)include/linux/bpf_verifier.h +9
-1@@ -559,6 +559,11 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_idset { +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 bpf_idset idset_scratch; + };struct {int *insn_state;int *insn_stack;kernel/bpf/verifier.c +51
-0@@ -3787,6 +3787,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static bool idset_contains (struct bpf_idset *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i) +if (s->ids[i] == id) +return true; + +return false; +} + +static int idset_push (struct bpf_idset *s,u32 id) +{ +if (WARN_ON_ONCE (s->count >=ARRAY_SIZE (s->ids))) +return -1 ; + s->ids[s->count++] = id; +return 0 ; +} + +static void idset_reset (struct bpf_idset *s) +{ + 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 int mark_precise_scalar_ids (struct bpf_verifier_env *env,struct bpf_verifier_state *st) +{ +struct bpf_idset *precise_ids = &env->idset_scratch; +struct backtrack_state *bt = &env->bt; +struct bpf_func_state *func; +struct bpf_reg_state *reg; +DECLARE_BITMAP (mask,64 ); +int i, fr; + +idset_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 (idset_push (precise_ids, reg->id)) +return -1 ; + } + +bitmap_from_u64 (mask,bt_frame_stack_mask (bt, fr));
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3850
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+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) +continue ; +if (idset_push (precise_ids, reg->id)) +return -1 ;
-EFAULT, -1 is -EPERM, super confusing if it ever bubbles up. Same for idset_push return code, please use more appropriate error code constants
Other than that, it looks good. Please add my ack once you fix error values:
Quoted 29 lines
kernel/bpf/verifier.c +29
-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 (!idset_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 (!idset_contains (precise_ids, reg->id)) +continue ; +bt_set_frame_slot (bt, fr, i); + } + } + +return 0 ; +} +
[...]
Eduard Zingerman
maintainerPATCH v4 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 | 344 ++++++++++++++++++ 2 files changed, 346 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 +344 -0
344 lines not on this page · raw message
Signature · 1 line
2.40.1
Eduard Zingerman
maintainerPATCH v4 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 adds a new function: check_scalar_ids() and updates regsafe() to call it for precise scalar registers. check_scalar_ids() differs from check_ids() in order to:
- treat ID zero as a unique scalar ID;
- disallow mapping same 'cur_id' to multiple 'old_id'.
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.
--- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 77 +++++++++++++++++++++++++++++++++--- 2 files changed, 73 insertions(+), 5 deletions(-)
include/linux/bpf_verifier.h +1 -0
@@ -584,6 +584,7 @@ struct bpf_verifier_env {u32 used_map_cnt;/* number of used maps */ u32 used_btf_cnt;/* number of used BTF objects */ u32 id_gen;/* used to generate unique reg IDs */ +u32 tmp_id_gen;bool explore_alu_limits;bool allow_ptr_leaks;bool allow_uninit_stack;
kernel/bpf/verifier.c +72 -5
124 lines not on this page · raw message
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v4 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 36 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 adds a new function:
check_scalar_ids()and updatesregsafe()to call it for precise scalar registers.check_scalar_ids()differs fromcheck_ids()in order to:
- treat ID zero as a unique scalar ID;
- disallow mapping same 'cur_id' to multiple 'old_id'.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.
Quoted 7 lines
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 77 +++++++++++++++++++++++++++++++++--- 2 files changed, 73 insertions(+), 5 deletions(-)
I have lots of gripes with specifics in this patch, as you can see below. But ultimately this should fix the issue and we can discuss the rest separately.
Quoted 59 lines
include/linux/bpf_verifier.h +1
-0@@ -584,6 +584,7 @@ struct bpf_verifier_env {u32 used_map_cnt;/* number of used maps */ u32 used_btf_cnt;/* number of used BTF objects */ u32 id_gen;/* used to generate unique reg IDs */ +u32 tmp_id_gen;bool explore_alu_limits;bool allow_ptr_leaks;bool allow_uninit_stack;kernel/bpf/verifier.c +18
-2@@ -12942,12 +12942,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. @@ -12966,7 +12968,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 @@ -15148,6 +15150,36 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +/* Similar to check_ids(), but: +* - disallow mapping of different 'old_id' values to same 'cur_id' value; +* - for zero 'old_id' or 'cur_id' allocate a unique temporary ID +* to allow pairs like '0 vs unique ID', 'unique ID vs 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->tmp_id_gen; + cur_id = cur_id ? cur_id : ++env->tmp_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 15176
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;
As I mentioned, I think we should do it always (even if in some *partial* cases this might not be necessary to guarantee correctness), I believe this is what idmap semantics is promising to check, but we actually don't. But we can discuss that separately.
Quoted 10 lines
kernel/bpf/verifier.c +6
-0+ } +/* 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) {
kernel/bpf/verifier.c static bool regs_exact(const struct bpf_reg_state *rold, · line 15294
Quoted 10 lines
kernel/bpf/verifier.c +7
-0@@ -15253,6 +15285,15 @@ static bool regs_exact(const struct bpf_reg_state *rold,check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); } +static bool scalar_regs_exact (struct bpf_verifier_env *env, +const struct bpf_reg_state *rold, +const struct bpf_reg_state *rcur, +struct bpf_id_pair *idmap) +{ +return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && +check_scalar_ids (env, rold->id, rcur->id, idmap);
At this point I don't know if there is any benefit to having this special scalar_regs_exact() implementation. We are just assuming that memcmp() of 88 bytes is significantly faster than doing range_within() (8 straightforward comparisons) and tnum_in() (few bit operations and one comparison). And if this doesn't work out, we pay the price of both memcmp and range_within+tnum_in. Plus check_scalar_ids() in both cases.
I suspect that just dropping memcmp() will be at least not worse, if not better.
Quoted 49 lines
kernel/bpf/verifier.c +29
-3+} +/* Returns true if (rold safe implies rcur safe) */ static bool regsafe (struct bpf_verifier_env *env,struct bpf_reg_state *rold,struct bpf_reg_state *rcur,struct bpf_id_pair *idmap)@@ -15292,15 +15333,39 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : -if (regs_exact (rold, rcur, idmap)) +if (scalar_regs_exact (env, rold, rcur, idmap))return true;if (env->explore_alu_limits)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_scalar_ids (env, rold->id, rcur->id, idmap);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM :
kernel/bpf/verifier.c static bool states_equal(struct bpf_verifier_env *env, · line 15611
Quoted 5 lines
kernel/bpf/verifier.c +2
-0@@ -15542,6 +15607,8 @@ static bool states_equal(struct bpf_verifier_env *env,if (old->active_rcu_lock != cur->active_rcu_lock)return false; + env->tmp_id_gen = env->id_gen; +
sigh, this is kind of ugly, but ok :( Ideally we have
struct idmap_scratch {
int id_gen;
struct bpf_id_pair mapping[BPF_ID_MAP_SIZE];
}and just initialize idmap_scratch.id_gen = env->id_gen and keep all this very local to id_map.
But I'm nitpicking.
Quoted 6 lines
kernel/bpf/verifier.c +0
-1/* for states to be equal callsites have to be the same * and all frame states need to be equivalent */ --2.40.1
Eduard Zingerman
maintainerRe: [PATCH bpf-next v4 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 118 lines · Andrii Nakryiko
Quoted 36 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 adds a new function:
check_scalar_ids()and updatesregsafe()to call it for precise scalar registers.check_scalar_ids()differs fromcheck_ids()in order to:
- treat ID zero as a unique scalar ID;
- disallow mapping same 'cur_id' to multiple 'old_id'.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.Quoted 7 lines
Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 1 + kernel/bpf/verifier.c | 77 +++++++++++++++++++++++++++++++++--- 2 files changed, 73 insertions(+), 5 deletions(-)I have lots of gripes with specifics in this patch, as you can see below. But ultimately this should fix the issue and we can discuss the rest separately.
Acked-by Andrii Nakryiko <[email protected]>Quoted 66 lines
include/linux/bpf_verifier.h +1
-0@@ -584,6 +584,7 @@ struct bpf_verifier_env {u32 used_map_cnt;/* number of used maps */ u32 used_btf_cnt;/* number of used BTF objects */ u32 id_gen;/* used to generate unique reg IDs */ +u32 tmp_id_gen;bool explore_alu_limits;bool allow_ptr_leaks;bool allow_uninit_stack;kernel/bpf/verifier.c +25
-2@@ -12942,12 +12942,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. @@ -12966,7 +12968,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 @@ -15148,6 +15150,36 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return false; } +/* Similar to check_ids(), but: +* - disallow mapping of different 'old_id' values to same 'cur_id' value; +* - for zero 'old_id' or 'cur_id' allocate a unique temporary ID +* to allow pairs like '0 vs unique ID', 'unique ID vs 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->tmp_id_gen; + cur_id = cur_id ? cur_id : ++env->tmp_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)
Quoted 8 lines
kernel/bpf/verifier.c static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap) · line 15176
Quoted 3 lines
kernel/bpf/verifier.c +3
-0+return idmap[i].cur == cur_id; +if (idmap[i].cur == cur_id) +return false;As I mentioned, I think we should do it always (even if in some *partial* cases this might not be necessary to guarantee correctness), I believe this is what idmap semantics is promising to check, but we actually don't. But we can discuss that separately.
I'll compile the list of use-cases and we can discuss.
Quoted 30 lines
Quoted 11 lines
kernel/bpf/verifier.c +6
-0+ } +/* 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) {kernel/bpf/verifier.c static bool regs_exact(const struct bpf_reg_state *rold, · line 15294
Quoted 10 lines
kernel/bpf/verifier.c +7
-0@@ -15253,6 +15285,15 @@ static bool regs_exact(const struct bpf_reg_state *rold,check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); } +static bool scalar_regs_exact (struct bpf_verifier_env *env, +const struct bpf_reg_state *rold, +const struct bpf_reg_state *rcur, +struct bpf_id_pair *idmap) +{ +return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && +check_scalar_ids (env, rold->id, rcur->id, idmap);At this point I don't know if there is any benefit to having this special
scalar_regs_exact()implementation. We are just assuming thatmemcmp()of 88 bytes is significantly faster than doingrange_within()(8 straightforward comparisons) andtnum_in()(few bit operations and one comparison). And if this doesn't work out, we pay the price of both memcmp and range_within+tnum_in. Pluscheck_scalar_ids()in both cases.
Quoted 1 line
I suspect that just dropping
memcmp()will be at least not worse, if not better.
Sounds reasonable, but I'm a bit hesitant here because of the "explore_alu_limits":
if (scalar_regs_exact(env, rold, rcur, idmap))
return true;
if (env->explore_alu_limits)
return false;tbh, I don't understand if this special case is necessary for "explore_alu_limits", will think about it.
Quoted 58 lines
Quoted 50 lines
kernel/bpf/verifier.c +29
-3+} +/* Returns true if (rold safe implies rcur safe) */ static bool regsafe (struct bpf_verifier_env *env,struct bpf_reg_state *rold,struct bpf_reg_state *rcur,struct bpf_id_pair *idmap)@@ -15292,15 +15333,39 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : -if (regs_exact (rold, rcur, idmap)) +if (scalar_regs_exact (env, rold, rcur, idmap))return true;if (env->explore_alu_limits)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_scalar_ids (env, rold->id, rcur->id, idmap);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :case PTR_TO_MEM :kernel/bpf/verifier.c static bool states_equal(struct bpf_verifier_env *env, · line 15611
Quoted 5 lines
kernel/bpf/verifier.c +2
-0@@ -15542,6 +15607,8 @@ static bool states_equal(struct bpf_verifier_env *env,if (old->active_rcu_lock != cur->active_rcu_lock)return false; + env->tmp_id_gen = env->id_gen; +sigh, this is kind of ugly, but ok :( Ideally we have
Quoted 7 lines
struct idmap_scratch { int id_gen; struct bpf_id_pair mapping[BPF_ID_MAP_SIZE]; }and just initialize idmap_scratch.id_gen =
env->id_genand keep all this very local toid_map.
This looks better, will update the patch.
Quoted 10 lines
But I'm nitpicking.
Quoted 6 lines
kernel/bpf/verifier.c +0
-1/* for states to be equal callsites have to be the same * and all frame states need to be equivalent */ --2.40.1
Eduard Zingerman
maintainerPATCH v4 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;
- check that unique scalar IDs are ignored when new verifier state is compared to cached verifier state;
- check that two different scalar IDs in a verified state can't be mapped to the same scalar ID in current state.
--- .../selftests/bpf/progs/verifier_scalar_ids.c | 313 ++++++++++++++++++ 1 file changed, 313 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +313 -0
@@ -341,4 +341,317 @@ __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") +__msg("processed 15 insns") +__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") +__msg("processed 15 insns") +__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); +} + +/* Check that unique scalar IDs are ignored when new verifier state is +* compared to cached verifier state. For this test: +* - cached state has no id on r1 +* - new state has a unique id on r1 +*/ +SEC("socket") +__success __log_level(2) +__msg("6: (25) if r6 > 0x7 goto pc+1") +__msg("7: (57) r1 &= 255") +__msg("8: (bf) r2 = r10") +__msg("from 6 to 8: safe") +__msg("processed 12 insns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void ignore_unique_scalar_ids_cur(void) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +"r6 = r0;" +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* r1.id == r0.id */ +"r1 = r0;" +/* make r1.id unique */ +"r0 = 0;" +"if r6 > 7 goto l0_%=;" +/* clear r1 id, but keep the range compatible */ +"r1 &= 0xff;" +"l0_%=:" +/* get here in two states: +* - first: r1 has no id (cached state) +* - second: r1 has a unique id (should be considered equivalent) +*/ +"r2 = r10;" +"r2 += r1;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that unique scalar IDs are ignored when new verifier state is +* compared to cached verifier state. For this test: +* - cached state has a unique id on r1 +* - new state has no id on r1 +*/ +SEC("socket") +__success __log_level(2) +__msg("6: (25) if r6 > 0x7 goto pc+1") +__msg("7: (05) goto pc+1") +__msg("9: (bf) r2 = r10") +__msg("9: safe") +__msg("processed 13 insns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void ignore_unique_scalar_ids_old(void) +{ + asmvolatile ( +"call %[bpf_ktime_get_ns];" +"r6 = r0;" +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +/* r1.id == r0.id */ +"r1 = r0;" +/* make r1.id unique */ +"r0 = 0;" +"if r6 > 7 goto l1_%=;" +"goto l0_%=;" +"l1_%=:" +/* clear r1 id, but keep the range compatible */ +"r1 &= 0xff;" +"l0_%=:" +/* get here in two states: +* - first: r1 has a unique id (cached state) +* - second: r1 has no id (should be considered equivalent) +*/ +"r2 = r10;" +"r2 += r1;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + +/* Check that two different scalar IDs in a verified state can't be +* mapped to the same scalar ID in current state. +*/ +SEC("socket") +__success __log_level(2) +/* The exit instruction should be reachable from two states, +* use two matches and "processed .. insns" to ensure this. + */ +__msg("13: (95) exit") +__msg("13: (95) exit") +__msg("processed 18 insns") +__flag (BPF_F_TEST_STATE_FREQ) +__naked void two_old_ids_one_cur_id(void) +{ + asmvolatile ( +/* Give unique scalar IDs to r{6,7} */ +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +"r6 = r0;" +"call %[bpf_ktime_get_ns];" +"r0 &= 0xff;" +"r7 = r0;" +"r0 = 0;" +/* Maybe make r{6,7} IDs identical */ +"if r6 > r7 goto l0_%=;" +"goto l1_%=;" +"l0_%=:" +"r6 = r7;" +"l1_%=:" +/* Mark r{6,7} precise. +* Get here in two states: +* - first: r6{.id=A}, r7{.id=B} (cached state) +* - second: r6{.id=A}, r7{.id=A} +* Currently we don't want to consider such states equivalent. +* Thus, marker instruction "r0 = r0;" would be verified twice. +*/ +"r2 = r10;" +"r2 += r6;" +"r2 += r7;" +"exit;" + : + : __imm(bpf_ktime_get_ns) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.40.1