[PATCH bpf-next v2 1/1] bpf: Simplify checking size of helper accesses

[Andrei Matei <andreimatei1@gmail.com>]

This patch simplifies the verification of size arguments associated to
pointer arguments to helpers and kfuncs. Many helpers take a pointer
argument followed by the size of the memory access performed to be
performed through that pointer. Before this patch, the handling of the
size argument in check_mem_size_reg() was confusing and wasteful: if the
size register's lower bound was 0, then the verification was done twice:
once considering the size of the access to be the lower-bound of the
respective argument, and once considering the upper bound (even if the
two are the same). The upper bound checking is a super-set of the
lower-bound checking(*), except: the only point of the lower-bound check
is to handle the case where zero-sized-accesses are explicitly not
allowed and the lower-bound is zero. This static condition is now
checked explicitly, replacing a much more complex, expensive and
confusing verification call to check_helper_mem_access().

Now that check_mem_size_reg() deals directly with the zero_size_allowed
checking, the single remaining call to check_helper_mem_access() can
pass a static value for the zero_size_allowed arg, instead of
propagating a dynamic one. I think this is an improvement, as tracking
the wide propagation of zero_sized_allowed is already complicated.

This patch also results in better error messages for rejected zero-size
reads. Before, the message one would get depended on the type of the
pointer and on other conditions, and sometimes the message was plain
wrong: in some tests that changed you'll see that the old message was
something like "R1 min value is outside of the allowed memory range",
where R1 is the pointer register; the error was wrongly claiming that
the pointer was bad instead of the size being bad. Other times the
information that the size came for a register with a possible range of
values was wrong, and the error presented the size as a fixed zero.

(*) Besides standing to reason that the checks for a bigger size access
are a super-set of the checks for a smaller size access, I have also
mechanically verified this by reading the code for all types of
pointers. I could convince myself that it's true for all but
PTR_TO_BTF_ID (check_ptr_to_btf_access). There, simply looking
line-by-line does not immediately prove what we want. If anyone has any
qualms, let me know.

Signed-off-by: Andrei Matei <andreimatei1@gmail.com>
---
 kernel/bpf/verifier.c                         | 85 +++++++++++++++++--
 .../bpf/progs/verifier_helper_value_access.c  | 45 +++++++++-
 .../selftests/bpf/progs/verifier_raw_stack.c  |  4 +-
 3 files changed, 120 insertions(+), 14 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1863826a4ac3..cf2a09408bdc 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7256,6 +7256,65 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
 	}
 }
 
