KASAN: What is it? How does it work? And what are the strange numbers at the end?

Why Should I Care About Sanitizers?

Achieving memory safety is hard. Code is written by humans, and humans are bound to make mistakes. Tack on pointer arithmetic and strict aliasing and the situation only becomes more complex. ZDNet recently posted an article stating that 70 percent of all (Microsoft) security bugs are memory safety issues, and I would guess that this statistic is not specific to Microsoft. In LLVM 3.1 and in GCC 4.8, the compilers introduced the -fsanitize=address option and the asan libraries for user-space applications to be built with the Address Sanitizer. The Address Sanitizer is a tool that helps detect use after free bugs, buffer overflows, use after return bugs, and memory leaks. While not suitable for a production environment, setting up an address sanitizer in a testing environment is easy when compared to the potential pay offs. In most cases one can benefit from address sanitizers by merely adding the -fsanitize=address -fno-omit-frame-pointer flags to CFLAGS, building the project, and running the tests. Both the LLVM and GCC implementations are great. There is an extensive pros and cons document maintained by Google that can be found on the the google sanitizers wiki.

KASAN: What is it?

Implementing support for address sanitizers for user-space applications has undoubtedly been a success, so in v5.0 of GCC the -fsanitize=kernel-address compiler flag was added, and in v4.0 of the Linux Kernel, support for building a kernel with this option was added with the CONFIG_KASAN Kconfig option. This option enables a fast and efficient memory error detector with minor performance degradation.

Implementation Details

It can be helpful to understand how KASAN is implemented when debugging issues discovered when using it. In this section we will discuss how KASAN_GENERIC is implemented. All examples will assume the x86_64 architecture.

Shadow Memory

The state of each 8 aligned bytes of memory is encoded in a byte in shadow memory. As a result, 1/8th of the kernel’s memory is dedicated to this shadow memory. The compiler instrumentation then relies on intrinsics provided by the kernel. The kernel intrinsics find the address of the corresponding shadow memory then determine if each access is valid based on the state stored in the shadow memory and the size requested. The translation function for finding the shadow region is kasan_mem_to_shadow which is implemented as:

