K-LEAK: Towards Automating the Generation of Multi-Step Infoleak Exploits against the Linux Kernel

K-LEAK: Towards Automating the Generation of Multi-Step Infoleak Exploits against the Linux Kernel

Speakers: Zhengchuan Liang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=z92ChP9oyBY

Overview

The security of the operating system kernel is paramount, as it forms the trusted computing base for all modern systems. Despite continuous efforts, memory errors such as out-of-bounds (OOB) and use-after-free (UAF) vulnerabilities, largely due to the kernel's implementation in memory-unsafe languages like C and assembly, remain primary attack vectors. Modern kernels have implemented sophisticated exploit mitigations, with Kernel Address Space Layout Randomization (KASLR) being a critical example designed to randomize memory layouts and make reliable control-flow hijacking attacks exceedingly difficult. This is precisely where information leaks (infoleaks) become indispensable, as they serve to bypass KASLR by disclosing sensitive memory addresses or contents, including cryptographic keys.

Infoleaks typically arise from exploiting software vulnerabilities to reveal randomized memory layouts or sensitive program memory contents. These can be categorized into side-channel-based approaches (e.g., micro-architectural attacks) and memory-error-based approaches. K-LEAK, the framework presented by Zhengchuan Liang, focuses on the latter, where attackers leverage existing memory errors to leak information. A successful kernel infoleak exploit involves chaining unintended reads and writes to create a data-flow that propagates sensitive kernel information to userspace. While infoleaks are a crucial first step in any sophisticated kernel exploit chain, the automation of memory-error-based kernel infoleak generation has historically received surprisingly little attention, leaving a significant gap between theoretical potential and practical exploit automation.

K-LEAK aims to bridge this gap by proposing a novel graph-based data-flow reasoning and search framework. Its core innovation lies in unifying the handling of both intended and unintended data-flow fragments, supporting reasoning across syscall boundaries, and allowing for the derivation of intermediate primitives, such as new memory errors, before ultimately discovering a complete infoleak path. This comprehensive approach is packaged within a unified graph search algorithm, enabling systematic exploration of the vast search space to generate diverse and multi-step infoleak exploits against the Linux kernel.

Background

▶ Watch: Introduction to K-LEAK and infoleak motivation (0:00)

The Linux kernel, being the core of the operating system, is written predominantly in C and assembly, languages that offer high performance but lack inherent memory safety. This characteristic makes it perpetually vulnerable to memory errors like OOB accesses and UAF conditions, which can be exploited to read or write to unintended memory locations. To counter these vulnerabilities, modern kernels employ a suite of exploit mitigations. KASLR is a particularly effective countermeasure, as it randomizes the base addresses of kernel modules, the kernel image, and other memory regions, making it impossible for attackers to hardcode addresses for control-flow hijacking. Consequently, a prerequisite for most advanced kernel exploits is an infoleak to defeat KASLR.

The generation of infoleak exploits, especially those leveraging memory errors, presents unique challenges. Prior conceptual frameworks, such as a 2013 SoK paper, suggested that theoretically, any memory error could be exploited for an infoleak. However, these frameworks often remained program-agnostic and lacked the specific modeling required for concrete exploit generation in a complex environment like the Linux kernel. A more recent study (referred to as 46 in the transcript, likely AlphaEXP) provided a more concrete reasoning framework for Linux, but its primary focus was on finding useful kernel objects for generic exploits, not specifically for infoleaks, leading to imprecise data-flow analysis for this purpose.

A fundamental limitation of traditional data-flow analysis techniques, which are crucial for understanding how information propagates through a program, is their assumption of correct program execution. These techniques, often relying on Data-Flow Graphs (DFGs), model only intended data flows. They are inherently incapable of accounting for the unintended data flows introduced by memory errors, which are the very essence of an infoleak exploit. This inability to model error-induced data flows has been a major hurdle for automating infoleak generation.

Another significant challenge in kernel analysis is its multi-interaction nature. The kernel exposes numerous entry points through syscalls, and data can flow across these syscalls via global memory. An infoleak might involve sensitive information being stored in global memory by one syscall and then read and leaked by another. Traditional points-to analysis and data-flow analysis often struggle with this cross-syscall propagation. SUTURE (51), a static analysis framework, addressed this multi-interaction problem for the Linux kernel by using a summary-based approach to perform inter-procedural, flow-, context-, and field-sensitive points-to and data-flow analysis. While SUTURE's points-to analysis is valuable, its data-flow analysis relies on taint propagation, which can be less efficient and suitable for complex graph-based searches compared to a DFG. K-LEAK adopts SUTURE's robust points-to analysis but significantly enhances the data-flow reasoning by developing its own Memory-error-augmented Data-Flow Graph (M-DFG), specifically designed to capture both intended and unintended data flows for efficient infoleak exploit generation.

