Race conditions, a common type of security vulnerability, arise from the unpredictable interleaving of multi-threaded execution. This poses significant challenges for several key areas:
- Bug Confirmation: Verifying potential bug candidates identified manually or through static analysis can be difficult.
- Regression Testing: After fixing a race condition, creating a reliable regression test that consistently triggers the bug within a test suite is problematic.
- Automatic Bug Discovery: Fuzzing tools struggle to explore all critical interleavings of concurrent operations or reach code paths that are only exposed when operations race.
My primary method for discovering bugs has been manual code review. When I suspect a race condition, I typically write a test case to confirm or refute its existence. However, for race conditions, achieving either outcome can be challenging.
For Linux kernel bugs, I often resort to recompiling the kernel and inserting conditional mdelay() calls (which introduce a spin-loop for a specified duration) at strategic locations. These delays are usually conditional on the running thread's name, though more complex conditions are sometimes necessary. On systems supporting DTrace (like macOS and Windows), DTrace probes can be used to call chill() for a similar effect. However, DTrace's utility is limited as it can only trace at non-inline function boundaries or explicit trace points, not at every instruction. Regardless of the platform, this approach is time-consuming and requires trial and error to definitively confirm a bug.
Furthermore, in the Linux kernel, fixes for race condition bugs are frequently accompanied by hand-drawn ASCII diagrams illustrating problematic thread interleavings, complete with call graphs and relevant memory accesses. Examples include a recent rt_spin_unlock UAF fix and a recent jbd2 deadlock fix. It would be highly beneficial to have developer tools capable of analyzing potentially vulnerable code and presenting results in a similar visual format.
Summary
I have developed tools to explore possible interleavings of multi-threaded test cases for the Linux kernel:
- A tool that automatically tests all possible A-B-A interleavings of a given test case.
- A terminal user interface for manual exploration of possible interleavings.
- A graphical user interface for manual exploration of possible interleavings.
The kernel component is intended for discovering race conditions via fuzzing, though userspace tooling for this purpose is still under development.
The tools are available on GitHub under the name MAccConc, short for “Memory Access Concurrency.” The README file provides detailed installation and usage instructions.
For a demonstration of the tooling in action, please refer to the section Demo: automatic testing.
For those interested in the theoretical underpinnings of the tooling, please read the section Stable identifiers for memory accesses across runs: count-augmented stack traces.
Prior work
This project was inspired by discussions with Ned Williamson, whose sockfuzzer project explored concurrency bugs using a custom scheduler that could reschedule at synchronization primitives to explore interleavings. Relevant resources include the conference talk slides and recording, which focus on the concurrency testing aspect.
My tooling is largely based on concepts similar to SKI, but SKI employs a different implementation. It records memory accesses and controls vCPU scheduling using a patched QEMU in TCG mode, utilizing VM snapshots to explore different execution interleavings.
Discovering memory accesses that could contribute to race conditions (communication points)
As detailed in the SKI paper, interesting execution interleavings of a multi-threaded test case can be found by tracing memory accesses across all threads and identifying pairs of accesses on different threads that could interact. This interaction is defined as at least one access being a write operation and both accesses targeting overlapping memory ranges. The SKI paper refers to such memory accesses as communication points.
This requires a mechanism for collecting memory access coverage. SKI achieved this by patching QEMU's TCG mode. My approach, however, relies on ASAN instrumentation in “outline” mode (compiler backend flag asan-instrumentation-with-call-threshold=0, selected by CONFIG_KASAN_OUTLINE in the Linux kernel). This mode generates helper function calls for memory accesses. I believe the kernel is the appropriate place to collect this data, as it would allow the kernel to provide higher-level information about lock acquire/release events, although I have not yet implemented this. Implementing this within the kernel also theoretically enables testing on bare-metal hardware rather than solely within VMs.
Since Linux already provides KCOV for feeding basic block kernel coverage information to userspace, I decided to leverage the same mechanism for recording memory access information. An alternative would have been to use ftrace, which is designed for tracing use cases and includes a function graph tracing mode built on fentry hooks and more complex output buffer management suitable for system-wide data collection. I chose KCOV due to its simpler in-memory representation of trace data (which could be beneficial for recovering trace data from crashed VMs), its use of static always-on instrumentation rather than runtime-enabled instrumentation with near-zero overhead in its disabled state, and my impression that KCOV is designed for higher-frequency trace events than ftrace.
Implementation detail: ASAN and TSAN
ASAN typically merges helper calls for consecutive memory accesses. To ensure a separate callback for each memory access, the kernel patches explicitly disable this compiler optimization using the asan-opt-same-temp backend flag.
ASAN is primarily intended for identifying Use-After-Free (UAF) vulnerabilities and therefore does not emit helper calls for direct stack memory access unless there's a potential for out-of-bounds access. This means some race conditions involving on-stack objects, such as wait queues, might not be detectable with this method. By default, ASAN also emits no helper calls for global variable access, but this optimization can be disabled using the asan-opt-globals backend flag.
An alternative would be to use TSAN instrumentation, which is designed for detecting data races and provides information about access atomicity. However, compilers do not support emitting both ASAN and TSAN hooks simultaneously. Therefore, to maintain detection of memory safety violations (like UAF) while using TSAN hooks, it would be necessary to run the kernel's ASAN implementation off of the TSAN hooks or modify the compiler.
Implementation detail: KCOV and background work
Some race conditions involve background work, such as:
- Receive processing of loopback network packets
- RCU callbacks
KCOV can optionally collect remote coverage for background work in certain subsystems. However, in upstream Linux, most types of background work relevant to my use case are not yet integrated with this mechanism. Remote coverage is currently primarily used for fuzzing subsystems that handle incoming data from devices, such as Bluetooth and USB.
Enabling this for other parts of the kernel should be relatively straightforward. I have a draft patch for implementing this for RCU callbacks.
Stable identifiers for memory accesses across runs: count-augmented stack traces
To effectively test different orderings of memory accesses, a stable method for identifying interesting memory accesses across test case executions is required. Identifying memory accesses by their data address would be ineffective if the data address resided within an object that is newly allocated in each test case execution. Similarly, identifying memory accesses solely by instruction address would not work well for functions like memcpy() or spin_lock().
SKI addresses this by using VM state snapshots, ensuring each execution begins from the same global state. My approach, conversely, identifies memory accesses using count-augmented stack traces. Each element in a stack trace consists of a callee function address and a count indicating how many calls to that callee should be skipped within the calling stack frame.
For example, a count-augmented stack trace might semantically represent: “On this thread, consider the second call to __x64_sys_recvfrom, then within that, the first call to __sys_recvfrom, then within that, the first call to sock_recvmsg, then within that, the first call to unix_stream_recvmsg, then within that, the first call to unix_stream_read_generic, then within that, the second call to _raw_spin_unlock, and finally, the first memory access at instruction address X.”
This method uniquely identifies a point within an execution trace, is independent of concrete data addresses, and remains relatively stable against changes in the control flow of irrelevant parts of the trace.
To facilitate this, KCOV must provide information about function entry and exit events. This allows userspace, when parsing KCOV coverage output, to track changes in the call stack. This functionality requires compiler support as part of SanitizerCoverage. I integrated an LLVM feature patch for this, which was included in the LLVM 23.1.0 release (see documentation).
Forcing execution orderings with delay injection
To enforce specific execution orderings through KCOV, I implemented an ioctl called KCOV_SET_DI. This ioctl allows userspace to request actions (essentially wait/wake operations) on memory accesses identified by specific count-augmented stack traces. (Refer to the documentation in my kernel branch for details.) Each action either sets a flag or waits for a flag to be set at a userspace-specified index in a shared flag array. The available action types are:
DI_STACK_WAKE_PRE: Set flag N before the memory access.DI_STACK_WAIT: Spin-wait until flag N is set before the memory access.DI_STACK_WAKE_POST: Set flag N after the memory access.
With the same ioctl, userspace also configures an upper limit for spin-wait iterations. Additionally, there are ioctls for direct user interaction with these flags.
This API supports two distinct methods for delay injection:
Constraint-style delay injection (A-happens-before-B)
Userspace can establish a series of A-happens-before-B constraints. Each constraint is implemented as a pair of actions in different threads that operate on the same flag:
DI_STACK_WAKE_POSTfor the access that should occur first.DI_STACK_WAITfor the access that should occur second.
This approach leaves the execution ordering partially non-deterministic, which is currently implemented by the GUI and terminal UI tools. An advantage is its relative intuitiveness for simpler scenarios. However, it necessitates recording timing information to present the user with an approximate order of events and can complicate the execution trace. It often requires more constraints than a fully specified ordering and is more complex to reason about.
Fully specified ordering (context-switch-style)
Userspace can dictate a precise ordering of events by selecting points at which execution should transfer between contexts. For a simple case with two execution contexts, this involves thread A initiating a syscall while thread B begins by spin-waiting on a flag. When thread A reaches a specific count-augmented stack trace, it uses a combination of DI_STACK_WAKE_PRE and DI_STACK_WAIT to pause its execution and allow thread B to proceed. Later, thread B can perform a similar action to switch execution back to thread A.
This is the method employed for the automatic A-B-A interleaving tester.
Demo: automatic testing
I will provide more background information below, but first, here are two demonstrations of the automatic A-B-A interleaving tester using a toy example.
This example demonstrates the automatic A-B-A interleaving tester applied to a test case involving concurrent dup(5) and close(5) calls:
#define _GNU_SOURCE
#include
#include
#include
#include
#include
#include
static int test_fd;
static int dup_res, dup_errno;
void test_setup(void) {
test_fd = open("/", O_PATH);
}
void test_thread1(void) {
dup_res = dup(test_fd);
dup_errno = errno;
}
void test_thread2(void) {
close(test_fd);
}
void test_end(void) {
printf("dup(%d) = %d (%s)\n",
test_fd,
dup_res,
dup_res == -1 ? strerror(dup_errno) : "success");
}
It discovers one ordering where dup(5) returns 5, which, while functional, might be an unexpected result:
sh-5.3# ./kcov-autorace testcase/demo-dup-vs-close.so
loading kallsyms
RCU state (excluded): base=ffffffff82970100 len=500
loading testcase
initializing kcov
collecting A-B coverage
dup(5) = 6 (success)
testing candidates
dup(5) = -1 (Bad file descriptor)
dup(5) = -1 (Bad file descriptor)
dup(5) = -1 (Bad file descriptor)
dup(5) = 5 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
dup(5) = 6 (success)
stats: injection-failed:0 wait-timeout:7 reordered:4
sh-5.3#
Demo: GUI
Here is an example of using the GUI on the same test case, manually forcing an ordering where dup(7) returns 7.
First, I launch the GUI and then run the test case once in the guest:
sh-5.3# ./kcov-vsock-client testcase/demo-dup-vs-close.so
dup(7) = 8 (success)
At this point, no ordering constraints are enforced; dup() and close() are racing randomly. The GUI displays the order in which events occurred:
This view shows function call graphs for both threads (thread 1 in black indent, thread 2 in red indent). The close() syscall happened to execute after dup() in this instance. Normal functions are displayed in black; inline functions are shown in green but only if they called a normal function (as the “all inline functions” option is not selected).
Selecting “filter to communication points” reveals several memory accesses in blue, which are identified as communication points (briefly, reads from locations written to by other threads and writes to locations accessed by other threads; kfree() is considered a write operation). Each memory access line indicates the type of access (Read/Write/Free), data address, access size, and the memory value before the access. Hovering over an access highlights all overlapping accesses in yellow.
Left-clicking on a memory access filters the view to show only memory accesses that overlap with the selected access. Note that this can include reads not initially identified as communication points (because all writes occur on the same thread). This view is filtered to show accesses to the files_struct::file_lock.
Left-clicking a function name displays a source code view on the right, interspersed with trace data. Data values loaded by memory reads are shown in red (aligned with the source line and column attributed by the compiler to the access); data writes are similarly marked with a red “WRITE”; memory accesses that are communication points are prefixed with “INTERFERENCE” in orange. Function calls are shown in blue.
By right-clicking on two memory accesses in the call graph view, it is possible to establish an ordering constraint between them, ensuring the first selected access occurs before the second. Each ordering constraint is displayed on the right, represented by two count-augmented stack traces. Note that the last element at the bottom of the stack identifies a specific instruction, though the UI does not explicitly show this. The count-augmented stack traces presented here do not include inline functions.
In this scenario, ordering constraints have been defined, but the test case has not yet been executed with these constraints. The view is filtered to show accesses to the files_struct::file_lock.
Re-running the test case now yields:
sh-5.3# ./kcov-vsock-client testcase/demo-dup-vs-close.so
dup(7) = 7 (success)
The new trace appears in the UI, with brown “DELAY INJECTION” lines indicating how the ordering constraints were applied. The UI displays event orderings based on timing information associated solely with memory accesses; the placement of other events is inferred. In views filtered by data accesses, function entry events are shown only at the time of the first displayed non-function-entry event. For instance, in the following screenshot, the first thread might have already entered get_unused_fd_flags() by the time file_close_fd() called spin_unlock(), even though the events are displayed in reverse order. However, memory accesses should be shown in approximately the correct sequence, with the caveat that the order of memory accesses might be inaccurate if events occurred at the same clock value, and that timing information is recorded by instrumentation that runs immediately before the actual access. (Using fully specified orderings instead would mitigate such caveats.) This view is filtered to show accesses to the file descriptor table entry.
More detailed documentation is available within the GUI.
Implementation status
For LLVM: The necessary patch has been integrated into LLVM 23.1.0.
For the Linux kernel: The required patches are not yet part of the upstream kernel. I am submitting the Linux kernel patch series for upstream review concurrently with this blog post. A git branch containing my patches is also available on GitHub (with a few additional patches not yet ready for upstreaming). If you wish to test this tooling, you will need to use my kernel branch for the time being. (Refer to the README in the tools repository for build instructions.)
My kernel patches are in a clean state; the userspace tooling, particularly the GUI implementation, is somewhat more rudimentary.
The command-line tooling supports only two concurrent threads, whereas the GUI can handle additional execution contexts (using the kcov-vsock-client harness for background work initiated by thread A).
I am eager to learn if this tooling proves useful to others and what innovative tools might be developed based on it. Please feel free to contact me (e.g., via email at maccconc-tooling@google.com).
Future work
Use fully specified orderings instead of constraint-style for manual tooling
The non-automatic tooling currently employs constraint-style delay injection. However, as discussed, fully specified orderings offer several advantages, including more deterministic behavior. I may transition the GUI implementation to use fully specified orderings in the future.
Type information for human-readable memory access traces
For human readability of memory access traces, providing information about the types of objects being accessed would be beneficial. One approach would be to emulate Microsoft's debugging tools with CodeView debuginfo by using debuginfo to associate memory allocation function call sites with type information, and then have the allocator track the call sites from which objects were allocated.
I proposed adding such a feature to the DWARF standard, which has been accepted and is included in the current DWARF 6 draft (search for DW_AT_alloc_type). I have also added sufficient support to LLVM to enable it in cases where it previously worked with CodeView. However, this currently only supports C++ new calls; I have not yet implemented the necessary changes for malloc.
Implementing this in the kernel would require infrastructure that either queries allocator metadata for every memory access record or provides an initial snapshot of system-wide heap allocator metadata along with metadata for subsequent memory allocations.
Higher-level memory access feedback
An inefficiency in my current prototype is the lack of semantic information about locking operations provided to userspace. If two threads perform numerous memory accesses on an object while holding a lock protecting it, this generates a large number of potential communication points. In reality, a locked section represents a single, unified communication point. It would be advantageous if the kernel provided events such as “lock acquired” and “lock about to be released.”
However, this might not be a universally applicable approach, as impossible orderings caused by locking are not fundamentally different from impossible orderings arising from scenarios like an object being initialized before it is published via a global pointer.
Detecting impossible orderings faster: Deadlock detection
In my current implementation, attempting to enforce an impossible ordering through delay injection results in one thread spinning/waiting on a lock until another thread reaches its delay injection timeout, which is inefficient. Integrating with lock debugging infrastructure to detect such semi-deadlocks in simpler cases and abort the test case more quickly could be beneficial.
Fuzzing: Building up test cases with potential communication points like Snowboard
Snowboard, a project that identifies concurrency bugs caused by interactions between single-threaded test cases generated by fuzzers, utilized recorded memory access information from single-threaded test cases to pinpoint test cases with potential communication points when executed in parallel. It would be interesting to build a similar system on top of this KCOV-based instrumentation.
It might also be valuable for single-threaded test case creation: begin by collecting memory access coverage for individual system calls, then use this data to identify which syscalls might interact in interesting ways when executed sequentially, and subsequently construct longer system call sequences.
This would be more feasible using VM snapshots (similar to SKI), as my approach does not yield stable data addresses across test case executions. However, it might be achievable by abstractly identifying memory locations that differ between test cases based on allocation sites, provided that allocation site information is available for all objects allocated per test case execution.
KCOV output to host-shared memory
My current tooling loses KCOV output if the kernel under test panics, rendering it unusable for diagnosing kernel crashes. For use cases involving a KVM guest, providing the host with direct access to the KCOV output buffer could be advantageous. One method might involve using pages in a file on virtiofs with DAX as the KCOV output buffer, enabling writes of KCOV output into userspace-provided pages.
