Coverage deduplication for KCOV
Subsystems (13)
Alexander Potapenko
reviewerv4 cover Coverage deduplication for KCOV
As mentioned by Joey Jiao in [1], the current kcov implementation may suffer from certain syscalls overflowing the userspace coverage buffer.
According to our measurements, among 24 syzkaller instances running upstream Linux, 5 had a coverage overflow in at least 50% of executed programs. The median percentage of programs with overflows across those 24 instances was 8.8%.
One way to mitigate this problem is to increase the size of the kcov buffer in the userspace application using kcov. But right now syzkaller already uses 4Mb per each of up to 32 threads to store the coverage, and increasing it further would result in reduction in the number of executors on a single machine. Replaying the same program with an increased buffer size in the case of overflow would also lead to fewer executions being possible.
When executing a single system call, excessive coverage usually stems from loops, which write the same PCs into the output buffer repeatedly. Although collecting precise traces may give us some insights into e.g. the number of loop iterations and the branches being taken, the fuzzing engine does not take advantage of these signals, and recording only unique PCs should be just as practical.
In [1] Joey Jiao suggested using a hash table to deduplicate the coverage signal on the kernel side. While being universally applicable to all types of data collected by kcov, this approach adds another layer of complexity, requiring dynamically growing the map. Another problem is potential hash collisions, which can as well lead to lost coverage. Hash maps are also unavoidably sparse, which potentially requires more memory.
The approach proposed in this patch series is to assign a unique (and almost) sequential ID to each of the coverage callbacks in the kernel. Then we carve out a fixed-sized bitmap from the userspace trace buffer, and on every callback invocation we:
- obtain the callback_ID;
- if bitmap[callback_ID] is set, append the PC to the trace buffer;
- set bitmap[callback_ID] to true.
LLVM's -fsanitize-coverage=trace-pc-guard replaces every coverage callback in the kernel with a call to __sanitizer_cov_trace_pc_guard(&guard_variable) , where guard_variable is a 4-byte global that is unique for the callsite.
This allows us to lazily allocate sequential numbers just for the callbacks that have actually been executed, using a lock-free algorithm.
This patch series implements a new config, CONFIG_KCOV_ENABLE_GUARDS, which utilizes the mentioned LLVM flag for coverage instrumentation. In addition to the existing coverage collection modes, it introduces ioctl(KCOV_UNIQUE_ENABLE), which splits the existing kcov buffer into the bitmap and the trace part for a particular fuzzing session, and collects only unique coverage in the trace buffer.
To reset the coverage between runs, it is now necessary to set trace[0] to 0 AND clear the entire bitmap. This is still considered feasible, based on the experimental results below.
Alternatively, users can call ioctl(KCOV_RESET_TRACE) to reset the coverage. This makes it possible to make the coverage buffer read-only, so that it is harder to corrupt.
The current design does not address the deduplication of KCOV_TRACE_CMP comparisons; however, the number of kcov overflows during the hints collection process is insignificant compared to the overflows of KCOV_TRACE_PC.
In addition to the mentioned changes, this patch series implements a selftest in tools/testing/selftests/kcov/kcov_test. This will help check the variety of different coverage collection modes.
Experimental results.
We've conducted an experiment running syz-testbed [3] on 10 syzkaller instances for 24 hours. Out of those 10 instances, 5 were enabling the kcov_deduplicate flag from [4], which makes use of the KCOV_UNIQUE_ENABLE ioctl, reserving 4096 words (262144 bits) for the bitmap and leaving 520192 words for the trace collection.
Below are the average stats from the runs.
kcov_deduplicate=false:
corpus: 52176
coverage: 302658
cover overflows: 225288
comps overflows: 491
exec total: 1417829
max signal: 318894
kcov_deduplicate=true:
corpus: 52581
coverage: 304344
cover overflows: 986
comps overflows: 626
exec total: 1484841
max signal: 322455
[1] https://lore.kernel.org/linux-arm-kernel/[email protected]/T/
[2] https://clang.llvm.org/docs/SanitizerCoverage.html
[3] https://github.com/google/syzkaller/tree/master/tools/syz-testbed
[4] https://github.com/ramosian-glider/syzkaller/tree/kcov_dedup-new
v4:
- fix a compilation error detected by the kernel test robot <[email protected]>
- add CONFIG_KCOV_UNIQUE=y as a prerequisite for kcov_test
- Reviewed-by: tags
v3:
- drop "kcov: apply clang-format to kcov code"
- address reviewers' comments
- merge __sancov_guards into .bss
- proper testing of unique coverage in kcov_test
- fix a warning detected by the kernel test robot <[email protected]>
- better comments
v2:
- assorted cleanups (enum kcov_mode, docs)
- address reviewers' comments
- drop R_X86_64_REX_GOTPCRELX support
- implement ioctl(KCOV_RESET_TRACE)
- add a userspace selftest
Alexander Potapenko (10):
x86: kcov: disable instrumentation of arch/x86/kernel/tsc.c
kcov: elaborate on using the shared buffer
kcov: factor out struct kcov_state
mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
kcov: x86: introduce CONFIG_KCOV_UNIQUE
kcov: add trace and trace_size to struct kcov_state
kcov: add ioctl(KCOV_UNIQUE_ENABLE)
kcov: add ioctl(KCOV_RESET_TRACE)
kcov: selftests: add kcov_test
kcov: use enum kcov_mode in kcov_mode_enabled()
Documentation/dev-tools/kcov.rst | 124 +++++++ MAINTAINERS | 3 + arch/x86/Kconfig | 1 + arch/x86/kernel/Makefile | 2 + arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 13 +- include/linux/kcov.h | 6 +- include/linux/kcov_types.h | 37 +++ include/linux/sched.h | 13 +- include/uapi/linux/kcov.h | 2 + kernel/kcov.c | 368 ++++++++++++++------- lib/Kconfig.debug | 26 ++ mm/kasan/generic.c | 24 ++ mm/kasan/kasan.h | 2 + scripts/Makefile.kcov | 7 + scripts/module.lds.S | 35 ++ tools/objtool/check.c | 3 +- tools/testing/selftests/kcov/Makefile | 6 + tools/testing/selftests/kcov/config | 2 + tools/testing/selftests/kcov/kcov_test.c | 401 +++++++++++++++++++++++ 20 files changed, 949 insertions(+), 127 deletions(-) create mode 100644 include/linux/kcov_types.h create mode 100644 tools/testing/selftests/kcov/Makefile create mode 100644 tools/testing/selftests/kcov/config create mode 100644 tools/testing/selftests/kcov/kcov_test.c
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 1/10 x86: kcov: disable instrumentation of arch/x86/kernel/tsc.c
sched_clock() appears to be called from interrupts, producing spurious coverage, as reported by CONFIG_KCOV_SELFTEST:
RIP: 0010:__sanitizer_cov_trace_pc_guard+0x66/0xe0 kernel/kcov.c:288 ... fault_in_kernel_space+0x17/0x70 arch/x86/mm/fault.c:1119 handle_page_fault arch/x86/mm/fault.c:1477 exc_page_fault+0x56/0x110 arch/x86/mm/fault.c:1538 asm_exc_page_fault+0x26/0x30 ./arch/x86/include/asm/idtentry.h:623 RIP: 0010:__sanitizer_cov_trace_pc_guard+0x66/0xe0 kernel/kcov.c:288 ... sched_clock+0x12/0x70 arch/x86/kernel/tsc.c:284 __lock_pin_lock kernel/locking/lockdep.c:5628 lock_pin_lock+0xd7/0x180 kernel/locking/lockdep.c:5959 rq_pin_lock kernel/sched/sched.h:1761 rq_lock kernel/sched/sched.h:1838 __schedule+0x3a8/0x4b70 kernel/sched/core.c:6691 preempt_schedule_irq+0xbf/0x160 kernel/sched/core.c:7090 irqentry_exit+0x6f/0x90 kernel/entry/common.c:354 asm_sysvec_reschedule_ipi+0x1a/0x20 ./arch/x86/include/asm/idtentry.h:707 RIP: 0010:selftest+0x26/0x60 kernel/kcov.c:1223 ... kcov_init+0x81/0xa0 kernel/kcov.c:1252 do_one_initcall+0x2e1/0x910 do_initcall_level+0xff/0x160 init/main.c:1319 do_initcalls+0x4a/0xa0 init/main.c:1335 kernel_init_freeable+0x448/0x610 init/main.c:1567 kernel_init+0x24/0x230 init/main.c:1457 ret_from_fork+0x60/0x90 arch/x86/kernel/process.c:153 ret_from_fork_asm+0x1a/0x30 arch/x86/entry/entry_64.S:245 </TASK>
---
Change-Id: Ica191d73bf5601b31e893d6e517b91be983e986a
--- arch/x86/kernel/Makefile | 2 ++ 1 file changed, 2 insertions(+)
arch/x86/kernel/Makefile +2 -0
@@ -43,6 +43,8 @@ KCOV_INSTRUMENT_dumpstack_$(BITS).o := n KCOV_INSTRUMENT_unwind_orc.o := n KCOV_INSTRUMENT_unwind_frame.o := n KCOV_INSTRUMENT_unwind_guess.o := n +# Avoid instrumenting code that produces spurious coverage in interrupts. +KCOV_INSTRUMENT_tsc.o := n CFLAGS_head32.o := -fno-stack-protector CFLAGS_head64.o := -fno-stack-protector
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 2/10 kcov: elaborate on using the shared buffer
In reply to Alexander PotapenkoAdd a paragraph about the shared buffer usage to kcov.rst.
---
v3:
- add Reviewed-by: Dmitry Vyukov
Change-Id: Ia47ef7c3fcc74789fe57a6e1d93e29a42dbc0a97
--- Documentation/dev-tools/kcov.rst | 55 ++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+)
Documentation/dev-tools/kcov.rst +55 -0
@@ -137,6 +137,61 @@ mmaps coverage buffer, and then forks child processes in a loop. The child processes only need to enable coverage (it gets disabled automatically when a thread exits). +Shared buffer for coverage collection +------------------------------------- +KCOV employs a shared memory buffer as a central mechanism for efficient and +direct transfer of code coverage information between the kernel and userspace +applications. + +Calling ``ioctl(fd, KCOV_INIT_TRACE, size)`` initializes coverage collection for +the current thread associated with the file descriptor ``fd``. The buffer +allocated will hold ``size`` unsigned long values, as interpreted by the kernel. +Notably, even in a 32-bit userspace program on a 64-bit kernel, each entry will +occupy 64 bits. + +Following initialization, the actual shared memory buffer is created using:: + + mmap(NULL, size * sizeof(unsigned long), PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0) + +The size of this memory mapping, calculated as ``size * sizeof(unsigned long)``, +must be a multiple of ``PAGE_SIZE``. + +This buffer is then shared between the kernel and the userspace. The first +element of the buffer contains the number of PCs stored in it. +Both the userspace and the kernel may write to the shared buffer, so to avoid +race conditions each userspace thread should only update its own buffer. + +Normally the shared buffer is used as follows:: + + Userspace Kernel + -----------------------------------------+------------------------------------------- + ioctl(fd, KCOV_INIT_TRACE, size) | + | Initialize coverage for current thread + mmap(..., MAP_SHARED, fd, 0) | + | Allocate the buffer, initialize it + | with zeroes + ioctl(fd, KCOV_ENABLE, KCOV_TRACE_PC) | + | Enable PC collection for current thread + | starting at buffer[1] (KCOV_ENABLE will + | already write some coverage) + Atomically write 0 to buffer[0] to | + reset the coverage | + | + Execute some syscall(s) | + | Write new coverage starting at + | buffer[1] + Atomically read buffer[0] to get the | + total coverage size at this point in | + time | + | + ioctl(fd, KCOV_DISABLE, 0) | + | Write some more coverage for ioctl(), + | then disable PC collection for current + | thread + Safely read and process the coverage | + up to the buffer[0] value saved above | + + Comparison operands collection ------------------------------
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 3/10 kcov: factor out struct kcov_state
In reply to Alexander PotapenkoGroup several kcov-related fields (area, size, sequence) that are stored in various structures, into struct kcov_state, so that these fields can be easily passed around and manipulated. Note that now the spinlock in struct kcov applies to every member of struct kcov_state, including the sequence number.
This prepares us for the upcoming change that will introduce more kcov state.
Also update the MAINTAINERS entry: add include/linux/kcov_types.h, add myself as kcov reviewer.
---
v4:
- add Reviewed-by: Dmitry Vyukov
v3:
- fix comments by Dmitry Vyukov:
- adjust a comment in sched.h
- fix incorrect parameters passed to kcov_start()
v2:
- add myself to kcov MAINTAINERS
- rename kcov-state.h to kcov_types.h
- update the description
- do not move mode into struct kcov_state
- use '{ }' instead of '{ 0 }'
Change-Id: If225682ea2f6e91245381b3270de16e7ea40df39
--- MAINTAINERS | 2 + include/linux/kcov.h | 2 +- include/linux/kcov_types.h | 22 ++++++++ include/linux/sched.h | 13 +---- kernel/kcov.c | 112 ++++++++++++++++--------------------- 5 files changed, 77 insertions(+), 74 deletions(-) create mode 100644 include/linux/kcov_types.h
MAINTAINERS +2 -0
@@ -13008,11 +13008,13 @@ F: include/linux/kcore.h KCOV R: Dmitry Vyukov <[email protected]> R: Andrey Konovalov <[email protected]> +R: Alexander Potapenko <[email protected]> L: [email protected] S: Maintained B: https://bugzilla.kernel.org/buglist.cgi?component=Sanitizers&product=Memory%20Management F: Documentation/dev-tools/kcov.rst F: include/linux/kcov.h +F: include/linux/kcov_types.h F: include/uapi/linux/kcov.h F: kernel/kcov.c F: scripts/Makefile.kcov
include/linux/kcov.h +1 -1
@@ -2,7 +2,7 @@#ifndef _LINUX_KCOV_H#define _LINUX_KCOV_H -#include <linux/sched.h> +#include <linux/kcov_types.h> #include <uapi/linux/kcov.h> struct task_struct ;
include/linux/kcov_types.h new file +22 -0
@@ -0,0 +1,22 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_KCOV_STATE_H +#define _LINUX_KCOV_STATE_H + +#ifdef CONFIG_KCOV +/* See kernel/kcov.c for more details. */ +struct kcov_state { +/* Size of the area (in long's). */ +unsigned int size; + +/* Buffer for coverage collection, shared with the userspace. */ +void *area; + +/* +* KCOV sequence number: incremented each time kcov is reenabled, used +* by kcov_remote_stop(), see the comment there. +*/ +int sequence; +}; +#endif /* CONFIG_KCOV */ + +#endif /* _LINUX_KCOV_STATE_H */
include/linux/sched.h +3 -10
@@ -42,6 +42,7 @@#include <linux/restart_block.h> #include <uapi/linux/rseq.h> #include <linux/seqlock_types.h> +#include <linux/kcov_types.h> #include <linux/kcsan.h> #include <linux/rv.h> #include <linux/uidgid_types.h>
@@ -1516,16 +1517,11 @@ struct task_struct {#endif /* CONFIG_TRACING */ #ifdef CONFIG_KCOV -/* See kernel/kcov.c for more details. */ -/* Coverage collection mode enabled for this task (0 if disabled): */ unsigned int kcov_mode; -/* Size of the kcov_area: */ -unsigned int kcov_size; - -/* Buffer for coverage collection: */ -void *kcov_area; +/* KCOV buffer state for this task. */ +struct kcov_state kcov_state;/* KCOV descriptor wired with this task or NULL: */ struct kcov *kcov;
@@ -1533,9 +1529,6 @@ struct task_struct {/* KCOV common handle for remote coverage collection: */ u64 kcov_handle; -/* KCOV sequence number: */ -int kcov_sequence; -/* Collect coverage from softirq context: */ unsigned int kcov_softirq;#endif
kernel/kcov.c +49 -63
286 lines not on this page · raw message
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 4/10 mm/kasan: define __asan_before_dynamic_init, __asan_after_dynamic_init
In reply to Alexander PotapenkoCalls to __asan_before_dynamic_init() and __asan_after_dynamic_init() are inserted by Clang when building with coverage guards. These functions can be used to detect initialization order fiasco bugs in the userspace, but it is fine for them to be no-ops in the kernel.
---
v4:
- Fix a compilation error reported by the kernel test robot <[email protected]>
v3:
- add Reviewed-by: Dmitry Vyukov
v2:
- Address comments by Dmitry Vyukov:
- rename CONFIG_KCOV_ENABLE_GUARDS to CONFIG_KCOV_UNIQUE
- Move this patch before the one introducing CONFIG_KCOV_UNIQUE, per Marco Elver's request.
Change-Id: I7f8eb690a3d96f7d122205e8f1cba8039f6a68eb
fixup asan_before
Change-Id: If653ba4f160414cafe65eee530b6b67e5b5b547c
--- mm/kasan/generic.c | 24 ++++++++++++++++++++++++ mm/kasan/kasan.h | 2 ++ 2 files changed, 26 insertions(+)
mm/kasan/generic.c +24 -0
@@ -238,6 +238,30 @@ void __asan_unregister_globals(void *ptr, ssize_t size) }EXPORT_SYMBOL (__asan_unregister_globals); +#if defined(CONFIG_KCOV_UNIQUE ) +/* +* __asan_before_dynamic_init() and __asan_after_dynamic_init() are inserted +* when the user requests building with coverage guards. In the userspace, these +* two functions can be used to detect initialization order fiasco bugs, but in +* the kernel they can be no-ops. +* +* There is an inconsistency between how Clang and GCC emit calls to this +* function, with Clang expecting the parameter to be i64, whereas GCC wants it +* to be const void *. +* We pick the latter option, because Clang does not care, and GCC prints a +* warning with -Wbuiltin-declaration-mismatch. +*/ +void __asan_before_dynamic_init (const void *module_name) +{ +} +EXPORT_SYMBOL (__asan_before_dynamic_init); + +void __asan_after_dynamic_init (void ) +{ +} +EXPORT_SYMBOL (__asan_after_dynamic_init); +#endif +#define DEFINE_ASAN_LOAD_STORE (size) \ void __asan_load##size(void *addr) \ { \
mm/kasan/kasan.h +2 -0
@@ -582,6 +582,8 @@ void kasan_restore_multi_shot(bool enabled);void __asan_register_globals (void *globals,ssize_t size);void __asan_unregister_globals (void *globals,ssize_t size); +void __asan_before_dynamic_init (const void *module_name); +void __asan_after_dynamic_init (void );void __asan_handle_no_return (void );void __asan_alloca_poison (void *,ssize_t size);void __asan_allocas_unpoison (void *stack_top,ssize_t stack_bottom);
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 5/10 kcov: x86: introduce CONFIG_KCOV_UNIQUE
In reply to Alexander PotapenkoThe new config switches coverage instrumentation to using
__sanitizer_cov_trace_pc_guard(u32 *guard)
instead of
__sanitizer_cov_trace_pc(void)
This relies on Clang's -fsanitize-coverage=trace-pc-guard flag [1].
Each callback receives a unique 32-bit guard variable residing in .bss. Those guards can be used by kcov to deduplicate the coverage on the fly.
As a first step, we make the new instrumentation mode 1:1 compatible with the old one.
[1] https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards
---
v4:
- add Reviewed-by: Dmitry Vyukov
v3:
- per Dmitry Vyukov's request, add better comments in scripts/module.lds.S and lib/Kconfig.debug
- add -sanitizer-coverage-drop-ctors to scripts/Makefile.kcov to drop the unwanted constructors emitting unsupported relocations
- merge the __sancov_guards section into .bss
v2:
- Address comments by Dmitry Vyukov
- rename CONFIG_KCOV_ENABLE_GUARDS to CONFIG_KCOV_UNIQUE
- update commit description and config description
- Address comments by Marco Elver
- rename sanitizer_cov_write_subsequent() to kcov_append_to_buffer()
- make config depend on X86_64 (via ARCH_HAS_KCOV_UNIQUE)
- swap #ifdef branches
- tweak config description
- remove redundant check for CONFIG_CC_HAS_SANCOV_TRACE_PC_GUARD
Change-Id: Iacb1e71fd061a82c2acadf2347bba4863b9aec39
--- arch/x86/Kconfig | 1 + arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 13 ++++++- include/linux/kcov.h | 2 + kernel/kcov.c | 61 +++++++++++++++++++++---------- lib/Kconfig.debug | 26 +++++++++++++ scripts/Makefile.kcov | 7 ++++ scripts/module.lds.S | 35 ++++++++++++++++++ tools/objtool/check.c | 1 + 9 files changed, 126 insertions(+), 21 deletions(-)
arch/x86/Kconfig +1 -0
@@ -94,6 +94,7 @@ config X86 select ARCH_HAS_FORTIFY_SOURCE select ARCH_HAS_GCOV_PROFILE_ALL select ARCH_HAS_KCOV if X86_64 + select ARCH_HAS_KCOV_UNIQUE if X86_64 select ARCH_HAS_KERNEL_FPU_SUPPORT select ARCH_HAS_MEM_ENCRYPT select ARCH_HAS_MEMBARRIER_SYNC_CORE
arch/x86/kernel/vmlinux.lds.S +1 -0
@@ -372,6 +372,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); *(BSS_MAIN) BSS_DECRYPTED + BSS_SANCOV_GUARDS . = ALIGN(PAGE_SIZE); __bss_stop = .; }
include/asm-generic/vmlinux.lds.h +12 -1
@@ -102,7 +102,8 @@* sections to be brought in with rodata. */ #if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION ) || defined(CONFIG_LTO_CLANG ) || \ -defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) + defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) || \ + defined(CONFIG_KCOV_UNIQUE )#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*#else #define TEXT_MAIN .text
@@ -121,6 +122,16 @@ defined(CONFIG_AUTOFDO_CLANG) || defined(CONFIG_PROPELLER_CLANG)#define SBSS_MAIN .sbss#endif +#if defined(CONFIG_KCOV_UNIQUE ) +/* BSS_SANCOV_GUARDS must be part of the .bss section so that it is zero-initialized. */ +#define BSS_SANCOV_GUARDS \ + __start___sancov_guards = .; \ + *(__sancov_guards); \ + __stop___sancov_guards = .; +#else +#define BSS_SANCOV_GUARDS +#endif +/* * GCC 4.5 and later have a 32 bytes section alignment for structures. * Except GCC 4.9, that feels the need to align on 64 bytes.
include/linux/kcov.h +2 -0
@@ -107,6 +107,8 @@ typedef unsigned long long kcov_u64;#endif void __sanitizer_cov_trace_pc (void ); +void __sanitizer_cov_trace_pc_guard (u32 *guard); +void __sanitizer_cov_trace_pc_guard_init (uint32_t *start,uint32_t *stop);void __sanitizer_cov_trace_cmp1 (u8 arg1,u8 arg2);void __sanitizer_cov_trace_cmp2 (u16 arg1,u16 arg2);void __sanitizer_cov_trace_cmp4 (u32 arg1,u32 arg2);
kernel/kcov.c +41 -20
82 lines not on this page · raw message
lib/Kconfig.debug +26 -0
@@ -2153,6 +2153,12 @@ config ARCH_HAS_KCOV build and run with CONFIG_KCOV. This typically requires disabling instrumentation for some early boot code. +config CC_HAS_SANCOV_TRACE_PC + def_bool $(cc-option,-fsanitize-coverage=trace-pc) + +config CC_HAS_SANCOV_TRACE_PC_GUARD + def_bool $(cc-option,-fsanitize-coverage=trace-pc-guard) + config KCOV bool "Code coverage for fuzzing" depends on ARCH_HAS_KCOV
@@ -2166,6 +2172,26 @@ config KCOV For more details, see Documentation/dev-tools/kcov.rst. +config ARCH_HAS_KCOV_UNIQUE + bool + help + An architecture should select this when it can successfully + build and run with CONFIG_KCOV_UNIQUE. + +config KCOV_UNIQUE + depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD && ARCH_HAS_KCOV_UNIQUE + bool "Enable unique program counter collection mode for KCOV" + help + This option enables KCOV's unique program counter (PC) collection mode, + which deduplicates PCs on the fly when the KCOV_UNIQUE_ENABLE ioctl is + used. + + This significantly reduces the memory footprint for coverage data + collection compared to trace mode, as it prevents the kernel from + storing the same PC multiple times. + Enabling this mode incurs a slight increase in kernel binary size. + config KCOV_ENABLE_COMPARISONS bool "Enable comparison operands collection by KCOV" depends on KCOV
scripts/Makefile.kcov +7 -0
@@ -1,5 +1,12 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_UNIQUE),y) +kcov-flags-y += -fsanitize-coverage=trace-pc-guard +# Drop per-file constructors that -fsanitize-coverage=trace-pc-guard inserts by default. +# Kernel does not need them, and they may produce unknown relocations. +kcov-flags-y += -mllvm -sanitizer-coverage-drop-ctors +else kcov-flags-y += -fsanitize-coverage=trace-pc +endif kcov-flags-$(CONFIG_KCOV_ENABLE_COMPARISONS) += -fsanitize-coverage=trace-cmp kcov-rflags-y += -Cpasses=sancov-module
scripts/module.lds.S +35 -0
@@ -47,6 +47,7 @@ SECTIONS { .bss : { *(.bss .bss.[0-9a-zA-Z_]*) *(.bss..L*) + *(__sancov_guards) } .data : {
@@ -64,6 +65,40 @@ SECTIONS { MOD_CODETAG_SECTIONS() } #endif + +#ifdef CONFIG_KCOV_UNIQUE + /* + * CONFIG_KCOV_UNIQUE creates COMDAT groups for instrumented functions, + * which has the following consequences in the presence of + * -ffunction-sections: + * - Separate .init.text and .exit.text sections in the modules are not + * merged together, which results in errors trying to create + * duplicate entries in /sys/module/MODNAME/sections/ at module load + * time. + * - Each function is placed in a separate .text.funcname section, so + * there is no .text section anymore. Collecting them together here + * has mostly aesthetic purpose, although some tools may be expecting + * it to be present. + */ + .text : { + *(.text .text.[0-9a-zA-Z_]*) + *(.text..L*) + } + .init.text : { + *(.init.text .init.text.[0-9a-zA-Z_]*) + *(.init.text..L*) + } + .exit.text : { + *(.exit.text .exit.text.[0-9a-zA-Z_]*) + *(.exit.text..L*) + } + .bss : { + *(.bss .bss.[0-9a-zA-Z_]*) + *(.bss..L*) + *(__sancov_guards) + } +#endif + MOD_SEPARATE_CODETAG_SECTIONS() }
tools/objtool/check.c +1 -0
@@ -1156,6 +1156,7 @@ static const char *uaccess_safe_builtin[] = {"write_comp_data" ,"check_kcov_mode" ,"__sanitizer_cov_trace_pc" , +"__sanitizer_cov_trace_pc_guard" ,"__sanitizer_cov_trace_const_cmp1" ,"__sanitizer_cov_trace_const_cmp2" , "__sanitizer_cov_trace_const_cmp4",
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Re: [PATCH v4 05/10] kcov: x86: introduce CONFIG_KCOV_UNIQUE
Quoted 276 lines · Alexander Potapenko
The new config switches coverage instrumentation to using
__sanitizer_cov_trace_pc_guard(u32 *guard)
instead of
__sanitizer_cov_trace_pc(void)This relies on Clang's -fsanitize-coverage=trace-pc-guard flag [1].
Each callback receives a unique 32-bit guard variable residing in .bss. Those guards can be used by kcov to deduplicate the coverage on the fly.
As a first step, we make the new instrumentation mode 1:1 compatible with the old one.
[1] https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards
Signed-off-by Alexander Potapenko <[email protected]>Reviewed-by Dmitry Vyukov <[email protected]>---
v4:
- add Reviewed-by: Dmitry Vyukovv3:
- per Dmitry Vyukov's request, add better comments inscripts/module.lds.Sandlib/Kconfig.debug
- add -sanitizer-coverage-drop-ctors toscripts/Makefile.kcovto drop the unwanted constructors emitting unsupported relocations
- merge the__sancov_guardssection into .bssv2:
- Address comments by Dmitry Vyukov
- renameCONFIG_KCOV_ENABLE_GUARDStoCONFIG_KCOV_UNIQUE
- update commit description and config description
- Address comments by Marco Elver
- renamesanitizer_cov_write_subsequent()tokcov_append_to_buffer()
- make config depend onX86_64(viaARCH_HAS_KCOV_UNIQUE)
- swap #ifdef branches
- tweak config description
- remove redundant check forCONFIG_CC_HAS_SANCOV_TRACE_PC_GUARDChange-Id: Iacb1e71fd061a82c2acadf2347bba4863b9aec39
--- arch/x86/Kconfig | 1 + arch/x86/kernel/vmlinux.lds.S | 1 + include/asm-generic/vmlinux.lds.h | 13 ++++++- include/linux/kcov.h | 2 + kernel/kcov.c | 61 +++++++++++++++++++++---------- lib/Kconfig.debug | 26 +++++++++++++ scripts/Makefile.kcov | 7 ++++ scripts/module.lds.S | 35 ++++++++++++++++++ tools/objtool/check.c | 1 + 9 files changed, 126 insertions(+), 21 deletions(-)arch/x86/Kconfig +1
-0@@ -94,6 +94,7 @@ config X86 select ARCH_HAS_FORTIFY_SOURCE select ARCH_HAS_GCOV_PROFILE_ALL select ARCH_HAS_KCOV if X86_64 + select ARCH_HAS_KCOV_UNIQUE if X86_64 select ARCH_HAS_KERNEL_FPU_SUPPORT select ARCH_HAS_MEM_ENCRYPT select ARCH_HAS_MEMBARRIER_SYNC_COREarch/x86/kernel/vmlinux.lds.S +1
-0@@ -372,6 +372,7 @@ SECTIONS . = ALIGN(PAGE_SIZE); *(BSS_MAIN) BSS_DECRYPTED + BSS_SANCOV_GUARDS . = ALIGN(PAGE_SIZE); __bss_stop = .; }include/asm-generic/vmlinux.lds.h +12
-1@@ -102,7 +102,8 @@* sections to be brought in with rodata. */ #if defined(CONFIG_LD_DEAD_CODE_DATA_ELIMINATION ) || defined(CONFIG_LTO_CLANG ) || \ -defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) + defined(CONFIG_AUTOFDO_CLANG ) || defined(CONFIG_PROPELLER_CLANG ) || \ + defined(CONFIG_KCOV_UNIQUE )#define TEXT_MAIN .text .text.[0-9a-zA-Z_]*#else #define TEXT_MAIN .text@@ -121,6 +122,16 @@ defined(CONFIG_AUTOFDO_CLANG) || defined(CONFIG_PROPELLER_CLANG)#define SBSS_MAIN .sbss#endif +#if defined(CONFIG_KCOV_UNIQUE ) +/* BSS_SANCOV_GUARDS must be part of the .bss section so that it is zero-initialized. */ +#define BSS_SANCOV_GUARDS \ + __start___sancov_guards = .; \ + *(__sancov_guards); \ + __stop___sancov_guards = .; +#else +#define BSS_SANCOV_GUARDS +#endif +/* * GCC 4.5 and later have a 32 bytes section alignment for structures. * Except GCC 4.9, that feels the need to align on 64 bytes. include/linux/kcov.h +2
-0@@ -107,6 +107,8 @@ typedef unsigned long long kcov_u64;#endif void __sanitizer_cov_trace_pc (void ); +void __sanitizer_cov_trace_pc_guard (u32 *guard); +void __sanitizer_cov_trace_pc_guard_init (uint32_t *start,uint32_t *stop);void __sanitizer_cov_trace_cmp1 (u8 arg1,u8 arg2);void __sanitizer_cov_trace_cmp2 (u16 arg1,u16 arg2);void __sanitizer_cov_trace_cmp4 (u32 arg1,u32 arg2);kernel/kcov.c +41
-20@@ -194,27 +194,15 @@ static notrace unsigned long canonicalize_ip(unsigned long ip)return ip; } -/* -* Entry point from instrumented code. -* This is called once per basic-block/edge. -*/ -void notrace __sanitizer_cov_trace_pc(void) +static notrace void kcov_append_to_buffer(unsigned long *area, int size, +unsigned long ip) { -struct task_struct *t; -unsigned long *area; -unsigned long ip =canonicalize_ip (_RET_IP_); -unsigned long pos; - - t = current; -if (!check_kcov_mode (KCOV_MODE_TRACE_PC , t)) -return ; - - area = t->kcov_state.area;/* The first 64-bit word is the number of subsequent PCs. */ - pos =READ_ONCE (area[0 ]) +1 ; -if (likely (pos < t->kcov_state.size)) { -/* Previously we write pc before updating pos. However, some -* early interrupt code could bypass check_kcov_mode() check +unsigned long pos =READ_ONCE (area[0 ]) +1 ; + +if (likely (pos < size)) { +/* +* Some early interrupt code could bypass check_kcov_mode() check * and invoke __sanitizer_cov_trace_pc(). If such interrupt is * raised between writing pc and updating pos, the pc could be * overitten by the recursive __sanitizer_cov_trace_pc(). @@ -225,7 +213,40 @@ void notrace __sanitizer_cov_trace_pc(void) area[pos] = ip; } } + +/* +* Entry point from instrumented code. +* This is called once per basic-block/edge. +*/ +#ifdef CONFIG_KCOV_UNIQUE +void notrace __sanitizer_cov_trace_pc_guard(u32 *guard) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +kcov_append_to_buffer (current->kcov_state.area, + current->kcov_state.size, +canonicalize_ip (_RET_IP_)); +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard); + +void notrace __sanitizer_cov_trace_pc_guard_init(uint32_t *start, +uint32_t *stop) +{ +} +EXPORT_SYMBOL (__sanitizer_cov_trace_pc_guard_init); +#else /* !CONFIG_KCOV_UNIQUE */ +void notrace __sanitizer_cov_trace_pc(void) +{ +if (!check_kcov_mode (KCOV_MODE_TRACE_PC , current)) +return ; + +kcov_append_to_buffer (current->kcov_state.area, + current->kcov_state.size, +canonicalize_ip (_RET_IP_)); +}EXPORT_SYMBOL (__sanitizer_cov_trace_pc); +#endif #ifdef CONFIG_KCOV_ENABLE_COMPARISONS static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip)@@ -253,7 +274,7 @@ static void notrace write_comp_data(u64 type, u64 arg1, u64 arg2, u64 ip) start_index =1 + count *KCOV_WORDS_PER_CMP ; end_pos = (start_index +KCOV_WORDS_PER_CMP ) *sizeof (u64);if (likely (end_pos <= max_pos)) { -/* See comment in __sanitizer_cov_trace_pc(). */ +/* See comment in kcov_append_to_buffer(). */ WRITE_ONCE (area[0 ], count +1 );barrier (); area[start_index] = type;lib/Kconfig.debug +26
-0@@ -2153,6 +2153,12 @@ config ARCH_HAS_KCOV build and run with CONFIG_KCOV. This typically requires disabling instrumentation for some early boot code. +config CC_HAS_SANCOV_TRACE_PC + def_bool $(cc-option,-fsanitize-coverage=trace-pc) + +config CC_HAS_SANCOV_TRACE_PC_GUARD + def_bool $(cc-option,-fsanitize-coverage=trace-pc-guard) + config KCOV bool "Code coverage for fuzzing" depends on ARCH_HAS_KCOV@@ -2166,6 +2172,26 @@ config KCOV For more details, see Documentation/dev-tools/kcov.rst. +config ARCH_HAS_KCOV_UNIQUE + bool + help + An architecture should select this when it can successfully + build and run with CONFIG_KCOV_UNIQUE. + +config KCOV_UNIQUE + depends on KCOV + depends on CC_HAS_SANCOV_TRACE_PC_GUARD && ARCH_HAS_KCOV_UNIQUE + bool "Enable unique program counter collection mode for KCOV" + help + This option enables KCOV's unique program counter (PC) collection mode, + which deduplicates PCs on the fly when the KCOV_UNIQUE_ENABLE ioctl is + used. + + This significantly reduces the memory footprint for coverage data + collection compared to trace mode, as it prevents the kernel from + storing the same PC multiple times. + Enabling this mode incurs a slight increase in kernel binary size. + config KCOV_ENABLE_COMPARISONS bool "Enable comparison operands collection by KCOV" depends on KCOVscripts/Makefile.kcov +7
-0@@ -1,5 +1,12 @@ # SPDX-License-Identifier: GPL-2.0-only +ifeq ($(CONFIG_KCOV_UNIQUE),y) +kcov-flags-y += -fsanitize-coverage=trace-pc-guard +# Drop per-file constructors that -fsanitize-coverage=trace-pc-guard inserts by default. +# Kernel does not need them, and they may produce unknown relocations. +kcov-flags-y += -mllvm -sanitizer-coverage-drop-ctors +else kcov-flags-y += -fsanitize-coverage=trace-pc +endif kcov-flags-$(CONFIG_KCOV_ENABLE_COMPARISONS) += -fsanitize-coverage=trace-cmp kcov-rflags-y += -Cpasses=sancov-modulescripts/module.lds.S +0
-0
scripts/module.lds.S SECTIONS { · line 50
Quoted 4 lines
scripts/module.lds.S +1
-0@@ -47,6 +47,7 @@ SECTIONS { .bss : { *(.bss .bss.[0-9a-zA-Z_]*) *(.bss..L*) + *(__sancov_guards)
This line looks like redundant?
I can boot without it both normal build and kasan build.
Quoted 28 lines
scripts/module.lds.S +21
-0} .data : {@@ -64,6 +65,40 @@ SECTIONS { MOD_CODETAG_SECTIONS() } #endif + +#ifdef CONFIG_KCOV_UNIQUE + /* + * CONFIG_KCOV_UNIQUE creates COMDAT groups for instrumented functions, + * which has the following consequences in the presence of + * -ffunction-sections: + * - Separate .init.text and .exit.text sections in the modules are not + * merged together, which results in errors trying to create + * duplicate entries in /sys/module/MODNAME/sections/ at module load + * time. + * - Each function is placed in a separate .text.funcname section, so + * there is no .text section anymore. Collecting them together here + * has mostly aesthetic purpose, although some tools may be expecting + * it to be present. + */ + .text : { + *(.text .text.[0-9a-zA-Z_]*) + *(.text..L*) + } + .init.text : { + *(.init.text .init.text.[0-9a-zA-Z_]*)
scripts/module.lds.S SECTIONS { · line 98
Quoted 10 lines
scripts/module.lds.S +10
-0+ *(.init.text..L*) + } + .exit.text : { + *(.exit.text .exit.text.[0-9a-zA-Z_]*) + *(.exit.text..L*) + } + .bss : { + *(.bss .bss.[0-9a-zA-Z_]*) + *(.bss..L*) + *(__sancov_guards)
Need to include __start___sancov_guards and __stop___sancov_guards to treat them as local, otherwise it won't boot on aarch64, error like:
Modules: module proxy_consumer: overflow in relocation type 311 val 0.
So, finally it should look like:
__start___sancov_guards = .; *(__sancov_guards) __stop___sancov_guards = .;
Quoted 21 lines
scripts/module.lds.S +3
-0+ } +#endif + MOD_SEPARATE_CODETAG_SECTIONS() }tools/objtool/check.c +1
-0@@ -1156,6 +1156,7 @@ static const char *uaccess_safe_builtin[] = {"write_comp_data" ,"check_kcov_mode" ,"__sanitizer_cov_trace_pc" , +"__sanitizer_cov_trace_pc_guard" ,"__sanitizer_cov_trace_const_cmp1" ,"__sanitizer_cov_trace_const_cmp2" , "__sanitizer_cov_trace_const_cmp4",Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 6/10 kcov: add trace and trace_size to struct kcov_state
In reply to Alexander PotapenkoKeep kcov_state.area as the pointer to the memory buffer used by kcov and shared with the userspace. Store the pointer to the trace (part of the buffer holding sequential events) separately, as we will be splitting that buffer in multiple parts.
No functional changes so far.
---
v4:
- add Reviewed-by: Dmitry Vyukov
v3:
- Fix a warning detected by the kernel test robot <[email protected]>
- Address comments by Dmitry Vyukov:
- s/kcov/KCOV/
- fix struct initialization style
v2:
- Address comments by Dmitry Vyukov:
- tweak commit description
- Address comments by Marco Elver:
- rename sanitizer_cov_write_subsequent() to kcov_append_to_buffer()
- Update code to match the new description of struct kcov_state
Change-Id: I50b5589ef0e0b6726aa0579334093c648f76790a
--- include/linux/kcov_types.h | 9 ++++++- kernel/kcov.c | 48 +++++++++++++++++++++----------------- 2 files changed, 35 insertions(+), 22 deletions(-)
include/linux/kcov_types.h +8 -1
@@ -7,9 +7,16 @@struct kcov_state {/* Size of the area (in long's). */ unsigned int size; +/* +* Pointer to user-provided memory used by KCOV. This memory may +* contain multiple buffers. +*/ +void *area; +/* Size of the trace (in long's). */ +unsigned int trace_size;/* Buffer for coverage collection, shared with the userspace. */ -void *area; +unsigned long *trace;/* * KCOV sequence number: incremented each time kcov is reenabled, used
kernel/kcov.c +27 -21
121 lines not on this page · raw message
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 7/10 kcov: add ioctl(KCOV_UNIQUE_ENABLE)
In reply to Alexander Potapenkoioctl(KCOV_UNIQUE_ENABLE) enables collection of deduplicated coverage in the presence of CONFIG_KCOV_ENABLE_GUARDS.
The buffer shared with the userspace is divided in two parts, one holding a bitmap, and the other one being the trace. The single parameter of ioctl(KCOV_UNIQUE_ENABLE) determines the number of words used for the bitmap.
Each __sanitizer_cov_trace_pc_guard() instrumentation hook receives a pointer to a unique guard variable. Upon the first call of each hook, the guard variable is initialized with a unique integer, which is used to map those hooks to bits in the bitmap. In the new coverage collection mode, the kernel first checks whether the bit corresponding to a particular hook is set, and then, if it is not, the PC is written into the trace buffer, and the bit is set.
Note: when CONFIG_KCOV_ENABLE_GUARDS is disabled, ioctl(KCOV_UNIQUE_ENABLE) returns -ENOTSUPP, which is consistent with the existing kcov code.
Measuring the exact performance impact of this mode directly can be challenging. However, based on fuzzing experiments (50 instances x 24h with and without deduplication), we observe the following:
- When normalized by pure fuzzing time, total executions decreased by 2.1% (p=0.01).
- When normalized by fuzzer uptime, the reduction in total executions was statistically insignificant (-1.0% with p=0.20).
Despite a potential slight slowdown in execution count, the new mode positively impacts fuzzing effectiveness:
- Statistically significant increase in corpus size (+0.6%, p<0.01).
- Statistically significant increase in coverage (+0.6%, p<0.01).
- A 99.8% reduction in coverage overflows.
Also update the documentation.
---
v4:
Add Reviewed-by: Dmitry Vyukov
v3:
- s/check_kcov_mode/get_kcov_mode in objtool
v2:
- Address comments by Dmitry Vyukov:
- rename CONFIG_KCOV_ENABLE_GUARDS to CONFIG_KCOV_UNIQUE
- rename KCOV_MODE_TRACE_UNIQUE_PC to KCOV_MODE_UNIQUE_PC
- simplify index allocation
- update documentation and comments
- Address comments by Marco Elver:
- change _IOR to _IOW in KCOV_UNIQUE_ENABLE definition
- rename sanitizer_cov_write_subsequent() to kcov_append_to_buffer()
- Use __test_and_set_bit() to avoid the lock prefix on the bit operation
- Update code to match the new description of struct kcov_state
- Rename kcov_get_mode() to kcov_arg_to_mode() to avoid confusion with get_kcov_mode(). Also make it use enum kcov_mode.
Change-Id: I9805e7b22619a50e05cc7c7d794dacf6f7de2f03
--- Documentation/dev-tools/kcov.rst | 43 ++++++++ include/linux/kcov.h | 2 + include/linux/kcov_types.h | 8 ++ include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 164 ++++++++++++++++++++++++++----- tools/objtool/check.c | 2 +- 6 files changed, 193 insertions(+), 27 deletions(-)
Documentation/dev-tools/kcov.rst +43 -0
@@ -192,6 +192,49 @@ Normally the shared buffer is used as follows:: up to the buffer[0] value saved above | +Unique coverage collection +--------------------------- + +Instead of collecting a trace of PCs, KCOV can deduplicate them on the fly. +This mode is enabled by the ``KCOV_UNIQUE_ENABLE`` ioctl (only available if +``CONFIG_KCOV_UNIQUE`` is on). + +.. code-block:: c + + /* Same includes and defines as above. */ + #define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long) + #define BITMAP_SIZE (4<<10) + + /* Instead of KCOV_ENABLE, enable unique coverage collection. */ + if (ioctl(fd, KCOV_UNIQUE_ENABLE, BITMAP_SIZE)) + perror("ioctl"), exit(1); + /* Reset the coverage from the tail of the ioctl() call. */ + __atomic_store_n(&cover[BITMAP_SIZE], 0, __ATOMIC_RELAXED); + memset(cover, 0, BITMAP_SIZE * sizeof(unsigned long)); + + /* Call the target syscall call. */ + /* ... */ + + /* Read the number of collected PCs. */ + n = __atomic_load_n(&cover[BITMAP_SIZE], __ATOMIC_RELAXED); + /* Disable the coverage collection. */ + if (ioctl(fd, KCOV_DISABLE, 0)) + perror("ioctl"), exit(1); + +Calling ``ioctl(fd, KCOV_UNIQUE_ENABLE, bitmap_size)`` carves out ``bitmap_size`` +unsigned long's from those allocated by ``KCOV_INIT_TRACE`` to keep an opaque +bitmap that prevents the kernel from storing the same PC twice. The remaining +part of the buffer is used to collect PCs, like in other modes (this part must +contain at least two unsigned long's, like when collecting non-unique PCs). + +The mapping between a PC and its position in the bitmap is persistent during the +kernel lifetime, so it is possible for the callers to directly use the bitmap +contents as a coverage signal (like when fuzzing userspace with AFL). + +In order to reset the coverage between the runs, the user needs to rewind the +trace (by writing 0 into the first buffer element past ``bitmap_size``) and zero +the whole bitmap. + Comparison operands collection ------------------------------
include/linux/kcov.h +2 -0
@@ -10,6 +10,7 @@ struct task_struct;#ifdef CONFIG_KCOV enum kcov_mode { +KCOV_MODE_INVALID =-1 ,/* Coverage collection is not enabled yet. */ KCOV_MODE_DISABLED =0 , /* KCOV was initialized, but tracing mode hasn't been chosen yet. */
@@ -23,6 +24,7 @@ enum kcov_mode {KCOV_MODE_TRACE_CMP =3 ,/* The process owns a KCOV remote reference. */ KCOV_MODE_REMOTE =4 , + KCOV_MODE_UNIQUE_PC = 5, };#define KCOV_IN_CTXSW (1 << 30)
include/linux/kcov_types.h +8 -0
@@ -18,6 +18,14 @@ struct kcov_state {/* Buffer for coverage collection, shared with the userspace. */ unsigned long *trace; +/* Size of the bitmap (in bits). */ +unsigned int bitmap_size; +/* +* Bitmap for coverage deduplication, shared with the +* userspace. +*/ +unsigned long *bitmap; +/* * KCOV sequence number: incremented each time kcov is reenabled, used * by kcov_remote_stop(), see the comment there.
include/uapi/linux/kcov.h +1 -0
@@ -22,6 +22,7 @@ struct kcov_remote_arg {#define KCOV_ENABLE _IO('c', 100)#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg) +#define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long)enum {/*
kernel/kcov.c +138 -26
269 lines not on this page · raw message
tools/objtool/check.c +1 -1
@@ -1154,7 +1154,7 @@ static const char *uaccess_safe_builtin[] = {"__tsan_unaligned_write16" ,/* KCOV */ "write_comp_data" , -"check_kcov_mode" , +"get_kcov_mode" ,"__sanitizer_cov_trace_pc" ,"__sanitizer_cov_trace_pc_guard" , "__sanitizer_cov_trace_const_cmp1",
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 8/10 kcov: add ioctl(KCOV_RESET_TRACE)
In reply to Alexander PotapenkoProvide a mechanism to reset the coverage for the current task without writing directly to the coverage buffer.
This is slower, but allows the fuzzers to map the coverage buffer as read-only, making it harder to corrupt.
---
v4:
- Add Reviewed-by: Dmitry Vyukov
v2:
- Update code to match the new description of struct kcov_state
Change-Id: I8f9e6c179d93ccbfe0296b14764e88fa837cfffe
--- Documentation/dev-tools/kcov.rst | 26 ++++++++++++++++++++++++++ include/uapi/linux/kcov.h | 1 + kernel/kcov.c | 15 +++++++++++++++ 3 files changed, 42 insertions(+)
Documentation/dev-tools/kcov.rst +26 -0
@@ -470,3 +470,29 @@ local tasks spawned by the process and the global task that handles USB bus #1: perror("close"), exit(1); return 0; } + + +Resetting coverage with an KCOV_RESET_TRACE +------------------------------------------- + +The ``KCOV_RESET_TRACE`` ioctl provides a mechanism to clear collected coverage +data for the current task. It resets the program counter (PC) trace and, if +``KCOV_UNIQUE_ENABLE`` mode is active, also zeroes the associated bitmap. + +The primary use case for this ioctl is to enhance safety during fuzzing. +Normally, a user could map the kcov buffer with ``PROT_READ | PROT_WRITE`` and +reset the trace from the user-space program. However, when fuzzing system calls, +the kernel itself might inadvertently write to this shared buffer, corrupting +the coverage data. + +To prevent this, a fuzzer can map the buffer with ``PROT_READ`` and use +``ioctl(fd, KCOV_RESET_TRACE, 0)`` to safely clear the buffer from the kernel +side before each fuzzing iteration. + +Note that: + +* This ioctl is safer but slower than directly writing to the shared memory + buffer due to the overhead of a system call. +* ``KCOV_RESET_TRACE`` is itself a system call, and its execution will be traced + by kcov. Consequently, immediately after the ioctl returns, cover[0] will be + greater than 0.
include/uapi/linux/kcov.h +1 -0
@@ -23,6 +23,7 @@ struct kcov_remote_arg {#define KCOV_DISABLE _IO('c', 101)#define KCOV_REMOTE_ENABLE _IOW('c', 102, struct kcov_remote_arg)#define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long) +#define KCOV_RESET_TRACE _IO('c', 104)enum {/*
kernel/kcov.c +15 -0
@@ -740,6 +740,21 @@ static int kcov_ioctl_locked(struct kcov *kcov, unsigned int cmd,return 0 ;case KCOV_UNIQUE_ENABLE :return kcov_handle_unique_enable (kcov, arg); +case KCOV_RESET_TRACE : + unused = arg; +if (unused !=0 || current->kcov != kcov) +return -EINVAL ; + t = current; +if (WARN_ON (kcov->t != t)) +return -EINVAL ; + mode = kcov->mode; +if (mode <KCOV_MODE_TRACE_PC ) +return -EINVAL ; +if (kcov->state.bitmap) +bitmap_zero (kcov->state.bitmap, + kcov->state.bitmap_size); +WRITE_ONCE (kcov->state.trace[0 ],0 ); +return 0 ;case KCOV_DISABLE :/* Disable coverage for the current task. */ unused = arg;
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 9/10 kcov: selftests: add kcov_test
In reply to Alexander PotapenkoImplement test fixtures for testing different combinations of coverage collection modes:
- unique and non-unique coverage;
- collecting PCs and comparison arguments;
- mapping the buffer as RO and RW.
To build:
$ make -C tools/testing/selftests/kcov kcov_test
---
v4:
- Per Dmitry Vyukov's request, add CONFIG_KCOV_UNIQUE=y to the list of required configs
v3:
- Address comments by Dmitry Vyukov:
- add tools/testing/selftests/kcov/config
- add ifdefs to KCOV_UNIQUE_ENABLE and KCOV_RESET_TRACE
- Properly handle/reset the coverage buffer when collecting unique coverage
Change-Id: I0793f1b91685873c77bcb222a03f64321244df8f
--- MAINTAINERS | 1 + tools/testing/selftests/kcov/Makefile | 6 + tools/testing/selftests/kcov/config | 2 + tools/testing/selftests/kcov/kcov_test.c | 401 +++++++++++++++++++++++ 4 files changed, 410 insertions(+) create mode 100644 tools/testing/selftests/kcov/Makefile create mode 100644 tools/testing/selftests/kcov/config create mode 100644 tools/testing/selftests/kcov/kcov_test.c
MAINTAINERS +1 -0
@@ -13018,6 +13018,7 @@ F: include/linux/kcov_types.h F: include/uapi/linux/kcov.h F: kernel/kcov.c F: scripts/Makefile.kcov +F: tools/testing/selftests/kcov/ KCSAN M: Marco Elver <[email protected]>
tools/testing/selftests/kcov/Makefile new file +6 -0
@@ -0,0 +1,6 @@ +# SPDX-License-Identifier: GPL-2.0-only +LDFLAGS += -static + +TEST_GEN_PROGS := kcov_test + +include ../lib.mk
tools/testing/selftests/kcov/config new file +2 -0
@@ -0,0 +1,2 @@ +CONFIG_KCOV=y +CONFIG_KCOV_UNIQUE=y
tools/testing/selftests/kcov/kcov_test.c new file +401 -0
401 lines not on this page · raw message
Signature · 1 line
2.50.1.552.g942d659e1b-goog
Re: [PATCH v4 09/10] kcov: selftests: add kcov_test
Quoted 11 lines · Alexander Potapenko
Implement test fixtures for testing different combinations of coverage collection modes:
- unique and non-unique coverage;
- collecting PCs and comparison arguments;
- mapping the buffer as RO and RW.To build:
$ make -C tools/testing/selftests/kcov kcov_testSigned-off-by Alexander Potapenko <[email protected]>
Quoted 464 lines
---
v4:
- Per Dmitry Vyukov's request, addCONFIG_KCOV_UNIQUE=yto the list of required configs
v3:
- Address comments by Dmitry Vyukov:
- addtools/testing/selftests/kcov/config
- add ifdefs toKCOV_UNIQUE_ENABLEandKCOV_RESET_TRACE
- Properly handle/reset the coverage buffer when collecting unique coverageChange-Id: I0793f1b91685873c77bcb222a03f64321244df8f
--- MAINTAINERS | 1 + tools/testing/selftests/kcov/Makefile | 6 + tools/testing/selftests/kcov/config | 2 + tools/testing/selftests/kcov/kcov_test.c | 401 +++++++++++++++++++++++ 4 files changed, 410 insertions(+) create mode 100644 tools/testing/selftests/kcov/Makefile create mode 100644 tools/testing/selftests/kcov/config create mode 100644 tools/testing/selftests/kcov/kcov_test.cMAINTAINERS +1
-0@@ -13018,6 +13018,7 @@ F: include/linux/kcov_types.h F: include/uapi/linux/kcov.h F: kernel/kcov.c F: scripts/Makefile.kcov +F: tools/testing/selftests/kcov/ KCSAN M: Marco Elver <[email protected]>tools/testing/selftests/kcov/Makefile new file +6
-0@@ -0,0 +1,6 @@ +# SPDX-License-Identifier: GPL-2.0-only +LDFLAGS += -static + +TEST_GEN_PROGS := kcov_test + +include ../lib.mktools/testing/selftests/kcov/config new file +2
-0@@ -0,0 +1,2 @@ +CONFIG_KCOV=y +CONFIG_KCOV_UNIQUE=ytools/testing/selftests/kcov/kcov_test.c new file +401
-1@@ -0,0 +1,401 @@ +// SPDX-License-Identifier: GPL-2.0 +/* +* Test the kernel coverage (/sys/kernel/debug/kcov). +* +* Copyright 2025 Google LLC. +*/ +#include <fcntl.h> +#include <linux/kcov.h> +#include <stdint.h> +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/ioctl.h> +#include <sys/mman.h> +#include <sys/types.h> +#include <unistd.h> + +#include "../kselftest_harness.h" + +/* Normally these defines should be provided by linux/kcov.h, but they aren't there yet. */ +#ifndef KCOV_UNIQUE_ENABLE +#define KCOV_UNIQUE_ENABLE _IOW('c', 103, unsigned long) +#endif +#ifndef KCOV_RESET_TRACE +#define KCOV_RESET_TRACE _IO('c', 104) +#endif + +#define COVER_SIZE (64 << 10) +#define BITMAP_SIZE (4 << 10) + +#define DEBUG_COVER_PCS 0 + +FIXTURE (kcov) +{ +int fd; +unsigned long *mapping; +size_t mapping_size; +}; + +FIXTURE_VARIANT (kcov) +{ +int mode; +bool fast_reset; +bool map_readonly; +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov, mode_trace_pc) +{ +/* clang-format on */ + .mode = KCOV_TRACE_PC, + .fast_reset = true, + .map_readonly = false, +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov, mode_trace_cmp) +{ +/* clang-format on */ + .mode =KCOV_TRACE_CMP , + .fast_reset = true, + .map_readonly = false, +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov, reset_ioctl_rw) +{ +/* clang-format on */ + .mode = KCOV_TRACE_PC, + .fast_reset = false, + .map_readonly = false, +}; + +FIXTURE_VARIANT_ADD (kcov, reset_ioctl_ro) +/* clang-format off */ +{ +/* clang-format on */ + .mode =KCOV_TRACE_PC , + .fast_reset = false, + .map_readonly = true, +}; + +int kcov_open_init (struct __test_metadata *_metadata,unsigned long size, +int prot,unsigned long **out_mapping) +{ +unsigned long *mapping; + +/* A single fd descriptor allows coverage collection on a single thread. */ +int fd =open ("/sys/kernel/debug/kcov" ,O_RDWR ); + + ASSERT_NE(fd, -1) + { +perror ("open" ); + } + + EXPECT_EQ(ioctl(fd, KCOV_INIT_TRACE, size), 0) + { +perror ("ioctl KCOV_INIT_TRACE" ); +close (fd); + } + +/* Mmap buffer shared between kernel- and user-space. */ + mapping = (unsigned long *)mmap (NULL , size *sizeof (unsigned long ), + prot,MAP_SHARED , fd,0 ); + ASSERT_NE((void *)mapping, MAP_FAILED) + { +perror ("mmap" ); +close (fd); + } + *out_mapping = mapping; + +return fd; +} + +FIXTURE_SETUP (kcov) +{ +int prot = variant->map_readonly ?PROT_READ : (PROT_READ |PROT_WRITE ); + +/* Read-only mapping is incompatible with fast reset. */ +ASSERT_FALSE (variant->map_readonly && variant->fast_reset); + + self->mapping_size =COVER_SIZE ; + self->fd =kcov_open_init (_metadata, self->mapping_size, prot, + &(self->mapping)); + +/* Enable coverage collection on the current thread. */ + EXPECT_EQ(ioctl(self->fd, KCOV_ENABLE, variant->mode), 0) + { +perror ("ioctl KCOV_ENABLE" ); +/* Cleanup will be handled by FIXTURE_TEARDOWN. */ +return ; + } +} + +void kcov_uninit_close (struct __test_metadata *_metadata,int fd, +unsigned long *mapping,size_t size) +{ +/* Disable coverage collection for the current thread. */ + EXPECT_EQ(ioctl(fd, KCOV_DISABLE, 0), 0) + { +perror ("ioctl KCOV_DISABLE" ); + } + +/* Free resources. */ + EXPECT_EQ(munmap(mapping, size * sizeof(unsigned long)), 0) + { +perror ("munmap" ); + } + + EXPECT_EQ(close(fd), 0) + { +perror ("close" ); + } +} + +FIXTURE_TEARDOWN (kcov) +{ +kcov_uninit_close (_metadata, self->fd, self->mapping, + self->mapping_size); +} + +void dump_collected_pcs (struct __test_metadata *_metadata,unsigned long *cover, +size_t start,size_t end) +{ +int i =0 ; + +TH_LOG ("Collected %lu PCs" , end - start); +#if DEBUG_COVER_PCS +for (i = start; i < end; i++) +TH_LOG ("0x%lx" , cover[i +1 ]); +#endif +} + +/* Coverage collection helper without assertions. */ +unsigned long collect_coverage_unchecked (struct __test_metadata *_metadata, +unsigned long *cover,bool dump) +{ +unsigned long before, after; + + before =__atomic_load_n (&cover[0 ], __ATOMIC_RELAXED); +/* +* Call the target syscall call. Here we use read(-1, NULL, 0) as an example. +* This will likely return an error (-EFAULT or -EBADF), but the goal is to +* collect coverage for the syscall's entry/exit paths. +*/ +read (-1 ,NULL ,0 ); + + after =__atomic_load_n (&cover[0 ], __ATOMIC_RELAXED); + +if (dump) +dump_collected_pcs (_metadata, cover, before, after); +return after - before; +} + +unsigned long collect_coverage_once (struct __test_metadata *_metadata, +unsigned long *cover) +{ +unsigned long collected = +collect_coverage_unchecked (_metadata, cover,/*dump*/ true); + +/* Coverage must be non-zero. */ +EXPECT_GT (collected,0 ); +return collected; +} + +void reset_coverage (struct __test_metadata *_metadata,bool fast,int fd, +unsigned long *mapping) +{ +unsigned long count; + +if (fast) { +__atomic_store_n (&mapping[0 ],0 , __ATOMIC_RELAXED); + }else { + EXPECT_EQ(ioctl(fd, KCOV_RESET_TRACE, 0), 0) + { +perror ("ioctl KCOV_RESET_TRACE" ); + } + count =__atomic_load_n (&mapping[0 ], __ATOMIC_RELAXED); +EXPECT_NE (count,0 ); + } +} + +TEST_F(kcov, kcov_basic_syscall_coverage) +{ +unsigned long first, second, before, after, i; + +/* Reset coverage that may be left over from the fixture setup. */ +reset_coverage (_metadata, variant->fast_reset, self->fd, self->mapping); + +/* Collect the coverage for a single syscall two times in a row. */ + first =collect_coverage_once (_metadata, self->mapping); + second =collect_coverage_once (_metadata, self->mapping); +/* Collected coverage should not differ too much. */ +EXPECT_GT (first *10 , second); +EXPECT_GT (second *10 , first); + +/* Now reset the buffer and collect the coverage again. */ +reset_coverage (_metadata, variant->fast_reset, self->fd, self->mapping); +collect_coverage_once (_metadata, self->mapping); + +/* Now try many times to fill up the buffer. */ +reset_coverage (_metadata, variant->fast_reset, self->fd, self->mapping); +while (collect_coverage_unchecked (_metadata, self->mapping, +/*dump*/ false)) { +/* Do nothing. */ + } + before =__atomic_load_n (&(self->mapping[0 ]), __ATOMIC_RELAXED); +/* +* Resetting with ioctl may still generate some coverage, but much less +* than there was before. +*/ +reset_coverage (_metadata, variant->fast_reset, self->fd, self->mapping); + after =__atomic_load_n (&(self->mapping[0 ]), __ATOMIC_RELAXED); +EXPECT_GT (before, after); +/* Collecting coverage after reset will now succeed. */ +collect_coverage_once (_metadata, self->mapping); +} + +FIXTURE (kcov_uniq) +{ +int fd; +unsigned long *mapping; +size_t mapping_size; +unsigned long *bitmap; +size_t bitmap_size; +unsigned long *cover; +size_t cover_size; +}; + +FIXTURE_VARIANT (kcov_uniq) +{ +bool fast_reset; +bool map_readonly; +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov_uniq, fast_rw) +{ +/* clang-format on */ + .fast_reset = true, + .map_readonly = false, +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov_uniq, slow_rw) +{ +/* clang-format on */ + .fast_reset = false, + .map_readonly = false, +}; + +/* clang-format off */ +FIXTURE_VARIANT_ADD (kcov_uniq, slow_ro) +{ +/* clang-format on */ + .fast_reset = false, + .map_readonly = true, +}; + +FIXTURE_SETUP (kcov_uniq) +{ +int prot = variant->map_readonly ?PROT_READ : (PROT_READ |PROT_WRITE ); + +/* Read-only mapping is incompatible with fast reset. */ +ASSERT_FALSE (variant->map_readonly && variant->fast_reset); + + self->mapping_size =COVER_SIZE ; + self->fd =kcov_open_init (_metadata, self->mapping_size, prot, + &(self->mapping)); + + self->bitmap = self->mapping; + self->bitmap_size =BITMAP_SIZE ; +/* +* Enable unique coverage collection on the current thread. Carve out +* self->bitmap_size unsigned long's for the bitmap. +*/ + EXPECT_EQ(ioctl(self->fd, KCOV_UNIQUE_ENABLE, self->bitmap_size), 0) + { +perror ("ioctl KCOV_ENABLE" ); +/* Cleanup will be handled by FIXTURE_TEARDOWN. */ +return ; + } + self->cover = self->mapping +BITMAP_SIZE ; + self->cover_size = self->mapping_size -BITMAP_SIZE ; +} + +FIXTURE_TEARDOWN (kcov_uniq) +{ +kcov_uninit_close (_metadata, self->fd, self->mapping, + self->mapping_size); +} + +void reset_uniq_coverage (struct __test_metadata *_metadata,bool fast,int fd, +unsigned long *bitmap,unsigned long *cover) +{ +unsigned long count; + +if (fast) { +/* +* Resetting the buffer for unique coverage collection requires +* zeroing out the bitmap and cover[0]. We are assuming that +* the coverage buffer immediately follows the bitmap, as they +* belong to the same memory mapping. +*/ +if (cover > bitmap) +memset (bitmap,0 ,sizeof (unsigned long ) * (cover - bitmap)); +__atomic_store_n (&cover[0 ],0 , __ATOMIC_RELAXED); + }else { + EXPECT_EQ(ioctl(fd, KCOV_RESET_TRACE, 0), 0) + { +perror ("ioctl KCOV_RESET_TRACE" ); + } + count =__atomic_load_n (&cover[0 ], __ATOMIC_RELAXED); +EXPECT_NE (count,0 ); + } +} + +TEST_F(kcov_uniq, kcov_uniq_coverage) +{ +unsigned long first, second, before, after, i; + +/* Reset coverage that may be left over from the fixture setup. */ +reset_uniq_coverage (_metadata, variant->fast_reset, self->fd, self->bitmap, self->cover); + +/* +* Collect the coverage for a single syscall two times in a row. +* Use collect_coverage_unchecked(), because it may return zero coverage. +*/ + first =collect_coverage_unchecked (_metadata, self->cover, +/*dump*/ true); + second =collect_coverage_unchecked (_metadata, self->cover, +/*dump*/ true); + +/* Now reset the buffer and collect the coverage again. */ +reset_uniq_coverage (_metadata, variant->fast_reset, self->fd, self->bitmap, self->cover); +collect_coverage_once (_metadata, self->cover); + +/* Now try many times to saturate the unique coverage bitmap. */ +reset_uniq_coverage (_metadata, variant->fast_reset, self->fd, self->bitmap, self->cover); +for (i =0 ; i <1000 ; i++) +collect_coverage_unchecked (_metadata, self->cover, +/*dump*/ false); + +/* Another invocation of collect_coverage_unchecked() should not produce new coverage. */ +EXPECT_EQ (collect_coverage_unchecked (_metadata, self->cover, +/*dump*/ false), +0 ); + + before =__atomic_load_n (&(self->cover[0 ]), __ATOMIC_RELAXED); +/* +* Resetting with ioctl may still generate some coverage, but much less +* than there was before. +*/ +reset_uniq_coverage (_metadata, variant->fast_reset, self->fd, self->bitmap, self->cover); + after =__atomic_load_n (&(self->cover[0 ]), __ATOMIC_RELAXED); +EXPECT_GT (before, after); +/* Collecting coverage after reset will now succeed. */ +collect_coverage_once (_metadata, self->cover); +} + +TEST_HARNESS_MAIN --2.50.1.552.g942d659e1b-goog
Alexander Potapenko
reviewerPATCH v4 10/10 kcov: use enum kcov_mode in kcov_mode_enabled()
In reply to Alexander PotapenkoReplace the remaining declarations of unsigned int mode with enum kcov_mode mode. No functional change.
---
v4:
- Add Reviewed-by: Dmitry Vyukov
Change-Id: I739b293c1f689cc99ef4adbe38bdac5813802efe
--- kernel/kcov.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/kcov.c +3 -3
@@ -949,7 +949,7 @@ static const struct file_operations kcov_fops = {* collecting coverage and copies all collected coverage into the kcov area. */ -static inline bool kcov_mode_enabled (unsigned int mode) +static inline bool kcov_mode_enabled (enum kcov_mode mode) {return (mode & ~KCOV_IN_CTXSW ) !=KCOV_MODE_DISABLED ; }
@@ -957,7 +957,7 @@ static inline bool kcov_mode_enabled(unsigned int mode)static void kcov_remote_softirq_start (struct task_struct *t) {struct kcov_percpu_data *data =this_cpu_ptr (&kcov_percpu_data); -unsigned int mode; +enum kcov_mode mode; mode =READ_ONCE (t->kcov_mode);barrier ();
@@ -1134,7 +1134,7 @@ void kcov_remote_stop(void) {struct task_struct *t = current;struct kcov *kcov; -unsigned int mode; +enum kcov_mode mode;void *area;unsigned int size;int sequence;
Signature · 1 line
2.50.1.552.g942d659e1b-goog