Leveraging Binary Coverage for Effective Generation Guidance in Kernel Fuzzing

State-of-the-art kernel fuzzers use edge-based code coverage metrics for novel behavior detection. However, code coverage is not sufficient for operating system kernels, for they contain many untracked but interesting features, such as comparison operands, kernel state identifiers, flags, and executable code, within its data segments, that reflects different execution patterns, and can profoundly increase the granularity and scope of the coverage metrics. This paper proposes the use of Kernel Binary Coverage Feedback, a comprehensive and effective execution feedback method that provides metrics reflecting the execution coverage status of the entire binary coverage to kernel fuzzers. Our approach abstracts program behavior as its memory access pattern during execution, and considers all such relevant behavior, including standard memory reads and writes, predicate comparisons, etc., to obtain a coverage metric on the whole kernel binary for input generation guidance. We implemented a prototype tool KBinCov and integrated it into a popular kernel fuzzer Syzkaller. We evaluated its effectiveness against vanilla Syzkaller, as well as certain other approaches, including StateFuzz and IJON. Our results show that KBinCov achieves code and binary coverage increases of 7%, 7%, 9%, and 87%, 34%, 61%, compared to Syzkaller (using kcov), StateFuzz, and IJON, on recent versions of the Linux kernels, respectively, while only incurring a 1.74× overhead increase, less than StateFuzz and IJON's 2.5× and 2.2× figures. In addition, we found 21 previously unknown bugs using KBinCov with Syzkaller, more than Syzkaller (with kcov), StateFuzz, and IJON, which found 4, 4, and 2 bugs, respectively.