From: Alexei Starovoitov <alexei.starovoitov@gmail.com> To: Yonghong Song <yhs@fb.com> Cc: Kurt Manucredo <fuzzybritches0@gmail.com>, syzbot+bed360704c521841c85d@syzkaller.appspotmail.com, Andrii Nakryiko <andrii@kernel.org>, Alexei Starovoitov <ast@kernel.org>, bpf <bpf@vger.kernel.org>, Daniel Borkmann <daniel@iogearbox.net>, "David S. Miller" <davem@davemloft.net>, Jesper Dangaard Brouer <hawk@kernel.org>, John Fastabend <john.fastabend@gmail.com>, Martin KaFai Lau <kafai@fb.com>, KP Singh <kpsingh@kernel.org>, Jakub Kicinski <kuba@kernel.org>, LKML <linux-kernel@vger.kernel.org>, Network Development <netdev@vger.kernel.org>, Song Liu <songliubraving@fb.com>, syzkaller-bugs <syzkaller-bugs@googlegroups.com>, nathan@kernel.org, Nick Desaulniers <ndesaulniers@google.com>, Clang-Built-Linux ML <clang-built-linux@googlegroups.com>, linux-kernel-mentees@lists.linuxfoundation.org, Shuah Khan <skhan@linuxfoundation.org>, Greg Kroah-Hartman <gregkh@linuxfoundation.org> Subject: Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run Date: Sat, 5 Jun 2021 12:10:26 -0700 [thread overview] Message-ID: <CAADnVQKexxZQw0yK_7rmFOdaYabaFpi2EmF6RGs5bXvFHtUQaA@mail.gmail.com> (raw) In-Reply-To: <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> 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.
WARNING: multiple messages have this Message-ID (diff)
From: Alexei Starovoitov <alexei.starovoitov@gmail.com> To: Yonghong Song <yhs@fb.com> Cc: Song Liu <songliubraving@fb.com>, Alexei Starovoitov <ast@kernel.org>, Andrii Nakryiko <andrii@kernel.org>, syzbot+bed360704c521841c85d@syzkaller.appspotmail.com, Daniel Borkmann <daniel@iogearbox.net>, John Fastabend <john.fastabend@gmail.com>, Clang-Built-Linux ML <clang-built-linux@googlegroups.com>, Jakub Kicinski <kuba@kernel.org>, linux-kernel-mentees@lists.linuxfoundation.org, Jesper Dangaard Brouer <hawk@kernel.org>, syzkaller-bugs <syzkaller-bugs@googlegroups.com>, KP Singh <kpsingh@kernel.org>, nathan@kernel.org, Nick Desaulniers <ndesaulniers@google.com>, LKML <linux-kernel@vger.kernel.org>, "David S. Miller" <davem@davemloft.net>, Network Development <netdev@vger.kernel.org>, bpf <bpf@vger.kernel.org>, Martin KaFai Lau <kafai@fb.com> Subject: Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run Date: Sat, 5 Jun 2021 12:10:26 -0700 [thread overview] Message-ID: <CAADnVQKexxZQw0yK_7rmFOdaYabaFpi2EmF6RGs5bXvFHtUQaA@mail.gmail.com> (raw) In-Reply-To: <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> 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. _______________________________________________ Linux-kernel-mentees mailing list Linux-kernel-mentees@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees
next prev parent reply other threads:[~2021-06-05 19:11 UTC|newest] Thread overview: 47+ messages / expand[flat|nested] mbox.gz Atom feed top 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-02 21:27 ` Kurt Manucredo 2021-06-03 4:43 ` Greg KH 2021-06-03 4:43 ` Greg KH 2021-06-05 15:01 ` [PATCH v4] " Kurt Manucredo 2021-06-05 15:01 ` Kurt Manucredo 2021-06-05 17:55 ` Yonghong Song 2021-06-05 17:55 ` Yonghong Song via Linux-kernel-mentees 2021-06-05 19:10 ` Alexei Starovoitov [this message] 2021-06-05 19:10 ` Alexei Starovoitov 2021-06-05 21:39 ` Yonghong Song 2021-06-05 21:39 ` Yonghong Song via Linux-kernel-mentees 2021-06-06 19:44 ` Kurt Manucredo 2021-06-06 19:44 ` Kurt Manucredo 2021-06-07 7:38 ` Dmitry Vyukov 2021-06-07 7:38 ` Dmitry Vyukov 2021-06-07 7:38 ` Dmitry Vyukov via Linux-kernel-mentees 2021-06-09 18:20 ` Kees Cook 2021-06-09 18:20 ` Kees Cook 2021-06-09 23:40 ` Yonghong Song 2021-06-09 23:40 ` Yonghong Song via Linux-kernel-mentees 2021-06-10 5:32 ` Dmitry Vyukov 2021-06-10 5:32 ` Dmitry Vyukov 2021-06-10 5:32 ` Dmitry Vyukov via Linux-kernel-mentees 2021-06-10 6:06 ` Yonghong Song 2021-06-10 6:06 ` Yonghong Song via Linux-kernel-mentees 2021-06-10 17:06 ` Kees Cook 2021-06-10 17:06 ` Kees Cook 2021-06-10 17:52 ` Alexei Starovoitov 2021-06-10 17:52 ` Alexei Starovoitov 2021-06-10 17:52 ` Alexei Starovoitov 2021-06-10 20:00 ` Eric Biggers 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 2021-06-06 19:15 ` Kurt Manucredo
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=CAADnVQKexxZQw0yK_7rmFOdaYabaFpi2EmF6RGs5bXvFHtUQaA@mail.gmail.com \ --to=alexei.starovoitov@gmail.com \ --cc=andrii@kernel.org \ --cc=ast@kernel.org \ --cc=bpf@vger.kernel.org \ --cc=clang-built-linux@googlegroups.com \ --cc=daniel@iogearbox.net \ --cc=davem@davemloft.net \ --cc=fuzzybritches0@gmail.com \ --cc=gregkh@linuxfoundation.org \ --cc=hawk@kernel.org \ --cc=john.fastabend@gmail.com \ --cc=kafai@fb.com \ --cc=kpsingh@kernel.org \ --cc=kuba@kernel.org \ --cc=linux-kernel-mentees@lists.linuxfoundation.org \ --cc=linux-kernel@vger.kernel.org \ --cc=nathan@kernel.org \ --cc=ndesaulniers@google.com \ --cc=netdev@vger.kernel.org \ --cc=skhan@linuxfoundation.org \ --cc=songliubraving@fb.com \ --cc=syzbot+bed360704c521841c85d@syzkaller.appspotmail.com \ --cc=syzkaller-bugs@googlegroups.com \ --cc=yhs@fb.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.