[syzbot] UBSAN: shift-out-of-bounds in ___bpf_prog_run

Hello,

syzbot found the following issue on:

HEAD commit:    144c79ef Merge tag 'perf-tools-fixes-for-v5.12-2020-03-07'..
git tree:       upstream
console output: https://syzkaller.appspot.com/x/log.txt?x=1572d952d00000
kernel config:  https://syzkaller.appspot.com/x/.config?x=ccdd84f79f45b23d
dashboard link: https://syzkaller.appspot.com/bug?extid=bed360704c521841c85d

Unfortunately, I don't have any reproducer for this issue yet.

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com

================================================================================
UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1420:2
shift exponent 255 is too large for 64-bit type 'long long unsigned int'
CPU: 1 PID: 11097 Comm: syz-executor.4 Not tainted 5.12.0-rc2-syzkaller #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011
Call Trace:
 __dump_stack lib/dump_stack.c:79 [inline]
 dump_stack+0x141/0x1d7 lib/dump_stack.c:120
 ubsan_epilogue+0xb/0x5a lib/ubsan.c:148
 __ubsan_handle_shift_out_of_bounds.cold+0xb1/0x181 lib/ubsan.c:327
 ___bpf_prog_run.cold+0x19/0x56c kernel/bpf/core.c:1420
 __bpf_prog_run32+0x8f/0xd0 kernel/bpf/core.c:1735
 bpf_dispatcher_nop_func include/linux/bpf.h:644 [inline]
 bpf_prog_run_pin_on_cpu include/linux/filter.h:624 [inline]
 bpf_prog_run_clear_cb include/linux/filter.h:755 [inline]
 run_filter+0x1a1/0x470 net/packet/af_packet.c:2031
 packet_rcv+0x313/0x13e0 net/packet/af_packet.c:2104
 dev_queue_xmit_nit+0x7c2/0xa90 net/core/dev.c:2387
 xmit_one net/core/dev.c:3588 [inline]
 dev_hard_start_xmit+0xad/0x920 net/core/dev.c:3609
 __dev_queue_xmit+0x2121/0x2e00 net/core/dev.c:4182
 __bpf_tx_skb net/core/filter.c:2116 [inline]
 __bpf_redirect_no_mac net/core/filter.c:2141 [inline]
 __bpf_redirect+0x548/0xc80 net/core/filter.c:2164
 ____bpf_clone_redirect net/core/filter.c:2448 [inline]
 bpf_clone_redirect+0x2ae/0x420 net/core/filter.c:2420
 ___bpf_prog_run+0x34e1/0x77d0 kernel/bpf/core.c:1523
 __bpf_prog_run512+0x99/0xe0 kernel/bpf/core.c:1737
 bpf_dispatcher_nop_func include/linux/bpf.h:644 [inline]
 bpf_test_run+0x3ed/0xc50 net/bpf/test_run.c:50
 bpf_prog_test_run_skb+0xabc/0x1c50 net/bpf/test_run.c:582
 bpf_prog_test_run kernel/bpf/syscall.c:3127 [inline]
 __do_sys_bpf+0x1ea9/0x4f00 kernel/bpf/syscall.c:4406
 do_syscall_64+0x2d/0x70 arch/x86/entry/common.c:46
 entry_SYSCALL_64_after_hwframe+0x44/0xae
RIP: 0033:0x465f69
Code: ff ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 40 00 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 c7 c1 bc ff ff ff f7 d8 64 89 01 48
RSP: 002b:00007f2797f63188 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 000000000056bf60 RCX: 0000000000465f69
RDX: 0000000000000028 RSI: 0000000020000080 RDI: 000000000000000a
RBP: 00000000004bfa3f R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000246 R12: 000000000056bf60
R13: 00007ffcd53d929f R14: 00007f2797f63300 R15: 0000000000022000
================================================================================


---
This report is generated by a bot. It may contain errors.
See https://goo.gl/tpsmEJ for more information about syzbot.
syzbot engineers can be reached at syzkaller@googlegroups.com.

syzbot will keep track of this issue. See:
https://goo.gl/tpsmEJ#status for how to communicate with syzbot.

syzbot has found a reproducer for the following issue on:

