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