[Paper Reading] “SegFuzz: Segmentizing Thread Interleaving to Discover Kernel Concurrency Bugs through Fuzzing”

Introduction

This post looks at SegFuzz, a kernel concurrency fuzzer that treats thread interleaving itself as a coverage metric. It was published at IEEE S&P 2023 by KAIST and Seoul National University.

Paper: [SegFuzz: Segmentizing Thread Interleaving to Discover Kernel Concurrency Bugs through Fuzzing](https://lifeasageek.github.io/papers/jeong-segfuzz.pdf) (IEEE S&P 2023)

Code: https://github.com/casys-kaist/segfuzz

The paper decomposes a thread interleaving into interleaving segments, each covering at most four memory-accessing instructions, and uses the set of those segments as a new coverage metric called interleaving segment coverage. On top of that it applies mutation — flipping the execution order inside an already-observed segment — to derive unexplored interleavings ahead of time, and then forces them to run from the hypervisor layer.

The result: 21 new concurrency bugs across Linux 5.19-rc2 through 6.2, and known bugs reproduced 4.1× faster on average than state-of-the-art approaches.

Background

Coverage-guided kernel fuzzing, of which Syzkaller is the canonical example, generates and runs random system call sequences and uses code coverage such as branch coverage to decide whether an input reached a new execution path. The problem is that this only measures the path a single thread took. The concurrent aspect — the order in which two threads interleaved — never shows up in coverage, so you can run the same code path thousands of times and still never hit the one interleaving that triggers the bug.

thread interleaving: the order in which instructions from multiple threads end up interleaved during execution **interleaving coverage: a coverage metric that tracks the distinct patterns of those interleavings **Notation: X ⇒ Y means X executed before Y. The X → Y that appears later is different — it denotes the write→read pair that alias coverage records.

How prior work approaches this

Several concurrency fuzzers already start from this same observation. They differ along two axes.

Interleaving exploration. Razzer and Snowboard pick a single pair of instructions per run and enforce the order of just those two. KRACE injects random delays at runtime to induce random scheduling, and Conzzer designates two functions and runs them concurrently.

Interleaving coverage metric. KRACE's alias coverage is the representative one. It tracks the execution order of two instructions — specifically a directed-instruction pair IW → IR, where IR reads a value written by IW. Conzzer works at a coarser granularity, using pairs of concurrently-executed functions (concurrent call pairs) as its metric.

Motivation: CVE-2017-17712

The paper uses CVE-2017-17712 to expose the limits of these approaches, and derives its design goals from there.

![Code snippet for CVE-2017-17712]()

Figure 1. Code snippet for CVE-2017-17712. The vertical positions across the two columns are layout only and do not imply execution order; the red labels A2, A4 and B1 mark the accesses involved in triggering the bug. (Fig. 1 in the paper)

If inet->hdrincl starts at 1, thread A reads it at A2, the condition is false, and rfv is never initialized. But if thread B's B1 slips in between A2 and A4 and sets the value to 0, the condition at A4 becomes true and A5 passes the uninitialized rfv straight through. That produces an uninitialized stack pointer, and the paper notes that with a dedicated attack technique on top an attacker can escalate all the way to root.

For the bug to manifest, three instructions have to line up in exactly the order A2 ⇒ B1 ⇒ A4. From this the paper derives two design goals.

Design goal 1: informative interleaving coverage.

Compare these two interleavings:

(a) B1 ⇒ A2 ⇒ A4 — no bug
(b) A2 ⇒ B1 ⇒ A4 — bug

Figure 2. Interleaving (a), where the bug does not manifest, and (b), where it does. The bug-irrelevant accesses A6 and B2 are omitted. (Fig. 2 in the paper)

A coverage metric has to tell these two apart. Under alias coverage it does not. Running (a) first records two pairs, (B1 → A2) and (B1 → A4). Running (b) afterwards yields no new coverage at all, because (B1 → A4) has already been seen. The fuzzer concludes there is nothing left to gain from this input and moves on — while the bug sits right there in that interleaving. Concurrent call pairs hit the same wall: both interleavings happen inside raw_sendmsg() and do_ip_setsockopt(), so function-level tracking cannot separate them.

Tracking more instructions is not a free win, of course. Track thousands and the coverage space explodes past any tractable search complexity. The real design question is where to strike the balance between bug-finding capability and search complexity.

Design goal 2: speculative interleaving exploration.

Once (a) has run, we know that B1, A2 and A4 all touched the same memory object and executed in that order. From that alone we can work out before running anything that flipping B1 and A2 yields (b). So instead of hammering random executions thousands of times, we can invert the observed execution to compute the next interleaving worth trying and run it directly.

None of the four tools above meets this second goal. Razzer and Snowboard are coverage-oblivious — they use no interleaving coverage and fall back on heuristics. KRACE has coverage but spends it only on deciding whether to keep running an input, leaving the scheduling itself random. Conzzer controls things at function granularity and does not consider instruction order inside them. The paper's summary: "existing approaches do not systematically search for thread interleavings, and execute redundant thread interleavings."

Methodology

0. System Overview

Figure 3. Overall architecture of SegFuzz. Single-thread fuzzing on the left, multi-thread fuzzing on the right. (Fig. 7 in the paper)

SegFuzz splits fuzzing into two stages.

Single-thread fuzzing: generates and runs system call sequences like a conventional fuzzer, widening execution paths with branch coverage. Along the way it records memory accesses with timestamps and picks out system call pairs likely to expose new interleaving segments if run concurrently.
Multi-thread fuzzing: splits the handed-off input across two threads and runs it repeatedly, varying the interleaving, accumulating interleaving segment coverage.

The core contribution lives in the second stage, which runs in three steps:

decompose the observed interleaving into segments
mutate the order inside each segment to produce unexplored interleavings
recompose the mutated segments into an actual schedule

1. Multi-thread Fuzzing: Input Transformation and Bug Detection

When single-thread fuzzing hands over a system call pair (Si, Sj), the multi-thread generator transforms the single-thread input I_ST into a multi-thread input I_MT. The split rule is simple: everything from the first call through Si goes to one thread, the rest to the other, and every call except Si and Sj runs in the same order as in I_ST. Only Si and Sj are designated to run concurrently. For the CVE above, a sequence of socket(), setsockopt() and sendmsg() splits into a thread handling socketsetsockopt and a thread handling sendmsg, with only setsockopt and sendmsg running at the same time.

Bug detection is not something the fuzzer does itself — it delegates to the kernel's own developer tooling. During execution the multi-thread executor watches whether lockdep, the kernel watchdog, or the sanitizers report memory corruption or a deadlock; if one of them fires, it records the report together with I_MT and the interleaving that ran. Anything those tools catch — use-after-free, hangs — arrives through this path. If nothing fires, it computes the set of segment graphs produced by this run (call it G'), folds that into coverage, and feeds it back to the generator for the next round of interleaving exploration.