+/* Helper function for logging an error about an invalid attempt to perform a
+ * (possibly) zero-sized memory access. The pointer being dereferenced is in
+ * register @ptr_regno, and the size of the access is in register @size_regno.
+ * The size register is assumed to either be a constant zero or have a zero lower
+ * bound.
+ *
+ * Logs a message like:
+ * invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48
+ */
+static void log_zero_size_access_err(struct bpf_verifier_env *env,
+			      int ptr_regno,
+			      int size_regno)
+{
+	struct bpf_reg_state *ptr_reg = &cur_regs(env)[ptr_regno];
+	struct bpf_reg_state *size_reg = &cur_regs(env)[size_regno];
+	const bool size_is_const = tnum_is_const(size_reg->var_off);
+	const char *ptr_type_str = reg_type_str(env, ptr_reg->type);
+	/* allocate a few buffers to be used as parts of the error message */
+	char size_range_buf[64] = {0}, max_size_buf[64] = {0}, off_buf[64] = {0};
+	s64 min_off, max_off;
+	if (!size_is_const) {
+		snprintf(size_range_buf, sizeof(size_range_buf),
+			"[0,%lld]", size_reg->umax_value);
+	}
+
+	if (tnum_is_const(ptr_reg->var_off)) {
+		min_off = (s64)ptr_reg->var_off.value + ptr_reg->off;
+		snprintf(off_buf, sizeof(off_buf), "%lld", min_off);
+	} else {
+		min_off = ptr_reg->smin_value + ptr_reg->off;
+		max_off = ptr_reg->smax_value + ptr_reg->off;
+		snprintf(off_buf, sizeof(off_buf), "[%lld,%lld]", min_off, max_off);
+	}
+
+	/* attempt to figure out info about the maximum offset that could be allowed */
+	switch (ptr_reg->type) {
+	case PTR_TO_MAP_KEY:
+		snprintf(max_size_buf, sizeof(max_size_buf), "key_size=%d", ptr_reg->map_ptr->key_size);
+		break;
+	case PTR_TO_MAP_VALUE:
+		snprintf(max_size_buf, sizeof(max_size_buf), "value_size=%d", ptr_reg->map_ptr->value_size);
+		break;
+	case PTR_TO_PACKET:
+	case PTR_TO_PACKET_META:
+		snprintf(max_size_buf, sizeof(max_size_buf), "packet_size=%d", ptr_reg->range);
+		break;
+	case PTR_TO_MEM:
+	default:
+		snprintf(max_size_buf, sizeof(max_size_buf), "max_size=N/A");
+	}
+
+	verbose(env, "invalid %szero-size read. Size comes from R%d=%s. "
+		"Attempting to dereference *%s R%d: off=%s %s\n",
+		size_is_const ? "" : "possibly ",
+		size_regno, size_is_const ? "0" : size_range_buf,
+		ptr_type_str, ptr_regno, off_buf, max_size_buf);
+}
+
+
 /* verify arguments to helpers or kfuncs consisting of a pointer and an access
  * size.
  *
@@ -7268,6 +7327,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env,
 			      struct bpf_call_arg_meta *meta)
 {
 	int err;
+	const bool size_is_const = tnum_is_const(reg->var_off);
 
 	/* This is used to refine r0 return value bounds for helpers
 	 * that enforce this value as an upper bound on return values.
@@ -7282,7 +7342,7 @@ static int check_mem_size_reg(struct bpf_verifier_env *env,
 	/* The register is SCALAR_VALUE; the access check
 	 * happens using its boundaries.
 	 */
-	if (!tnum_is_const(reg->var_off))
+	if (!size_is_const)
 		/* For unprivileged variable accesses, disable raw
 		 * mode so that the program is required to
 		 * initialize all the memory that the helper could
@@ -7296,12 +7356,9 @@ static int check_mem_size_reg(struct bpf_verifier_env *env,
 		return -EACCES;
 	}
 
-	if (reg->umin_value == 0) {
-		err = check_helper_mem_access(env, regno - 1, 0,
-					      zero_size_allowed,
-					      meta);
-		if (err)
-			return err;
+	if (reg->umin_value == 0 && !zero_size_allowed) {
+		log_zero_size_access_err(env, regno-1, regno);
+		return -EACCES;
 	}
 
 	if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
@@ -7309,9 +7366,21 @@ static int check_mem_size_reg(struct bpf_verifier_env *env,
 			regno);
 		return -EACCES;
 	}
+	/* If !zero_size_allowed, we already checked that umin_value > 0, so
+	 * umax_value should also be > 0.
+	 */
+	if (reg->umax_value == 0 && !zero_size_allowed) {
+		verbose(env, "verifier bug: !zero_size_allowed should have been handled already\n");
+		return -EFAULT;
+	}
 	err = check_helper_mem_access(env, regno - 1,
 				      reg->umax_value,
-				      zero_size_allowed, meta);
+				      /* zero_size_allowed: we asserted above that umax_value is
+				       * not zero if !zero_size_allowed, so we don't need any
+				       * further checks.
+				       */
+				      true ,
+				      meta);
 	if (!err)
 		err = mark_chain_precision(env, regno);
 	return err;
diff --git a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c
index 692216c0ad3d..9fe10f63c931 100644
--- a/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c
+++ b/tools/testing/selftests/bpf/progs/verifier_helper_value_access.c
@@ -89,9 +89,14 @@ l0_%=:	exit;						\
 	: __clobber_all);
 }
 
+/* Call a function taking a pointer and a size which doesn't allow the size to
+ * be zero (i.e. bpf_trace_printk() declares the second argument to be
+ * ARG_CONST_SIZE, not ARG_CONST_SIZE_OR_ZERO). We attempt to pass zero for the
+ * size and expect to fail.
+ */
 SEC("tracepoint")
 __description("helper access to map: empty range")