static inline void *kasan_mem_to_shadow(const void *addr)
{
        return (void *)((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT)
                + KASAN_SHADOW_OFFSET;
}

Each byte of the shadow region encodes the status of the address to be accessed as:

0x00 All 8 bytes are accessible.

0x00 < N < 0x08 The lower N bytes are accessible. Bytes 8 - N to byte 8 are not.

0xff The page was freed.

0xfe A redzone for kmalloc_large.

0xfc A redzone for a slub object.

0xfb The object was freed.

0xf5 Stack use after return.

0xf8 Stack use after scope.

For example, let’s say we were to have some code like the following:

  u8 *ptr = kmalloc(12, GFP_KERNEL); /* ptr=0xffff8882245bc8c0 */
  ...
  kfree(ptr);

The address space and encoding in the shadow buffer would look something like the following:

In addition to setting up the shadow memory for encoding the state of the address, The kernel then must implement several __asan_load and __asan_store functions. Given an address and size, the kernel must check the shadow region to ensure the access is valid, returning true if it is and false if it is not. If the CONFIG_KASAN_INLINE option is set, the calls to these functions will be inlined causing a significant increase in performance at the cost of an increase in the size of the kernel image.

Redzone

Each shadow state area is surrounded by gaps called ‘redzones’, used to detect overflow in consecutive buffers. In order to see why this is necessary let us consider what the shadow state would contain for two consecutive heap allocations without a redzone surrounding them for an allocation of 16 bytes followed by an allocation of 12 bytes.

Note that this encoding is exactly what we would expect the shadow state to be for a buffer of 28 bytes in length. As a result, we might not catch buffer overflows of the first buffer.

With the introduction of the redzone gaps between buffer shadow states, we can easily detect buffer overflows even when a buffer is sized with 8 byte increments.

Example

Let’s test out KASAN by creating a kernel module that creates a proc device that contains a buffer overflow.

Create the Module

Create a file test_kasan.c that contains something like this:

#include <linux/fs.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/slab.h>
#include <linux/uaccess.h>

static struct proc_dir_entry *entry;

static u8 *test_kasan_buffer;

static ssize_t test_kasan_write(
      struct file *filep, const char __user *buf,
      size_t length, loff_t *off)
{
    unsigned long n;
    n = copy_from_user(test_kasan_buffer, buf, length);
    return length;
}

static struct file_operations test_kasan_fops = {
    .owner = THIS_MODULE,
    .write = test_kasan_write
};

static int __init test_kasan_init(void)
{
    test_kasan_buffer = kmalloc(14, GFP_KERNEL);
    if (!test_kasan_buffer)
        return -ENOMEM;

    entry = proc_create("test_kasan", S_IWUSR, NULL, &test_kasan_fops);
    if (!entry)
        return -ENOMEM;

    return 0;
}

static void test_kasan_exit(void)
{
    kfree(test_kasan_buffer);
    remove_proc_entry("test_kasan", NULL);
}

MODULE_AUTHOR("Star Lab <info@starlab.io>");
MODULE_DESCRIPTION("Testing KASAN");
MODULE_LICENSE("GPL");

module_init(test_kasan_init);
module_exit(test_kasan_exit);

Note that our proc device’s write implementation test_kasan_write does not check the length of the write before attempting to write to our local buffer, test_kasan_buffer, with copy_from_user. Our local buffer points to 14 bytes of allocated memory, so any write to the /proc/test_kasan device that is over 14 bytes in length should trigger an error.

Triggering a KASAN Error

After compiling the module and creating a VM that boots a kernel with CONFIG_KASAN set, we should be able to trigger a KASAN error after loading the module with something like the following:

echo "Hello, KASAN error" > /proc/test_kasan

This should trigger an error and display a report.

Dissecting the Report

The load and store functions should also dump a report for the user if the memory check finds an issue with the memory access. The report provides information useful for debugging the error and provides a backtrace that should look familiar if you have seen a kernel oops or panic before. A simple example is shown below:

 ==================================================================
 BUG: KASAN: slab-out-of-bounds in _copy_from_user+0x51/0x90
 Write of size 19 at addr ffff888230c0d4a0 by task bash/879

 CPU: 3 PID: 879 Comm: bash Tainted: G           O      5.4.0-rc5+ #16
 Hardware name: QEMU Standard PC (Q35 + ICH9, 2009), BIOS ?
\-20190711_202441-buildvm-armv7-10.arm.fedoraproject.org-2.fc31 04/01/2014
 Call Trace:
  dump_stack+0x5b/0x90
  print_address_description.constprop.0+0x16/0x200
  ? _copy_from_user+0x51/0x90
  ? _copy_from_user+0x51/0x90
  __kasan_report.cold+0x1a/0x41
  ? _copy_from_user+0x51/0x90
  kasan_report+0xe/0x20
  check_memory_region+0x130/0x1a0
  _copy_from_user+0x51/0x90
  test_kasan_write+0x11/0x30 [test_kasan]
  proc_reg_write+0x110/0x160
  ? proc_reg_unlocked_ioctl+0x150/0x150
  ? __pmd_alloc+0x150/0x150
  ? __audit_syscall_entry+0x18e/0x1f0
  ? ktime_get_coarse_real_ts64+0x46/0x60
  ? security_file_permission+0x66/0x190
  vfs_write+0xed/0x240
  ksys_write+0xb4/0x150
  ? __ia32_sys_read+0x40/0x40
  ? up_read+0x10/0x70
  ? do_user_addr_fault+0x3da/0x560
  do_syscall_64+0x5e/0x190
  entry_SYSCALL_64_after_hwframe+0x44/0xa9
 RIP: 0033:0x7fe39aa3c150
 Code: 73 01 c3 48 8b 0d 20 6d 2d 00 f7 d8 64 89 01 48 83 c8 ff c3\
 66 0f 1f 44 00 00 83 3d 4d ce 2d 00 00 75 10 b8 01 00 00 00 0f 05\
 <48> 3d 01 f0 ff ff 73 31 c3 48 83 ec 08 e8 ee cb 01 00 48 89 04 24
 RSP: 002b:00007fff5b7839d8 EFLAGS: 00000246 ORIG_RAX: 0000000000000001
 RAX: ffffffffffffffda RBX: 0000000000000011 RCX: 00007fe39aa3c150
 RDX: 0000000000000011 RSI: 00007fe39b366000 RDI: 0000000000000001
 RBP: 00007fe39b366000 R08: 000000000000000a R09: 00007fe39b35c740
 R10: 0000000000000022 R11: 0000000000000246 R12: 00007fe39ad14400
 R13: 0000000000000011 R14: 0000000000000001 R15: 0000000000000000

 Allocated by task 894:
  save_stack+0x1b/0x80
  __kasan_kmalloc.constprop.0+0xc2/0xd0
  0xffffffffc0008022
  do_one_initcall+0x86/0x29f
  do_init_module+0xf8/0x350
  load_module+0x3e57/0x4120
  __do_sys_finit_module+0x162/0x190
  do_syscall_64+0x5e/0x190
  entry_SYSCALL_64_after_hwframe+0x44/0xa9

 Freed by task 614:
  save_stack+0x1b/0x80
  __kasan_slab_free+0x12c/0x170
  kfree+0x90/0x240
  xdr_free_bvec+0x1a/0x30
  xprt_release+0x10a/0x270
  rpc_release_resources_task+0x14/0x70
  __rpc_execute+0x253/0x590
  rpc_async_schedule+0x44/0x70
  process_one_work+0x476/0x760
  worker_thread+0x73/0x680
  kthread+0x18c/0x1e0
  ret_from_fork+0x35/0x40

 The buggy address belongs to the object at ffff888230c0d4a0
  which belongs to the cache kmalloc-16 of size 16
 The buggy address is located 0 bytes inside of
  16-byte region [ffff888230c0d4a0, ffff888230c0d4b0)
 The buggy address belongs to the page:
 page:ffffea0008c30340 refcount:1 mapcount:0
mapping:ffff888236403b80 index:0xffff888230c0d9c0
 flags: 0x200000000000200(slab)
 raw: 0200000000000200 ffffea0008b86700 0000001200000012 ffff888236403b80
 raw: ffff888230c0d9c0 0000000080800079 00000001ffffffff 0000000000000000
 page dumped because: kasan: bad access detected

 Memory state around the buggy address:
  ffff888230c0d380: 00 00 fc fc fb fb fc fc fb fb fc fc fb fb fc fc
  ffff888230c0d400: fb fb fc fc fb fb fc fc fb fb fc fc fb fb fc fc
 >ffff888230c0d480: fb fb fc fc 00 06 fc fc fb fb fc fc 00 00 fc fc
                                   ^
  ffff888230c0d500: 00 00 fc fc 00 00 fc fc 00 00 fc fc 00 00 fc fc
  ffff888230c0d580: 00 00 fc fc 00 00 fc fc 00 00 fc fc 00 00 fc fc
 ==================================================================

Note that the last section of the report includes a hex dump of the associated shadow memory for the access that triggered the error. The line of interest to us in the hex dump is indicated by a >. The exact byte that encodes the 8 byte section the address was located in is indicated by a ^.

 >ffff888230c0d480: fb fb fc fc 00 06 fc fc fb fb fc fc 00 00 fc fc
                                   ^

We can use this information along with the cause of the error shown in line 2 (Write of size 19 at addr ffff888230c0d4a0) to gain some information about the error.

In the example above, we see the buffer is encoded with the bytes 00 06. This byte sequence encodes an 8 byte region followed by a 6 byte region which would be the encoding for a buffer of 14 bytes in length. This checks with the error provided as a write of size 19 to this buffer would write beyond the end of the buffer.