Key Findings

▶ Watch: Limitations of traditional data-flow analysis in kernel (2:00)

K-LEAK's evaluation on a comprehensive dataset of 250 real-world, fixed memory bugs from syzbot (a continuous fuzzer for Linux) yielded compelling results, demonstrating its effectiveness and scalability in automating infoleak exploit generation:

• High Exploitation Rate: K-LEAK successfully identified and verified infoleak paths for 40 out of the 250 syzbot cases (16% of the dataset). All 40 verified cases were capable of leaking full or transformed kernel pointers, effectively bypassing KASLR.
• Comprehensive Coverage of Prior Work: The framework statically found all 10 infoleak cases previously identified by ELOISE (14), a notable prior work in this domain, confirming its foundational capabilities.
• Diverse Exploit Strategies: K-LEAK was able to generate exploits employing a variety of strategies, including read-induced infoleaks (Rinfo), write-induced infoleaks (Winfo), and multi-step approaches where initial errors lead to new errors before an infoleak (e.g., Rnewerr + Rinfo and Wnewerr + Rinfo). Many bugs offered multiple distinct infoleak paths.
• Impact of Cross-Syscall Modeling: The ability to model data flows across syscall boundaries proved crucial, enabling K-LEAK to discover 12 additional infoleak cases. Notably, 10 of these cases involved unintended cross-syscall data flows, highlighting the importance of this capability for real-world kernel exploits.
• Value of Multi-Iteration Search: The iterative search algorithm, designed to find and leverage new memory errors, significantly expanded the exploit surface. The second iteration of K-LEAK's algorithm produced 9 infoleak paths that were derived from these newly discovered memory errors. Among these, 3 cases utilized the Wnerr + Rinfo strategy (excluding elastic objects), showcasing the framework's ability to uncover complex, multi-step attack chains.
• Scalability and Efficiency: K-LEAK demonstrated excellent performance. For each bug, the average context-sensitive Control Flow Graph (CFG) analyzed comprised approximately 500,000 basic blocks, resulting in an M-DFG with roughly 1,000,000 nodes and edges. Despite this complexity, the static search times were remarkably fast, with a median of 51ms (shortest 7ms, longest 81ms). The average length of data-flow paths was 12 nodes, often under 10 for direct infoleak paths, corresponding to CFG paths spanning up to 100 basic blocks.
• Comparison with Public Exploits: When compared against 11 additional CVEs with publicly available memory-error-based infoleak exploits, K-LEAK successfully detected infoleaks for 7 of them. This indicates strong practical relevance, although it also revealed current limitations regarding unmodeled exploit primitives (e.g., illegal free primitives, stack memory errors, control-flow based infoleaks).
• End-to-End Exploits: K-LEAK's output enabled the development of seven end-to-end exploits for specific syzbot bugs (e.g., 1d22a2c and 9ea5654), providing concrete proof of concept for its findings, albeit with manual effort still required for heap manipulation.

Technical Deep Dive

▶ Watch: Introducing M-DFG for unintended data-flow modeling (2:48)

K-LEAK's technical architecture is meticulously designed to address the complexities of kernel infoleak generation. Its problem scope focuses on automating memory-error-based infoleak exploits against the Linux kernel, specifically targeting heap-based memory errors like UAF and OOB. It assumes the attacker possesses knowledge of an initial memory error and a corresponding bug reproducer (e.g., a KASAN report from syzbot). Crucially, it operates under the assumption that attackers cannot yet hijack kernel control-flow, as infoleaks are often a prerequisite for such attacks (e.g., to bypass KASLR). The framework also assumes the absence of data-flow integrity mitigations.

The key insight behind K-LEAK is that by explicitly modeling the unintended data flows introduced by memory errors, existing efficient data-flow analyses can be leveraged to systematically generate infoleak exploits. This transforms the complex problem into a tractable graph search.

To realize this insight, K-LEAK tackles several technical challenges:

1. Modeling Unintended Data-Flow: Memory errors essentially involve dereferencing invalid pointers. From a data-flow perspective, an invalid pointer creates new, unintended aliasing between memory load and store operations. K-LEAK addresses this by designing a specialized memory-error-aware alias analysis.
2. Modeling Data-Flow Across System Calls: Kernel exploits frequently involve sequences of syscalls where data flows, both intended and unintended, can cross syscall boundaries. K-LEAK leverages the robust cross-syscall points-to analysis from SUTURE (51) and extends its DFG to handle these multi-interaction data flows.
3. Modeling Additional Memory Errors: A single memory error might not directly lead to an infoleak. For instance, an attacker might use an OOB write to corrupt an object's length field, which then leads to a new OOB read error when the object is accessed. K-LEAK employs an iterative search algorithm that not only searches for infoleak paths but also for attacker-controlled pointers that could derive new memory errors, feeding these back into subsequent iterations.