How G' is computed, and how the generator turns it into the next schedule, is what the rest of this section covers.

2. Interleaving Segment: Decomposing the Interleaving

The paper handles the exponentially growing search space through problem decomposition.

The segment size comes from an existing survey. According to it, 92.4% (97 of 105) concurrency bugs manifest from the execution order of at most four accesses to shared memory. The authors checked whether that still holds on recent kernels: of 15 recent concurrency-bug patches they analyzed, 14 were triggered by at most four memory accesses, and only 6 by at most two. That number is exactly why tracking only two instructions, as alias coverage does, falls short.

So an interleaving segment is defined as an interleaving over at most four memory-accessing instructions. In the CVE above, A2, A4 and B1 are involved in the bug while A6 and B2 are not; decomposition produces a separate segment holding just those three relevant accesses. Segments mixing in irrelevant accesses get produced too, but the whole design cuts the problem down under the assumption that "accesses beyond four, and their ordering, do not meaningfully contribute to manifestation."

Figure 4. Interleaving segments (b) extracted from a single execution (a). Red circles are the instructions involved in triggering the bug. (Fig. 3 in the paper)

As Figure 4 shows, one execution yields three segments: #1 (B1, A2, A4), #2 (B1, A2, A6, B2), and #3 (B1, A4, A6, B2).

3. Interleaving Segment Coverage

3-1) Representing an interleaving as a graph

The full executed interleaving is first represented as a DAG. Vertices are memory-accessing instructions; edges are execution order. There are two kinds of edge.

program-order edge: the order among accesses within the same thread. Not just adjacent pairs — every ordered pair by timestamp (e.g. A2 ⇒ A4, A2 ⇒ A6)
interleaving-order edge: the order between two instructions that ① touch the same data, ② include at least one write, and ③ execute on different threads (e.g. B1 ⇒ A2)

Read-read pairs fail condition ② and are excluded. This interleaving-order edge is what segment graph selection keys on later, and it is also the sole target of mutation.

3-2) Extracting segment graphs

Figure 5. The DAG representing the whole interleaving (a), and the segment graph for Segment #1 extracted from it (b). Dotted arrows are program-order edges, solid arrows are interleaving-order edges. (Fig. 4 in the paper)

