From patchwork Mon Aug 8 23:34:58 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Corbet X-Patchwork-Id: 73492 Delivered-To: patch@linaro.org Received: by 10.140.29.52 with SMTP id a49csp210273qga; Mon, 8 Aug 2016 16:36:52 -0700 (PDT) X-Received: by 10.98.135.13 with SMTP id i13mr167218952pfe.44.1470699412167; Mon, 08 Aug 2016 16:36:52 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id g4si39333939pax.227.2016.08.08.16.36.51; Mon, 08 Aug 2016 16:36:52 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752625AbcHHXgn (ORCPT + 27 others); Mon, 8 Aug 2016 19:36:43 -0400 Received: from tex.lwn.net ([70.33.254.29]:44614 "EHLO vena.lwn.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752246AbcHHXf1 (ORCPT ); Mon, 8 Aug 2016 19:35:27 -0400 Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by vena.lwn.net (Postfix) with ESMTP id 963EE154004A; Mon, 8 Aug 2016 17:35:25 -0600 (MDT) From: Jonathan Corbet To: linux-doc@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Jani Nikula , Jonathan Corbet , Andrey Ryabinin , Alexander Potapenko , Dmitry Vyukov Subject: [PATCH 06/10] docs: sphinxify kasan.txt and move to dev-tools Date: Mon, 8 Aug 2016 17:34:58 -0600 Message-Id: <20160808233502.16950-7-corbet@lwn.net> X-Mailer: git-send-email 2.9.2 In-Reply-To: <20160808233502.16950-1-corbet@lwn.net> References: <20160808233502.16950-1-corbet@lwn.net> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org No textual changes beyond formatting. Cc: Andrey Ryabinin Cc: Alexander Potapenko Cc: Dmitry Vyukov Signed-off-by: Jonathan Corbet --- Documentation/dev-tools/kasan.rst | 173 ++++++++++++++++++++++++++++++++++++++ Documentation/dev-tools/tools.rst | 1 + Documentation/kasan.txt | 171 ------------------------------------- MAINTAINERS | 2 +- 4 files changed, 175 insertions(+), 172 deletions(-) create mode 100644 Documentation/dev-tools/kasan.rst delete mode 100644 Documentation/kasan.txt -- 2.9.2 diff --git a/Documentation/dev-tools/kasan.rst b/Documentation/dev-tools/kasan.rst new file mode 100644 index 0000000..948d243 --- /dev/null +++ b/Documentation/dev-tools/kasan.rst @@ -0,0 +1,173 @@ +The Kernel Address Sanitizer (KASAN) +==================================== + +Overview +-------- + +KernelAddressSANitizer (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 for checking every memory access, +therefore you will need a GCC version 4.9.2 or later. GCC 5.0 or later is +required for detection of out-of-bounds accesses to stack or global variables. + +Currently KASAN is supported only for x86_64 architecture. + +Usage +----- + +To enable KASAN configure kernel with:: + + CONFIG_KASAN = y + +and choose between CONFIG_KASAN_OUTLINE and CONFIG_KASAN_INLINE. Outline and +inline are compiler instrumentation types. The former produces smaller binary +the latter is 1.1 - 2 times faster. Inline instrumentation requires a GCC +version 5.0 or later. + +KASAN works with both SLUB and SLAB memory allocators. +For better bug detection and nicer reporting, enable CONFIG_STACKTRACE. + +To disable instrumentation for specific files or directories, add a line +similar to the following to the respective kernel Makefile: + +- For a single file (e.g. main.o):: + + KASAN_SANITIZE_main.o := n + +- For all files in one directory:: + + KASAN_SANITIZE := n + +Error reports +~~~~~~~~~~~~~ + +A typical out of bounds access report looks like this:: + + ================================================================== + BUG: AddressSanitizer: out of bounds access in kmalloc_oob_right+0x65/0x75 [test_kasan] at addr ffff8800693bc5d3 + Write of size 1 by task modprobe/1689 + ============================================================================= + BUG kmalloc-128 (Not tainted): kasan error + ----------------------------------------------------------------------------- + + Disabling lock debugging due to kernel taint + INFO: Allocated in kmalloc_oob_right+0x3d/0x75 [test_kasan] age=0 cpu=0 pid=1689 + __slab_alloc+0x4b4/0x4f0 + kmem_cache_alloc_trace+0x10b/0x190 + kmalloc_oob_right+0x3d/0x75 [test_kasan] + init_module+0x9/0x47 [test_kasan] + do_one_initcall+0x99/0x200 + load_module+0x2cb3/0x3b20 + SyS_finit_module+0x76/0x80 + system_call_fastpath+0x12/0x17 + INFO: Slab 0xffffea0001a4ef00 objects=17 used=7 fp=0xffff8800693bd728 flags=0x100000000004080 + INFO: Object 0xffff8800693bc558 @offset=1368 fp=0xffff8800693bc720 + + Bytes b4 ffff8800693bc548: 00 00 00 00 00 00 00 00 5a 5a 5a 5a 5a 5a 5a 5a ........ZZZZZZZZ + Object ffff8800693bc558: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc568: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc578: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc588: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc598: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc5a8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc5b8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk + Object ffff8800693bc5c8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b a5 kkkkkkkkkkkkkkk. + Redzone ffff8800693bc5d8: cc cc cc cc cc cc cc cc ........ + Padding ffff8800693bc718: 5a 5a 5a 5a 5a 5a 5a 5a ZZZZZZZZ + CPU: 0 PID: 1689 Comm: modprobe Tainted: G B 3.18.0-rc1-mm1+ #98 + Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.7.5-0-ge51488c-20140602_164612-nilsson.home.kraxel.org 04/01/2014 + ffff8800693bc000 0000000000000000 ffff8800693bc558 ffff88006923bb78 + ffffffff81cc68ae 00000000000000f3 ffff88006d407600 ffff88006923bba8 + ffffffff811fd848 ffff88006d407600 ffffea0001a4ef00 ffff8800693bc558 + Call Trace: + [] dump_stack+0x46/0x58 + [] print_trailer+0xf8/0x160 + [] ? kmem_cache_oob+0xc3/0xc3 [test_kasan] + [] object_err+0x35/0x40 + [] ? kmalloc_oob_right+0x65/0x75 [test_kasan] + [] kasan_report_error+0x38a/0x3f0 + [] ? kasan_poison_shadow+0x2f/0x40 + [] ? kasan_unpoison_shadow+0x14/0x40 + [] ? kasan_poison_shadow+0x2f/0x40 + [] ? kmem_cache_oob+0xc3/0xc3 [test_kasan] + [] __asan_store1+0x75/0xb0 + [] ? kmem_cache_oob+0x1d/0xc3 [test_kasan] + [] ? kmalloc_oob_right+0x65/0x75 [test_kasan] + [] kmalloc_oob_right+0x65/0x75 [test_kasan] + [] init_module+0x9/0x47 [test_kasan] + [] do_one_initcall+0x99/0x200 + [] ? __vunmap+0xec/0x160 + [] load_module+0x2cb3/0x3b20 + [] ? m_show+0x240/0x240 + [] SyS_finit_module+0x76/0x80 + [] system_call_fastpath+0x12/0x17 + Memory state around the buggy address: + ffff8800693bc300: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc + ffff8800693bc380: fc fc 00 00 00 00 00 00 00 00 00 00 00 00 00 fc + ffff8800693bc400: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc + ffff8800693bc480: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc + ffff8800693bc500: fc fc fc fc fc fc fc fc fc fc fc 00 00 00 00 00 + >ffff8800693bc580: 00 00 00 00 00 00 00 00 00 00 03 fc fc fc fc fc + ^ + ffff8800693bc600: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc + ffff8800693bc680: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc + ffff8800693bc700: fc fc fc fc fb fb fb fb fb fb fb fb fb fb fb fb + ffff8800693bc780: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb + ffff8800693bc800: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb + ================================================================== + +The header of the report discribe what kind of bug happened and what kind of +access caused it. It's followed by the description of the accessed slub object +(see 'SLUB Debug output' section in Documentation/vm/slub.txt for details) and +the description of the accessed memory page. + +In the last section the report shows memory state around the accessed address. +Reading this part requires some understanding of how KASAN works. + +The state of each 8 aligned bytes of memory is encoded in one shadow byte. +Those 8 bytes can be accessible, partially accessible, freed or be a redzone. +We use the following encoding for each shadow byte: 0 means that all 8 bytes +of the corresponding memory region are accessible; number N (1 <= N <= 7) means +that the first N bytes are accessible, and other (8 - N) bytes are not; +any negative value indicates that the entire 8-byte word is inaccessible. +We use different negative values to distinguish between different kinds of +inaccessible memory like redzones or freed memory (see mm/kasan/kasan.h). + +In the report above the arrows point to the shadow byte 03, which means that +the accessed address is partially accessible. + + +Implementation details +---------------------- + +From a high level, our approach to memory error detection is similar to that +of kmemcheck: use shadow memory to record whether each byte of memory is safe +to access, and use compile-time instrumentation to check shadow memory on each +memory access. + +AddressSanitizer dedicates 1/8 of kernel memory to its shadow memory +(e.g. 16TB to cover 128TB on x86_64) and uses direct mapping with a scale and +offset to translate a memory address to its corresponding shadow address. + +Here is the function which translates an address to its corresponding shadow +address:: + + static inline void *kasan_mem_to_shadow(const void *addr) + { + return ((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT) + + KASAN_SHADOW_OFFSET; + } + +where ``KASAN_SHADOW_SCALE_SHIFT = 3``. + +Compile-time instrumentation used for checking memory accesses. 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 access is +valid or not by checking corresponding shadow memory. + +GCC 5.0 has possibility to perform inline instrumentation. Instead of making +function calls GCC directly inserts the code to check the shadow memory. +This option significantly enlarges kernel but it gives x1.1-x2 performance +boost over outline instrumented kernel. diff --git a/Documentation/dev-tools/tools.rst b/Documentation/dev-tools/tools.rst index 404d044..0500e65 100644 --- a/Documentation/dev-tools/tools.rst +++ b/Documentation/dev-tools/tools.rst @@ -18,3 +18,4 @@ whole; patches welcome! sparse kcov gcov + kasan diff --git a/Documentation/kasan.txt b/Documentation/kasan.txt deleted file mode 100644 index 7dd95b3..0000000 --- a/Documentation/kasan.txt +++ /dev/null @@ -1,171 +0,0 @@ -KernelAddressSanitizer (KASAN) -============================== - -0. Overview -=========== - -KernelAddressSANitizer (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 for checking every memory access, -therefore you will need a GCC version 4.9.2 or later. GCC 5.0 or later is -required for detection of out-of-bounds accesses to stack or global variables. - -Currently KASAN is supported only for x86_64 architecture. - -1. Usage -======== - -To enable KASAN configure kernel with: - - CONFIG_KASAN = y - -and choose between CONFIG_KASAN_OUTLINE and CONFIG_KASAN_INLINE. Outline and -inline are compiler instrumentation types. The former produces smaller binary -the latter is 1.1 - 2 times faster. Inline instrumentation requires a GCC -version 5.0 or later. - -KASAN works with both SLUB and SLAB memory allocators. -For better bug detection and nicer reporting, enable CONFIG_STACKTRACE. - -To disable instrumentation for specific files or directories, add a line -similar to the following to the respective kernel Makefile: - - For a single file (e.g. main.o): - KASAN_SANITIZE_main.o := n - - For all files in one directory: - KASAN_SANITIZE := n - -1.1 Error reports -================= - -A typical out of bounds access report looks like this: - -================================================================== -BUG: AddressSanitizer: out of bounds access in kmalloc_oob_right+0x65/0x75 [test_kasan] at addr ffff8800693bc5d3 -Write of size 1 by task modprobe/1689 -============================================================================= -BUG kmalloc-128 (Not tainted): kasan error ------------------------------------------------------------------------------ - -Disabling lock debugging due to kernel taint -INFO: Allocated in kmalloc_oob_right+0x3d/0x75 [test_kasan] age=0 cpu=0 pid=1689 - __slab_alloc+0x4b4/0x4f0 - kmem_cache_alloc_trace+0x10b/0x190 - kmalloc_oob_right+0x3d/0x75 [test_kasan] - init_module+0x9/0x47 [test_kasan] - do_one_initcall+0x99/0x200 - load_module+0x2cb3/0x3b20 - SyS_finit_module+0x76/0x80 - system_call_fastpath+0x12/0x17 -INFO: Slab 0xffffea0001a4ef00 objects=17 used=7 fp=0xffff8800693bd728 flags=0x100000000004080 -INFO: Object 0xffff8800693bc558 @offset=1368 fp=0xffff8800693bc720 - -Bytes b4 ffff8800693bc548: 00 00 00 00 00 00 00 00 5a 5a 5a 5a 5a 5a 5a 5a ........ZZZZZZZZ -Object ffff8800693bc558: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc568: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc578: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc588: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc598: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc5a8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc5b8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b kkkkkkkkkkkkkkkk -Object ffff8800693bc5c8: 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b 6b a5 kkkkkkkkkkkkkkk. -Redzone ffff8800693bc5d8: cc cc cc cc cc cc cc cc ........ -Padding ffff8800693bc718: 5a 5a 5a 5a 5a 5a 5a 5a ZZZZZZZZ -CPU: 0 PID: 1689 Comm: modprobe Tainted: G B 3.18.0-rc1-mm1+ #98 -Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.7.5-0-ge51488c-20140602_164612-nilsson.home.kraxel.org 04/01/2014 - ffff8800693bc000 0000000000000000 ffff8800693bc558 ffff88006923bb78 - ffffffff81cc68ae 00000000000000f3 ffff88006d407600 ffff88006923bba8 - ffffffff811fd848 ffff88006d407600 ffffea0001a4ef00 ffff8800693bc558 -Call Trace: - [] dump_stack+0x46/0x58 - [] print_trailer+0xf8/0x160 - [] ? kmem_cache_oob+0xc3/0xc3 [test_kasan] - [] object_err+0x35/0x40 - [] ? kmalloc_oob_right+0x65/0x75 [test_kasan] - [] kasan_report_error+0x38a/0x3f0 - [] ? kasan_poison_shadow+0x2f/0x40 - [] ? kasan_unpoison_shadow+0x14/0x40 - [] ? kasan_poison_shadow+0x2f/0x40 - [] ? kmem_cache_oob+0xc3/0xc3 [test_kasan] - [] __asan_store1+0x75/0xb0 - [] ? kmem_cache_oob+0x1d/0xc3 [test_kasan] - [] ? kmalloc_oob_right+0x65/0x75 [test_kasan] - [] kmalloc_oob_right+0x65/0x75 [test_kasan] - [] init_module+0x9/0x47 [test_kasan] - [] do_one_initcall+0x99/0x200 - [] ? __vunmap+0xec/0x160 - [] load_module+0x2cb3/0x3b20 - [] ? m_show+0x240/0x240 - [] SyS_finit_module+0x76/0x80 - [] system_call_fastpath+0x12/0x17 -Memory state around the buggy address: - ffff8800693bc300: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc - ffff8800693bc380: fc fc 00 00 00 00 00 00 00 00 00 00 00 00 00 fc - ffff8800693bc400: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc - ffff8800693bc480: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc - ffff8800693bc500: fc fc fc fc fc fc fc fc fc fc fc 00 00 00 00 00 ->ffff8800693bc580: 00 00 00 00 00 00 00 00 00 00 03 fc fc fc fc fc - ^ - ffff8800693bc600: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc - ffff8800693bc680: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc - ffff8800693bc700: fc fc fc fc fb fb fb fb fb fb fb fb fb fb fb fb - ffff8800693bc780: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb - ffff8800693bc800: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb -================================================================== - -The header of the report discribe what kind of bug happened and what kind of -access caused it. It's followed by the description of the accessed slub object -(see 'SLUB Debug output' section in Documentation/vm/slub.txt for details) and -the description of the accessed memory page. - -In the last section the report shows memory state around the accessed address. -Reading this part requires some understanding of how KASAN works. - -The state of each 8 aligned bytes of memory is encoded in one shadow byte. -Those 8 bytes can be accessible, partially accessible, freed or be a redzone. -We use the following encoding for each shadow byte: 0 means that all 8 bytes -of the corresponding memory region are accessible; number N (1 <= N <= 7) means -that the first N bytes are accessible, and other (8 - N) bytes are not; -any negative value indicates that the entire 8-byte word is inaccessible. -We use different negative values to distinguish between different kinds of -inaccessible memory like redzones or freed memory (see mm/kasan/kasan.h). - -In the report above the arrows point to the shadow byte 03, which means that -the accessed address is partially accessible. - - -2. Implementation details -========================= - -From a high level, our approach to memory error detection is similar to that -of kmemcheck: use shadow memory to record whether each byte of memory is safe -to access, and use compile-time instrumentation to check shadow memory on each -memory access. - -AddressSanitizer dedicates 1/8 of kernel memory to its shadow memory -(e.g. 16TB to cover 128TB on x86_64) and uses direct mapping with a scale and -offset to translate a memory address to its corresponding shadow address. - -Here is the function which translates an address to its corresponding shadow -address: - -static inline void *kasan_mem_to_shadow(const void *addr) -{ - return ((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT) - + KASAN_SHADOW_OFFSET; -} - -where KASAN_SHADOW_SCALE_SHIFT = 3. - -Compile-time instrumentation used for checking memory accesses. 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 access is -valid or not by checking corresponding shadow memory. - -GCC 5.0 has possibility to perform inline instrumentation. Instead of making -function calls GCC directly inserts the code to check the shadow memory. -This option significantly enlarges kernel but it gives x1.1-x2 performance -boost over outline instrumented kernel. diff --git a/MAINTAINERS b/MAINTAINERS index bb53779..2ffd7ed 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -6587,7 +6587,7 @@ L: kasan-dev@googlegroups.com S: Maintained F: arch/*/include/asm/kasan.h F: arch/*/mm/kasan_init* -F: Documentation/kasan.txt +F: Documentation/dev-tools/kasan.rst F: include/linux/kasan*.h F: lib/test_kasan.c F: mm/kasan/