UBSAN: shift-out-of-bounds in ___bpf_prog_run

UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2

shift exponent 248 is too large for 32-bit type 'unsigned int'

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

      check in ___bpf_prog_run().

thanks

kind regards

Kurt

  kernel/bpf/verifier.c | 30 +++++++++---------------------
  1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
  	u32_min_val = src_reg.u32_min_value;

kernel/bpf/verifier.c +1 -0

+
  	if (alu32) {
  		src_known = tnum_subreg_is_const(src_reg.var_off);
  		if ((src_known &&

kernel/bpf/verifier.c +0 -14

  		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

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

      check in ___bpf_prog_run().

thanks

kind regards

Kurt

  kernel/bpf/verifier.c | 30 +++++++++---------------------
  1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
      u32_min_val = src_reg.u32_min_value;
      u32_max_val = src_reg.u32_max_value;
 

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

the following code though:

         if (!src_known &&
             opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                 __mark_reg_unknown(env, dst_reg);
                 return 0;
         }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
      if (alu32) {
              src_known = tnum_subreg_is_const(src_reg.var_off);
              if ((src_known &&

@@ -7592,39 +7601,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;

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 47 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

       check in ___bpf_prog_run().

thanks

kind regards

Kurt

   kernel/bpf/verifier.c | 30 +++++++++---------------------
   1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
       u32_min_val = src_reg.u32_min_value;
       u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 23 lines

the following code though:

          if (!src_known &&
              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                  __mark_reg_unknown(env, dst_reg);
                  return 0;
          }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
       if (alu32) {
               src_known = tnum_subreg_is_const(src_reg.var_off);
               if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Quoted 59 lines · Alexei Starovoitov

Quoted 47 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

       check in ___bpf_prog_run().

thanks

kind regards

Kurt

   kernel/bpf/verifier.c | 30 +++++++++---------------------
   1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
       u32_min_val = src_reg.u32_min_value;
       u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lldn", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

Quoted 1 line

I suspect such change will break valid programs that do shift by register.

Oh yes, you are correct. We should guard it with src_known. But this should be extremely rare with explicit shifting amount being greater than 31/64 and if it is the case, the compiler will has a warning.

Quoted 32 lines

Quoted 31 lines

the following code though:

          if (!src_known &&
              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                  __mark_reg_unknown(env, dst_reg);
                  return 0;
          }

Quoted 5 lines

kernel/bpf/verifier.c +1 -0

+
       if (alu32) {
               src_known = tnum_subreg_is_const(src_reg.var_off);
               if ((src_known &&

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 10 lines

kernel/bpf/verifier.c +0 -7

@@ -7592,39 +7601,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;
-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Agree. This makes sense.

Quoted 44 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

      check in ___bpf_prog_run().

thanks

kind regards

Kurt

  kernel/bpf/verifier.c | 30 +++++++++---------------------
  1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
      u32_min_val = src_reg.u32_min_value;
      u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 22 lines

the following code though:

         if (!src_known &&
             opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                 __mark_reg_unknown(env, dst_reg);
                 return 0;
         }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
      if (alu32) {
              src_known = tnum_subreg_is_const(src_reg.var_off);
              if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Quoted 89 lines · Alexei Starovoitov

Quoted 44 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

      check in ___bpf_prog_run().

thanks

kind regards

Kurt

  kernel/bpf/verifier.c | 30 +++++++++---------------------
  1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
      u32_min_val = src_reg.u32_min_value;
      u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 22 lines

the following code though:

         if (!src_known &&
             opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                 __mark_reg_unknown(env, dst_reg);
                 return 0;
         }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
      if (alu32) {
              src_known = tnum_subreg_is_const(src_reg.var_off);
              if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Hi Alexei,

The report is produced by KUBSAN. I thought there was an agreement on cleaning up KUBSAN reports from the kernel (the subset enabled on syzbot at least).
What exactly cases should KUBSAN ignore? +linux-hardening/kasan-dev for KUBSAN false positive

Quoted 96 lines · Dmitry Vyukov' via Clang Built Linux

Quoted 89 lines · Alexei Starovoitov

Quoted 44 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

       check in ___bpf_prog_run().

thanks

kind regards

Kurt

   kernel/bpf/verifier.c | 30 +++++++++---------------------
   1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
       u32_min_val = src_reg.u32_min_value;
       u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 22 lines

the following code though:

          if (!src_known &&
              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                  __mark_reg_unknown(env, dst_reg);
                  return 0;
          }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
       if (alu32) {
               src_known = tnum_subreg_is_const(src_reg.var_off);
               if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Hi Alexei,

Quoted 5 lines

The report is produced by KUBSAN. I thought there was an agreement on cleaning up KUBSAN reports from the kernel (the subset enabled on syzbot at least).
What exactly cases should KUBSAN ignore? +linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things readable and compiler-happy, whatever the implementation. :)

Quoted 97 lines · Kees Cook

Quoted 96 lines · Dmitry Vyukov' via Clang Built Linux

Quoted 89 lines · Alexei Starovoitov

Quoted 44 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

       check in ___bpf_prog_run().

thanks

kind regards

Kurt

   kernel/bpf/verifier.c | 30 +++++++++---------------------
   1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
       u32_min_val = src_reg.u32_min_value;
       u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 22 lines

the following code though:

          if (!src_known &&
              opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                  __mark_reg_unknown(env, dst_reg);
                  return 0;
          }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
       if (alu32) {
               src_known = tnum_subreg_is_const(src_reg.var_off);
               if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Hi Alexei,

Quoted 8 lines

Quoted 5 lines

The report is produced by KUBSAN. I thought there was an agreement on cleaning up KUBSAN reports from the kernel (the subset enabled on syzbot at least).
What exactly cases should KUBSAN ignore? +linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things readable and compiler-happy, whatever the implementation. :)

This is not a compile issue. If the shift amount is a constant, compiler should have warned and user should fix the warning.

This is because user code has
something like

     a << s;

where s is a unknown variable and
verifier just marked the result of a << s as unknown value. Verifier may not reject the code depending on how a << s result is used.

If bpf program writer uses check_shl_overflow() or some kind of checking for shift value and won't do shifting if the shifting may cause an undefined result, there should not be any kubsan warning.

Quoted 118 lines · Yonghong Song

Quoted 97 lines · Kees Cook

Quoted 96 lines · Dmitry Vyukov' via Clang Built Linux

Quoted 89 lines · Alexei Starovoitov

Quoted 44 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 37 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

        check in ___bpf_prog_run().

thanks

kind regards

Kurt

    kernel/bpf/verifier.c | 30 +++++++++---------------------
    1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
        u32_min_val = src_reg.u32_min_value;
        u32_max_val = src_reg.u32_max_value;
 

Quoted 10 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 8 lines

kernel/bpf/verifier.c +8 -0

+     if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+                     umax_val >= insn_bitness) {
+             /* Shifts greater than 31 or 63 are undefined.
+              * This includes shifts by a negative number.
+              */
+             verbose(env, "invalid shift %lld\n", umax_val);
+             return -EINVAL;
+     }

I think your fix is good. I would like to move after

I suspect such change will break valid programs that do shift by register.

Quoted 22 lines

the following code though:

           if (!src_known &&
               opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                   __mark_reg_unknown(env, dst_reg);
                   return 0;
           }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
        if (alu32) {
                src_known = tnum_subreg_is_const(src_reg.var_off);
                if ((src_known &&

@@ -7592,39 +7601,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;

Quoted 8 lines

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-             }

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Hi Alexei,

Quoted 8 lines

Quoted 5 lines

The report is produced by KUBSAN. I thought there was an agreement on cleaning up KUBSAN reports from the kernel (the subset enabled on syzbot at least).
What exactly cases should KUBSAN ignore? +linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things readable and compiler-happy, whatever the implementation. :)

This is not a compile issue. If the shift amount is a constant, compiler should have warned and user should fix the warning.

This is because user code has
something like

      a << s;

where s is a unknown variable and
verifier just marked the result of a << s as unknown value. Verifier may not reject the code depending on how a << s result is used.

Quoted 4 lines

If bpf program writer uses check_shl_overflow() or some kind of checking for shift value and won't do shifting if the shifting may cause an undefined result, there should not be any kubsan warning.

I guess the main question: what should happen if a bpf program writer does _not_ use compiler nor check_shl_overflow()?

Quoted 35 lines · Dmitry Vyukov

Quoted 34 lines · Yonghong Song

Quoted 21 lines · Kees Cook

Quoted 20 lines · Dmitry Vyukov' via Clang Built Linux

Quoted 13 lines · Alexei Starovoitov

Quoted 11 lines · Yonghong Song

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

[...]

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Quoted 2 lines

The large shift is not wrong. It's just undefined. syzbot has to ignore such cases.

Hi Alexei,

Quoted 8 lines

Quoted 5 lines

The report is produced by KUBSAN. I thought there was an agreement on cleaning up KUBSAN reports from the kernel (the subset enabled on syzbot at least).
What exactly cases should KUBSAN ignore? +linux-hardening/kasan-dev for KUBSAN false positive

Can check_shl_overflow() be used at all? Best to just make things readable and compiler-happy, whatever the implementation. :)

This is not a compile issue. If the shift amount is a constant, compiler should have warned and user should fix the warning.

Quoted 7 lines

Quoted 7 lines

This is because user code has
something like

      a << s;

where s is a unknown variable and
verifier just marked the result of a << s as unknown value. Verifier may not reject the code depending on how a << s result is used.

Quoted 4 lines

Quoted 4 lines

If bpf program writer uses check_shl_overflow() or some kind of checking for shift value and won't do shifting if the shifting may cause an undefined result, there should not be any kubsan warning.

Quoted 2 lines

I guess the main question: what should happen if a bpf program writer does _not_ use compiler nor check_shl_overflow()?

If kubsan is not enabled, everything should work as expected even with shl overflow may cause undefined result.

if kubsan is enabled, the reported shift-out-of-bounds warning should be ignored. You could disasm the insn to ensure that there indeed exists a potential shl overflow.

Quoted 3 lines

Quoted 3 lines

I guess the main question: what should happen if a bpf program writer does _not_ use compiler nor check_shl_overflow()?

I think the BPF runtime needs to make such actions defined, instead of doing a blind shift. It needs to check the size of the shift explicitly when handling the shift instruction.

Sure, but the point of UBSAN is to find and alert about undefined behavior, so we still need to fix this.

Quoted 4 lines · Kees Cook

Quoted 3 lines

Quoted 3 lines

I guess the main question: what should happen if a bpf program writer does _not_ use compiler nor check_shl_overflow()?

Quoted 3 lines

I think the BPF runtime needs to make such actions defined, instead of doing a blind shift. It needs to check the size of the shift explicitly when handling the shift instruction.

Such ideas were brought up in the past and rejected. We're not going to sacrifice performance to make behavior a bit more 'defined'. CPUs are doing it deterministically.

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

The shift-out-of-bounds happens when we have BPF_X. This means we have to go the same way we go when we want to avoid a divide-by-zero. We do it in do_misc_fixups().

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

How does UBSAN detect this in general? I would assume generated code for interpreter wrt DST = DST << SRC would not really change as otherwise all valid cases would be broken as well, given compiler has not really room to optimize or make any assumptions here, in other words, it's only propagating potential quirks under such cases from underlying arch.

Quoted 11 lines · Daniel Borkmann

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 6 lines

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same both before and after (with UBSAN disabled). Here is the patch I used:

kernel/bpf/core.c +18 -0

index 5e31ee9f7512..996db8a1bbfb 100644
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
 		DST = (u32) DST OP (u32) IMM;	\
 		CONT;
 
+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.
+	 */
+#define ALU_SHIFT(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		DST = DST OP (SRC & 63);\
+		CONT;			\
+	ALU_##OPCODE##_X:		\
+		DST = (u32) DST OP ((u32)SRC & 31);	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\
+		DST = DST OP (IMM & 63);	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		DST = (u32) DST OP ((u32)IMM & 31);	\
+		CONT;
+
 	ALU(ADD,  +)

Quoted 30 lines · Eric Biggers

Quoted 11 lines · Daniel Borkmann

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 6 lines

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same both before and after (with UBSAN disabled). Here is the patch I used:

kernel/bpf/core.c +0 -0

index 5e31ee9f7512..996db8a1bbfb 100644
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
  		DST = (u32) DST OP (u32) IMM;	\
  		CONT;
 

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1412

Quoted 3 lines

kernel/bpf/core.c +3 -0

+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.

Quoted 6 lines

kernel/bpf/core.c +6 -0

+	 */
+#define ALU_SHIFT(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		DST = DST OP (SRC & 63);\
+		CONT;			\
+	ALU_##OPCODE##_X:		\

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1426

Quoted 8 lines

kernel/bpf/core.c +8 -0

+		DST = (u32) DST OP ((u32)SRC & 31);	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\
+		DST = DST OP (IMM & 63);	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		DST = (u32) DST OP ((u32)IMM & 31);	\
+		CONT;

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1436

Quoted 11 lines

kernel/bpf/core.c +2 -2

  	ALU(ADD,  +)
  	ALU(SUB,  -)
  	ALU(AND,  &)
  	ALU(OR,   |)
-	ALU(LSH, <<)
-	ALU(RSH, >>)
+	ALU_SHIFT(LSH, <<)
+	ALU_SHIFT(RSH, >>)
  	ALU(XOR,  ^)
  	ALU(MUL,  *)
  #undef ALU

Note, I missed the arithmetic right shifts later on in the function. Same result there, though.

- Eric

Quoted 23 lines · Eric Biggers

Quoted 22 lines · Eric Biggers

Quoted 11 lines · Daniel Borkmann

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 6 lines

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same both before and after (with UBSAN disabled). Here is the patch I used:

Quoted 10 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1411

Quoted 10 lines

kernel/bpf/core.c +3 -0

index 5e31ee9f7512..996db8a1bbfb 100644
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
  		DST = (u32) DST OP (u32) IMM;	\
  		CONT;
+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.

The last one should probably be more specific in terms of 'normally', e.g. that it is expected that the compiler is optimizing this away for archs like x86. Is arm64 also covered by this ... do you happen to know on which archs this won't be the case?

Additionally, I think such comment should probably be more clear in that it also needs to give proper guidance to JIT authors that look at the interpreter code to see what they need to implement, in other words, that they don't end up copying an explicit AND instruction emission if not needed there.

Quoted 10 lines

Quoted 10 lines

kernel/bpf/core.c +9 -0

+	 */
+#define ALU_SHIFT(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		DST = DST OP (SRC & 63);\
+		CONT;			\
+	ALU_##OPCODE##_X:		\
+		DST = (u32) DST OP ((u32)SRC & 31);	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\

Quoted 5 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1426

Quoted 5 lines

kernel/bpf/core.c +5 -0

+		DST = DST OP (IMM & 63);	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		DST = (u32) DST OP ((u32)IMM & 31);	\
+		CONT;

For the *_K cases these are explicitly rejected by the verifier already. Is this required here nevertheless to suppress UBSAN false positive?

Quoted 39 lines · Daniel Borkmann

Quoted 23 lines · Eric Biggers

Quoted 22 lines · Eric Biggers

Quoted 11 lines · Daniel Borkmann

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 6 lines

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same both before and after (with UBSAN disabled). Here is the patch I used:

Quoted 9 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1410

Quoted 9 lines

kernel/bpf/core.c +3 -0

index 5e31ee9f7512..996db8a1bbfb 100644
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
  		DST = (u32) DST OP (u32) IMM;	> > >   		CONT;
+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.

The last one should probably be more specific in terms of 'normally', e.g. that it is expected that the compiler is optimizing this away for archs like x86. Is arm64 also covered by this ... do you happen to know on which archs this won't be the case?

Quoted 4 lines

Additionally, I think such comment should probably be more clear in that it also needs to give proper guidance to JIT authors that look at the interpreter code to see what they need to implement, in other words, that they don't end up copying an explicit AND instruction emission if not needed there.

Same result on arm64 with gcc 10.2.0.

On arm32 it is different, probably because the 64-bit shifts aren't native in that case. I don't know about other architectures. But there aren't many ways to implement shifts, and using just the low bits of the shift amount is the most logical way.

Please feel free to send out a patch with whatever comment you want. The diff I gave was just an example and I am not an expert in BPF.

Quoted 7 lines

Quoted 3 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1412

Quoted 3 lines

kernel/bpf/core.c +2 -0

+	 */
+#define ALU_SHIFT(OPCODE, OP)		> > > +	ALU64_##OPCODE##_X:		> > > +		DST = DST OP (SRC & 63);> > > +		CONT;			> > > +	ALU_##OPCODE##_X:		> > > +		DST = (u32) DST OP ((u32)SRC & 31);	> > > +		CONT;			> > > +	ALU64_##OPCODE##_K:		> > > +		DST = DST OP (IMM & 63);	> > > +		CONT;			> > > +	ALU_##OPCODE##_K:		> > > +		DST = (u32) DST OP ((u32)IMM & 31);	> > > +		CONT;

For the *_K cases these are explicitly rejected by the verifier already. Is this required here nevertheless to suppress UBSAN false positive?

No, I just didn't know that these constants are never out of range. Please feel free to send out a patch that does this properly.

Quoted 40 lines · Daniel Borkmann

Quoted 23 lines · Eric Biggers

Quoted 22 lines · Eric Biggers

Quoted 11 lines · Daniel Borkmann

Quoted 10 lines · Eric Biggers

Quoted 8 lines · Edward Cree

As I understand it, the UBSAN report is coming from the eBPF interpreter,
which is the *slow path* and indeed on many production systems is compiled out for hardening reasons (CONFIG_BPF_JIT_ALWAYS_ON).
Perhaps a better approach to the fix would be to change the interpreter
to compute "DST = DST << (SRC & 63);" (and similar for other shifts and bitnesses), thus matching the behaviour of most chips' shift opcodes.
This would shut up UBSAN, without affecting JIT code generation.

Quoted 6 lines

Quoted 3 lines

Yes, I suggested that last week
(https://lkml.kernel.org/netdev/[email protected]). The AND will even get optimized out when compiling for most CPUs.

Did you check if the generated interpreter code for e.g. x86 is the same before/after with that?

Yes, on x86_64 with gcc 10.2.1, the disassembly of ___bpf_prog_run() is the same both before and after (with UBSAN disabled). Here is the patch I used:

Quoted 10 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1411

Quoted 10 lines

kernel/bpf/core.c +3 -0

index 5e31ee9f7512..996db8a1bbfb 100644
@@ -1407,12 +1407,30 @@ static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn)
   		DST = (u32) DST OP (u32) IMM;	\
   		CONT;
+	/*
+	 * Explicitly mask the shift amounts with 63 or 31 to avoid undefined
+	 * behavior.  Normally this won't affect the generated code.

The last one should probably be more specific in terms of 'normally', e.g. that it is expected that the compiler is optimizing this away for archs like x86. Is arm64 also covered by this ... do you happen to know on which archs this won't be the case?

Quoted 4 lines

Additionally, I think such comment should probably be more clear in that it also needs to give proper guidance to JIT authors that look at the interpreter code to see what they need to implement, in other words, that they don't end up copying an explicit AND instruction emission if not needed there.

Same result on arm64 with gcc 10.2.0.

On arm32 it is different, probably because the 64-bit shifts aren't native in that case. I don't know about other architectures. But there aren't many ways to implement shifts, and using just the low bits of the shift amount is the most logical way.

Please feel free to send out a patch with whatever comment you want. The diff I gave was just an example and I am not an expert in BPF.

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

kernel/bpf/core.c +9 -0

+	 */
+#define ALU_SHIFT(OPCODE, OP)		\
+	ALU64_##OPCODE##_X:		\
+		DST = DST OP (SRC & 63);\
+		CONT;			\
+	ALU_##OPCODE##_X:		\
+		DST = (u32) DST OP ((u32)SRC & 31);	\
+		CONT;			\
+	ALU64_##OPCODE##_K:		\

Quoted 8 lines

Quoted 5 lines

kernel/bpf/core.c static u64 ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn) · line 1426

Quoted 5 lines

kernel/bpf/core.c +5 -0

+		DST = DST OP (IMM & 63);	\
+		CONT;			\
+	ALU_##OPCODE##_K:		\
+		DST = (u32) DST OP ((u32)IMM & 31);	\
+		CONT;

For the *_K cases these are explicitly rejected by the verifier already. Is this required here nevertheless to suppress UBSAN false positive?

No, I just didn't know that these constants are never out of range. Please feel free to send out a patch that does this properly.

Quoted 2 lines · Kurt Manucredo

Syzbot detects a shift-out-of-bounds in ___bpf_prog_run() kernel/bpf/core.c:1414:2.

This is not enough. We need more information on why this happens so we can judge whether the patch indeed fixed the issue.

Quoted 35 lines

I propose: In adjust_scalar_min_max_vals() move boundary check up to avoid missing them and return with error when detected.

Reported-and-tested-by [email protected]

Signed-off-by Kurt Manucredo <[email protected]>

---

https://syzkaller.appspot.com/bug?id=edb51be4c9a320186328893287bb30d5eed09231

Changelog:
----------
v4 - Fix shift-out-of-bounds in adjust_scalar_min_max_vals.
Fix commit message.
v3 - Make it clearer what the fix is for.
v2 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary
check in check_alu_op() in verifier.c.
v1 - Fix shift-out-of-bounds in ___bpf_prog_run() by adding boundary

      check in ___bpf_prog_run().

thanks

kind regards

Kurt

  kernel/bpf/verifier.c | 30 +++++++++---------------------
  1 file changed, 9 insertions(+), 21 deletions(-)

kernel/bpf/verifier.c +0 -0

index 94ba5163d4c5..ed0eecf20de5 100644
@@ -7510,6 +7510,15 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
  	u32_min_val = src_reg.u32_min_value;

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7520

Quoted 10 lines

kernel/bpf/verifier.c +8 -0

  	u32_max_val = src_reg.u32_max_value;
 
+	if ((opcode == BPF_LSH || opcode == BPF_RSH || opcode == BPF_ARSH) &&
+			umax_val >= insn_bitness) {
+		/* Shifts greater than 31 or 63 are undefined.
+		 * This includes shifts by a negative number.
+		 */
+		verbose(env, "invalid shift %lldn", umax_val);
+		return -EINVAL;
+	}

I think your fix is good. I would like to move after the following code though:

         if (!src_known &&
             opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) {
                 __mark_reg_unknown(env, dst_reg);
                 return 0;
         }

Quoted 14 lines

kernel/bpf/verifier.c +1 -6

+
  	if (alu32) {
  		src_known = tnum_subreg_is_const(src_reg.var_off);
  		if ((src_known &&

@@ -7592,39 +7601,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;

kernel/bpf/verifier.c static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, · line 7601

Quoted 1 line

kernel/bpf/verifier.c +0 -1

-		}

I think this is what happens. For the above case, we simply marks the dst reg as unknown and didn't fail verification. So later on at runtime, the shift optimization will have wrong shift value (> 31/64). Please correct me if this is not right analysis. As I mentioned in the early please write detailed analysis in commit log.

Please also add a test at tools/testing/selftests/bpf/verifier/.