1kcov: code coverage for fuzzing
2===============================
3
4kcov exposes kernel code coverage information in a form suitable for coverage-
5guided fuzzing (randomized testing). Coverage data of a running kernel is
6exported via the "kcov" debugfs file. Coverage collection is enabled on a task
7basis, and thus it can capture precise coverage of a single system call.
8
9Note that kcov does not aim to collect as much coverage as possible. It aims
10to collect more or less stable coverage that is function of syscall inputs.
11To achieve this goal it does not collect coverage in soft/hard interrupts
12and instrumentation of some inherently non-deterministic parts of kernel is
13disabled (e.g. scheduler, locking).
14
15kcov is also able to collect comparison operands from the instrumented code
16(this feature currently requires that the kernel is compiled with clang).
17
18Prerequisites
19-------------
20
21Configure the kernel with::
22
23        CONFIG_KCOV=y
24
25CONFIG_KCOV requires gcc 6.1.0 or later.
26
27If the comparison operands need to be collected, set::
28
29	CONFIG_KCOV_ENABLE_COMPARISONS=y
30
31Profiling data will only become accessible once debugfs has been mounted::
32
33        mount -t debugfs none /sys/kernel/debug
34
35Coverage collection
36-------------------
37
38The following program demonstrates coverage collection from within a test
39program using kcov:
40
41.. code-block:: c
42
43    #include <stdio.h>
44    #include <stddef.h>
45    #include <stdint.h>
46    #include <stdlib.h>
47    #include <sys/types.h>
48    #include <sys/stat.h>
49    #include <sys/ioctl.h>
50    #include <sys/mman.h>
51    #include <unistd.h>
52    #include <fcntl.h>
53    #include <linux/types.h>
54
55    #define KCOV_INIT_TRACE			_IOR('c', 1, unsigned long)
56    #define KCOV_ENABLE			_IO('c', 100)
57    #define KCOV_DISABLE			_IO('c', 101)
58    #define COVER_SIZE			(64<<10)
59
60    #define KCOV_TRACE_PC  0
61    #define KCOV_TRACE_CMP 1
62
63    int main(int argc, char **argv)
64    {
65	int fd;
66	unsigned long *cover, n, i;
67
68	/* A single fd descriptor allows coverage collection on a single
69	 * thread.
70	 */
71	fd = open("/sys/kernel/debug/kcov", O_RDWR);
72	if (fd == -1)
73		perror("open"), exit(1);
74	/* Setup trace mode and trace size. */
75	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
76		perror("ioctl"), exit(1);
77	/* Mmap buffer shared between kernel- and user-space. */
78	cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
79				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
80	if ((void*)cover == MAP_FAILED)
81		perror("mmap"), exit(1);
82	/* Enable coverage collection on the current thread. */
83	if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_PC))
84		perror("ioctl"), exit(1);
85	/* Reset coverage from the tail of the ioctl() call. */
86	__atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
87	/* That's the target syscal call. */
88	read(-1, NULL, 0);
89	/* Read number of PCs collected. */
90	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
91	for (i = 0; i < n; i++)
92		printf("0x%lx\n", cover[i + 1]);
93	/* Disable coverage collection for the current thread. After this call
94	 * coverage can be enabled for a different thread.
95	 */
96	if (ioctl(fd, KCOV_DISABLE, 0))
97		perror("ioctl"), exit(1);
98	/* Free resources. */
99	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
100		perror("munmap"), exit(1);
101	if (close(fd))
102		perror("close"), exit(1);
103	return 0;
104    }
105
106After piping through addr2line output of the program looks as follows::
107
108    SyS_read
109    fs/read_write.c:562
110    __fdget_pos
111    fs/file.c:774
112    __fget_light
113    fs/file.c:746
114    __fget_light
115    fs/file.c:750
116    __fget_light
117    fs/file.c:760
118    __fdget_pos
119    fs/file.c:784
120    SyS_read
121    fs/read_write.c:562
122
123If a program needs to collect coverage from several threads (independently),
124it needs to open /sys/kernel/debug/kcov in each thread separately.
125
126The interface is fine-grained to allow efficient forking of test processes.
127That is, a parent process opens /sys/kernel/debug/kcov, enables trace mode,
128mmaps coverage buffer and then forks child processes in a loop. Child processes
129only need to enable coverage (disable happens automatically on thread end).
130
131Comparison operands collection
132------------------------------
133
134Comparison operands collection is similar to coverage collection:
135
136.. code-block:: c
137
138    /* Same includes and defines as above. */
139
140    /* Number of 64-bit words per record. */
141    #define KCOV_WORDS_PER_CMP 4
142
143    /*
144     * The format for the types of collected comparisons.
145     *
146     * Bit 0 shows whether one of the arguments is a compile-time constant.
147     * Bits 1 & 2 contain log2 of the argument size, up to 8 bytes.
148     */
149
150    #define KCOV_CMP_CONST          (1 << 0)
151    #define KCOV_CMP_SIZE(n)        ((n) << 1)
152    #define KCOV_CMP_MASK           KCOV_CMP_SIZE(3)
153
154    int main(int argc, char **argv)
155    {
156	int fd;
157	uint64_t *cover, type, arg1, arg2, is_const, size;
158	unsigned long n, i;
159
160	fd = open("/sys/kernel/debug/kcov", O_RDWR);
161	if (fd == -1)
162		perror("open"), exit(1);
163	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
164		perror("ioctl"), exit(1);
165	/*
166	* Note that the buffer pointer is of type uint64_t*, because all
167	* the comparison operands are promoted to uint64_t.
168	*/
169	cover = (uint64_t *)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
170				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
171	if ((void*)cover == MAP_FAILED)
172		perror("mmap"), exit(1);
173	/* Note KCOV_TRACE_CMP instead of KCOV_TRACE_PC. */
174	if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_CMP))
175		perror("ioctl"), exit(1);
176	__atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
177	read(-1, NULL, 0);
178	/* Read number of comparisons collected. */
179	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
180	for (i = 0; i < n; i++) {
181		uint64_t ip;
182
183		type = cover[i * KCOV_WORDS_PER_CMP + 1];
184		/* arg1 and arg2 - operands of the comparison. */
185		arg1 = cover[i * KCOV_WORDS_PER_CMP + 2];
186		arg2 = cover[i * KCOV_WORDS_PER_CMP + 3];
187		/* ip - caller address. */
188		ip = cover[i * KCOV_WORDS_PER_CMP + 4];
189		/* size of the operands. */
190		size = 1 << ((type & KCOV_CMP_MASK) >> 1);
191		/* is_const - true if either operand is a compile-time constant.*/
192		is_const = type & KCOV_CMP_CONST;
193		printf("ip: 0x%lx type: 0x%lx, arg1: 0x%lx, arg2: 0x%lx, "
194			"size: %lu, %s\n",
195			ip, type, arg1, arg2, size,
196		is_const ? "const" : "non-const");
197	}
198	if (ioctl(fd, KCOV_DISABLE, 0))
199		perror("ioctl"), exit(1);
200	/* Free resources. */
201	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
202		perror("munmap"), exit(1);
203	if (close(fd))
204		perror("close"), exit(1);
205	return 0;
206    }
207
208Note that the kcov modes (coverage collection or comparison operands) are
209mutually exclusive.
210
211Remote coverage collection
212--------------------------
213
214With KCOV_ENABLE coverage is collected only for syscalls that are issued
215from the current process. With KCOV_REMOTE_ENABLE it's possible to collect
216coverage for arbitrary parts of the kernel code, provided that those parts
217are annotated with kcov_remote_start()/kcov_remote_stop().
218
219This allows to collect coverage from two types of kernel background
220threads: the global ones, that are spawned during kernel boot in a limited
221number of instances (e.g. one USB hub_event() worker thread is spawned per
222USB HCD); and the local ones, that are spawned when a user interacts with
223some kernel interface (e.g. vhost workers); as well as from soft
224interrupts.
225
226To enable collecting coverage from a global background thread or from a
227softirq, a unique global handle must be assigned and passed to the
228corresponding kcov_remote_start() call. Then a userspace process can pass
229a list of such handles to the KCOV_REMOTE_ENABLE ioctl in the handles
230array field of the kcov_remote_arg struct. This will attach the used kcov
231device to the code sections, that are referenced by those handles.
232
233Since there might be many local background threads spawned from different
234userspace processes, we can't use a single global handle per annotation.
235Instead, the userspace process passes a non-zero handle through the
236common_handle field of the kcov_remote_arg struct. This common handle gets
237saved to the kcov_handle field in the current task_struct and needs to be
238passed to the newly spawned threads via custom annotations. Those threads
239should in turn be annotated with kcov_remote_start()/kcov_remote_stop().
240
241Internally kcov stores handles as u64 integers. The top byte of a handle
242is used to denote the id of a subsystem that this handle belongs to, and
243the lower 4 bytes are used to denote the id of a thread instance within
244that subsystem. A reserved value 0 is used as a subsystem id for common
245handles as they don't belong to a particular subsystem. The bytes 4-7 are
246currently reserved and must be zero. In the future the number of bytes
247used for the subsystem or handle ids might be increased.
248
249When a particular userspace process collects coverage via a common
250handle, kcov will collect coverage for each code section that is annotated
251to use the common handle obtained as kcov_handle from the current
252task_struct. However non common handles allow to collect coverage
253selectively from different subsystems.
254
255.. code-block:: c
256
257    /* Same includes and defines as above. */
258
259    struct kcov_remote_arg {
260	__u32		trace_mode;
261	__u32		area_size;
262	__u32		num_handles;
263	__aligned_u64	common_handle;
264	__aligned_u64	handles[0];
265    };
266
267    #define KCOV_INIT_TRACE			_IOR('c', 1, unsigned long)
268    #define KCOV_DISABLE			_IO('c', 101)
269    #define KCOV_REMOTE_ENABLE		_IOW('c', 102, struct kcov_remote_arg)
270
271    #define COVER_SIZE	(64 << 10)
272
273    #define KCOV_TRACE_PC	0
274
275    #define KCOV_SUBSYSTEM_COMMON	(0x00ull << 56)
276    #define KCOV_SUBSYSTEM_USB	(0x01ull << 56)
277
278    #define KCOV_SUBSYSTEM_MASK	(0xffull << 56)
279    #define KCOV_INSTANCE_MASK	(0xffffffffull)
280
281    static inline __u64 kcov_remote_handle(__u64 subsys, __u64 inst)
282    {
283	if (subsys & ~KCOV_SUBSYSTEM_MASK || inst & ~KCOV_INSTANCE_MASK)
284		return 0;
285	return subsys | inst;
286    }
287
288    #define KCOV_COMMON_ID	0x42
289    #define KCOV_USB_BUS_NUM	1
290
291    int main(int argc, char **argv)
292    {
293	int fd;
294	unsigned long *cover, n, i;
295	struct kcov_remote_arg *arg;
296
297	fd = open("/sys/kernel/debug/kcov", O_RDWR);
298	if (fd == -1)
299		perror("open"), exit(1);
300	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
301		perror("ioctl"), exit(1);
302	cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
303				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
304	if ((void*)cover == MAP_FAILED)
305		perror("mmap"), exit(1);
306
307	/* Enable coverage collection via common handle and from USB bus #1. */
308	arg = calloc(1, sizeof(*arg) + sizeof(uint64_t));
309	if (!arg)
310		perror("calloc"), exit(1);
311	arg->trace_mode = KCOV_TRACE_PC;
312	arg->area_size = COVER_SIZE;
313	arg->num_handles = 1;
314	arg->common_handle = kcov_remote_handle(KCOV_SUBSYSTEM_COMMON,
315							KCOV_COMMON_ID);
316	arg->handles[0] = kcov_remote_handle(KCOV_SUBSYSTEM_USB,
317						KCOV_USB_BUS_NUM);
318	if (ioctl(fd, KCOV_REMOTE_ENABLE, arg))
319		perror("ioctl"), free(arg), exit(1);
320	free(arg);
321
322	/*
323	 * Here the user needs to trigger execution of a kernel code section
324	 * that is either annotated with the common handle, or to trigger some
325	 * activity on USB bus #1.
326	 */
327	sleep(2);
328
329	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
330	for (i = 0; i < n; i++)
331		printf("0x%lx\n", cover[i + 1]);
332	if (ioctl(fd, KCOV_DISABLE, 0))
333		perror("ioctl"), exit(1);
334	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
335		perror("munmap"), exit(1);
336	if (close(fd))
337		perror("close"), exit(1);
338	return 0;
339    }
340