From patchwork Thu Aug 9 19:20:52 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Andrey Konovalov X-Patchwork-Id: 10561697 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 7B3021390 for ; Thu, 9 Aug 2018 19:21:22 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 662302B93E for ; Thu, 9 Aug 2018 19:21:22 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 632572B942; Thu, 9 Aug 2018 19:21:22 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-10.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE, USER_IN_DEF_DKIM_WL autolearn=unavailable version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3FF442B941 for ; Thu, 9 Aug 2018 19:21:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id DF5636B0006; Thu, 9 Aug 2018 15:21:18 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id DB0486B0008; Thu, 9 Aug 2018 15:21:18 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C45FE6B0007; Thu, 9 Aug 2018 15:21:18 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-wr1-f70.google.com (mail-wr1-f70.google.com [209.85.221.70]) by kanga.kvack.org (Postfix) with ESMTP id 5B5A16B0003 for ; Thu, 9 Aug 2018 15:21:18 -0400 (EDT) Received: by mail-wr1-f70.google.com with SMTP id s14-v6so5276770wra.0 for ; Thu, 09 Aug 2018 12:21:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:from:to:cc:subject:date :message-id:mime-version:content-transfer-encoding; bh=sYOtkPk+LjjrvrLFndeQZE28t2ttWE+vThtxXb9GtN4=; b=L4bgJ3yFtBb817IVcvQdw0wxnmnvJ+eB5BXLgzMeESTrFGILVteSaNayEKfl1l9JiV ABXn/hGuTMvFJCm5+WFNZR4qNpbyQcxmftQslVte4YC1wSUao4DCIWmlwRr9cKeW3QIh QcMxtheL+SU9fl7YFdpTsjtohPdgJphn6YRC4DU4uOlucaxwsPb+dznzn+HWl1Br2+MW odJxkixmK4WJiovIpGkRDEwIP+YpudmRGh4TGntbOSxLtmBhQqaS1VXLXNVW97OZoZPQ rwN5ji7xWWrXkjuNRW4Odaw7c49A5gNdJwSZ3oeSmbOqPpzYT9CMOu3cORNQW1sP3rLe plpQ== X-Gm-Message-State: AOUpUlE+MEGFKB+EXk5QPEi2u41jzQ0GcRC5pmd/sG7hHjsGWz/lzT6d cgkBbqPJ6FlVKgQ7RcSEayy8XTMYnh5I1Em30ERb9DsIn1GXoDmpktaUR5xaCDlSMwVt6p5NpcP 1PUY0gAyD+fBuumjUINLEN68CWXELYno6wInmy5Lf5toqsG4t3Bj6HwIhtvyQI5wz5Vz9Bk8a1Z +HBQYsDO3kCBHwHL8GAgD95x7PkHxsxFCupJieNN9rF/JpJNzky0b1TWVHdNegSaPVYr+/hDo75 Gl19b4i+gqsUpqWOD9wmgB50zXZIAL+AutL63Vs7nH18MeAUffazPL0EQP/1luyCzlNy74kaU8f UP+Gijjhtg8EpqH+N66E20MzUAdSSFacrD+qVAdKtcPKn3RogZWKquNGPbISxsEGq+gWTPqE6HY + X-Received: by 2002:a1c:5e48:: with SMTP id s69-v6mr2355135wmb.19.1533842477534; Thu, 09 Aug 2018 12:21:17 -0700 (PDT) X-Received: by 2002:a1c:5e48:: with SMTP id s69-v6mr2355075wmb.19.1533842475580; Thu, 09 Aug 2018 12:21:15 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1533842475; cv=none; d=google.com; s=arc-20160816; b=PEggjw5AhfrNxgC/F0F1Y5N8s23mTzJygOQDHWmaSuIe8OFfw4f8JCinT69TXkwhjI uJj6MwTPxyxn1EE3PYWgN7V3RUfl2zTp0uJiGMryyDAMBbHMN4fjjKB+QdON3ETTMIPi D+mjIqQRXs6Fvqfhx3iReyCeDfXg3R/aQBXwqMT755TWydBtzsOGVRh92+DqwtUBslwU VZo2R10UFDDP854F2GhEjPBJCUnE1f05nrnqvIbU+1efGMY1/K5ZaNlPQNgnZlrFGMm3 Eu4uIwYY4mrHlGJH47TIZu1juuVE58CdeaKXHjvZmBEkiNU18ipC2f1PmBvShPEzWkL3 ZU3w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:dkim-signature:arc-authentication-results; bh=sYOtkPk+LjjrvrLFndeQZE28t2ttWE+vThtxXb9GtN4=; b=L7f+DAAVQh31IwBeYI5BQPKoxq/BnXpF4EmWoWgPLvcwb1Wd7zojcAXNL3WmAf2MMF YhszOO1NxUkPicWcjNl1QKdQKf1hp6N8mT2w/e1KF72eZERl0wvNlKMSn+NonsUDDaEv V8KfEWil80v7PWjXmuypSbokC7NFAQn33qmL2CK6vitDMwjIYwPBfjII39WKP76FkQxX +Tx6w21HapYIdwckWAI/LXZJuMhYqOpoDJV+v69Fa4XBuSuB97nmAcmMFUBt9SvjxZ3s I7OupsMKQIr3R2+nDnyC2gnsZsxDao6PM1eShaobqnaZ7+6ZWa2c6o9UjfgggTTdVsFi N7Lw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b="JS/NJfp6"; spf=pass (google.com: domain of andreyknvl@google.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=andreyknvl@google.com; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id y1-v6sor3090095wrl.6.2018.08.09.12.21.15 for (Google Transport Security); Thu, 09 Aug 2018 12:21:15 -0700 (PDT) Received-SPF: pass (google.com: domain of andreyknvl@google.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b="JS/NJfp6"; spf=pass (google.com: domain of andreyknvl@google.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=andreyknvl@google.com; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=sYOtkPk+LjjrvrLFndeQZE28t2ttWE+vThtxXb9GtN4=; b=JS/NJfp65mpiOOZn2qNDwefF0izCLijMlUwrNK3TOaz5XUOA9ol6D5Zv9YpYvKqk7X kbl9ATdI2vsF66RpaF1PzSNQLgYkg4HwWjBBzKgG9EhkC8438H+ExPSGCf9Rt724MiQJ T4DYiCojVtc3KK8+OgUDBYVqz6pyrA8eTsF/9v2OsQH2RPwwZ2p0HiIdqGLy3cOrOFEs KJ6igU5HGedFcwjX3IqMVw0bVQDfovA3YvsTXJbYbPzKvMU4v6OklAHGHoGyCN90rzKu 5MrYArXQXf3LGZxLOLYWG2AOEb6A8iiNXYguDP+YN63r5ukfhvpKygphGZogMeBcxOcP ygIg== X-Google-Smtp-Source: AA+uWPyQGRVKuxcJmJNMJ8NjyBKtSaKncBrPCI1026HMp+G9Ck5E3vhPEIJVG/bkkjQr++r9H54Tuw== X-Received: by 2002:a5d:63c1:: with SMTP id c1-v6mr2331295wrw.106.1533842474624; Thu, 09 Aug 2018 12:21:14 -0700 (PDT) Received: from andreyknvl0.muc.corp.google.com ([2a00:79e0:15:10:84be:a42a:826d:c530]) by smtp.gmail.com with ESMTPSA id o14-v6sm14738797wmd.35.2018.08.09.12.21.12 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 09 Aug 2018 12:21:13 -0700 (PDT) From: Andrey Konovalov To: Andrey Ryabinin , Alexander Potapenko , Dmitry Vyukov , Catalin Marinas , Will Deacon , Christoph Lameter , Andrew Morton , Mark Rutland , Nick Desaulniers , Marc Zyngier , Dave Martin , Ard Biesheuvel , "Eric W . Biederman" , Ingo Molnar , Paul Lawrence , Geert Uytterhoeven , Arnd Bergmann , "Kirill A . Shutemov" , Greg Kroah-Hartman , Kate Stewart , Mike Rapoport , kasan-dev@googlegroups.com, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, linux-sparse@vger.kernel.org, linux-mm@kvack.org, linux-kbuild@vger.kernel.org Cc: Kostya Serebryany , Evgeniy Stepanov , Lee Smith , Ramana Radhakrishnan , Jacob Bramley , Ruben Ayrapetyan , Jann Horn , Mark Brand , Chintan Pandya , Vishwath Mohan , Andrey Konovalov Subject: [PATCH v5 00/18] khwasan: kernel hardware assisted address sanitizer Date: Thu, 9 Aug 2018 21:20:52 +0200 Message-Id: X-Mailer: git-send-email 2.18.0.597.ga71716f1ad-goog MIME-Version: 1.0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: X-Virus-Scanned: ClamAV using ClamSMTP This patchset adds a new mode to KASAN [1], which is called KHWASAN (Kernel HardWare assisted Address SANitizer). The plan is to implement HWASan [2] for the kernel with the incentive, that it's going to have comparable to KASAN performance, but in the same time consume much less memory, trading that off for somewhat imprecise bug detection and being supported only for arm64. The overall idea of the approach used by KHWASAN is the following: 1. By using the Top Byte Ignore arm64 CPU feature, we can store pointer tags in the top byte of each kernel pointer. 2. Using shadow memory, we can store memory tags for each chunk of kernel memory. 3. On each memory allocation, we can generate a random tag, embed it into the returned pointer and set the memory tags that correspond to this chunk of memory to the same value. 4. By using compiler instrumentation, before each memory access we can add a check that the pointer tag matches the tag of the memory that is being accessed. 5. On a tag mismatch we report an error. [1] https://www.kernel.org/doc/html/latest/dev-tools/kasan.html [2] http://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html ====== Rationale On mobile devices KASAN's memory usage is significant problem. One of the main reasons to have KWHASAN is to be able to perform a similar set of checks that KASAN does, but with lower memory requirements. Comment from Vishwath Mohan : I don't have data on-hand, but anecdotally both ASAN and KASAN have proven problematic to enable for environments that don't tolerate the increased memory pressure well. This includes, (a) Low-memory form factors - Wear, TV, Things, lower-tier phones like Go, (c) Connected components like Pixel's visual core [1]. These are both places I'd love to have a low(er) memory footprint option at my disposal. Comment from Evgenii Stepanov : Looking at a live Android device under load, slab (according to /proc/meminfo) + kernel stack take 8-10% available RAM (~350MB). KASAN's overhead of 2x - 3x on top of it is not insignificant. Not having this overhead enables near-production use - ex. running KASAN/KHWASAN kernel on a personal, daily-use device to catch bugs that do not reproduce in test configuration. These are the ones that often cost the most engineering time to track down. CPU overhead is bad, but generally tolerable. RAM is critical, in our experience. Once it gets low enough, OOM-killer makes your life miserable. [1] https://www.blog.google/products/pixel/pixel-visual-core-image-processing-and-machine-learning-pixel-2/ ====== Technical details KHWASAN is implemented in a very similar way to KASAN. This patchset essentially does the following: 1. TCR_TBI1 is set to enable Top Byte Ignore. 2. Shadow memory is used (with a different scale, 1:16, so each shadow byte corresponds to 16 bytes of kernel memory) to store memory tags. 3. All slab objects are aligned to shadow scale, which is 16 bytes. 4. All pointers returned from the slab allocator are tagged with a random tag and the corresponding shadow memory is poisoned with the same value. 5. Compiler instrumentation is used to insert tag checks. Either by calling callbacks or by inlining them (CONFIG_KASAN_OUTLINE and CONFIG_KASAN_INLINE flags are reused). 6. When a tag mismatch is detected in callback instrumentation mode KHWASAN simply prints a bug report. In case of inline instrumentation, clang inserts a brk instruction, and KHWASAN has it's own brk handler, which reports the bug. 7. The memory in between slab objects is marked with a reserved tag, and acts as a redzone. 8. When a slab object is freed it's marked with a reserved tag. Bug detection is imprecise for two reasons: 1. We won't catch some small out-of-bounds accesses, that fall into the same shadow cell, as the last byte of a slab object. 2. We only have 1 byte to store tags, which means we have a 1/256 probability of a tag match for an incorrect access (actually even slightly less due to reserved tag values). Despite that there's a particular type of bugs that KHWASAN can detect compared to KASAN: use-after-free after the object has been allocated by someone else. ====== Benchmarks The following numbers were collected on Odroid C2 board. Both KASAN and KHWASAN were used in inline instrumentation mode. Boot time [1]: * ~1.7 sec for clean kernel * ~5.0 sec for KASAN * ~5.0 sec for KHWASAN Network performance [2]: * 8.33 Gbits/sec for clean kernel * 3.17 Gbits/sec for KASAN * 2.85 Gbits/sec for KHWASAN Slab memory usage after boot [3]: * ~40 kb for clean kernel * ~105 kb (~260% overhead) for KASAN * ~47 kb (~20% overhead) for KHWASAN KASAN memory overhead consists of three main parts: 1. Increased slab memory usage due to redzones. 2. Shadow memory (the whole reserved once during boot). 3. Quaratine (grows gradually until some preset limit; the more the limit, the more the chance to detect a use-after-free). Comparing KWHASAN vs KASAN for each of these points: 1. 20% vs 260% overhead. 2. 1/16th vs 1/8th of physical memory. 3. KHWASAN doesn't require quarantine. [1] Time before the ext4 driver is initialized. [2] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`. [3] Measured as `cat /proc/meminfo | grep Slab`. ====== Some notes A few notes: 1. The patchset can be found here: https://github.com/xairy/kasan-prototype/tree/khwasan 2. Building requires a recent LLVM version (r330044 or later). 3. Stack instrumentation is not supported yet and will be added later. ====== Changes Changes in v5: - Rebased onto 1ffaddd029 (4.18-rc8). - Preassign tags for objects from caches with constructors and SLAB_TYPESAFE_BY_RCU caches. - Fix SLAB allocator support by untagging page->s_mem in kasan_poison_slab(). - Performed dynamic testing to find potential places where pointer tagging might result in bugs [1]. - Clarified and fixed memory usage benchmarks in the cover letter. - Added a rationale for having KHWASAN to the cover letter. Changes in v4: - Fixed SPDX comment style in mm/kasan/kasan.h. - Fixed mm/kasan/kasan.h changes being included in a wrong patch. - Swapped "khwasan, arm64: fix up fault handling logic" and "khwasan: add tag related helper functions" patches order. - Rebased onto 6f0d349d (4.18-rc2+). Changes in v3: - Minor documentation fixes. - Fixed CFLAGS variable name in KASAN makefile. - Added a "SPDX-License-Identifier: GPL-2.0" line to all source files under mm/kasan. - Rebased onto 81e97f013 (4.18-rc1+). Changes in v2: - Changed kmalloc_large_node_hook to return tagged pointer instead of using an output argument. - Fix checking whether -fsanitize=hwaddress is supported by the compiler. - Removed duplication of -fno-builtin for KASAN and KHWASAN. - Removed {} block for one line for_each_possible_cpu loop. - Made set_track() static inline as it is used only in common.c. - Moved optimal_redzone() to common.c. - Fixed using tagged pointer for shadow calculation in kasan_unpoison_shadow(). - Restored setting cache->align in kasan_cache_create(), which was accidentally lost. - Simplified __kasan_slab_free(), kasan_alloc_pages() and kasan_kmalloc(). - Removed tagging from kasan_kmalloc_large(). - Added page_kasan_tag_reset() to kasan_poison_slab() and removed !PageSlab() check from page_to_virt. - Reset pointer tag in _virt_addr_is_linear. - Set page tag for each page when multiple pages are allocated or freed. - Added a comment as to why we ignore cma allocated pages. Changes in v1: - Rebased onto 4.17-rc4. - Updated benchmarking stats. - Documented compiler version requirements, memory usage and slowdown. - Dropped kvm patches, as clang + arm64 + kvm is completely broken [1]. Changes in RFC v3: - Renamed CONFIG_KASAN_CLASSIC and CONFIG_KASAN_TAGS to CONFIG_KASAN_GENERIC and CONFIG_KASAN_HW respectively. - Switch to -fsanitize=kernel-hwaddress instead of -fsanitize=hwaddress. - Removed unnecessary excessive shadow initialization. - Removed khwasan_enabled flag (it’s not needed since KHWASAN is initialized before any slab caches are used). - Split out kasan_report.c and khwasan_report.c from report.c. - Moved more common KASAN and KHWASAN functions to common.c. - Added tagging to pagealloc. - Rebased onto 4.17-rc1. - Temporarily dropped patch that adds kvm support (arm64 + kvm + clang combo is broken right now [2]). Changes in RFC v2: - Removed explicit casts to u8 * for kasan_mem_to_shadow() calls. - Introduced KASAN_TCR_FLAGS for setting the TCR_TBI1 flag. - Added a comment regarding the non-atomic RMW sequence in khwasan_random_tag(). - Made all tag related functions accept const void *. - Untagged pointers in __kimg_to_phys, which is used by virt_to_phys. - Untagged pointers in show_ptr in fault handling logic. - Untagged pointers passed to KVM. - Added two reserved tag values: 0xFF and 0xFE. - Used the reserved tag 0xFF to disable validity checking (to resolve the issue with pointer tag being lost after page_address + kmap usage). - Used the reserved tag 0xFE to mark redzones and freed objects. - Added mnemonics for esr manipulation in KHWASAN brk handler. - Added a comment about the -recover flag. - Some minor cleanups and fixes. - Rebased onto 3215b9d5 (4.16-rc6+). - Tested on real hardware (Odroid C2 board). - Added better benchmarks. [1] https://lkml.org/lkml/2018/7/18/765 [2] https://lkml.org/lkml/2018/4/19/775 Andrey Konovalov (18): khwasan, mm: change kasan hooks signatures khwasan: move common kasan and khwasan code to common.c khwasan: add CONFIG_KASAN_GENERIC and CONFIG_KASAN_HW khwasan, arm64: adjust shadow size for CONFIG_KASAN_HW khwasan: initialize shadow to 0xff khwasan, arm64: untag virt address in __kimg_to_phys and _virt_addr_is_linear khwasan: add tag related helper functions khwasan: preassign tags to objects with ctors or SLAB_TYPESAFE_BY_RCU khwasan, arm64: fix up fault handling logic khwasan, arm64: enable top byte ignore for the kernel khwasan, mm: perform untagged pointers comparison in krealloc khwasan: split out kasan_report.c from report.c khwasan: add bug reporting routines khwasan: add hooks implementation khwasan, arm64: add brk handler for inline instrumentation khwasan, mm, arm64: tag non slab memory allocated via pagealloc khwasan: update kasan documentation kasan: add SPDX-License-Identifier mark to source files Documentation/dev-tools/kasan.rst | 213 ++++---- arch/arm64/Kconfig | 1 + arch/arm64/Makefile | 2 +- arch/arm64/include/asm/brk-imm.h | 2 + arch/arm64/include/asm/memory.h | 41 +- arch/arm64/include/asm/pgtable-hwdef.h | 1 + arch/arm64/kernel/traps.c | 69 ++- arch/arm64/mm/fault.c | 3 + arch/arm64/mm/kasan_init.c | 18 +- arch/arm64/mm/proc.S | 8 +- include/linux/compiler-clang.h | 5 +- include/linux/compiler-gcc.h | 4 + include/linux/compiler.h | 3 +- include/linux/kasan.h | 90 +++- include/linux/mm.h | 29 ++ include/linux/page-flags-layout.h | 10 + lib/Kconfig.kasan | 77 ++- mm/cma.c | 11 + mm/kasan/Makefile | 9 +- mm/kasan/common.c | 663 +++++++++++++++++++++++++ mm/kasan/kasan.c | 565 +-------------------- mm/kasan/kasan.h | 85 +++- mm/kasan/kasan_init.c | 1 + mm/kasan/kasan_report.c | 156 ++++++ mm/kasan/khwasan.c | 181 +++++++ mm/kasan/khwasan_report.c | 61 +++ mm/kasan/quarantine.c | 1 + mm/kasan/report.c | 272 +++------- mm/page_alloc.c | 1 + mm/slab.c | 18 +- mm/slab.h | 2 +- mm/slab_common.c | 6 +- mm/slub.c | 21 +- scripts/Makefile.kasan | 27 +- 34 files changed, 1736 insertions(+), 920 deletions(-) create mode 100644 mm/kasan/common.c create mode 100644 mm/kasan/kasan_report.c create mode 100644 mm/kasan/khwasan.c create mode 100644 mm/kasan/khwasan_report.c