[PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Cupertino Miranda]

Hi everyone,

New version.
There is one extra patch which implements some code improvements
suggested by Andrii.

Thanks for your reviews!

Regards,
Cupertino

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

Changes from v2:
 - Added a patch to replace mark_reg_unknowon for __mark_reg_unknown in
   the context of range computation.
 - Reverted implementation of refactor to v1 which used a simpler
   boolean return value in check function.
 - Further relaxed MUL to allow it to still compute a range when neither
   of its registers is a known value.
 - Simplified tests based on Eduards example.
 - Added messages in selftest commits.

Changes from v3:
 - Improved commit message of patch nr 1.
 - Coding style fixes.
 - Improve XOR and OR tests.
 - Made function calls to pass struct bpf_reg_state pointer instead.
 - Improved final code as a last patch.

Cupertino Miranda (7):
  bpf/verifier: replace calls to mark_reg_unknown.
  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.
  bpf/verifier: improve code after range computation recent changes.

 kernel/bpf/verifier.c                         | 111 ++++++++----------
 .../selftests/bpf/progs/verifier_bounds.c     |  63 ++++++++++
 2 files changed, 109 insertions(+), 65 deletions(-)

-- 
2.39.2

[PATCH bpf-next v4 1/7] bpf/verifier: replace calls to mark_reg_unknown.

[Cupertino Miranda]

