[RFC PATCH 00/14] khwasan: kernel hardware assisted address sanitizer

[Andrey Konovalov <andreyknvl@google.com>]

This patchset adds a new mode to KASAN, 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 a RFC to
collect some initial feedback.

The plan is to implement HWASan [1] for the kernel with the incentive,
that it's going to have comparable 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] 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 random tag, and
   acts as a redzone.

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.

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.


====== Benchmarks

As of now I've only did a few simple tests of KHWASAN on arm64 in QEMU
emulation mode. I'm yet to perform proper benchmarks on actual hardware.

These are the numbers I got with the current prototype and they are likely
to change.

Boot time:
* ~3.5 sec for clean kernel
* ~5.6 sec for KASAN
* ~8.9 sec for KHWASAN

The difference in KASAN and KHWASAN performance here can be explained by
QEMU performance drop when it needs to emulate Top Byte Ignore. I don't
think there's any reason to belive that the final implementation will
cause significant performance drop compared to KASAN on actual hardware.

Slab memory usage after boot:
* ~15 kb for clean kernel
* ~60 kb for KASAN
* ~16 kb for KHWASAN

Note, that KHWASAN (compared to KASAN) doesn't require quarantine and uses
twice as less shadow memory (1/16th vs 1/8th).


====== 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).

3. Stack instrumentation is not supported yet (in progress).

4. There's at least one issue with using the top byte of kernel pointers,
   see the jbd2 commit for details.

5. There's still a few TODOs in the code, that need to be addressed.


Andrey Konovalov (14):
  khwasan: change kasan hooks signatures
  khwasan: move common kasan and khwasan code to common.c
  khwasan: add CONFIG_KASAN_CLASSIC and CONFIG_KASAN_TAGS
  khwasan: adjust shadow size for CONFIG_KASAN_TAGS
  khwasan: initialize shadow to 0xff
  khwasan: enable top byte ignore for the kernel
  khwasan: add tag related helper functions
  khwasan: perform untagged pointers comparison in krealloc
  khwasan: add hooks implementation
  khwasan: add bug reporting routines
  khwasan: add brk handler for inline instrumentation
  khwasan, jbd2: add khwasan annotations
  khwasan: update kasan documentation
  khwasan: default the instrumentation mode to inline

 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/memory.h        |  13 +-
 arch/arm64/include/asm/pgtable-hwdef.h |   1 +
 arch/arm64/kernel/traps.c              |  40 +++
 arch/arm64/mm/kasan_init.c             |  13 +-
 arch/arm64/mm/proc.S                   |   8 +-
 fs/jbd2/journal.c                      |   6 +
 include/linux/compiler-clang.h         |   7 +-
 include/linux/compiler-gcc.h           |   4 +
 include/linux/compiler.h               |   3 +-
 include/linux/kasan.h                  |  84 ++++--
 lib/Kconfig.kasan                      |  70 +++--
 mm/kasan/Makefile                      |   9 +-
 mm/kasan/common.c                      | 325 ++++++++++++++++++++++++
 mm/kasan/kasan.c                       | 302 +---------------------
 mm/kasan/kasan.h                       |  29 +++
 mm/kasan/khwasan.c                     | 338 +++++++++++++++++++++++++
 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 ++-
 26 files changed, 1177 insertions(+), 450 deletions(-)
 create mode 100644 mm/kasan/common.c
 create mode 100644 mm/kasan/khwasan.c

-- 
2.16.2.395.g2e18187dfd-goog

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>