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.
... continue reading