MOCK: Optimizing Kernel Fuzzing Mutation with Context-aware Dependency

Optimizing Kernel Fuzzing Mutation with Context-aware Dependency

Speakers: Jiacheng Xu

Conference: NDSS Symposium

YouTube: (no public video)

Overview

Modern operating system kernels are the bedrock of computing, responsible for managing hardware and software resources and providing a secure platform for applications. However, their immense complexity, characterized by vast codebases and intricate architectures, makes them a perennial source of vulnerabilities. For instance, 2022 alone saw 288 Linux kernel vulnerabilities reported, averaging a CVSS score of 6.5, with an annual average of 196 vulnerabilities over the past five years. These flaws present critical attack vectors, potentially leading to sensitive data exposure, system disruption, or full system compromise. Coverage-guided fuzzing has emerged as a leading technique for discovering such vulnerabilities, demonstrating significant success in complex real-world systems by generating diverse inputs to explore code paths.

In the realm of kernel fuzzing, inputs primarily consist of sequences of system calls, or syscalls. The highly stateful nature of kernels means that specific, often complex, sequences of syscalls are required to build the necessary internal states to reach deep kernel code paths where critical vulnerabilities frequently reside. Existing kernel fuzzers, despite their advancements, often struggle to synthesize these stateful syscall sequences effectively, frequently generating inputs that lack the contextual dependencies needed for deep code coverage. This limitation leads to inefficient exploration of the kernel's attack surface and an increased likelihood of missing subtle, yet critical, bugs.

This article details MOCK, a novel kernel fuzzing framework designed to overcome these challenges. MOCK addresses the fundamental problem of generating context-aware syscall sequences by learning and leveraging the intricate contextual dependencies within them. By adaptively mutating syscall sequences in alignment with the calling context, MOCK aims to generate higher-quality test cases, significantly reduce the search space, and ultimately enhance the efficiency and effectiveness of kernel vulnerability discovery.

Background

[▶ Watch: Introduction to kernel vulnerabilities and fuzzing challenges (0:00)]()

The interaction between user-space applications and the kernel is primarily facilitated through syscalls. The behavior of any given syscall is profoundly influenced by the kernel's internal state, which is established by preceding syscalls. This inherent statefulness demands that syscall sequences possess a specific structure; consequently, random combinations are largely ineffective for achieving comprehensive code coverage.

Kernel Fuzzing Landscape:

• Syzkaller: Google's Syzkaller stands as the state-of-the-art kernel fuzzer, credited with reporting over 3,900 bugs in the Linux kernel. It utilizes declarative templates, known as Syzlang, to describe syscall syntax and structure. Syzkaller guides syscall sequence generation through a choice table that incorporates both static priority (based on argument directions, e.g., producer-consumer relationships) and dynamic priority (derived from syscall adjacency in initial seeds).
• Improvements over Syzkaller: Numerous research efforts have sought to enhance kernel fuzzing:
• MoonShine: This fuzzer employs static analysis of syscall traces and global variables to capture explicit and implicit dependencies, generating high-quality seeds for Syzkaller.
• SyzVegas: It dynamically adapts task and seed selection using the EXP3 algorithm to boost coverage.
• HEALER: HEALER deduces dependencies during the fuzzing campaign, defining a binary influence relation where one syscall's execution can affect another's. It uses both static (explicit relations) and dynamic (implicit relations via minimization) learning to construct a relation table.

While these tools have made significant strides, they predominantly rely on context-free dependency models, often focusing on point-to-point interactions within a limited range of syscalls. This approach often falls short in synthesizing the intricate, interrelated sequences required to build complex kernel states and explore deeper code paths.

Language Models (LM):

Language models (LM) are statistical models that predict the probability of a word sequence. Traditional N-gram models, constrained by the Markov assumption (where the probability of a word depends only on the preceding N-1 words), struggle with capturing long-range dependencies and suffer from data sparsity. Neural Network Language Models (NNLM) address these limitations by encoding words into feature vectors, or embeddings, which capture semantic information. Pioneered by Bengio et al. and advanced by Word2Vec with architectures like Continuous Bag-of-Words (CBOW) and skip-gram, NNLMs have proven effective in understanding contextual relationships in natural language. MOCK leverages NNLMs to learn syscall dependencies, treating syscalls as "words" in a "language" of kernel interactions.

Multi-Armed Bandit (MAB) Problem:

