Efficient Input Minimization for Kernel Fuzzing via Relation- and Type-Guided Optimization

Coverage-guided kernel fuzzing is an effective technique for ensuring the reliability and security of operating system (OS) kernels. For example, Syzkaller, a widely used and representative coverage-guided kernel fuzzer, has successfully uncovered over 5000 bugs in Linux to date. Specifically, in kernel fuzzing, input minimization is a critical stage for improving fuzzing efficacy by compressing interesting inputs (programs) into shorter and coverage-preserving seeds. If this minimization stage is omitted, the achieved coverage and number of unique bugs found in Syzkaller would decrease by 27.5% and 40.4%, respectively, during a 48-hour fuzzing campaign. However, the minimization stage also takes over half of all fuzzing resources. During the 48-hour fuzzing campaign, 57.5% of program executions are expended in this stage, significantly limiting the potential of kernel fuzzing.

To the best of our knowledge, no prior work has explored or mitigated the problem described above in kernel fuzzing. To bridge this gap, this paper introduces two general and novel optimization strategies — influence-guided call removal and type-informed argument simplification — to reduce the cost of the minimization stage. The key idea of these two strategies is to reduce the number of program executions required to verify whether the new coverage achieved by the inputs is preserved.

We built SyzMini, a prototype based on Syzkaller that implements our two strategies to optimize input minimization. The evaluation shows that SyzMini significantly reduces the cost of the minimization stage by 60.7%, leading to a 12.5% improvement in branch coverage and a 1.7~2X increase in the number of unique bugs found. In addition, SyzMini has found 13 previously unknown bugs in the latest upstream kernel, all of which have been confirmed, with four already fixed. In terms of applicability, our optimization strategies can also improve the effectiveness of other kernel fuzzers ( e.g. , SyzVegas, SyzDirect, and CountDown).

Additionally, based on the insight that calls with indirect influence on the target call have a low probability of actually affecting its execution, we extended the influence-guided call removal strategy by introducing an additional attempt. This attempt preserves only the direct influences to further reduce the cost during call removal. We also integrated the extended strategy into SyzMini, which we refer to as SyzMini ⁺ . Our evaluation results demonstrate that SyzMini ⁺ achieves a coverage improvement of 14.5% to 16.5% and uncovers 1.9 to 2.3 times as many unique bugs as Syzkaller, further enhancing the effectiveness of SyzMini. We have released the implementations of both SyzMini and SyzMini ⁺ as open-source projects, which is available at [1].