verify scalar ids mapping in regsafe()
Subsystems (4)
Eduard Zingerman
maintainerv5 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:
- V4 -> V5 (all changes are based on feedback for V4 from Andrii):
- mark_precise_scalar_ids() error code is updated to EFAULT;
- bpf_verifier_env::idmap_scratch field type is changed to struct
bpf_idmap to encapsulate temporary ID generation counter;
- regsafe() is updated to call scalar_regs_exact() only for env->explore_alu_limits case (this had no measurable impact on verification duration when tested using veristat).
- 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/ [V4] https://lore.kernel.org/bpf/[email protected]/ [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 | 25 +- kernel/bpf/verifier.c | 223 +++++- .../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, 883 insertions(+), 32 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/verifier_scalar_ids.c
Signature · 1 line
2.40.1
Eduard Zingerman
maintainerPATCH v5 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 v5 1/4] bpf: use scalar ids in mark_chain_precision()
Quoted 32 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().Acked-by Andrii Nakryiko <[email protected]>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(-)
[...]
Quoted 5 lines
kernel/bpf/verifier.c +5
-0+static bool idset_contains (struct bpf_idset *s,u32 id) +{ +u32 i; + +for (i =0 ; i < s->count; ++i)
kernel/bpf/verifier.c static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ · line 3804
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+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 ;
minor, but should be -EFAULT as well
Quoted 9 lines
kernel/bpf/verifier.c +9
-0+ s->ids[s->count++] = id; +return 0 ; +} + +static void idset_reset (struct bpf_idset *s) +{ + s->count =0 ; +} +
[...]
Eduard Zingerman
maintainerPATCH v5 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 v5 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.
Changes in this commit:
- Function check_scalar_ids() is added, it differs from check_ids() in the following aspects:
- treats ID zero as a unique scalar ID;
- disallows mapping same 'cur_id' to multiple 'old_id'.
- check_scalar_ids() needs to generate temporary unique IDs, field 'tmp_id_gen' is added to bpf_verifier_env::idmap_scratch to facilitate this.
- Function scalar_regs_exact() is added, it differs from regs_exact() in the following aspects:
- uses check_scalar_ids() for ID comparison;
- does not check reg_obj_id as this field is not used for scalar values.
- regsafe() is updated to:
- use check_scalar_ids() for precise scalar registers.
- use scalar_regs_exact() for scalar registers, but only for explore_alu_limits branch. This simplifies control flow for scalar case, and has no measurable performance impact.
- check_alu_op() is updated avoid generating bpf_reg_state::id for constant scalar values when processing BPF_MOV. ID is needed to propagate range information for identical values, but there is nothing to propagate for constants.
--- include/linux/bpf_verifier.h | 17 ++++-- kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++------- 2 files changed, 97 insertions(+), 28 deletions(-)
include/linux/bpf_verifier.h +11 -6
@@ -313,11 +313,6 @@ struct bpf_idx_pair {u32 idx; }; -struct bpf_id_pair { -u32 old; -u32 cur; -}; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)
@@ -559,6 +554,16 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_id_pair { +u32 old; +u32 cur; +}; + +struct bpf_idmap { +u32 tmp_id_gen; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; +}; +struct bpf_idset {u32 count;u32 ids[BPF_ID_MAP_SIZE ];
@@ -596,7 +601,7 @@ struct bpf_verifier_env {struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ];union { -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct bpf_idmap idmap_scratch;struct bpf_idset idset_scratch; };struct {
kernel/bpf/verifier.c +86 -22
199 lines not on this page · raw message
Signature · 1 line
2.40.1
Re: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 173 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.Changes in this commit:
- Functioncheck_scalar_ids()is added, it differs fromcheck_ids()in the following aspects:
- treats ID zero as a unique scalar ID;
- disallows mapping same 'cur_id' to multiple 'old_id'.
-check_scalar_ids()needs to generate temporary unique IDs, field 'tmp_id_gen' is added tobpf_verifier_env::idmap_scratchto facilitate this.
- Functionscalar_regs_exact()is added, it differs fromregs_exact()in the following aspects:
- usescheck_scalar_ids()for ID comparison;
- does not checkreg_obj_idas this field is not used for scalar values.
-regsafe()is updated to:
- usecheck_scalar_ids()for precise scalar registers.
- usescalar_regs_exact()for scalar registers, but only forexplore_alu_limitsbranch. This simplifies control flow for scalar case, and has no measurable performance impact.
-check_alu_op()is updated avoid generatingbpf_reg_state::idfor constant scalar values when processingBPF_MOV. ID is needed to propagate range information for identical values, but there is nothing to propagate for constants.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Acked-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 17 ++++-- kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++------- 2 files changed, 97 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +11
-6@@ -313,11 +313,6 @@ struct bpf_idx_pair {u32 idx; }; -struct bpf_id_pair { -u32 old; -u32 cur; -}; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)@@ -559,6 +554,16 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_id_pair { +u32 old; +u32 cur; +}; + +struct bpf_idmap { +u32 tmp_id_gen; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; +}; +struct bpf_idset {u32 count;u32 ids[BPF_ID_MAP_SIZE ];@@ -596,7 +601,7 @@ struct bpf_verifier_env {struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ];union { -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct bpf_idmap idmap_scratch;struct bpf_idset idset_scratch; };struct {kernel/bpf/verifier.c +31
-8@@ -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 @@ -15122,8 +15124,9 @@ static bool range_within(struct bpf_reg_state *old,* So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ -static bool check_ids (u32 old_id,u32 cur_id,struct bpf_id_pair *idmap) +static bool check_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { +struct bpf_id_pair *map = idmap->map;unsigned int i;/* either both IDs should be set or both should be zero */ @@ -15134,14 +15137,44 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return true;for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!idmap[i].old) { +if (!map[i].old) {/* Reached an empty slot; haven't seen this id before */ - idmap[i].old = old_id; - idmap[i].cur = cur_id; + map[i].old = old_id; + map[i].cur = cur_id;return true; } -if (idmap[i].old == old_id) -return idmap[i].cur == cur_id; +if (map[i].old == old_id) +return map[i].cur == cur_id; + } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) +{ +struct bpf_id_pair *map = idmap->map; +unsigned int i; + + old_id = old_id ? old_id : ++idmap->tmp_id_gen; + cur_id = cur_id ? cur_id : ++idmap->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 15177
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!map[i].old) { +/* Reached an empty slot; haven't seen this id before */ + map[i].old = old_id; + map[i].cur = cur_id; +return true; + } +if (map[i].old == old_id) +return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false;
We were discussing w/ Alexei (offline) making these changes as backportable and minimal as possible, so I looked again how to minimize all the extra code added.
I still insist that the current logic in check_ids() is invalid to allow the same cur_id to map to two different old_ids, especially for non-SCALAR, actually. E.g., a situation where we have a register that is auto-invalidated. E.g., bpf_iter element (each gets an ID), or it could be id'ed dynptr_ringbuf.
Think about the following situation:
In the old state, we could have r1.id = 1; r2.id = 2; Two registers keep two separate pointers to ringbuf.
In the new state, we have r1.id = r2.id = 3; That is, two registers keep the *same* pointer to ringbuf elem.
Now imagine that a BPF program has bpf_ringbuf_submit(r1) and invalidates this register. With the old state it will invalidate r1 and will keep r2 valid. So it's safe for the BPF program to keep working with r2 as valid ringbuf (and eventually submit it as well).
Now this is entirely unsafe for the new state. Once bpf_ringbuf_submit(r1) happens, r2 shouldn't be accessed anymore. But yet it will be declared safe with current check_ids() logic.
Ergo, check_ids() should make sure we do not have multi-mapping for any of the IDs. Even if in some corner case that might be ok.
I actually tested this change with veristat, there are no regressions at all. I think it's both safe from a perf standpoint, and necessary and safe from a correctness standpoint.
So all in all (I did inline scalar_regs_exact in a separate patch, up to you), I have these changes on top and they all are good from veristat perspective:
Author: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 12:53:25 2023 -0700
bpf: inline scalar_regs_exact
kernel/bpf/verifier.c +0 -0
@@ -15262,14 +15262,6 @@ 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(const struct bpf_reg_state *rold,
- const struct bpf_reg_state *rcur,
- struct bpf_idmap *idmap)
-{
- return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
- check_scalar_ids(rold->id, rcur->id, idmap);
-}
-
/* 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_idmap *idmap)
@@ -15309,8 +15301,13 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
switch (base_type(rold->type)) {
case SCALAR_VALUE:- if (env->explore_alu_limits)
- return scalar_regs_exact(rold, rcur, idmap);
+ if (env->explore_alu_limits) {
+ /* explore_alu_limits disables tnum_in() andrange_within()
+ * logic and requires everything to be strict
+ */
+ return memcmp(rold, rcur, offsetof(structbpf_reg_state, id)) == 0 &&
+ check_scalar_ids(rold->id, rcur->id, idmap);
+ }
if (!rold->precise)
return true;
/* Why check_ids() for scalar registers?commit 57297c01fe747e423cd3c924ef492c0688d8057a
Author: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 11:46:46 2023 -0700
bpf: make check_ids disallow multi-mapping of IDs universally
kernel/bpf/verifier.c +0 -0
@@ -15137,6 +15137,8 @@ static bool check_ids(u32 old_id, u32 cur_id,
struct bpf_idmap *idmap)
}
if (map[i].old == old_id)
return map[i].cur == cur_id;
+ if (map[i].cur == cur_id)
+ return false;
}
/* We ran out of idmap slots, which should be impossible */
WARN_ON_ONCE(1);@@ -15144,33 +15146,15 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap)
}
/* 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(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) {
- struct bpf_id_pair *map = idmap->map;
- unsigned int i;
-
old_id = old_id ? old_id : ++idmap->tmp_id_gen;
cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen;- for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
- if (!map[i].old) {
- /* Reached an empty slot; haven't seen this id before */ - map[i].old = old_id; - map[i].cur = cur_id; - return true;
- }
- if (map[i].old == old_id)
- return map[i].cur == cur_id;
- if (map[i].cur == cur_id)
- return false;
- } - /* We ran out of idmap slots, which should be impossible */ - WARN_ON_ONCE(1); - return false; + return check_ids(old_id, cur_id, idmap);
}
static void clean_func_state(struct bpf_verifier_env *env,
Quoted 15 lines
kernel/bpf/verifier.c +1
-1}/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE (1 );@@ -15246,16 +15279,24 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,static bool regs_exact (const struct bpf_reg_state *rold,const struct bpf_reg_state *rcur, -struct bpf_id_pair *idmap) +struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); }
[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 215 lines · Andrii Nakryiko
Quoted 173 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.Changes in this commit:
- Functioncheck_scalar_ids()is added, it differs fromcheck_ids()in the following aspects:
- treats ID zero as a unique scalar ID;
- disallows mapping same 'cur_id' to multiple 'old_id'.
-check_scalar_ids()needs to generate temporary unique IDs, field 'tmp_id_gen' is added tobpf_verifier_env::idmap_scratchto facilitate this.
- Functionscalar_regs_exact()is added, it differs fromregs_exact()in the following aspects:
- usescheck_scalar_ids()for ID comparison;
- does not checkreg_obj_idas this field is not used for scalar values.
-regsafe()is updated to:
- usecheck_scalar_ids()for precise scalar registers.
- usescalar_regs_exact()for scalar registers, but only forexplore_alu_limitsbranch. This simplifies control flow for scalar case, and has no measurable performance impact.
-check_alu_op()is updated avoid generatingbpf_reg_state::idfor constant scalar values when processingBPF_MOV. ID is needed to propagate range information for identical values, but there is nothing to propagate for constants.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Acked-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 17 ++++-- kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++------- 2 files changed, 97 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +11
-6@@ -313,11 +313,6 @@ struct bpf_idx_pair {u32 idx; }; -struct bpf_id_pair { -u32 old; -u32 cur; -}; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)@@ -559,6 +554,16 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_id_pair { +u32 old; +u32 cur; +}; + +struct bpf_idmap { +u32 tmp_id_gen; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; +}; +struct bpf_idset {u32 count;u32 ids[BPF_ID_MAP_SIZE ];@@ -596,7 +601,7 @@ struct bpf_verifier_env {struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ];union { -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct bpf_idmap idmap_scratch;struct bpf_idset idset_scratch; };struct {kernel/bpf/verifier.c +31
-8@@ -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 @@ -15122,8 +15124,9 @@ static bool range_within(struct bpf_reg_state *old,* So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ -static bool check_ids (u32 old_id,u32 cur_id,struct bpf_id_pair *idmap) +static bool check_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { +struct bpf_id_pair *map = idmap->map;unsigned int i;/* either both IDs should be set or both should be zero */ @@ -15134,14 +15137,44 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return true;for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!idmap[i].old) { +if (!map[i].old) {/* Reached an empty slot; haven't seen this id before */ - idmap[i].old = old_id; - idmap[i].cur = cur_id; + map[i].old = old_id; + map[i].cur = cur_id;return true; } -if (idmap[i].old == old_id) -return idmap[i].cur == cur_id; +if (map[i].old == old_id) +return map[i].cur == cur_id; + } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) +{ +struct bpf_id_pair *map = idmap->map; +unsigned int i; + + old_id = old_id ? old_id : ++idmap->tmp_id_gen; + cur_id = cur_id ? cur_id : ++idmap->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 15177
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!map[i].old) { +/* Reached an empty slot; haven't seen this id before */ + map[i].old = old_id; + map[i].cur = cur_id; +return true; + } +if (map[i].old == old_id) +return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false;We were discussing w/ Alexei (offline) making these changes as backportable and minimal as possible, so I looked again how to minimize all the extra code added.
I still insist that the current logic in
check_ids()is invalid to allow the samecur_idto map to two differentold_ids, especially for non-SCALAR, actually. E.g., a situation where we have a register that is auto-invalidated. E.g.,bpf_iterelement (each gets an ID), or it could be id'eddynptr_ringbuf.Think about the following situation:
In the old state, we could have r1.id = 1; r2.id = 2; Two registers keep two separate pointers to ringbuf.
In the new state, we have r1.id = r2.id = 3; That is, two registers keep the *same* pointer to ringbuf elem.
Now imagine that a BPF program has
bpf_ringbuf_submit(r1)and invalidates this register. With the old state it will invalidate r1 and will keep r2 valid. So it's safe for the BPF program to keep working with r2 as valid ringbuf (and eventually submit it as well).Now this is entirely unsafe for the new state. Once
bpf_ringbuf_submit(r1)happens, r2 shouldn't be accessed anymore. But yet it will be declared safe with currentcheck_ids()logic.Ergo,
check_ids()should make sure we do not have multi-mapping for any of the IDs. Even if in some corner case that might be ok.
Quoted 7 lines
I actually tested this change with veristat, there are no regressions at all. I think it's both safe from a perf standpoint, and necessary and safe from a correctness standpoint.
So all in all (I did inline
scalar_regs_exactin a separate patch, up to you), I have these changes on top and they all are good from veristat perspective:
Ok, rinbuf is a good example.
To minimize the patch-set I'll do the following:
- move your check_ids patch to the beginning of the series
- add selftest for ringbuf
- squash the scalar_regs_exact patch with current patch #3
And resubmit with EFAULT fix in patch #1.
Thank you for looking into this.
Quoted 126 lines
Author: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 12:53:25 2023 -0700bpf: inline
scalar_regs_exactSigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +0
-8@@ -15262,14 +15262,6 @@ 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 (const struct bpf_reg_state *rold, -const struct bpf_reg_state *rcur, -struct bpf_idmap *idmap) -{ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); -} -/* 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, structbpf_idmap*idmap)kernel/bpf/verifier.c +5
-2@@ -15309,8 +15301,13 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) {case SCALAR_VALUE : -if (env->explore_alu_limits) -return scalar_regs_exact (rold, rcur, idmap); +if (env->explore_alu_limits) { +/* explore_alu_limits disables tnum_in() and range_within() +* logic and requires everything to be strict +*/ + return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0 &&kernel/bpf/verifier.c +2
-0+check_scalar_ids (rold->id, rcur->id, idmap); + }if (!rold->precise)return true;/* Why check_ids() for scalar registers? commit
57297c01fe747e423cd3c924ef492c0688d8057aAuthor: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 11:46:46 2023 -0700bpf: make
check_idsdisallow multi-mapping of IDs universallySigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +2
-0@@ -15137,6 +15137,8 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }if (map[i].old == old_id)return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false; }/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE(1);kernel/bpf/verifier.c +1
-19@@ -15144,33 +15146,15 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }/* 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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { -struct bpf_id_pair *map = idmap->map; -unsigned int i; - old_id = old_id ? old_id : ++idmap->tmp_id_gen; cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!map[i].old) { -/* Reached an empty slot; haven't seen this id before */ - map[i].old = old_id; - map[i].cur = cur_id; -return true; - } -if (map[i].old == old_id) -return map[i].cur == cur_id; -if (map[i].cur == cur_id) -return false; - } -/* We ran out of idmap slots, which should be impossible */ -WARN_ON_ONCE (1 ); -return false; +return check_ids (old_id, cur_id, idmap); }static void clean_func_state(struct
bpf_verifier_env*env,Quoted 15 lines
kernel/bpf/verifier.c +1
-1}/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE (1 );@@ -15246,16 +15279,24 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,static bool regs_exact (const struct bpf_reg_state *rold,const struct bpf_reg_state *rcur, -struct bpf_id_pair *idmap) +struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); }[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 224 lines · Eduard Zingerman
Quoted 215 lines · Andrii Nakryiko
Quoted 173 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.Changes in this commit:
- Functioncheck_scalar_ids()is added, it differs fromcheck_ids()in the following aspects:
- treats ID zero as a unique scalar ID;
- disallows mapping same 'cur_id' to multiple 'old_id'.
-check_scalar_ids()needs to generate temporary unique IDs, field 'tmp_id_gen' is added tobpf_verifier_env::idmap_scratchto facilitate this.
- Functionscalar_regs_exact()is added, it differs fromregs_exact()in the following aspects:
- usescheck_scalar_ids()for ID comparison;
- does not checkreg_obj_idas this field is not used for scalar values.
-regsafe()is updated to:
- usecheck_scalar_ids()for precise scalar registers.
- usescalar_regs_exact()for scalar registers, but only forexplore_alu_limitsbranch. This simplifies control flow for scalar case, and has no measurable performance impact.
-check_alu_op()is updated avoid generatingbpf_reg_state::idfor constant scalar values when processingBPF_MOV. ID is needed to propagate range information for identical values, but there is nothing to propagate for constants.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Acked-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 17 ++++-- kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++------- 2 files changed, 97 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +11
-6@@ -313,11 +313,6 @@ struct bpf_idx_pair {u32 idx; }; -struct bpf_id_pair { -u32 old; -u32 cur; -}; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)@@ -559,6 +554,16 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_id_pair { +u32 old; +u32 cur; +}; + +struct bpf_idmap { +u32 tmp_id_gen; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; +}; +struct bpf_idset {u32 count;u32 ids[BPF_ID_MAP_SIZE ];@@ -596,7 +601,7 @@ struct bpf_verifier_env {struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ];union { -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct bpf_idmap idmap_scratch;struct bpf_idset idset_scratch; };struct {kernel/bpf/verifier.c +31
-8@@ -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 @@ -15122,8 +15124,9 @@ static bool range_within(struct bpf_reg_state *old,* So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ -static bool check_ids (u32 old_id,u32 cur_id,struct bpf_id_pair *idmap) +static bool check_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { +struct bpf_id_pair *map = idmap->map;unsigned int i;/* either both IDs should be set or both should be zero */ @@ -15134,14 +15137,44 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return true;for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!idmap[i].old) { +if (!map[i].old) {/* Reached an empty slot; haven't seen this id before */ - idmap[i].old = old_id; - idmap[i].cur = cur_id; + map[i].old = old_id; + map[i].cur = cur_id;return true; } -if (idmap[i].old == old_id) -return idmap[i].cur == cur_id; +if (map[i].old == old_id) +return map[i].cur == cur_id; + } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) +{ +struct bpf_id_pair *map = idmap->map; +unsigned int i; + + old_id = old_id ? old_id : ++idmap->tmp_id_gen; + cur_id = cur_id ? cur_id : ++idmap->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 15177
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!map[i].old) { +/* Reached an empty slot; haven't seen this id before */ + map[i].old = old_id; + map[i].cur = cur_id; +return true; + } +if (map[i].old == old_id) +return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false;We were discussing w/ Alexei (offline) making these changes as backportable and minimal as possible, so I looked again how to minimize all the extra code added.
I still insist that the current logic in
check_ids()is invalid to allow the samecur_idto map to two differentold_ids, especially for non-SCALAR, actually. E.g., a situation where we have a register that is auto-invalidated. E.g.,bpf_iterelement (each gets an ID), or it could be id'eddynptr_ringbuf.Think about the following situation:
In the old state, we could have r1.id = 1; r2.id = 2; Two registers keep two separate pointers to ringbuf.
In the new state, we have r1.id = r2.id = 3; That is, two registers keep the *same* pointer to ringbuf elem.
Now imagine that a BPF program has
bpf_ringbuf_submit(r1)and invalidates this register. With the old state it will invalidate r1 and will keep r2 valid. So it's safe for the BPF program to keep working with r2 as valid ringbuf (and eventually submit it as well).Now this is entirely unsafe for the new state. Once
bpf_ringbuf_submit(r1)happens, r2 shouldn't be accessed anymore. But yet it will be declared safe with currentcheck_ids()logic.Ergo,
check_ids()should make sure we do not have multi-mapping for any of the IDs. Even if in some corner case that might be ok.Quoted 7 lines
I actually tested this change with veristat, there are no regressions at all. I think it's both safe from a perf standpoint, and necessary and safe from a correctness standpoint.
So all in all (I did inline
scalar_regs_exactin a separate patch, up to you), I have these changes on top and they all are good from veristat perspective:
Quoted 8 lines
Ok, rinbuf is a good example.
To minimize the patch-set I'll do the following:
- move yourcheck_idspatch to the beginning of the series
- add selftest for ringbuf
- squash thescalar_regs_exactpatch with current patch #3And resubmit with EFAULT fix in patch #1.
Thank you for looking into this.
Welp, it turns out it is not possible to create a failing example with ringbuf. This is so, because ringbuf objects are tracked in bpf_func_state::refs (of type struct bpf_reference_state).
ID of each acquired object is stored in this array and compared in func_states_equal() using refsafe() function:
static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,
struct bpf_idmap *idmap)
{
int i;
if (old->acquired_refs != cur->acquired_refs)
return false;
for (i = 0; i < old->acquired_refs; i++) {
if (!check_ids(old->refs[i].id, cur->refs[i].id, idmap))
return false;
}
return true;
}Whatever combination of old and current IDs we get in register is later checked against full list of acquired IDs.
So far I haven't been able to create a counter-example that shows the following snippet is necessary in check_ids():
+ if (map[i].cur == cur_id)
+ return false;
But this saga has to end somehow :)
I'll just squash your patches on top of patch #3, since there are not verification performance regressions.
Quoted 128 lines
Quoted 127 lines
Author: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 12:53:25 2023 -0700bpf: inline
scalar_regs_exactSigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +0
-8@@ -15262,14 +15262,6 @@ 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 (const struct bpf_reg_state *rold, -const struct bpf_reg_state *rcur, -struct bpf_idmap *idmap) -{ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); -} -/* 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, structbpf_idmap*idmap)kernel/bpf/verifier.c +5
-2@@ -15309,8 +15301,13 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) {case SCALAR_VALUE : -if (env->explore_alu_limits) -return scalar_regs_exact (rold, rcur, idmap); +if (env->explore_alu_limits) { +/* explore_alu_limits disables tnum_in() and range_within() +* logic and requires everything to be strict +*/ + return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0 &&kernel/bpf/verifier.c +2
-0+check_scalar_ids (rold->id, rcur->id, idmap); + }if (!rold->precise)return true;/* Why check_ids() for scalar registers? commit
57297c01fe747e423cd3c924ef492c0688d8057aAuthor: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 11:46:46 2023 -0700bpf: make
check_idsdisallow multi-mapping of IDs universallySigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +2
-0@@ -15137,6 +15137,8 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }if (map[i].old == old_id)return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false; }/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE(1);kernel/bpf/verifier.c +1
-19@@ -15144,33 +15146,15 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }/* 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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { -struct bpf_id_pair *map = idmap->map; -unsigned int i; - old_id = old_id ? old_id : ++idmap->tmp_id_gen; cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!map[i].old) { -/* Reached an empty slot; haven't seen this id before */ - map[i].old = old_id; - map[i].cur = cur_id; -return true; - } -if (map[i].old == old_id) -return map[i].cur == cur_id; -if (map[i].cur == cur_id) -return false; - } -/* We ran out of idmap slots, which should be impossible */ -WARN_ON_ONCE (1 ); -return false; +return check_ids (old_id, cur_id, idmap); }static void clean_func_state(struct
bpf_verifier_env*env,Quoted 15 lines
kernel/bpf/verifier.c +1
-1}/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE (1 );@@ -15246,16 +15279,24 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,static bool regs_exact (const struct bpf_reg_state *rold,const struct bpf_reg_state *rcur, -struct bpf_id_pair *idmap) +struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); }[...]
Re: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
Quoted 267 lines · Eduard Zingerman
Quoted 224 lines · Eduard Zingerman
Quoted 215 lines · Andrii Nakryiko
Quoted 173 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.Changes in this commit:
- Functioncheck_scalar_ids()is added, it differs fromcheck_ids()in the following aspects:
- treats ID zero as a unique scalar ID;
- disallows mapping same 'cur_id' to multiple 'old_id'.
-check_scalar_ids()needs to generate temporary unique IDs, field 'tmp_id_gen' is added tobpf_verifier_env::idmap_scratchto facilitate this.
- Functionscalar_regs_exact()is added, it differs fromregs_exact()in the following aspects:
- usescheck_scalar_ids()for ID comparison;
- does not checkreg_obj_idas this field is not used for scalar values.
-regsafe()is updated to:
- usecheck_scalar_ids()for precise scalar registers.
- usescalar_regs_exact()for scalar registers, but only forexplore_alu_limitsbranch. This simplifies control flow for scalar case, and has no measurable performance impact.
-check_alu_op()is updated avoid generatingbpf_reg_state::idfor constant scalar values when processingBPF_MOV. ID is needed to propagate range information for identical values, but there is nothing to propagate for constants.Fixes 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")Acked-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- include/linux/bpf_verifier.h | 17 ++++-- kernel/bpf/verifier.c | 108 ++++++++++++++++++++++++++++------- 2 files changed, 97 insertions(+), 28 deletions(-)include/linux/bpf_verifier.h +11
-6@@ -313,11 +313,6 @@ struct bpf_idx_pair {u32 idx; }; -struct bpf_id_pair { -u32 old; -u32 cur; -}; -#define MAX_CALL_FRAMES 8/* Maximum number of register states that can exist at once */ #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)@@ -559,6 +554,16 @@ struct backtrack_state {u64 stack_masks[MAX_CALL_FRAMES ]; }; +struct bpf_id_pair { +u32 old; +u32 cur; +}; + +struct bpf_idmap { +u32 tmp_id_gen; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; +}; +struct bpf_idset {u32 count;u32 ids[BPF_ID_MAP_SIZE ];@@ -596,7 +601,7 @@ struct bpf_verifier_env {struct bpf_verifier_log log;struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS +1 ];union { -struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE ]; +struct bpf_idmap idmap_scratch;struct bpf_idset idset_scratch; };struct {kernel/bpf/verifier.c +31
-8@@ -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 @@ -15122,8 +15124,9 @@ static bool range_within(struct bpf_reg_state *old,* So we look through our idmap to see if this old id has been seen before. If * so, we require the new id to match; otherwise, we add the id pair to the map. */ -static bool check_ids (u32 old_id,u32 cur_id,struct bpf_id_pair *idmap) +static bool check_ids (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { +struct bpf_id_pair *map = idmap->map;unsigned int i;/* either both IDs should be set or both should be zero */ @@ -15134,14 +15137,44 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)return true;for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!idmap[i].old) { +if (!map[i].old) {/* Reached an empty slot; haven't seen this id before */ - idmap[i].old = old_id; - idmap[i].cur = cur_id; + map[i].old = old_id; + map[i].cur = cur_id;return true; } -if (idmap[i].old == old_id) -return idmap[i].cur == cur_id; +if (map[i].old == old_id) +return map[i].cur == cur_id; + } +/* We ran out of idmap slots, which should be impossible */ +WARN_ON_ONCE (1 ); +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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) +{ +struct bpf_id_pair *map = idmap->map; +unsigned int i; + + old_id = old_id ? old_id : ++idmap->tmp_id_gen; + cur_id = cur_id ? cur_id : ++idmap->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 15177
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+if (!map[i].old) { +/* Reached an empty slot; haven't seen this id before */ + map[i].old = old_id; + map[i].cur = cur_id; +return true; + } +if (map[i].old == old_id) +return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false;We were discussing w/ Alexei (offline) making these changes as backportable and minimal as possible, so I looked again how to minimize all the extra code added.
I still insist that the current logic in
check_ids()is invalid to allow the samecur_idto map to two differentold_ids, especially for non-SCALAR, actually. E.g., a situation where we have a register that is auto-invalidated. E.g.,bpf_iterelement (each gets an ID), or it could be id'eddynptr_ringbuf.Think about the following situation:
In the old state, we could have r1.id = 1; r2.id = 2; Two registers keep two separate pointers to ringbuf.
In the new state, we have r1.id = r2.id = 3; That is, two registers keep the *same* pointer to ringbuf elem.
Now imagine that a BPF program has
bpf_ringbuf_submit(r1)and invalidates this register. With the old state it will invalidate r1 and will keep r2 valid. So it's safe for the BPF program to keep working with r2 as valid ringbuf (and eventually submit it as well).Now this is entirely unsafe for the new state. Once
bpf_ringbuf_submit(r1)happens, r2 shouldn't be accessed anymore. But yet it will be declared safe with currentcheck_ids()logic.Ergo,
check_ids()should make sure we do not have multi-mapping for any of the IDs. Even if in some corner case that might be ok.Quoted 7 lines
I actually tested this change with veristat, there are no regressions at all. I think it's both safe from a perf standpoint, and necessary and safe from a correctness standpoint.
So all in all (I did inline
scalar_regs_exactin a separate patch, up to you), I have these changes on top and they all are good from veristat perspective:Quoted 8 lines
Ok, rinbuf is a good example.
To minimize the patch-set I'll do the following:
- move yourcheck_idspatch to the beginning of the series
- add selftest for ringbuf
- squash thescalar_regs_exactpatch with current patch #3And resubmit with EFAULT fix in patch #1.
Thank you for looking into this.Welp, it turns out it is not possible to create a failing example with ringbuf. This is so, because ringbuf objects are tracked in
bpf_func_state::refs(of type structbpf_reference_state).ID of each acquired object is stored in this array and compared in
func_states_equal()usingrefsafe()function:static bool refsafe(struct
bpf_func_state*old, structbpf_func_state*cur,
structbpf_idmap*idmap){ int i; if (old->acquired_refs != cur->acquired_refs) return false; for (i = 0; i < old->acquired_refs; i++) { if (!check_ids(old->refs[i].id, cur->refs[i].id, idmap)) return false; } return true;}
Whatever combination of old and current IDs we get in register is later checked against full list of acquired IDs.
So far I haven't been able to create a counter-example that shows the following snippet is necessary in
check_ids():(quoted diff) +2
-0+ if (map[i].cur == cur_id) + return false;
Quoted 1 line
But this saga has to end somehow :)
ha-ha, yep. I think we should add this check and not rely on some side-effects of other checks for correctness.
Quoted 2 lines
I'll just squash your patches on top of patch #3, since there are not verification performance regressions.
Thanks!
Quoted 130 lines
Quoted 129 lines
Quoted 128 lines
Author: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 12:53:25 2023 -0700bpf: inline
scalar_regs_exactSigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +0
-8@@ -15262,14 +15262,6 @@ 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 (const struct bpf_reg_state *rold, -const struct bpf_reg_state *rcur, -struct bpf_idmap *idmap) -{ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && -check_scalar_ids (rold->id, rcur->id, idmap); -} -/* 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, structbpf_idmap*idmap)kernel/bpf/verifier.c +5
-2@@ -15309,8 +15301,13 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, switch (base_type(rold->type)) {case SCALAR_VALUE : -if (env->explore_alu_limits) -return scalar_regs_exact (rold, rcur, idmap); +if (env->explore_alu_limits) { +/* explore_alu_limits disables tnum_in() and range_within() +* logic and requires everything to be strict +*/ + return memcmp(rold, rcur, offsetof(struct
bpf_reg_state, id)) == 0 &&kernel/bpf/verifier.c +2
-0+check_scalar_ids (rold->id, rcur->id, idmap); + }if (!rold->precise)return true;/* Why check_ids() for scalar registers? commit
57297c01fe747e423cd3c924ef492c0688d8057aAuthor: Andrii Nakryiko <[email protected]> Date: Mon Jun 12 11:46:46 2023 -0700bpf: make
check_idsdisallow multi-mapping of IDs universallySigned-off-by Andrii Nakryiko <[email protected]>kernel/bpf/verifier.c +2
-0@@ -15137,6 +15137,8 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }if (map[i].old == old_id)return map[i].cur == cur_id; +if (map[i].cur == cur_id) +return false; }/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE(1);kernel/bpf/verifier.c +1
-19@@ -15144,33 +15146,15 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) }/* 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 (u32 old_id,u32 cur_id,struct bpf_idmap *idmap) { -struct bpf_id_pair *map = idmap->map; -unsigned int i; - old_id = old_id ? old_id : ++idmap->tmp_id_gen; cur_id = cur_id ? cur_id : ++idmap->tmp_id_gen; -for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) { -if (!map[i].old) { -/* Reached an empty slot; haven't seen this id before */ - map[i].old = old_id; - map[i].cur = cur_id; -return true; - } -if (map[i].old == old_id) -return map[i].cur == cur_id; -if (map[i].cur == cur_id) -return false; - } -/* We ran out of idmap slots, which should be impossible */ -WARN_ON_ONCE (1 ); -return false; +return check_ids (old_id, cur_id, idmap); }static void clean_func_state(struct
bpf_verifier_env*env,Quoted 15 lines
kernel/bpf/verifier.c +1
-1}/* We ran out of idmap slots, which should be impossible */ WARN_ON_ONCE (1 );@@ -15246,16 +15279,24 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,static bool regs_exact (const struct bpf_reg_state *rold,const struct bpf_reg_state *rcur, -struct bpf_id_pair *idmap) +struct bpf_idmap *idmap) {return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 &&check_ids (rold->id, rcur->id, idmap) &&check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); }[...]
kernel test robot
build botRe: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids()
In reply to Eduard Zingermankernel test robot noticed the following build warnings:
Hi Eduard,
kernel test robot noticed the following build warnings:
[auto build test WARNING on bpf-next/master]
url: https://github.com/intel-lab-lkp/linux/commits/Eduard-Zingerman/bpf-use-scalar-ids-in-mark_chain_precision/20230613-001651 base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master patch link: https://lore.kernel.org/r/20230612160801.2804666-4-eddyz87%40gmail.com patch subject: [PATCH bpf-next v5 3/4] bpf: verify scalar ids mapping in regsafe() using check_ids() config: x86_64-rhel-8.3-rust (https://download.01.org/0day-ci/archive/20230613/[email protected]/config) compiler: clang version 15.0.7 (https://github.com/llvm/llvm-project.git 8dfdcc7b7bf66834a761bd8de445840ef68e4d1a)
reproduce (this is a W=1 build):
mkdir -p ~/bin
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
git remote add bpf-next https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git
git fetch bpf-next master
git checkout bpf-next/master
b4 shazam https://lore.kernel.org/r/[email protected]
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang ~/bin/make.cross W=1 O=build_dir ARCH=x86_64 olddefconfig COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang ~/bin/make.cross W=1 O=build_dir ARCH=x86_64 SHELL=/bin/bash kernel/bpf/
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All warnings (new ones prefixed by >>):
In file included from kernel/bpf/verifier.c:7:
In file included from include/linux/bpf-cgroup.h:5:
In file included from include/linux/bpf.h:10:
In file included from include/linux/workqueue.h:9:
In file included from include/linux/timer.h:6:
In file included from include/linux/ktime.h:24:
In file included from include/linux/time.h:60:
In file included from include/linux/time32.h:13:
In file included from include/linux/timex.h:67:
In file included from arch/x86/include/asm/timex.h:5:
In file included from arch/x86/include/asm/processor.h:23:
In file included from arch/x86/include/asm/msr.h:11:
In file included from arch/x86/include/asm/cpumask.h:5:
In file included from include/linux/cpumask.h:12:
In file included from include/linux/bitmap.h:11:
In file included from include/linux/string.h:254:
>> include/linux/fortify-string.h:430:4: warning: call to __write_overflow_field declared with 'warning' attribute: detected write beyond size of field (1st parameter); maybe use struct_group()? [-Wattribute-warning]
__write_overflow_field(p_size_field, size);
^1 warning generated.
vim +/warning +430 include/linux/fortify-string.h
a28a6e860c6cf2 Francis Laniel 2021-02-25 411
28e77cc1c06866 Kees Cook 2021-06-16 412 __FORTIFY_INLINE void fortify_memset_chk(__kernel_size_t size,
28e77cc1c06866 Kees Cook 2021-06-16 413 const size_t p_size,
28e77cc1c06866 Kees Cook 2021-06-16 414 const size_t p_size_field)
a28a6e860c6cf2 Francis Laniel 2021-02-25 415 {
28e77cc1c06866 Kees Cook 2021-06-16 416 if (__builtin_constant_p(size)) {
28e77cc1c06866 Kees Cook 2021-06-16 417 /*
28e77cc1c06866 Kees Cook 2021-06-16 418 * Length argument is a constant expression, so we
28e77cc1c06866 Kees Cook 2021-06-16 419 * can perform compile-time bounds checking where
fa35198f39571b Kees Cook 2022-09-19 420 * buffer sizes are also known at compile time.
28e77cc1c06866 Kees Cook 2021-06-16 421 */
a28a6e860c6cf2 Francis Laniel 2021-02-25 422
28e77cc1c06866 Kees Cook 2021-06-16 423 /* Error when size is larger than enclosing struct. */
fa35198f39571b Kees Cook 2022-09-19 424 if (__compiletime_lessthan(p_size_field, p_size) &&
fa35198f39571b Kees Cook 2022-09-19 425 __compiletime_lessthan(p_size, size))
a28a6e860c6cf2 Francis Laniel 2021-02-25 426 __write_overflow();
28e77cc1c06866 Kees Cook 2021-06-16 427
28e77cc1c06866 Kees Cook 2021-06-16 428 /* Warn when write size is larger than dest field. */
fa35198f39571b Kees Cook 2022-09-19 429 if (__compiletime_lessthan(p_size_field, size))
28e77cc1c06866 Kees Cook 2021-06-16 @430 __write_overflow_field(p_size_field, size);
a28a6e860c6cf2 Francis Laniel 2021-02-25 431 }
28e77cc1c06866 Kees Cook 2021-06-16 432 /*
28e77cc1c06866 Kees Cook 2021-06-16 433 * At this point, length argument may not be a constant expression,
28e77cc1c06866 Kees Cook 2021-06-16 434 * so run-time bounds checking can be done where buffer sizes are
28e77cc1c06866 Kees Cook 2021-06-16 435 * known. (This is not an "else" because the above checks may only
28e77cc1c06866 Kees Cook 2021-06-16 436 * be compile-time warnings, and we want to still warn for run-time
28e77cc1c06866 Kees Cook 2021-06-16 437 * overflows.)
28e77cc1c06866 Kees Cook 2021-06-16 438 */
28e77cc1c06866 Kees Cook 2021-06-16 439
28e77cc1c06866 Kees Cook 2021-06-16 440 /*
28e77cc1c06866 Kees Cook 2021-06-16 441 * Always stop accesses beyond the struct that contains the
28e77cc1c06866 Kees Cook 2021-06-16 442 * field, when the buffer's remaining size is known.
311fb40aa0569a Kees Cook 2022-09-02 443 * (The SIZE_MAX test is to optimize away checks where the buffer
28e77cc1c06866 Kees Cook 2021-06-16 444 * lengths are unknown.)
28e77cc1c06866 Kees Cook 2021-06-16 445 */
311fb40aa0569a Kees Cook 2022-09-02 446 if (p_size != SIZE_MAX && p_size < size)
28e77cc1c06866 Kees Cook 2021-06-16 447 fortify_panic("memset");
28e77cc1c06866 Kees Cook 2021-06-16 448 }
28e77cc1c06866 Kees Cook 2021-06-16 449 Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki
Eduard Zingerman
maintainerPATCH v5 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
Re: [PATCH bpf-next v5 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe()
Quoted 62 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 thatcheck_alu_op()forBPF_MOVinstruction 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.Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/progs/verifier_scalar_ids.c | 313 ++++++++++++++++++ 1 file changed, 313 insertions(+)tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +30
-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() */
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c __naked void precision_two_ids(void) · line 383
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +10
-0+"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;"
Sorry if I'm missing some context, but there seem to be discrepancies between the code of this test, the comments right here, the comment above the test and the commit message. r6 vs r7 don't match in a few places.
The code matches the commit message and looks correct (unsafe). The code sample in the comments, however, is different and looks safe to me (r7 <= r6 <= X, accessing r9[r7]).
Quoted 278 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +273
-0+ "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
Eduard Zingerman
maintainerRe: [PATCH bpf-next v5 4/4] selftests/bpf: verify that check_ids() is used for scalars in regsafe()
Quoted 79 lines · Maxim Mikityanskiy
Quoted 62 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 thatcheck_alu_op()forBPF_MOVinstruction 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.Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/progs/verifier_scalar_ids.c | 313 ++++++++++++++++++ 1 file changed, 313 insertions(+)tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +30
-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() */tools/testing/selftests/bpf/progs/verifier_scalar_ids.c __naked void precision_two_ids(void) · line 383
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +10
-0+"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;" Sorry if I'm missing some context, but there seem to be discrepancies between the code of this test, the comments right here, the comment above the test and the commit message. r6 vs r7 don't match in a few places.
Quoted 3 lines
The code matches the commit message and looks correct (unsafe). The code sample in the comments, however, is different and looks safe to me (r7 <= r6 <= X, accessing r9[r7]).
Yep, thank you for catching this. I need top update comments. Will wait a couple of hours for other comments and re-send v6 with a fix.
Quoted 279 lines
Quoted 279 lines
tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +273
-0+ "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