Pick two interleaving-order edges from the DAG, collect the vertices they connect, then pull in every edge among those vertices — that gives one segment graph. In the example, selecting (B1 ⇒ A2) and (B1 ⇒ A4) gathers three vertices, and adding (A2 ⇒ A4) completes Segment #1.

Why exactly two edges? Because of the "at most four accesses" observation from earlier. Two edges connect at most four vertices, so the rule of picking two is the mechanism that enforces the four-vertex limit — and the paper says as much, describing it as reflecting the survey's finding.

3-3) Using it as coverage: graph hashing

The collected set of segment graphs is interleaving segment coverage. If new segment graphs keep appearing, that is the signal to spend more compute on this input; if they stop, the input is considered exhausted.

The problem is memory. Individual graphs are small but there are a great many of them, so each segment graph is hashed and kept in a hash table. An ordinary hash will not do, because graphs with the same vertex set but different edge directions must be told apart. Hence Merkle hashing.

hash(v) = H(v.label ++ o1.label ++ ... ++ om.label) // o1..om are v's out-going neighbors

hash(G) = XOR of hash(v) for all v in V

H is the non-cryptographic FNV hash. For B1 ⇒ A2 ⇒ A4 we get hash(B1) = H(B1++A2++A4), whereas in the graph where A2 and B1 are flipped it becomes hash(B1) = H(B1++A4). Folding out-going edges into the hash makes the direction difference surface directly in the hash value.

4. Mutation-based Interleaving Exploration

4-1) Flipping edge directions

Figure 6. Mutation of a segment graph. (b), (c) and (d) derive from the explored graph (a); (d) forms a loop and is discarded. (Fig. 5 in the paper)

Mutation flips the direction of an interleaving-order edge, which swaps the execution order of two instructions touching the same memory.

Starting from the explored graph (a) B1 ⇒ A2 ⇒ A4, flipping only (B1 ⇒ A2) gives (b) A2 ⇒ B1 ⇒ A4 — the interleaving we were after. Flipping both edges gives yet another interleaving, (c). Flipping only (B1 ⇒ A4), however, produces (d), which forms the loop B1 ⇒ A2 ⇒ A4 ⇒ B1; that ordering is unexecutable, so it is discarded. Graphs whose hash is already in coverage are dropped too. What survives is the set of unexplored mutated segments, G_mutated.

4-2) Recompose: merging them back

Testing G_mutated one graph at a time would need far too many runs. So several are selected and merged into one larger graph, letting a single execution validate multiple segments at once.

The constraint during merging is, again, loops. Starting from an empty graph, the fuzzer walks G_mutated, adds each segment graph's edges one by one, and checks for loops with BFS. If even one edge creates a loop, that whole segment graph is set aside for this round; only if all of them pass do its edges get committed. Set-aside graphs stay in G_mutated as candidates for the next round — the only ones removed from the set are those that merged successfully.

4-3) Deriving scheduling points

Figure 7. The graph (b) formed by merging mutated segments (a), and the instruction sequence (c) obtained by topological sort. (Fig. 6 in the paper)

Running a topological sort over the merged graph yields an instruction sequence. Extracting the points at which preemption must occur gives the scheduling points. Each one records which instruction to stop at and which thread to run next. The end of each system call is a scheduling point as well.

5. Kernel Instrumentation

All of this requires recording, per system call, both basic blocks (for code coverage) and memory accesses (for interleaving coverage). Memory accesses carry a timestamp.

An LLVM compiler pass inserts a callback at each basic block entry and before each instruction accessing a globally-visible memory object. The former records the block's start address; the latter records a 5-tuple of (memory object address, instruction address, access size, access type, timestamp). The two go into separate per-thread regions, both shared with userspace via mmap, so a thread can read them back after a system call finishes to see which basic blocks and memory accesses it went through.

6. Execution Engine: Enforcing the Schedule

The part that actually enforces the computed schedule lives in the hypervisor layer, so as not to intrude on kernel execution.

Figure 8. Workflow of the execution engine. (Fig. 8 in the paper)

1. The fuzzer process spawns threads and assigns each one the system calls to run and its scheduling points.

2. Each thread delivers its scheduling points to the engine via the hcall_sched() hypercall, passing their ordering as the second argument.

3. The engine installs breakpoints on the corresponding instructions.

4. All threads rendezvous at hcall_ready().

5. The system calls execute.

Throughout execution only one thread is ever allowed to run, and preemption happens whenever a breakpoint is hit.

