[PATCH bpf-next 0/7] BPF verifier state equivalence checks improvements

[PATCH bpf-next 0/7] BPF verifier state equivalence checks improvements

[Andrii Nakryiko]

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(-)

-- 
2.30.2

[PATCH bpf-next 1/7] bpf: teach refsafe() to take into account ID remapping

[Andrii Nakryiko]

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.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index faa358b3d5d7..ab8337f6a576 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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_stat
 	if (!stacksafe(env, old, cur, env->idmap_scratch))
 		return false;
 
-	if (!refsafe(old, cur))
+	if (!refsafe(old, cur, env->idmap_scratch))
 		return false;
 
 	return true;
-- 
2.30.2

[PATCH bpf-next 2/7] bpf: reorganize struct bpf_reg_state fields

[Andrii Nakryiko]

Move 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.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 include/linux/bpf_verifier.h | 40 ++++++++++++++++++------------------
 kernel/bpf/verifier.c        | 17 ++++++++-------
 2 files changed, 28 insertions(+), 29 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 53d175cbaa02..127058cfec47 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ab8337f6a576..e419e6024251 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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);
-- 
2.30.2

[PATCH bpf-next 3/7] bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule

[Andrii Nakryiko]

Make 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.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e419e6024251..218a7ace4210 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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.
 		 */
-- 
2.30.2

[PATCH bpf-next 4/7] bpf: reject non-exact register type matches in regsafe()

[Andrii Nakryiko]

Generalize 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.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++-----------------------
 1 file changed, 21 insertions(+), 24 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 218a7ace4210..5133d0a5b0cb 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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,
-- 
2.30.2

[PATCH bpf-next 5/7] bpf: perform byte-by-byte comparison only when necessary in regsafe()

[Andrii Nakryiko]

Extract 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).

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5133d0a5b0cb..6431b994b3f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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 & REG_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,
-- 
2.30.2

[PATCH bpf-next 6/7] bpf: fix regs_exact() logic in regsafe() to remap IDs correctly

[Andrii Nakryiko]

Comparing 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%)
-------------------------------------------  --------------------------------  ---------  ---------  --------------  ----------  ----------  -------------

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6431b994b3f6..b23812d2bb49 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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);
 	}
 }
 
-- 
2.30.2

[PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

[Andrii Nakryiko]

Make 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).

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b23812d2bb49..7e0fa3924f01 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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);
 	}
 }
 
-- 
2.30.2

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

[Alexei Starovoitov]

On Thu, Dec 22, 2022 at 09:49:21PM -0800, Andrii Nakryiko wrote:
> 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.

> 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.

> 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.

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.

> 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.

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 0/7] BPF verifier state equivalence checks improvements

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

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.
> 
> 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!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

[Andrii Nakryiko]

On Tue, Dec 27, 2022 at 6:00 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Dec 22, 2022 at 09:49:21PM -0800, Andrii Nakryiko wrote:
> > 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.
>
> > 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.
>
> > 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.
>
> 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.

>
> > 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.
>
> 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().

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?

>
> SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> Keeping default as regs_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.

>
> 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.

> 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 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.

>
> 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()

[Alexei Starovoitov]

On Thu, Dec 29, 2022 at 01:59:49PM -0800, Andrii Nakryiko wrote:
> On Tue, Dec 27, 2022 at 6:00 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Thu, Dec 22, 2022 at 09:49:21PM -0800, Andrii Nakryiko wrote:
> > > 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.
> >
> > > 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.
> >
> > > 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.
> >
> > 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.
> 
> >
> > > 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.
> >
> > 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().
> 
> 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?

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.

> 
> >
> > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > Keeping default as regs_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.

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.

> 
> >
> > 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.
> 
> > 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 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.

> >
> > 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()

[Andrii Nakryiko]

On Thu, Dec 29, 2022 at 6:19 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Dec 29, 2022 at 01:59:49PM -0800, Andrii Nakryiko wrote:
> > On Tue, Dec 27, 2022 at 6:00 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Thu, Dec 22, 2022 at 09:49:21PM -0800, Andrii Nakryiko wrote:
> > > > 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.
> > >
> > > > 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.
> > >
> > > > 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.
> > >
> > > 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.
> >
> > >
> > > > 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.
> > >
> > > 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().
> >
> > 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?
>
> 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'

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.

