Re: [PATCH v2 00/16] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov <andreyknvl@google.com>]

On Fri, May 25, 2018 at 4:40 PM, Andrey Konovalov <andreyknvl@google.com> wrote:
> 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.

Nevermind this part about TODOs, forgot to edit that after going from RFC to v1.

>
> 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).
>
> 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
>
> Slab memory usage after boot [2]:
> * ~40 kb for clean kernel
> * ~105 kb + 1/8th shadow ~= 118 kb for KASAN
> * ~47 kb + 1/16th shadow ~= 50 kb for KHWASAN
>
> Network performance [3]:
> * 8.33 Gbits/sec for clean kernel
> * 3.17 Gbits/sec for KASAN
> * 2.85 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 (r330044 or later).
>
> 3. Stack instrumentation is not supported yet and will be added later.
>
>
> ====== Changes
>
> 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 [1]).
>
> 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/4/19/775
>
> Andrey Konovalov (16):
>   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, arm64: fix up fault handling logic
>   khwasan: add tag related helper functions
>   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
>
>  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                  |  84 +++-
>  include/linux/mm.h                     |  29 ++
>  include/linux/page-flags-layout.h      |  10 +
>  lib/Kconfig.kasan                      |  76 +++-
>  mm/cma.c                               |  11 +
>  mm/kasan/Makefile                      |   9 +-
>  mm/kasan/common.c                      | 598 +++++++++++++++++++++++++
>  mm/kasan/kasan.c                       | 503 +--------------------
>  mm/kasan/kasan.h                       |  85 +++-
>  mm/kasan/kasan_report.c                | 155 +++++++
>  mm/kasan/khwasan.c                     | 162 +++++++
>  mm/kasan/khwasan_report.c              |  60 +++
>  mm/kasan/report.c                      | 271 +++--------
>  mm/page_alloc.c                        |   1 +
>  mm/slab.c                              |  12 +-
>  mm/slab.h                              |   2 +-
>  mm/slab_common.c                       |   6 +-
>  mm/slub.c                              |  17 +-
>  scripts/Makefile.kasan                 |  27 +-
>  32 files changed, 1630 insertions(+), 858 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
>
> --
> 2.17.0.921.gf22659ad46-goog
>