Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S934774AbcKPVYB (ORCPT ); Wed, 16 Nov 2016 16:24:01 -0500 Received: from aserp1040.oracle.com ([141.146.126.69]:28580 "EHLO aserp1040.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933944AbcKPVX4 (ORCPT ); Wed, 16 Nov 2016 16:23:56 -0500 From: Quentin Casasnovas To: Dmitry Vyukov Cc: linux-kernel@vger.kernel.org, Vegard Nossum , Michal Zalewski , Kees Cook , syzkaller , Quentin Casasnovas Subject: [PATCH 2/2] kcov: add AFL-style tracing Date: Wed, 16 Nov 2016 22:27:46 +0100 Message-Id: <20161116212746.29047-3-quentin.casasnovas@oracle.com> X-Mailer: git-send-email 2.10.2 In-Reply-To: <20161116212746.29047-1-quentin.casasnovas@oracle.com> References: <20161116212746.29047-1-quentin.casasnovas@oracle.com> X-Source-IP: userv0022.oracle.com [156.151.31.74] Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6371 Lines: 212 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); -- 2.10.2