Digging through KASAN
A Dynamic Memory Error Detection Tool
KernelAddressSANitizer (KASAN) is a dynamic memory error detection tool that is used to detect invalid/bad memory accesses, such as out-of-bounds errors, or use-after-free errors, for heap, stack, and global variables. It is based on compiler instrumentation.
It has many advantages and functionalities. It serves as a fast and comprehensive solution for both UAF and OOB. It is helpful in detecting bugs at the point of occurrence, also prints informative reports about them.
KASAN has the following three modes:
1. Generic KASAN (similar to userspace ASan)
2. Software tag-based KASAN (similar to userspace HWASan)
3. Hardware tag-based KASAN (based on hardware memory tagging)
In order to enable KASAN, we need to configure the kernel with the following command:
CONFIG_KASAN =y
And other implementations include:
CONFIG_KASAN_GENERIC (to enable generic KASAN), CONFIG_KASAN_SW_TAGS (to enable software tag-based KASAN), and CONFIG_KASAN_HW_TAGS (to enable hardware tag-based KASAN).
For software modes, also choose between CONFIG_KASAN_OUTLINE and CONFIG_KASAN_INLINE. Outline and inline are compiler instrumentation types. The former produces a smaller binary while the latter is 1.1–2 times faster.
Generic KASAN
It is mainly used for debugging due to large memory overhead and is supported in GCC and Clang using Compile-time instrumentation to insert memory access checks. For this, the size of each memory granule is 8. The state of each granule is encoded in one shadow byte. Those 8 bytes can be accessible, partially accessible, freed, or be a part of a redzone. 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 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. Compiler inserts function calls (__asan_load*(addr), __asan_store*(addr)) before each memory access of size 1, 2, 4, 8, or 16. These functions check whether memory accesses are valid or not by checking corresponding shadow memory.
Software tag-based KASAN
Software KASAN modes use shadow memory to record whether each byte of memory is safe to access and use compile-time instrumentation to insert shadow memory checks before each memory access. Also used on dogfood testing devices due to its low memory overhead. It is only supported in CLANG and works with both SLUB and SLAB memory allocators. It uses the Top Byte Ignore (TBI) arm64 CPU feature, which can store pointer tags in the top byte of each kernel pointer. It uses shadow memory for storing memory tags with each 16-byte memory cell and so it dedicates 1/16th of the kernel memory for shadow memory. For each memory allocation, software tag-based KASAN generates a random tag, and tags the allocated memory with it, and embeds the same tag into the returned pointer. It currently only supports tagging of the slab and page_alloc memory.
Hardware tag-based KASAN
Hardware tag-based KASAN uses hardware memory tagging support. By relying on the Top Byte Ignore (TBI) arm64 CPU feature, pointer tags are stored in the top byte of each kernel pointer. Along with TBI, hardware tag-based KASAN also relies on the Memory Tagging Extension (MTE) which allows the storage of a tag in just bits 59–56 of a virtual address, i.e. the lower nibble of the top byte, which is not accessible via normal instructions. On every memory allocation, hardware makes sure that the tag of the memory that is being accessed is equal to the tag of the pointer that is used to access this memory. In case of a tag mismatch, a fault is generated, and a report is printed. This mode keeps the same low memory overhead as software tag-based KASAN and is expected to have a significantly lower performance impact, due to the tag checks being performed by the hardware. Thus, it is considered a better alternative in dogfood testing for hardware supporting MTE. It only reports the first found bug. After that, MTE tag checking gets disabled. Currently, it only supports SLUB.
Error reports
A common generic KASAN report looks like this:
==================================================================
BUG: KASAN: slab-out-of-bounds in _copy_from_user+0x51/0x90
Write of size 19 at addr ffff888230c0d4a0 by task bash/879CPU: 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: 0000000000000000Allocated 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/0xa9Freed 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/0x40The 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 detectedMemory 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
==================================================================
The report header summarizes the bug and its cause. Next, the stack trace of bad access, a stack trace of where the accessed memory was allocated, and the trace where the object was freed are enlisted. Later on, a briefing of the accessed slab object and memory page is mentioned.
In the end, the report shows the memory state around the access address which is separate for different modes ranging 8 to 16 aligned bytes.
Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer
