BPF verifier state equivalence checks improvements
Andrii Nakryiko
maintainercover BPF verifier state equivalence checks improvements
This patch set fixes, improves, and refactors parts of BPF verifier's state equivalence checks.
Patch #1 fixes refsafe(), making it take into account ID map when comparing reference IDs. See patch for details.
Patches #2-#7 refactor regsafe() function which compares two register states across old and current states. regsafe() is critical piece of logic, so to make it easier to review and validate refactorings and logic fixes and improvements, each patch makes a small change, explaining why the change is correct and makes sense. Please see individual patches for details.
This patch set is one of the preliminaries required for upcoming BPF open-coded iterators, as with open-coded iterators verifier's loop safety and completion proof is critically dependent on correct state equivalence logic.
Andrii Nakryiko (7):
bpf: teach refsafe() to take into account ID remapping
bpf: reorganize struct bpf_reg_state fields
bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule
bpf: reject non-exact register type matches in regsafe()
bpf: perform byte-by-byte comparison only when necessary in regsafe()
bpf: fix regs_exact() logic in regsafe() to remap IDs correctly
bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
include/linux/bpf_verifier.h | 40 +++++----- kernel/bpf/verifier.c | 151 +++++++++++++++++++---------------- 2 files changed, 101 insertions(+), 90 deletions(-)
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 1/7 bpf: teach refsafe() to take into account ID remapping
states_equal() check performs ID mapping between old and new states to establish a 1-to-1 correspondence between IDs, even if their absolute numberic values across two equivalent states differ. This is important both for correctness and to avoid unnecessary work when two states are equivalent.
With recent changes we partially fixed this logic by maintaining ID map across all function frames. This patch also makes refsafe() check take into account (and maintain) ID map, making states_equal() behavior more optimal and correct.
--- kernel/bpf/verifier.c | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +12 -4
@@ -13223,12 +13223,20 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,return true; } -static bool refsafe (struct bpf_func_state *old,struct bpf_func_state *cur) +static bool refsafe (struct bpf_func_state *old,struct bpf_func_state *cur, +struct bpf_id_pair *idmap) { +int i; +if (old->acquired_refs != cur->acquired_refs)return false; -return !memcmp (old->refs, cur->refs, -sizeof (*old->refs) * old->acquired_refs); + +for (i =0 ; i < old->acquired_refs; i++) { +if (!check_ids (old->refs[i].id, cur->refs[i].id, idmap)) +return false; + } + +return true; }/* compare two verifier states
@@ -13270,7 +13278,7 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_statif (!stacksafe (env, old, cur, env->idmap_scratch))return false; -if (!refsafe (old, cur)) +if (!refsafe (old, cur, env->idmap_scratch))return false;return true;
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 2/7 bpf: reorganize struct bpf_reg_state fields
In reply to Andrii NakryikoMove id and ref_obj_id fields after scalar data section (var_off and ranges). This is necessary to simplify next patch which will change regsafe()'s logic to be safer, as it makes the contents that has to be an exact match (type-specific parts, off, type, and var_off+ranges) a single sequential block of memory, while id and ref_obj_id should always be remapped and thus can't be memcp()'ed.
There are few places that assume that var_off is after id/ref_obj_id to clear out id/ref_obj_id with the single memset(0). These are changed to explicitly zero-out id/ref_obj_id fields. Other places are adjusted to preserve exact byte-by-byte comparison behavior.
No functional changes.
--- include/linux/bpf_verifier.h | 40 ++++++++++++++++++------------------ kernel/bpf/verifier.c | 17 ++++++++------- 2 files changed, 28 insertions(+), 29 deletions(-)
include/linux/bpf_verifier.h +20 -20
@@ -92,6 +92,26 @@ struct bpf_reg_state {u32 subprogno;/* for PTR_TO_FUNC */ }; +/* For scalar types (SCALAR_VALUE), this represents our knowledge of +* the actual value. +* For pointer types, this represents the variable part of the offset +* from the pointed-to object, and is shared with all bpf_reg_states +* with the same id as us. +*/ +struct tnum var_off; +/* Used to determine if any memory access using this register will +* result in a bad access. +* These refer to the same value as var_off, not necessarily the actual +* contents of the register. +*/ +s64 smin_value;/* minimum possible (s64)value */ +s64 smax_value;/* maximum possible (s64)value */ +u64 umin_value;/* minimum possible (u64)value */ +u64 umax_value;/* maximum possible (u64)value */ +s32 s32_min_value;/* minimum possible (s32)value */ +s32 s32_max_value;/* maximum possible (s32)value */ +u32 u32_min_value;/* minimum possible (u32)value */ +u32 u32_max_value;/* maximum possible (u32)value */ /* For PTR_TO_PACKET, used to find other pointers with the same variable * offset, so they can share range knowledge. * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
@@ -144,26 +164,6 @@ struct bpf_reg_state {* allowed and has the same effect as bpf_sk_release(sk). */ u32 ref_obj_id; -/* For scalar types (SCALAR_VALUE), this represents our knowledge of -* the actual value. -* For pointer types, this represents the variable part of the offset -* from the pointed-to object, and is shared with all bpf_reg_states -* with the same id as us. -*/ -struct tnum var_off; -/* Used to determine if any memory access using this register will -* result in a bad access. -* These refer to the same value as var_off, not necessarily the actual -* contents of the register. -*/ -s64 smin_value;/* minimum possible (s64)value */ -s64 smax_value;/* maximum possible (s64)value */ -u64 umin_value;/* minimum possible (u64)value */ -u64 umax_value;/* maximum possible (u64)value */ -s32 s32_min_value;/* minimum possible (s32)value */ -s32 s32_max_value;/* maximum possible (s32)value */ -u32 u32_min_value;/* minimum possible (u32)value */ -u32 u32_max_value;/* maximum possible (u32)value */ /* parentage chain for liveness checking */ struct bpf_reg_state *parent;/* Inside the callee two registers can be both PTR_TO_STACK like
kernel/bpf/verifier.c +8 -9
@@ -1402,9 +1402,11 @@ static void ___mark_reg_known(struct bpf_reg_state *reg, u64 imm)*/ static void __mark_reg_known (struct bpf_reg_state *reg,u64 imm) { -/* Clear id, off, and union(map_ptr, range) */ +/* Clear off and union(map_ptr, range) */ memset (((u8 *)reg) +sizeof (reg->type),0 , offsetof(struct bpf_reg_state , var_off) -sizeof (reg->type)); + reg->id =0 ; + reg->ref_obj_id =0 ;___mark_reg_known (reg, imm); }
@@ -1750,11 +1752,13 @@ static void __mark_reg_unknown(const struct bpf_verifier_env *env, struct bpf_reg_state *reg) {/* -* Clear type, id, off, and union(map_ptr, range) and +* Clear type, off, and union(map_ptr, range) and * padding between 'type' and union */ memset (reg,0 , offsetof(struct bpf_reg_state , var_off)); reg->type =SCALAR_VALUE ; + reg->id =0 ; + reg->ref_obj_id =0 ; reg->var_off = tnum_unknown; reg->frameno =0 ; reg->precise = !env->bpf_capable;
@@ -13104,7 +13108,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,if (type_may_be_null (rold->type)) {if (!type_may_be_null (rcur->type))return false; -if (memcmp (rold, rcur, offsetof(struct bpf_reg_state , id))) +if (memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off)))return false;/* Check our ids match any regs they're supposed to */ return check_ids (rold->id, rcur->id, idmap);
@@ -13112,13 +13116,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* If the new min/max/var_off satisfy the old ones and * everything else matches, we are OK. -* 'id' is not compared, since it's only used for maps with -* bpf_spin_lock inside map element and in such cases if -* the rest of the prog is valid for one map element then -* it's valid for all map elements regardless of the key -* used in bpf_map_lookup() */ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , id)) ==0 && +return memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off)) ==0 &&range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off) &&check_ids (rold->id, rcur->id, idmap);
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 3/7 bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule
In reply to Andrii NakryikoMake generic check to prevent XXX_OR_NULL and XXX register types to be intermixed. While technically in some situations it could be safe, it's impossible to enforce due to the loss of an ID when converting XXX_OR_NULL to its non-NULL variant. So prevent this in general, not just for PTR_TO_MAP_KEY and PTR_TO_MAP_VALUE.
PTR_TO_MAP_KEY_OR_NULL and PTR_TO_MAP_VALUE_OR_NULL checks, which were previously special-cased, are simplified to generic check that takes into account range_within() and tnum_in(). This is correct as BPF verifier doesn't allow arithmetic on XXX_OR_NULL register types, so var_off and ranges should stay zero. But even if in the future this restriction is lifted, it's even more important to enforce that var_off and ranges are compatible, otherwise it's possible to construct case where this can be exploited to bypass verifier's memory range safety checks.
--- kernel/bpf/verifier.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-)
kernel/bpf/verifier.c +15 -16
@@ -13074,6 +13074,21 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return true;if (rcur->type ==NOT_INIT )return false; + +/* Register types that are *not* MAYBE_NULL could technically be safe +* to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE is +* safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point to +* the same map). +* However, if the old MAYBE_NULL register then got NULL checked, +* doing so could have affected others with the same id, and we can't +* check for that because we lost the id when we converted to +* a non-MAYBE_NULL variant. +* So, as a general rule we don't allow mixing MAYBE_NULL and +* non-MAYBE_NULL registers. +*/ +if (type_may_be_null (rold->type) !=type_may_be_null (rcur->type)) +return false; +switch (base_type (rold->type)) {case SCALAR_VALUE :if (equal)
@@ -13098,22 +13113,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, }case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE : -/* a PTR_TO_MAP_VALUE could be safe to use as a -* PTR_TO_MAP_VALUE_OR_NULL into the same map. -* However, if the old PTR_TO_MAP_VALUE_OR_NULL then got NULL- -* checked, doing so could have affected others with the same -* id, and we can't check for that because we lost the id when -* we converted to a PTR_TO_MAP_VALUE. -*/ -if (type_may_be_null (rold->type)) { -if (!type_may_be_null (rcur->type)) -return false; -if (memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off))) -return false; -/* Check our ids match any regs they're supposed to */ -return check_ids (rold->id, rcur->id, idmap); - } -/* If the new min/max/var_off satisfy the old ones and * everything else matches, we are OK. */
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 4/7 bpf: reject non-exact register type matches in regsafe()
In reply to Andrii NakryikoGeneralize the (somewhat implicit) rule of regsafe(), which states that if register types in old and current states do not match *exactly*, they can't be safely considered equivalent.
--- kernel/bpf/verifier.c | 45 ++++++++++++++++++++----------------------- 1 file changed, 21 insertions(+), 24 deletions(-)
kernel/bpf/verifier.c +21 -24
@@ -13075,18 +13075,28 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,if (rcur->type ==NOT_INIT )return false; -/* Register types that are *not* MAYBE_NULL could technically be safe -* to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE is -* safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point to -* the same map). +/* Enforce that register types have to match exactly, including their +* modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general +* rule. +* +* One can make a point that using a pointer register as unbounded +* SCALAR would be technically acceptable, but this could lead to +* pointer leaks because scalars are allowed to leak while pointers +* are not. We could make this safe in special cases if root is +* calling us, but it's probably not worth the hassle. +* +* Also, register types that are *not* MAYBE_NULL could technically be +* safe to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE +* is safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point +* to the same map). * However, if the old MAYBE_NULL register then got NULL checked, * doing so could have affected others with the same id, and we can't * check for that because we lost the id when we converted to * a non-MAYBE_NULL variant. * So, as a general rule we don't allow mixing MAYBE_NULL and -* non-MAYBE_NULL registers. +* non-MAYBE_NULL registers as well. */ -if (type_may_be_null (rold->type) !=type_may_be_null (rcur->type)) +if (rold->type != rcur->type)return false;switch (base_type (rold->type)) {
@@ -13095,22 +13105,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,return true;if (env->explore_alu_limits)return false; -if (rcur->type ==SCALAR_VALUE ) { -if (!rold->precise) -return true; -/* new val must satisfy old val knowledge */ -return range_within (rold, rcur) && -tnum_in (rold->var_off, rcur->var_off); - }else { -/* We're trying to use a pointer in place of a scalar. -* Even if the scalar was unbounded, this could lead to -* pointer leaks because scalars are allowed to leak -* while pointers are not. We could make this safe in -* special cases if root is calling us, but it's -* probably not worth the hassle. -*/ -return false; - } +if (!rold->precise) +return true; +/* new val must satisfy old val knowledge */ +return range_within (rold, rcur) && +tnum_in (rold->var_off, rcur->var_off);case PTR_TO_MAP_KEY :case PTR_TO_MAP_VALUE :/* If the new min/max/var_off satisfy the old ones and
@@ -13122,8 +13121,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,check_ids (rold->id, rcur->id, idmap);case PTR_TO_PACKET_META :case PTR_TO_PACKET : -if (rcur->type != rold->type) -return false;/* We must have at least as much range as the old ptr * did, so that any accesses which were safe before are * still safe. This is true even if old range < old off,
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 5/7 bpf: perform byte-by-byte comparison only when necessary in regsafe()
In reply to Andrii NakryikoExtract byte-by-byte comparison of bpf_reg_state in regsafe() into a helper function, which makes it more convenient to use it "on demand" only for registers that benefit from such checks, instead of doing it all the time, even if result of such comparison is ignored.
Also, remove WARN_ON_ONCE(1)+return false dead code. There is no risk of missing some case as compiler will warn about non-void function not returning value in some branches (and that under assumption that default case is removed in the future).
--- kernel/bpf/verifier.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +9 -12
@@ -13057,18 +13057,19 @@ 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) +{ +return memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; +} +/* Returns true if (rold safe implies rcur safe) */ static bool regsafe (struct bpf_verifier_env *env,struct bpf_reg_state *rold,struct bpf_reg_state *rcur,struct bpf_id_pair *idmap) { -bool equal; -if (!(rold->live ®_LIVE_READ ))/* explored state didn't use this */ return true; - - equal =memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; -if (rold->type ==NOT_INIT )/* explored state can't have used this */ return true;
@@ -13101,7 +13102,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : -if (equal) +if (regs_exact (rold, rcur))return true;if (env->explore_alu_limits)return false;
@@ -13144,15 +13145,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* two stack pointers are equal only if they're pointing to * the same stack frame, since fp-8 in foo != fp-8 in bar */ -return equal && rold->frameno == rcur->frameno; +return regs_exact (rold, rcur) && rold->frameno == rcur->frameno;default :/* Only valid matches are exact, which memcmp() */ -return equal; +return regs_exact (rold, rcur); } - -/* Shouldn't get here; if we do, say it's not safe */ -WARN_ON_ONCE (1 ); -return false; } static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 6/7 bpf: fix regs_exact() logic in regsafe() to remap IDs correctly
In reply to Andrii NakryikoComparing IDs exactly between two separate states is not just suboptimal, but also incorrect in some cases. So update regs_exact() check to do byte-by-byte memcmp() only up to id/ref_obj_id. For id and ref_obj_id perform proper check_ids() checks, taking into account idmap.
This change makes more states equivalent improving insns and states stats across a bunch of selftest BPF programs:
File Program Insns (A) Insns (B) Insns (DIFF) States (A) States (B) States (DIFF) ------------------------------------------- -------------------------------- --------- --------- -------------- ---------- ---------- ------------- cgrp_kfunc_success.bpf.linked1.o test_cgrp_get_release 141 137 -4 (-2.84%) 13 13 +0 (+0.00%) cgrp_kfunc_success.bpf.linked1.o test_cgrp_xchg_release 142 139 -3 (-2.11%) 14 13 -1 (-7.14%) connect6_prog.bpf.linked1.o connect_v6_prog 139 102 -37 (-26.62%) 9 6 -3 (-33.33%) ima.bpf.linked1.o bprm_creds_for_exec 68 61 -7 (-10.29%) 6 5 -1 (-16.67%) linked_list.bpf.linked1.o global_list_in_list 569 499 -70 (-12.30%) 60 52 -8 (-13.33%) linked_list.bpf.linked1.o global_list_push_pop 167 150 -17 (-10.18%) 18 16 -2 (-11.11%) linked_list.bpf.linked1.o global_list_push_pop_multiple 881 815 -66 (-7.49%) 74 63 -11 (-14.86%) linked_list.bpf.linked1.o inner_map_list_in_list 579 534 -45 (-7.77%) 61 55 -6 (-9.84%) linked_list.bpf.linked1.o inner_map_list_push_pop 190 181 -9 (-4.74%) 19 18 -1 (-5.26%) linked_list.bpf.linked1.o inner_map_list_push_pop_multiple 916 850 -66 (-7.21%) 75 64 -11 (-14.67%) linked_list.bpf.linked1.o map_list_in_list 588 525 -63 (-10.71%) 62 55 -7 (-11.29%) linked_list.bpf.linked1.o map_list_push_pop 183 174 -9 (-4.92%) 18 17 -1 (-5.56%) linked_list.bpf.linked1.o map_list_push_pop_multiple 909 843 -66 (-7.26%) 75 64 -11 (-14.67%) map_kptr.bpf.linked1.o test_map_kptr 264 256 -8 (-3.03%) 26 26 +0 (+0.00%) map_kptr.bpf.linked1.o test_map_kptr_ref 95 91 -4 (-4.21%) 9 8 -1 (-11.11%) task_kfunc_success.bpf.linked1.o test_task_xchg_release 139 136 -3 (-2.16%) 14 13 -1 (-7.14%) test_bpf_nf.bpf.linked1.o nf_skb_ct_test 815 509 -306 (-37.55%) 57 30 -27 (-47.37%) test_bpf_nf.bpf.linked1.o nf_xdp_ct_test 815 509 -306 (-37.55%) 57 30 -27 (-47.37%) test_cls_redirect.bpf.linked1.o cls_redirect 78925 78390 -535 (-0.68%) 4782 4704 -78 (-1.63%) test_cls_redirect_subprogs.bpf.linked1.o cls_redirect 64901 63897 -1004 (-1.55%) 4612 4470 -142 (-3.08%) test_sk_lookup.bpf.linked1.o access_ctx_sk 181 95 -86 (-47.51%) 19 10 -9 (-47.37%) test_sk_lookup.bpf.linked1.o ctx_narrow_access 447 437 -10 (-2.24%) 38 37 -1 (-2.63%) test_sk_lookup_kern.bpf.linked1.o sk_lookup_success 148 133 -15 (-10.14%) 14 12 -2 (-14.29%) test_tcp_check_syncookie_kern.bpf.linked1.o check_syncookie_clsact 304 300 -4 (-1.32%) 23 22 -1 (-4.35%) test_tcp_check_syncookie_kern.bpf.linked1.o check_syncookie_xdp 304 300 -4 (-1.32%) 23 22 -1 (-4.35%) test_verify_pkcs7_sig.bpf.linked1.o bpf 87 76 -11 (-12.64%) 7 6 -1 (-14.29%) ------------------------------------------- -------------------------------- --------- --------- -------------- ---------- ---------- -------------
--- kernel/bpf/verifier.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-)
kernel/bpf/verifier.c +16 -7
@@ -12946,6 +12946,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap) {unsigned int i; +/* either both IDs should be set or both should be zero */ +if (!!old_id != !!cur_id) +return false; + +if (old_id ==0 )/* cur_id == 0 as well */ +return true; +for (i =0 ; i <BPF_ID_MAP_SIZE ; i++) {if (!idmap[i].old) {/* Reached an empty slot; haven't seen this id before */
@@ -13058,9 +13065,12 @@ 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) +const struct bpf_reg_state *rcur, +struct bpf_id_pair *idmap) { -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , parent)) ==0 ; +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); }/* Returns true if (rold safe implies rcur safe) */
@@ -13102,7 +13112,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,switch (base_type (rold->type)) {case SCALAR_VALUE : -if (regs_exact (rold, rcur)) +if (regs_exact (rold, rcur, idmap))return true;if (env->explore_alu_limits)return false;
@@ -13136,7 +13146,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,if (rold->off != rcur->off)return false;/* id relations must be preserved */ -if (rold->id && !check_ids (rold->id, rcur->id, idmap)) +if (!check_ids (rold->id, rcur->id, idmap))return false;/* new val must satisfy old val knowledge */ return range_within(rold, rcur) &&
@@ -13145,10 +13155,9 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* two stack pointers are equal only if they're pointing to * the same stack frame, since fp-8 in foo != fp-8 in bar */ -return regs_exact (rold, rcur) && rold->frameno == rcur->frameno; +return regs_exact (rold, rcur, idmap) && rold->frameno == rcur->frameno;default : -/* Only valid matches are exact, which memcmp() */ -return regs_exact (rold, rcur); +return regs_exact (rold, rcur, idmap); } }
Signature · 1 line
2.30.2
Andrii Nakryiko
maintainerPATCH 7/7 bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
In reply to Andrii NakryikoMake default case in regsafe() safer. Instead of doing byte-by-byte comparison, take into account ID remapping and also range and var_off checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.
With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.
With these changes veristat shows no difference in verifier stats across selftests and Cilium BPF programs (which is a good thing).
--- kernel/bpf/verifier.c | 26 ++++++++++++++------------ 1 file changed, 14 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +14 -12
@@ -12919,8 +12919,8 @@ static int check_btf_info(struct bpf_verifier_env *env, }/* check %cur's range satisfies %old's */ -static bool range_within (struct bpf_reg_state *old, -struct bpf_reg_state *cur) +static bool range_within (const struct bpf_reg_state *old, +const struct bpf_reg_state *cur) {return old->umin_value <= cur->umin_value && old->umax_value >= cur->umax_value &&
@@ -13073,6 +13073,17 @@ static bool regs_exact(const struct bpf_reg_state *rold,check_ids (rold->ref_obj_id, rcur->ref_obj_id, idmap); } +static bool regs_equal (const struct bpf_reg_state *rold, +const struct bpf_reg_state *rcur, +struct bpf_id_pair *idmap) +{ +return memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off)) ==0 && +range_within (rold, rcur) && +tnum_in (rold->var_off, rcur->var_off) && +check_ids (rold->id, rcur->id, idmap) && +check_ids (rold->ref_obj_id, rcur->ref_obj_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_id_pair *idmap)
@@ -13121,15 +13132,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,/* new val must satisfy old val knowledge */ return range_within (rold, rcur) &&tnum_in (rold->var_off, rcur->var_off); -case PTR_TO_MAP_KEY : -case PTR_TO_MAP_VALUE : -/* If the new min/max/var_off satisfy the old ones and -* everything else matches, we are OK. -*/ -return memcmp (rold, rcur, offsetof(struct bpf_reg_state , var_off)) ==0 && -range_within (rold, rcur) && -tnum_in (rold->var_off, rcur->var_off) && -check_ids (rold->id, rcur->id, idmap);case PTR_TO_PACKET_META :case PTR_TO_PACKET :/* We must have at least as much range as the old ptr
@@ -13157,7 +13159,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,*/ return regs_exact (rold, rcur, idmap) && rold->frameno == rcur->frameno;default : -return regs_exact (rold, rcur, idmap); +return regs_equal (rold, rcur, idmap); } }
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 1 line · Andrii Nakryiko
Make default case in
regsafe()safer. Instead of doing byte-by-byte
I love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.
Quoted 1 line
comparison, take into account ID remapping and also range and
var_off
ID remapping is handled by the patch 6 in regs_exact(). This patch adds range and var_off check as default. Which might not be correct in the future.
Quoted 5 lines
checks. For most of registers range and
var_offwill be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching whatregsafe()was doing as a special case. But in any case, if register has id and/orref_obj_idset, check it usingcheck_ids()logic, taking into account idmap.
That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.
Quoted 5 lines
With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like
PTR_TO_PACKET, one would still need to implement extra checks (like special handling ofreg->range) to get better state equivalence, but default logic shouldn't be wrong.
PTR_TO_BTF_ID with var_off would be a counter example where
such default of comparing ranges and var_off would lead to issues. Currently PTR_TO_BTF_ID doesn't allow var_off, but folks requested this support. The range_within() logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes. PTR_TO_BTF_ID with var_off would be wrong to do with just range_within().
SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.
Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.
I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR, PTR_TO_BTF_ID and PTR_TO_MAP will be the majority of types we can special case them and refactor comparison to only things
that matter to these types. var_off and min/max_value are the biggest part of bpf_reg_state. They should be zero for PTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottest regsafe() function.
Same thing for SCALAR. Doing regs_exact() with big memcmp and then finer range_within() on the same bytes is probably wasteful and can be optimized.
We might consider reshuffling bpf_reg_state fields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.
I've applied the first 6 patches.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko
Make default case in
regsafe()safer. Instead of doing byte-by-byteI love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.Quoted 1 line
comparison, take into account ID remapping and also range and
var_offID remapping is handled by the patch 6 in
regs_exact(). This patch adds range andvar_offcheck as default. Which might not be correct in the future.
Quoted 8 lines
Quoted 5 lines
checks. For most of registers range and
var_offwill be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching whatregsafe()was doing as a special case. But in any case, if register has id and/orref_obj_idset, check it usingcheck_ids()logic, taking into account idmap.That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.
True, I think I had regs_exact() and regs_equals() change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.
Quoted 7 lines
Quoted 6 lines
With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like
PTR_TO_PACKET, one would still need to implement extra checks (like special handling ofreg->range) to get better state equivalence, but default logic shouldn't be wrong.
Quoted 6 lines
PTR_TO_BTF_IDwithvar_offwould be a counter example where
such default of comparing ranges andvar_offwould lead to issues. CurrentlyPTR_TO_BTF_IDdoesn't allowvar_off, but folks requested this support. Therange_within()logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes.PTR_TO_BTF_IDwithvar_offwould be wrong to do with justrange_within().
I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined var_off and range_within() would be incorrect.
Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?
Quoted 3 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.
It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.
Quoted 5 lines
Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.
yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.
Quoted 4 lines
I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR,
PTR_TO_BTF_IDandPTR_TO_MAPwill be the majority of types we can special case them and refactor comparison to only things
that matter to these types.var_offand min/max_value are the biggest part
Quoted 8 lines
of
bpf_reg_state. They should be zero forPTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottestregsafe()function.
Same thing for SCALAR. Doingregs_exact()with big memcmp and then finerrange_within()on the same bytes is probably wasteful and can be optimized.
We might consider reshufflingbpf_reg_statefields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.
I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.
Quoted 2 lines
I've applied the first 6 patches.
Cool, thanks, less patches to carry around. If you don't mind, let's look at this var_off concern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 49 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko
Make default case in
regsafe()safer. Instead of doing byte-by-byteI love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.Quoted 1 line
comparison, take into account ID remapping and also range and
var_offID remapping is handled by the patch 6 in
regs_exact(). This patch adds range andvar_offcheck as default. Which might not be correct in the future.Quoted 8 lines
Quoted 5 lines
checks. For most of registers range and
var_offwill be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching whatregsafe()was doing as a special case. But in any case, if register has id and/orref_obj_idset, check it usingcheck_ids()logic, taking into account idmap.That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.
True, I think I had
regs_exact()andregs_equals()change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.Quoted 7 lines
Quoted 6 lines
With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like
PTR_TO_PACKET, one would still need to implement extra checks (like special handling ofreg->range) to get better state equivalence, but default logic shouldn't be wrong.Quoted 6 lines
PTR_TO_BTF_IDwithvar_offwould be a counter example where
such default of comparing ranges andvar_offwould lead to issues. CurrentlyPTR_TO_BTF_IDdoesn't allowvar_off, but folks requested this support. Therange_within()logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes.PTR_TO_BTF_IDwithvar_offwould be wrong to do with justrange_within().I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined
var_offandrange_within()would be incorrect.
Quoted 5 lines
Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?
Kumar's example was for a constant. range_within is the same as equality check, so we concluded it's safe for that case.
I'm worried about non uniformity of structs with types and general comparison of ranges.
I guess you're arguing that if old state had wider range than every single possible value from that range was already validated to be safe and hence new narrow range is safe too.
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'
// branch taken kicks in
else
// issues that were never checked
Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)
Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.
PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.
Quoted 24 lines
Quoted 6 lines
Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.
Quoted 4 lines
I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR,
PTR_TO_BTF_IDandPTR_TO_MAPwill be the majority of types we can special case them and refactor comparison to only things
that matter to these types.var_offand min/max_value are the biggest partQuoted 8 lines
of
bpf_reg_state. They should be zero forPTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottestregsafe()function.
Same thing for SCALAR. Doingregs_exact()with big memcmp and then finerrange_within()on the same bytes is probably wasteful and can be optimized.
We might consider reshufflingbpf_reg_statefields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.
Quoted 7 lines
I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.
Thank you. Lorenz was pondering at it at some point, but lost interest. I guess. I did a bunch of perf runs with our test_verif_scale* long ago.
The perf report used to be the same and stable for them. processed_insn and number of states affects both memory and speed and % wise have higher contribution to verifier speed, so any improvements there help more. Optimizing the actual regsafe() is secondary.
Just something to put on todo list.
Quoted 8 lines
Quoted 2 lines
I've applied the first 6 patches.
Cool, thanks, less patches to carry around. If you don't mind, let's look at this
var_offconcern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 57 lines · Alexei Starovoitov
Quoted 49 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko
Make default case in
regsafe()safer. Instead of doing byte-by-byteI love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.Quoted 1 line
comparison, take into account ID remapping and also range and
var_offID remapping is handled by the patch 6 in
regs_exact(). This patch adds range andvar_offcheck as default. Which might not be correct in the future.Quoted 8 lines
Quoted 5 lines
checks. For most of registers range and
var_offwill be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching whatregsafe()was doing as a special case. But in any case, if register has id and/orref_obj_idset, check it usingcheck_ids()logic, taking into account idmap.That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.
True, I think I had
regs_exact()andregs_equals()change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.Quoted 7 lines
Quoted 6 lines
With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like
PTR_TO_PACKET, one would still need to implement extra checks (like special handling ofreg->range) to get better state equivalence, but default logic shouldn't be wrong.Quoted 6 lines
PTR_TO_BTF_IDwithvar_offwould be a counter example where
such default of comparing ranges andvar_offwould lead to issues. CurrentlyPTR_TO_BTF_IDdoesn't allowvar_off, but folks requested this support. Therange_within()logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes.PTR_TO_BTF_IDwithvar_offwould be wrong to do with justrange_within().I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined
var_offandrange_within()would be incorrect.Quoted 5 lines
Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?
Quoted 11 lines
Kumar's example was for a constant.
range_withinis the same as equality check, so we concluded it's safe for that case.
I'm worried about non uniformity of structs with types and general comparison of ranges.
I guess you're arguing that if old state had wider range than every single possible value from that range was already validated to be safe and hence new narrow range is safe too.
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'
a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.
But I probably misunderstood your example, sorry.
Quoted 11 lines
// branch taken kicks in
else
// issues that were never checkedNow new state has:
R1=(min=4,max=6), R2=(min=5, max=5)Both R1 and R2 of new state individually
range_withinof old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)
No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.
So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).
Quoted 13 lines
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.
Quoted 4 lines
PTR_TO_MEMandPTR_TO_BUFexplicitly are likely ok despite my convoluted example above.
I'm less sure aboutPTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.
Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.
For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.
But just to take a step back, from my perspective var_off and range_within are complementary and solve slightly different uses, but should be both satisfied:
- var_off is not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.
- range_within() can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.
So while I previously thought that we can do away without var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possible var_off + range_within situation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.
Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.
Quoted 33 lines
Quoted 25 lines
Quoted 7 lines
Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.
Quoted 4 lines
I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR,
PTR_TO_BTF_IDandPTR_TO_MAPwill be the majority of types we can special case them and refactor comparison to only things
that matter to these types.var_offand min/max_value are the biggest partQuoted 8 lines
of
bpf_reg_state. They should be zero forPTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottestregsafe()function.
Same thing for SCALAR. Doingregs_exact()with big memcmp and then finerrange_within()on the same bytes is probably wasteful and can be optimized.
We might consider reshufflingbpf_reg_statefields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.Quoted 7 lines
I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.
Quoted 7 lines
Thank you. Lorenz was pondering at it at some point, but lost interest. I guess. I did a bunch of perf runs with our test_verif_scale* long ago.
The perf report used to be the same and stable for them.processed_insnand number of states affects both memory and speed and % wise have higher contribution to verifier speed, so any improvements there help more. Optimizing the actualregsafe()is secondary.
Just something to put on todo list.
Sure. With veristat we can also have a more aggregated view across multiple object files (and we can add some mode to veristat to repeatedly load each program for N times to help with profile collection).
Quoted 9 lines
Quoted 9 lines
Quoted 3 lines
I've applied the first 6 patches.
Cool, thanks, less patches to carry around. If you don't mind, let's look at this
var_offconcern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of
R1 < R2checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.
Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.
Quoted 14 lines
But I probably misunderstood your example, sorry.
Quoted 11 lines
// branch taken kicks in
else
// issues that were never checkedNow new state has:
R1=(min=4,max=6), R2=(min=5, max=5)Both R1 and R2 of new state individually
range_withinof old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)
Quoted 6 lines
No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.
Correct. The issue would apply to regular scalar if such 'within' operation was available.
Quoted 4 lines
So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).
Yes. I personally don't believe that doing range_within for all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example with range_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.
Quoted 18 lines
Quoted 13 lines
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.Quoted 4 lines
PTR_TO_MEMandPTR_TO_BUFexplicitly are likely ok despite my convoluted example above.
I'm less sure aboutPTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.
Quoted 7 lines
Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.
For
PTR_TO_BTF_IDspecifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.
Likely yes, but why?
You're trying hard to collapse the switch statement in regsafe() while claiming it's a safer way. I don't see it this way.
For example the upcoming active_lock_id would need its own check_ids() call. It will be necessary for PTR_TO_BTF_ID only.
Why collapse the switch into 'default:' just to bring some back? The default without checking active_lock_id through check_ids would be wrong, so collapsed switch doesn't make things safer.
Quoted 10 lines
But just to take a step back, from my perspective
var_offandrange_withinare complementary and solve slightly different uses, but should be both satisfied:
-var_offis not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.
Right. var_off is used for alignment checking too. grep tnum_is_aligned. We have bare minimum of testing for that though.
Only few tests in the test_verifier use BPF_F_STRICT_ALIGNMENT
Quoted 2 lines
-
range_within()can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.
Right.
Quoted 6 lines
So while I previously thought that we can do away without
var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possiblevar_off+range_withinsituation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.
Right. Likely true.
Quoted 2 lines
Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.
Not sure what conclusion you're looking for.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of
R1 < R2checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.
Quoted 2 lines
Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.
I just don't know what kind of instruction has this "within" semantics, that's why I was confused.
Quoted 30 lines
Quoted 15 lines
But I probably misunderstood your example, sorry.
Quoted 11 lines
// branch taken kicks in
else
// issues that were never checkedNow new state has:
R1=(min=4,max=6), R2=(min=5, max=5)Both R1 and R2 of new state individually
range_withinof old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)Quoted 6 lines
No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.
Correct. The issue would apply to regular scalar if such 'within' operation was available.
Quoted 4 lines
So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).
Quoted 6 lines
Yes. I personally don't believe that doing
range_withinfor all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example withrange_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.
Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.
Quoted 22 lines
Quoted 22 lines
Quoted 14 lines
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.Quoted 4 lines
PTR_TO_MEMandPTR_TO_BUFexplicitly are likely ok despite my convoluted example above.
I'm less sure aboutPTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.
Quoted 6 lines
Quoted 4 lines
For
PTR_TO_BTF_IDspecifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.Likely yes, but why?
No reason, just seems sane. But it also doesn't matter for the discussion at hand.
Quoted 7 lines
You're trying hard to collapse the switch statement in
regsafe()while claiming it's a safer way. I don't see it this way.
For example the upcomingactive_lock_idwould need its owncheck_ids()call. It will be necessary forPTR_TO_BTF_IDonly.
Why collapse the switch into 'default:' just to bring some back? The default without checkingactive_lock_idthroughcheck_idswould be wrong, so collapsed switch doesn't make things safer.
I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like PTR_TO_MEM and PTR_TO_BUF in the future.
Your point is that some register will need a custom/extra check is correct, obviously (just like we have PTR_TO_STACK extra frameno check), and doesn't contradict what I'm saying. We still need to be careful for new register types or further changes to existing ones.
Quoted 28 lines
Quoted 11 lines
But just to take a step back, from my perspective
var_offandrange_withinare complementary and solve slightly different uses, but should be both satisfied:
-var_offis not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.Right.
var_offis used for alignment checking too. greptnum_is_aligned. We have bare minimum of testing for that though.
Only few tests in thetest_verifieruseBPF_F_STRICT_ALIGNMENTQuoted 2 lines
-
range_within()can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.Right.
Quoted 6 lines
So while I previously thought that we can do away without
var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possiblevar_off+range_withinsituation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.
Quoted 6 lines
Right. Likely true.
Quoted 2 lines
Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.
Not sure what conclusion you're looking for.
Seeing if I'm missing something. Now I don't think I am. That's the conclusion I was looking for.
We don't have to make the default case do range_within(), I'll just explicitly add PTR_TO_MEM and PTR_TO_BUF into PTR_TO_MAP_{VALUE,KEY} case in a future patch set.
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 103 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of
R1 < R2checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.Quoted 2 lines
Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.I just don't know what kind of instruction has this "within" semantics, that's why I was confused.
Quoted 30 lines
Quoted 15 lines
But I probably misunderstood your example, sorry.
Quoted 11 lines
// branch taken kicks in
else
// issues that were never checkedNow new state has:
R1=(min=4,max=6), R2=(min=5, max=5)Both R1 and R2 of new state individually
range_withinof old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)Quoted 6 lines
No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.
Correct. The issue would apply to regular scalar if such 'within' operation was available.
Quoted 4 lines
So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).
Quoted 6 lines
Yes. I personally don't believe that doing
range_withinfor all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example withrange_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.
Quoted 22 lines
Quoted 22 lines
Quoted 14 lines
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.Quoted 4 lines
PTR_TO_MEMandPTR_TO_BUFexplicitly are likely ok despite my convoluted example above.
I'm less sure aboutPTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.
Quoted 6 lines
Quoted 4 lines
For
PTR_TO_BTF_IDspecifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.Likely yes, but why?
No reason, just seems sane. But it also doesn't matter for the discussion at hand.
Quoted 7 lines
You're trying hard to collapse the switch statement in
regsafe()while claiming it's a safer way. I don't see it this way.
For example the upcomingactive_lock_idwould need its owncheck_ids()call. It will be necessary forPTR_TO_BTF_IDonly.
Why collapse the switch into 'default:' just to bring some back? The default without checkingactive_lock_idthroughcheck_idswould be wrong, so collapsed switch doesn't make things safer.
Quoted 4 lines
I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like
PTR_TO_MEMandPTR_TO_BUFin the future.
Wait. What do you mean 'miss cases like PTR_TO_MEM' ?
With 'switch() default: regs_exact()'
it's not a safety issue that PTR_TO_MEM doesn't do range_within() like PTR_TO_MAP_KEY. The verifier is unnecessary conservative with PTR_TO_MEM.
Applying range_within() will allow more valid programs to be accepted. What did I miss?
Or all this time I've been misreading your 'saner' default as 'safer' default?
Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()
Quoted 110 lines · Alexei Starovoitov
Quoted 103 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of
R1 < R2checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.Quoted 2 lines
Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.I just don't know what kind of instruction has this "within" semantics, that's why I was confused.
Quoted 30 lines
Quoted 15 lines
But I probably misunderstood your example, sorry.
Quoted 11 lines
// branch taken kicks in
else
// issues that were never checkedNow new state has:
R1=(min=4,max=6), R2=(min=5, max=5)Both R1 and R2 of new state individually
range_withinof old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)Quoted 6 lines
No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.
Correct. The issue would apply to regular scalar if such 'within' operation was available.
Quoted 4 lines
So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).
Quoted 6 lines
Yes. I personally don't believe that doing
range_withinfor all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example withrange_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.
Quoted 22 lines
Quoted 22 lines
Quoted 14 lines
More gut feel than real issue.
Quoted 10 lines
Quoted 4 lines
SCALARS and
PTR_TO_BTF_IDwill likely dominate future bpf progs. Keeping default asregs_exact(that does ID match) is safer default.It's fine, though the point of this patch set was patch #7, enabling logic similar to
PTR_TO_MAP_VALUEforPTR_TO_MEMandPTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.Quoted 4 lines
PTR_TO_MEMandPTR_TO_BUFexplicitly are likely ok despite my convoluted example above.
I'm less sure aboutPTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.
Quoted 6 lines
Quoted 4 lines
For
PTR_TO_BTF_IDspecifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.Likely yes, but why?
No reason, just seems sane. But it also doesn't matter for the discussion at hand.
Quoted 7 lines
You're trying hard to collapse the switch statement in
regsafe()while claiming it's a safer way. I don't see it this way.
For example the upcomingactive_lock_idwould need its owncheck_ids()call. It will be necessary forPTR_TO_BTF_IDonly.
Why collapse the switch into 'default:' just to bring some back? The default without checkingactive_lock_idthroughcheck_idswould be wrong, so collapsed switch doesn't make things safer.Quoted 4 lines
I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like
PTR_TO_MEMandPTR_TO_BUFin the future.
Quoted 6 lines
Wait. What do you mean 'miss cases like
PTR_TO_MEM' ?
With 'switch()default:regs_exact()'
it's not a safety issue thatPTR_TO_MEMdoesn't dorange_within()likePTR_TO_MAP_KEY. The verifier is unnecessary conservative withPTR_TO_MEM.
Applyingrange_within()will allow more valid programs to be accepted. What did I miss?
I don't think you missed anything. This was all exactly to allow the verifier to see that two PTR_TO_MEM (and PTR_TO_BUF, and whatnot) registers are compatible, even if their ranges are not exactly matching. This is just an inefficiency in state comparison right now (and potentially missed infinite loop detection, but that's also just inefficiency), but it becomes an issue with open-coded iterators because state equivalence is necessary to conclude that loop actually terminates safely.
Quoted 1 line
Or all this time I've been misreading your 'saner' default as 'safer' default?
I meant "saner" (with 'n') as "better and more flexible without
compromising safety".
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 6 lines · On Thu, 22 Dec 2022 21:49:14 -0800 you wrote:
This patch set fixes, improves, and refactors parts of BPF verifier's state equivalence checks.
Patch #1 fixes
refsafe(), making it take into account ID map when comparing reference IDs. See patch for details.
Quoted 7 lines
Patches #2-#7 refactor
regsafe()function which compares two register states across old and current states.regsafe()is critical piece of logic, so to make it easier to review and validate refactorings and logic fixes and improvements, each patch makes a small change, explaining why the change is correct and makes sense. Please see individual patches for details.[...]
Here is the summary with links:
- [bpf-next,1/7] bpf: teach refsafe() to take into account ID remapping
https://git.kernel.org/bpf/bpf-next/c/e8f55fcf7779 - [bpf-next,2/7] bpf: reorganize struct bpf_reg_state fields https://git.kernel.org/bpf/bpf-next/c/a73bf9f2d969 - [bpf-next,3/7] bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule https://git.kernel.org/bpf/bpf-next/c/7f4ce97cd5ed - [bpf-next,4/7] bpf: reject non-exact register type matches in regsafe() https://git.kernel.org/bpf/bpf-next/c/910f69996674 - [bpf-next,5/7] bpf: perform byte-by-byte comparison only when necessary in regsafe() https://git.kernel.org/bpf/bpf-next/c/4a95c85c9948 - [bpf-next,6/7] bpf: fix regs_exact() logic in regsafe() to remap IDs correctly https://git.kernel.org/bpf/bpf-next/c/4633a0068258
- [bpf-next,7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe() (no matching commit)
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html