From patchwork Tue Aug 23 18:52:59 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kumar Kartikeya Dwivedi X-Patchwork-Id: 12952551 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 52570C32772 for ; Tue, 23 Aug 2022 19:50:18 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229602AbiHWTuQ (ORCPT ); Tue, 23 Aug 2022 15:50:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52964 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232459AbiHWTtk (ORCPT ); Tue, 23 Aug 2022 15:49:40 -0400 Received: from mail-ej1-x644.google.com (mail-ej1-x644.google.com [IPv6:2a00:1450:4864:20::644]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 656F6AB for ; Tue, 23 Aug 2022 11:53:08 -0700 (PDT) Received: by mail-ej1-x644.google.com with SMTP id ce26so13520312ejb.11 for ; Tue, 23 Aug 2022 11:53:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=2dOEuGGOPXsAXXBcbu/VW/hh2kSOMBgir3kb7gZmhSo=; b=S2UTpYOBicGjJDOpRNzBZtNnpjD/nkQK8z5Uzmdj7f4J2tUZW7ULPxcUyEFU0AwN98 isxxGN4QyvqlIWgS1ukNN/u1GfHyTvb6ezBGU1sVqR7B5H4RUcAZ28vQL9yB6HE4AUQc LdLPQH6LlA2fsH5zA8vm05T0l+MZqnYcGj4rOxdldp04rzHFo1yLz9jJGPcJHu3ON6xm HEBG+/e6YIXF1/Hv/E9RKrZeM3WiBCC2g/c+At5TJKOBBlebNDvbSJr/fs0s/cy6Jcs1 UI1vBimJz/kkavXp0CbvWqjfJAV/5/cvdsaeiKAVY32a5SBmJhHVB2tPgl1iybSbFNQH p0SA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=2dOEuGGOPXsAXXBcbu/VW/hh2kSOMBgir3kb7gZmhSo=; b=NOB/30Y5qfYnutLnU9oMBep37CJi8Htr0gFAaKbdgptB1YctKUb0dVF0xVlBUM/atU jq0Wop0g1hAMiSqKtUOIzGFwC1sMuOM7ptfr4m2rFgbtStK9bZxKLJ8ojCjaDfM9K2ne +EPr+hkdLdHCcQROeTRQbhJQ7RPuRODJCKin5EI+VOeWFj2UP4XyPYI0AOyoofOk2i1i vi+eYj+iB5q8ErP0jK/y+XrfX5HcQB1oZTkh3jwoaxAVULzdO/0Dr6w8qqB3YHuoRxm7 180rn441tsAKk811o0CcJRvQuoY/kGvBKS/PgrkkHOlaDweWBtoS41x+sYxo4qRMRBDq 97wA== X-Gm-Message-State: ACgBeo3S9pGq2glPX13YcPFtoAu/fRyxY1suSTB67h6d/XVgJ6X5uZvr L4eeld9/j56NHg8HettsJXIPV/NQj2w= X-Google-Smtp-Source: AA6agR44vj+/9L5YGPkL/vfRBLFtlGUBmTdleQT82rpDPR8Cf5i3lPNJgHIqfUlq9AgUq2vdICj97A== X-Received: by 2002:a17:906:93ef:b0:73d:9ef5:e577 with SMTP id yl15-20020a17090693ef00b0073d9ef5e577mr614389ejb.127.1661280786762; Tue, 23 Aug 2022 11:53:06 -0700 (PDT) Received: from localhost (vpn-254-130.epfl.ch. [128.179.254.130]) by smtp.gmail.com with ESMTPSA id z17-20020a50cd11000000b0043be16f5f4csm1872429edi.52.2022.08.23.11.53.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Aug 2022 11:53:06 -0700 (PDT) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann Subject: [PATCH bpf v1 1/2] bpf: Do mark_chain_precision for ARG_CONST_ALLOC_SIZE_OR_ZERO Date: Tue, 23 Aug 2022 20:52:59 +0200 Message-Id: <20220823185300.406-2-memxor@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220823185300.406-1-memxor@gmail.com> References: <20220823185300.406-1-memxor@gmail.com> MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=3478; i=memxor@gmail.com; h=from:subject; bh=Zic2rPrJHya0bfuj+Gvdco0EPQJKiWid70r/RKeo2tc=; b=owEBbQKS/ZANAwAKAUzgyIZIvxHKAcsmYgBjBSIEQtmLdWTmp26P2AJZC4+G4LuZb/FgCdK9dwu3 iZcb6ZeJAjMEAAEKAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCYwUiBAAKCRBM4MiGSL8RyrDzD/ 47NB8P1R2FrF6ERp3qQp5G8TBeYOwcS/43PV6bKcpBhU8/VZ9ZGiU/3grEmI7vLsaoYkrOi+xkKKOe TxKv3+KUH9bTnQT7yR3vmqrEmDrPVSiA5aCsaf6VJU3n7McFJVcL7HSCAVEto4i2YjabhgbhBJUgSX QmLhaZD9zzqRMhGEB7G0UJO/X8FcXMvBEHagliJh0JUd/SoyrP6CQbZzuRMk+K3vqIYrjAaOCLEKoz SUXoYwJRFMe0qlstuVBqo5Ff2fROdS++vbOhMQz0WazkAr+7D2j+R3faA1qjwcQIzTvm5o0maOpkRI QseIccKT14hSo8eMDLokyqEEyWipBO/iSo+KAhcUeembLYcOUnqrJRXw79T2WWWNEWjH6EW9ebu0jK kJflLnDADJSPbkItnNuFM8mN3fdsDDqI0XVxDYYZzj/6o9YH8ADzyfTwTbz026vSTc4qpBbFw8nCwX T87yewvAmFO+vo7DYHQ5/XT1Il8FgQBgCj8+KMGiPSyLstf9vAW+UhGatePGllNihrlXZUaBkkW2FT xM8jtrVqXid7r3xdc7N3HUeeNDWXGKOgTT3G6hcafUNM6UGOqaPT7X0jvXo+huV+IPoU9HZlXcU4Aj i9wmjwB0xkuBoRu2jLj0su4S1diQ7iXtu6zhYnj2bVPvNKsoyHMwc4Ag31aA== X-Developer-Key: i=memxor@gmail.com; a=openpgp; fpr=4BBE2A7E06ECF9D5823C61114CE0C88648BF11CA Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Precision markers need to be propagated whenever we have an ARG_CONST_* style argument, as the verifier cannot consider imprecise scalars to be equivalent for the purposes of states_equal check when such arguments refine the return value (in this case, set mem_size for PTR_TO_MEM). The resultant mem_size for the R0 is derived from the constant value, and if the verifier incorrectly prunes states considering them equivalent where such arguments exist (by seeing that both registers have reg->precise as false in regsafe), we can end up with invalid programs passing the verifier which can do access beyond what should have been the correct mem_size in that explored state. To show a concrete example of the problem: 0000000000000000 : 0: r2 = *(u32 *)(r1 + 80) 1: r1 = *(u32 *)(r1 + 76) 2: r3 = r1 3: r3 += 4 4: if r3 > r2 goto +18 5: w2 = 0 6: *(u32 *)(r1 + 0) = r2 7: r1 = *(u32 *)(r1 + 0) 8: r2 = 1 9: if w1 == 0 goto +1 10: r2 = -1 0000000000000058 : 11: r1 = 0 ll 13: r3 = 0 14: call bpf_ringbuf_reserve 15: if r0 == 0 goto +7 16: r1 = r0 17: r1 += 16777215 18: w2 = 0 19: *(u8 *)(r1 + 0) = r2 20: r1 = r0 21: r2 = 0 22: call bpf_ringbuf_submit 00000000000000b8 : 23: w0 = 0 24: exit For the first case, the single line execution's exploration will prune the search at insn 14 for the branch insn 9's second leg as it will be verified first using r2 = -1 (UINT_MAX), while as w1 at insn 9 will always be 0 so at runtime we don't get error for being greater than UINT_MAX/4 from bpf_ringbuf_reserve. The verifier during regsafe just sees reg->precise as false for both r2 registers in both states, hence considers them equal for purposes of states_equal. If we propagated precise markers using the backtracking support, we would use the precise marking to then ensure that old r2 (UINT_MAX) was within the new r2 (1) and this would never be true, so the verification would rightfully fail. The end result is that the out of bounds access at instruction 19 would be permitted without this fix. Note that reg->precise is always set to true when user does not have CAP_BPF (or when subprog count is greater than 1 (i.e. use of any static or global functions)), hence this is only a problem when precision marks need to be explicitly propagated (i.e. privileged users with CAP_BPF). A simplified test case has been included in the next patch to prevent future regressions. Fixes: 457f44363a88 ("bpf: Implement BPF ring buffer and verifier support for it") Signed-off-by: Kumar Kartikeya Dwivedi --- kernel/bpf/verifier.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 096fdac70165..30c6eebce146 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6066,6 +6066,9 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg, return -EACCES; } meta->mem_size = reg->var_off.value; + err = mark_chain_precision(env, regno); + if (err) + return err; break; case ARG_PTR_TO_INT: case ARG_PTR_TO_LONG: From patchwork Tue Aug 23 18:55:00 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kumar Kartikeya Dwivedi X-Patchwork-Id: 12952553 X-Patchwork-Delegate: bpf@iogearbox.net Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5FC3DC32772 for ; Tue, 23 Aug 2022 19:51:40 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232776AbiHWTvh (ORCPT ); Tue, 23 Aug 2022 15:51:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53168 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229574AbiHWTvH (ORCPT ); Tue, 23 Aug 2022 15:51:07 -0400 Received: from mail-ej1-x642.google.com (mail-ej1-x642.google.com [IPv6:2a00:1450:4864:20::642]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 262644F650 for ; Tue, 23 Aug 2022 11:55:07 -0700 (PDT) Received: by mail-ej1-x642.google.com with SMTP id w19so29267186ejc.7 for ; Tue, 23 Aug 2022 11:55:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=YW1sLT45zOLuNc7+I1Go1iXbU4Fm2wky+Wgtd/aYq5c=; b=ewRAWJ1G+v91jSkODr5zOtnscMNiBt5ZcmPLd45c3yT0S516T7efN/PSKD0ooeCctz K/DqHlqkVzJcvHoAQcRz/xMeUo91MgRjXN55ZuFDmlMfZprYCnVLUoIa5EmhBP9OjqM1 OkUB5oTwYzP7wcVQKapOEqgi4ZGuR38sWaAJpGIK3yT3Qk5wcwln7ZGB9xgFojKAyYIY kAKvJ8/vqM2gJcf5YmSr3VAkPlixDoUessaZx0XWxl8CD2zlWBOC305w87nl+9h8boeD baUVsTHuIXVEGVFMj/4sXrWbXg0SAzjcYgHjgLEN6AaHceePzfK1I7yzoL1IjtUtZDU9 eY/A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=YW1sLT45zOLuNc7+I1Go1iXbU4Fm2wky+Wgtd/aYq5c=; b=TRupsNciJcpMM2doyULAwyhB5FRyk5ocHgwe6ZA0Y57pINmb9dU1SYKollZAmqHqgl icGb4S3NnZ+FKl8zD3SugzuGiZa4hqINxo+fk1ceChI82N9CyPfCMBYeZUXh98rMXMCv 3oWKHHVRbJoPQPLtd8HBA9owVdM2R7Ok4BSabY1NStXK0YY+DYdRrnWeVElk2D8o6ZoR A4Xtz68MgnSTKPMKvGIfW+4UwE4Hw+5XUVkRDdluOaG9gLNvDciqzkTtgHQsycApMjAZ 167Iww+ygbz5w3KhEzEFariQdyWLV2LiMSKugzJJ1U6rarKwNVFp+yq8G95s1/TWrV09 563A== X-Gm-Message-State: ACgBeo0j0AiFBZGJkWQmoBBrKwmqPESbfzRG7QXSoA90JRNDUR4yQbi3 U8Zh5tQvuT95yGVpFvjn+GVFFbosFwo= X-Google-Smtp-Source: AA6agR7uO1sQUVeisgYlVX1eqjhNRyXemCDiqu7iGvgjeM+nSiuWQ6zZOqHl6acvuxH1ZBCNZeuPHA== X-Received: by 2002:a17:907:2c57:b0:73d:aa21:8027 with SMTP id hf23-20020a1709072c5700b0073daa218027mr649715ejc.42.1661280905312; Tue, 23 Aug 2022 11:55:05 -0700 (PDT) Received: from localhost (212.191.202.62.dynamic.cgnat.res.cust.swisscom.ch. [62.202.191.212]) by smtp.gmail.com with ESMTPSA id n13-20020aa7c44d000000b00446639c01easm1814271edr.44.2022.08.23.11.55.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 23 Aug 2022 11:55:05 -0700 (PDT) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann Subject: [PATCH bpf v1 2/2] selftests/bpf: Add regression test for pruning fix Date: Tue, 23 Aug 2022 20:55:00 +0200 Message-Id: <20220823185500.467-1-memxor@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220823185300.406-1-memxor@gmail.com> References: <20220823185300.406-1-memxor@gmail.com> MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=1705; i=memxor@gmail.com; h=from:subject; bh=kGl6AEuTvv/gD7y+LLM2RPoiGQhu9X82DSrHCzmE5kc=; b=owEBbQKS/ZANAwAKAUzgyIZIvxHKAcsmYgBjBSIEpcTs7KUtih6Yxfb4whexlvXZI6pm0DUiZM3h LDYivh6JAjMEAAEKAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCYwUiBAAKCRBM4MiGSL8RypndD/ wNPK2h6hlY1jFgevVh9umU8LaiAE9jywPVBU5KgZxlboqyOpXfkbV2otjv8ofUd3p06JSRWWku4QiH x8Qyb4qtKY7BPLRO4Pgvh3Uy5r6UqVcBHqOIsU9Rd7GNtyYfX9IJdmuFmKAKiMYYqKCYqHHYdfMTo/ fRjh/hWEEkaWb6EiX3EaB75cEClqrfyNB4KRkiZCP02aR3Kut4Zm1ag5b/fYcj1RDKMZQtazGkDkEW LAp86961hdPM+DIu/xK+aWgJtzDLr1ODKLEFAtpjtScP8FS2t5sEsOxLGv1tApmqNSEHpWtMqSM9Dp sC9/gISqclWv4hKD6FlUyIR1bGo7HZmHoCeURsvrNpRvEz575SmYGtq1ncNnbTck+tKwu12faTj0TW eAFcTsdgXOsXG4zSR8WMlx/dZJoukAuH4hGrlBB0Ab67CGDSpa68VVXfJ5hwxzjzISAfXSl4cAliZa UpCNmhKFbkledhCsh0jvX8ggP03LO39Elq755oLBugAoBZzvPPLsxvLyLzrhT2Hx5CxvkK4KnD4Ww6 rQbKiPLf0VSDnbrYKXX+Cc/cABcGvYEdviP79duMQEPo3j4GXLsdA2wJSKgWY1Fni1QD0Mod+6c5vI SrBS5LGJgXf0UFZX6/r9rhVvwUiE3I34fCWJBIOBe6+gJNpXaEV1EB3L+Uuw== X-Developer-Key: i=memxor@gmail.com; a=openpgp; fpr=4BBE2A7E06ECF9D5823C61114CE0C88648BF11CA Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org X-Patchwork-Delegate: bpf@iogearbox.net Add a test to ensure we do mark_chain_precision for the argument type ARG_CONST_ALLOC_SIZE_OR_ZERO. For other argument types, this was already done, but propagation for missing for this case. Without the fix, this test case loads successfully. Signed-off-by: Kumar Kartikeya Dwivedi --- .../testing/selftests/bpf/verifier/precise.c | 25 +++++++++++++++++++ 1 file changed, 25 insertions(+) diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c index 9e754423fa8b..6c03a7d805f9 100644 --- a/tools/testing/selftests/bpf/verifier/precise.c +++ b/tools/testing/selftests/bpf/verifier/precise.c @@ -192,3 +192,28 @@ .result = VERBOSE_ACCEPT, .retval = -1, }, +{ + "precise: mark_chain_precision for ARG_CONST_ALLOC_SIZE_OR_ZERO", + .insns = { + BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_1, offsetof(struct xdp_md, ingress_ifindex)), + BPF_LD_MAP_FD(BPF_REG_6, 0), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_6), + BPF_MOV64_IMM(BPF_REG_2, 1), + BPF_MOV64_IMM(BPF_REG_3, 0), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_4, 0, 1), + BPF_MOV64_IMM(BPF_REG_2, 0x1000), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_ringbuf_reserve), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_0), + BPF_LDX_MEM(BPF_DW, BPF_REG_2, BPF_REG_0, 42), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_ringbuf_submit), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .fixup_map_ringbuf = { 1 }, + .prog_type = BPF_PROG_TYPE_XDP, + .flags = BPF_F_TEST_STATE_FREQ, + .errstr = "invalid access to memory, mem_size=1 off=42 size=8", + .result = REJECT, +},