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

Commit Message

Cupertino Miranda April 29, 2024, 9:22 p.m. UTC

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 <[e-mail]>
Cc: Yonghong Song <[e-mail]>
Cc: Alexei Starovoitov <[e-mail]>
Cc: David Faust <[e-mail]>
Cc: Jose Marchesi <[e-mail]>
Cc: Elena Zannoni <[e-mail]>
Cc: Andrii Nakryiko <[e-mail]>
Cc: Eduard Zingerman <[e-mail]>
---
 kernel/bpf/verifier.c | 42 ++++++++++--------------------------------
 1 file changed, 10 insertions(+), 32 deletions(-)

Comments

Eduard Zingerman April 29, 2024, 11:16 p.m. UTC | #1

[...]


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

[...]

Eduard Zingerman April 29, 2024, 11:29 p.m. UTC | #2

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

Eduard Zingerman April 30, 2024, 4:48 p.m. UTC | #3

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 <[e-mail]>

Patch

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: