PaperlayerView exact revision on arXiv

Source-linked AI summary

Breaking the Coupling: Efficient Concurrency Fuzzing for Linux Kernel Data Race Detection

Cen Zhang, Jia-Ju Bai, Zi-Yu Zhang, Zuming Jiang

arXiv:2610.30813v1cs.OS

TL;DR

Kernel race detection must search both inputs and thread schedules, while existing approaches leave these searches coupled. DCIGSE decouples them with MRPs that guide input mutation and targeted scheduling. It found 187 races, including 59 harmful races, and detected substantially more races than existing fuzzers under the same testing budget.

  • Problem

    Race detection depends on both inputs that produce conflicting accesses and schedules that make them overlap, while existing approaches still couple input generation with interleaving exploration.

    Source: §1 · p. 1, §2.3 · p. 3

  • Method

    DCIGSE collects May Race Pairs during concurrent syscall-group execution to guide mutation and select concrete access pairs for a separate targeted-scheduling stage.

    Source: §1 · p. 2, §2.3 · p. 3, §3.1 · p. 4

  • Results

    187 unique real-world races, including 59 harmful races, were found across eight Linux kernel modules, and DCIGSE detected substantially more races than existing approaches under the same testing budget.

    Source: §1 · pp. 2–3, §9 · p. 14

  • Takeaways & Limitations

    The evaluation supports decoupling concurrent-input generation from interleaving exploration as an effective way to focus scheduling on promising race candidates.

    Source: §9 · p. 14

    Sequential observations can predict concurrent interactions imperfectly: Snowboard reports that only about 36% of resulting tests exercise its predicted channel.

    Source: §2.3 · p. 3

Abstract

from arXiv · show

Detecting data races in the Linux kernel requires exploring both the input space and the thread-interleaving space. Existing kernel concurrency fuzzers couple these two searches by exploring interleavings during fuzzing, often spending substantial scheduling effort on inputs with little potential to trigger real races. In this paper, we present a new concurrency fuzzing paradigm that decouples concurrent-input generation from thread-interleaving exploration, enabling expensive scheduling to focus on promising inputs. To identify inputs that warrant targeted scheduling, we introduce May Race Pairs (MRPs), which represent conflicting memory-access pairs observed within a dynamically determined time threshold. Our framework first generates and executes concurrent syscall groups without controlled scheduling, collecting MRPs to guide further input mutation and identify schedule-worthy inputs. It then uses a separate scheduling instance to explore targeted interleavings and confirm real data races. To improve the effectiveness of both stages, we incorporate LLM-assisted semantic mutation for generating diverse syscall groups, backpressure-guided dynamic threshold control for balancing candidate production and scheduling consumption, and history-aware context recovery, context-aware interleaving scheduling, and candidate MRP prioritization for efficient race confirmation. We implement our framework for the Linux kernel and evaluate it on eight common kernel modules in Linux 6.17. It discovers 187 unique real-world data races, including 59 harmful races. Under the same testing budget, our approach detects substantially more data races than existing kernel concurrency fuzzers, including SegFuzz and CONZZER. These results demonstrate the effectiveness of decoupling concurrent-input generation from interleaving exploration and concentrating scheduling effort on promising candidates.

1. Introduction

Kernel data-race detection must find inputs that create conflicting accesses and schedules that make them overlap, yet existing approaches couple these searches. DCIGSE uses May Race Pairs (MRPs) to select promising inputs for targeted scheduling and reports more races than existing approaches under the same testing budget.

1. Introduction

  • Race detection must find both inputs that produce conflicting accesses and schedules that make them overlap; existing approaches couple these searches and spend scheduling effort on low-potential inputs.Races can cause data corruption, memory corruption, and severe security vulnerabilities –.Source: §1 · pp. 1–2
  • DCIGSE decouples concurrent-input generation from interleaving exploration, using MRPs to identify inputs and concrete access pairs for expensive targeted scheduling.An MRP is a conflicting access pair observed within a dynamically determined time threshold; it indicates potential, not a confirmed race.Source: §1 · p. 2
  • The input-generation instance executes syscall groups concurrently without controlled scheduling, uses MRP feedback for LLM-assisted semantic mutation, and adjusts the MRP threshold according to candidate-queue backpressure.The threshold decreases when MRPs accumulate faster than scheduling can consume them and increases when candidates are insufficient.Source: §1 · p. 2
  • The scheduling instance confirms candidate races using history-aware context recovery, context-aware interleaving scheduling, and candidate-MRP prioritization.These methods recover state needed to reproduce candidates, distinguish dynamic occurrences of static access sites, and prioritize inputs using prior scheduling results.Source: §1 · p. 2
  • DCIGSE found 187 unique real-world races, including 59 harmful races, and detected substantially more races than existing approaches under the same testing budget.The evaluation covered eight common Linux kernel modules in Linux 6.17; 39 bugs were confirmed and 15 fixed as of submission.Source: §1 · pp. 2–3

2. Background

The background defines races through conflicting accesses that overlap in execution and explains why kernel race detection depends on both syscall inputs and schedules. It contrasts coupled prior approaches with DCIGSE, which collects MRPs during concurrent execution to guide mutation and later scheduling.

2.1. Data Race

  • A data race is identified when conflicting accesses from different threads to overlapping memory, with at least one write, overlap in execution.The paper follows prior kernel race fuzzers in treating the accesses’ monitored temporal overlap as the race criterion.Source: §2.1 · p. 3

2.2. Concurrent Execution in the Linux Kernel

  • Syscall sequences drive kernel state and memory accesses; concurrent executions create many possible interleavings, so race detection needs both inputs that produce a conflicting pair and schedules that overlap its accesses.Inputs alone do not ensure temporal overlap, and scheduling alone cannot reach the required states and execution contexts.Source: §2.2 · p. 3

2.3. Limitations of Existing Approaches

  • Prior approaches either search inputs and schedules jointly or use static or sequential observations before constructing concurrent inputs and schedules together.Snowboard reports that only about 36% of resulting tests exercise its predicted channel. DCIGSE instead collects MRPs during concurrent syscall-group execution; each guides mutation and records a concrete pair for later scheduling.Source: §2.3 · p. 3

3. Basic Idea

DCIGSE uses May Race Pairs to select syscall groups for targeted scheduling, separating candidate generation from race confirmation. A dynamically adjusted time threshold balances the supply of candidates against scheduling workload.

3.1. May Race Pair

  • An MRP is a conflicting access pair from different threads whose overlapping ranges include a write and occur within a short time threshold; it signals potential, not a confirmed race.The threshold τ controls admission of pairs for later scheduling.Source: §3.1 · p. 4

3.2. Fuzzing Framework

  • DCIGSE collects new MRPs during concurrent syscall-group execution, then queues their inputs for a separate instance to schedule the recorded conflicts and confirm races.The groups are also stored for further mutation.Source: §3.2 · p. 4

3.3. Dynamic Time-Threshold Control

  • A fixed threshold can starve scheduling or accumulate candidates, so backpressure-guided control adjusts τ to balance candidate admission with scheduling consumption.The controller tightens τ when workload is excessive and relaxes it when the queue is empty or workload is low.Source: §3.3 · pp. 4–5

3.4. Concurrent Execution Model

  • By default, each syscall group contains two sequences assigned to separate execution contexts, released simultaneously to run concurrently.Pairwise testing is used to reduce complexity while preserving most bug-exposing capability.Source: §3.4 · p. 5

4. Concurrent-Input Generation

DCIGSE uses LLM-assisted semantic mutation to generate diverse syscall groups that interact with shared or related kernel state. Validation, concurrent execution, and MRP feedback then support continued mutation and targeted scheduling.

4. Concurrent-Input Generation

  • LLM-assisted semantic mutation jointly edits syscall sequences to coordinate access to shared or related kernel state while respecting module-specific syscall, resource, and environment constraints.The mutation combines LLM reasoning with system-interface knowledge, including syscall semantics and kernel-resource lifecycle relations.Source: §4 · p. 5

4.1. LLM-Assisted Semantic Mutation

  • The workflow mutates corpus seeds, validates generated groups, and executes accepted groups concurrently; new-MRP groups return to the corpus and enter the scheduling queue.While LLM requests are pending, a fast mutator generates additional groups using sampled sequences and lightweight Syzkaller mutations.Source: §4.1 · pp. 5–6
  • The mutation prompt combines a seed and role, module constraints, a policy for cross-sequence interaction, and a structured output format; the F2FS example coordinates operations around shared filesystem state.The interaction objectives include shared instances, related resources, and shared subsystem context.Source: §4.1 · p. 6
  • MRP feedback prioritizes seeds using access-site-pair novelty and newly observed stack contexts, with novelty decreasing as more contexts for a pair are covered.A previously unseen access-site pair indicates a new pair of conflicting code locations.Source: §4.1 · pp. 6–7

5. Thread Scheduling

DCIGSE directs scheduling toward MRPs rather than exploring interleavings for every generated input, using prioritization, history replay, and context-aware scheduling to confirm races. These mechanisms manage the scheduling budget and help reproduce and target candidate access pairs.

5. Thread Scheduling

  • DCIGSE targets the conflicting access pairs in schedule-worthy groups’ MRPs, scheduling threads to make the accesses concurrent and confirm real races.Candidate MRP prioritization, history-aware context recovery, and context-aware interleaving scheduling support this process.Source: §5 · p. 7

5.1. Candidate MRP Prioritizing

  • Candidate MRP prioritization skips confirmed races, defers skipped candidates or tasks, and adjusts effort based on prior targeted-scheduling attempts.New candidates initially receive a scheduling opportunity; unresolved candidates’ skip probabilities inform task-level prioritization.Source: §5.1 · p. 7

5.2. History-Aware Context Recovery

  • History-aware recovery replays the bounded history of preceding syscall groups before the target group to reconstruct kernel context without replaying the complete fuzzing history.The configurable history bound balances context recovery effectiveness against replay cost.Source: §5.2 · pp. 7–8

5.3. Context-Aware Interleaving Scheduling

  • Context-aware scheduling uses recorded access-site, stack-context, ASN, and temporal-gap metadata to locate target occurrences, delay the earlier access, and confirm a race if the conflicting access occurs within the observation window.It tries exact ASN matching, bounded ASN drift, then stack-only matching; fallback strategies address occurrence shifts across replays.Source: §5.3 · p. 8

6. Implementation

DCIGSE extends Syzkaller with changes for MRP extraction, syscall-group mutation, queue management, threshold control, and targeted validation. LLVM instrumentation and runtime callbacks support memory tracing and race validation.

6. Implementation

  • Syzkaller extensions manage MRP extraction and corpora, syscall-group generation and mutation, scheduling queues, dynamic thresholds, and replay-based targeted validation.The extensions comprise about 14.1 KLoC of Go/C++ code, with about 1.0 KLoC of Go code for snapshot-based QEMU resets.Source: §6 · pp. 8–9
  • Table 1 lists the tested Linux kernel modules, selected to cover diverse kernel components in a reproducible QEMU/Syzkaller environment.The evaluation includes four filesystems, three device-driver subsystems, and one network protocol stack.Source: Table 1 · p. 9
  • An LLVM pass instruments selected kernel modules’ memory accesses, while runtime callbacks emit ftrace records and support watchpoint-based race confirmation.The instrumentation and runtime support comprise about 3.3 KLoC of C/C++ code; MRP extraction uses recorded address ranges without reconstructing high-level object types.Source: §6 · p. 9

7. Evaluation

DCIGSE found 187 unique real-world races across eight Linux 6.17 modules, including 59 harmful races. In same-budget comparisons, it confirmed more races than SegFuzz and CONZZER.

7.1. Experiment Setup

  • The evaluation covered eight common Linux 6.17 modules, including four file systems, three device-driver subsystems, and one network protocol stack.Experiments used dedicated physical cores; unless stated otherwise, DCIGSE split them evenly between input generation and thread scheduling.Source: §7.1 · p. 9

7.2. Finding Real-World Data Races

  • 187 unique races were found; 59 were classified as harmful, 39 were maintainer-confirmed, and 15 of those had been fixed.All 59 harmful races were reported to the corresponding kernel maintainers.Source: §7.2 · p. 9

