linux-kbuild.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC/PATCH RESEND -next 00/21] Address sanitizer for kernel (kasan) - dynamic memory error detector.
@ 2014-07-09 11:29 Andrey Ryabinin
  2014-07-09 11:29 ` [RFC/PATCH RESEND -next 01/21] Add kernel address sanitizer infrastructure Andrey Ryabinin
                   ` (26 more replies)
  0 siblings, 27 replies; 116+ messages in thread
From: Andrey Ryabinin @ 2014-07-09 11:29 UTC (permalink / raw)
  To: linux-kernel
  Cc: Dmitry Vyukov, Konstantin Serebryany, Alexey Preobrazhensky,
	Andrey Konovalov, Yuri Gribov, Konstantin Khlebnikov,
	Sasha Levin, Michal Marek, Russell King, Thomas Gleixner,
	Ingo Molnar, Christoph Lameter, Pekka Enberg, David Rientjes,
	Joonsoo Kim, Andrew Morton, linux-kbuild, linux-arm-kernel, x86,
	linux-mm, Andrey Ryabinin

Hi all.

(Sorry, I screwd up with CC list in previous mails, so I'm doing this resend).

This patch set introduces address sanitizer for linux kernel (kasan).
Address sanitizer is dynamic memory error detector. It detects:
 - Use after free bugs.
 - Out of bounds reads/writes in kmalloc

It is possible, but not implemented yet or not included into this patch series:
 - Global buffer overflow
 - Stack buffer overflow
 - Use after return

In this patches contains kasan for x86/x86_64/arm architectures, for buddy and SLUB allocator.

Patches are base on next-20140704 and also available in git:
	git://github.com/aryabinin/linux.git --branch=kasan/kasan_v1

The main idea was borrowed from https://code.google.com/p/address-sanitizer/wiki/AddressSanitizerForKernel.
The original implementation (only x88_64 and only for SLAB) by Andrey Konovalov could be
found here http://github.com/xairy/linux. Some of code in this patches was stolen from there.

To use this feature you need pretty fresh GCC (revision r211699 from 2014-06-16 or
above).

To enable kasan configure kernel with:
     CONFIG_KASAN = y
and
     CONFIG_KASAN_SANTIZE_ALL = y

Currently KASAN works only with SLUB allocator. It is highly recommended to run KASAN with
CONFIG_SLUB_DEBUG=y and use 'slub_debug=U' in boot cmdline to enable user tracking
(free and alloc stacktraces).

Basic concept of kasan:

The main idea of KASAN is to use shadow memory to record whether each byte of memory
is safe to access or not, and use compiler's instrumentation to check the shadow memory
on each memory access.

Address sanitizer dedicates 1/8 of the low memory to the shadow memory and uses direct
mapping with a scale and offset to translate a memory address to its corresponding
shadow address.

Here is function to translate address to corresponding shadow address:

     unsigned long kasan_mem_to_shadow(unsigned long addr)
     {
		return ((addr) >> KASAN_SHADOW_SCALE_SHIFT)
       	             + kasan_shadow_start - (PAGE_OFFSET >> KASAN_SHADOW_SCALE_SHIFT);
     }

where KASAN_SHADOW_SCALE_SHIFT = 3.

So for every 8 bytes of lowmemory there is one corresponding byte of shadow memory.
The following encoding used for each shadow byte: 0 means that all 8 bytes of the
corresponding memory region are valid for access; k (1 <= k <= 7) means that
the first k bytes are valid for access, and other (8 - k) bytes are not;
Any negative value indicates that the entire 8-bytes are unaccessible.
Different negative values used to distinguish between different kinds of
unaccessible memory (redzones, freed memory) (see mm/kasan/kasan.h).

To be able to detect accesses to bad memory we need a special compiler.
Such compiler inserts a specific 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 region is valid to access or not by checking
corresponding shadow memory. If access is not valid an error printed.


TODO:
 - Optimizations: __asan_load*/__asan_store* are called for every memory access, so it's
        important to make them as fast as possible.
        In this patch set introduced only reference design of memory checking algorithm. It's
        slow but very simple, so anyone could easily understand basic concept.
        In future versions I'll try bring optimized versions with some numbers.

 - It seems like guard page introduced in c0a32f (mm: more intensive memory corruption debugging)
       could be easily reused for kasan as well.

 - get rid of kasan_disable_local()/kasan_enable_local() functions. kasan_enable/kasan_disable are
       used in some rare cases when we need validly access poisoned areas. This functions might be a
       stopping gap for inline instrumentation (see below).

TODO probably not for these series:
 - Quarantine for slub. For more strong use after free detection we need to delay reusing of freed
      slabs. So we need a something similar to guard pages in buddy allocator. Such quarantine might
      be useful even without kasan.

 - Inline instrumentation. Inline instrumentation means that fast patch of __asan_load* __asan_store* calls
    will be implemented in compiler, and instead of inserting function calls compiler will actually insert
    this fast path. To be able to do this we need (at least):
       a) get rid of kasan_disable()/kasan_enable() (see above)
       b) get rid of kasan_initialized flag. The main reason why we have this flag now is because we don't
       	  have any shadow on early stages of boot.

	  Konstantin Khlebnikov suggested a way to solve this issue:
               We could reserve virtual address space for shadow and map pages on very early stage of
               boot process (for x86_64 I think it should be done somewhere in x86_64_start_kernel).
               So we will have shadow all the time an flag kasan_initialized will no longer required.

 - Stack instrumentation (currently doesn't supported in mainline GCC though it is possible)
 - Global variables instrumentation
 - Use after return



[1] https://code.google.com/p/address-sanitizer/wiki/AddressSanitizerForKernel

List of already fixed bugs found by address sanitizer:

aab515d (fib_trie: remove potential out of bound access)
984f173 ([SCSI] sd: Fix potential out-of-bounds access)
5e9ae2e (aio: fix use-after-free in aio_migratepage)
2811eba (ipv6: udp packets following an UFO enqueued packet need also be handled by UFO)
057db84 (tracing: Fix potential out-of-bounds in trace_get_user())
9709674 (ipv4: fix a race in ip4_datagram_release_cb())
4e8d213 (ext4: fix use-after-free in ext4_mb_new_blocks)
624483f (mm: rmap: fix use-after-free in __put_anon_vma)

Cc: Dmitry Vyukov <dvyukov@google.com>
Cc: Konstantin Serebryany <kcc@google.com>
Cc: Alexey Preobrazhensky <preobr@google.com>
Cc: Andrey Konovalov <adech.fo@gmail.com>
Cc: Yuri Gribov <tetra2005@gmail.com>
Cc: Konstantin Khlebnikov <koct9i@gmail.com>
Cc: Sasha Levin <sasha.levin@oracle.com>
Cc: Michal Marek <mmarek@suse.cz>
Cc: Russell King <linux@arm.linux.org.uk>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Christoph Lameter <cl@linux.com>
Cc: Pekka Enberg <penberg@kernel.org>
Cc: David Rientjes <rientjes@google.com>
Cc: Joonsoo Kim <iamjoonsoo.kim@lge.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: <linux-kbuild@vger.kernel.org>
Cc: <linux-arm-kernel@lists.infradead.org>
Cc: <x86@kernel.org>
Cc: <linux-mm@kvack.org>

Andrey Ryabinin (21):
  Add kernel address sanitizer infrastructure.
  init: main: initialize kasan's shadow area on boot
  x86: add kasan hooks fort memcpy/memmove/memset functions
  x86: boot: vdso: disable instrumentation for code not linked with
    kernel
  x86: cpu: don't sanitize early stages of a secondary CPU boot
  x86: mm: init: allocate shadow memory for kasan
  x86: Kconfig: enable kernel address sanitizer
  mm: page_alloc: add kasan hooks on alloc and free pathes
  mm: Makefile: kasan: don't instrument slub.c and slab_common.c files
  mm: slab: share virt_to_cache() between slab and slub
  mm: slub: share slab_err and object_err functions
  mm: util: move krealloc/kzfree to slab_common.c
  mm: slub: add allocation size field to struct kmem_cache
  mm: slub: kasan: disable kasan when touching unaccessible memory
  mm: slub: add kernel address sanitizer hooks to slub allocator
  arm: boot: compressed: disable kasan's instrumentation
  arm: add kasan hooks fort memcpy/memmove/memset functions
  arm: mm: reserve shadow memory for kasan
  arm: Kconfig: enable kernel address sanitizer
  fs: dcache: manually unpoison dname after allocation to shut up
    kasan's reports
  lib: add kmalloc_bug_test module

 Documentation/kasan.txt           | 224 ++++++++++++++++++++
 Makefile                          |   8 +-
 arch/arm/Kconfig                  |   1 +
 arch/arm/boot/compressed/Makefile |   2 +
 arch/arm/include/asm/string.h     |  30 +++
 arch/arm/mm/init.c                |   3 +
 arch/x86/Kconfig                  |   1 +
 arch/x86/boot/Makefile            |   2 +
 arch/x86/boot/compressed/Makefile |   2 +
 arch/x86/include/asm/string_32.h  |  28 +++
 arch/x86/include/asm/string_64.h  |  24 +++
 arch/x86/kernel/cpu/Makefile      |   3 +
 arch/x86/lib/Makefile             |   2 +
 arch/x86/mm/init.c                |   3 +
 arch/x86/realmode/Makefile        |   2 +-
 arch/x86/realmode/rm/Makefile     |   1 +
 arch/x86/vdso/Makefile            |   1 +
 commit                            |   3 +
 fs/dcache.c                       |   3 +
 include/linux/kasan.h             |  61 ++++++
 include/linux/sched.h             |   4 +
 include/linux/slab.h              |  19 +-
 include/linux/slub_def.h          |   5 +
 init/main.c                       |   3 +-
 lib/Kconfig.debug                 |  10 +
 lib/Kconfig.kasan                 |  22 ++
 lib/Makefile                      |   1 +
 lib/test_kmalloc_bugs.c           | 254 +++++++++++++++++++++++
 mm/Makefile                       |   5 +
 mm/kasan/Makefile                 |   3 +
 mm/kasan/kasan.c                  | 420 ++++++++++++++++++++++++++++++++++++++
 mm/kasan/kasan.h                  |  42 ++++
 mm/kasan/report.c                 | 187 +++++++++++++++++
 mm/page_alloc.c                   |   4 +
 mm/slab.c                         |   6 -
 mm/slab.h                         |  25 ++-
 mm/slab_common.c                  |  96 +++++++++
 mm/slub.c                         |  50 ++++-
 mm/util.c                         |  91 ---------
 scripts/Makefile.lib              |  10 +
 40 files changed, 1550 insertions(+), 111 deletions(-)
 create mode 100644 Documentation/kasan.txt
 create mode 100644 commit
 create mode 100644 include/linux/kasan.h
 create mode 100644 lib/Kconfig.kasan
 create mode 100644 lib/test_kmalloc_bugs.c
 create mode 100644 mm/kasan/Makefile
 create mode 100644 mm/kasan/kasan.c
 create mode 100644 mm/kasan/kasan.h
 create mode 100644 mm/kasan/report.c

-- 
1.8.5.5


^ permalink raw reply	[flat|nested] 116+ messages in thread

end of thread, other threads:[~2015-02-16 23:56 UTC | newest]

Thread overview: 116+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-07-09 11:29 [RFC/PATCH RESEND -next 00/21] Address sanitizer for kernel (kasan) - dynamic memory error detector Andrey Ryabinin
2014-07-09 11:29 ` [RFC/PATCH RESEND -next 01/21] Add kernel address sanitizer infrastructure Andrey Ryabinin
2014-07-09 14:26   ` Christoph Lameter
2014-07-10  7:31     ` Andrey Ryabinin
2014-07-09 19:29   ` Andi Kleen
2014-07-09 20:40     ` Yuri Gribov
2014-07-10 12:10     ` Andrey Ryabinin
2014-07-09 20:26   ` Dave Hansen
2014-07-10 12:12     ` Andrey Ryabinin
2014-07-10 15:55       ` Dave Hansen
2014-07-10 19:48         ` Andrey Ryabinin
2014-07-10 20:04           ` Dave Hansen
2014-07-09 20:37   ` Dave Hansen
2014-07-09 20:38   ` Dave Hansen
2014-07-10 11:55   ` Sasha Levin
2014-07-10 13:01     ` Andrey Ryabinin
2014-07-10 13:31       ` Sasha Levin
2014-07-10 13:39         ` Andrey Ryabinin
2014-07-10 14:02           ` Sasha Levin
2014-07-10 19:04             ` Andrey Ryabinin
2014-07-10 13:50         ` Andrey Ryabinin
2014-07-09 11:29 ` [RFC/PATCH RESEND -next 02/21] init: main: initialize kasan's shadow area on boot Andrey Ryabinin
2014-07-09 11:29 ` [RFC/PATCH RESEND -next 03/21] x86: add kasan hooks fort memcpy/memmove/memset functions Andrey Ryabinin
2014-07-09 19:31   ` Andi Kleen
2014-07-10 13:54     ` Andrey Ryabinin
2014-07-09 11:29 ` [RFC/PATCH RESEND -next 04/21] x86: boot: vdso: disable instrumentation for code not linked with kernel Andrey Ryabinin
2014-07-09 11:29 ` [RFC/PATCH RESEND -next 05/21] x86: cpu: don't sanitize early stages of a secondary CPU boot Andrey Ryabinin
2014-07-09 19:33   ` Andi Kleen
2014-07-10 13:15     ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 06/21] x86: mm: init: allocate shadow memory for kasan Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 07/21] x86: Kconfig: enable kernel address sanitizer Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 08/21] mm: page_alloc: add kasan hooks on alloc and free pathes Andrey Ryabinin
2014-07-15  5:52   ` Joonsoo Kim
2014-07-15  6:54     ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 09/21] mm: Makefile: kasan: don't instrument slub.c and slab_common.c files Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 10/21] mm: slab: share virt_to_cache() between slab and slub Andrey Ryabinin
2014-07-15  5:53   ` Joonsoo Kim
2014-07-15  6:56     ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 11/21] mm: slub: share slab_err and object_err functions Andrey Ryabinin
2014-07-09 14:29   ` Christoph Lameter
2014-07-10  7:41     ` Andrey Ryabinin
2014-07-10 14:07       ` Christoph Lameter
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 12/21] mm: util: move krealloc/kzfree to slab_common.c Andrey Ryabinin
2014-07-09 14:32   ` Christoph Lameter
2014-07-10  7:43     ` Andrey Ryabinin
2014-07-10 14:08       ` Christoph Lameter
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 13/21] mm: slub: add allocation size field to struct kmem_cache Andrey Ryabinin
2014-07-09 14:33   ` Christoph Lameter
2014-07-10  8:44     ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 14/21] mm: slub: kasan: disable kasan when touching unaccessible memory Andrey Ryabinin
2014-07-15  6:04   ` Joonsoo Kim
2014-07-15  7:37     ` Andrey Ryabinin
2014-07-15  8:18       ` Joonsoo Kim
2014-07-15  9:51         ` Andrey Ryabinin
2014-07-15 14:26         ` Christoph Lameter
2014-07-15 15:02           ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 15/21] mm: slub: add kernel address sanitizer hooks to slub allocator Andrey Ryabinin
2014-07-09 14:48   ` Christoph Lameter
2014-07-10  9:24     ` Andrey Ryabinin
2014-07-15  6:09   ` Joonsoo Kim
2014-07-15  7:45     ` Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 16/21] arm: boot: compressed: disable kasan's instrumentation Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 17/21] arm: add kasan hooks fort memcpy/memmove/memset functions Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 18/21] arm: mm: reserve shadow memory for kasan Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 19/21] arm: Kconfig: enable kernel address sanitizer Andrey Ryabinin
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 20/21] fs: dcache: manually unpoison dname after allocation to shut up kasan's reports Andrey Ryabinin
2014-07-15  6:12   ` Joonsoo Kim
2014-07-15  6:08     ` Dmitry Vyukov
2014-07-15  9:34     ` Andrey Ryabinin
2014-07-15  9:45       ` Dmitry Vyukov
2014-07-09 11:30 ` [RFC/PATCH RESEND -next 21/21] lib: add kmalloc_bug_test module Andrey Ryabinin
2014-07-09 21:19 ` [RFC/PATCH RESEND -next 00/21] Address sanitizer for kernel (kasan) - dynamic memory error detector Dave Hansen
2014-07-09 21:44   ` Andi Kleen
2014-07-09 21:59     ` Vegard Nossum
2014-07-09 23:33       ` Dave Hansen
2014-07-10  0:03       ` Andi Kleen
2014-07-10 13:59       ` Andrey Ryabinin
2014-09-10 14:31 ` [RFC/PATCH v2 00/10] Kernel address sainitzer (KASan) - dynamic memory error deetector Andrey Ryabinin
2014-09-10 15:01   ` Dave Hansen
2014-09-10 14:58     ` Andrey Ryabinin
2014-09-10 15:12   ` Sasha Levin
2014-09-24 12:43 ` [PATCH v3 00/13] Kernel address sanitizer - runtime memory debugger Andrey Ryabinin
2014-09-24 15:11   ` Andrew Morton
2014-09-26 17:01   ` Sasha Levin
2014-09-26 17:07     ` Dmitry Vyukov
2014-09-26 17:22       ` Andrey Ryabinin
2014-09-26 17:29         ` Dmitry Vyukov
2014-09-26 18:48           ` Yuri Gribov
2014-09-29 14:22             ` Dmitry Vyukov
2014-09-29 14:36               ` Peter Zijlstra
2014-09-29 14:48                 ` Dmitry Vyukov
2014-09-26 17:17     ` Andrey Ryabinin
2014-10-16 17:18   ` Yuri Gribov
     [not found] ` <1421859105-25253-1-git-send-email-a.ryabinin@samsung.com>
2015-01-21 16:51   ` [PATCH v9 01/17] Add kernel address sanitizer infrastructure Andrey Ryabinin
     [not found]     ` <54C23FFB.5010800@suse.cz>
2015-01-23 12:48       ` Andrey Ryabinin
2015-01-21 16:51   ` [PATCH v9 12/17] kasan: enable stack instrumentation Andrey Ryabinin
2015-01-21 16:51   ` [PATCH v9 17/17] kasan: enable instrumentation of global variables Andrey Ryabinin
     [not found] ` <1422544321-24232-1-git-send-email-a.ryabinin@samsung.com>
2015-01-29 15:11   ` [PATCH v10 01/17] Add kernel address sanitizer infrastructure Andrey Ryabinin
2015-01-29 23:12     ` Andrew Morton
2015-01-30 16:04       ` Andrey Ryabinin
2015-01-29 15:11   ` [PATCH v10 12/17] kasan: enable stack instrumentation Andrey Ryabinin
2015-01-29 15:12   ` [PATCH v10 17/17] kasan: enable instrumentation of global variables Andrey Ryabinin
2015-01-29 23:13     ` Andrew Morton
2015-01-30 17:47       ` Andrey Ryabinin
2015-01-30 21:45         ` Andrew Morton
2015-01-30 23:18           ` Andrey Ryabinin
     [not found] ` <1422985392-28652-1-git-send-email-a.ryabinin@samsung.com>
2015-02-03 17:42   ` [PATCH v11 02/19] Add kernel address sanitizer infrastructure Andrey Ryabinin
2015-02-03 23:04     ` Andrew Morton
2015-02-04  4:00       ` Andrey Konovalov
2015-02-03 17:43   ` [PATCH v11 14/19] kasan: enable stack instrumentation Andrey Ryabinin
2015-02-03 17:43   ` [PATCH v11 19/19] kasan: enable instrumentation of global variables Andrey Ryabinin
2015-02-16  2:58     ` Rusty Russell
2015-02-16 14:44       ` Andrey Ryabinin
2015-02-16 14:47         ` Dmitry Vyukov
2015-02-16 15:09           ` Andrey Ryabinin
2015-02-16 23:55         ` Rusty Russell

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).