From patchwork Fri Nov 11 20:27:18 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: 13040777 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 BDD06C433FE for ; Fri, 11 Nov 2022 20:28:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233844AbiKKU17 (ORCPT ); Fri, 11 Nov 2022 15:27:59 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58062 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234485AbiKKU16 (ORCPT ); Fri, 11 Nov 2022 15:27:58 -0500 Received: from mail-pg1-x541.google.com (mail-pg1-x541.google.com [IPv6:2607:f8b0:4864:20::541]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A29B276F81 for ; Fri, 11 Nov 2022 12:27:57 -0800 (PST) Received: by mail-pg1-x541.google.com with SMTP id 6so5227982pgm.6 for ; Fri, 11 Nov 2022 12:27:57 -0800 (PST) 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:subject:date :message-id:reply-to; bh=RS03vjLIroSZIkyHrOf+K4IrRoWOidwQJyrYr1fTaXA=; b=Lk4wyqyhZ+PUSU/P8lJx9Du8ciJ1yTtRJINotBoUcfy6LvOfxmkpYFWQbXXI455vWm H9UEJMs7I0KdTPvFLwEedbJ7olt9e0aLastxt2rk7j+APpYKybiAAkZLu9spmo10H1HD KuzgwZa6k0Z1Pgapj9KeCXoljghAsA1vjzMu0Gv7gUw9KEWB2cdaqFy0rwkiu3d7ukPe VEFzh8rAflWJgL0N/ZWNqDFR6ixBD+ralP0vsqiK/b/RbmgMHiWhi5eaukCEAIbYySGL neg5is70whqsbIGIZ7pZNLXGTNWVrTK5GM9LoNO+hOeb7l+rZqZEis9vcfjDKplBzc7f 7YGQ== 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 :subject:date:message-id:reply-to; bh=RS03vjLIroSZIkyHrOf+K4IrRoWOidwQJyrYr1fTaXA=; b=GDsl+ltxNGPtiIO0+JUOO7JrMKoouVkZut0378gzqIMVGRkwjRllbyTWt64OPoiTQ3 oi29L+PAPdkhZpPHwHUymmFpbnuDfAt2il4Z7k2EKrscNXDzj3zvROTX6mQyxPNBVEFJ +sIsv4EL/qado0JokDWLXlgLPxTfWbblIlha5SYZk0UPEW+Y9IL4g33fvxqZy9GCEXxh B4hQH26Qtd5COS3VWBXi0uMMNraay5icAaWeAoB4AjDUbP8N9WirPUYcdm/9EOjuoINF kXSbEfyedzhvXKQ2qxO2ZauEFwtyik+k6+JA5ZWvtGx4pOBASM0HClR9H6BLTN9eJ6hV gwCw== X-Gm-Message-State: ANoB5pn66hMdKbxj4LvuazZqm5+n0zs5KPwSrySWh+DhxMDRNc9h/gNw toFMMAKCSCXDNUqH5ypZqvD0uDPt++7mgw== X-Google-Smtp-Source: AA0mqf6jO1yRESlUetjZOygM3EAH8288rNBTFC66kNrhvZbb5jmPG/Um39qJWSFamCeaELgfi/Xr0Q== X-Received: by 2002:aa7:9218:0:b0:562:ce80:1417 with SMTP id 24-20020aa79218000000b00562ce801417mr4322281pfo.19.1668198476881; Fri, 11 Nov 2022 12:27:56 -0800 (PST) Received: from localhost ([14.96.13.220]) by smtp.gmail.com with ESMTPSA id w190-20020a6230c7000000b0056bb99db338sm2033612pfw.175.2022.11.11.12.27.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 11 Nov 2022 12:27:56 -0800 (PST) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann , Martin KaFai Lau , Edward Cree Subject: [PATCH bpf v1 1/2] bpf: Fix state pruning check for PTR_TO_MAP_VALUE Date: Sat, 12 Nov 2022 01:57:18 +0530 Message-Id: <20221111202719.982118-2-memxor@gmail.com> X-Mailer: git-send-email 2.38.1 In-Reply-To: <20221111202719.982118-1-memxor@gmail.com> References: <20221111202719.982118-1-memxor@gmail.com> MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=4703; i=memxor@gmail.com; h=from:subject; bh=+iKmCDqrZh4fPpK1FufVgf0AgNJZSsM2gmax3k0dc6Y=; b=owEBbQKS/ZANAwAIAUzgyIZIvxHKAcsmYgBjbq/82o/QbdiMPu5GtzmexV0YG50aEDgyE+zZxV+h ODAgqXiJAjMEAAEIAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCY26v/AAKCRBM4MiGSL8RyvDqEA CrYaxm0jUjVB52LPu9RQeZnmWogZIlFD7Ixm1aOTDFkkb0PpWRjemSCWvr8aHyvOH5PM3gEHZV+llr NUaFRV+Mf9vLspPwG7eJjPb5dmyvioscA4FcUNbFSvXuvqgWjvVfGBZrRpUugX0HGg+/DqZQQSL2ff ikPe+Up6T7FxSfxqeqoOIKxzdyjNhmhHiFRktEaQ4dFvb0gIhFnZDhjQzjiO/gzuorHKOIHsLHOfGO tM/IHWrpH0aIOXSZrvruv2q5GeEkG0yZclW73FPN606zvmAXoHjLlsTvdAj39IMiHxziLgVey2LgmI 9LhM/iubHiAlF4X9RhTifDDiMLgk9bb7Quda24akV2Ow+kt82Bt8cSdgbEOxhQkFmvT3rzB4I2mVIK wewpGDhfAjU9cQv3cTYKRUQ37y6M9JNiGDzBOU/Qh5rWVSSgoZCHVXmd+qgOmIqu1Q852CzZ515Ijt N+JQVfXI4IvDiXlwzENm7K7oHfobYZ9NFMRg5FDMP2ttSc7nNYtxPbCAWsn6Ue50YIFMr8NLLt9ESr 6HjTm+g8TmAlt2Os0zzE4ObcAYvQ3o0dQC5Us9c89ZpM+M9w9OMErRrkVb9QSGkz7cL8vohnjUppLX budZw6C8qU7dJptqF31SDB2r5XpflfQQVNb34uNjJ74q3zJ6i4X7yEcZGuHw== 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 Currently, the verifier preserves reg->id for PTR_TO_MAP_VALUE when it points to a map value that contains a bpf_spin_lock element (see the logic in reg_may_point_to_spin_lock and how it is used to skip setting reg->id to 0 in mark_ptr_or_null_reg). This gives a unique lock ID for each critical section begun by a bpf_spin_lock helper call. The same reg->id is matched with env->active_spin_lock during unlock to determine whether bpf_spin_unlock is called for the same bpf_spin_lock object. However, regsafe takes a different approach to safety checks currently. The comparison of reg->id was explicitly skipped in the commit being fixed with the reasoning that the reg->id value should have no bearing on the safety of the program if the old state was verified to be safe. This however is demonstrably not true (with a selftest having the verbose working test case in a later commit), with the following pseudo code: r0 = bpf_map_lookup_elem(&map, ...); // id=1 r6 = r0; r0 = bpf_map_lookup_elem(&map, ...); // id=2 r7 = r0; bpf_spin_lock(r1=r6); if (cond) // unknown scalar, hence verifier cannot predict branch r6 = r7; p: bpf_spin_unlock(r1=r7); In the first exploration path, we would want the verifier to skip over the r6 = r7 assignment so that it reaches BPF_EXIT and the state branches counter drops to 0 and it becomes a safe verified state. The branch target 'p' acts a pruning point, hence states will be compared. If the old state was verified without assignment, it has r6 with id=1, but the new state will have r6 with id=2. The other parts of register, stack, and reference state and any other verifier state compared in states_equal remain unaffected by the assignment. Now, when the memcmp fails for r6, the verifier drops to the switch case and simply memcmp until the id member, and requires the var_off to be more permissive in the current state. Once establishing this fact, it returns true and search is pruned. Essentially, we end up calling unlock for a bpf_spin_lock that was never locked whenever the condition is true at runtime. To fix this, also include id in the memcmp comparison. Since ref_obj_id is never set for PTR_TO_MAP_VALUE, change the offsetof to be until that member. Note that by default the reg->id in case of PTR_TO_MAP_VALUE should be 0 (without PTR_MAYBE_NULL), so it should only really impact cases where a bpf_spin_lock is present in the map element. Fixes: d83525ca62cf ("bpf: introduce bpf_spin_lock") Signed-off-by: Kumar Kartikeya Dwivedi Acked-by: Stanislav Fomichev --- kernel/bpf/verifier.c | 33 +++++++++++++++++++++++++++------ 1 file changed, 27 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 264b3dc714cc..7e6bac344d37 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -11559,13 +11559,34 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold, /* If the new min/max/var_off satisfy the old ones and * everything else matches, we are OK. - * 'id' is not compared, since it's only used for maps with - * bpf_spin_lock inside map element and in such cases if - * the rest of the prog is valid for one map element then - * it's valid for all map elements regardless of the key - * used in bpf_map_lookup() + * + * 'id' must also be compared, since it's used for maps with + * bpf_spin_lock inside map element and in such cases if the + * rest of the prog is valid for one map element with a specific + * id, then the id in the current state must match that of the + * old state so that any operations on this reg in the rest of + * the program work correctly. + * + * One example is a program doing the following: + * r0 = bpf_map_lookup_elem(&map, ...); // id=1 + * r6 = r0; + * r0 = bpf_map_lookup_elem(&map, ...); // id=2 + * r7 = r0; + * + * bpf_spin_lock(r1=r6); + * if (cond) + * r6 = r7; + * p: + * bpf_spin_unlock(r1=r6); + * + * The label 'p' is a pruning point, hence states for that + * insn_idx will be compared. If we don't compare the id, the + * program will pass as the r6 and r7 are otherwise identical + * during the second pass that compares the already verified + * state with the one coming from the path having the additional + * r6 = r7 assignment. */ - return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && + return memcmp(rold, rcur, offsetof(struct bpf_reg_state, ref_obj_id)) == 0 && range_within(rold, rcur) && tnum_in(rold->var_off, rcur->var_off); case PTR_TO_PACKET_META: From patchwork Fri Nov 11 20:27:19 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: 13040778 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 A7E26C4332F for ; Fri, 11 Nov 2022 20:28:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234485AbiKKU2F (ORCPT ); Fri, 11 Nov 2022 15:28:05 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:58136 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234500AbiKKU2D (ORCPT ); Fri, 11 Nov 2022 15:28:03 -0500 Received: from mail-pl1-x642.google.com (mail-pl1-x642.google.com [IPv6:2607:f8b0:4864:20::642]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9E217845D3 for ; Fri, 11 Nov 2022 12:28:00 -0800 (PST) Received: by mail-pl1-x642.google.com with SMTP id g24so5086448plq.3 for ; Fri, 11 Nov 2022 12:28:00 -0800 (PST) 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:subject:date :message-id:reply-to; bh=sLzoA6C1VcOgFXhrd/ol3IikbXD4CC3ueplXHs8iYOY=; b=c+/8MK3wQWTOan1ehxGSmSq01U8HmorcdxM5upYlHePxH5px0hczFfUcEUKrR4D1CP ZyMOTIVz5/7eozMdcMTB+68ChzWONqIm28fOdrnzQIhZfCxHKH6U8yh7eiSZUQqngG5G t74xZAz5w4P4J+4Rni0Kzj2GUoujqM8oER7AKkW5ItM2D05pGZCVWcmpxVts5fWKlm8T Kp3oO1jeCRCow+B7oC7U6gBHZHBLKm+9X/yF2FTLn9jhTnAZqknpdSumgwFIYvYDONrC d64vz7/9/Z4+abS+HfnKnG6mUvLBSq9nlWKAO+fVsNfWcg1amn3GvJ+biXJlCb58KN/Q 9Bpg== 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 :subject:date:message-id:reply-to; bh=sLzoA6C1VcOgFXhrd/ol3IikbXD4CC3ueplXHs8iYOY=; b=mhDoBH51a7TcZ3+q6Zh4gqh0sv+W8564jPyO531tBpFLkof8qYTMSHukA+rNXgHJsI +SbqXh+L+RDjKB8eA1huZn1lg8EnHgMlml3vCo9fEnbPfVM/Nhi4Fa9qO3AzvUX9Ndd4 TbPdCbR5VslMgleNteMeucJFUlp+zd+QPNBj4VKncOqnxH1m69z+cUz8JkJH68PUBnTU xiY7qTi5BiPfGv6q6bD6V7Rw53FO0ZRcVK0zr/0n8VGrAw/6qLj7YlQtr4G4cHNO95Bc n+H/Xp/FD11TM4dLVCzvUr71baL5tQStilzWxc1b8qfc+nZ8llnLRmLFsOLIRQgMfP+a LMpQ== X-Gm-Message-State: ANoB5plDeApmWJzuYU9RjqoWRUga5iP/moLcgOqfL0E8OeF4rw/Wzhpn QRx7RVsCKVsQxBenPyVRwRTrzJ4IqQgn4A== X-Google-Smtp-Source: AA0mqf5ynfNWPE/XD+R8LSQViISG6KQKP+dc4BMrQi6Zg+1kD5LyGkyBdGkFA99G5icwyNqevkdUTw== X-Received: by 2002:a17:902:e154:b0:187:190f:6aa7 with SMTP id d20-20020a170902e15400b00187190f6aa7mr3898207pla.131.1668198479750; Fri, 11 Nov 2022 12:27:59 -0800 (PST) Received: from localhost ([14.96.13.220]) by smtp.gmail.com with ESMTPSA id 8-20020a630e48000000b0046fabcb5150sm1680410pgo.93.2022.11.11.12.27.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 11 Nov 2022 12:27:59 -0800 (PST) From: Kumar Kartikeya Dwivedi To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Andrii Nakryiko , Daniel Borkmann , Martin KaFai Lau , Edward Cree Subject: [PATCH bpf v1 2/2] selftests/bpf: Add pruning test case for bpf_spin_lock Date: Sat, 12 Nov 2022 01:57:19 +0530 Message-Id: <20221111202719.982118-3-memxor@gmail.com> X-Mailer: git-send-email 2.38.1 In-Reply-To: <20221111202719.982118-1-memxor@gmail.com> References: <20221111202719.982118-1-memxor@gmail.com> MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=2319; i=memxor@gmail.com; h=from:subject; bh=4Lj0SCiBlMxIlznwRSj1DNFWI2gsST6+I5SQtbjxYuQ=; b=owEBbQKS/ZANAwAIAUzgyIZIvxHKAcsmYgBjbq/9Hgt//Y33Uyjux3qOe3w3tfjisu6a9w1AccFg ee8KvpOJAjMEAAEIAB0WIQRLvip+Buz51YI8YRFM4MiGSL8RygUCY26v/QAKCRBM4MiGSL8RynkcD/ 4pf3XXjOV4dh7rBm7Z90/c51WZzKud0lL7e/C3rKgwMX9E+dMYXQOVHzX1V+K1mKUwITTwnxL70/uK joz0P8e27glKoOa2h1rc+9Kr0v9DXgZEE3kc17v1kf5u09HeMZVdQwNnZF185IC0OsVAg7B2BeiCl9 LszMvaCKnU7UVnA/UGMygeA6zN+ptoAPaYXUwsjxm8KbeBoOzOMf+Xm54pWN23//NBnIedQZXvj40n p/GQwdpEtBMpIoiadrn3pT7k38TH0BYqolJluz5Og8FHPdhzu7VnHSEhR9sXPXWoD/gKJdmH34285M MEiGZF3HPJXLGG3HOYT+wcsy3TK/HzmIG2BrDrbjn+cE/8WQGYywXaioM/B7nE7oFP9w7WhUIdZjtn 0pGDt9UK6hY9d0SN8Hq/z1SLIlu/erF4lZD5S48iGvPiiqflY/HwpcrjBjRxiuJ4G9rQO4XyVcwI7b xFb4ZPZnD5Z2h0Z7z4xwWVeAng1oN0KK89DtBHTAMc+/yzLP3cis/eY3KQQsywNOS8MuqNUjlSEbOo tPfX8S62IbFRzMrzk1DMaQOiiIjQMQc8ykaoy67px/+8scQ0sfFj9IZP5zXzo/zSMvefHZY6tgm6h+ X77jbXaum1MSdGzJPqVD4LN0ZO0DUV4OJfYVaQniwr+EY4tFgATvmbkfFUtg== 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 Test that when reg->id is not same for the same register of type PTR_TO_MAP_VALUE between current and old explored state, we currently return false from regsafe and continue exploring. Without the fix in prior commit, the test case fails. Signed-off-by: Kumar Kartikeya Dwivedi Acked-by: Stanislav Fomichev --- .../selftests/bpf/verifier/spin_lock.c | 39 +++++++++++++++++++ 1 file changed, 39 insertions(+) diff --git a/tools/testing/selftests/bpf/verifier/spin_lock.c b/tools/testing/selftests/bpf/verifier/spin_lock.c index 781621facae4..0a8dcfc37fc6 100644 --- a/tools/testing/selftests/bpf/verifier/spin_lock.c +++ b/tools/testing/selftests/bpf/verifier/spin_lock.c @@ -331,3 +331,42 @@ .errstr = "inside bpf_spin_lock", .prog_type = BPF_PROG_TYPE_SCHED_CLS, }, +{ + "spin_lock: regsafe compare reg->id for map value", + .insns = { + BPF_MOV64_REG(BPF_REG_6, BPF_REG_1), + BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_6, offsetof(struct __sk_buff, mark)), + BPF_LD_MAP_FD(BPF_REG_1, 0), + BPF_MOV64_REG(BPF_REG_9, BPF_REG_1), + BPF_ST_MEM(BPF_W, BPF_REG_10, -4, 0), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_7, BPF_REG_0), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_9), + BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), + BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), + BPF_EXIT_INSN(), + BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_7), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_spin_lock), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_6, 0, 1), + BPF_JMP_IMM(BPF_JA, 0, 0, 1), + BPF_MOV64_REG(BPF_REG_7, BPF_REG_8), + BPF_MOV64_REG(BPF_REG_1, BPF_REG_7), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 4), + BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_spin_unlock), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 2 }, + .result = REJECT, + .errstr = "bpf_spin_unlock of different lock", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .flags = BPF_F_TEST_STATE_FREQ, +},