How preemption works. SegFuzz uses the hardware breakpoints in Intel CPUs. On a hit, the register context is saved into hypervisor memory and the PC is swapped to a trampoline that calls cond_resched() in an infinite loop. The thread keeps yielding the CPU and stays parked without making progress. Resuming just restores the saved registers.

The breakpoint budget. Intel allows only four breakpoints installed at once, and there are often more scheduling points than that. SegFuzz exploits the fact that scheduling points are ordered: it installs the first four and, each time one is hit, moves that breakpoint on to the next point.

Missed points. Kernel-internal state can change control flow so that a given scheduling point is never reached. To keep the ordering from going out of sync, the engine ignores every point before the one that was actually hit and keeps enforcing from there on.

VMI (Virtual Machine Introspection). The engine inspects kernel internals for two reasons. First, a breakpoint alone cannot tell which thread hit it, so task_struct and the per-cpu preempt_count are used to identify the execution context (hits from unrelated threads or interrupt handlers are ignored). Second, if a lock-holding thread is suspended and another thread then asks for the same lock, everything deadlocks — so lockdep functions such as lock_acquire()lock_release() are hooked to detect the impending stall and hand control over in advance.

The implementation comes to 3,334 lines of Go plus 341 of C++ on top of Syzkaller, 323 lines of C++ for the LLVM 12.0.1 compiler pass, 265 lines of C for the kernel callbacks, and 1,662 lines of C for the execution engine on QEMU 6.0.0. KVM hardware acceleration is used as-is.

Performance Analysis

The setup is a Xeon E5-2683 v4 (32 cores) with 512 GB of RAM, running 32 VMs at 4 vCPUs and 8 GB each. The kernel configuration is the one Syzkaller uses, so that both fuzzers explore the same subsystems.

21 New Concurrency Bugs

Over the evaluation period there were 83 unique crashes (including ones Syzkaller also finds), of which 21 were confirmed as new concurrency bugs. The target kernels span 5.19-rc2 through 6.2. The paper also notes that 3 of the 21 were independently reported by Syzkaller some months later.

What stands out is the spread. Unlike KRACE, which is specialized for file systems, SegFuzz is not tied to any particular subsystem, and bugs turned up across every layer — from device drivers such as drivers/misc/vmw_vmci to net/ipv4, kernel/events, mm and sound/core/oss. Severity ranges just as widely, from warnings to use-after-free, general protection faults and invalid page faults.

Two in particular stand out: the UAF in slip_ioctl had been in the kernel since 2013, and the GPF in add_wait_queue since 2011. That these came out of subsystems Syzkaller has been covering for years is, to me, the paper's strongest piece of evidence.

Coverage metric comparison: how discriminating is alias coverage?

