From patchwork Wed Apr 21 12:23:48 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Brendan Jackman X-Patchwork-Id: 12216069 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=-21.3 required=3.0 tests=BAYES_00,DKIMWL_WL_MED, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS, INCLUDES_PATCH,MAILING_LIST_MULTI,SPF_HELO_NONE,SPF_PASS,URIBL_BLOCKED, USER_AGENT_GIT,USER_IN_DEF_DKIM_WL 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 261CDC433ED for ; Wed, 21 Apr 2021 12:25:01 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id E7DE86144D for ; Wed, 21 Apr 2021 12:25:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234637AbhDUMZc (ORCPT ); Wed, 21 Apr 2021 08:25:32 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:57850 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234625AbhDUMZa (ORCPT ); Wed, 21 Apr 2021 08:25:30 -0400 Received: from mail-qv1-xf4a.google.com (mail-qv1-xf4a.google.com [IPv6:2607:f8b0:4864:20::f4a]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4FA01C06138A for ; Wed, 21 Apr 2021 05:24:56 -0700 (PDT) Received: by mail-qv1-xf4a.google.com with SMTP id x15-20020a0ce0cf0000b029019cb3e75c62so13538557qvk.15 for ; Wed, 21 Apr 2021 05:24:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:message-id:mime-version:subject:from:to:cc :content-transfer-encoding; bh=OD2jJ9yLCKnYZIcD98cpt1RR7ymAHhRQ2H9+zlmmjug=; b=Avtml08dV8RD/7rMgmE8OvfgkjFdUDKpPY/pGUuZzrs4SHKHLGtOaYo/MEW4pVtG3A Yvm2aK343VzqaJksCf19+sHWvrbtM7zz5B8N7J+QhUqieWsel9Po8IVRfk+LoCHw4qAl WkMdgnNXw/jJ4paY1dzzBdUpFK+wTHotoj9Iuo/IzjnXWVMUtAS9ptqW1R+qjK8F/Lhh N8BU5qKoBvxc2vW0I9UTSoIxLlt/HEqTVDdlontCV+qTfNQnkmdQ2KPjqtjjwNsNgUxT 7QZW3LiixvtvtEbeBnceOU8FJx6orLMTyS+eWDh6IfNjspUAOAewHp50hN95RkaR0kT2 ELmg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:message-id:mime-version:subject:from:to:cc :content-transfer-encoding; bh=OD2jJ9yLCKnYZIcD98cpt1RR7ymAHhRQ2H9+zlmmjug=; b=qc1Gjb6YxutMvyLEkmxqF6iZQQ+wtcshkVtD0HNW4nAHgBc/OEvNvWg7F6Aqzs58i5 gmmJDdEgqcG/kcBeAh6CVTxY6Ry48UUHW28tbQPLUhlabY9QIYNyiAaUJxn0ZlM4+tR8 vgT8/nlhRm2BFkPAnN4j/fduV7Z/BS0b1M4NaMMsgu0IEDwgBICcc+KYv3dqwpUz99Gu +skdFjmlMykhdUCzuJWe1GgGZw7aQ5aBYJ6wLjS/f/2KEkwGxdFO/CUULD0gKm58I9Iy BS7YrS5vA+orRFSsG8RN8/NIGP30AXg7/1z322S0m/mQwtIG4+gp/RwGhnDDaa9pEHzp 0WRQ== X-Gm-Message-State: AOAM530gzISW3XfEwVAr+gfrR95W1efNckUu9Cu+bEQQUJFeo6CW6vXl OBIjHz3CSK/NwnGfmD5U7/7Oi0XWjXB69xLbOEVtkK1LCqBSuN9FLzwB+NZ9QeTZFWL+2AbUBDK f+Hw8BIjlaiA7+islNhYspTDfVc6/LqhxgSG4I+6+fM3dAwaLpM+M1AQ5Ja6/EHg= X-Google-Smtp-Source: ABdhPJwdPqK7TVpIQ7Pri5OSevKRBEwXc8ZU2QtGuP5x3Hg+8x8ccehM6kZA+SSmO+esKvGhPL5q7ilIY2JSKw== X-Received: from beeg.c.googlers.com ([fda3:e722:ac3:10:28:9cb1:c0a8:11db]) (user=jackmanb job=sendgmr) by 2002:a0c:f802:: with SMTP id r2mr32315555qvn.50.1619007895392; Wed, 21 Apr 2021 05:24:55 -0700 (PDT) Date: Wed, 21 Apr 2021 12:23:48 +0000 Message-Id: <20210421122348.547922-1-jackmanb@google.com> Mime-Version: 1.0 X-Mailer: git-send-email 2.31.1.368.gbe11c130af-goog Subject: Help with verifier failure From: Brendan Jackman To: bpf@vger.kernel.org Cc: ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org, linux-kernel@vger.kernel.org, Brendan Jackman Precedence: bulk List-ID: X-Mailing-List: bpf@vger.kernel.org Hi, Recently when our internal Clang build was updated to 0e92cbd6a652 we started hitting a verifier issue that I can't see an easy fix for. I've narrowed it down to a minimal reproducer - this email is a patch to add that repro as a prog test (./test_progs -t example). Here's the BPF code I get from the attached source: 0000000000000000 : ; int BPF_PROG(exec, struct linux_binprm *bprm) { 0: 79 11 00 00 00 00 00 00 r1 = *(u64 *)(r1 + 0) 1: 7b 1a e8 ff 00 00 00 00 *(u64 *)(r10 - 24) = r1 ; uint64_t args_size = bprm->argc & 0xFFFFFFF; 2: 61 17 58 00 00 00 00 00 r7 = *(u32 *)(r1 + 88) 3: b4 01 00 00 00 00 00 00 w1 = 0 ; int map_key = 0; 4: 63 1a fc ff 00 00 00 00 *(u32 *)(r10 - 4) = r1 5: bf a2 00 00 00 00 00 00 r2 = r10 6: 07 02 00 00 fc ff ff ff r2 += -4 ; void *buf = bpf_map_lookup_elem(&buf_map, &map_key); 7: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll 9: 85 00 00 00 01 00 00 00 call 1 10: 7b 0a f0 ff 00 00 00 00 *(u64 *)(r10 - 16) = r0 11: 57 07 00 00 ff ff ff 0f r7 &= 268435455 12: bf 76 00 00 00 00 00 00 r6 = r7 ; if (!buf) 13: 16 07 12 00 00 00 00 00 if w7 == 0 goto +18 14: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16) 15: 15 01 10 00 00 00 00 00 if r1 == 0 goto +16 16: b4 09 00 00 00 00 00 00 w9 = 0 17: b7 01 00 00 00 10 00 00 r1 = 4096 18: bf 68 00 00 00 00 00 00 r8 = r6 19: 05 00 0e 00 00 00 00 00 goto +14 00000000000000a0 : ; void *src = (void *)(char *)bprm->p + offset; 20: 79 a1 e8 ff 00 00 00 00 r1 = *(u64 *)(r10 - 24) 21: 79 13 18 00 00 00 00 00 r3 = *(u64 *)(r1 + 24) ; uint64_t read_size = args_size - offset; 22: 0f 73 00 00 00 00 00 00 r3 += r7 23: 07 03 00 00 00 f0 ff ff r3 += -4096 ; (void) bpf_probe_read_user(buf, read_size, src); 24: 79 a1 f0 ff 00 00 00 00 r1 = *(u64 *)(r10 - 16) 25: 85 00 00 00 70 00 00 00 call 112 ; for (int i = 0; i < 512 && offset < args_size; i++) { 26: 26 09 05 00 fe 01 00 00 if w9 > 510 goto +5 27: 07 08 00 00 00 f0 ff ff r8 += -4096 28: bf 71 00 00 00 00 00 00 r1 = r7 29: 07 01 00 00 00 10 00 00 r1 += 4096 30: 04 09 00 00 01 00 00 00 w9 += 1 ; for (int i = 0; i < 512 && offset < args_size; i++) { 31: ad 67 02 00 00 00 00 00 if r7 < r6 goto +2 0000000000000100 : ; int BPF_PROG(exec, struct linux_binprm *bprm) { 32: b4 00 00 00 00 00 00 00 w0 = 0 33: 95 00 00 00 00 00 00 00 exit 0000000000000110 : 34: bf 17 00 00 00 00 00 00 r7 = r1 ; (void) bpf_probe_read_user(buf, read_size, src); 35: bc 82 00 00 00 00 00 00 w2 = w8 36: a5 08 ef ff 00 10 00 00 if r8 < 4096 goto -17 37: b4 02 00 00 00 10 00 00 w2 = 4096 38: 05 00 ed ff 00 00 00 00 goto -19 The full log I get is at https://gist.githubusercontent.com/bjackman/2928c4ff4cc89545f3993bddd9d5edb2/raw/feda6d7c165d24be3ea72c3cf7045c50246abd83/gistfile1.txt, but basically the verifier runs through the loop a large number of times, going down the true path of the `if (read_size > CHUNK_LEN)` every time. Then eventually it takes the false path. In the disassembly this is basically instructions 35-37 - pseudocode: w2 = w8 if (r8 < 4096) { w2 = 4096 } w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those bounds from r8 (note the umax_value for R8 goes to 4095 after the branch from 36 to 20, but R2's umax_value is still 266342399) from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152 R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2093056 R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_ ; int BPF_PROG(exec, struct linux_binprm *bprm) { 34: (bf) r7 = r1 ; (void) bpf_probe_read_user(buf, read_size, src); 35: (bc) w2 = w8 36: (a5) if r8 < 0x1000 goto pc-17 from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152 R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_ ; void *src = (void *)(char *)bprm->p + offset; 20: (79) r1 = *(u64 *)(r10 -24) 21: (79) r3 = *(u64 *)(r1 +24) ; uint64_t read_size = args_size - offset; 22: (0f) r3 += r7 23: (07) r3 += -4096 ; (void) bpf_probe_read_user(buf, read_size, src); 24: (79) r1 = *(u64 *)(r10 -16) 25: (85) call bpf_probe_read_user#112 R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_ R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_ invalid access to map value, value_size=4096 off=0 size=266342399 R1 min value is outside of the allowed memory range processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133 peak_states 133 mark_read 2 This seems like it must be a common pitfall, any idea what we can do to fix it and avoid it in future? Am I misunderstanding the issue? Cheers, Brendan --- .../selftests/bpf/prog_tests/example.c | 17 ++++++++ tools/testing/selftests/bpf/progs/example.c | 42 +++++++++++++++++++ 2 files changed, 59 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/example.c create mode 100644 tools/testing/selftests/bpf/progs/example.c 2.31.1.368.gbe11c130af-goog diff --git a/tools/testing/selftests/bpf/prog_tests/example.c b/tools/testing/selftests/bpf/prog_tests/example.c new file mode 100644 index 000000000000..9c36858019b3 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/example.c @@ -0,0 +1,17 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include + +#include "example.skel.h" + +void test_example(void) +{ + struct example *skel; + __u32 duration = 0; + + skel = example__open_and_load(); + if (CHECK(!skel, "skel_load", "couldn't load program\n")) + return; + + example__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/example.c b/tools/testing/selftests/bpf/progs/example.c new file mode 100644 index 000000000000..6c90060e92e0 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/example.c @@ -0,1 +1,42 @@ +#include "vmlinux.h" + +#include +#include + +char _license[] SEC("license") = "GPL"; + +#define CHUNK_LEN (uint64_t)4096 +struct { + __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY); + __uint(key_size, sizeof(int)); + __uint(value_size, CHUNK_LEN); + __uint(max_entries, 1); +} buf_map SEC(".maps"); + +SEC("lsm/bprm_committed_creds") +int BPF_PROG(exec, struct linux_binprm *bprm) { + /* Actual value doesn't make sense here, just picking something unknown to the + * verifier that produces simple disassembly + */ + uint64_t args_size = bprm->argc & 0xFFFFFFF; + int map_key = 0; + void *buf = bpf_map_lookup_elem(&buf_map, &map_key); + uint64_t offset = 0; + if (!buf) + return 0; + + for (int i = 0; i < 512 && offset < args_size; i++) { + void *src = (void *)(char *)bprm->p + offset; + uint64_t read_size = args_size - offset; + + if (read_size > CHUNK_LEN) { + read_size = CHUNK_LEN; + } + + (void) bpf_probe_read_user(buf, read_size, src); + + offset += CHUNK_LEN; + } + + return 0; +} --