7.3. Security Impact Analysis

  • Of 59 harmful races, 7 could cause memory corruption or denial of service, 39 could corrupt critical kernel state or persistent data, and 13 could cause unexpected behavior.Examples include a Bluetooth use-after-free, F2FS persistent data corruption, and an ALSA race affecting playback-state recovery.Source: §7.3 · pp. 9–10, Figure 4 · p. 9, Figure 5 · p. 10

7.5. Ablation Study on Concurrent-Input Mutation

  • GPT-5.4 and DeepSeek-V4-Pro confirmed 76 and 79 races, respectively, versus 41 for random mutation; both LLM configurations outperformed random mutation on every evaluated module.Across eight GPT-5.4 runs, API usage totaled 14.01M tokens and $66.01.Source: Table 4 · p. 11, §7.5 · p. 11, Figure 7 · p. 11

7.6. Ablation Study on Thread Scheduling

  • The full scheduling configuration confirmed 83 races, versus 35 without history recovery, 46 without ASN matching, and 40 without candidate backoff.The three mechanisms respectively restore state from execution history, target specific dynamic occurrences, and skip or defer low-priority candidates; without backoff, the full configuration advanced through about 2.97 times as many candidate pairs for a similar number of attempts.Source: §7.6 · pp. 11–12, Table 6 · p. 12

7.7. Comparison with Prior Approaches

  • 79 data races were confirmed by DCIGSEDS-V4P, versus 19 for SegFuzz and 11 for CONZZER; DCIGSERandom confirmed 41.The reported improvements were 4.16× and 7.18× for DCIGSEDS-V4P, and 2.16× and 3.73× for DCIGSERandom, against SegFuzz and CONZZER, respectively.Source: Table 8 · p. 13, §7.7 · p. 13

8. Related Work

Prior kernel fuzzing often focuses on sequential input coverage or couples input generation with scheduling, leaving concurrency exploration costly. DCIGSE instead targets MRPs and explicitly mutates semantic interactions between concurrent syscall groups.

8.1. Coverage-Guided Fuzzing

  • Coverage-guided fuzzers broaden sequential paths, but their coverage feedback does not reliably indicate inputs likely to trigger interesting concurrent executions or races.Kernel fuzzers that explore only inputs may miss races requiring rare or specific interleavings.Source: §8.1 · p. 13, §8.2 · p. 13

8.2. Kernel and Concurrency Fuzzing

  • Kernel concurrency fuzzers use search-space reduction, concurrency feedback, or controlled scheduling, yet coupling input generation with interleaving exploration can waste effort on low-potential inputs.DCIGSE collects MRPs during concurrent execution and uses them to focus later scheduling on promising interleavings.Source: §8.2 · p. 13

8.3. LLM-Assisted Testing

  • Prior LLM-based kernel fuzzers improve specifications or input generation, while DCIGSE makes semantic interactions among concurrently executed syscall groups an explicit mutation objective.The paper contrasts this with prior LLM testing approaches for kernel fuzzing, distributed races, and socket-state exploration.Source: §8.3 · pp. 13–14

9. Conclusion

DCIGSE decouples concurrent-input generation from interleaving exploration through May Race Pairs. Its Linux evaluation found real-world races, including harmful ones, and it detected substantially more races than existing kernel concurrency fuzzers under the same budget.

9. Conclusion

  • DCIGSE uses May Race Pairs to guide semantic mutation during input generation and focus subsequent scheduling on promising interleavings.The framework is presented as avoiding substantial testing effort on inputs with little potential to trigger races.Source: §9 · p. 14
  • The evaluation found 187 data races, including 59 harmful races; maintainers confirmed 39 harmful races and fixed 15.The paper reports substantially more detections than state-of-the-art kernel concurrency fuzzers under the same testing budget.Source: §9 · p. 14
  • The paper proposes lightweight runtime abstractions, such as deallocation/use pairs, as a possible way to decouple searches for concurrency bugs beyond data races.For concurrency-induced use-after-frees, such pairs could identify inputs with greater potential while scheduling targets the unsafe order.Source: §9 · p. 14
Loading 2610.30813v1…