[PATCH bpf-next 1/3] bpf: fix to XOR and OR range computation

[PATCH bpf-next 1/3] bpf: fix to 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 seems excessive, relative to how easy it is to compute a
safe range for these operators.

BPF self-tests were added to validate the new functionality.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
---
 kernel/bpf/verifier.c                         |  3 +-
 .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
 2 files changed, 66 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2aad6d90550f..a219f601569a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13764,7 +13764,8 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	}
 
 	if (!src_known &&
-	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
+	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND &&
+	    opcode != BPF_XOR && opcode != BPF_OR) {
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
 	}
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 960998f16306..2fcf46341b30 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.30.2

[PATCH bpf-next 2/3] bpf: 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>
---
 kernel/bpf/verifier.c | 141 +++++++++++++++++++++++-------------------
 1 file changed, 77 insertions(+), 64 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index a219f601569a..7894af2e1bdb 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13709,6 +13709,82 @@ 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;
+}
+
+static bool is_safe_to_compute_dst_reg_ranges(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 false;
+
+	switch (opcode) {
+	case BPF_ADD:
+	case BPF_SUB:
+	case BPF_AND:
+	case BPF_XOR:
+	case BPF_OR:
+		return true;
+
+	/* Compute range for MUL if the src_reg is known.
+	 */
+	case BPF_MUL:
+		return src_known;
+
+	/* 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:
+		return src_known && (src_reg.umax_value < insn_bitness);
+	default:
+		break;
+	}
+
+	return false;
+}
+
 /* 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.
@@ -13720,52 +13796,10 @@ 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 &&
-	    opcode != BPF_XOR && opcode != BPF_OR) {
+	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
 	}
@@ -13822,39 +13856,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.30.2

[PATCH bpf-next 3/3] bpf: relax MUL range computation check

[Cupertino Miranda]

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

BPF self-tests were added to check the new functionality.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
---
 kernel/bpf/verifier.c                         | 10 +-
 .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
 2 files changed, 105 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7894af2e1bdb..a326ec024d82 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13741,15 +13741,17 @@ static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
 }
 
 static bool is_safe_to_compute_dst_reg_ranges(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);
+	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);
 
 	/* Taint dst register if offset had invalid bounds
 	 * derived from e.g. dead branches.
@@ -13765,10 +13767,10 @@ static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
 	case BPF_OR:
 		return true;
 
-	/* Compute range for MUL if the src_reg is known.
+	/* Compute range for MUL if at least one of its registers is know.
 	 */
 	case BPF_MUL:
-		return src_known;
+		return src_known || dst_known;
 
 	/* Shift operators range is only computable if shift dimension operand
 	 * is known. Also, shifts greater than 31 or 63 are undefined. This
@@ -13799,7 +13801,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
 	int ret;
 
-	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
+	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
 	}
diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 2fcf46341b30..09bb1b270ca7 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.30.2

Re: [PATCH bpf-next 1/3] bpf: fix to XOR and OR range computation

[Yonghong Song]

On 4/11/24 10:37 AM, 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 seems excessive, relative to how easy it is to compute a
> safe range for these operators.

Please break this patch into two patches. One for verifier and another
for selftest. This will make it easy for possible backport.

As the number of patches grows, it would be great if you can add
a cover letter for the series.

For the subject, the following seems better:
    improve XOR and OR range computation

I would not call the previous implementation as a bug. It is just
conservative.

For the following:
   This condition seems excessive, relative to how easy it is to compute a
   safe range for these operators.

You can just say:
   This condition is unnecessary, and the following XOR/OR operator handling
   could compute a possible better range.

>
> BPF self-tests were added to validate the new functionality.
>
> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
> ---
>   kernel/bpf/verifier.c                         |  3 +-
>   .../selftests/bpf/progs/verifier_bounds.c     | 64 +++++++++++++++++++
>   2 files changed, 66 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 2aad6d90550f..a219f601569a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13764,7 +13764,8 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   	}
>   
>   	if (!src_known &&
> -	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
> +	    opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND &&
> +	    opcode != BPF_XOR && opcode != BPF_OR) {
>   		__mark_reg_unknown(env, dst_reg);
>   		return 0;
>   	}
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
> index 960998f16306..2fcf46341b30 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 2/3] bpf: refactor checks for range computation

[Yonghong Song]

On 4/11/24 10:37 AM, Cupertino Miranda wrote:
> 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>
> ---
>   kernel/bpf/verifier.c | 141 +++++++++++++++++++++++-------------------
>   1 file changed, 77 insertions(+), 64 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index a219f601569a..7894af2e1bdb 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13709,6 +13709,82 @@ 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;

*valid = false;

> +	} else {
> +		if ((known &&
> +		     (smin_val != smax_val || umin_val != umax_val)) ||
> +		    smin_val > smax_val || umin_val > umax_val)
> +			*valid &= false;

*valid = false;

> +	}
> +
> +	return known;
> +}
> +
> +static bool is_safe_to_compute_dst_reg_ranges(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 false;
> +
> +	switch (opcode) {
> +	case BPF_ADD:
> +	case BPF_SUB:
> +	case BPF_AND:
> +	case BPF_XOR:
> +	case BPF_OR:
> +		return true;
> +
> +	/* Compute range for MUL if the src_reg is known.
> +	 */
> +	case BPF_MUL:
> +		return src_known;
> +
> +	/* 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:
> +		return src_known && (src_reg.umax_value < insn_bitness);
> +	default:
> +		break;
> +	}
> +
> +	return false;
> +}
> +
>   /* 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.
> @@ -13720,52 +13796,10 @@ 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 &&
> -	    opcode != BPF_XOR && opcode != BPF_OR) {
> +	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
>   		__mark_reg_unknown(env, dst_reg);

This is not a precise refactoring. there are some cases like below
which uses mark_reg_unknow().

Let us put the refactoring patch as the first patch in the serious and all
additional changes after that and this will make it easy to review.

>   		return 0;
>   	}
> @@ -13822,39 +13856,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

Re: [PATCH bpf-next 3/3] bpf: relax MUL range computation check

[Yonghong Song]

On 4/11/24 10:37 AM, Cupertino Miranda wrote:
> MUL instruction required that src_reg would be a known value (i.e.
> src_reg would be evaluate as a const value). The condition in this case
> can be relaxed, since multiplication is a commutative operator and the
> range computation is still valid if at least one of its registers is
> known.
>
> BPF self-tests were added to check the new functionality.
>
> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
> ---
>   kernel/bpf/verifier.c                         | 10 +-
>   .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
>   2 files changed, 105 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 7894af2e1bdb..a326ec024d82 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13741,15 +13741,17 @@ static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
>   }
>   
>   static bool is_safe_to_compute_dst_reg_ranges(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);
> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);

Is it a possible the above could falsely reject some operation since
in the original code, dst_reg is not checked here?

>   
>   	/* Taint dst register if offset had invalid bounds
>   	 * derived from e.g. dead branches.
> @@ -13765,10 +13767,10 @@ static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
>   	case BPF_OR:
>   		return true;
>   
> -	/* Compute range for MUL if the src_reg is known.
> +	/* Compute range for MUL if at least one of its registers is know.

know => known

>   	 */
>   	case BPF_MUL:
> -		return src_known;
> +		return src_known || dst_known;
>   
>   	/* Shift operators range is only computable if shift dimension operand
>   	 * is known. Also, shifts greater than 31 or 63 are undefined. This
> @@ -13799,7 +13801,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>   	int ret;
>   
> -	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
> +	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
>   		__mark_reg_unknown(env, dst_reg);
>   		return 0;
>   	}
> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c

Let us break this commit into two patches: verifier change and selftest change. This will make possible backport easier.

> index 2fcf46341b30..09bb1b270ca7 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);
>   }
>   
[...]

Re: [PATCH bpf-next 3/3] bpf: relax MUL range computation check

[Cupertino Miranda]

Hi Yonghong,

Thanks for the reviews. I will prepare a patch series with your
recomendations soon.

> On 4/11/24 10:37 AM, Cupertino Miranda wrote:
>> MUL instruction required that src_reg would be a known value (i.e.
>> src_reg would be evaluate as a const value). The condition in this case
>> can be relaxed, since multiplication is a commutative operator and the
>> range computation is still valid if at least one of its registers is
>> known.
>>
>> BPF self-tests were added to check the new functionality.
>>
>> Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
>> ---
>>   kernel/bpf/verifier.c                         | 10 +-
>>   .../selftests/bpf/progs/verifier_bounds.c     | 99 +++++++++++++++++++
>>   2 files changed, 105 insertions(+), 4 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 7894af2e1bdb..a326ec024d82 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -13741,15 +13741,17 @@ static bool is_const_reg_and_valid(struct bpf_reg_state reg, bool alu32,
>>   }
>>     static bool is_safe_to_compute_dst_reg_ranges(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);
>> +	dst_known = is_const_reg_and_valid(dst_reg, alu32, &valid_known);
>
> Is it a possible the above could falsely reject some operation since
> in the original code, dst_reg is not checked here?
I guess, I believe in the case where min/max information is not matching
tnum value/mask, when the value is known.
My thoguht was that there would be no arm, since it could not
rely on that known value to compute MUL ranges anyway.
Still, I just realized this applies for all the other expressions, so
indeed it is rejecting and need some more patching.

>>     	/* Taint dst register if offset had invalid bounds
>>   	 * derived from e.g. dead branches.
>> @@ -13765,10 +13767,10 @@ static bool is_safe_to_compute_dst_reg_ranges(struct bpf_insn *insn,
>>   	case BPF_OR:
>>   		return true;
>>   -	/* Compute range for MUL if the src_reg is known.
>> +	/* Compute range for MUL if at least one of its registers is know.
>
> know => known
>
>>   	 */
>>   	case BPF_MUL:
>> -		return src_known;
>> +		return src_known || dst_known;
>>     	/* Shift operators range is only computable if shift dimension operand
>>   	 * is known. Also, shifts greater than 31 or 63 are undefined. This
>> @@ -13799,7 +13801,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
>>   	bool alu32 = (BPF_CLASS(insn->code) != BPF_ALU64);
>>   	int ret;
>>   -	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
>> +	if (!is_safe_to_compute_dst_reg_ranges(insn, *dst_reg, src_reg)) {
>>   		__mark_reg_unknown(env, dst_reg);
>>   		return 0;
>>   	}
>> diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
>
> Let us break this commit into two patches: verifier change and selftest change. This will make possible backport easier.
>
>> index 2fcf46341b30..09bb1b270ca7 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);
>>   }
>>
> [...]

Re: [PATCH bpf-next 2/3] bpf: refactor checks for range computation

[Cupertino Miranda]

Yonghong Song writes:

> On 4/11/24 10:37 AM, Cupertino Miranda wrote:
>> 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>
>> ---
>>   kernel/bpf/verifier.c | 141 +++++++++++++++++++++++-------------------
>>   1 file changed, 77 insertions(+), 64 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index a219f601569a..7894af2e1bdb 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -13709,6 +13709,82 @@ 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;
>
> *valid = false;
>
>> +	} else {
>> +		if ((known &&
>> +		     (smin_val != smax_val || umin_val != umax_val)) ||
>> +		    smin_val > smax_val || umin_val > umax_val)
>> +			*valid &= false;
>
> *valid = false;
>
>> +	}
>> +
>> +	return known;
>> +}
>> +
>> +static bool is_safe_to_compute_dst_reg_ranges(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 false;
>> +
>> +	switch (opcode) {
>> +	case BPF_ADD:
>> +	case BPF_SUB:
>> +	case BPF_AND:
>> +	case BPF_XOR:
>> +	case BPF_OR:
>> +		return true;
>> +
>> +	/* Compute range for MUL if the src_reg is known.
>> +	 */
>> +	case BPF_MUL:
>> +		return src_known;
>> +
>> +	/* 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:
>> +		return src_known && (src_reg.umax_value < insn_bitness);
>> +	default:
>> +		break;
>> +	}
>> +
>> +	return false;
>> +}
>> +
>>   /* 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.
>> @@ -13720,52 +13796,10 @@ 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 &&
>> -	    opcode != BPF_XOR && opcode != BPF_OR) {
>> +	if (!is_safe_to_compute_dst_reg_ranges(insn, src_reg)) {
>>   		__mark_reg_unknown(env, dst_reg);
>
> This is not a precise refactoring. there are some cases like below
> which uses mark_reg_unknow().
Oh, right I miss those underscores above. :(
Will make sure to cover that.
>
> Let us put the refactoring patch as the first patch in the serious and all
> additional changes after that and this will make it easy to review.
>
>>   		return 0;
>>   	}
>> @@ -13822,39 +13856,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