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