Technical Summary: Towards Better Linux Kernel Fault Localization

Problem Statement

Debugging the Linux kernel remains a formidable challenge due to its massive scale (exceeding 40 million lines of code), complex architecture, and low-level programming intricacies. Effective Fault Localization (FL) is critical for maintenance, yet existing techniques struggle in this domain for three primary reasons:

1. Symptom-Cause Gap: Asynchronous execution and cross-subsystem coupling often delay or obscure bug manifestations, creating a significant semantic gap between the crash symptom and the root cause.
2. Scale and Interdependence: The kernel's massive size and complex dependencies exceed the input capacity of Large Language Models (LLMs) and render traditional static analysis ineffective.
3. Loss of Diagnostic Information: Kernel crashes often erase runtime states, making runtime coverage data (essential for Spectrum-Based FL) unavailable.

Existing LLM-based FL techniques, while promising for general software, are ill-suited for the kernel. They often treat bug reports and source code as plain text, relying on static reasoning that naively combines heterogeneous inputs. This approach fails to address the kernel's unique characteristics, such as the indirect relationship between bug descriptions and faulty code, and the inability to handle the massive search space without precise context.

Methodology: CoHiKer

The authors propose CoHiKer (Contrastive Reasoning and Hierarchical Context Analysis for Kernel Fault Localization), a novel LLM-based framework tailored to the Linux kernel. CoHiKer operates through three main stages:

1. Contrastive Reasoning

To bridge the gap between bug symptoms and root causes, CoHiKer moves beyond static analysis by analyzing behavioral divergence.

• Mutant Generation: The system uses an LLM to generate "contrastive mutants" of a failing test case. These mutants involve minimal, semantically valid modifications to syscall parameters (e.g., flags, sizes) designed to prevent the bug from triggering (i.e., causing the test to pass).
• Root Cause Inference: By comparing the execution results of the original failing test against the passing mutants, the LLM reasons about the specific conditions or sequences required for the bug to manifest. This isolates fault-relevant kernel features and provides a causal explanation grounded in system behavior rather than surface-level pattern matching.

2. Hierarchical Context Analysis

To manage the kernel's scale under LLM input constraints, CoHiKer employs a two-level localization strategy:

• File-Level Localization (FL@F):
  • Candidate Expansion: The system starts with files referenced in the crash trace but expands this set by analyzing system calls in the test case and inferring semantic dependencies between files (e.g., linking file-open syscalls to permission checks in other subsystems).
  • Ranking: The expanded candidate list is ranked by aligning the files with the inferred root cause from the contrastive reasoning stage.
• Method-Level Localization (FL@M):
  • Syntactic Filtering: A lightweight defect prediction model (MLP) trained on historical kernel bugs filters out methods with low defect likelihood based on structural features (e.g., cyclomatic complexity, call depth).
  • Semantic Filtering: The remaining methods are summarized by an LLM. These summaries are then ranked against the bug report and the inferred root cause to identify the most probable faulty methods.

3. Implementation Details

• LLM Backend: The system utilizes DeepSeek-V3 for reasoning and mutation generation.
• Prompting Strategy: CoHiKer employs Chain-of-Thought (CoT) prompting to decompose tasks into interpretable reasoning steps, ensuring the LLM focuses on causal links rather than mere text similarity.
• Efficiency: By narrowing the search space before invoking the LLM for deep reasoning, CoHiKer significantly reduces token consumption compared to baselines that process large code contexts.

Key Contributions

1. CoHiKer Framework: The proposal of a novel LLM-based FL technique specifically designed for the Linux kernel, integrating contrastive reasoning and hierarchical context analysis.
2. Contrastive Reasoning Component: A mechanism that leverages LLMs to compare failing and passing test cases, enabling the identification of root causes tightly linked to kernel-level bug manifestations, thereby mitigating the lack of runtime coverage.
3. Hierarchical Context Analysis: A framework that discriminatively incorporates file-level and method-level signals, optimizing for LLM input efficiency while maintaining contextual relevance.
4. Extensive Evaluation: A comprehensive evaluation on an extended dataset of 210 verified Linux kernel bugs, demonstrating superior performance over both traditional and state-of-the-art LLM-based baselines.

Experimental Results

The authors evaluated CoHiKer against five baselines (including traditional IR-based techniques like PathIdea and FineLocator, and LLM-based techniques like Agentless and LinuxFL+) on 210 real-world kernel bugs.

• Accuracy: CoHiKer consistently outperformed all competitors.
  • File Level: Improved Top-1 accuracy by up to 26.07% over state-of-the-art LLM baselines (achieving 55.24% vs. 43.6% for LinuxFL+).
  • Method Level: Improved Top-1 accuracy by up to 56.85% over baselines (achieving 32.86% vs. 24.76% for LinuxFL+).
  • Robustness: CoHiKer showed significant gains even when bug reports did not explicitly mention the faulty files or methods, a scenario where other techniques often failed completely.
• Efficiency: CoHiKer achieved substantial reductions in token consumption, reducing usage by 8.84× at the file level and 28.9× at the method level compared to baselines, while also reducing runtime overhead.
• Generalizability: When tested on a non-kernel dataset (SWE-bench-lite), CoHiKer maintained its superiority, improving Top-1 accuracy by 15.5% (file level) and 5.3% (method level) over baselines, confirming the broad applicability of its core methodologies.

Significance and Claims

The paper claims that CoHiKer represents a significant advancement in kernel fault localization by addressing the specific limitations of prior techniques: the lack of precise root cause analysis and ineffective context utilization. By aligning LLM reasoning with kernel-specific characteristics (such as syscall semantics and cross-subsystem dependencies) through contrastive reasoning and hierarchical analysis, CoHiKer offers a practical, accurate, and efficient solution.

The authors emphasize that their approach does not merely rely on static code understanding but derives causal explanations from system behavior, enabling more interpretable and actionable fault localization in complex kernel environments. The results suggest that CoHiKer sets a new state-of-the-art for Linux kernel debugging, offering a pathway to handle the inherent difficulties of large-scale, low-level software maintenance.