The Multi-Armed Bandit (MAB) problem is a classic decision-making dilemma that involves balancing exploration (trying new options) and exploitation (leveraging known good options). In fuzzing, this translates to selecting mutation strategies to maximize code coverage. Algorithms like ε-Greedy, Thompson Sampling, and Upper Confidence Bound (UCB) are commonly employed. MOCK specifically utilizes UCB-1 for its efficiency and effectiveness in striking this crucial balance between exploring new mutation avenues and exploiting those that have proven successful.

Key Findings

[▶ Watch: Background: state-of-the-art kernel fuzzing and its improvements (2:00)]()

MOCK's extensive evaluation across multiple Linux kernel versions demonstrated superior performance compared to state-of-the-art kernel fuzzers, particularly in achieving deeper code coverage and discovering complex vulnerabilities.

1. Enhanced Code Coverage: MOCK consistently achieved higher code coverage, with an average of 12%, 6%, and 3% branch coverage improvement over HEALER, Syzkaller, and SyzVegas, respectively. It also significantly accelerated coverage exploration, demonstrating a 2.23x, 1.58x, and 1.32x speed-up over these counterparts. Overall, MOCK achieved an average of 7% increase in unique code branches and a 1.71x speed-up.
2. Generation of Deeper, Interrelated Sequences: MOCK excelled at generating longer, more interrelated syscall sequences, which are crucial for building complex kernel states. For sequences of length five or more, MOCK's assigned execution times were 1.61x, 1.49x, and 1.41x higher than HEALER, Syzkaller, and SyzVegas, respectively. This highlights its ability to move beyond shallow, context-free interactions.
3. Effectiveness of Context-aware Dependencies: The context-aware dependency mechanism within MOCK proved highly effective. It generated 1.24 times more sequences achieving new coverage (25,275) compared to context-free dependencies (20,389). For extended contexts (length two or more), it showed significant improvements in increasing sequence lengths, overcoming the limitations of context-free approaches.
4. Reduced Warm-up Time and Boosted Performance: The integration of initial seeds (crawled from syzbot) or pre-trained models significantly boosted MOCK's performance. With initial seeds, MOCK-Seeds achieved an 84% coverage growth and up to a 4.31x speed-up. A pre-trained model yielded a 10% coverage growth and a 3.29x speed-up. These findings underscore the value of prior dependency knowledge in accelerating the fuzzing process.
5. Superior Vulnerability Detection: MOCK demonstrated superior vulnerability detection capabilities, identifying 39 unique vulnerabilities in Linux kernel 5.10, surpassing HEALER (30), Syzkaller (35), and SyzVegas (37). It uniquely discovered 8 vulnerabilities not found by HEALER and 5 not found by Syzkaller or SyzVegas. The average length of syscall sequences to reproduce MOCK's unique vulnerabilities was 16, indicating complex, deep-seated bugs.
6. Real-World Impact: MOCK successfully discovered 15 unique practical vulnerabilities in real-world Linux kernel versions (4.19, 5.4, 5.10, 5.15, 5.19), with four confirmed and fixed by developers. This includes two high-severity CVE IDs: CVE-2022-2978 (CVSS 7.8) and CVE-2022-40476 (CVSS 5.5), indicating its ability to find critical security flaws.
7. Synergistic Component Contribution with Minimal Overhead: A stepwise analysis confirmed that both the dependency-guided mutation (via the language model) and the adaptive task scheduler contribute significantly to MOCK's overall efficacy, yielding 17% and 14% coverage improvements, respectively. The lightweight design ensures minimal overhead, with model training averaging 23 minutes and mutation adding less than 7% to fuzzing time, running in parallel routines.

Technical Deep Dive

