Published: Thu 26 February 2026
By Mathias Payer
In Academia .
tags: fuzzing kernel NDSS
Fuzzing faces a key challenge: after running for an extensive time, coverage
plateaus and will no longer increase despite extensive mutations. Only new
seed inputs or mutation operators will likely change that. We have observed
that for Syzbot fuzzing in the Linux kernel has essentially plateaued due to
Google's multi-year fuzzing efforts.
Instead of blindly rerunning campaigns with slightly adjusted operators, we
wondered if we can find bugs in already covered areas. We observed that
execution frequency of basic blocks is heavily skewed with some basic blocks
executed extremely frequently while many are executed rarely at all. On average,
basic blocks are executed less than 30 times. Our goal was therefore to balance
the execution frequency of basic blocks by boosting under-fuzzed areas. Our
intuition is that bugs are hiding in these under-fuzzed areas.
Two key challenges when boosting under-fuzzed areas are (i) resource constraints
and (ii) context-destroying mutations. First, adding new fuzzing tasks will deflect
energy from other areas and blindly iterating on seeds that do not create new
findings simply wastes energy. Second, these under-fuzzed basic block are hard
to reach and often require precise system call sequences. Mutations therefore
often destroy the context and make the target unreachable.
Sysyphuzz runs in two phases: first, we replay the existing corpus during a
warm up phase to get approximate counts of under-fuzzed areas. During this time
we simply count basic block execution frequencies along with creating a map
between basic blocks and seeds. In the second phase, we introduce a boost
delegator that tracks frequency of basic blocks to decide which ones should be
boosted. During boost tasks, sysyphuzz checks that the target basic blocks
remain reachable and then issues context-preserving mutations.
The sysyphuzz implementation is open
source and we carefully evaluated it against syskaller. The exact evaluation
details are in the paper .
The key takeaway of Sysyphuzz is that, after plateauing, fuzzers can still find
bugs when focusing on under-fuzzed areas. For this, we need to track seeds that
reach certain areas and carefully boost them.
This work was led by Zezhong Ren during his visit in the lab along with Han
Zheng, Zhiyao Feng, Qinying Wang, Marcel Busch, Yuqing Zhang, and Chao Zhang.
Zezhong deserves the majority of the credit for the hard work on the system, the
evaluation, and the revision.