SYSYPHUZZ: the Pressure of More Coverage

SYSYPHUZZ: the Pressure of More Coverage

Speakers: Zezhong Ren

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=b4uf5-nJjjQ

Overview

Coverage-centric kernel fuzzing has a blind spot: once a basic block is marked as "covered," fuzzers ignore it forever, even if it was executed only once or twice. This talk presents SYSYPHUZZ, a kernel fuzzer that makes execution frequency a first-class objective alongside coverage. Analysis of the Linux kernel under Syzkaller shows a heavily skewed distribution: after 72 hours, the bottom 5% of basic blocks are hit fewer than 30 times while the median is around 3,000. Over 22% of initially underexplored basic blocks remain insufficiently exercised even after prolonged fuzzing. SYSYPHUZZ introduces a boost delegator for selective task scheduling and context-preserving mutation that maintains the syscall context needed to reach low-frequency regions while exploring beyond them. Targeting Linux 6.12, SYSYPHUZZ discovered 67 bugs (31% more than Syzkaller) and 10% more than SyzGPT, with 2x the low-frequency coverage, demonstrating that execution frequency is complementary to coverage for kernel bug discovery.

Background

▶ Watch: Execution frequency imbalance: bottom 5% hit fewer than 30 times in 72 hours (1:30)

Kernel fuzzing is a mature field where the Syzbot system has run for years, accumulating an enormous corpus. Discovering new coverage has become extremely difficult. Yet within this "covered" code, many basic blocks are hit so infrequently that they are effectively untested. The standard fuzzing reward function provides no incentive to revisit already-covered regions, creating persistent "underexplored" zones where bugs can hide indefinitely.

The execution frequency imbalance follows a heavy-tailed distribution: a small set of hot-path basic blocks dominates execution while the vast majority are barely touched. This is an inherent property of kernel code structure, where common paths handle typical workloads and edge cases are rarely reached.

Key Findings

▶ Watch: SYSYPHUZZ design: boost delegator and context-preserving mutation (6:00)

Persistent underexploration: 22%+ of initially low-frequency basic blocks remain in the bottom 5% even after 72 hours of continuous fuzzing. These regions represent potential bug-hiding locations that coverage-centric fuzzers systematically ignore.

Boost delegator with context-preserving mutation: SYSYPHUZZ records per-basic-block hit counts, identifies bottom-5% targets, selects seeds that reach these targets (verified through pre-mutation checking), and mutates while preserving the syscall context needed to reach the target. Boost tasks run with higher priority, and conventional coverage tasks are appended only when new coverage is discovered.

67 bugs discovered, 31% more than Syzkaller: SYSYPHUZZ outperforms both Syzkaller and SyzGPT in total bug discovery. The overlap analysis (Venn diagram) shows unique bugs found by each tool, confirming that frequency-based exploration discovers bugs that coverage-centric approaches miss.

Bug-frequency correlation confirmed: Analysis of 13 discovered bugs shows they reside in previously low-frequency basic blocks, confirming the hypothesis that underexplored regions harbor overlooked bugs.

Technical Deep Dive

▶ Watch: Seed selection and pre-mutation checking for target reachability (8:00)

The two-stage workflow starts with corpus replay from Syzbot's existing corpus to warm up and establish initial hit count baselines. In the second stage, the boost delegator identifies low-frequency targets (bottom 5%), selects seeds via a seed map (which seeds hit which basic blocks), and generates boost tasks. Pre-mutation checking confirms seeds still reach targets before mutation begins. Context-preserving mutation keeps prior syscalls fixed (they build the state needed to reach the target) and adds/removes/adjusts subsequent syscalls. A deny list filters targets that show no improvement after 10 consecutive rounds, preventing resource waste on unreachable blocks. About 17.5% of underexplored basic blocks remain unreachable by this approach, representing potential targets for symbolic execution or LLM-guided generation.

Demo / Proof of Concept

▶ Watch: Results: 67 bugs, 31% more than Syzkaller, 2x low-frequency coverage (12:00)

72-hour campaigns on Linux 6.12 using the Syzbot corpus demonstrate 2x improvement in low-frequency region coverage, fewer persistently overlooked regions, and 67 bugs total vs. Syzkaller's ~51 and SyzGPT's ~61. Source code and artifacts are publicly available on GitHub with artifact evaluation badges.

Defensive Implications

▶ Watch: Bug-frequency correlation: discovered bugs reside in low-frequency blocks (14:00)

For kernel security teams, SYSYPHUZZ demonstrates that "high coverage" does not mean "thorough testing." Kernel code regions with low execution frequency are where bugs persist despite years of fuzzing by Syzbot. For fuzzing practitioners, execution frequency should be treated as a complementary metric to coverage, particularly for mature targets where coverage plateaus. For Linux kernel developers, the 17.5% of unreachable low-frequency blocks represent a concrete target list for manual review or alternative analysis techniques.

Key Takeaways

• Coverage-centric kernel fuzzing leaves basic blocks underexplored despite marking them as "covered"
• Execution frequency is heavily skewed: bottom 5% hit fewer than 30 times while median is 3,000 after 72 hours
• Boost delegator and context-preserving mutation increase low-frequency coverage by 2x
• 67 bugs discovered, 31% more than Syzkaller, confirming bugs hide in underexplored regions
• 17.5% of low-frequency blocks remain unreachable, representing targets for future analysis techniques
• Execution frequency is complementary to coverage as a fuzzing objective

About the Speaker(s)

Zezhong Ren is the first author (unable to attend due to visa issues). The talk was presented by Mathias Payer from EPFL. The research builds on the Syzbot/Syzkaller ecosystem and introduces execution frequency as a new optimization dimension for kernel fuzzing.