>   // 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 :)

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).

> More gut feel than real issue.
>
> >
> > >
> > > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > > Keeping default as regs_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.
>
> 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.

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.

>
> >
> > >
> > > 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.
> >
> > > 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 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.

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).

>
> > >
> > > 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()

[Alexei Starovoitov]

On Tue, Jan 03, 2023 at 02:04:44PM -0800, Andrii Nakryiko wrote:
> > 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.

Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.

> But I probably misunderstood your example, sorry.
> 
> >   // 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 :)
> 
> 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.

> 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'.

> > More gut feel than real issue.
> >
> > >
> > > >
> > > > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > > > Keeping default as regs_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.
> >
> > 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.
> 
> 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.

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.

> 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.

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

>   - range_within() can and should be used for *precise* range of value
> tracking, but it can't express that alignment restriction.

Right.

> 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.

Right. Likely true.

> 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()

[Andrii Nakryiko]

On Wed, Jan 4, 2023 at 2:35 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Jan 03, 2023 at 02:04:44PM -0800, Andrii Nakryiko wrote:
> > > 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.
>
> 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.

>
> > But I probably misunderstood your example, sorry.
> >
> > >   // 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 :)
> >
> > 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.
>
> > 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'.

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.

>
> > > More gut feel than real issue.
> > >
> > > >
> > > > >
> > > > > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > > > > Keeping default as regs_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.
> > >
> > > 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.
> >
> > 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.
>
> Likely yes, but why?

No reason, just seems sane. But it also doesn't matter for the
discussion at hand.

> 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.

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.

>
> > 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.
>
> 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
>
> >   - range_within() can and should be used for *precise* range of value
> > tracking, but it can't express that alignment restriction.
>
> Right.
>
> > 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.
>
> Right. Likely true.
>
> > 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()

[Alexei Starovoitov]

On Wed, Jan 04, 2023 at 03:03:23PM -0800, Andrii Nakryiko wrote:
> On Wed, Jan 4, 2023 at 2:35 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Tue, Jan 03, 2023 at 02:04:44PM -0800, Andrii Nakryiko wrote:
> > > > 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.
> >
> > 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.
> 
> >
> > > But I probably misunderstood your example, sorry.
> > >
> > > >   // 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 :)
> > >
> > > 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.
> >
> > > 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'.
> 
> 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.
> 
> >
> > > > More gut feel than real issue.
> > > >
> > > > >
> > > > > >
> > > > > > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > > > > > Keeping default as regs_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.
> > > >
> > > > 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.
> > >
> > > 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.
> >
> > Likely yes, but why?
> 
> No reason, just seems sane. But it also doesn't matter for the
> discussion at hand.
> 
> > 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.
> 
> 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.

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()

[Andrii Nakryiko]

On Wed, Jan 4, 2023 at 4:14 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Wed, Jan 04, 2023 at 03:03:23PM -0800, Andrii Nakryiko wrote:
> > On Wed, Jan 4, 2023 at 2:35 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Tue, Jan 03, 2023 at 02:04:44PM -0800, Andrii Nakryiko wrote:
> > > > > 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.
> > >
> > > 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.
> >
> > >
> > > > But I probably misunderstood your example, sorry.
> > > >
> > > > >   // 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 :)
> > > >
> > > > 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.
> > >
> > > > 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'.
> >
> > 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.
> >
> > >
> > > > > More gut feel than real issue.
> > > > >
> > > > > >
> > > > > > >
> > > > > > > SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs.
> > > > > > > Keeping default as regs_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.
> > > > >
> > > > > 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.
> > > >
> > > > 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.
> > >
> > > Likely yes, but why?
> >
> > No reason, just seems sane. But it also doesn't matter for the
> > discussion at hand.
> >
> > > 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.
> >
> > 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.
>
> 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?

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.

> 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".