Testing race conditions with memory access tracing and stack-based delay injection

Many security bugs are race conditions, where multi-threaded execution has to occur with the right interleaving for a negative effect to appear. This creates challenges for several use cases: Confirming bug candidates that have been discovered manually or through static analysis. Regression tests: After fixing a race condition bug, there is often no good way to write a regression test that reliably triggers the bug as part of a test suite. Automatic bug discovery, such as fuzzing: It is hard for a fuzzer to exercise all interesting interleavings of concurrent operations, or reach code paths that are only exercised when operations are racing. I mostly discover bugs by manually reading code. When I think I’ve found a bug, I normally write a test case to either prove or disprove that the bug exists. For race condition bugs, it can be hard to achieve either outcome. For Linux kernel bugs, I often resort to recompiling the kernel after adding conditional mdelay() calls (which spinloop for roughly the specified amount of time) in appropriate places; I usually make these conditional based on the name of the running thread, though sometimes more complex conditions are needed. On platforms that support DTrace (like macOS and Windows), it is possible to use DTrace probes that call chill() for similar effect, though the utility of this is limited as DTrace can only trace on non-inline function boundaries or explicit trace points, rather than on every instruction. Regardless of platform, this approach can be time consuming and can require trial and error to definitely determine whether code is buggy. Additionally, in the Linux kernel, fixes for race condition bugs are often accompanied by hand-written ASCII diagrams showing problematic thread interleavings with call graphs and relevant memory accesses (for example, see this recent rt_spin_unlock UAF fix, or this recent jbd2 deadlock fix). It would be convenient to have developer tooling that can analyze potentially vulnerable code and show results in a similar representation. Summary I wrote tools for exploring possible interleavings of multi-threaded test cases for the Linux kernel: A tool that automatically tests all possible A-B-A interleavings of a test case. A terminal UI for manual exploration of possible interleavings. A GUI for manual exploration of possible interleavings. The kernel part of this is intended to also be usable for discovering race conditions via fuzzing, but userspace tooling for that still needs to be implemented. The tools are available on GitHub under the name MAccConc, short for “Memory Access Concurrency”; see the README there for installation and usage instructions. If you just want to see the tooling in action, skip to Demo: automatic testing. If you’re just interested in the theory behind the tooling, read 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 involved exploration of concurrency bugs by using a custom scheduler that can reschedule at synchronization primitives to explore interleavings. See the conference talk slides and recording focused on the concurrency testing aspect of this. My tooling is largely based on ideas similar to SKI, but SKI uses a different implementation: It records memory accesses and controls scheduling of vCPUs using a patched version of QEMU in TCG mode, and uses VM snapshots to explore different execution interleavings. Discovering memory accesses that could contribute to race conditions (communication points) As described in the SKI paper, interesting execution interleavings of a given multi-threaded test case can be discovered by tracing memory accesses of all threads and searching for pairs of accesses on two threads that could interact with each other - meaning, roughly, that at least one of them is a write operation, and they access overlapping memory ranges. The SKI paper calls such memory accesses communication points. This requires some mechanism to collect memory access coverage. SKI did this by patching QEMU’s TCG mode; I am instead relying on ASAN instrumentation in “outline” mode (compiler backend flag asan-instrumentation-with-call-threshold=0, selected by CONFIG_KASAN_OUTLINE in the Linux kernel), which generates helper function calls on memory access. I believe that the kernel is the right place to collect this data because it would allow the kernel to also provide higher-level information about lock acquire/release events and such, though I have not implemented this at this time. Implementing this in the kernel also means that it would theoretically be possible to test on bare-metal hardware, rather than inside VMs. Since Linux already has KCOV as a mechanism to feed basic block kernel coverage information to userspace, I decided to use the same mechanism to record information about memory accesses. An alternative would have been to use ftrace, which is oriented towards tracing use cases, and includes a function graph tracing mode built on fentry hooks and more complex output buffer management that is oriented towards use cases including system-wide data collection. I chose to use KCOV because of its simpler in-memory representation of trace data (which could become relevant for recovering trace data from crashed VMs); because it uses static always-on instrumentation rather than runtime-enabled instrumentation with near-zero overhead in disabled state; and because my impression is that KCOV is designed for higher-frequency trace events than ftrace. Implementation detail: ASAN and TSAN ASAN normally merges helper calls for subsequent memory accesses. To receive one callback per memory access, the kernel patches explicitly disable this compiler optimization using the asan-opt-same-temp backend flag. ASAN is intended for identifying UAF, so it does not emit helper calls on direct stack memory access unless there is potential for out-of-bounds access. This means that some race conditions involving on-stack objects, such as wait queues, may not be detectable with this. ASAN also by default emits no helper calls for access to globals, but this optimization can be disabled using the asan-opt-globals backend flag. An alternative would be to use TSAN instrumentation instead, which is designed for detecting data races and also provides information about access atomicity. The downside of TSAN instrumentation is that compilers do not support emitting both ASAN and TSAN hooks at the same time - so to still have working 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 change the compiler. Implementation detail: KCOV and background work Some race conditions involve background work, for example: receive processing of loopback network packets RCU callbacks KCOV can optionally collect remote coverage for background work in some subsystems; however, in upstream Linux, most types of background work that would be interesting for me are not yet integrated with this mechanism, and remote coverage is currently mainly used for fuzzing subsystems that handle incoming data from devices, like bluetooth and USB. Enabling this for other parts of the kernel should be relatively straightforward, and I have a draft patch for doing this for RCU callbacks. Stable identifiers for memory accesses across runs: count-augmented stack traces To test out different orderings of memory accesses, a way to stably identify interesting memory accesses across test case executions is needed. Identifying memory accesses based on the data address would not work if the data address was located in an object which is freshly allocated during each test case execution; and identifying memory accesses solely by instruction address would not work well if the memory access was in a function like memcpy() or spin_lock(). SKI solves this using VM state snapshots, so that each execution starts from the same global state. I am instead identifying memory accesses with count-augmented stack traces, where each stack trace element essentially consists of a callee function address and a number indicating how many calls to this callee should be skipped in the calling stack frame. An example of the semantics of a count-augmented stack trace would be something like: “On this thread, look at 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 then within that, the first memory access at instruction address X”. This unambiguously identifies a point in an execution trace, is independent of concrete data addresses, and is relatively stable with regards to changes in the control flow of irrelevant parts of the trace. To make this work, KCOV must provide information about function entry/exit events so that when userspace is parsing KCOV coverage output, it can keep track of how the call stack changes. Doing this nicely requires compiler support as part of SanitizerCoverage; I landed an LLVM feature patch for this a few months ago (see documentation), which landed in the LLVM 23.1.0 release. Forcing execution orderings with delay injection To force specific execution orderings through KCOV, I implemented an ioctl KCOV_SET_DI using which userspace can request that actions (essentially wait/wake) are taken on memory accesses at specific count-augmented stack traces. (See documentation in my kernel branch.) Each action either sets one flag, or waits for one flag to be set, at a userspace-provided index in a shared array of flags. The possible action types are: DI_STACK_WAKE_PRE: before the memory access, set flag N