K-LEAK Workflow

The high-level workflow of K-LEAK begins with the Linux kernel source code and an initial memory error (e.g., a KASAN report). The source code is compiled into LLVM Intermediate Representation (IR) using Clang. SUTURE (51) performs points-to analysis to generate comprehensive points-to information. This information is then used by the M-DFG Builder to construct an intended M-DFG. The M-DFG Extender augments this graph with unintended data flows introduced by memory errors, creating an extended M-DFG. Finally, the M-DFG Searcher iteratively explores this graph for infoleak paths and new memory errors. If new memory errors are found, the M-DFG Extender incorporates them, and the search process repeats until a threshold is met or no new paths are discovered.

Memory-Error-Augmented Data-Flow Graph (M-DFG)

The M-DFG is the cornerstone of K-LEAK. It is a directed graph G = (N, E) where:

• Nodes (N) represent program elements:
• Variable Node: Represents the definition of a top-level variable.
• Load Node: Represents a memory read (LOAD) instruction.
• Store Node: Represents a memory write (STORE) instruction. Explicitly modeling LOAD and STORE instructions is critical for identifying new memory errors and updating the M-DFG with error-induced dependencies.
• Edges (E) represent data dependencies:
• Data Edge: Represents a direct def-use data flow, transferring data from source to destination.
• Pointer Edge: A special data flow applicable only to LOAD or STORE instructions, where the memory location depends on the source code.

M-DFG Construction:

1. Pre-Analysis: The M-DFG construction relies on the Linux kernel in LLVM's partial Static Single Assignment (SSA) form and flow-, context-, and field-sensitive inter-procedural points-to information from SUTURE. To preserve context-sensitivity, each LLVM instruction is cloned and associated with a context string.
2. M-DFG Builder: This component constructs the intended M-DFG. Standard def-use relations create nodes and data edges for binary, conversion, and Phi operations. Inter-procedural calls create nodes for arguments and return values. LOAD instructions create a variable node and a load node, with a data edge connecting the load to the variable, and a pointer edge connecting the pointer to the load. Similarly, STORE instructions create a store node, with a data edge from the value to the store, and a pointer edge from the pointer to the store. Special functions like copy_to_user are treated as special load/store nodes.

Crucially, the read-after-write (RAW) rule is applied: if the pointer variables of a store ls: q = v and a load li: v' = p are aliases (i.e., point to the same abstract memory object), a data edge ls -> li is added.

1. Cross-Syscall Data-Flow: To connect M-DFGs of different syscalls, K-LEAK leverages SUTURE's cross-syscall points-to information. If a store in one syscall aliases with a load in another, the RAW rule is applied to add cross-syscall RAW edges, modeling multi-interaction data flows.

M-DFG Extender and Memory-Error-Aware Points-to Analysis

The M-DFG Extender is where K-LEAK models unintended data flows. Given a memory error, the key challenge is to determine what unintended memory location an invalid pointer can point to. Traditional points-to analysis cannot answer this, so K-LEAK developed a memory-error-aware points-to analysis:

• Adjacent Objects: For OOB pointers, K-LEAK determines what memory objects may be allocated adjacently by relying on previously summarized objects from published work (13-15).
• OOB Capability: KASAN reports are leveraged to extract concrete OOB capabilities. For a UAF read within a kmalloc-192 slab, for instance, the points-to set of the UAF pointer variable is updated to include all objects that could be reallocated in that UAF slot. This enables the application of the RAW rule to add unintended RAW edges. Similar logic applies to dangling pointers.
• Arbitrary Pointers: If a pointer's capability is confirmed to be arbitrary (attacker-controlled), K-LEAK follows prior conventions (14, 46): arbitrary reads are assumed to pair with all locations inside all objects (adding corresponding RAW edges), while arbitrary writes are assumed not to pair with any objects to prevent corruption of critical kernel data structures when panic_on_oops is off.

The M-DFG offers several advantages: Efficiency through graph-based algorithms versus taint propagation, explicit New Memory Error Reasoning via pointer edges, and a Combined Search for both infoleaks and new errors using a single iterative BFS.

Search on M-DFG: Infoleak Search

