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.6 required=3.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,INCLUDES_PATCH,MAILING_LIST_MULTI, MENTIONS_GIT_HOSTING,SPF_HELO_NONE,SPF_PASS,USER_AGENT_SANE_1 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 DE525C47247 for ; Fri, 8 May 2020 11:47:17 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id BD44620A8B for ; Fri, 8 May 2020 11:47:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1588938437; bh=t1Iwu24XFt/a9NpFSyEL3vQir1AT95eNfYgPSI3dRXk=; h=Date:From:To:Cc:Subject:References:In-Reply-To:List-ID:From; b=XX072S2CdchhqhhmUK+aV/12q53B/Q87/r4GkEsrKrxE7idrUoH8gIOVMXRzIYnbZ 6ZykUcDF8Sm5Qv3X51rOrKlJqJFZxp9dewjotcFd5ZzkJQNq+IR+pk+b4CZc4ojlA2 9eYdtDJDYIs7HbVTH2Y3kEXgGWMii9+iE+aVi1ow= Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726904AbgEHLrR (ORCPT ); Fri, 8 May 2020 07:47:17 -0400 Received: from mail.kernel.org ([198.145.29.99]:41932 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726618AbgEHLrR (ORCPT ); Fri, 8 May 2020 07:47:17 -0400 Received: from willie-the-truck (236.31.169.217.in-addr.arpa [217.169.31.236]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 4AF1C208DB; Fri, 8 May 2020 11:47:13 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1588938436; bh=t1Iwu24XFt/a9NpFSyEL3vQir1AT95eNfYgPSI3dRXk=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Fbr0ksTlgIL5FTsuoGevS/1Dfx/6oKLeeINEHrjnfmHHcaDmHd5vjhSs6V/18OxQl d87ngXBx/xymM9BE8xEn5y929HYpCE0cwOKixvFuxVhneks1P992dmKU3twX75N40j S/0gFC6NylCeiDyMUntAk0xuU23GFqIAXLPGpZOc= Date: Fri, 8 May 2020 12:47:10 +0100 From: Will Deacon To: Luke Nelson Cc: Marc Zyngier , Luke Nelson , bpf , Xi Wang , Catalin Marinas , Daniel Borkmann , Alexei Starovoitov , Zi Shen Lim , Martin KaFai Lau , Song Liu , Yonghong Song , Andrii Nakryiko , John Fastabend , KP Singh , Mark Rutland , Greg Kroah-Hartman , Thomas Gleixner , linux-arm-kernel@lists.infradead.org, open list , Networking , clang-built-linux@googlegroups.com Subject: Re: [RFC PATCH bpf-next 1/3] arm64: insn: Fix two bugs in encoding 32-bit logical immediates Message-ID: <20200508114709.GB16247@willie-the-truck> References: <20200507010504.26352-1-luke.r.nels@gmail.com> <20200507010504.26352-2-luke.r.nels@gmail.com> <20200507082934.GA28215@willie-the-truck> <20200507101224.33a44d71@why> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Thu, May 07, 2020 at 02:48:07PM -0700, Luke Nelson wrote: > Thanks for the comments! Responses below: > > > It's a bit grotty spreading the checks out now. How about we tweak things > > slightly along the lines of: > > > > > > diff --git a/arch/arm64/kernel/insn.c b/arch/arm64/kernel/insn.c > > index 4a9e773a177f..60ec788eaf33 100644 > > --- a/arch/arm64/kernel/insn.c > > +++ b/arch/arm64/kernel/insn.c > > [...] > > Agreed; this new version looks much cleaner. I re-ran all the tests / > verification and everything seems good. Would you like me to submit a > v2 of this series with this new code? Yes, please! And please include Daniel's acks on the BPF changes too. It's a public holiday here in the UK today, but I can pick this up next week. > >> We tested the new code against llvm-mc with all 1,302 encodable 32-bit > >> logical immediates and all 5,334 encodable 64-bit logical immediates. > > > > That, on its own, is awesome information. Do you have any pointer on > > how to set this up? > > Sure! The process of running the tests is pretty involved, but I'll > describe it below and give some links here. > > We found the bugs in insn.c while adding support for logical immediates > to the BPF JIT and verifying the changes with our tool, Serval: > https://github.com/uw-unsat/serval-bpf. The basic idea for how we tested / > verified logical immediates is the following: > > First, we have a Python script [1] for generating every encodable > logical immediate and the corresponding instruction fields that encode > that immediate. The script validates the list by checking that llvm-mc > decodes each instruction back to the expected immediate. > > Next, we use the list [2] from the first step to check a Racket > translation [3] of the logical immediate encoding function in insn.c. > We found the second mask bug by noticing that some (encodable) 32-bit > immediates were being rejected by the encoding function. > > Last, we use the Racket translation of the encoding function to verify > the correctness of the BPF JIT implementation [4], i.e., the JIT > correctly compiles BPF_{AND,OR,XOR,JSET} BPF_K instructions to arm64 > instructions with equivalent semantics. We found the first bug as the > verifier complained that the function was producing invalid encodings > for 32-bit -1 immediates, and we were able to reproduce a kernel crash > using the BPF tests. > > We manually translated the C code to Racket because our verifier, Serval, > currently only works on Racket code. Nice! Two things: (1) I really think you should give a talk on this at a Linux conference (2) Did you look at any instruction generation functions other than the logical immediate encoding function? Cheers, Will 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=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,INCLUDES_PATCH,MAILING_LIST_MULTI,MENTIONS_GIT_HOSTING, SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED,USER_AGENT_SANE_1 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 00261C47254 for ; Fri, 8 May 2020 11:47:21 +0000 (UTC) Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (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 CBE5F20A8B for ; Fri, 8 May 2020 11:47:20 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="iIwQHZu8"; dkim=fail reason="signature verification failed" (1024-bit key) header.d=kernel.org header.i=@kernel.org header.b="Fbr0ksTl" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org CBE5F20A8B Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=kernel.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20170209; h=Sender: Content-Transfer-Encoding:Content-Type:Cc:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:In-Reply-To:MIME-Version:References: Message-ID:Subject:To:From:Date:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=F38INhe7oTJcUh/gb6ke4qFWXuG5RoHIUS/3Lps7kBc=; b=iIwQHZu8BSGm1A VQhJC9EJ6Rxi2dzHAmoAg9wMxDqTDKcahWvq1QhNHVrmpAzZ5LWKZnHQ9nvbzUjRuh/L3khzhu2Zi TR3XfvRQapS8mYOynIVlWPpjs/Vv+UBzJ5oGzfzeGn8DHqcBYSGCFe5Dfic3TfzOoR2150cMtoK4y ea7YP4I2h8nN+YILBE1FW6PzPGfdviE7bQPDq2hkDaF5GP60ZnhVJjZPnmR3JS//Ej9ipju7x8fww 0s2r7c6HqkhRI4m91cGMeEH2RH8WlQL720sScnlIkVVaYOFlLfEVsVKZ2YamCdDAUeqB0NPfm1woj Tv0PG2CzhMVrvtq/boVQ==; Received: from localhost ([127.0.0.1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX1TM-0005MV-As; Fri, 08 May 2020 11:47:20 +0000 Received: from mail.kernel.org ([198.145.29.99]) by bombadil.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1jX1TJ-0005Ll-1X for linux-arm-kernel@lists.infradead.org; Fri, 08 May 2020 11:47:18 +0000 Received: from willie-the-truck (236.31.169.217.in-addr.arpa [217.169.31.236]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 4AF1C208DB; Fri, 8 May 2020 11:47:13 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=default; t=1588938436; bh=t1Iwu24XFt/a9NpFSyEL3vQir1AT95eNfYgPSI3dRXk=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=Fbr0ksTlgIL5FTsuoGevS/1Dfx/6oKLeeINEHrjnfmHHcaDmHd5vjhSs6V/18OxQl d87ngXBx/xymM9BE8xEn5y929HYpCE0cwOKixvFuxVhneks1P992dmKU3twX75N40j S/0gFC6NylCeiDyMUntAk0xuU23GFqIAXLPGpZOc= Date: Fri, 8 May 2020 12:47:10 +0100 From: Will Deacon To: Luke Nelson Subject: Re: [RFC PATCH bpf-next 1/3] arm64: insn: Fix two bugs in encoding 32-bit logical immediates Message-ID: <20200508114709.GB16247@willie-the-truck> References: <20200507010504.26352-1-luke.r.nels@gmail.com> <20200507010504.26352-2-luke.r.nels@gmail.com> <20200507082934.GA28215@willie-the-truck> <20200507101224.33a44d71@why> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200508_044717_129253_A9065120 X-CRM114-Status: GOOD ( 23.69 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Mark Rutland , Song Liu , clang-built-linux@googlegroups.com, Daniel Borkmann , Greg Kroah-Hartman , Marc Zyngier , John Fastabend , Alexei Starovoitov , open list , Networking , KP Singh , Luke Nelson , Thomas Gleixner , linux-arm-kernel@lists.infradead.org, Catalin Marinas , Zi Shen Lim , Yonghong Song , bpf , Andrii Nakryiko , Martin KaFai Lau , Xi Wang Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+infradead-linux-arm-kernel=archiver.kernel.org@lists.infradead.org On Thu, May 07, 2020 at 02:48:07PM -0700, Luke Nelson wrote: > Thanks for the comments! Responses below: > > > It's a bit grotty spreading the checks out now. How about we tweak things > > slightly along the lines of: > > > > > > diff --git a/arch/arm64/kernel/insn.c b/arch/arm64/kernel/insn.c > > index 4a9e773a177f..60ec788eaf33 100644 > > --- a/arch/arm64/kernel/insn.c > > +++ b/arch/arm64/kernel/insn.c > > [...] > > Agreed; this new version looks much cleaner. I re-ran all the tests / > verification and everything seems good. Would you like me to submit a > v2 of this series with this new code? Yes, please! And please include Daniel's acks on the BPF changes too. It's a public holiday here in the UK today, but I can pick this up next week. > >> We tested the new code against llvm-mc with all 1,302 encodable 32-bit > >> logical immediates and all 5,334 encodable 64-bit logical immediates. > > > > That, on its own, is awesome information. Do you have any pointer on > > how to set this up? > > Sure! The process of running the tests is pretty involved, but I'll > describe it below and give some links here. > > We found the bugs in insn.c while adding support for logical immediates > to the BPF JIT and verifying the changes with our tool, Serval: > https://github.com/uw-unsat/serval-bpf. The basic idea for how we tested / > verified logical immediates is the following: > > First, we have a Python script [1] for generating every encodable > logical immediate and the corresponding instruction fields that encode > that immediate. The script validates the list by checking that llvm-mc > decodes each instruction back to the expected immediate. > > Next, we use the list [2] from the first step to check a Racket > translation [3] of the logical immediate encoding function in insn.c. > We found the second mask bug by noticing that some (encodable) 32-bit > immediates were being rejected by the encoding function. > > Last, we use the Racket translation of the encoding function to verify > the correctness of the BPF JIT implementation [4], i.e., the JIT > correctly compiles BPF_{AND,OR,XOR,JSET} BPF_K instructions to arm64 > instructions with equivalent semantics. We found the first bug as the > verifier complained that the function was producing invalid encodings > for 32-bit -1 immediates, and we were able to reproduce a kernel crash > using the BPF tests. > > We manually translated the C code to Racket because our verifier, Serval, > currently only works on Racket code. Nice! Two things: (1) I really think you should give a talk on this at a Linux conference (2) Did you look at any instruction generation functions other than the logical immediate encoding function? Cheers, Will _______________________________________________ linux-arm-kernel mailing list linux-arm-kernel@lists.infradead.org http://lists.infradead.org/mailman/listinfo/linux-arm-kernel