HEAD commit:    0f4498ce Merge tag 'for-5.12/dm-fixes-2' of git://git.kern..
git tree:       upstream
console output: https://syzkaller.appspot.com/x/log.txt?x=16d734aad00000
kernel config:  https://syzkaller.appspot.com/x/.config?x=d4e9addca54f3b44
dashboard link: https://syzkaller.appspot.com/bug?extid=bed360704c521841c85d
syz repro:      https://syzkaller.appspot.com/x/repro.syz?x=1424cd9ed00000
C reproducer:   https://syzkaller.appspot.com/x/repro.c?x=1085497cd00000

IMPORTANT: if you fix the issue, please add the following tag to the commit:
Reported-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com

================================================================================
UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1421:2
shift exponent 248 is too large for 32-bit type 'unsigned int'
CPU: 1 PID: 8388 Comm: syz-executor895 Not tainted 5.12.0-rc4-syzkaller #0
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011
Call Trace:
 __dump_stack lib/dump_stack.c:79 [inline]
 dump_stack+0x141/0x1d7 lib/dump_stack.c:120
 ubsan_epilogue+0xb/0x5a lib/ubsan.c:148
 __ubsan_handle_shift_out_of_bounds.cold+0xb1/0x181 lib/ubsan.c:327
 ___bpf_prog_run.cold+0x20f/0x56c kernel/bpf/core.c:1421
 __bpf_prog_run480+0x99/0xe0 kernel/bpf/core.c:1739
 bpf_dispatcher_nop_func include/linux/bpf.h:659 [inline]
 __bpf_trace_run kernel/trace/bpf_trace.c:2091 [inline]
 bpf_trace_run2+0x12f/0x390 kernel/trace/bpf_trace.c:2128
 __bpf_trace_tlb_flush+0xbd/0x100 include/trace/events/tlb.h:38
 trace_tlb_flush+0xe0/0x1c0 include/trace/events/tlb.h:38
 switch_mm_irqs_off+0x48b/0x970 arch/x86/mm/tlb.c:563
 unuse_temporary_mm arch/x86/kernel/alternative.c:842 [inline]
 __text_poke+0x541/0x8c0 arch/x86/kernel/alternative.c:938
 text_poke_bp_batch+0x187/0x550 arch/x86/kernel/alternative.c:1190
 text_poke_flush arch/x86/kernel/alternative.c:1347 [inline]
 text_poke_flush arch/x86/kernel/alternative.c:1344 [inline]
 text_poke_finish+0x16/0x30 arch/x86/kernel/alternative.c:1354
 arch_jump_label_transform_apply+0x13/0x20 arch/x86/kernel/jump_label.c:126
 jump_label_update+0x1da/0x400 kernel/jump_label.c:825
 static_key_enable_cpuslocked+0x1b1/0x260 kernel/jump_label.c:177
 static_key_enable+0x16/0x20 kernel/jump_label.c:190
 tracepoint_add_func+0x707/0xa90 kernel/tracepoint.c:303
 tracepoint_probe_register_prio kernel/tracepoint.c:369 [inline]
 tracepoint_probe_register+0x9c/0xe0 kernel/tracepoint.c:389
 __bpf_probe_register kernel/trace/bpf_trace.c:2154 [inline]
 bpf_probe_register+0x15a/0x1c0 kernel/trace/bpf_trace.c:2159
 bpf_raw_tracepoint_open+0x34a/0x720 kernel/bpf/syscall.c:2878
 __do_sys_bpf+0x2586/0x4f40 kernel/bpf/syscall.c:4435
 do_syscall_64+0x2d/0x70 arch/x86/entry/common.c:46
 entry_SYSCALL_64_after_hwframe+0x44/0xae
RIP: 0033:0x43f009
Code: Unable to access opcode bytes at RIP 0x43efdf.
RSP: 002b:00007ffc64740b68 EFLAGS: 00000246 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 0000000000400488 RCX: 000000000043f009
RDX: 0000000000000010 RSI: 0000000020000080 RDI: 0000000000000011
RBP: 0000000000402ff0 R08: 0000000000000000 R09: 0000000000400488
R10: 0000000000000000 R11: 0000000000000246 R12: 0000000000403080
R13: 0000000000000000 R14: 00000000004ac018 R15: 0000000000400488
================================================================================

UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
shift exponent 248 is too large for 32-bit type 'unsigned int'

Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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

Changelog:
----------
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().

Hi everyone,

I hope this fixes it!

kind regards

 kernel/bpf/verifier.c | 22 +++++++++++++++++-----
 1 file changed, 17 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..04e3bf344ecd 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -7880,13 +7880,25 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			return -EINVAL;
 		}
 
-		if ((opcode == BPF_LSH || opcode == BPF_RSH ||
-		     opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
+		if (opcode == BPF_LSH || opcode == BPF_RSH ||
+		     opcode == BPF_ARSH) {
 			int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
 
-			if (insn->imm < 0 || insn->imm >= size) {
-				verbose(env, "invalid shift %d\n", insn->imm);
-				return -EINVAL;
+			if (BPF_SRC(insn->code) == BPF_K) {
+				if (insn->imm < 0 || insn->imm >= size) {
+					verbose(env, "invalid shift %d\n", insn->imm);
+					return -EINVAL;
+				}
+			}
+			if (BPF_SRC(insn->code) == BPF_X) {
+				struct bpf_reg_state *src_reg;
+
+				src_reg = &regs[insn->src_reg];
+				if (src_reg->umax_value >= size) {
+					verbose(env, "invalid shift %lld\n",
+							src_reg->umax_value);
+					return -EINVAL;
+				}
 			}
 		}
 

-- 
2.30.2

On Wed, Jun 02, 2021 at 09:27:26PM +0000, Kurt Manucredo wrote:

UBSAN: shift-out-of-bounds in kernel/bpf/core.c:1414:2
shift exponent 248 is too large for 32-bit type 'unsigned int'

I'm sorry, but I still do not understand what this changelog text means.

Please be very descriptive about what you are doing and why you are
doing it.  All that is here is a message from a random tool :(

thanks,
greg k-h

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;
 
+	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;
+	}
+
 	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;
-		}
 		if (alu32)
 			scalar32_min_max_lsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_lsh(dst_reg, &src_reg);
 		break;
 	case BPF_RSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_rsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_rsh(dst_reg, &src_reg);
 		break;
 	case BPF_ARSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_arsh(dst_reg, &src_reg);
 		else

-- 
2.30.2

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

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.

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;
         }

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

  		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

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

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

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

+
      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;
-             }

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.

On 6/5/21 12:10 PM, Alexei Starovoitov wrote:

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

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

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

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

+
       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;
-             }

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.

Agree. This makes sense.

On Sat, 5 Jun 2021 10:55:25 -0700, Yonghong Song [off-list ref] wrote:

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;
  
+	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;
         }

It can only be right before that code not after. That's the latest. In the
case of the syzbot bug, opcode == BPF_LSH and !src_known. Therefore it
needs to be before that block of code.

quoted

+
  	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;
-		}

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.

Shouldn't the src reg be changed so that the shift-out-of-bounds can't
occur, if return -EINVAL is not what we want here? Changing the dst reg
might not help. If I look into kernel/bpf/core.c I can see:
	DST = DST OP SRC;

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

I'm going to look into selftests,

kind regards
thanks,

Kurt Manucredo

On Sat, 5 Jun 2021 14:39:57 -0700, Yonghong Song [off-list ref] wrote:

On 6/5/21 12:10 PM, Alexei Starovoitov wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

quoted

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

+
       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;
-             }

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.

Agree. This makes sense.

Thanks for your input. If you find I should look closer into this bug
just let me know. I'd love to help. If not it's fine, too. :-)

kind regards,

Kurt Manucredo

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

+
      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;
-             }

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.

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

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

+
      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;
-             }

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.

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

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

-- 
Kees Cook

On 6/9/21 11:20 AM, Kees Cook wrote:

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:

quoted

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

+
       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;
-             }

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.

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

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.

On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song [off-list ref] wrote:

On 6/9/21 11:20 AM, Kees Cook wrote:

quoted

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:

quoted

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

+
       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;
-             }

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.

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

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.

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

On 6/9/21 10:32 PM, Dmitry Vyukov wrote:

