Poison, redzones and shadows: inside KASAN – Bootlin

Even if the presence of Rust is slowly increasing in the Linux kernel code base, the project largely remains written in C, and while this is the de facto language to write low level code, it unfortunately also comes with a significant ability of making mistakes, with the corresponding failures then coming in a wide variety of shapes: undefined behaviors, buffer overflows, segmentation faults… The kernel is not immune to such issues, and so kernel developers need some dedicated tooling to catch those issues early. As many problems have their roots in memory management, one tool that can legitimately sit in any kernel hacker toolbox is the Kernel Address Sanitizer, or KASAN for short. This blog does not aim to teach readers how to use KASAN: the kernel documentation is pretty explicit on this matter. We are rather going to explore KASAN internals, mostly to understand its impact (both at build time and at runtime), but up to some extent, to appreciate the elegant engineering involved in its implementation!

The Kernel Address Sanitizer KASAN is a runtime checker implemented in the kernel, allowing to catch two kinds of memory manipulation mistakes: out-of-bounds accesses and use-after-free. This tooling has to be explicitly enabled at kernel build time, as it actually depends on two main parts:

some build time instrumentation inserted by the compiler: GCC or LLVM inserts some additional code in front of all memory-accessing instructions, thanks to the Address Sanitizer library. But that’s not the only component: this additional instrumentation then needs a way to distinguish memory accesses that are legitimate from those that are invalid. To achieve this, KASAN relies on some special memory called the shadow memory, maintained by the kernel to track the whole memory it is able to use.

Enabling KASAN is pretty easy: we mostly need to enable CONFIG_KASAN and to rebuild our kernel.

KASAN also comes with a few parameters that we can tune:

the inserted instrumentation can be inlined or outlined, depending on the trade-offs we can afford some hardware support can be enabled (if our architecture supports it) to reduce KASAN overhead, like software tags and hardware tags we can tune which kind of memory is tracked (vmalloc memory, stack memory, etc)

With the goal of learning and experimenting with KASAN support, we definitely want a basic setup allowing to run a test kernel in a virtualized environment: as we may end up performing wrong memory accesses, we don’t want to crash our host kernel. There are multiple solutions to bring up such a setup; using virtme-ng from Andrea Righi surely is one of the easiest solutions. Here is a very basic setup workflow to get familiar with KASAN reports: $ git clone https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git $ cd linux && git checkout linux-7.1.y $ vng -b \ --configitem CONFIG_KASAN=y \ --configitem CONFIG_KUNIT=y \ --configitem CONFIG_KASAN_KUNIT_TEST=m $ vng --user root With this basic list of commands, we are asking virtme-ng to configure and build a kernel with basic KASAN support and the corresponding kunit tests embedded. The final vng command starts this kernel in a QEMU environment emulating the same architecture as for the host used to build the kernel, and with a minimal rootfs. Once booted, we can generate and study KASAN reports by loading the corresponding test kernel module: # modprobe kasan_test # dmesg The kernel log buffer now contains plenty of KASAN reports related to faulty memory accesses, such as this one: ================================================================== BUG: KASAN: slab-out-of-bounds in kmalloc_oob_right+0x705/0x7d0 [kasan_test] Write of size 1 at addr ffff888005fa5f73 by task kunit_try_catch/249

CPU: 2 UID: 0 PID: 249 Comm: kunit_try_catch Tainted: G N

7.1.2-virtme #6 PREEMPT(lazy) Tainted: [N]=TEST Hardware name: Bochs Bochs, BIOS Bochs 01/01/2011 Call Trace: <TASK> dump_stack_lvl+0x4d/0x70 print_report+0x14b/0x4b0 ? __pfx__raw_spin_lock_irqsave+0x10/0x10 kasan_report+0x119/0x140 ? kmalloc_oob_right+0x705/0x7d0 [kasan_test] ? kmalloc_oob_right+0x705/0x7d0 [kasan_test] kmalloc_oob_right+0x705/0x7d0 [kasan_test] ? __pfx_kmalloc_oob_right+0x10/0x10 [kasan_test] ? dequeue_task_fair+0x14d/0x6c0 ? kvm_clock_get_cycles+0x18/0x30 ? ktime_get_ts64+0x1ce/0x380 kunit_try_run_case+0x1a0/0x2c0 ? __pfx_kunit_try_run_case+0x10/0x10 ? kthread_affine_node+0x1e6/0x2d0 ? __pfx_kunit_generic_run_threadfn_adapter+0x10/0x10 kunit_generic_run_threadfn_adapter+0x85/0xf0 kthread+0x329/0x410 ? recalc_sigpending+0x162/0x210 ? __pfx_kthread+0x10/0x10 ret_from_fork+0x289/0x580 ? __pfx_ret_from_fork+0x10/0x10 ? __switch_to+0x585/0xf70 ? __

pfx_kthread+0x10/0x10 ret_from_fork_asm+0x1a/0x30 </TASK>

Allocated by task 249: kasan_save_stack+0x2f/0x50 kasan_save_track+0x14/0x30 __kasan_kmalloc+0x7f/0x90 kmalloc_oob_right+0xae/0x7d0 [kasan_test] kunit_try_run_case+0x1a0/0x2c0 kunit_generic_run_threadfn_adapter+0x85/0xf0 kthread+0x329/0x410 ret_from_fork+0x289/0x580 ret_from_fork_asm+0x1a/0x30

The buggy address belongs to the object at ffff888005fa5f00 which belongs to the cache kmalloc-128 of size 128 The buggy address is located 0 bytes to the right of allocated 115-byte region [ffff888005fa5f00, ffff888005fa5f73)