This experiment tests Design goal 1 — whether informative interleaving coverage actually pays off. The nine target bugs (Vul #1–#9 in the paper's numbering) were chosen because prior work had already studied them and patches were available, making them injectable into a kernel. Two Android-specific CVEs evaluated in ExpRace were excluded. To keep the environment uniform, everything ran on a single kernel version, v6.0-rc7, with the relevant patches rolled back to bring the bugs back, and the authors manually supplied the multi-thread input and system call pair that triggers each bug.

Since the alias coverage implementation is file-system-only and cannot be run directly, it was emulated by capping SegFuzz's segment graphs at two vertices. Each bug was then run until coverage saturated, ten trials apiece, watching for manifestation.

The result: 6 of the 9 were never found, even after coverage had fully saturated. The 3 that were found manifested in only 6, 7 and 9 of the 10 trials respectively — hardly stable reproduction. With interleaving segment coverage, by contrast, all 9 were found before saturation, in every single trial. The authors' manual analysis confirmed that all 9 bugs manifest through interleavings of three or four instructions.

Alias coverage, meanwhile, saturates fast. Keeping SegFuzz's mutation-based exploration and swapping only the metric, saturation arrives after 13.9 executions on average (range 6–32) — low search complexity, and correspondingly weak detection. Interleaving segment coverage carries a far larger search space but much stronger detection.

Exploration efficiency

Figure 9. Executions (left) and elapsed time (right) needed to discover each bug. Naive is the stock kernel scheduler with no scheduling control. (Fig. 9 in the paper)

This experiment tests Design goal 2 — whether speculative interleaving exploration actually wins. Snowboard and KRACE cannot be run as-is (KRACE is file-system-only, and Snowboard runs on QEMU's TCG, making timing comparisons unfair), so KRACE's random delay injection and Snowboard's single-interleaving-order enforcement were reimplemented on top of SegFuzz's multi-thread fuzzing stage. The stock kernel scheduler with no scheduling control (Naive) serves as the baseline.

Because execution counts and elapsed times depend heavily on the initial seed and the seed mutation process, which would distort a fair comparison, the manual input provisioning from the previous experiment applies here too. The numbers below therefore skip the single-thread fuzzing stage entirely and isolate interleaving exploration with the bug-triggering input already in hand.

† The paper's wording is "discovers them, if successful, within 329.1 runs" — an average over the successful cases only. KRACE failed to find CVE-2019-6974 and the bug-fixing commit 69e16d01d1de within 10,000 runs.

‡ The stock kernel scheduler failed to find CVE-2019-6974, CVE-2019-11486 and commit 69e16d01d1de within 10,000 runs. The paper gives no average for Naive, so the elapsed-time cell is left blank.

Exhausting a bug-free input

The more common situation in fuzzing is working through an input that has no bug and moving on. So the patches fixing all the bugs above were re-applied, and the time to saturate interleaving segment coverage for a given multi-thread input was measured. One of the nine (Vul #8, absent from Figure 10) was excluded because its patch simply disables the vulnerable subsystem; the remaining 8 inputs are the targets.

Figure 10. Time to exhaust all interleavings of a given multi-thread input after patching. (Fig. 10 in the paper)

SegFuzz is 7.1× faster than Snowboard and 11.1× faster than KRACE. That saves an average of 298 seconds per input against Snowboard — and given that SegFuzz generated more than 60,000 inputs over the evaluation, the gain keeps compounding.

Coverage growth and overhead

Results from 100 hours of fuzzing:

- Disabling scheduling control (i.e. random scheduling) yields 29.1% less interleaving segment coverage over the same period. Repeating the experiment at 24 hours and running a Mann-Whitney U test gives a p-value of 0.03, so this is a real performance difference rather than random variation.

- Code coverage, on the other hand, comes in 3.2% below Syzkaller. That is the expected cost of spending compute on re-running the same input. The paper concedes it as a clear downside, but adds that it is acceptable given what interleaving exploration buys.

Throughput was measured starting from an empty seed set. Both SegFuzz and Syzkaller restart their VMs hourly, and the measurement window was cut at one hour to keep reboot and kernel-crash noise out.

SegFuzz comes in at 4.55 exec/s, roughly 54% of Syzkaller's 8.40. But a build of Syzkaller with the memory access tracing instrumentation added and simply not used lands at 4.74 exec/s — only 4.1% off SegFuzz. The main cause of the throughput drop is not SegFuzz's algorithm; it is the memory access tracing instrumentation.

Breaking down the 267.2 ms it takes to run one input (averaged over 10,000 runs) makes this clearer.

The two runtime overheads nearly double the execution time, while SegFuzz's own computational overhead is 26.1 ms — under 10% of the total (about 9% by the paper's reckoning). Building coverage and computing the next interleaving is cheap; the cost is in the observation (90.7 ms) and schedule enforcement (42.8 ms) that make it possible.

Conclusion

SegFuzz is a kernel concurrency fuzzer built out of one empirical observation: most concurrency bugs manifest from the execution order of at most four memory accesses. The pipeline:

1. represent the executed interleaving as a DAG

2. decompose it into segment graphs of at most four vertices, keyed on pairs of interleaving-order edges

3. track them as coverage using Merkle hashing, which distinguishes edge direction

4. flip edges to work backwards to unexplored interleavings

5. recompose without forming loops and derive a schedule via topological sort

6. enforce that schedule from the hypervisor using hardware breakpoints

This machinery found 21 new concurrency bugs in recent kernels, some of which had been sitting there for over a decade.

The authors flag three limits and scope conditions of their own.

Interleavings larger than four. Bugs that need five or more memory accesses to line up (8 of the 105 in the survey) cannot have their interleavings tracked as coverage. The paper adds that tracking is the only thing lost — triggering them is still possible through recomposing multiple segments.

Kernel background threads. Threads like kworkerd have no mechanism for tracing basic blocks and memory accesses, so interleaving segment coverage does not apply to them and bug hunting in that territory is correspondingly inefficient. The paper is careful to attribute this to the missing tracing mechanism rather than to a design choice, and leaves building one as future work.

Double-fetch bugs and data race detectors. SegFuzz is not effective against double-fetch bugs whose shared data lives in user memory, because it does not trace user memory accesses and so never forms interleavings that cross the kernel/user boundary. It is also orthogonal to data race detectors by design: SegFuzz targets bugs that surface as harmful behavior such as memory corruption — data races included — and so catches non-data-race bugs like CVE-2019-6974, while a detector catches the semantic bugs that never corrupt memory. The paper positions itself as complementary to both lines of work.