On Mon, Nov 19, 2018 at 6:26 PM, Andrey Konovalov <andreyknvl@xxxxxxxxxx> wrote: > This patchset adds a new software tag-based mode to KASAN [1]. > (Initially this mode was called KHWASAN, but it got renamed, > see the naming rationale at the end of this section). > > 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 underlying ideas of the approach used by software tag-based KASAN are: > > 1. By using the Top Byte Ignore (TBI) 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. > > With this patchset the existing KASAN mode gets renamed to generic KASAN, > with the word "generic" meaning that the implementation can be supported > by any architecture as it is purely software. > > The new mode this patchset adds is called software tag-based KASAN. The > word "tag-based" refers to the fact that this mode uses tags embedded into > the top byte of kernel pointers and the TBI arm64 CPU feature that allows > to dereference such pointers. The word "software" here means that shadow > memory manipulation and tag checking on pointer dereference is done in > software. As it is the only tag-based implementation right now, "software > tag-based" KASAN is sometimes referred to as simply "tag-based" in this > patchset. > > A potential expansion of this mode is a hardware tag-based mode, which would > use hardware memory tagging support (announced by Arm [3]) instead of > compiler instrumentation and manual shadow memory manipulation. > > Same as generic KASAN, software tag-based KASAN is strictly a debugging > feature. > > [1] https://www.kernel.org/doc/html/latest/dev-tools/kasan.html > > [2] http://clang.llvm.org/docs/HardwareAssistedAddressSanitizerDesign.html > > [3] https://community.arm.com/processors/b/blog/posts/arm-a-profile-architecture-2018-developments-armv85a > > > ====== Rationale > > On mobile devices generic KASAN's memory usage is significant problem. One > of the main reasons to have tag-based KASAN is to be able to perform a > similar set of checks as the generic one does, but with lower memory > requirements. > > Comment from Vishwath Mohan <vishwath@xxxxxxxxxx>: > > 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 <eugenis@xxxxxxxxxx>: > > 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 > > Software tag-based KASAN mode is implemented in a very similar way to the > generic one. 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 > KASAN simply prints a bug report. In case of inline instrumentation, > clang inserts a brk instruction, and KASAN 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 tag-based KASAN can > detect compared to generic KASAN: use-after-free after the object has been > allocated by someone else. > > > ====== Testing > > Some kernel developers voiced a concern that changing the top byte of > kernel pointers may lead to subtle bugs that are difficult to discover. > To address this concern deliberate testing has been performed. > > It doesn't seem feasible to do some kind of static checking to find > potential issues with pointer tagging, so a dynamic approach was taken. > All pointer comparisons/subtractions have been instrumented in an LLVM > compiler pass and a kernel module that would print a bug report whenever > two pointers with different tags are being compared/subtracted (ignoring > comparisons with NULL pointers and with pointers obtained by casting an > error code to a pointer type) has been used. Then the kernel has been > booted in QEMU and on an Odroid C2 board and syzkaller has been run. > > This yielded the following results. > > The two places that look interesting are: > > is_vmalloc_addr in include/linux/mm.h > is_kernel_rodata in mm/util.c > > Here we compare a pointer with some fixed untagged values to make sure > that the pointer lies in a particular part of the kernel address space. > Since tag-based KASAN doesn't add tags to pointers that belong to rodata > or vmalloc regions, this should work as is. To make sure debug checks to > those two functions that check that the result doesn't change whether > we operate on pointers with or without untagging has been added. > > A few other cases that don't look that interesting: > > Comparing pointers to achieve unique sorting order of pointee objects > (e.g. sorting locks addresses before performing a double lock): > > tty_ldisc_lock_pair_timeout in drivers/tty/tty_ldisc.c > pipe_double_lock in fs/pipe.c > unix_state_double_lock in net/unix/af_unix.c > lock_two_nondirectories in fs/inode.c > mutex_lock_double in kernel/events/core.c > > ep_cmp_ffd in fs/eventpoll.c > fsnotify_compare_groups fs/notify/mark.c > > Nothing needs to be done here, since the tags embedded into pointers > don't change, so the sorting order would still be unique. > > Checks that a pointer belongs to some particular allocation: > > is_sibling_entry in lib/radix-tree.c > object_is_on_stack in include/linux/sched/task_stack.h > > Nothing needs to be done here either, since two pointers can only belong > to the same allocation if they have the same tag. > > Overall, since the kernel boots and works, there are no critical bugs. > As for the rest, the traditional kernel testing way (use until fails) is > the only one that looks feasible. > > Another point here is that tag-based KASAN is available under a separate > config option that needs to be deliberately enabled. Even though it might > be used in a "near-production" environment to find bugs that are not found > during fuzzing or running tests, it is still a debug tool. > > > ====== Benchmarks > > The following numbers were collected on Odroid C2 board. Both generic and > tag-based KASAN were used in inline instrumentation mode. > > Boot time [1]: > * ~1.7 sec for clean kernel > * ~5.0 sec for generic KASAN > * ~5.0 sec for tag-based KASAN > > Network performance [2]: > * 8.33 Gbits/sec for clean kernel > * 3.17 Gbits/sec for generic KASAN > * 2.85 Gbits/sec for tag-based KASAN > > Slab memory usage after boot [3]: > * ~40 kb for clean kernel > * ~105 kb (~260% overhead) for generic KASAN > * ~47 kb (~20% overhead) for tag-based KASAN > > 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 tag-based vs generic KASAN for each of these points: > 1. 20% vs 260% overhead. > 2. 1/16th vs 1/8th of physical memory. > 3. Tag-based KASAN 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 Clang version (7.0.0 or later). > > 3. Stack instrumentation is not supported yet and will be added later. > > > ====== Changes > > Changes in v11: > - Rebased onto 9ff01193 (4.20-rc3). > - Moved KASAN_SHADOW_SCALE_SHIFT definition to arch/arm64/Makefile. > - Added and used CC_HAS_KASAN_GENERIC and CC_HAS_KASAN_SW_TAGS configs to > detect compiler support. > - New patch: "kasan: rename kasan_zero_page to kasan_early_shadow_page". > - New patch: "arm64: move untagged_addr macro from uaccess.h to memory.h". > - Renamed KASAN_SET_TAG/... macros in arch/arm64/include/asm/memory.h to > __tag_set/... and reused them later in KASAN core code instead of > redefining. > - Removed tag reset from the __kimg_to_phys() macro. > - Fixed tagged pointer handling in arm64 fault handling logic. Hi Mark and Catalin, I've addressed your comments, please take a look. Thanks! > > Changes in v10: > - Rebased onto 65102238 (4.20-rc1). > - Don't ignore kasan_kmalloc() return valued in kmem_cache_alloc_trace() > and kmem_cache_alloc_node_trace() in include/linux/slab.h. > - New patch: don't ignore kasan_kmalloc return value in > early_kmem_cache_node_alloc. > - New patch: added __must_check annotations to KASAN hooks that assign > tags. > - Changed KASAN clang version requirement to 7.0.0 (as we need rL329612). > - Moved __no_sanitize_address definition from compiler_attributes.h to > compiler-gcc.h and compiler-clang.h. > > Changes in v9: > - Fixed kasan_init_slab_obj() hook when KASAN is disabled. > - Added assign_tag() function that preassigns tags for caches with > constructors. > - Fixed KASAN_TAG_MASK redefinition in include/linux/mm.h vs > mm/kasan/kasan.h. > > Changes in v8: > - Rebased onto 7876320f (4.19-rc4). > - Renamed KHWASAN to software tag-based KASAN (see the top of the cover > letter for details). > - Explicitly called tag-based KASAN a debug tool. > - Reused kasan_init_slab_obj() callback to preassign tags to caches > without constructors, remove khwasan_preset_sl(u/a)b_tag(). > - Moved move obj_to_index to include/linux/slab_def.h from mm/slab.c. > - Moved cache->s_mem untagging to alloc_slabmgmt() for SLAB. > - Fixed check_memory_region() to correctly handle user memory accesses and > size == 0 case. > - Merged __no_sanitize_hwaddress into __no_sanitize_address. > - Defined KASAN_SET_TAG and KASAN_RESET_TAG macros for non KASAN builds to > avoid duplication of __kimg_to_phys, _virt_addr_is_linear and > page_to_virt macros. > - Fixed and simplified find_first_bad_addr for generic KASAN. > - Use non symbolized example KASAN report in documentation. > - Mention clang version requirements for both KASAN modes in the Kconfig > options and in the documentation. > - Various small fixes. > > Version v7 got accidentally skipped. > > Changes in v6: > - Rebased onto 050cdc6c (4.19-rc1+). > - Added notes regarding patchset testing into the cover letter. > > 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 > > Reviewed-by: Andrey Ryabinin <aryabinin@xxxxxxxxxxxxx> > Reviewed-by: Dmitry Vyukov <dvyukov@xxxxxxxxxx> > Signed-off-by: Andrey Konovalov <andreyknvl@xxxxxxxxxx> > > Andrey Konovalov (24): > kasan, mm: change hooks signatures > kasan, slub: handle pointer tags in early_kmem_cache_node_alloc > kasan: move common generic and tag-based code to common.c > kasan: rename source files to reflect the new naming scheme > kasan: add CONFIG_KASAN_GENERIC and CONFIG_KASAN_SW_TAGS > kasan, arm64: adjust shadow size for tag-based mode > kasan: rename kasan_zero_page to kasan_early_shadow_page > kasan: initialize shadow to 0xff for tag-based mode > arm64: move untagged_addr macro from uaccess.h to memory.h > kasan: add tag related helper functions > kasan, arm64: untag address in _virt_addr_is_linear > kasan: preassign tags to objects with ctors or SLAB_TYPESAFE_BY_RCU > kasan, arm64: fix up fault handling logic > kasan, arm64: enable top byte ignore for the kernel > kasan, mm: perform untagged pointers comparison in krealloc > kasan: split out generic_report.c from report.c > kasan: add bug reporting routines for tag-based mode > mm: move obj_to_index to include/linux/slab_def.h > kasan: add hooks implementation for tag-based mode > kasan, arm64: add brk handler for inline instrumentation > kasan, mm, arm64: tag non slab memory allocated via pagealloc > kasan: add __must_check annotations to kasan hooks > kasan: update documentation > kasan: add SPDX-License-Identifier mark to source files > > Documentation/dev-tools/kasan.rst | 232 +++++---- > arch/arm64/Kconfig | 1 + > arch/arm64/Makefile | 11 +- > arch/arm64/include/asm/brk-imm.h | 2 + > arch/arm64/include/asm/kasan.h | 8 +- > arch/arm64/include/asm/memory.h | 42 +- > arch/arm64/include/asm/pgtable-hwdef.h | 1 + > arch/arm64/include/asm/uaccess.h | 7 - > arch/arm64/kernel/traps.c | 68 ++- > arch/arm64/mm/fault.c | 31 +- > arch/arm64/mm/kasan_init.c | 56 ++- > arch/arm64/mm/proc.S | 8 +- > arch/s390/mm/dump_pagetables.c | 16 +- > arch/s390/mm/kasan_init.c | 33 +- > arch/x86/mm/dump_pagetables.c | 11 +- > arch/x86/mm/kasan_init_64.c | 55 ++- > arch/xtensa/mm/kasan_init.c | 18 +- > include/linux/compiler-clang.h | 5 +- > include/linux/compiler-gcc.h | 6 + > include/linux/compiler_attributes.h | 13 - > include/linux/kasan.h | 101 +++- > include/linux/mm.h | 29 ++ > include/linux/page-flags-layout.h | 10 + > include/linux/slab.h | 4 +- > include/linux/slab_def.h | 13 + > lib/Kconfig.kasan | 96 +++- > mm/cma.c | 11 + > mm/kasan/Makefile | 15 +- > mm/kasan/{kasan.c => common.c} | 655 +++++++++---------------- > mm/kasan/generic.c | 344 +++++++++++++ > mm/kasan/generic_report.c | 153 ++++++ > mm/kasan/{kasan_init.c => init.c} | 71 +-- > mm/kasan/kasan.h | 59 ++- > mm/kasan/quarantine.c | 1 + > mm/kasan/report.c | 272 +++------- > mm/kasan/tags.c | 161 ++++++ > mm/kasan/tags_report.c | 58 +++ > mm/page_alloc.c | 1 + > mm/slab.c | 29 +- > mm/slab.h | 2 +- > mm/slab_common.c | 6 +- > mm/slub.c | 51 +- > scripts/Makefile.kasan | 53 +- > 43 files changed, 1822 insertions(+), 997 deletions(-) > rename mm/kasan/{kasan.c => common.c} (59%) > create mode 100644 mm/kasan/generic.c > create mode 100644 mm/kasan/generic_report.c > rename mm/kasan/{kasan_init.c => init.c} (82%) > create mode 100644 mm/kasan/tags.c > create mode 100644 mm/kasan/tags_report.c > > -- > 2.19.1.1215.g8438c0b245-goog >