Infoleak search is a graph search problem on the M-DFG.

• Infoleak Path Definition: A path of data edges from a source node (sensitive information like kernel pointers, crypto keys, network messages) to a sink node (functions leaking data to userspace, e.g., copy_to_user, nla_put, memcpy to userspace, _printk).
• Search Process:

1. Add unintended RAW edges for each memory error.
2. Use Breadth-First Search (BFS) to find paths from sources to sinks.
3. Categorize paths as read-induced infoleak (Rinfo) or write-induced infoleak (Winfo) based on the primitive causing the unintended RAW edge.

• Feasibility Verification: To reduce false positives from static analysis imprecision, K-LEAK employs a dynamic verification process using symbolic execution (based on Angr 40, similar to SyzScope 54).
• Control-Flow Feasibility: Ensures a feasible control-flow path exists for the data-flow.
• RAW Edge Feasibility: Verifies that static points-to aliases are dynamically reachable.
• Symbolic execution takes a kernel snapshot, symbolizes attacker-controlled regions and sensitive information, and checks if the sensitive data flows to userspace. For cross-syscall paths, it assumes heap fengshui (49) is feasible to ensure object placement.

Search on M-DFG: New Memory Error Search & Iterative Algorithm

K-LEAK also searches for opportunities to create new memory errors.

• New Memory Error Search: Finds data-flow paths from attacker-controlled data (e.g., copy_from_user nodes) to a pointer variable node linked to a LOAD or STORE instruction via a pointer edge.
• Capability Determination: Symbolic execution precisely analyzes the controlled pointer's value to determine if it has arbitrary or limited capability.
• Categorization: New errors are categorized as read-induced new error (Rnerr) or write-induced new error (Wnerr).
• Iterative Search Algorithm (Algorithm 1): This algorithm combines infoleak and new memory error searches. It starts with RAW edges from the initial error, populating a worklist. In each iteration, it dequeues an edge, finds paths, and checks for infoleaks (verifying and adding to leakPaths) or new memory errors (verifying, determining capability, extending M-DFG with new RAW edges, and enqueuing them). The process repeats for a limited number of iterations (e.g., 2 in evaluation) or until no new paths are found, naturally categorizing multi-step exploit strategies like Wnerr + Rinfo.

The implementation leverages Clang for LLVM IR, SUTURE for points-to analysis (limited to relevant syscalls), and a C++ program with Boost Graph and Boost Multi Index for M-DFG construction. Symbolic execution is handled by an Angr-based framework. Manual analysis and GDB are used for final exploitability verification.

Demo / Proof of Concept

▶ Watch: K-LEAK's problem scope and core innovation (4:00)

While K-LEAK primarily focuses on automated path discovery, its outputs are concrete enough to enable the development of seven end-to-end exploits for specific syzbot bugs. These represent practical proof-of-concept demonstrations of the framework's capabilities. K-LEAK provides the infoleak data-flow path and the corresponding control-flow path, significantly streamlining the exploit development process, although manual effort for heap manipulation (e.g., heap fengshui) is still required to ensure objects are placed as expected.

Two case studies from the evaluation illustrate K-LEAK's ability to identify diverse and complex infoleak strategies:

1. Winfo Strategy and Unintended Cross-Syscall Data Flow (syzbot case ID 9ea5654):

This bug involved multiple OOB write errors in the kmalloc-192 slab, specifically writing heap and function pointers to out-of-bound memory locations. K-LEAK, leveraging the kmalloc-192 capability derived from KASAN reports, identified that these OOB writes could alias with struct user_key_payload objects. This allowed the framework to add unintended RAW edges connecting the memory error store nodes to a copy_to_user load node. The result was the discovery of three data-flow paths that started from sensitive kernel function pointers and ended at a userspace leaking sink. Successfully developing an end-to-end exploit for this case demonstrated a Winfo (write-induced infoleak) strategy, where an OOB write directly led to an infoleak. This particular exploit also highlighted how unintended cross-syscall data flow was critical, as the write and read operations could occur in different syscall contexts.

1. Rinfo and Rnerr + Rinfo Strategies (syzbot case ID 148d2f1):

This case involved a dangling pointer struct drm_master *master within the drm_getunique function. This dangling pointer made master->unique and master->unique_len attacker-controlled. K-LEAK identified that this control could lead to a new memory read error at a subsequent copy_to_user call, where the attacker-controlled master->unique_len dictates the amount of data read OOB. This scenario exemplifies an Rnerr + Rinfo (read-induced new error followed by a read-induced infoleak) strategy. Additionally, the initial memory read error (u_unique_len = master->unique_len) itself, in the first iteration of the search, directly led to an Rinfo path in drm_ioctl. This case effectively showcased K-LEAK's capability to identify exploits leveraging multiple, distinct infoleak strategies from a single initial vulnerability.

