• Dmitry Vyukov's avatar
    kernel: add kcov code coverage · 5c9a8750
    Dmitry Vyukov authored
    kcov provides code coverage collection for coverage-guided fuzzing
    (randomized testing).  Coverage-guided fuzzing is a testing technique
    that uses coverage feedback to determine new interesting inputs to a
    system.  A notable user-space example is AFL
    (http://lcamtuf.coredump.cx/afl/).  However, this technique is not
    widely used for kernel testing due to missing compiler and kernel
    support.
    
    kcov does not aim to collect as much coverage as possible.  It aims to
    collect more or less stable coverage that is function of syscall inputs.
    To achieve this goal it does not collect coverage in soft/hard
    interrupts and instrumentation of some inherently non-deterministic or
    non-interesting parts of kernel is disbled (e.g.  scheduler, locking).
    
    Currently there is a single coverage collection mode (tracing), but the
    API anticipates additional collection modes.  Initially I also
    implemented a second mode which exposes coverage in a fixed-size hash
    table of counters (what Quentin used in his original patch).  I've
    dropped the second mode for simplicity.
    
    This patch adds the necessary support on kernel side.  The complimentary
    compiler support was added in gcc revision 231296.
    
    We've used this support to build syzkaller system call fuzzer, which has
    found 90 kernel bugs in just 2 months:
    
      https://github.com/google/syzkaller/wiki/Found-Bugs
    
    We've also found 30+ bugs in our internal systems with syzkaller.
    Another (yet unexplored) direction where kcov coverage would greatly
    help is more traditional "blob mutation".  For example, mounting a
    random blob as a filesystem, or receiving a random blob over wire.
    
    Why not gcov.  Typical fuzzing loop looks as follows: (1) reset
    coverage, (2) execute a bit of code, (3) collect coverage, repeat.  A
    typical coverage can be just a dozen of basic blocks (e.g.  an invalid
    input).  In such context gcov becomes prohibitively expensive as
    reset/collect coverage steps depend on total number of basic
    blocks/edges in program (in case of kernel it is about 2M).  Cost of
    kcov depends only on number of executed basic blocks/edges.  On top of
    that, kernel requires per-thread coverage because there are always
    background threads and unrelated processes that also produce coverage.
    With inlined gcov instrumentation per-thread coverage is not possible.
    
    kcov exposes kernel PCs and control flow to user-space which is
    insecure.  But debugfs should not be mapped as user accessible.
    
    Based on a patch by Quentin Casasnovas.
    
    [akpm@linux-foundation.org: make task_struct.kcov_mode have type `enum kcov_mode']
    [akpm@linux-foundation.org: unbreak allmodconfig]
    [akpm@linux-foundation.org: follow x86 Makefile layout standards]
    Signed-off-by: default avatarDmitry Vyukov <dvyukov@google.com>
    Reviewed-by: default avatarKees Cook <keescook@chromium.org>
    Cc: syzkaller <syzkaller@googlegroups.com>
    Cc: Vegard Nossum <vegard.nossum@oracle.com>
    Cc: Catalin Marinas <catalin.marinas@arm.com>
    Cc: Tavis Ormandy <taviso@google.com>
    Cc: Will Deacon <will.deacon@arm.com>
    Cc: Quentin Casasnovas <quentin.casasnovas@oracle.com>
    Cc: Kostya Serebryany <kcc@google.com>
    Cc: Eric Dumazet <edumazet@google.com>
    Cc: Alexander Potapenko <glider@google.com>
    Cc: Kees Cook <keescook@google.com>
    Cc: Bjorn Helgaas <bhelgaas@google.com>
    Cc: Sasha Levin <sasha.levin@oracle.com>
    Cc: David Drysdale <drysdale@google.com>
    Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
    Cc: Andrey Ryabinin <ryabinin.a.a@gmail.com>
    Cc: Kirill A. Shutemov <kirill@shutemov.name>
    Cc: Jiri Slaby <jslaby@suse.cz>
    Cc: Ingo Molnar <mingo@elte.hu>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: "H. Peter Anvin" <hpa@zytor.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    5c9a8750
sched.h 92.2 KB