From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-12.8 required=3.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER,INCLUDES_PATCH, MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8330FC4743F for ; Sun, 6 Jun 2021 19:42:09 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id 651FE61209 for ; Sun, 6 Jun 2021 19:42:09 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229813AbhFFTn6 (ORCPT ); Sun, 6 Jun 2021 15:43:58 -0400 Received: from mail-wr1-f44.google.com ([209.85.221.44]:39569 "EHLO mail-wr1-f44.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229799AbhFFTn4 (ORCPT ); Sun, 6 Jun 2021 15:43:56 -0400 Received: by mail-wr1-f44.google.com with SMTP id l2so15013890wrw.6; Sun, 06 Jun 2021 12:41:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=cc:to:from:message-id:in-reply-to:references:date:subject; bh=oZ1GBZrLrWXtFesbiX91BZUiYjDuBUEVaSbSR2qwXnk=; b=Vb7IpsFy+BRK9mzlMUFUVTpdpPwQgx02PAl7qfZN0OpzSd9XTK9vScN0k9i3S+Ur4h AFdi91WOX/K4e+2eMsAqEApSTWKeCHNfvZQcuadANxmO2pX+iqw81EKL6JeNmagsqWpB A7RAHnvFb/cQ8FdUM32kdyr8lRM9Z0WIGwCOu1Rqf7UhOTqEmUxj3tPGvyQYoK5nAOjS MlboEBKLlQ9zocUlka0a+QP9DeIbk7swJPuRXLDnTcpcKK1f0zGvl7O5yHbii+uH7Tmm umi32cSNu3n+Q2xR3Fe7h/6SJqjy0SICy8v1+9pBvuoh9KvaF0G7aBQiKv0OhFLRuIsU ihvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:cc:to:from:message-id:in-reply-to:references :date:subject; bh=oZ1GBZrLrWXtFesbiX91BZUiYjDuBUEVaSbSR2qwXnk=; b=End6g0Ca6J0d3k7CeTrXNY+1lL72fSHcs9bqPbALsCQADC1zpjubkm+MkRPcuUI65D vEd8HoFlnOQEstOMLGRlElQdZFXlT5CV853YT7g5ivdcm6xJB4s9GXgb0lBRCWQsbdWK 8ngfiXiPW/OWCUk6sGy/1BoL0QXk3LAP+M3nxJ+9UogFgxUf2htBsO76dOGn3fKIBvIt oMZpJvIqjJDRoQanNLedDwlvzWCg1suSLqLSDxlt22XG2em8velQFu766fTHMtiLvWJi TVf+Dh73kW43n3uLYgTAoTuox3+9jNH6XNqT/UgcGQSXB3iAhECHiOsyXRPbC4Ap/bmD TfEg== X-Gm-Message-State: AOAM531UWn5CuymJQl/MXkiV3bxBqH3jwJt4SymQJFz91jwtXpk6ghrP Xb/OjFGeQWmd+CdSnlK25/A= X-Google-Smtp-Source: ABdhPJy5jJ91aNujE1QtO1DS2ck9EWnjopyoYjaJ6DQaRnIsh7ax62b4yVNiRpDVe+DXfmwFWs3rYQ== X-Received: by 2002:a05:6000:18ac:: with SMTP id b12mr13369745wri.44.1623008448271; Sun, 06 Jun 2021 12:40:48 -0700 (PDT) Received: from localhost ([185.199.80.151]) by smtp.gmail.com with ESMTPSA id n10sm15227477wre.95.2021.06.06.12.40.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 06 Jun 2021 12:40:47 -0700 (PDT) Cc: andrii@kernel.org, ast@kernel.org, bpf@vger.kernel.org, daniel@iogearbox.net, davem@davemloft.net, hawk@kernel.org, john.fastabend@gmail.com, kafai@fb.com, kpsingh@kernel.org, kuba@kernel.org, linux-kernel@vger.kernel.org, netdev@vger.kernel.org, songliubraving@fb.com, syzkaller-bugs@googlegroups.com, nathan@kernel.org, ndesaulniers@google.com, clang-built-linux@googlegroups.com, linux-kernel-mentees@lists.linuxfoundation.org, skhan@linuxfoundation.org, gregkh@linuxfoundation.org To: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com, yhs@fb.com From: "Kurt Manucredo" Message-ID: <20484-14561-curtm@phaethon> In-Reply-To: <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> References: <000000000000c2987605be907e41@google.com> <20210602212726.7-1-fuzzybritches0@gmail.com> <87609-531187-curtm@phaethon> <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> Date: Sun, 06 Jun 2021 21:15:46 +0200 Subject: Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, 5 Jun 2021 10:55:25 -0700, Yonghong Song 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 > > --- > > > > 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-10.5 required=3.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED,DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FORGED_FROMDOMAIN, FREEMAIL_FROM,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_CR_TRAILER, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5ED0AC4743D for ; Sun, 6 Jun 2021 19:40:54 +0000 (UTC) Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id DA0CC6141E for ; Sun, 6 Jun 2021 19:40:53 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org DA0CC6141E Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=gmail.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=linux-kernel-mentees-bounces@lists.linuxfoundation.org Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 9C898607BB; Sun, 6 Jun 2021 19:40:53 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mcrBIU1V-YpT; Sun, 6 Jun 2021 19:40:52 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp3.osuosl.org (Postfix) with ESMTP id 9C74E606C2; Sun, 6 Jun 2021 19:40:52 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7150BC000D; Sun, 6 Jun 2021 19:40:52 +0000 (UTC) Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 77D27C0001 for ; Sun, 6 Jun 2021 19:40:51 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 51DC04018F for ; Sun, 6 Jun 2021 19:40:51 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id my1PURtMm8Bq for ; Sun, 6 Jun 2021 19:40:50 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-wr1-x42b.google.com (mail-wr1-x42b.google.com [IPv6:2a00:1450:4864:20::42b]) by smtp2.osuosl.org (Postfix) with ESMTPS id 445F0400C7 for ; Sun, 6 Jun 2021 19:40:50 +0000 (UTC) Received: by mail-wr1-x42b.google.com with SMTP id c5so14955701wrq.9 for ; Sun, 06 Jun 2021 12:40:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=cc:to:from:message-id:in-reply-to:references:date:subject; bh=oZ1GBZrLrWXtFesbiX91BZUiYjDuBUEVaSbSR2qwXnk=; b=Vb7IpsFy+BRK9mzlMUFUVTpdpPwQgx02PAl7qfZN0OpzSd9XTK9vScN0k9i3S+Ur4h AFdi91WOX/K4e+2eMsAqEApSTWKeCHNfvZQcuadANxmO2pX+iqw81EKL6JeNmagsqWpB A7RAHnvFb/cQ8FdUM32kdyr8lRM9Z0WIGwCOu1Rqf7UhOTqEmUxj3tPGvyQYoK5nAOjS MlboEBKLlQ9zocUlka0a+QP9DeIbk7swJPuRXLDnTcpcKK1f0zGvl7O5yHbii+uH7Tmm umi32cSNu3n+Q2xR3Fe7h/6SJqjy0SICy8v1+9pBvuoh9KvaF0G7aBQiKv0OhFLRuIsU ihvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:cc:to:from:message-id:in-reply-to:references :date:subject; bh=oZ1GBZrLrWXtFesbiX91BZUiYjDuBUEVaSbSR2qwXnk=; b=tnTi8PGO7M3pYM7jTzHmy26e5mXoF7Y1fA/e0NvzHr4HrRqSbIADVc0PQ/AOEk3jng Qpip7xucEBTG4CtABZYCpzT5CmicwKsNjISYXlUqVCQiXaJKFTtyY+CuU+ZtrMWuagJA 5mvds38MuZYxl8ywrC9tBP3sjBeMYBFEFxW5v12wKm0JOOfqxJN4H840Z4c4kWTXfFy5 FYIZfmEByWxdf835QezufmTrOdTcW5UiPseArxJ4QhvL+qjvJPWVo3rMgMqI14PGB+3o bS1HLX+4h4PcIwEIGPoagps4RPQ8bUPA/aIHhoytOeFgoEOQFdGeXd2sKXg0SKGTAPBv Wjfg== X-Gm-Message-State: AOAM532nqWEdiLmgpWB/1SGrMMFhzHCBlShq1AiVWi1ydRfbD9GVGX8f kI7tILCMC55dAhZwdNJs7iQ= X-Google-Smtp-Source: ABdhPJy5jJ91aNujE1QtO1DS2ck9EWnjopyoYjaJ6DQaRnIsh7ax62b4yVNiRpDVe+DXfmwFWs3rYQ== X-Received: by 2002:a05:6000:18ac:: with SMTP id b12mr13369745wri.44.1623008448271; Sun, 06 Jun 2021 12:40:48 -0700 (PDT) Received: from localhost ([185.199.80.151]) by smtp.gmail.com with ESMTPSA id n10sm15227477wre.95.2021.06.06.12.40.46 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 06 Jun 2021 12:40:47 -0700 (PDT) To: syzbot+bed360704c521841c85d@syzkaller.appspotmail.com, yhs@fb.com From: "Kurt Manucredo" Message-ID: <20484-14561-curtm@phaethon> In-Reply-To: <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> References: <000000000000c2987605be907e41@google.com> <20210602212726.7-1-fuzzybritches0@gmail.com> <87609-531187-curtm@phaethon> <6a392b66-6f26-4532-d25f-6b09770ce366@fb.com> Date: Sun, 06 Jun 2021 21:15:46 +0200 Subject: Re: [PATCH v4] bpf: core: fix shift-out-of-bounds in ___bpf_prog_run Cc: nathan@kernel.org, songliubraving@fb.com, kafai@fb.com, hawk@kernel.org, daniel@iogearbox.net, linux-kernel@vger.kernel.org, john.fastabend@gmail.com, andrii@kernel.org, ast@kernel.org, syzkaller-bugs@googlegroups.com, clang-built-linux@googlegroups.com, ndesaulniers@google.com, netdev@vger.kernel.org, kpsingh@kernel.org, kuba@kernel.org, bpf@vger.kernel.org, linux-kernel-mentees@lists.linuxfoundation.org, davem@davemloft.net X-BeenThere: linux-kernel-mentees@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: linux-kernel-mentees-bounces@lists.linuxfoundation.org Sender: "Linux-kernel-mentees" On Sat, 5 Jun 2021 10:55:25 -0700, Yonghong Song 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 > > --- > > > > 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 _______________________________________________ Linux-kernel-mentees mailing list Linux-kernel-mentees@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/linux-kernel-mentees