-__failure __msg("invalid access to map value, value_size=48 off=0 size=0")
+__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48")
 __naked void access_to_map_empty_range(void)
 {
 	asm volatile ("					\
@@ -113,6 +118,38 @@ l0_%=:	exit;						\
 	: __clobber_all);
 }
 
+/* Like the test above, but this time the size register is not known to be zero;
+ * its lower-bound is zero though, which is still unacceptible.
+ */
+SEC("tracepoint")
+__description("helper access to map: possibly-empty range")
+__failure __msg("invalid possibly zero-size read. Size comes from R2=[0,4]. Attempting to dereference *map_value R1: off=0 value_size=48")
+__naked void access_to_map_possibly_empty_range(void)
+{
+	asm volatile ("                                         \
+	r2 = r10;                                               \
+	r2 += -8;                                               \
+	r1 = 0;                                                 \
+	*(u64*)(r2 + 0) = r1;                                   \
+	r1 = %[map_hash_48b] ll;                                \
+	call %[bpf_map_lookup_elem];                            \
+	if r0 == 0 goto l0_%=;                                  \
+	r1 = r0;                                                \
+	/* Read an unknown value */                             \
+	r7 = *(u64*)(r0 + 0);                                   \
+	/* Make it small and positive, to avoid other errors */ \
+	r7 &= 4;                                                \
+	r2 = 0;                                                 \
+	r2 += r7;                                               \
+	call %[bpf_trace_printk];                               \
+l0_%=:	exit;                                               \
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm(bpf_trace_printk),
+	  __imm_addr(map_hash_48b)
+	: __clobber_all);
+}
+
 SEC("tracepoint")
 __description("helper access to map: out-of-bound range")
 __failure __msg("invalid access to map value, value_size=48 off=0 size=56")
@@ -221,7 +258,7 @@ l0_%=:	exit;						\
 
 SEC("tracepoint")
 __description("helper access to adjusted map (via const imm): empty range")
-__failure __msg("invalid access to map value, value_size=48 off=4 size=0")
+__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=4 value_size=48")
 __naked void via_const_imm_empty_range(void)
 {
 	asm volatile ("					\
@@ -386,7 +423,7 @@ l0_%=:	exit;						\
 
 SEC("tracepoint")
 __description("helper access to adjusted map (via const reg): empty range")
-__failure __msg("R1 min value is outside of the allowed memory range")
+__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=0 value_size=48")
 __naked void via_const_reg_empty_range(void)
 {
 	asm volatile ("					\
@@ -556,7 +593,7 @@ l0_%=:	exit;						\
 
 SEC("tracepoint")
 __description("helper access to adjusted map (via variable): empty range")
-__failure __msg("R1 min value is outside of the allowed memory range")
+__failure __msg("invalid zero-size read. Size comes from R2=0. Attempting to dereference *map_value R1: off=[0,4] value_size=48")
 __naked void map_via_variable_empty_range(void)
 {
 	asm volatile ("					\
diff --git a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
index f67390224a9c..c133d9d2c45e 100644
--- a/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
+++ b/tools/testing/selftests/bpf/progs/verifier_raw_stack.c
@@ -64,7 +64,7 @@ __naked void load_bytes_negative_len_2(void)
 
 SEC("tc")
 __description("raw_stack: skb_load_bytes, zero len")
-__failure __msg("invalid zero-sized read")
+__failure __msg("invalid zero-size read. Size comes from R4=0. Attempting to dereference *fp R3: off=-8 max_size=N/A")
 __naked void skb_load_bytes_zero_len(void)
 {
 	asm volatile ("					\
@@ -333,7 +333,7 @@ __naked void load_bytes_invalid_access_5(void)
 
 SEC("tc")
 __description("raw_stack: skb_load_bytes, invalid access 6")
-__failure __msg("invalid zero-sized read")
+__failure __msg("invalid zero-size read. Size comes from R4=0. Attempting to dereference *fp R3: off=-512 max_size=N/A")
 __naked void load_bytes_invalid_access_6(void)
 {
 	asm volatile ("					\
-- 
2.40.1