January 29, 2016 - Shuah Khan
An Introduction to Using KASan to Detect Dynamic Memory Errors
The Next Generation Media Controller added several new interfaces to add and remove media graph objects. I started running tests with KASan enabled to detect dynamic memory errors introduced in this work, and I ended up finding some out-of-bounds address access and use-after-free bugs. This article will introduce you to KASan and provide some examples of how it can be valuable.
What is KASan?
Kernel Address sanitizer (KASan) is a dynamic memory error detector. It provides a fast and comprehensive solution for finding use-after-free and out-of-bounds bugs. KASan uses compile-time instrumentation to allocate shadow memory to keep track of out-of-bounds and use-after-free bugs. Each memory allocation gets the same area allocated in the shadow memory and accesses to allocated areas results in corresponding shadow memory accesses which then KASan flags when out-of-bounds access or use-after-free accesses occur.
How to Use KASan
The dependencies are:
- gcc 4.9.2 or later
- gcc 5.2 or later is required to detect out of bounds accesses to stack or global variables
- SLUB allocator
- Supported only on x86_64 architecture.
It is very easy to use it, simply enable CONFIG_KASAN = y.
You can choose between outline/inline compiler instrumentation types by enabling the CONFIG_KASAN_OUTLINE or CONFIG_KASAN_INLINE kernel configuration options. I chose CONFIG_KASAN_INLINE because it is 1.1 to 2 times faster compared to the outline option. However, the outline option produces smaller binary. KASan allows disabling instrumentation for specific files or directories. Simply add KASAN_SANITIZE_main.o := n to disable a single file or KASAN_SANITIZE := n for all files in a directory to the respective makefile.
Finding Errors in the Next Generation Media Controller
The out-of-bounds access bug I was able to find using KASan was a result of a cut and paste error which resulted in allocating memory for an incorrect, smaller data structure. This problem would have been very hard to find and debug without KASan. The fix is a single line change shown below:
- /* allocate media_ctl */
- mctl = kzalloc(sizeof(struct media_ctl), GFP_KERNEL);
+ /* allocate media_mixer_ctl */
+ mctl = kzalloc(sizeof(*mctl), GFP_KERNEL);
The KASan report for the out-of-bounds bug I found looked like the following (please note: this report is shortened to show only the important details):
[ 205.120798] BUG: KASan: out of bounds access in media_entity_init+0x2ad/0x2c0 at addr ffff88009b6591f0
[ 205.120805] Write of size 8 by task systemd-udevd/1647
[ 205.120809] ================================================
[ 205.120816] BUG kmalloc-256 (Not tainted): kasan: bad access detected
[ 205.120820] ----------------------------------------------------------------
[ 205.120977] Call Trace:
[ 205.120987] [<ffffffff828d320b>] dump_stack+0x45/0x57
[ 205.120996] [<ffffffff814ea689>] print_trailer+0xf9/0x150
[ 205.121003] [<ffffffff814ef838>] object_err+0x38/0x50
[ 205.121010] [<ffffffff814f1f89>] kasan_report_error+0x1d9/0x3c0
[ 205.121018] [<ffffffff811efbf8>] ? mark_held_locks+0xc8/0x120
[ 205.121025] [<ffffffff814f2433>] __asan_report_store8_noabort+0x43/0x50
[ 205.121032] [<ffffffff822889ad>] ? media_entity_init+0x2ad/0x2c0
[ 205.121039] [<ffffffff822889ad>] media_entity_init+0x2ad/0x2c0
[ 205.121068] [<ffffffffa0f4ed00>] media_mixer_init+0x2a0/0x520 [snd_usb_audio]
[ 205.121089] [<ffffffffa0f2e59c>] ? snd_usb_create_mixer+0x3dc/0xc40 [snd_usb_audio]
[ 205.121109] [<ffffffffa0f12625>] usb_audio_probe+0x1205/0x21f0 [snd_usb_audio]
[ 205.121129] [<ffffffffa0f11420>] ? snd_usb_create_stream+0x4e0/0x4e0 [snd_usb_audio]
[ 205.121135] [<ffffffff811f022d>] ? trace_hardirqs_on+0xd/0x10
[ 205.121142] [<ffffffff828e5b7e>] ? mutex_unlock+0xe/0x10
[ 205.121150] [<ffffffff82104aa0>] usb_probe_interface+0x420/0x870
[ 205.121158] [<ffffffff81ea051f>] driver_probe_device+0x3cf/0xcf0
[ 205.121165] [<ffffffff81ea0e40>] ? driver_probe_device+0xcf0/0xcf0
[ 205.121171] [<ffffffff81ea0e40>] ? driver_probe_device+0xcf0/0xcf0
[ 205.121177] [<ffffffff81ea0f6d>] __driver_attach+0x12d/0x170
[ 205.121184] [<ffffffff81e9a9e2>] bus_for_each_dev+0x122/0x1a0
[ 205.121190] [<ffffffff828bf456>] ? klist_add_tail+0xb6/0xf0
[ 205.121196] [<ffffffff81e9a8c0>] ? subsys_dev_iter_exit+0x10/0x10
[ 205.121202] [<ffffffff828eac5b>] ? _raw_spin_unlock+0x2b/0x40
[ 205.121209] [<ffffffff81e9f34d>] driver_attach+0x3d/0x50
[ 205.121215] [<ffffffff81e9e6b9>] bus_add_driver+0x4c9/0x770
[ 205.121222] [<ffffffff81ea26cc>] driver_register+0x18c/0x3b0
[ 205.121229] [<ffffffff81202556>] ? __raw_spin_lock_init+0x36/0x110
[ 205.121237] [<ffffffff8100035b>] ? do_one_initcall+0x11b/0x2c0
[ 205.121245] [<ffffffff820ffe88>] usb_register_driver+0x1f8/0x440
[ 205.121250] [<ffffffff814f1a54>] ? kasan_slab_free+0x44/0x50
[ 205.121256] [<ffffffffa0f90000>] ? 0xffffffffa0f90000
[ 205.121276] [<ffffffffa0f9001e>] usb_audio_driver_init+0x1e/0x1000 [snd_usb_audio]
For more information on KASan, please refer to the Linux Kernel documentation for it, and this article from LWN. I’ve found KASan to be very easy to use and to be extremely useful; I plan to use it whenever I make changes to the Kernel related to memory allocation, and you should too.
About Shuah Khan
Shuah Khan is a Senior Linux Kernel Developer at Samsung's Open Source Group. She is a Linux Kernel Maintainer and Contributor who focuses on Linux Media Core and Power Management. She maintains Kernel Selftest framework. She has contributed to IOMMU, and DMA areas. In addition, she is helping with stable release kernel testing. She authored Linux Kernel Testing and Debugging paper published on the Linux Journal and writes Linux Journal kernel news articles. She has presented at several Linux conferences and Linux Kernel Developer Keynote Panels. She served on the Linux Foundation Technical Advisory Board. Prior to joining Samsung, she worked as a kernel and software developer at HP and Lucent.