[PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements

[PATCH bpf-next v2 0/5] bpf/verifier: range computation improvements

[Cupertino Miranda]

Hi everyone,

This is the second series of this patches, now changed after Yonghong
review. Thank you for the review.

Changes from v1:
 - Reordered patches in the series.
 - Fix refactor to be acurate with original code.
 - Fixed other mentioned small problems.


This patch series is a follow up on the problem identified in
https://github.com/systemd/systemd/issues/31888.
This problem first shown as a result of a GCC compilation for BPF that
ends converting a condition based decision tree, into a logic based one
(making use of XOR), in order to compute expected return value for the
function.

This issue was also reported in
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114523 and contains both
the original reproducer pattern and some other that also fails within
clang.

This is the result of an earlier test that allows to describe the
problem better:

  VERIFIER LOG:
  =============
  Global function reg32_0_reg32_xor_reg_01() doesn't return scalar. Only those are supported.
  0: R1=ctx() R10=fp0
  ; asm volatile ("                                       \ @ verifier_bounds.c:755
  0: (85) call bpf_get_prandom_u32#7    ; R0_w=scalar()
  1: (bf) r6 = r0                       ; R0_w=scalar(id=1) R6_w=scalar(id=1)
  2: (b7) r1 = 0                        ; R1_w=0
  3: (7b) *(u64 *)(r10 -8) = r1         ; R1_w=0 R10=fp0 fp-8_w=0
  4: (bf) r2 = r10                      ; R2_w=fp0 R10=fp0
  5: (07) r2 += -8                      ; R2_w=fp-8
  6: (18) r1 = 0xffff8e8ec3b99000       ; R1_w=map_ptr(map=map_hash_8b,ks=8,vs=8)
  8: (85) call bpf_map_lookup_elem#1    ; R0=map_value_or_null(id=2,map=map_hash_8b,ks=8,vs=8)
  9: (55) if r0 != 0x0 goto pc+1 11: R0=map_value(map=map_hash_8b,ks=8,vs=8) R6=scalar(id=1) R10=fp0 fp-8=mmmmmmmm
  11: (b4) w1 = 0                       ; R1_w=0
  12: (77) r6 >>= 63                    ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,var_off=(0x0; 0x1))
  13: (ac) w1 ^= w6                     ; R1_w=scalar() R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,var_off=(0x0; 0x1))
  14: (16) if w1 == 0x0 goto pc+2       ; R1_w=scalar(smin=0x8000000000000001,umin=umin32=1)
  15: (16) if w1 == 0x1 goto pc+1       ; R1_w=scalar(smin=0x8000000000000002,umin=umin32=2)
  16: (79) r0 = *(u64 *)(r0 +8)
  invalid access to map value, value_size=8 off=8 size=8
  R0 min value is outside of the allowed memory range
  processed 16 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
  =============

The test collects a random number and shifts it right by 63 bits to reduce its
range to (0,1), which will then xor to compute the value of w1, checking
if the value is either 0 or 1 after.
By analysing the code and the ranges computations, one can easily deduce
that the result of the XOR is also within the range (0,1), however:

  11: (b4) w1 = 0                       ; R1_w=0
  12: (77) r6 >>= 63                    ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,var_off=(0x0; 0x1))
  13: (ac) w1 ^= w6                     ; R1_w=scalar() R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=1,var_off=(0x0; 0x1))
                                            ^
                                            |___ No range is computed for R1

The verifier seems to act pessimistically and will only compute a range
for dst_reg, if the src_reg is a known value.
This happens in:

  -- verifier.c:13700 --
  if (!src_known &&
      opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
          __mark_reg_unknown(env, dst_reg);
          return 0;
  }

This patch series addresses the problem and improves the support for
range computation for XOR and OR.
Apart from XOR and OR the patch series also improves the range
computation for MUL for the case where either of its operands is a known
value.

Looking forward to your comments.

Regards,
Cupertino

Cupertino Miranda (5):
  bpf/verifier: refactor checks for range computation
  bpf/verifier: improve XOR and OR range computation
  selftests/bpf: XOR and OR range computation tests.
  bpf/verifier: relax MUL range computation check
  selftests/bpf: MUL range computation tests.

 kernel/bpf/verifier.c                         | 160 ++++++++++-------
 .../selftests/bpf/progs/verifier_bounds.c     | 163 ++++++++++++++++++
 2 files changed, 260 insertions(+), 63 deletions(-)

-- 
2.39.2

[PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Cupertino Miranda]

Split range computation checks in its own function, isolating pessimitic
range set for dst_reg and failing return to a single point.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
 kernel/bpf/verifier.c | 155 +++++++++++++++++++++++++-----------------
 1 file changed, 92 insertions(+), 63 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8e7b6072e3f4..0aa6580af7a2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13395,6 +13395,90 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
 	__update_reg_bounds(dst_reg);
 }
 
