Beyond Edge Coverage: Per-Task Data-Flow Extraction at Kernel Function Boundaries via LLVM

This paper introduces TOOLNAME, an LLVM-based instrumentation framework that extends Linux KCOV to capture per-task function argument and return value data-flow at kernel boundaries, thereby enabling context-aware fuzzing and efficient root-cause analysis without requiring source modifications or incurring significant runtime overhead.

The Gist

Imagine the Linux kernel as a massive, bustling city with over 40 million buildings (lines of code). Security researchers use "fuzzers"—basically automated robots that throw random rocks at the city walls to see if anything breaks.

For years, these robots have only had one way to know if they hit something: Edge Coverage. Think of this like a security camera that only counts which doors a person walked through. If a person walks through the front door, then the kitchen door, the camera logs "Front → Kitchen."

The Problem: The "Blind" Robot
The problem is that two people can walk through the exact same doors but carry very different things.

• Person A walks through the kitchen door carrying a harmless apple.
• Person B walks through the same kitchen door carrying a bomb.

The security camera (the fuzzer) sees the exact same path: "Front → Kitchen." It has no idea that Person B is dangerous. In the real world, this means the robot keeps throwing rocks at the same doors, thinking it's making progress, while missing the actual bombs hidden in the arguments (the "stuff" being carried). This is called "coverage saturation"—the robot gets stuck because it can't tell the difference between a safe apple and a dangerous bomb.

The Solution: KCOV-DATAFLOW
The author, Yunseong Kim, built a new tool called KCOV-DATAFLOW. Instead of just watching which doors people walk through, this tool acts like a super-observant security guard who stands at every doorway and writes down exactly what the person is carrying.

Here is how it works, using simple analogies:

1. The "Smart Doorway" (LLVM Instrumentation)

The tool modifies the city's blueprints (the code) before the city is even built. It installs a tiny, invisible sensor at every single doorway (function boundary).

• What it does: When someone walks through, the sensor instantly snaps a photo of their ID, what they are holding (arguments), and what they are leaving behind (return values).
• The Magic: It doesn't just see a "box." If the box is a complex package (a struct), the sensor automatically opens it up and lists every item inside, even if the package was wrapped in layers. It does this without needing anyone to manually label the boxes in the code.

2. The "Silent Messenger" (Lock-Free Ring Buffer)

Once the sensor snaps a photo, it needs to send that info to the security team outside without slowing down the city or causing traffic jams.

• The Analogy: Imagine a high-speed conveyor belt (a ring buffer) that runs alongside the city. The sensors drop their notes onto the belt.
• Why it's special: It's "lock-free," meaning the sensors don't have to wait for permission to drop a note. They just drop it and move on. This ensures the city keeps running smoothly even while the sensors are working. It also keeps the notes separate for every single person (task), so Person A's notes don't get mixed up with Person B's.

3. The "Universal Translator" (Rust Support)

The city has two types of construction crews: the old-school C crew and the new, modern Rust crew.

• The Challenge: The Rust crew builds things differently, and their blueprints often hide details (optimizations) that make it hard to see what's inside the boxes.
• The Fix: KCOV-DATAFLOW has two ways to handle this. It can either translate the Rust blueprints after they are built (post-compilation) or work directly with the Rust builders to install the sensors during construction. This is the first time anyone has been able to see exactly what Rust functions are carrying while the city is running.

What This Actually Achieves

The paper demonstrates that this tool solves two main problems:

1. For the Robots (Fuzzers): Now, when the robot sees "Front → Kitchen," it also sees "Carrying a bomb." It can realize, "Oh! This path is dangerous!" and focus its energy there. It stops wasting time on safe paths and starts hunting for the real bugs.
2. For the Human Detectives (Analysts): When a crash happens, the detective doesn't just see "The kitchen door opened." They get a full report: "The kitchen door opened, and the person was carrying a bomb labeled 'Size: 15'." This helps them figure out why it exploded much faster than before, without needing to dig through the wreckage (crash dumps) or install loud, slow microphones (kprobes) that slow the city down.

The "Reality Check"

The author tested this on real city scenarios (kernel modules) and found:

• It catches "silent" bugs where the city doesn't crash but behaves wrongly (like a guard accepting a fake ID because the numbers looked similar).
• It works even when the city is running at top speed (with optimizations turned on).
• It adds very little weight to the city's operations (low overhead), making it safe to use continuously.

In short: KCOV-DATAFLOW turns a security camera that only counts footsteps into a smart system that reads the luggage, helping both robots and humans find the real dangers hidden in the details.

Technical Summary

Technical Summary: KCOV-DATAFLOW

1. Problem Statement

Coverage-guided kernel fuzzers, such as syzkaller, rely exclusively on edge coverage (trace-pc) as their feedback signal. This approach suffers from a fundamental "semantic gap": it identifies which basic blocks were executed but not with what values. Consequently, two invocations of a function (e.g., copy_from_user() or vfs_open()) with different argument values traverse identical control-flow edges yet possess vastly different security implications.

This limitation leads to coverage saturation on stateful subsystems (e.g., ksmbd, io_uring, binder) where security-critical behavior depends on runtime argument values rather than control-flow topology. Existing alternatives fail to address this at scale:

• Dynamic tracing (ftrace/kprobes): Imposes high per-function overhead unsuitable for continuous fuzzing.
• Manual annotation (IJON): Infeasible for the Linux kernel's 30+ million lines of code.
• Context-sensitive coverage (Angora, CollAFL): Explodes in complexity with polymorphic dispatch.
• DataFlowSanitizer: Incurs 10–100× overhead, rendering it unusable for kernel fuzzing.
• Post-mortem analysis (drgn/vmcore): Fails to capture Rust function arguments under -O2 optimization due to DWARF variable elision.

2. Methodology: KCOV-DATAFLOW

The paper presents KCOV-DATAFLOW, an LLVM-based instrumentation framework that extends Linux KCOV to capture data-flow tuples (function arguments and return values) at function boundaries. The system operates without source-level annotation and is designed for low-overhead, continuous operation.

Architecture

The system consists of three layers:

1. Compile-Time Instrumentation (LLVM Pass):

   • Extends the existing SanitizerCoverage framework.
   • At function entry and return, the pass emits callbacks capturing structured tuples: <PC, arg_idx, arg_size, ptr, offsets[]>.
   • Struct Decomposition: Automatically decomposes composite types (structs/unions) by walking DICompositeType metadata from DWARF. It generates a compile-time constant array of field offsets and sizes, allowing the runtime to extract specific field values without source modification.
   • Rust Support: Provides two paths:
     • Post-compilation: Converts Rust IR to text format (.ll), applies the pass, and re-compiles.
     • Native: Builds rustc against a custom LLVM 23 containing the pass, allowing direct instrumentation via RUSTFLAGS.

2. Kernel Runtime Transport:

   • Implements a lock-free, per-task ring buffer stored in task_struct.
   • Safety: Uses READ_ONCE/WRITE_ONCE for atomic writes. It includes an in_task() guard to reject calls from interrupt, softirq, or NMI contexts, preventing reentrancy issues.
   • Memory Safety: Uses copy_from_kernel_nofault() to safely dereference pointers, handling KASAN-poisoned memory, unmapped pages, and ERR_PTR values gracefully without crashing.
   • Interface: Exposes a dedicated debugfs interface (/sys/kernel/debug/kcov_dataflow) independent of existing KCOV, ensuring zero interference with syzkaller's standard operation.

3. User-Space Consumer:

   • Fuzzers or analysts map the buffer via mmap() for zero-copy reading.
   • Records include entry arguments and return values, allowing offline verification of pre/post-conditions.

3. Key Contributions

• LLVM SanitizerCoverage Extension: A compiler pass that captures function arguments and return values with automatic struct field expansion via DICompositeType metadata, requiring zero source annotation.
• Lock-Free Per-Task Transport: A kernel-resident mechanism that operates safely in process context with explicit interrupt rejection, avoiding interference with existing KCOV or syzkaller infrastructure.
• Rust Instrumentation: The first runtime methods for capturing Rust function arguments under -O2 optimization, addressing the failure of drgn and vmcore analysis on optimized Rust code.
• Empirical Validation: Demonstrated on five vulnerability classes (OOB, UAF, Double-Free, deep chains, and Rust modules) showing that boundary data-flow context provides information unavailable through any combination of existing tools (coverage + sanitizers + post-mortem debuggers).

4. Results and Evaluation

The system was evaluated on Linux-next 7.1.0-rc6 with KASAN and Rust enabled, running in a QEMU/KVM environment.

• Correctness: The tool correctly captured pre-corruption (ENTRY) and post-corruption (RET) values for all test cases, matching printk ground truth. It successfully captured Rust FFI contract violations and struct field expansions.
• Information Gain: Unlike KASAN (which reports the violation address but not the specific argument) or drgn (which fails on optimized Rust), KCOV-DATAFLOW identifies the exact argument and field responsible for corruption, even in Rust modules.
• Performance Overhead:
  • Per-call cost: ~27 ns per individual callback.
  • Recording Overhead: +8.3% latency when recording is active.
  • Global Instrumentation (No Recording): When all kernel objects are instrumented but recording is disabled, syscall latency increases by +133% and boot time by +71%. The .data section increases by 44% due to per-function offset arrays.
  • Comparison: The overhead falls within the range of a single sanitizer (e.g., KASAN) and is significantly lower than KMSAN. The authors note that global instrumentation is suitable for targeted sessions, while per-module instrumentation is recommended for continuous fuzzing.

5. Significance and Claims

The paper claims that KCOV-DATAFLOW bridges the semantic gap between coverage-guided fuzzing and data-flow analysis for OS kernels. Its significance lies in:

1. Breaking Coverage Saturation: By providing value-aware feedback, it allows fuzzers to distinguish between execution paths that differ only in argument values, enabling mutation guidance into value-dependent state transitions that edge coverage misses.
2. Deterministic Root-Cause Analysis: It provides security analysts with deterministic argument records for triage without the overhead of printk or kprobes, and crucially, works on Rust kernel modules where other tools fail.
3. Runtime Contract Verification: It enables a new form of "runtime-originated auditing," where captured records are used to verify pre/post-condition contracts (e.g., struct field consistency) against formal specifications. This allows for the detection of "silent" bugs (logic errors without crashes) that static analysis and sanitizers miss.
4. Reproducibility: The system generates deterministic artifacts (PC, args, ret tuples) that allow any party to independently reproduce and verify security findings, shifting the workflow from speculative source review to evidence-based analysis.

The authors emphasize that while the tool provides evidence of potential violations (e.g., out-of-bounds values or contract breaches), the final determination of whether a behavior constitutes a bug requires human judgment and maintainer confirmation, as demonstrated by their retraction of initial severity labels on specific Binder findings after maintainer review.