1The Kernel Address Sanitizer (KASAN)
2====================================
3
4Overview
5--------
6
7KernelAddressSANitizer (KASAN) is a dynamic memory error detector. It provides
8a fast and comprehensive solution for finding use-after-free and out-of-bounds
9bugs.
10
11KASAN uses compile-time instrumentation for checking every memory access,
12therefore you will need a GCC version 4.9.2 or later. GCC 5.0 or later is
13required for detection of out-of-bounds accesses to stack or global variables.
14
15Currently KASAN is supported only for the x86_64 and arm64 architectures.
16
17Usage
18-----
19
20To enable KASAN configure kernel with::
21
22	  CONFIG_KASAN = y
23
24and choose between CONFIG_KASAN_OUTLINE and CONFIG_KASAN_INLINE. Outline and
25inline are compiler instrumentation types. The former produces smaller binary
26the latter is 1.1 - 2 times faster. Inline instrumentation requires a GCC
27version 5.0 or later.
28
29KASAN works with both SLUB and SLAB memory allocators.
30For better bug detection and nicer reporting, enable CONFIG_STACKTRACE.
31
32To disable instrumentation for specific files or directories, add a line
33similar to the following to the respective kernel Makefile:
34
35- For a single file (e.g. main.o)::
36
37    KASAN_SANITIZE_main.o := n
38
39- For all files in one directory::
40
41    KASAN_SANITIZE := n
42
43Error reports
44~~~~~~~~~~~~~
45
46A typical out of bounds access report looks like this::
47
48    ==================================================================
49    BUG: AddressSanitizer: out of bounds access in kmalloc_oob_right+0x65/0x75 [test_kasan] at addr ffff8800693bc5d3
50    Write of size 1 by task modprobe/1689
51    =============================================================================
52    BUG kmalloc-128 (Not tainted): kasan error
53    -----------------------------------------------------------------------------
54
55    Disabling lock debugging due to kernel taint
56    INFO: Allocated in kmalloc_oob_right+0x3d/0x75 [test_kasan] age=0 cpu=0 pid=1689
57     __slab_alloc+0x4b4/0x4f0
58     kmem_cache_alloc_trace+0x10b/0x190
59     kmalloc_oob_right+0x3d/0x75 [test_kasan]
60     init_module+0x9/0x47 [test_kasan]
61     do_one_initcall+0x99/0x200
62     load_module+0x2cb3/0x3b20
63     SyS_finit_module+0x76/0x80
64     system_call_fastpath+0x12/0x17
65    INFO: Slab 0xffffea0001a4ef00 objects=17 used=7 fp=0xffff8800693bd728 flags=0x100000000004080
66    INFO: Object 0xffff8800693bc558 @offset=1368 fp=0xffff8800693bc720
67
68    Bytes b4 ffff8800693bc548: 00 00 00 00 00 00 00 00 5a 5a 5a 5a 5a 5a 5a 5a  ........ZZZZZZZZ
69    Object ffff8800693bc558: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
70    Object ffff8800693bc568: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
71    Object ffff8800693bc578: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
72    Object ffff8800693bc588: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
73    Object ffff8800693bc598: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
74    Object ffff8800693bc5a8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
75    Object ffff8800693bc5b8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b  kkkkkkkkkkkkkkkk
76    Object ffff8800693bc5c8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b a5  kkkkkkkkkkkkkkk.
77    Redzone ffff8800693bc5d8: cc cc cc cc cc cc cc cc                          ........
78    Padding ffff8800693bc718: 5a 5a 5a 5a 5a 5a 5a 5a                          ZZZZZZZZ
79    CPU: 0 PID: 1689 Comm: modprobe Tainted: G    B          3.18.0-rc1-mm1+ #98
80    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.7.5-0-ge51488c-20140602_164612-nilsson.home.kraxel.org 04/01/2014
81     ffff8800693bc000 0000000000000000 ffff8800693bc558 ffff88006923bb78
82     ffffffff81cc68ae 00000000000000f3 ffff88006d407600 ffff88006923bba8
83     ffffffff811fd848 ffff88006d407600 ffffea0001a4ef00 ffff8800693bc558
84    Call Trace:
85     [<ffffffff81cc68ae>] dump_stack+0x46/0x58
86     [<ffffffff811fd848>] print_trailer+0xf8/0x160
87     [<ffffffffa00026a7>] ? kmem_cache_oob+0xc3/0xc3 [test_kasan]
88     [<ffffffff811ff0f5>] object_err+0x35/0x40
89     [<ffffffffa0002065>] ? kmalloc_oob_right+0x65/0x75 [test_kasan]
90     [<ffffffff8120b9fa>] kasan_report_error+0x38a/0x3f0
91     [<ffffffff8120a79f>] ? kasan_poison_shadow+0x2f/0x40
92     [<ffffffff8120b344>] ? kasan_unpoison_shadow+0x14/0x40
93     [<ffffffff8120a79f>] ? kasan_poison_shadow+0x2f/0x40
94     [<ffffffffa00026a7>] ? kmem_cache_oob+0xc3/0xc3 [test_kasan]
95     [<ffffffff8120a995>] __asan_store1+0x75/0xb0
96     [<ffffffffa0002601>] ? kmem_cache_oob+0x1d/0xc3 [test_kasan]
97     [<ffffffffa0002065>] ? kmalloc_oob_right+0x65/0x75 [test_kasan]
98     [<ffffffffa0002065>] kmalloc_oob_right+0x65/0x75 [test_kasan]
99     [<ffffffffa00026b0>] init_module+0x9/0x47 [test_kasan]
100     [<ffffffff810002d9>] do_one_initcall+0x99/0x200
101     [<ffffffff811e4e5c>] ? __vunmap+0xec/0x160
102     [<ffffffff81114f63>] load_module+0x2cb3/0x3b20
103     [<ffffffff8110fd70>] ? m_show+0x240/0x240
104     [<ffffffff81115f06>] SyS_finit_module+0x76/0x80
105     [<ffffffff81cd3129>] system_call_fastpath+0x12/0x17
106    Memory state around the buggy address:
107     ffff8800693bc300: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
108     ffff8800693bc380: fc fc 00 00 00 00 00 00 00 00 00 00 00 00 00 fc
109     ffff8800693bc400: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
110     ffff8800693bc480: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
111     ffff8800693bc500: fc fc fc fc fc fc fc fc fc fc fc 00 00 00 00 00
112    >ffff8800693bc580: 00 00 00 00 00 00 00 00 00 00 03 fc fc fc fc fc
113                                                 ^
114     ffff8800693bc600: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
115     ffff8800693bc680: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
116     ffff8800693bc700: fc fc fc fc fb fb fb fb fb fb fb fb fb fb fb fb
117     ffff8800693bc780: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
118     ffff8800693bc800: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
119    ==================================================================
120
121The header of the report discribe what kind of bug happened and what kind of
122access caused it. It's followed by the description of the accessed slub object
123(see 'SLUB Debug output' section in Documentation/vm/slub.txt for details) and
124the description of the accessed memory page.
125
126In the last section the report shows memory state around the accessed address.
127Reading this part requires some understanding of how KASAN works.
128
129The state of each 8 aligned bytes of memory is encoded in one shadow byte.
130Those 8 bytes can be accessible, partially accessible, freed or be a redzone.
131We use the following encoding for each shadow byte: 0 means that all 8 bytes
132of the corresponding memory region are accessible; number N (1 <= N <= 7) means
133that the first N bytes are accessible, and other (8 - N) bytes are not;
134any negative value indicates that the entire 8-byte word is inaccessible.
135We use different negative values to distinguish between different kinds of
136inaccessible memory like redzones or freed memory (see mm/kasan/kasan.h).
137
138In the report above the arrows point to the shadow byte 03, which means that
139the accessed address is partially accessible.
140
141
142Implementation details
143----------------------
144
145From a high level, our approach to memory error detection is similar to that
146of kmemcheck: use shadow memory to record whether each byte of memory is safe
147to access, and use compile-time instrumentation to check shadow memory on each
148memory access.
149
150AddressSanitizer dedicates 1/8 of kernel memory to its shadow memory
151(e.g. 16TB to cover 128TB on x86_64) and uses direct mapping with a scale and
152offset to translate a memory address to its corresponding shadow address.
153
154Here is the function which translates an address to its corresponding shadow
155address::
156
157    static inline void *kasan_mem_to_shadow(const void *addr)
158    {
159	return ((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT)
160		+ KASAN_SHADOW_OFFSET;
161    }
162
163where ``KASAN_SHADOW_SCALE_SHIFT = 3``.
164
165Compile-time instrumentation used for checking memory accesses. Compiler inserts
166function calls (__asan_load*(addr), __asan_store*(addr)) before each memory
167access of size 1, 2, 4, 8 or 16. These functions check whether memory access is
168valid or not by checking corresponding shadow memory.
169
170GCC 5.0 has possibility to perform inline instrumentation. Instead of making
171function calls GCC directly inserts the code to check the shadow memory.
172This option significantly enlarges kernel but it gives x1.1-x2 performance
173boost over outline instrumented kernel.
174