The buggy address belongs to the physical page: page: refcount:0 mapcount:0 mapping:0000000000000000 index:0x0 pfn:0x5fa4 head: order:1 mapcount:0 entire_mapcount:0 nr_pages_mapped:0 pincount:0 flags: 0x80000000000040(head|node=0|zone=1) page_type: f5(slab) raw:

0080000000000040 ffff888001042a00 dead000000000100 dead000000000122 raw: 0000000000000000 0000000000200020 00000000f5000000 0000000000000000 head: 0080000000000040 ffff888001042a00 dead000000000100 dead000000000122 head: 0000000000000000 0000000000200020 00000000f5000000 0000000000000000 head: 0080000000000001 ffffffffffffff81 00000000ffffffff 00000000ffffffff head: 0000000000000000 0000000000000000 00000000ffffffff 0000000000000000 page dumped because: kasan: bad access detected

Memory state around the buggy address: ffff888005fa5e00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 fc ffff888005fa5e80:

fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc >ffff888005fa5f00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 fc ^ ffff888005fa5f80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc ffff888005fa6000: fa fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb This reports gives us plenty of information about the nature of the faulty access:

the first line alone tells us about the exact nature of the faulty access: this is an out-of-bound access on a dynamically allocated buffer. We are also being told that it has been performed by the kmalloc_oob_right function from the kasan_test module, that it was a single byte write, and that the access address was 0x0xffff888005fa5f73. Next we have some more info about the execution context of this faulty access and the platform: the CPU on which it happened, the task that was running, the kernel version, and the platform name This is followed by the full call stack for the access Finally, depending on the kind of memory, we can have some more specific data: since the faulty access is on a slab-allocated zone, we have the corresponding allocation size, its allocation call stack, the slab cache that has been used to allocate it, and the fact that the 1-byte write was attempted immediately after the valid region (this indeed matches the test code that performs this wrong access). If we take a look at the very end of the report, we will see some details about the “memory state” around the memory being accessed: this is not the content of the accessed memory but the value of some specific memory that we need to discuss: the shadow memory used to track the accessed memory state.

KASAN shadow memory When KASAN is enabled, the kernel will not use the full amount of memory it has access to, it will instead reserve some of this memory to track the state of the rest of the kernel virtual address space: this reserved space is the shadow memory.

By default, when using the generic version of KASAN, 1 byte of shadow memory is used to track 8 bytes of kernel memory (those 8 bytes being called a “granule”): this means that 1/8th of the system memory will be used for KASAN tracking when it is enabled. There is a direct mapping between shadow memory and the main memory it is tracking The reserved shadow memory will be set at a specific address in the kernel virtual map, which depends on the architecture. If we take a look for example at the x86_64 memory map, we will see that the shadow memory is mapped at address 0xffffec0000000000. This can be verified on our test kernel by  rebuilding it with CONFIG_PTDUMP_DEBUGFS, which allows us to check for the kernel mappings directly from debugfs: $ make menuconfig #Select CONFIG_PTDUMP_DEBUGFS $ vng -b $ vng --user root -- grep -A1 "\[ KASAN shadow \]" \ /sys/kernel/debug/page_tables/current_kernel ---[ KASAN shadow ]--- 0xffffec0000000000-0xffffed1000000000 1088G ro GLB NX pte As KASAN uses a direct mapping between kernel memory and the corresponding shadow memory, there is a well-defined relationship between an address and its corresponding shadow byte: shadow_byte = (target_addr >> KASAN_SHADOW_SCALE_SHIFT) + KASAN_SHADOW_OFFSET The target address is first shifted right by KASAN_SHADOW_SCALE_SHIFT: this is directly related to the granule size (8 bytes, monitored by a single byte), and so despite it being re-defined for each architecture supporting KASAN, this value is always equal to 3 for generic KASAN. This is not enough to get the address of a matching shadow memory though: we must make sure that this computed address falls in the shadow memory range, so we offset it with KASAN_SHADOW_OFFSET.

Take care that this value really is an offset, and so it does not point to the KASAN shadow region: this is also the value that is passed to the compiler so that it can correctly emit  inlined instrumentation. However, KASAN_SHADOW_OFFSETis used to derive KASAN_SHADOW_START and KASAN_SHADOW_END. But then, what is the exact meaning of the values that can be found in this shadow memory? First, the value found in a shadow memory byte can be negative: it means that the corresponding granule is not some valid memory area, and so the kernel should not try to access it. Otherwise, the number of bits being set to 0 hints about the number of valid bytes in the granule. If the whole granule is properly allocated and accesses to it are legitimate, then the corresponding shadow byte will be 0x00. But depending on an allocation size, maybe only a fraction of a granule will be valid! In this case, the value of the shadow memory byte indicates what part of the granule is accessible:

0x1: the first byte is accessible, the 7 other bytes should not be accessed 0x2: the two first bytes are accessible, the 6 other bytes should not be accessed 0x3: the three first bytes are accessible, the 5 other bytes should not be accessed and so on

So shadow memory allows to track at byte granularity the end of an allocated memory region. Why don’t we have the same granularity for the beginning of a memory region? Because the memory returned by kernel allocators has a minimal alignment which matches the granule size (8 bytes), so the beginning of an allocated region will always match the beginning of a new byte in shadow memory! (see ARCH_KMALLOC_MINALIGN). So now we know how the shadow memory represents the state of the kernel memory, but we still don’t know yet when it is updated. That’s something that can have been already guessed though: memory tracking is updated when said memory is allocated or de-allocated!  We can for example take a look at the kmalloc function in the kernel, and following all the children functions, we will eventually find __do_kmalloc_node, which executes two different steps when updating the shadow memory for the allocated memory:

it will first call slab_alloc_node, which calls kasan_slab_alloc.