In order to further simplify the code in adjust_scalar_min_max_vals all
the calls to mark_reg_unknown are replaced by __mark_reg_unknown.

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 to
adjust_scalar_min_max_vals(), because it 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.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 kernel/bpf/verifier.c | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5a7e34e83a5b..6fe641c8ae33 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13704,7 +13704,6 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 				      struct bpf_reg_state *dst_reg,
 				      struct bpf_reg_state src_reg)
 {
-	struct bpf_reg_state *regs = cur_regs(env);
 	u8 opcode = BPF_OP(insn->code);
 	bool src_known;
 	s64 smin_val, smax_val;
@@ -13811,7 +13810,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 			/* Shifts greater than 31 or 63 are undefined.
 			 * This includes shifts by a negative number.
 			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
+			__mark_reg_unknown(env, dst_reg);
 			break;
 		}
 		if (alu32)
@@ -13824,7 +13823,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 			/* Shifts greater than 31 or 63 are undefined.
 			 * This includes shifts by a negative number.
 			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
+			__mark_reg_unknown(env, dst_reg);
 			break;
 		}
 		if (alu32)
@@ -13837,7 +13836,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 			/* Shifts greater than 31 or 63 are undefined.
 			 * This includes shifts by a negative number.
 			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
+			__mark_reg_unknown(env, dst_reg);
 			break;
 		}
 		if (alu32)
@@ -13846,7 +13845,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 			scalar_min_max_arsh(dst_reg, &src_reg);
 		break;
 	default:
-		mark_reg_unknown(env, regs, insn->dst_reg);
+		__mark_reg_unknown(env, dst_reg);
 		break;
 	}
 
-- 
2.39.2

[PATCH bpf-next v4 2/7] 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>
Acked-by: Eduard Zingerman <eddyz87@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 kernel/bpf/verifier.c | 136 ++++++++++++++++++++++--------------------
 1 file changed, 72 insertions(+), 64 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6fe641c8ae33..1777ab00068b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13695,6 +13695,77 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
 	__update_reg_bounds(dst_reg);
 }
 
+static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
+				tnum_is_const(reg->var_off);
+
+	if (alu32) {
+		if ((is_const &&
+		     (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 ((is_const &&
+		     (smin_val != smax_val || umin_val != umax_val)) ||
+		    smin_val > smax_val || umin_val > umax_val)
+			*valid = false;
+	}
+
+	return is_const;
+}
+
+static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
+					     const struct bpf_reg_state *src_reg)
+{
+	bool src_is_const;
+	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
+	bool valid_const = true;
+
+	src_is_const = is_const_reg_and_valid(src_reg, insn_bitness == 32,
+					      &valid_const);
+
+	/* Taint dst register if offset had invalid bounds
+	 * derived from e.g. dead branches.
+	 */
+	if (valid_const == false)
+		return false;
+
+	switch (BPF_OP(insn->code)) {
+	case BPF_ADD:
+	case BPF_SUB:
+	case BPF_AND:
+		return true;
+
+	/* Compute range for the following only if the src_reg is const.
+	 */
+	case BPF_XOR:
+	case BPF_OR:
+	case BPF_MUL:
+		return src_is_const;
+
+	/* Shift operators range is only computable if shift dimension operand
+	 * is a constant. 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_is_const && src_reg->umax_value < insn_bitness);
+	default:
+		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.
@@ -13705,51 +13776,10 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 				      struct bpf_reg_state src_reg)
 {
 	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) {
+	if (!is_safe_to_compute_dst_reg_range(insn, &src_reg)) {
 		__mark_reg_unknown(env, dst_reg);
 		return 0;
 	}
@@ -13806,46 +13836,24 @@ 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, 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, 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, dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_arsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_arsh(dst_reg, &src_reg);
 		break;
 	default:
-		__mark_reg_unknown(env, dst_reg);
 		break;
 	}
 
-- 
2.39.2

Re: [PATCH bpf-next v4 2/7] bpf/verifier: refactor checks for range computation

[Eduard Zingerman]

[...]

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 6fe641c8ae33..1777ab00068b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13695,6 +13695,77 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>  	__update_reg_bounds(dst_reg);
>  }
>  
> +static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
> +				tnum_is_const(reg->var_off);
> +

Nit:
Sorry for missing this earlier, should we initialize 'valid' here? e.g.:

	*valid = true;

I understand that it is initialized upper in the stack,
but setting it here seems better.

> +	if (alu32) {
> +		if ((is_const &&
> +		     (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 ((is_const &&
> +		     (smin_val != smax_val || umin_val != umax_val)) ||
> +		    smin_val > smax_val || umin_val > umax_val)
> +			*valid = false;
> +	}
> +
> +	return is_const;
> +}

[...]

Re: [PATCH bpf-next v4 2/7] bpf/verifier: refactor checks for range computation

[Cupertino Miranda]

Eduard Zingerman writes:

> [...]
>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 6fe641c8ae33..1777ab00068b 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -13695,6 +13695,77 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>>  	__update_reg_bounds(dst_reg);
>>  }
>>
>> +static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
>> +				tnum_is_const(reg->var_off);
>> +
>
> Nit:
> Sorry for missing this earlier, should we initialize 'valid' here? e.g.:
>
> 	*valid = true;
>
> I understand that it is initialized upper in the stack,
> but setting it here seems better.
>

With the last patch and the suggestions of Andrii this code gets
removed.
Should we we keep having this small changes? :-)

Also the function was left like this on purpose since the original idea
was that it could be used multiple times for different registers and only
verified once, after calling for both src and dst.
It was in the context to verify that either the src or dst in MUL was a
const. That was further relaxed and aagain with the last patch it
removes the argument completelly.

Hope that it is Ok.


>> +	if (alu32) {
>> +		if ((is_const &&
>> +		     (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 ((is_const &&
>> +		     (smin_val != smax_val || umin_val != umax_val)) ||
>> +		    smin_val > smax_val || umin_val > umax_val)
>> +			*valid = false;
>> +	}
>> +
>> +	return is_const;
>> +}
>
> [...]

Re: [PATCH bpf-next v4 2/7] bpf/verifier: refactor checks for range computation

[Alexei Starovoitov]

On Tue, Apr 30, 2024 at 12:17 AM Cupertino Miranda
<cupertino.miranda@oracle.com> wrote:
>
>
> Eduard Zingerman writes:
>
> > [...]
> >
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index 6fe641c8ae33..1777ab00068b 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -13695,6 +13695,77 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
> >>      __update_reg_bounds(dst_reg);
> >>  }
> >>
> >> +static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
> >> +                            tnum_is_const(reg->var_off);
> >> +
> >
> > Nit:
> > Sorry for missing this earlier, should we initialize 'valid' here? e.g.:
> >
> >       *valid = true;
> >
> > I understand that it is initialized upper in the stack,
> > but setting it here seems better.
> >
>
> With the last patch and the suggestions of Andrii this code gets
> removed.
> Should we we keep having this small changes? :-)

Pls avoid this churn.
Don't add something in patch 2 just to delete it in patch 8.

pw-bot: cr

[PATCH bpf-next v4 3/7] 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.

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

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com
Acked-by: Eduard Zingerman <eddyz87@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.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 1777ab00068b..54aca9b377a4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13744,12 +13744,12 @@ static bool 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 true;
 
 	/* Compute range for the following only if the src_reg is const.
 	 */
-	case BPF_XOR:
-	case BPF_OR:
 	case BPF_MUL:
 		return src_is_const;
 
-- 
2.39.2

[PATCH bpf-next v4 4/7] selftests/bpf: XOR and OR range computation tests.

[Cupertino Miranda]

Added a test for bound computation in XOR and OR when non constant
values are used and both registers have bounded ranges.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 42 +++++++++++++++++++
 1 file changed, 42 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 960998f16306..7d570acf23ee 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -885,6 +885,48 @@ l1_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for non const xor src dst")
+__success __log_level(2)
+__msg("5: (af) r0 ^= r6                      ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=431,var_off=(0x0; 0x1af))")
+__naked void non_const_xor_src_dst(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 &= 0xaf;					\
+	r0 &= 0x1a0;					\
+	r0 ^= r6;					\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	__imm_addr(map_hash_8b),
+	__imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("bounds check for non const or src dst")
+__success __log_level(2)
+__msg("5: (4f) r0 |= r6                      ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=431,var_off=(0x0; 0x1af))")
+__naked void non_const_or_src_dst(void)
+{
+	asm volatile ("					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 = r0;					\
+	call %[bpf_get_prandom_u32];                    \
+	r6 &= 0xaf;					\
+	r0 &= 0x1a0;					\
+	r0 |= r6;					\
+	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 v4 5/7] 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 the range computation algorithm used in current code
already supports a proper range computation for any valid range value on
its operands.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Acked-by: Andrii Nakryiko <andrii.nakryiko@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 kernel/bpf/verifier.c | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 54aca9b377a4..b6344cead2e2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13746,12 +13746,8 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 	case BPF_AND:
 	case BPF_XOR:
 	case BPF_OR:
-		return true;
-
-	/* Compute range for the following only if the src_reg is const.
-	 */
 	case BPF_MUL:
-		return src_is_const;
+		return true;
 
 	/* Shift operators range is only computable if shift dimension operand
 	 * is a constant. Shifts greater than 31 or 63 are undefined. This
-- 
2.39.2

[PATCH bpf-next v4 6/7] selftests/bpf: MUL range computation tests.

[Cupertino Miranda]

Added a test for bound computation in MUL when non constant
values are used and both registers have bounded ranges.

Signed-off-by: Cupertino Miranda <cupertino.miranda@oracle.com>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Acked-by: Andrii Nakryiko <andrii.nakryiko@gmail.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>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
---
 .../selftests/bpf/progs/verifier_bounds.c     | 21 +++++++++++++++++++
 1 file changed, 21 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_bounds.c b/tools/testing/selftests/bpf/progs/verifier_bounds.c
index 7d570acf23ee..a0bb7fb40ea5 100644
--- a/tools/testing/selftests/bpf/progs/verifier_bounds.c
+++ b/tools/testing/selftests/bpf/progs/verifier_bounds.c
@@ -927,6 +927,27 @@ __naked void non_const_or_src_dst(void)
 	: __clobber_all);
 }
 
+SEC("socket")
+__description("bounds check for non const mul regs")
+__success __log_level(2)
+__msg("5: (2f) r0 *= r6                      ; R0_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=3825,var_off=(0x0; 0xfff))")
+__naked void non_const_mul_regs(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);
+}
+
 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 v4 7/7] bpf/verifier: improve code after range computation recent changes.

[Cupertino Miranda]

Recent changes in range computation had simplified code making some
checks unnecessary. This patch improves the code taking in consideration
those changes.

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>
Cc: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Cc: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 42 ++++++++++--------------------------------
 1 file changed, 10 insertions(+), 32 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b6344cead2e2..a6fd10b119ba 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -13695,33 +13695,19 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
 	__update_reg_bounds(dst_reg);
 }
 
-static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
-				tnum_is_const(reg->var_off);
-
+static bool is_valid_const_reg(const struct bpf_reg_state *reg, bool alu32)
+{
 	if (alu32) {
-		if ((is_const &&
-		     (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;
+		if (tnum_subreg_is_const(reg->var_off))
+			return reg->s32_min_value == reg->s32_max_value &&
+			       reg->u32_min_value == reg->u32_max_value;
 	} else {
-		if ((is_const &&
-		     (smin_val != smax_val || umin_val != umax_val)) ||
-		    smin_val > smax_val || umin_val > umax_val)
-			*valid = false;
+		if (tnum_is_const(reg->var_off))
+			return reg->smin_value == reg->smax_value &&
+			       reg->umin_value == reg->umax_value;
 	}
 
-	return is_const;
+	return false;
 }
 
 static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
@@ -13729,16 +13715,8 @@ static bool is_safe_to_compute_dst_reg_range(struct bpf_insn *insn,
 {
 	bool src_is_const;
 	u64 insn_bitness = (BPF_CLASS(insn->code) == BPF_ALU64) ? 64 : 32;
-	bool valid_const = true;
 
-	src_is_const = is_const_reg_and_valid(src_reg, insn_bitness == 32,
-					      &valid_const);
-
-	/* Taint dst register if offset had invalid bounds
-	 * derived from e.g. dead branches.
-	 */
-	if (valid_const == false)
-		return false;
+	src_is_const = is_valid_const_reg(src_reg, insn_bitness == 32);
 
 	switch (BPF_OP(insn->code)) {
 	case BPF_ADD:
-- 
2.39.2

Re: [PATCH bpf-next v4 7/7] bpf/verifier: improve code after range computation recent changes.

[Eduard Zingerman]

[...]


> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b6344cead2e2..a6fd10b119ba 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -13695,33 +13695,19 @@ static void scalar_min_max_arsh(struct bpf_reg_state *dst_reg,
>  	__update_reg_bounds(dst_reg);
>  }
>  
> -static bool is_const_reg_and_valid(const 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 is_const = alu32 ? tnum_subreg_is_const(reg->var_off) :
> -				tnum_is_const(reg->var_off);
> -
> +static bool is_valid_const_reg(const struct bpf_reg_state *reg, bool alu32)
> +{
>  	if (alu32) {
> -		if ((is_const &&
> -		     (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;

This check first originated in the following commit from 2018:

6f16101e6a8b ("bpf: mark dst unknown on inconsistent {s, u}bounds adjustments")

Back then it was added to handle the following program:

  0: (b7) r0 = 0
  1: (d5) if r0 s<= 0x0 goto pc+0          <---- note pc+0 here
   R0=inv0 R1=ctx(id=0,off=0,imm=0) R10=fp0
  2: (1f) r0 -= r1
   R0=inv0 R1=ctx(id=0,off=0,imm=0) R10=fp0
  verifier internal error: known but bad sbounds

Apparently, verifier visited both conditional branches for this program
deducing impossible bounds for the 'false' branch.
Nowadays is_scalar_branch_taken() should handle such situations w/o issues.
Still, I'm not sure if we want to remove this safety check.

[...]

Re: [PATCH bpf-next v4 7/7] bpf/verifier: improve code after range computation recent changes.

[Eduard Zingerman]

On Mon, 2024-04-29 at 16:16 -0700, Eduard Zingerman wrote:
[...]

> Still, I'm not sure if we want to remove this safety check.

... and if we are going to remove the safety check,
then at-least there should be a warning like there was before the
commit from 2018. Which is almost the same amount of code as current
'check + invalid flag'.

Re: [PATCH bpf-next v4 7/7] bpf/verifier: improve code after range computation recent changes.

[Eduard Zingerman]

On Mon, 2024-04-29 at 16:29 -0700, Eduard Zingerman wrote:
> On Mon, 2024-04-29 at 16:16 -0700, Eduard Zingerman wrote:
> [...]
> 
> > Still, I'm not sure if we want to remove this safety check.
> 
> ... and if we are going to remove the safety check,
> then at-least there should be a warning like there was before the
> commit from 2018. Which is almost the same amount of code as current
> 'check + invalid flag'.

My bad. I've been reminded by Yonghong that adjust_reg_min_max_vals()
is called from check_alu_op(), which does reg_bounds_sanity_check()
upon return.

This patch is fine and there is also no need to change anything in
patch #2, as it would be removed. Sorry for the noise.

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

Re: [PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Cupertino Miranda]

Hi everyone,

I wonder if there is anything else to do for this patch series.
Alexei: Without that later removed change in patch 2, the intermediate
state of the patches does not properly work. Eduard refered to that and
agreed in the review for patch 7.

Best regards,
Cupertino

Cupertino Miranda writes:

> Hi everyone,
>
> New version.
> There is one extra patch which implements some code improvements
> suggested by Andrii.
>
> Thanks for your reviews!
>
> Regards,
> Cupertino
>
> Changes from v1:
>  - Reordered patches in the series.
>  - Fix refactor to be acurate with original code.
>  - Fixed other mentioned small problems.
>
> Changes from v2:
>  - Added a patch to replace mark_reg_unknowon for __mark_reg_unknown in
>    the context of range computation.
>  - Reverted implementation of refactor to v1 which used a simpler
>    boolean return value in check function.
>  - Further relaxed MUL to allow it to still compute a range when neither
>    of its registers is a known value.
>  - Simplified tests based on Eduards example.
>  - Added messages in selftest commits.
>
> Changes from v3:
>  - Improved commit message of patch nr 1.
>  - Coding style fixes.
>  - Improve XOR and OR tests.
>  - Made function calls to pass struct bpf_reg_state pointer instead.
>  - Improved final code as a last patch.
>
> Cupertino Miranda (7):
>   bpf/verifier: replace calls to mark_reg_unknown.
>   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.
>   bpf/verifier: improve code after range computation recent changes.
>
>  kernel/bpf/verifier.c                         | 111 ++++++++----------
>  .../selftests/bpf/progs/verifier_bounds.c     |  63 ++++++++++
>  2 files changed, 109 insertions(+), 65 deletions(-)

Re: [PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Alexei Starovoitov]

On Fri, May 3, 2024 at 7:14 AM Cupertino Miranda
<cupertino.miranda@oracle.com> wrote:
>
>
> Hi everyone,
>
> I wonder if there is anything else to do for this patch series.
> Alexei: Without that later removed change in patch 2, the intermediate
> state of the patches does not properly work. Eduard refered to that and
> agreed in the review for patch 7.

Sorry, but I insist that the patches are done in the way that
they don't introduce churn.

Re: [PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Cupertino Miranda]

Is it Ok to reduce all this to 2 patches.
One with the verifier changes and another with selftests.

Alexei Starovoitov writes:

> On Fri, May 3, 2024 at 7:14 AM Cupertino Miranda
> <cupertino.miranda@oracle.com> wrote:
>>
>>
>> Hi everyone,
>>
>> I wonder if there is anything else to do for this patch series.
>> Alexei: Without that later removed change in patch 2, the intermediate
>> state of the patches does not properly work. Eduard refered to that and
>> agreed in the review for patch 7.
>
> Sorry, but I insist that the patches are done in the way that
> they don't introduce churn.

Re: [PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Eduard Zingerman]

On Fri, 2024-05-03 at 17:42 +0100, Cupertino Miranda wrote:
> Is it Ok to reduce all this to 2 patches.
> One with the verifier changes and another with selftests.

Hi Miranda,

I think Alexei meant that patch #7 could be moved to the beginning of the patch-set.
Which would simplify patch #2.
The main logical structure of the series makes sense to me, I think we should keep it:
- replace calls to mark_reg_unknown
>> do equivalent of patch #7 here, remove unnecessary checks <<
- refactor checks for range computation (factor out is_safe_to_compute_dst_reg_range)
- improve XOR and OR range computation
- XOR and OR range computation tests
- relax MUL range computation check
- MUL range computation tests

Re: [PATCH bpf-next v4 0/7] bpf/verifier: range computation improvements

[Cupertino Miranda]

Eduard Zingerman writes:

> On Fri, 2024-05-03 at 17:42 +0100, Cupertino Miranda wrote:
>> Is it Ok to reduce all this to 2 patches.
>> One with the verifier changes and another with selftests.
>
> Hi Miranda,
>
> I think Alexei meant that patch #7 could be moved to the beginning of the patch-set.
> Which would simplify patch #2.
> The main logical structure of the series makes sense to me, I think we should keep it:
> - replace calls to mark_reg_unknown
>>> do equivalent of patch #7 here, remove unnecessary checks <<
> - refactor checks for range computation (factor out is_safe_to_compute_dst_reg_range)
> - improve XOR and OR range computation
> - XOR and OR range computation tests
> - relax MUL range computation check
> - MUL range computation tests

Ok, I will reorganize the code for this.

Thanks,
Cupertino