From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: ARC-Seal: i=1; a=rsa-sha256; t=1521828358; cv=none; d=google.com; s=arc-20160816; b=Hg3x4e7n64Wps/aHkYKpSsOI9jAFfUH8gPu0PcN4xUIXjjO/YxOw3bGHazDvDtlqOA oYr+z2xxlweqbOPr8XclWoSoScwrmASWi0wPz8F5A22jNd2Af1fkuEG9w/tq5VxIVWww 23O8TdDICbxC39Dsn+fgn3GLaU5e6hqhTSnDb76m+UJB69vjf3vEGTR8s4/t74Vt/xX0 UTq/xiXCzXj+QGrSC0C8X9p1AIFB/kRdz7roj6RzJDOrj7LDPyfcAsarFMDLKAtb1vzw Qn4/5OmHta+sBTkXHZZ1M65ImiPedybyRlp3UQxLQqltU0ojHbhkcBr1NtcHyR41vZeY Y1mg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=message-id:date:subject:cc:to:from:dkim-signature :arc-authentication-results; bh=Ivf/kZ8LF7BtqVwH9Wy7ZjrkZ+dpP1vTYEg21SV2eek=; b=l60jfE8Jzt2hVQqoeyeqF6Tp0kkmwu+BlaAoLTiC6eG5o1wFgzPPyiyWUTUYIHv9cH EB+oV96KlYEPAvVRN8bT0fZjrPqfoeY9bQ8b2AC/orruj7v/NYVpHGHt2ku0iJIuE4dK X8p1DLE7vqaO+ARpFut1ZRfFvzTEC4OwTeRDGPNeH4n/ypYeeuM+sF9nbFo45s6pHGaU VPAIF6Efc+12idJcQrMEQOhETi95z0AeAbstCYdwgXswj5wrnpfmYzRDhV1GE7e0oLnx 1h9FgszPmkRuVaQOY5nWx+rGly1cJit/GkGIkyar7WqY6uRtP1/tVHIGWyi5A6cRWfw3 SixA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=uvmisi5Z; 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 Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=uvmisi5Z; 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 X-Google-Smtp-Source: AG47ELsztnh4I0hauRCuoc+85L04mW+nEgQzE+oiAvkPwn4PzUXNnR52vMu81DFjbQ2sM6QCaR3oGg== From: Andrey Konovalov To: Andrey Ryabinin , Alexander Potapenko , Dmitry Vyukov , Jonathan Corbet , Catalin Marinas , Will Deacon , Christoffer Dall , Marc Zyngier , Christopher Li , Christoph Lameter , Pekka Enberg , David Rientjes , Joonsoo Kim , Andrew Morton , Masahiro Yamada , Michal Marek , "GitAuthor : Andrey Konovalov" , Mark Rutland , Ard Biesheuvel , Yury Norov , Nick Desaulniers , Suzuki K Poulose , Kristina Martsenko , Punit Agrawal , Dave Martin , Michael Weiser , James Morse , Julien Thierry , Steve Capper , Tyler Baicar , "Eric W . Biederman" , Stephen Boyd , Thomas Gleixner , Ingo Molnar , Paul Lawrence , Greg Kroah-Hartman , David Woodhouse , Sandipan Das , Kees Cook , Herbert Xu , Geert Uytterhoeven , Josh Poimboeuf , Arnd Bergmann , kasan-dev@googlegroups.com, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-arm-kernel@lists.infradead.org, kvmarm@lists.cs.columbia.edu, 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 , Kees Cook , Jann Horn , Mark Brand Subject: [RFC PATCH v2 00/15] khwasan: kernel hardware assisted address sanitizer Date: Fri, 23 Mar 2018 19:05:36 +0100 Message-Id: X-Mailer: git-send-email 2.17.0.rc0.231.g781580f067-goog X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: =?utf-8?q?1595752692799805688?= X-GMAIL-MSGID: =?utf-8?q?1595752692799805688?= X-Mailing-List: linux-kernel@vger.kernel.org List-ID: Hi! This is the 2nd RFC version of the patchset. This patchset adds a new mode to KASAN [1], which is called KHWASAN (Kernel HardWare assisted Address SANitizer). There's still some work to do and there are a few TODOs in the code, so I'm publishing this as an RFC to collect some initial feedback. 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 ====== 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). ====== Benchmarks The following numbers were collected on Odroid C2 board. Both KASAN and KHWASAN were used in inline instrumentation mode. These are the numbers I got with the current prototype and they might change. Boot time [1]: * ~4.5 sec for clean kernel * ~5.0 sec for KASAN * ~5.1 sec for KHWASAN Slab memory usage after boot [2]: * ~32 kb for clean kernel * ~95 kb + 1/8th shadow ~= 107 kb for KASAN * ~38 kb + 1/16th shadow ~= 40 kb for KHWASAN Network performance [3]: * 11.9 Gbits/sec for clean kernel * 3.08 Gbits/sec for KASAN * 3.02 Gbits/sec for KHWASAN Note, that KHWASAN (compared to KASAN) doesn't require quarantine. [1] Time before the ext4 driver is initialized. [2] Measured as `cat /proc/meminfo | grep Slab`. [3] Measured as `iperf -s & iperf -c 127.0.0.1 -t 30`. ====== 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 (r325711 or later) with this patch applied: https://reviews.llvm.org/D44827. 3. Stack instrumentation is not supported yet (in progress). 4. There are still a few TODOs in the code, that need to be addressed. ====== Changes 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. Andrey Konovalov (15): khwasan, mm: change kasan hooks signatures khwasan: move common kasan and khwasan code to common.c khwasan: add CONFIG_KASAN_CLASSIC and CONFIG_KASAN_TAGS khwasan, arm64: adjust shadow size for CONFIG_KASAN_TAGS khwasan: initialize shadow to 0xff khwasan, arm64: untag virt address in __kimg_to_phys khwasan, arm64: fix up fault handling logic khwasan: add tag related helper functions khwasan, kvm: untag pointers in kern_hyp_va khwasan, arm64: enable top byte ignore for the kernel khwasan, mm: perform untagged pointers comparison in krealloc khwasan: add bug reporting routines khwasan: add hooks implementation khwasan, arm64: add brk handler for inline instrumentation khwasan: update kasan documentation Documentation/dev-tools/kasan.rst | 212 ++++++++------ arch/arm64/Kconfig | 1 + arch/arm64/Makefile | 2 +- arch/arm64/include/asm/brk-imm.h | 2 + arch/arm64/include/asm/kvm_mmu.h | 8 + arch/arm64/include/asm/memory.h | 22 +- arch/arm64/include/asm/pgtable-hwdef.h | 1 + arch/arm64/kernel/traps.c | 61 ++++ arch/arm64/mm/fault.c | 3 + arch/arm64/mm/kasan_init.c | 13 +- arch/arm64/mm/proc.S | 9 +- include/linux/compiler-clang.h | 9 +- include/linux/compiler-gcc.h | 4 + include/linux/compiler.h | 3 +- include/linux/kasan.h | 84 +++++- lib/Kconfig.kasan | 68 +++-- mm/kasan/Makefile | 9 +- mm/kasan/common.c | 325 +++++++++++++++++++++ mm/kasan/kasan.c | 302 +------------------- mm/kasan/kasan.h | 33 +++ mm/kasan/khwasan.c | 372 +++++++++++++++++++++++++ mm/kasan/report.c | 88 +++++- mm/slab.c | 12 +- mm/slab.h | 2 +- mm/slab_common.c | 6 +- mm/slub.c | 18 +- scripts/Makefile.kasan | 32 ++- virt/kvm/arm/mmu.c | 20 +- 28 files changed, 1266 insertions(+), 455 deletions(-) create mode 100644 mm/kasan/common.c create mode 100644 mm/kasan/khwasan.c -- 2.17.0.rc0.231.g781580f067-goog