+static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
+				   bool *valid)
+{
+	s64 smin_val = reg.smin_value;
+	s64 smax_val = reg.smax_value;
+	u64 umin_val = reg.umin_value;
+	u64 umax_val = reg.umax_value;
+
+	s32 s32_min_val = reg.s32_min_value;
+	s32 s32_max_val = reg.s32_max_value;
+	u32 u32_min_val = reg.u32_min_value;
+	u32 u32_max_val = reg.u32_max_value;
+
+	bool known = alu32 ? tnum_subreg_is_const(reg.var_off) :
+			     tnum_is_const(reg.var_off);
+
+	if (alu32) {
+		if ((known &&
+		     (s32_min_val != s32_max_val || u32_min_val != u32_max_val)) ||
+		      s32_min_val > s32_max_val || u32_min_val > u32_max_val)
+			*valid = false;
+	} else {
+		if ((known &&
+		     (smin_val != smax_val || umin_val != umax_val)) ||
+		    smin_val > smax_val || umin_val > umax_val)
+			*valid = false;
+	}
+
+	return known;
+}
+
+enum {
+	COMPUTABLE_RANGE    =  1,
+	UNCOMPUTABLE_RANGE  =  0,
+	UNDEFINED_BEHAVIOUR = -1,
+};
+
+static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
+					    struct bpf_reg_state src_reg)
+{
+	bool src_known;
+	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
+	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
+	u8 opcode = BPF_OP(insn->code);
+
+	bool valid_known = true;
+	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
+
+	/* Taint dst register if offset had invalid bounds
+	 * derived from e.g. dead branches.
+	 */
+	if (valid_known == false)
+		return UNCOMPUTABLE_RANGE;
+
+	switch (opcode) {
+	case BPF_ADD:
+	case BPF_SUB:
+	case BPF_AND:
+		return COMPUTABLE_RANGE;
+
+	/* Compute range for the following only if the src_reg is known.
+	 */
+	case BPF_XOR:
+	case BPF_OR:
+	case BPF_MUL:
+		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+
+	/* Shift operators range is only computable if shift dimension operand
+	 * is known. Also, shifts greater than 31 or 63 are undefined. This
+	 * includes shifts by a negative number.
+	 */
+	case BPF_LSH:
+	case BPF_RSH:
+	case BPF_ARSH:
+		if (src_reg.umax_value >= insn_bitness)
+			return UNDEFINED_BEHAVIOUR;
+		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+	default:
+		break;
+	}
+
+	return UNCOMPUTABLE_RANGE;
+}
+
 /* WARNING: This function does calculations on 64-bit values, but the actual
  * execution may occur on 32-bit values. Therefore, things like bitshifts
  * need extra checks in the 32-bit case.
@@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 {
 	struct bpf_reg_state *regs = cur_regs(env);
 	u8 opcode = BPF_OP(insn->code);
-	bool src_known;
-	s64 smin_val, smax_val;
-	u64 umin_val, umax_val;
-	s32 s32_min_val, s32_max_val;
-	u32 u32_min_val, u32_max_val;
-	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	int ret;
 
-	smin_val = src_reg.smin_value;
-	smax_val = src_reg.smax_value;
-	umin_val = src_reg.umin_value;
-	umax_val = src_reg.umax_value;
-
-	s32_min_val = src_reg.s32_min_value;
-	s32_max_val = src_reg.s32_max_value;
-	u32_min_val = src_reg.u32_min_value;
-	u32_max_val = src_reg.u32_max_value;
-
-	if (alu32) {
-		src_known = tnum_subreg_is_const(src_reg.var_off);
-		if ((src_known &&
-		     (s32_min_val != s32_max_val || u32_min_val != u32_max_val)) ||
-		    s32_min_val > s32_max_val || u32_min_val > u32_max_val) {
-			/* Taint dst register if offset had invalid bounds
-			 * derived from e.g. dead branches.
-			 */
-			__mark_reg_unknown(env, dst_reg);
-			return 0;
-		}
-	} else {
-		src_known = tnum_is_const(src_reg.var_off);
-		if ((src_known &&
-		     (smin_val != smax_val || umin_val != umax_val)) ||
-		    smin_val > smax_val || umin_val > umax_val) {
-			/* Taint dst register if offset had invalid bounds
-			 * derived from e.g. dead branches.
-			 */
-			__mark_reg_unknown(env, dst_reg);
-			return 0;
-		}
-	}
-
-	if (!src_known &&
-	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
+	int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
+	switch (is_safe) {
+	case UNCOMPUTABLE_RANGE:
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
+	case UNDEFINED_BEHAVIOUR:
+		mark_reg_unknown(env, regs, insn->dst_reg);
+		return 0;
+	default:
+		break;
 	}
 
 	if (sanitize_needed(opcode)) {
@@ -13507,39 +13557,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		scalar_min_max_xor(dst_reg, &src_reg);
 		break;
 	case BPF_LSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_lsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_lsh(dst_reg, &src_reg);
 		break;
 	case BPF_RSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_rsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_rsh(dst_reg, &src_reg);
 		break;
 	case BPF_ARSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_arsh(dst_reg, &src_reg);
 		else
-- 
2.39.2

[PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR range computation

[Cupertino Miranda]

Range for XOR and OR operators would not be attempted unless src_reg
would resolve to a single value, i.e. a known constant value.
This condition is unnecessary, and the following XOR/OR operator
handling could compute a possible better range.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
 kernel/bpf/verifier.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0aa6580af7a2..f410eb027e25 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13453,12 +13453,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	case BPF_ADD:
 	case BPF_SUB:
 	case BPF_AND:
+	case BPF_XOR:
+	case BPF_OR:
 		return COMPUTABLE_RANGE;
 
 	/* Compute range for the following only if the src_reg is known.
 	 */
-	case BPF_XOR:
-	case BPF_OR:
 	case BPF_MUL:
 		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
 
-- 
2.39.2

[PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.

[Cupertino Miranda]

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
 1 file changed, 64 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index ec430b71730b..e3c867d48664 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -885,6 +885,70 @@ l1_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 xor (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_xor_01(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 0;						\
+	r6 >>= 63;					\
+	w1 ^= w6;					\
+	if w1 <= 1 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 <= 1, 0 or (0,1)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void t_0_or_01(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 0;						\
+	r6 >>= 63;					\
+	w1 |= w6;					\
+	if w1 <= 1 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 SEC("socket")
 __description("bounds checks after 32-bit truncation. test 1")
 __success __failure_unpriv __msg_unpriv("R0 leaks addr")
-- 
2.39.2

[PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Cupertino Miranda]

MUL instruction required that src_reg would be a known value (i.e.
src_reg would be a const value). The condition in this case can be
relaxed, since multiplication is a cummutative operator and the range
computation is still valid if at least one of its registers is known.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
 kernel/bpf/verifier.c | 19 ++++++++++++-------
 1 file changed, 12 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f410eb027e25..185ea7f19a79 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13433,20 +13433,23 @@ enum {
 };
 
 static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
+					    struct bpf_reg_state dst_reg,
 					    struct bpf_reg_state src_reg)
 {
-	bool src_known;
+	bool src_known, dst_known;
 	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	u8 opcode = BPF_OP(insn->code);
 
-	bool valid_known = true;
-	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
+	bool valid_known_src = true;
+	bool valid_known_dst = true;
+	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
+	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
 
 	/* Taint dst register if offset had invalid bounds
 	 * derived from e.g. dead branches.
 	 */
-	if (valid_known == false)
+	if (valid_known_src == false)
 		return UNCOMPUTABLE_RANGE;
 
 	switch (opcode) {
@@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	case BPF_OR:
 		return COMPUTABLE_RANGE;
 
-	/* Compute range for the following only if the src_reg is known.
+	/* Compute range for MUL if at least one of its registers is known.
 	 */
 	case BPF_MUL:
-		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
+		if (src_known || (dst_known && valid_known_dst))
+			return COMPUTABLE_RANGE;
+		break;
 
 	/* Shift operators range is only computable if shift dimension operand
 	 * is known. Also, shifts greater than 31 or 63 are undefined. This
@@ -13493,7 +13498,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	int ret;
 
-	int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
+	int is_safe = is_safe_to_compute_dst_reg_range(insn, *dst_reg, src_reg);
 	switch (is_safe) {
 	case UNCOMPUTABLE_RANGE:
 		__mark_reg_unknown(env, dst_reg);
-- 
2.39.2

[PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests.

[Cupertino Miranda]

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Cc: Yonghong Song <yonghong.song@linux.dev>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: David Faust <david.faust@oracle.com>
Cc: Jose Marchesi <jose.marchesi@oracle.com
Cc: Elena Zannoni <elena.zannoni@oracle.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
 1 file changed, 99 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index e3c867d48664..719e247114f5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -949,6 +949,105 @@ l1_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for reg32 <= 9, 3 mul (0,3)")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_3_mul_reg_01(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 3;						\
+	r6 >>= 62;					\
+	w1 *= w6;					\
+	if w1 <= 9 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 <= 9, (0,3) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_13_mul_reg_3(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 3;						\
+	r6 >>= 62;					\
+	w6 *= w1;					\
+	if w6 <= 9 goto l1_%=;				\
+	r0 = *(u64*)(r0 + 8);				\
+l1_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for reg32 >= 6 && reg32 <= 15, (2,5) mul 3")
+__success __failure_unpriv
+__msg_unpriv("R0 min value is outside of the allowed memory range")
+__retval(0)
+__naked void reg32_25_mul_reg_3(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;                                        \
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	if r0 != 0 goto l0_%=;				\
+	exit;						\
+l0_%=:	w1 = 3;						\
+	r6 >>= 62;					\
+	r6 += 2;					\
+	w6 *= w1;					\
+	if w6 > 15 goto l1_%=;				\
+	if w6 < 6 goto l1_%=;				\
+	r0 = 0;						\
+	exit;						\
+l1_%=:  r0 = *(u64*)(r0 + 8);				\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b),
+	  __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 SEC("socket")
 __description("bounds checks after 32-bit truncation. test 1")
 __success __failure_unpriv __msg_unpriv("R0 leaks addr")
-- 
2.39.2

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Eduard Zingerman]

On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
[...]

> @@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,

[...]

> -	if (!src_known &&
> -	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> +	int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
> +	switch (is_safe) {
> +	case UNCOMPUTABLE_RANGE:
>  		__mark_reg_unknown(env, dst_reg);
>  		return 0;
> +	case UNDEFINED_BEHAVIOUR:
> +		mark_reg_unknown(env, regs, insn->dst_reg);
> +		return 0;
> +	default:
> +		break;
>  	}

Nit: I know that the division between __mark_reg_unknown() and
mark_reg_unknown() was asked for directly, but tbh I don't think that
it adds any value here, here is how mark_reg_unknown() is implemented:

static void mark_reg_unknown(struct bpf_verifier_env *env,
			     struct bpf_reg_state *regs, u32 regno)
{
	if (WARN_ON(regno >= MAX_BPF_REG)) {
		... mark all regs not init ...
		return;
    }
	__mark_reg_unknown(env, regs + regno);
}

The 'regno >= MAX_BPF_REG' does not apply here, because
adjust_scalar_min_max_vals() is only called from the following stack:
- check_alu_op
  - adjust_reg_min_max_vals
    - adjust_scalar_min_max_vals

The check_alu_op() does check_reg_arg() which verifies that both src
and dst register numbers are within bounds.

I suggest to replace the enum with as boolean value.
Miranda, Yonhong, what do you think?

[...]

Re: [PATCH bpf-next v2 2/5] bpf/verifier: improve XOR and OR range computation

[Eduard Zingerman]

On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> Range for XOR and OR operators would not be attempted unless src_reg
> would resolve to a single value, i.e. a known constant value.
> This condition is unnecessary, and the following XOR/OR operator
> handling could compute a possible better range.
> 
> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com
> Cc: Yonghong Song <yonghong.song@linux.dev>
> Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Cc: David Faust <david.faust@oracle.com>
> Cc: Jose Marchesi <jose.marchesi@oracle.com
> Cc: Elena Zannoni <elena.zannoni@oracle.com>
> ---

I agree with this reasoning regarding OR/XOR processing.

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.

[Eduard Zingerman]

On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:

[...]

> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_xor_01(void)
> +{
> +	asm volatile ("					\
> +	call %[bpf_get_prandom_u32];                    \
> +	r6 = r0;                                        \
> +	r1 = 0;						\
> +	*(u64*)(r10 - 8) = r1;				\
> +	r2 = r10;					\
> +	r2 += -8;					\
> +	r1 = %[map_hash_8b] ll;				\
> +	call %[bpf_map_lookup_elem];			\
> +	if r0 != 0 goto l0_%=;				\
> +	exit;						\
> +l0_%=:	w1 = 0;						\
> +	r6 >>= 63;					\
> +	w1 ^= w6;					\
> +	if w1 <= 1 goto l1_%=;				\
> +	r0 = *(u64*)(r0 + 8);				\
> +l1_%=:	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_map_lookup_elem),
> +	  __imm_addr(map_hash_8b),
> +	  __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}
> +

I think that this test case (and one below) should be simplified,
e.g. as follows:

SEC("socket")
__success __log_level(2)
__msg("5: (af) r0 ^= r6                      ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")
__naked void non_const_xor_src_dst(void)
{
	asm volatile ("					\
	call %[bpf_get_prandom_u32];                    \
	r6 = r0;					\
	call %[bpf_get_prandom_u32];                    \
	r6 &= 0xff;					\
	r0 &= 0x0f;					\
	r0 ^= r6;					\
	exit;						\
"	:
	: __imm(bpf_map_lookup_elem),
	  __imm_addr(map_hash_8b),
	  __imm(bpf_get_prandom_u32)
	: __clobber_all);
}

Patch #2 allows verifier to compute dst range for xor operation with
non-constant src and dst registers, which is exactly what checked when
verifier log for instruction "r0 ^= r6" is verified.
Manipulations with maps, unpriv behavior and retval are just a distraction.

Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Eduard Zingerman]

On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:

[...]

>  static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
> +					    struct bpf_reg_state dst_reg,
>  					    struct bpf_reg_state src_reg)

Nit: there is no need to pass {dst,src}_reg by value,
     struct bpf_reg_state is 120 bytes in size
    (but maybe compiler handles this).

>  {
> -	bool src_known;
> +	bool src_known, dst_known;
>  	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>  	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>  	u8 opcode = BPF_OP(insn->code);
>  
> -	bool valid_known = true;
> -	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
> +	bool valid_known_src = true;
> +	bool valid_known_dst = true;
> +	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>  
>  	/* Taint dst register if offset had invalid bounds
>  	 * derived from e.g. dead branches.
>  	 */
> -	if (valid_known == false)
> +	if (valid_known_src == false)
>  		return UNCOMPUTABLE_RANGE;
>  
>  	switch (opcode) {
> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>  	case BPF_OR:
>  		return COMPUTABLE_RANGE;
>  
> -	/* Compute range for the following only if the src_reg is known.
> +	/* Compute range for MUL if at least one of its registers is known.
>  	 */
>  	case BPF_MUL:
> -		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
> +		if (src_known || (dst_known && valid_known_dst))
> +			return COMPUTABLE_RANGE;
> +		break;

Is it even necessary to restrict src or dst to be known?
adjust_scalar_min_max_vals() logic for multiplication looks as follows:

	case BPF_MUL:
		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
		scalar32_min_max_mul(dst_reg, &src_reg);
		scalar_min_max_mul(dst_reg, &src_reg);
		break;

Where tnum_mul() refers to a paper, and that paper does not restrict
abstract multiplication algorithm to constant values on either side.
The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
- if both src and dst are positive
- if overflow is not possible
- adjust dst->min *= src->min
- adjust dst->max *= src->max

I think this should work just fine if neither of src or dst is a known constant.
What do you think?

[...]

Re: [PATCH bpf-next v2 5/5] selftests/bpf: MUL range computation tests.

[Eduard Zingerman]

On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
> Cc: Yonghong Song <yonghong.song@linux.dev>
> Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Cc: David Faust <david.faust@oracle.com>
> Cc: Jose Marchesi <jose.marchesi@oracle.com
> Cc: Elena Zannoni <elena.zannoni@oracle.com>
> ---

As with or/xor, I suggest to simplify these test cases:
- avoid unnecessary control flow
- avoid map manipulations
- drop __unpriv_* and __retval parts.

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Cupertino Miranda]

Eduard Zingerman writes:

> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
> [...]
>
>> @@ -13406,53 +13490,19 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>
> [...]
>
>> -	if (!src_known &&
>> -	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
>> +	int is_safe = is_safe_to_compute_dst_reg_range(insn, src_reg);
>> +	switch (is_safe) {
>> +	case UNCOMPUTABLE_RANGE:
>>  		__mark_reg_unknown(env, dst_reg);
>>  		return 0;
>> +	case UNDEFINED_BEHAVIOUR:
>> +		mark_reg_unknown(env, regs, insn->dst_reg);
>> +		return 0;
>> +	default:
>> +		break;
>>  	}
>
> Nit: I know that the division between __mark_reg_unknown() and
> mark_reg_unknown() was asked for directly, but tbh I don't think that
> it adds any value here, here is how mark_reg_unknown() is implemented:
>
> static void mark_reg_unknown(struct bpf_verifier_env *env,
> 			     struct bpf_reg_state *regs, u32 regno)
> {
> 	if (WARN_ON(regno >= MAX_BPF_REG)) {
> 		... mark all regs not init ...
> 		return;
>     }
> 	__mark_reg_unknown(env, regs + regno);
> }
>
> The 'regno >= MAX_BPF_REG' does not apply here, because
> adjust_scalar_min_max_vals() is only called from the following stack:
> - check_alu_op
>   - adjust_reg_min_max_vals
>     - adjust_scalar_min_max_vals
>
> The check_alu_op() does check_reg_arg() which verifies that both src
> and dst register numbers are within bounds.
>
> I suggest to replace the enum with as boolean value.
> Miranda, Yonhong, what do you think?

Thanks for the detailed review.

Well, honestly I could not evaluate if there was any actual difference
between the approaches. Although I can understand range computation in
isolation of an instruction I still did not explore the code in the
global perspective, for example the handling of control-flow.
I was proud of the initial boolean implementation that was very clean
and simple, although like Yonghong said, not truly a refactor.
If everyone agrees that it is Ok, I will be happy to change it back.

>
> [...]

Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.

[Cupertino Miranda]

Eduard Zingerman writes:

> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>
> [...]
>
>> +SEC("socket")
>> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
>> +__success __failure_unpriv
>> +__msg_unpriv("R0 min value is outside of the allowed memory range")
>> +__retval(0)
>> +__naked void t_0_xor_01(void)
>> +{
>> +	asm volatile ("					\
>> +	call %[bpf_get_prandom_u32];                    \
>> +	r6 = r0;                                        \
>> +	r1 = 0;						\
>> +	*(u64*)(r10 - 8) = r1;				\
>> +	r2 = r10;					\
>> +	r2 += -8;					\
>> +	r1 = %[map_hash_8b] ll;				\
>> +	call %[bpf_map_lookup_elem];			\
>> +	if r0 != 0 goto l0_%=;				\
>> +	exit;						\
>> +l0_%=:	w1 = 0;						\
>> +	r6 >>= 63;					\
>> +	w1 ^= w6;					\
>> +	if w1 <= 1 goto l1_%=;				\
>> +	r0 = *(u64*)(r0 + 8);				\
>> +l1_%=:	r0 = 0;						\
>> +	exit;						\
>> +"	:
>> +	: __imm(bpf_map_lookup_elem),
>> +	  __imm_addr(map_hash_8b),
>> +	  __imm(bpf_get_prandom_u32)
>> +	: __clobber_all);
>> +}
>> +
>
> I think that this test case (and one below) should be simplified,
> e.g. as follows:
>
> SEC("socket")
> __success __log_level(2)
> __msg("5: (af) r0 ^= r6                      ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=255,var_off=(0x0; 0xff))")
> __naked void non_const_xor_src_dst(void)
> {
> 	asm volatile ("					\
> 	call %[bpf_get_prandom_u32];                    \
> 	r6 = r0;					\
> 	call %[bpf_get_prandom_u32];                    \
> 	r6 &= 0xff;					\
> 	r0 &= 0x0f;					\
> 	r0 ^= r6;					\
> 	exit;						\
> "	:
> 	: __imm(bpf_map_lookup_elem),
> 	  __imm_addr(map_hash_8b),
> 	  __imm(bpf_get_prandom_u32)
> 	: __clobber_all);
> }
>
> Patch #2 allows verifier to compute dst range for xor operation with
> non-constant src and dst registers, which is exactly what checked when
> verifier log for instruction "r0 ^= r6" is verified.
> Manipulations with maps, unpriv behavior and retval are just a distraction.

Thanks for the suggestion.
I could not make it fail in the past without that control-flow in the
end of the test. I will try this.

Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Cupertino Miranda]

Eduard Zingerman writes:

> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>
> [...]
>
>>  static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>> +					    struct bpf_reg_state dst_reg,
>>  					    struct bpf_reg_state src_reg)
>
> Nit: there is no need to pass {dst,src}_reg by value,
>      struct bpf_reg_state is 120 bytes in size
>     (but maybe compiler handles this).
>
>>  {
>> -	bool src_known;
>> +	bool src_known, dst_known;
>>  	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>  	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>  	u8 opcode = BPF_OP(insn->code);
>>
>> -	bool valid_known = true;
>> -	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>> +	bool valid_known_src = true;
>> +	bool valid_known_dst = true;
>> +	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>
>>  	/* Taint dst register if offset had invalid bounds
>>  	 * derived from e.g. dead branches.
>>  	 */
>> -	if (valid_known == false)
>> +	if (valid_known_src == false)
>>  		return UNCOMPUTABLE_RANGE;
>>
>>  	switch (opcode) {
>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>  	case BPF_OR:
>>  		return COMPUTABLE_RANGE;
>>
>> -	/* Compute range for the following only if the src_reg is known.
>> +	/* Compute range for MUL if at least one of its registers is known.
>>  	 */
>>  	case BPF_MUL:
>> -		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>> +		if (src_known || (dst_known && valid_known_dst))
>> +			return COMPUTABLE_RANGE;
>> +		break;
>
> Is it even necessary to restrict src or dst to be known?
> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>
> 	case BPF_MUL:
> 		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
> 		scalar32_min_max_mul(dst_reg, &src_reg);
> 		scalar_min_max_mul(dst_reg, &src_reg);
> 		break;
>
> Where tnum_mul() refers to a paper, and that paper does not restrict
> abstract multiplication algorithm to constant values on either side.
> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
> - if both src and dst are positive
> - if overflow is not possible
> - adjust dst->min *= src->min
> - adjust dst->max *= src->max
>
> I think this should work just fine if neither of src or dst is a known constant.
> What do you think?
>
With the refactor this looked like an armless change. Indeed if we agree
that the algorithm covers all scenarios, then why not.
I did not study the paper or the scalar_min_max_mul function nearly
enough to know for sure.
>
> [...]

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Eduard Zingerman]

On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:

[...]

> I was proud of the initial boolean implementation that was very clean
> and simple, although like Yonghong said, not truly a refactor.
> If everyone agrees that it is Ok, I will be happy to change it back.

Yes, I liked it more than v2 as well :)
Let's wait and see what Yonghong would say.

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Eduard Zingerman]

On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:

[...]

> I was proud of the initial boolean implementation that was very clean
> and simple, although like Yonghong said, not truly a refactor.
> If everyone agrees that it is Ok, I will be happy to change it back.

Hi Miranda,

I've talked to Yonghong today, he is ok with removing distinction between
__mark_reg_unknown and mark_reg_unknown, but he asks to first make a patch,
that replaces the use of mark_reg_unknown() by __mark_reg_unknown().
So that the follow-up refactoring patch would not change any behaviour.
What do you think?

Best regards,
Eduard

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Cupertino Miranda]

Eduard Zingerman writes:

> On Fri, 2024-04-19 at 10:37 +0100, Cupertino Miranda wrote:
>
> [...]
>
>> I was proud of the initial boolean implementation that was very clean
>> and simple, although like Yonghong said, not truly a refactor.
>> If everyone agrees that it is Ok, I will be happy to change it back.
>
> Hi Miranda,
>
> I've talked to Yonghong today, he is ok with removing distinction between
> __mark_reg_unknown and mark_reg_unknown, but he asks to first make a patch,
> that replaces the use of mark_reg_unknown() by __mark_reg_unknown().
> So that the follow-up refactoring patch would not change any behaviour.
> What do you think?
Sure, I will prepare it. I presure the patch should be the first in the
series.

Thanks,
Cupertino
>
> Best regards,
> Eduard

Re: [PATCH bpf-next v2 1/5] bpf/verifier: refactor checks for range computation

[Eduard Zingerman]

On Tue, 2024-04-23 at 20:36 +0100, Cupertino Miranda wrote:

[...]

> Sure, I will prepare it. I presure the patch should be the first in the
> series.

Right, thank you.

Re: [PATCH bpf-next v2 3/5] selftests/bpf: XOR and OR range computation tests.

[Yonghong Song]

On 4/17/24 5:23 AM, Cupertino Miranda wrote:

Please add proper commit message.

> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
> Cc: Yonghong Song <yonghong.song@linux.dev>
> Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>
> Cc: David Faust <david.faust@oracle.com>
> Cc: Jose Marchesi <jose.marchesi@oracle.com
> Cc: Elena Zannoni <elena.zannoni@oracle.com>
> ---
>   .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
>   1 file changed, 64 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index ec430b71730b..e3c867d48664 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> @@ -885,6 +885,70 @@ l1_%=:	r0 = 0;						\
>   	: __clobber_all);
>   }
>   
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 xor (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_xor_01(void)
> +{
> +	asm volatile ("					\
> +	call %[bpf_get_prandom_u32];                    \
> +	r6 = r0;                                        \
> +	r1 = 0;						\
> +	*(u64*)(r10 - 8) = r1;				\
> +	r2 = r10;					\
> +	r2 += -8;					\
> +	r1 = %[map_hash_8b] ll;				\
> +	call %[bpf_map_lookup_elem];			\
> +	if r0 != 0 goto l0_%=;				\
> +	exit;						\
> +l0_%=:	w1 = 0;						\
> +	r6 >>= 63;					\
> +	w1 ^= w6;					\
> +	if w1 <= 1 goto l1_%=;				\
> +	r0 = *(u64*)(r0 + 8);				\
> +l1_%=:	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_map_lookup_elem),
> +	  __imm_addr(map_hash_8b),
> +	  __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}
> +
> +SEC("socket")
> +__description("bounds check for reg32 <= 1, 0 or (0,1)")
> +__success __failure_unpriv
> +__msg_unpriv("R0 min value is outside of the allowed memory range")
> +__retval(0)
> +__naked void t_0_or_01(void)
> +{
> +	asm volatile ("					\
> +	call %[bpf_get_prandom_u32];                    \
> +	r6 = r0;                                        \
> +	r1 = 0;						\
> +	*(u64*)(r10 - 8) = r1;				\
> +	r2 = r10;					\
> +	r2 += -8;					\
> +	r1 = %[map_hash_8b] ll;				\
> +	call %[bpf_map_lookup_elem];			\
> +	if r0 != 0 goto l0_%=;				\
> +	exit;						\
> +l0_%=:	w1 = 0;						\
> +	r6 >>= 63;					\
> +	w1 |= w6;					\
> +	if w1 <= 1 goto l1_%=;				\
> +	r0 = *(u64*)(r0 + 8);				\
> +l1_%=:	r0 = 0;						\
> +	exit;						\
> +"	:
> +	: __imm(bpf_map_lookup_elem),
> +	  __imm_addr(map_hash_8b),
> +	  __imm(bpf_get_prandom_u32)
> +	: __clobber_all);
> +}
> +
>   SEC("socket")
>   __description("bounds checks after 32-bit truncation. test 1")
>   __success __failure_unpriv __msg_unpriv("R0 leaks addr")

Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Yonghong Song]

On 4/19/24 2:47 AM, Cupertino Miranda wrote:
> Eduard Zingerman writes:
>
>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>
>> [...]
>>
>>>   static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>> +					    struct bpf_reg_state dst_reg,
>>>   					    struct bpf_reg_state src_reg)
>> Nit: there is no need to pass {dst,src}_reg by value,
>>       struct bpf_reg_state is 120 bytes in size
>>      (but maybe compiler handles this).
>>
>>>   {
>>> -	bool src_known;
>>> +	bool src_known, dst_known;
>>>   	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>>   	u8 opcode = BPF_OP(insn->code);
>>>
>>> -	bool valid_known = true;
>>> -	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>>> +	bool valid_known_src = true;
>>> +	bool valid_known_dst = true;
>>> +	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>
>>>   	/* Taint dst register if offset had invalid bounds
>>>   	 * derived from e.g. dead branches.
>>>   	 */
>>> -	if (valid_known == false)
>>> +	if (valid_known_src == false)
>>>   		return UNCOMPUTABLE_RANGE;
>>>
>>>   	switch (opcode) {
>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>   	case BPF_OR:
>>>   		return COMPUTABLE_RANGE;
>>>
>>> -	/* Compute range for the following only if the src_reg is known.
>>> +	/* Compute range for MUL if at least one of its registers is known.
>>>   	 */
>>>   	case BPF_MUL:
>>> -		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>> +		if (src_known || (dst_known && valid_known_dst))
>>> +			return COMPUTABLE_RANGE;
>>> +		break;
>> Is it even necessary to restrict src or dst to be known?
>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>
>> 	case BPF_MUL:
>> 		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>> 		scalar32_min_max_mul(dst_reg, &src_reg);
>> 		scalar_min_max_mul(dst_reg, &src_reg);
>> 		break;
>>
>> Where tnum_mul() refers to a paper, and that paper does not restrict
>> abstract multiplication algorithm to constant values on either side.
>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>> - if both src and dst are positive
>> - if overflow is not possible
>> - adjust dst->min *= src->min
>> - adjust dst->max *= src->max
>>
>> I think this should work just fine if neither of src or dst is a known constant.
>> What do you think?
>>
> With the refactor this looked like an armless change. Indeed if we agree
> that the algorithm covers all scenarios, then why not.
> I did not study the paper or the scalar_min_max_mul function nearly
> enough to know for sure.

I double checked and I think Eduard is correct. src_known checking
is not necessary for multiplication. It would be great if you can
add this change as well in the patch set.

>> [...]

Re: [PATCH bpf-next v2 4/5] bpf/verifier: relax MUL range computation check

[Cupertino Miranda]

Yonghong Song writes:

> On 4/19/24 2:47 AM, Cupertino Miranda wrote:
>> Eduard Zingerman writes:
>>
>>> On Wed, 2024-04-17 at 13:23 +0100, Cupertino Miranda wrote:
>>>
>>> [...]
>>>
>>>>   static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>> +					    struct bpf_reg_state dst_reg,
>>>>   					    struct bpf_reg_state src_reg)
>>> Nit: there is no need to pass {dst,src}_reg by value,
>>>       struct bpf_reg_state is 120 bytes in size
>>>      (but maybe compiler handles this).
>>>
>>>>   {
>>>> -	bool src_known;
>>>> +	bool src_known, dst_known;
>>>>   	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
>>>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>>>   	u8 opcode = BPF_OP(insn->code);
>>>>
>>>> -	bool valid_known = true;
>>>> -	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known);
>>>> +	bool valid_known_src = true;
>>>> +	bool valid_known_dst = true;
>>>> +	src_known = is_const_reg_and_valid(src_reg, alu32, &valid_known_src);
>>>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known_dst);
>>>>
>>>>   	/* Taint dst register if offset had invalid bounds
>>>>   	 * derived from e.g. dead branches.
>>>>   	 */
>>>> -	if (valid_known == false)
>>>> +	if (valid_known_src == false)
>>>>   		return UNCOMPUTABLE_RANGE;
>>>>
>>>>   	switch (opcode) {
>>>> @@ -13457,10 +13460,12 @@ static int is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
>>>>   	case BPF_OR:
>>>>   		return COMPUTABLE_RANGE;
>>>>
>>>> -	/* Compute range for the following only if the src_reg is known.
>>>> +	/* Compute range for MUL if at least one of its registers is known.
>>>>   	 */
>>>>   	case BPF_MUL:
>>>> -		return src_known ? COMPUTABLE_RANGE : UNCOMPUTABLE_RANGE;
>>>> +		if (src_known || (dst_known && valid_known_dst))
>>>> +			return COMPUTABLE_RANGE;
>>>> +		break;
>>> Is it even necessary to restrict src or dst to be known?
>>> adjust_scalar_min_max_vals() logic for multiplication looks as follows:
>>>
>>> 	case BPF_MUL:
>>> 		dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off);
>>> 		scalar32_min_max_mul(dst_reg, &src_reg);
>>> 		scalar_min_max_mul(dst_reg, &src_reg);
>>> 		break;
>>>
>>> Where tnum_mul() refers to a paper, and that paper does not restrict
>>> abstract multiplication algorithm to constant values on either side.
>>> The scalar_min_max_mul() and scalar32_min_max_mul() are similar:
>>> - if both src and dst are positive
>>> - if overflow is not possible
>>> - adjust dst->min *= src->min
>>> - adjust dst->max *= src->max
>>>
>>> I think this should work just fine if neither of src or dst is a known constant.
>>> What do you think?
>>>
>> With the refactor this looked like an armless change. Indeed if we agree
>> that the algorithm covers all scenarios, then why not.
>> I did not study the paper or the scalar_min_max_mul function nearly
>> enough to know for sure.
>
> I double checked and I think Eduard is correct. src_known checking
> is not necessary for multiplication. It would be great if you can
> add this change as well in the patch set.
Sure! Thanks for confirming this.
>
>>> [...]