On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/9/21 11:20 AM, Kees Cook wrote:

quoted

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:

quoted

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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

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: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ed0eecf20de5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -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;

+     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

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

+
        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;
-             }

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.

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

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.

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.

On Wed, Jun 09, 2021 at 11:06:31PM -0700, Yonghong Song wrote:

On 6/9/21 10:32 PM, Dmitry Vyukov wrote:

quoted

On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/9/21 11:20 AM, Kees Cook wrote:

quoted

On Mon, Jun 07, 2021 at 09:38:43AM +0200, 'Dmitry Vyukov' via Clang Built Linux wrote:

quoted

On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov
[off-list ref] wrote:

quoted

On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song [off-list ref] wrote:

quoted

On 6/5/21 8:01 AM, Kurt Manucredo wrote:

quoted

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.

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

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.

Ah, gotcha: it's the BPF code itself that needs to catch it.

quoted

quoted

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.

Right.

quoted

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.

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.

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


-- 
Kees Cook

On Thu, Jun 10, 2021 at 10:06 AM Kees Cook [off-list ref] wrote:

quoted

quoted

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.

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. It's the C standard
that needs fixing.

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

No. The undefined behavior of C standard doesn't need "fixing" most of the time.

On Thu, Jun 10, 2021 at 10:52:37AM -0700, Alexei Starovoitov wrote:

On Thu, Jun 10, 2021 at 10:06 AM Kees Cook [off-list ref] wrote:

quoted

quoted

quoted

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.

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.

What CPUs do is not the whole story.  The compiler can assume that the shift
amount is less than the width and use that assumption in other places, resulting
in other things being miscompiled.

Couldn't you just AND the shift amounts with the width minus 1?  That would make
the shifts defined, and the compiler would optimize out the AND on any CPU that
interprets the shift amounts modulo the width anyway (e.g., x86).

- Eric

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

When we have BPF_K we find divide-by-zero and shift-out-of-bounds guards
next each other in check_alu_op(). It seems only logical to me that the
same should be true for BPF_X in do_misc_fixups() since it is there where
I found the divide-by-zero guard. Or is there a reason I'm not aware of,
that dictates that the checks should be in adjust_scalar_min_max_vals(),
as they are now?

This patch was tested by syzbot.

Reported-and-tested-by: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com
Signed-off-by: Kurt Manucredo <redacted>
---

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

Changelog:
----------
v5 - Fix shift-out-of-bounds in do_misc_fixups().
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 | 53 +++++++++++++++++++++++++------------------
 1 file changed, 31 insertions(+), 22 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..83c7c1ccaf26 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -7496,7 +7496,6 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 	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;
 

@@ -7592,39 +7591,18 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		scalar_min_max_xor(dst_reg, &src_reg);
 		break;
 	case BPF_LSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_lsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_lsh(dst_reg, &src_reg);
 		break;
 	case BPF_RSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_rsh(dst_reg, &src_reg);
 		else
 			scalar_min_max_rsh(dst_reg, &src_reg);
 		break;
 	case BPF_ARSH:
-		if (umax_val >= insn_bitness) {
-			/* Shifts greater than 31 or 63 are undefined.
-			 * This includes shifts by a negative number.
-			 */
-			mark_reg_unknown(env, regs, insn->dst_reg);
-			break;
-		}
 		if (alu32)
 			scalar32_min_max_arsh(dst_reg, &src_reg);
 		else

@@ -12353,6 +12331,37 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			continue;
 		}
 
