Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753734AbcKQHxF (ORCPT ); Thu, 17 Nov 2016 02:53:05 -0500 Received: from mail-qk0-f171.google.com ([209.85.220.171]:36555 "EHLO mail-qk0-f171.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751567AbcKQHxE (ORCPT ); Thu, 17 Nov 2016 02:53:04 -0500 MIME-Version: 1.0 In-Reply-To: <20161116212746.29047-3-quentin.casasnovas@oracle.com> References: <20161116212746.29047-1-quentin.casasnovas@oracle.com> <20161116212746.29047-3-quentin.casasnovas@oracle.com> From: Dmitry Vyukov Date: Thu, 17 Nov 2016 08:52:42 +0100 Message-ID: Subject: Re: [PATCH 2/2] kcov: add AFL-style tracing To: syzkaller Cc: LKML , Vegard Nossum , Michal Zalewski , Kees Cook , Quentin Casasnovas Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 8439 Lines: 220 On Wed, Nov 16, 2016 at 10:27 PM, Quentin Casasnovas wrote: > AFL uses a fixed-size buffer (typically 64 KiB) where each byte is > a counter representing how many times an A -> B branch was taken. > Of course, since the buffer is fixed size, it's a little imprecise > in that e.g. two different branches could map to the same counter, > but in practice it works well. > > See afl:docs/technical_details.txt for more information. > > Here is a small test program that demonstrates the new capability: > > #include > #include > #include > > #include > #include > #include > #include > #include > #include > > #include > > #define KCOV_INIT_TRACE _IOR('c', 1, unsigned long) > #define KCOV_INIT_TABLE _IOR('c', 2, unsigned long) > #define KCOV_ENABLE _IO('c', 100) > #define KCOV_DISABLE _IO('c', 101) > > int main(int argc, char *argv[]) > { > int fd = open("/sys/kernel/debug/kcov", O_RDWR); > if (fd == -1) > error(1, errno, "open()"); > > unsigned long size = 1 << 10; > if (ioctl(fd, KCOV_INIT_TABLE, size) != 0) > error(1, errno, "ioctl(KCOV_INIT_TABLE)"); > > void *mem = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); > if (mem == MAP_FAILED) > error(1, errno, "mmap()"); > > /* Start kernel instrumentation */ > if (ioctl(fd, KCOV_ENABLE, 0) != 0) > error(1, errno, "ioctl(KCOV_ENABLE)"); > > printf("Hello world!\n"); > > /* End kernel instrumentation*/ > if (ioctl(fd, KCOV_DISABLE, 0) != 0) > error(1, errno, "ioctl(KCOV_DISABLE)"); > > /* Hex dump of memory area */ > unsigned char *mem2 = mem; > for (unsigned int i = 0; i < size / sizeof(i); ++i) { > printf("%02x ", mem2[i]); > if (i % 32 == 31) > printf("\n"); > } > > close(fd); > return 0; > } > > This patch is a collaboration between Quentin Casasnovas and Vegard Nossum. > > v2: As per Dmitry's suggestions: > - Initialize location after barrier > - Avoid additional indirections in __sanitizer_cov_trace_pc > - Renamed KCOV_INIT_AFL/KCOV_MODE_AFL to KCOV_INIT_TABLE/KCOV_MODE_TABLE. > > Cc: Dmitry Vyukov > Cc: Michal Zalewski > Cc: Kees Cook > Signed-off-by: Quentin Casasnovas > Signed-off-by: Vegard Nossum > --- > include/linux/kcov.h | 6 ++++++ > include/linux/sched.h | 10 ++++++++-- > include/uapi/linux/kcov.h | 1 + > kernel/kcov.c | 37 ++++++++++++++++++++++++++++++++++++- > 4 files changed, 51 insertions(+), 3 deletions(-) > > diff --git a/include/linux/kcov.h b/include/linux/kcov.h > index 2883ac98c280..5450b8296113 100644 > --- a/include/linux/kcov.h > +++ b/include/linux/kcov.h > @@ -18,6 +18,12 @@ enum kcov_mode { > * Covered PCs are collected in a per-task buffer. > */ > KCOV_MODE_TRACE = 1, > + /* > + * AFL-style collection. > + * Covered branches are hashed and collected in a fixed size buffer > + * (see AFL documentation for more information). > + */ > + KCOV_MODE_TABLE = 2, > }; > > #else > diff --git a/include/linux/sched.h b/include/linux/sched.h > index 348f51b0ec92..31f1bde64961 100644 > --- a/include/linux/sched.h > +++ b/include/linux/sched.h > @@ -1919,8 +1919,14 @@ struct task_struct { > #ifdef CONFIG_KCOV > /* Coverage collection mode enabled for this task (0 if disabled). */ > enum kcov_mode kcov_mode; > - /* Size of the kcov_area. */ > - unsigned kcov_size; > + union { > + /* Size of the kcov_area. */ > + unsigned kcov_size; > + /* Mask to fit within kcov_area */ > + unsigned kcov_mask; > + }; > + /* Hash of previous branch taken, to differentiate A > B from B > A */ > + unsigned long kcov_prev_location; > /* Buffer for coverage collection. */ > void *kcov_area; > /* kcov desciptor wired with this task or NULL. */ > diff --git a/include/uapi/linux/kcov.h b/include/uapi/linux/kcov.h > index 574e22ec640d..19b8ff763243 100644 > --- a/include/uapi/linux/kcov.h > +++ b/include/uapi/linux/kcov.h > @@ -4,6 +4,7 @@ > #include > > #define KCOV_INIT_TRACE _IOR('c', 1, unsigned long) > +#define KCOV_INIT_TABLE _IOR('c', 2, unsigned long) > #define KCOV_ENABLE _IO('c', 100) > #define KCOV_DISABLE _IO('c', 101) > > diff --git a/kernel/kcov.c b/kernel/kcov.c > index c2aa93851f93..8056013df16b 100644 > --- a/kernel/kcov.c > +++ b/kernel/kcov.c > @@ -5,6 +5,7 @@ > #include > #include > #include > +#include > #include > #include > #include > @@ -83,6 +84,18 @@ void notrace __sanitizer_cov_trace_pc(void) > area[pos] = _RET_IP_; > WRITE_ONCE(area[0], pos); > } > + } else if (mode == KCOV_MODE_TABLE) { > + unsigned char *area; > + unsigned long location; > + > + /* See above */ > + barrier(); > + > + location = _RET_IP_; > + area = t->kcov_area; > + > + ++area[(t->kcov_prev_location ^ location) & t->kcov_mask]; > + t->kcov_prev_location = hash_long(location, BITS_PER_LONG); > } > } > EXPORT_SYMBOL(__sanitizer_cov_trace_pc); > @@ -106,6 +119,7 @@ void kcov_task_init(struct task_struct *t) > t->kcov_size = 0; > t->kcov_area = NULL; > t->kcov = NULL; > + t->kcov_prev_location = hash_long(0, BITS_PER_LONG); > } > > void kcov_task_exit(struct task_struct *t) > @@ -205,6 +219,23 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd, > kcov->size = size * sizeof(unsigned long); > kcov->mode = KCOV_MODE_TRACE; > return 0; > + case KCOV_INIT_TABLE: > + size = arg; > + > + if (kcov->mode != KCOV_MODE_DISABLED) > + return -EBUSY; > + > + /* > + * We infer the index in the table buffer from the return > + * address of the caller and need a fast way to mask the > + * relevant bits. > + */ > + if (!is_power_of_2(size)) > + return -EINVAL; > + > + kcov->size = size; > + kcov->mode = KCOV_MODE_TABLE; > + return 0; > case KCOV_ENABLE: > /* > * Enable coverage for the current task. > @@ -221,8 +252,12 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd, > return -EBUSY; > t = current; > /* Cache in task struct for performance. */ > - t->kcov_size = kcov->size / sizeof(unsigned long); > + if (kcov->mode == KCOV_MODE_TRACE) > + t->kcov_size = kcov->size / sizeof(unsigned long); > + else if (kcov->mode == KCOV_MODE_TABLE) > + t->kcov_mask = kcov->size - 1; > t->kcov_area = kcov->area; > + t->kcov_prev_location = hash_long(0, BITS_PER_LONG); > /* See comment in __sanitizer_cov_trace_pc(). */ > barrier(); > WRITE_ONCE(t->kcov_mode, kcov->mode); > -- Thanks! Reviewed-and-tested-by: Dmitry Vyukov I've tested that KCOV_MODE_TRACE works for me with these two patches applied.