* [syzbot] UBSAN: shift-out-of-bounds in ___bpf_prog_run @ 2021-03-10 16:05 syzbot 2021-03-28 3:38 ` syzbot 0 siblings, 1 reply; 28+ messages in thread From: syzbot @ 2021-03-10 16:05 UTC (permalink / raw) To: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, yhs 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [syzbot] UBSAN: shift-out-of-bounds in ___bpf_prog_run 2021-03-10 16:05 [syzbot] UBSAN: shift-out-of-bounds in ___bpf_prog_run syzbot @ 2021-03-28 3:38 ` syzbot 2021-06-02 21:27 ` [PATCH v3] bpf: core: fix " Kurt Manucredo 0 siblings, 1 reply; 28+ messages in thread From: syzbot @ 2021-03-28 3:38 UTC (permalink / raw) To: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, yhs 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 ================================================================================ ^ permalink raw reply [flat|nested] 28+ messages in thread
* [PATCH v3] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-03-28 3:38 ` syzbot @ 2021-06-02 21:27 ` Kurt Manucredo 2021-06-03 4:43 ` Greg KH 0 siblings, 1 reply; 28+ messages in thread From: Kurt Manucredo @ 2021-06-02 21:27 UTC (permalink / raw) To: syzbot+bed360704c521841c85d Cc: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, yhs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan, gregkh, Kurt Manucredo 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 <fuzzybritches0@gmail.com> --- 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 = ®s[insn->src_reg]; + if (src_reg->umax_value >= size) { + verbose(env, "invalid shift %lld\n", + src_reg->umax_value); + return -EINVAL; + } } } -- 2.30.2 ^ permalink raw reply related [flat|nested] 28+ messages in thread
* Re: [PATCH v3] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-02 21:27 ` [PATCH v3] bpf: core: fix " Kurt Manucredo @ 2021-06-03 4:43 ` Greg KH 2021-06-05 15:01 ` [PATCH v4] " Kurt Manucredo 0 siblings, 1 reply; 28+ messages in thread From: Greg KH @ 2021-06-03 4:43 UTC (permalink / raw) To: Kurt Manucredo Cc: syzbot+bed360704c521841c85d, andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, yhs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-03 4:43 ` Greg KH @ 2021-06-05 15:01 ` Kurt Manucredo 2021-06-05 17:55 ` Yonghong Song 0 siblings, 1 reply; 28+ messages in thread From: Kurt Manucredo @ 2021-06-05 15:01 UTC (permalink / raw) To: syzbot+bed360704c521841c85d Cc: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, yhs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan, gregkh, Kurt Manucredo 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 <fuzzybritches0@gmail.com> --- 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 ^ permalink raw reply related [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 15:01 ` [PATCH v4] " Kurt Manucredo @ 2021-06-05 17:55 ` Yonghong Song 2021-06-05 19:10 ` Alexei Starovoitov 2021-06-06 19:15 ` [PATCH v4] " Kurt Manucredo 0 siblings, 2 replies; 28+ messages in thread From: Yonghong Song @ 2021-06-05 17:55 UTC (permalink / raw) To: Kurt Manucredo, syzbot+bed360704c521841c85d Cc: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan, gregkh 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 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 <fuzzybritches0@gmail.com> > --- > > 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 the following code though: if (!src_known && opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) { __mark_reg_unknown(env, dst_reg); return 0; } > + > 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. 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 > ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 17:55 ` Yonghong Song @ 2021-06-05 19:10 ` Alexei Starovoitov 2021-06-05 21:39 ` Yonghong Song 2021-06-07 7:38 ` Dmitry Vyukov 2021-06-06 19:15 ` [PATCH v4] " Kurt Manucredo 1 sibling, 2 replies; 28+ messages in thread From: Alexei Starovoitov @ 2021-06-05 19:10 UTC (permalink / raw) To: Yonghong Song Cc: Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > > > > 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 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 <fuzzybritches0@gmail.com> > > --- > > > > 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; > } > > > + > > 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 19:10 ` Alexei Starovoitov @ 2021-06-05 21:39 ` Yonghong Song 2021-06-06 19:44 ` Kurt Manucredo 2021-06-07 7:38 ` Dmitry Vyukov 1 sibling, 1 reply; 28+ messages in thread From: Yonghong Song @ 2021-06-05 21:39 UTC (permalink / raw) To: Alexei Starovoitov Cc: Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman On 6/5/21 12:10 PM, Alexei Starovoitov wrote: > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: >> >> >> >> 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 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 <fuzzybritches0@gmail.com> >>> --- >>> >>> 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. > >> the following code though: >> >> if (!src_known && >> opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) { >> __mark_reg_unknown(env, dst_reg); >> return 0; >> } >> >>> + >>> 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 21:39 ` Yonghong Song @ 2021-06-06 19:44 ` Kurt Manucredo 0 siblings, 0 replies; 28+ messages in thread From: Kurt Manucredo @ 2021-06-06 19:44 UTC (permalink / raw) To: yhs, alexei.starovoitov Cc: syzbot+bed360704c521841c85d, andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan, gregkh On Sat, 5 Jun 2021 14:39:57 -0700, Yonghong Song <yhs@fb.com> wrote: > > > > On 6/5/21 12:10 PM, Alexei Starovoitov wrote: > > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > >> > >> > >> > >> 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 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 <fuzzybritches0@gmail.com> > >>> --- > >>> > >>> 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. > > > > >> the following code though: > >> > >> if (!src_known && > >> opcode != BPF_ADD && opcode != BPF_SUB && opcode != BPF_AND) { > >> __mark_reg_unknown(env, dst_reg); > >> return 0; > >> } > >> > >>> + > >>> 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 19:10 ` Alexei Starovoitov 2021-06-05 21:39 ` Yonghong Song @ 2021-06-07 7:38 ` Dmitry Vyukov 2021-06-09 18:20 ` Kees Cook 1 sibling, 1 reply; 28+ messages in thread From: Dmitry Vyukov @ 2021-06-07 7:38 UTC (permalink / raw) To: Alexei Starovoitov Cc: Yonghong Song, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > > 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 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 <fuzzybritches0@gmail.com> > > > --- > > > > > > 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; > > } > > > > > + > > > 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-07 7:38 ` Dmitry Vyukov @ 2021-06-09 18:20 ` Kees Cook 2021-06-09 23:40 ` Yonghong Song 0 siblings, 1 reply; 28+ messages in thread From: Kees Cook @ 2021-06-09 18:20 UTC (permalink / raw) To: Dmitry Vyukov Cc: Alexei Starovoitov, Yonghong Song, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev 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 > <alexei.starovoitov@gmail.com> wrote: > > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > > > 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 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 <fuzzybritches0@gmail.com> > > > > --- > > > > > > > > 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; > > > } > > > > > > > + > > > > 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-09 18:20 ` Kees Cook @ 2021-06-09 23:40 ` Yonghong Song 2021-06-10 5:32 ` Dmitry Vyukov 0 siblings, 1 reply; 28+ messages in thread From: Yonghong Song @ 2021-06-09 23:40 UTC (permalink / raw) To: Kees Cook, Dmitry Vyukov Cc: Alexei Starovoitov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev 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: >> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov >> <alexei.starovoitov@gmail.com> wrote: >>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: >>>> 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 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 <fuzzybritches0@gmail.com> >>>>> --- >>>>> >>>>> 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; >>>> } >>>> >>>>> + >>>>> 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. > ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-09 23:40 ` Yonghong Song @ 2021-06-10 5:32 ` Dmitry Vyukov 2021-06-10 6:06 ` Yonghong Song 0 siblings, 1 reply; 28+ messages in thread From: Dmitry Vyukov @ 2021-06-10 5:32 UTC (permalink / raw) To: Yonghong Song Cc: Kees Cook, Alexei Starovoitov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote: > 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: > >> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov > >> <alexei.starovoitov@gmail.com> wrote: > >>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > >>>> 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 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 <fuzzybritches0@gmail.com> > >>>>> --- > >>>>> > >>>>> 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; > >>>> } > >>>> > >>>>> + > >>>>> 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()? ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-10 5:32 ` Dmitry Vyukov @ 2021-06-10 6:06 ` Yonghong Song 2021-06-10 17:06 ` Kees Cook 0 siblings, 1 reply; 28+ messages in thread From: Yonghong Song @ 2021-06-10 6:06 UTC (permalink / raw) To: Dmitry Vyukov Cc: Kees Cook, Alexei Starovoitov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On 6/9/21 10:32 PM, Dmitry Vyukov wrote: > On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote: >> 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: >>>> On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov >>>> <alexei.starovoitov@gmail.com> wrote: >>>>> On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: >>>>>> 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 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 <fuzzybritches0@gmail.com> >>>>>>> --- >>>>>>> >>>>>>> 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; >>>>>> } >>>>>> >>>>>>> + >>>>>>> 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-10 6:06 ` Yonghong Song @ 2021-06-10 17:06 ` Kees Cook 2021-06-10 17:52 ` Alexei Starovoitov 0 siblings, 1 reply; 28+ messages in thread From: Kees Cook @ 2021-06-10 17:06 UTC (permalink / raw) To: Yonghong Song Cc: Dmitry Vyukov, Alexei Starovoitov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On Wed, Jun 09, 2021 at 11:06:31PM -0700, Yonghong Song wrote: > > > On 6/9/21 10:32 PM, Dmitry Vyukov wrote: > > On Thu, Jun 10, 2021 at 1:40 AM Yonghong Song <yhs@fb.com> wrote: > > > 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: > > > > > On Sat, Jun 5, 2021 at 9:10 PM Alexei Starovoitov > > > > > <alexei.starovoitov@gmail.com> wrote: > > > > > > On Sat, Jun 5, 2021 at 10:55 AM Yonghong Song <yhs@fb.com> wrote: > > > > > > > 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. > > > > > > > [...] > > > > > > > > > > > > > > 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. > > > 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. > > 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-10 17:06 ` Kees Cook @ 2021-06-10 17:52 ` Alexei Starovoitov 2021-06-10 20:00 ` Eric Biggers 0 siblings, 1 reply; 28+ messages in thread From: Alexei Starovoitov @ 2021-06-10 17:52 UTC (permalink / raw) To: Kees Cook Cc: Yonghong Song, Dmitry Vyukov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On Thu, Jun 10, 2021 at 10:06 AM Kees Cook <keescook@chromium.org> wrote: > > > > 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. ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-10 17:52 ` Alexei Starovoitov @ 2021-06-10 20:00 ` Eric Biggers 2021-06-15 16:42 ` [PATCH v5] " Kurt Manucredo 0 siblings, 1 reply; 28+ messages in thread From: Eric Biggers @ 2021-06-10 20:00 UTC (permalink / raw) To: Alexei Starovoitov Cc: Kees Cook, Yonghong Song, Dmitry Vyukov, Kurt Manucredo, syzbot+bed360704c521841c85d, Andrii Nakryiko, Alexei Starovoitov, bpf, Daniel Borkmann, David S. Miller, Jesper Dangaard Brouer, John Fastabend, Martin KaFai Lau, KP Singh, Jakub Kicinski, LKML, Network Development, Song Liu, syzkaller-bugs, nathan, Nick Desaulniers, Clang-Built-Linux ML, linux-kernel-mentees, Shuah Khan, Greg Kroah-Hartman, Kernel Hardening, kasan-dev On Thu, Jun 10, 2021 at 10:52:37AM -0700, Alexei Starovoitov wrote: > On Thu, Jun 10, 2021 at 10:06 AM Kees Cook <keescook@chromium.org> wrote: > > > > > > 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-10 20:00 ` Eric Biggers @ 2021-06-15 16:42 ` Kurt Manucredo 2021-06-15 18:51 ` Edward Cree 0 siblings, 1 reply; 28+ messages in thread From: Kurt Manucredo @ 2021-06-15 16:42 UTC (permalink / raw) To: ebiggers, syzbot+bed360704c521841c85d Cc: Kurt Manucredo, keescook, yhs, dvyukov, andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev 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 <fuzzybritches0@gmail.com> --- 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 ^ permalink raw reply related [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 16:42 ` [PATCH v5] " Kurt Manucredo @ 2021-06-15 18:51 ` Edward Cree 2021-06-15 19:33 ` Eric Biggers 0 siblings, 1 reply; 28+ messages in thread From: Edward Cree @ 2021-06-15 18:51 UTC (permalink / raw) To: Kurt Manucredo, ebiggers, syzbot+bed360704c521841c85d Cc: keescook, yhs, dvyukov, andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 18:51 ` Edward Cree @ 2021-06-15 19:33 ` Eric Biggers 2021-06-15 21:08 ` Daniel Borkmann 0 siblings, 1 reply; 28+ messages in thread From: Eric Biggers @ 2021-06-15 19:33 UTC (permalink / raw) To: Edward Cree Cc: Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 19:33 ` Eric Biggers @ 2021-06-15 21:08 ` Daniel Borkmann 2021-06-15 21:32 ` Eric Biggers 0 siblings, 1 reply; 28+ messages in thread From: Daniel Borkmann @ 2021-06-15 21:08 UTC (permalink / raw) To: Eric Biggers, Edward Cree Cc: Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On 6/15/21 9:33 PM, Eric Biggers wrote: > 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. 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 21:08 ` Daniel Borkmann @ 2021-06-15 21:32 ` Eric Biggers 2021-06-15 21:38 ` Eric Biggers 0 siblings, 1 reply; 28+ messages in thread From: Eric Biggers @ 2021-06-15 21:32 UTC (permalink / raw) To: Daniel Borkmann Cc: Edward Cree, Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: > On 6/15/21 9:33 PM, Eric Biggers wrote: > > 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. > > 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 ^ permalink raw reply related [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 21:32 ` Eric Biggers @ 2021-06-15 21:38 ` Eric Biggers 2021-06-15 21:54 ` Daniel Borkmann 0 siblings, 1 reply; 28+ messages in thread From: Eric Biggers @ 2021-06-15 21:38 UTC (permalink / raw) To: Daniel Borkmann Cc: Edward Cree, Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote: > On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: > > On 6/15/21 9:33 PM, Eric Biggers wrote: > > > 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. > > > > 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 > Note, I missed the arithmetic right shifts later on in the function. Same result there, though. - Eric ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 21:38 ` Eric Biggers @ 2021-06-15 21:54 ` Daniel Borkmann 2021-06-15 22:07 ` Eric Biggers 0 siblings, 1 reply; 28+ messages in thread From: Daniel Borkmann @ 2021-06-15 21:54 UTC (permalink / raw) To: Eric Biggers Cc: Edward Cree, Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On 6/15/21 11:38 PM, Eric Biggers wrote: > On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote: >> On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: >>> On 6/15/21 9:33 PM, Eric Biggers wrote: >>>> 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. >>> >>> 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. >> + */ >> +#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? >> 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 > ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 21:54 ` Daniel Borkmann @ 2021-06-15 22:07 ` Eric Biggers 2021-06-15 22:31 ` Kurt Manucredo 2021-06-17 10:09 ` Daniel Borkmann 0 siblings, 2 replies; 28+ messages in thread From: Eric Biggers @ 2021-06-15 22:07 UTC (permalink / raw) To: Daniel Borkmann Cc: Edward Cree, Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote: > On 6/15/21 11:38 PM, Eric Biggers wrote: > > On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote: > > > On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: > > > > On 6/15/21 9:33 PM, Eric Biggers wrote: > > > > > 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. > > > > > > > > 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. > > > > + */ > > > +#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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 22:07 ` Eric Biggers @ 2021-06-15 22:31 ` Kurt Manucredo 2021-06-17 10:09 ` Daniel Borkmann 1 sibling, 0 replies; 28+ messages in thread From: Kurt Manucredo @ 2021-06-15 22:31 UTC (permalink / raw) To: ebiggers, daniel Cc: ecree.xilinx, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On Tue, 15 Jun 2021 15:07:43 -0700, Eric Biggers <ebiggers@kernel.org> wrote: > > On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote: > > On 6/15/21 11:38 PM, Eric Biggers wrote: > > > On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote: > > > > On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: > > > > > On 6/15/21 9:33 PM, Eric Biggers wrote: > > > > > > 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. > > > > > > > > > > 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. > > > > > > > + */ > > > > +#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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v5] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-15 22:07 ` Eric Biggers 2021-06-15 22:31 ` Kurt Manucredo @ 2021-06-17 10:09 ` Daniel Borkmann 1 sibling, 0 replies; 28+ messages in thread From: Daniel Borkmann @ 2021-06-17 10:09 UTC (permalink / raw) To: Eric Biggers Cc: Edward Cree, Kurt Manucredo, syzbot+bed360704c521841c85d, keescook, yhs, dvyukov, andrii, ast, bpf, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, kernel-hardening, kasan-dev On 6/16/21 12:07 AM, Eric Biggers wrote: > On Tue, Jun 15, 2021 at 11:54:41PM +0200, Daniel Borkmann wrote: >> On 6/15/21 11:38 PM, Eric Biggers wrote: >>> On Tue, Jun 15, 2021 at 02:32:18PM -0700, Eric Biggers wrote: >>>> On Tue, Jun 15, 2021 at 11:08:18PM +0200, Daniel Borkmann wrote: >>>>> On 6/15/21 9:33 PM, Eric Biggers wrote: >>>>>> 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. >>>>> >>>>> 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. > >> >>>> + */ >>>> +#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 ^ permalink raw reply [flat|nested] 28+ messages in thread
* Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run 2021-06-05 17:55 ` Yonghong Song 2021-06-05 19:10 ` Alexei Starovoitov @ 2021-06-06 19:15 ` Kurt Manucredo 1 sibling, 0 replies; 28+ messages in thread From: Kurt Manucredo @ 2021-06-06 19:15 UTC (permalink / raw) To: syzbot+bed360704c521841c85d, yhs Cc: andrii, ast, bpf, daniel, davem, hawk, john.fastabend, kafai, kpsingh, kuba, linux-kernel, netdev, songliubraving, syzkaller-bugs, nathan, ndesaulniers, clang-built-linux, linux-kernel-mentees, skhan, gregkh On Sat, 5 Jun 2021 10:55:25 -0700, Yonghong Song <yhs@fb.com> wrote: > > > > 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 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 <fuzzybritches0@gmail.com> > > --- > > > > 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. > > + > > 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 ^ permalink raw reply [flat|nested] 28+ messages in thread
end of thread, other threads:[~2021-06-17 10:09 UTC | newest] Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-03-10 16:05 [syzbot] UBSAN: shift-out-of-bounds in ___bpf_prog_run syzbot 2021-03-28 3:38 ` syzbot 2021-06-02 21:27 ` [PATCH v3] bpf: core: fix " Kurt Manucredo 2021-06-03 4:43 ` Greg KH 2021-06-05 15:01 ` [PATCH v4] " Kurt Manucredo 2021-06-05 17:55 ` Yonghong Song 2021-06-05 19:10 ` Alexei Starovoitov 2021-06-05 21:39 ` Yonghong Song 2021-06-06 19:44 ` Kurt Manucredo 2021-06-07 7:38 ` Dmitry Vyukov 2021-06-09 18:20 ` Kees Cook 2021-06-09 23:40 ` Yonghong Song 2021-06-10 5:32 ` Dmitry Vyukov 2021-06-10 6:06 ` Yonghong Song 2021-06-10 17:06 ` Kees Cook 2021-06-10 17:52 ` Alexei Starovoitov 2021-06-10 20:00 ` Eric Biggers 2021-06-15 16:42 ` [PATCH v5] " Kurt Manucredo 2021-06-15 18:51 ` Edward Cree 2021-06-15 19:33 ` Eric Biggers 2021-06-15 21:08 ` Daniel Borkmann 2021-06-15 21:32 ` Eric Biggers 2021-06-15 21:38 ` Eric Biggers 2021-06-15 21:54 ` Daniel Borkmann 2021-06-15 22:07 ` Eric Biggers 2021-06-15 22:31 ` Kurt Manucredo 2021-06-17 10:09 ` Daniel Borkmann 2021-06-06 19:15 ` [PATCH v4] " Kurt Manucredo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).