+		/* Make shift-out-of-bounds exceptions impossible. */
+		if (insn->code == (BPF_ALU64 | BPF_LSH | BPF_X) ||
+		    insn->code == (BPF_ALU64 | BPF_RSH | BPF_X) ||
+		    insn->code == (BPF_ALU64 | BPF_ARSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_LSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_RSH | BPF_X) ||
+		    insn->code == (BPF_ALU | BPF_ARSH | BPF_X)) {
+			bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
+			u8 insn_bitness = is64 ? 64 : 32;
+			struct bpf_insn chk_and_shift[] = {
+				/* [R,W]x shift >= 32||64 -> 0 */
+				BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
+					     BPF_JLT | BPF_K, insn->src_reg,
+					     insn_bitness, 2, 0),
+				BPF_ALU32_REG(BPF_XOR, insn->dst_reg, insn->dst_reg),
+				BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+				*insn,
+			};
+
+			cnt = ARRAY_SIZE(chk_and_shift);
+
+			new_prog = bpf_patch_insn_data(env, i + delta, chk_and_shift, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			continue;
+		}
+
 		/* Implement LD_ABS and LD_IND with a rewrite, if supported by the program type. */
 		if (BPF_CLASS(insn->code) == BPF_LD &&
 		    (BPF_MODE(insn->code) == BPF_ABS ||

-- 
2.30.2

On 15/06/2021 17:42, Kurt Manucredo wrote:

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

Shifts by more than insn_bitness are legal in the eBPF ISA; they are
 implementation-defined behaviour, rather than UB, and have been made
 legal for performance reasons.  Each of the JIT backends compiles the
 eBPF shift operations to machine instructions which produce
 implementation-defined results in such a case; the resulting contents
 of the register may be arbitrary but program behaviour as a whole
 remains defined.
Guard checks in the fast path (i.e. affecting JITted code) will thus
 not be accepted.
The case of division by zero is not truly analogous, as division
 instructions on many of the JIT-targeted architectures will raise a
 machine exception / fault on division by zero, whereas (to the best of
 my knowledge) none will do so on an out-of-bounds shift.
(That said, it would be possible to record from the verifier division
 instructions in the program which are known never to be passed zero as
 divisor, and eliding the fixup patch in those cases.  However, the
 extra complexity may not be worthwhile.)

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.

-ed

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

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/YMJvbGEz0xu9JU9D@gmail.com).  The AND will even
get optimized out when compiling for most CPUs.

- Eric

On 6/15/21 9:33 PM, Eric Biggers wrote:

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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.

Thanks,
Daniel

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:

On 6/15/21 9:33 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c

@@ -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,  +)
 	ALU(SUB,  -)
 	ALU(AND,  &)
 	ALU(OR,   |)
-	ALU(LSH, <<)
-	ALU(RSH, >>)
+	ALU_SHIFT(LSH, <<)
+	ALU_SHIFT(RSH, >>)
 	ALU(XOR,  ^)
 	ALU(MUL,  *)
 #undef ALU

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.

UBSAN inserts code that checks that shift amounts are in range.

In theory there are cases where the undefined behavior of out-of-range shift
amounts could cause problems.  For example, a compiler could make the following
function always return true, as it can assume that 'b' is in the range [0, 31].

	bool foo(int a, int b, int *c)
	{
		*c = a << b;
		return b < 32;
	}

- Eric

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:

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

- Eric

On 6/15/21 11:38 PM, Eric Biggers wrote:

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 9:33 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c

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

+	 */
+#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?

quoted

  	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

On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:

On 6/15/21 11:38 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 9:33 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c

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

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

quoted

+	 */
+#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.

- Eric

On Tue, 15 Jun 2021 15:07:43 -0700, Eric Biggers [off-list ref] wrote:

On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 11:38 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 9:33 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c

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

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

quoted

quoted

+	 */
+#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.

The shift-out-of-bounds on syzbot happens in ALU_##OPCODE##_X only. To
pass the syzbot test, only ALU_##OPCODE##_X needs to be guarded.

This old patch I tested on syzbot puts a check in all four.
https://syzkaller.appspot.com/text?tag=Patch&x=11f8cacbd00000

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

thanks,

kind regards

Kurt Manucredo

On 6/16/21 12:07 AM, Eric Biggers wrote:

On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 11:38 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote:

quoted

On 6/15/21 9:33 PM, Eric Biggers wrote:

quoted

On Tue, Jun 15, 2021 at 07:51:07PM +0100, Edward Cree wrote:

quoted

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/YMJvbGEz0xu9JU9D@gmail.com).  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:

diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 5e31ee9f7512..996db8a1bbfb 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c

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

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

quoted

quoted

+	 */
+#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.

Summarized and fixed via:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/commit/?id=28131e9d933339a92f78e7ab6429f4aaaa07061c

Thanks everyone,
Daniel