[▶ Watch: MOCK's foundational techniques: Language Models and MAB (3:05)]()

MOCK is engineered as a novel kernel fuzzing framework that addresses the challenge of kernel statefulness by learning and leveraging contextual dependencies within syscall sequences. Its design is structured around three primary phases: Pre-Processing, Input Generation, and Execution/Feedback.

Pre-Processing

The Pre-Processing phase establishes the foundational knowledge required for MOCK's operation, primarily focusing on identifying available syscalls and their static dependencies.

• Static Dependency Detection: Static dependencies serve as an initial baseline for guiding syscall mutation, particularly before the neural network language model (NNLM) has sufficiently learned dynamic dependencies. MOCK detects these dependencies by analyzing Syzlang descriptions, similar to HEALER. Specifically, it identifies two types:

1. If syscall Ci produces a return value that can be consumed by any parameter in Cj.
2. If Ci's parameters include an outward direction pointer that can be consumed by any parameter in Cj.

These relations capture explicit data flow or state changes between syscalls.

• Syscall Vocabulary Construction: A comprehensive syscall vocabulary is constructed from all available syscalls. A preliminary run on the target kernel determines which syscalls are actually invokable, ensuring the vocabulary's accuracy for the specific kernel version being fuzzed. This step ensures that the language model operates on a relevant and valid set of syscalls.

Context-aware Dependency Learning

The core innovation of MOCK lies in its ability to dynamically learn context-aware dependencies using an NNLM. This learning process relies on a high-quality corpus aggregated during fuzzing.

• Corpus Aggregation and Test Case Minimization: Coverage-guided fuzzing naturally collects syscall sequences that achieve new coverage, which are valuable for training. However, raw sequences can contain "noisy" syscalls that do not contribute to the new coverage or relevant interactions. To ensure a high-quality training set, MOCK performs Test Case Minimization (analogous to Algorithm 1 in the paper).
• When a test case triggers new coverage, MOCK minimizes it before adding it to the corpus.
• The algorithm takes the full syscall sequence, the new coverage achieved, and the position of the syscall that triggered it.
• It iterates backward from the syscall preceding the one that triggered new coverage. For each syscall in this prefix, it temporarily removes it, re-executes the truncated sequence, and checks if the new coverage is still maintained.
• If the coverage persists, the syscall is permanently removed, indicating it was non-essential for that specific coverage gain. Otherwise, it's retained.
• This iterative process ensures that minimized sequences only preserve the distinct dependencies crucial for achieving the observed coverage, thus providing a clean and effective training corpus for the language model.
• Neural Network Language Model (NNLM): MOCK employs a customized NNLM to capture these context-aware dependencies (illustrated conceptually by Figure 3 in the paper).

1. Input Conversion: A syscall sequence is first transformed into a numerical sequence based on the predefined syscall vocabulary.
2. Embedding Layer: Each numerical syscall is then converted into a dense, distributed vector representation, or embedding. These embeddings capture semantic relationships between syscalls.
3. BiGRU Layer: The sequence of embeddings is fed into a Bidirectional Gate Recurrent Unit (BiGRU) layer. The BiGRU processes inputs at each time step, considering both forward and backward hidden states from previous steps, along with the current syscall's embedding. The bidirectional nature of the BiGRU is crucial as it allows the model to predict promising syscalls based on the cumulative context—both preceding and succeeding syscalls—effectively capturing nuanced, directional dependencies.
4. Linear Layer: The output of the BiGRU layer is then passed through a linear layer, which generates a conditional probability distribution over the entire syscall vocabulary for the next potential syscall.

The model is trained to minimize the cross-entropy loss over a training set consisting of context-syscall pairs. MOCK utilizes a CBOW (Continuous Bag-of-Words) model variant, where the bidirectional RNN structure allows for predicting a syscall based on its surrounding context, further enhancing its ability to capture complex dependencies. Crucially, the language model is updated dynamically and regularly throughout the fuzzing process. As the kernel's state evolves and the corpus grows, the model continuously learns the latest dependencies, ensuring its relevance. The corpus is split into training and validation sets, and the model performing best on the validation set is deployed.

Dependency-guided Mutation and Task Scheduling

With the learned context-aware dependencies, MOCK generates mutated syscall sequences specifically designed to trigger deep code paths.

• Context-aware Mutation: MOCK enhances standard sequence-level mutation operations, such as inserting or removing syscalls, by integrating context-aware dependency information (as detailed in Algorithm 2).

1. Seed and Position Selection: A seed syscall sequence is chosen, and a random insertion position within it is determined.
2. Context Extraction and Prediction: MOCK extracts the front context (syscalls preceding the insertion point) and feeds it to the language model to obtain a probability distribution of candidate syscalls. The topK function identifies the top-k (specifically, 15) most probable suggestions.
3. Rear Context Analysis (if applicable): If the insertion point is not at the end of the sequence, MOCK extracts the rear context (syscalls succeeding the insertion point), reverses it, and feeds it to the language model to obtain another set of top-k suggestions.
4. Candidate Merging and Selection: Suggestions from both front and rear contexts are merged, with probabilities added for common syscalls. MOCK then randomly selects a syscall from these weighted candidates.
5. Parameter Synthesis: Parameters for the newly added syscall are synthesized according to Syzlang types.

The bidirectional nature of the BiGRU in the language model is paramount here, enabling MOCK to consider both preceding and succeeding syscalls, thereby capturing directional dependencies often missed by context-free fuzzers. This approach ensures the generation of high-quality test cases that align with the kernel's inherent statefulness.

• Task Scheduling: Fuzzing inherently involves a trade-off between exploration (trying diverse mutations to find new paths) and exploitation (using learned dependencies to efficiently find bugs). Over-reliance on historical knowledge can limit diversity. MOCK models this as a Multi-Armed Bandit (MAB) problem and employs the UCB-1 algorithm to manage this dilemma effectively (Algorithm 3).

1. UCB-1 Algorithm: MOCK chose UCB-1 over EXP3 (used by SyzVegas) due to its lower computational resource requirements and simplicity. Its goal is to maximize code coverage over time.
2. Exploration Stage (EXPLORE): Initially, MOCK assigns even weights to different mutation tasks (static-based and model-based). It randomly selects a task, executes the input, and records the number of executions (Ni) and new coverage/crashes (Ri).
3. Exploitation Stage (EXPLOIT): MOCK calculates the UCB-1 reward Gi = Ri/Ni + C * sqrt(ln(t)/Ni) for each task, where t is the total number of attempts and C is an exploration constant. It then selects the task with the highest reward (ibest).

The fuzzer cycles between EXPLORE (for texplore time) and EXPLOIT (for texploit time). Through extensive experimentation (Table IV in the paper), an optimal budget ratio of 4:1 (exploration:exploitation) was determined to yield the highest branch coverage (383k), which MOCK adopts. This adaptive task scheduling increases mutation diversity, improves the quality of the training corpus, and enhances the likelihood of discovering unpredictable bugs.

Implementation Details

MOCK is implemented as an extension module designed for integration into existing kernel fuzzers with minimal overhead. It leverages Syzlang from Syzkaller and builds its model training, model-guided mutation, and task scheduler components upon HEALER's fuzzing engine, comprising approximately 1,600 lines of code.

• Model Training Module: The lightweight NNLM is implemented using PyTorch 1.11.0.
• Architecture: Each syscall embedding has a dimension size of 64, and the BiGRU layer has a hidden state size of 128.
• Regularization: A dropout frequency of 0.5 is incorporated in the BiGRU to prevent overfitting.
• Optimizer: The Adam optimizer is used, with its learning rate adaptively decaying every ten training epochs.
• Model Persistence: The trained model is saved in TorchScript format.
• Dynamic Adjustment: MOCK dedicates the first hour of fuzzing to collect an initial training set. Subsequently, the training module is invoked every two hours to dynamically adjust the dependencies based on the accumulating corpus.
• Parallel Execution: To prevent conflicts between PyTorch/LibTorch and the main fuzzing loop, the training module runs in a parallel routine. It exposes RESTful APIs, enabling the mutation module to periodically load the updated model without interrupting fuzzing.
• Model-guided Mutation Module: This module loads the trained model and executes mutation operations. It uses tch-rs, which provides Rust bindings for the C++ PyTorch API (LibTorch 40). When the model outputs a probability distribution for syscall candidates, MOCK samples the top-k (specifically, 15) suggestions to introduce diversity while remaining contextually relevant.
• Task Scheduling Module: In the exploration stage, each task is initially assigned even weights. The determined optimal budget ratio for exploration and exploitation is 4:1, maximizing branch coverage.

Demo / Proof of Concept

[▶ Watch: MOCK's three-phase framework design overview (4:50)]()

While the talk did not feature a live, interactive demo, MOCK's effectiveness was concretely demonstrated through its ability to discover novel, high-severity vulnerabilities in real-world Linux kernels. This serves as a powerful proof of concept for its context-aware dependency learning and mutation strategies.

MOCK was run on various Linux kernel versions (4.19, 5.4, 5.10, 5.15, and 5.19) for two weeks, resulting in the discovery of 15 unique practical vulnerabilities. Critically, four of these were confirmed and subsequently fixed by developers, highlighting their real-world impact. Among these, MOCK received two official CVE IDs:

• CVE-2022-2978 (CVSS 7.8): A high-severity vulnerability.
• CVE-2022-40476 (CVSS 5.5): Another significant vulnerability.

One notable case study involved the discovery of a null pointer dereference vulnerability in the io_uring module. This bug, facilitated by KASAN (Kernel Address Sanitizer), occurs because a current variable, responsible for holding process information, unexpectedly becomes a null pointer due to the asynchronous nature of io_uring tasks. Subsequent access to this null pointer leads to a system crash or potential exploitation. MOCK's ability to uncover this complex vulnerability is directly attributed to its context-aware dependency mechanism. By effectively maintaining and extending the calling states over a sequence of interactions, MOCK was able to generate the precise, in-depth syscall sequence required to trigger this subtle and deep-seated bug, which might have been missed by fuzzers relying on simpler, context-free dependency models. The average length of syscall sequences required to reproduce the five vulnerabilities uniquely discovered by MOCK was 16, further underscoring its capability to find complex, deep-seated issues that require long, interrelated input sequences.

Defensive Implications

[▶ Watch: Pre-processing phase: inferring static syscall dependencies (5:30)]()

MOCK's advancements in kernel fuzzing offer crucial insights for defenders seeking to enhance the security posture of operating system kernels. The ability of MOCK to consistently achieve higher code coverage, generate longer and more interrelated syscall sequences, and uncover deep, complex vulnerabilities (including high-severity CVEs) has several key implications:

1. Prioritize Stateful Vulnerability Detection: Defenders should acknowledge that a significant portion of critical kernel vulnerabilities are not simple, single-syscall flaws but rather emerge from complex, stateful interactions across multiple syscalls. Traditional fuzzing approaches might miss these. Therefore, security teams should advocate for, and potentially integrate, fuzzing tools that specifically target and model these contextual dependencies and statefulness.
2. Adopt Advanced Fuzzing Techniques: Relying solely on basic coverage-guided fuzzing might not be sufficient for deep kernel exploration. MOCK demonstrates the power of integrating neural network language models and adaptive task scheduling into fuzzers. Organizations involved in kernel development or auditing should explore and adopt similar advanced techniques to improve their vulnerability discovery pipelines.
3. Leverage Initial Seeds and Pre-trained Models: MOCK's evaluation clearly showed that starting fuzzing campaigns with existing high-quality initial seeds (e.g., from syzbot or historical bug reports) or pre-trained models of syscall dependencies significantly reduces warm-up time and boosts overall performance. Defenders can use this insight to optimize their fuzzing efforts by curating and maintaining such seed corpora and potentially sharing pre-trained models within their security communities.
4. Focus on Minimization and Corpus Quality: The Test Case Minimization strategy employed by MOCK highlights the importance of creating a clean, high-quality corpus for learning dependencies. Developers of fuzzing tools should ensure robust minimization techniques are in place to extract only the essential syscall interactions, thereby making the learning process more efficient and accurate.
5. Address Concurrency Challenges: MOCK's acknowledged limitation regarding concurrency dependencies points to a significant area for future defensive focus. Kernel vulnerabilities often arise from race conditions and concurrent interactions. Defenders should be aware that even advanced sequential fuzzers may not fully cover these complex multi-threaded scenarios, necessitating dedicated research and tools for concurrency-aware fuzzing.
6. Continuous Fuzzing and Dynamic Model Updates: The dynamic nature of MOCK's language model, which updates regularly throughout the fuzzing process, underscores the need for continuous fuzzing. Kernels are constantly evolving, and so are their stateful interactions. Implementing a continuous fuzzing pipeline with dynamically updated dependency models can help ensure that new code paths and evolving complexities are adequately covered.

By incorporating these insights, defenders can move beyond superficial vulnerability detection to proactively identify and mitigate the deeper, more intricate flaws that MOCK has proven to uncover, ultimately strengthening kernel security.

Key Takeaways

• Context-aware Dependency is Crucial: MOCK’s core innovation is its ability to learn and leverage context-aware dependencies between syscalls, moving beyond context-free approaches to effectively build complex kernel states.
• Superior Coverage and Speed: MOCK achieved an average of 7% higher branch coverage and a 1.71x speed-up compared to state-of-the-art fuzzers like HEALER, Syzkaller, and SyzVegas.
• Deeper Vulnerability Detection: By generating longer, more interrelated syscall sequences, MOCK excels at finding complex, deep-seated vulnerabilities, uniquely discovering high-severity bugs (e.g., CVE-2022-2978, CVE-2022-40476) that require intricate interaction sequences.
• Neural Network Language Models Enhance Fuzzing: The integration of a dynamically updated BiGRU-based NNLM allows MOCK to learn syscall "language" and predict promising mutations, significantly improving test case quality.
• Adaptive Scheduling Balances Exploration and Exploitation: The UCB-1 algorithm effectively manages the trade-off between exploring new mutation strategies and exploiting known good ones, optimizing overall fuzzing efficiency and diversity.
• Warm-up Optimization is Key: Initial seeds and pre-trained models dramatically reduce the fuzzer's warm-up time, accelerating the discovery of vulnerabilities from the outset.

About the Speaker(s)

The talk was delivered by Jiacheng Xu. Based on the provided metadata and transcript, Jiacheng Xu is a researcher presenting work at the NDSS Symposium on optimizing kernel fuzzing. Further biographical details were not included in the provided input.