[PATCH 2/2] kcov: add AFL-style tracing
From: Quentin Casasnovas
Date: Wed Nov 16 2016 - 16:24:05 EST
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 <sys/ioctl.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <errno.h>
#include <error.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <linux/types.h>
#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 <dvyukov@xxxxxxxxxx>
Cc: Michal Zalewski <lcamtuf@xxxxxxxxx>
Cc: Kees Cook <keescook@xxxxxxxxxxxx>
Signed-off-by: Quentin Casasnovas <quentin.casasnovas@xxxxxxxxxx>
Signed-off-by: Vegard Nossum <vegard.nossum@xxxxxxxxxx>
---
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 <linux/types.h>
#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 <linux/types.h>
#include <linux/file.h>
#include <linux/fs.h>
+#include <linux/hash.h>
#include <linux/mm.h>
#include <linux/printk.h>
#include <linux/slab.h>
@@ -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