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.