Defensive Implications

▶ Watch: Technical challenges in modeling kernel data-flow (4:30)

K-LEAK provides critical insights for kernel defenders by highlighting the sophisticated ways memory errors can be chained and exploited for information leaks. Its findings underscore several key areas for defensive action:

• Comprehensive Vulnerability Remediation: K-LEAK demonstrates that even seemingly minor memory errors, such as small OOB reads or writes, can serve as primitives in complex, multi-step infoleak exploits. Defenders must move beyond isolated bug fixes to consider the broader exploitability context, including how a bug might be used to derive new memory errors or interact with other kernel objects.
• Awareness of Unintended Cross-Syscall Data Flows: The framework's ability to model unintended data propagation across syscall boundaries is a significant revelation. It implies that security analyses must extend beyond individual syscalls to consider the combined effect of sequences of syscall interactions. A bug in one syscall might expose sensitive data that is then unintentionally leaked by another, seemingly unrelated, syscall.
• Strengthening Data-Flow Integrity (DFI): K-LEAK operates under the assumption that DFI mitigations are absent. The widespread success of K-LEAK in finding infoleaks suggests that stronger, more pervasive DFI mechanisms in the kernel could significantly raise the bar for attackers. Such mitigations would make it substantially harder for unintended data flows, especially those originating from memory errors, to propagate to sensitive sinks.
• Improving Heap Allocator Predictability: The success of many infoleaks, particularly those involving UAF and OOB, relies on heap fengshui to place specific objects at predictable memory locations. Research into more randomized and less predictable heap allocators could make these types of exploits much harder to reliably achieve, even if an infoleak path is theoretically identified.
• Enhanced Memory Error Reporting: KASAN reports, while invaluable, have limitations in precisely determining the full capability of an OOB bug. Integrating approaches like KOOBE (13) for more precise capability reasoning could provide developers with a clearer understanding of the potential impact of a memory error, aiding in more robust mitigation strategies.
• Leveraging K-LEAK for Defensive Analysis: The framework itself could be adapted for defensive purposes. By running K-LEAK on newly identified vulnerabilities or during kernel development, security teams could proactively identify potential infoleak paths before they are discovered and exploited by attackers. This shift towards automated exploitability analysis can greatly enhance proactive security.
• Addressing Kernel Liveness and Useless Constraints: K-LEAK identified cases where attacker-controlled data could crash the kernel or where sensitive information was subject to "useless constraints" (e.g., controlledData == kernel_ptr). While K-LEAK conservatively flags these as harder to exploit, future defensive work could focus on making such scenarios definitively unexploitable, for instance, by implementing stricter validation on attacker-controlled inputs or by ensuring that critical kernel pointers are never exposed to such constraints.

Key Takeaways

• Automated Multi-Step Infoleak Generation: K-LEAK is a novel graph-based framework that automates the generation of multi-step, memory-error-based infoleak exploits against the Linux kernel, significantly bridging the gap between theoretical potential and practical exploit automation.
• Memory-Error-Augmented Data-Flow Graph (M-DFG): Its core innovation is the M-DFG, which explicitly models both intended and unintended data flows introduced by memory errors, enabling efficient graph-based data-flow analysis for exploit discovery.
• Comprehensive Exploit Modeling: K-LEAK effectively models cross-syscall data propagation (both intended and unintended) and iteratively discovers new memory errors that can be chained to form complex, multi-step infoleak exploits.
• Proven Effectiveness and Scalability: Evaluated on 250 real-world syzbot bugs, K-LEAK identified verified infoleak paths in 40 cases, including all 10 previously studied ELOISE cases. Its graph-based search is highly scalable, with median search times of 51ms for M-DFGs containing approximately 1,000,000 nodes and edges.
• Limitations and Future Work: While powerful, K-LEAK has limitations, including assumptions about successful heap fengshui, unmodeled error types (e.g., illegal free primitives, stack memory errors), and the absence of data-flow integrity (DFI) considerations. These represent key areas for future research and kernel hardening.
• Broader Exploit Generation Potential: The M-DFG design is versatile and has broader implications beyond infoleaks, serving as a general infrastructure for automating other types of memory-error-based exploit generation, such as achieving arbitrary code execution by chaining unintended writes to overwrite function pointers.

About the Speaker(s)

Zhengchuan Liang is the speaker who presented K-LEAK. Based on the provided metadata and transcript, no further biographical details are available.