An RbTree Family Drama: Exploiting a Linux Kernel 0-day Through Red-Black Tree Transformations

An RbTree Family Drama: Exploiting a Linux Kernel 0-day Through Red-Black Tree Transformations

Speakers: William Liu (NVIDIA), Savino Dicanosa (Independent)

Conference: Hexacon

YouTube: https://www.youtube.com/watch?v=C-52Gwmce3w

Overview

In this Hexacon talk, security researchers William Liu of NVIDIA and Savino Dicanosa, an independent researcher, unveiled a sophisticated Linux kernel zero-day exploit, dubbed "An RbTree Family Drama." This presentation details CVE-2025-38001, a critical vulnerability found within the Linux network scheduler (traffic controller) subsystem. The researchers, part of the Crusaders of Rust Security Research Group, demonstrate how a seemingly innocuous kernel soft lockup can be escalated through intricate Red-Black Tree (RB-tree) manipulations into a full page Use-After-Free (UAF) and ultimately, arbitrary code execution, achieving root privileges.

The talk stands out not only for the technical depth of its exploit but also for its cross-platform and cross-architecture implications, successfully compromising various Linux distributions, including Ubuntu on ARM, Debian on x86, and multiple instances of Google's Kernel CTF (LTS, COS, and even a mitigation-hardened instance). The team's work earned them $82,000 in bounties from Google, along with a $10,000 stability bonus. Their innovative approach to circumventing Kernel CTF's proof-of-work mechanism also left a lasting "cultural impact," leading to its permanent removal from future bounty submissions. This article delves into the specifics of their discovery, the elegant RB-tree attack, and their ingenious methods for bypassing modern kernel mitigations.

Background

▶ Watch: Introduction: Linux Kernel 0-day via Red-Black Trees (0:00)

The Linux network scheduler, also known as the traffic controller (TC), is a fundamental subsystem designed to provide users with fine-grained control over how network packets enter and leave kernel network interfaces. It achieves this through objects called Queuing Disciplines (Qdiscs), which manage packet enqueuing and dequeuing. The simplest Qdisc, P50Fast, operates as a basic First-In, First-Out queue. More complex Qdiscs include the Token Bucket Filter (TBF), which regulates packet transmission based on available tokens, and NetEm (Network Emulator), a notoriously buggy Qdisc that can simulate network conditions like duplication, loss, corruption, and delay. Qdiscs can be chained together to form complex hierarchical structures or Qdisc trees, offering highly customized network behavior. Each Qdisc is identified by a major:minor handle, with root Qdiscs typically having a minor handle of zero.

The Hierarchical Fair Service Curve (HFSC) Qdisc, a central component in this exploit, supports multiple children and is known for its intricate interactions within these Qdisc trees. Historically, the network scheduler has been a fertile ground for vulnerabilities, with numerous Use-After-Frees (UAFs) and Denial-of-Service (DoS) bugs reported in Qdiscs like FQ_Codel, DRR, and HFSC itself. These vulnerabilities often arise from "nonsensical complex setups" created by security researchers, as one network maintainer notably complained on a mailing list, highlighting the tension between complex configurations and robust kernel invariants.

The journey to discovering CVE-2025-38001 began with William Liu's custom fuzzer, developed for his master's thesis at MIT. Targeting the network scheduler due to its history of bugs, the fuzzer soon identified a kernel soft lockup—a state where the kernel thread remains stuck for over 20 seconds without a context switch, typically indicating an infinite loop. The specific trigger involved an HFSC parent Qdisc with a NetEm child, where NetEm's packet duplication feature was enabled. This seemingly straightforward configuration, combining two "buggy" Qdiscs, laid the groundwork for the elaborate exploit that followed.

Key Findings

▶ Watch: Netem Qdisc: Packet Duplication Feature Explained (2:40)

The core of the "RbTree Family Drama" is CVE-2025-38001, initially manifesting as a kernel soft lockup (an infinite loop). The vulnerability arises from a specific interaction between the HFSC (Hierarchical Fair Service Curve) Qdisc and the NetEm (Network Emulator) Qdisc when NetEm's packet duplication feature is enabled and it's configured as a child of HFSC.

Here's a breakdown of the root cause:

1. Packet Entry and Classification: When a packet first enters the HFSC Qdisc via hfsc_enqueue, it's classified for the correct child (in this case, NetEm). A crucial first variable is set to true, indicating no packets were previously in the queue.
2. NetEm Duplication: The packet is then enqueued to the NetEm child. Because duplication is enabled, NetEm clones the packet.
3. Global Duplication Disable and Re-enqueue: NetEm's internal logic temporarily disables global duplication for the current NetEm object. It then re-enqueues the cloned packet back to the root of the Qdisc tree (HFSC). After this recursive call returns, NetEm restores the original duplication value.
4. Second Level of Recursion: The cloned packet re-enters hfsc_enqueue. Again, classification is trivial. Crucially, because no other packets have been inserted at this specific level of recursion, the first variable is once again set to true.
5. eltree_insert Call: After the NetEm enqueue call (where duplication is now disabled for the cloned packet), the HFSC enqueue function calls eltree_insert. This function constructs the eligible tree (L-tree) of classes eligible for dequeuing. Because first was true at this level, the NetEm object is inserted into the L-tree.
6. Double Insertion: The control flow then returns to the initial hfsc_enqueue call. Here, first was also true. Consequently, eltree_insert is called again for the same NetEm object. This results in the NetEm object being inserted twice into the L-tree.
7. Self-Referencing RB-node: During the second eltree_insert, the rb_node corresponding to the NetEm object becomes self-referential: its rb_left pointer is linked back to the object itself.
8. Infinite Loop (Soft Lockup): When the kernel attempts to dequeue a packet, it calls L_tree_get_my_l, which uses rb_first to find the least element. rb_first traverses the rb_left pointers. Because the NetEm object's rb_left points to itself, the kernel enters an infinite loop, causing the observed soft lockup.

While an infinite loop is a Denial-of-Service (DoS) bug, the researchers aimed for a more severe impact. They successfully escalated this DoS into a Use-After-Free (UAF) by preventing the kernel from dequeuing. This was achieved by introducing a TBF (Token Bucket Filter) Qdisc as the root, configured with a very low token rate.

1. Block Dequeue: With TBF at the root and a minimal token rate, dequeuing is blocked when tokens are exhausted.
2. Trigger Double Insertion: The HFSC-NetEm setup triggers the double insertion bug, creating the self-referencing rb_node in the L-tree.
3. Return to User Space: Since dequeuing is blocked, the kernel returns to user space instead of entering the infinite loop.
4. Free the Class: From user space, the researchers can then free the HFSC class object using a traffic control command. This frees one of the self-referencing rb_node instances while the other remains in the L-tree, creating a dangling pointer.
5. UAF Trigger: Any subsequent network activity that interacts with the L-tree (e.g., attempting to dequeue) will attempt to access the freed memory, triggering a Use-After-Free condition. This UAF on the rb_node structure became the foundation for their full kernel compromise.

Technical Deep Dive

▶ Watch: Historical Vulnerabilities in Traffic Control Subsystem (4:50)

The core of the exploit hinges on a sophisticated data-oriented attack against the Linux kernel's Red-Black Tree (RB-tree) implementation. Savino Dicanosa devised a method to leverage the UAF on an rb_node to achieve pointer duplication and ultimately a page Use-After-Free (UAF), which is highly portable and stable across various Linux systems and Kernel CTF instances.

Red-Black Tree Fundamentals

A Red-Black Tree is a self-balancing binary search tree that maintains specific properties (color rules) to ensure logarithmic time complexity for insertions, deletions, and lookups. When a node is inserted or removed, these operations can violate the color rules, necessitating tree rebalancing through rotations and recoloring. The Linux kernel's rb_node structure is critical here:

• __rb_parent_color: Stores the parent node's address and the current node's color (1 for black, 0 for red).
• rb_right: Pointer to the right child.
• rb_left: Pointer to the left child.

By gaining control over a freed rb_node, the attackers can manipulate these pointers.

Page Vector Allocation

The second key component is the page vector, which consists of a vector of pages. These are allocated by creating packet sockets and then using tpacket_setup to create a packet ring. A packet ring is a ring buffer shared between kernel and user space, typically for asynchronous packet I/O, but here used for exploitation. The attackers control the number of pages in the vector and the page order (size of each page block). Pages are allocated using get_free_pages, which returns their virtual addresses. Crucially, packet_map iterates through the page vector and maps each page to user space using vm_insert_page.

Exploit Strategy: From UAF to Page UAF

The overarching strategy is as follows:

1. Trigger Vulnerability: Cause the double insertion of the HFSC class into the eligible tree (L-tree) using the HFSC-NetEm bug.
2. Free and Replace: Free the HFSC class object (which contains the self-referencing rb_node) and spray the freed memory with a page vector. This effectively replaces the rb_node's fields with pointers to user-controlled pages, allowing the kernel to treat these pages as rb_nodes.
3. Pointer Leak (First Attempt - Failed): Savino's initial idea was to trigger an RB-tree transformation that would overwrite one of the page_vector's pointers (now seen as an rb_node pointer) with another rb_node address. Then, packet_map would be called to remap the corrupted page_vector to user space, granting arbitrary read/write. This failed because packet_map uses validate_page_before_insert, which rejects pages that are part of kernel slab allocations, preventing mapping of the manipulated rb_node pointers.

1. Successful Pointer Leak and Duplication (Second Attempt):

• Setup:
• Configure a TBF Qdisc as the root with a very low rate (e.g., 1 token) to block packet dequeuing, preventing the infinite loop and allowing control to return to user space.
• Saturate the kmalloc-1k slab cache to ensure new allocations land in fresh slabs.
• Allocate the vulnerable HFSC class (class 1).
• Allocate a second class, class 2, specifically surrounded by page_vector objects in memory (e.g., 16 page_vectors before and 16 after). This memory layout is crucial.
• Trigger the HFSC-NetEm vulnerability by sending a packet to class 1. This inserts class 1 twice into the L-tree. The DQ is blocked, so no infinite loop.
• Free class 1 and replace it with a page_vector. The rb_node fields of class 1 are now controlled by pointers to user-allocated pages. The first quadword of this page_vector must be set to 1 (representing a black node parent).

• Pointer Leak:
• Send a packet to class 2. The kernel calls L_tree_insert to insert class 2 into the L-tree.
• During insertion, the kernel compares class 2's CLA field with the CLA field of class 1 (now the page_vector). Since page_vector's CLA field is a large user-controlled value, class 2 takes the left path.
• class 2 is inserted as the right child of page_P (one of the controlled pages within the page_vector that replaced class 1).
• __rb_insert_color is called to rebalance the tree. However, because page_P's parent (the first quadword of the page_vector) was set to 1 (black), the rebalancing loop immediately breaks.
• This results in a pointer to class 2 being written into page_P (a user-controlled page), effectively leaking a kernel pointer to user space.

• Forging "Evil Grandpa" and Pointer Copy Primitive:
• The leaked pointer allows the researchers to locate class 2 in memory.
• A new malicious rb_node, nicknamed "evil grandpa," is forged. It's strategically placed 16 bytes before the next page_vector in memory that surrounds class 2. When cast as an rb_node, evil grandpa's rb_left child will now point to the first page of this target page_vector.
• First Tree Update: A Netlink message is sent to class 2, triggering an update (remove and re-insert).
• L_tree_remove removes class 2.
• L_tree_insert re-inserts class 2. During this, page_P's parent is modified to point to evil grandpa, and its color becomes red.
• The tree rebalances: page_P moves down, evil grandpa moves down, leading to a complex configuration where grandpa becomes the child of its grandchild. Crucially, the first page of the target page_vector is set to zero during this process.
• Second Tree Update (Pointer Copy): class 2 is removed again from the tree. During this deletion, evil grandpa becomes the designated successor node. The critical outcome is that the address of page_P (which contains the leaked pointer) is copied into evil grandpa's rb_left child, which, due to its strategic placement, corresponds to the first page of the target page_vector.
• This creates a powerful pointer duplication primitive: the address of page_P (a user-controlled page containing a leaked kernel pointer) now exists in two different page_vectors—its original one and the target one.

Page Use-After-Free Exploitation

With the pointer duplication, the researchers can now trigger a page UAF:

1. Locate Duplicated Page: Iterate through all page_vectors and identify the duplicated page (e.g., using a unique marker like 0xff).
2. Map Page: Map the page from user space. Its reference count increases to 2.
3. Free Original page_vector: Close the first packet socket, freeing the original page_vector. The page's reference count drops to 1.
4. Reclaim Page: Reclaim the page by writing to pre-allocated pipes. The pipe_write function internally calls alloc_page, which can reuse the freed physical page.
5. Trigger UAF: Close the second packet socket, freeing the target page_vector. Since this page_vector still held a reference to the page (which has now been reclaimed by the pipes), this action triggers a page Use-After-Free on the reclaimed page.

Achieving Root with Page UAF

With a reliable page UAF, the path to root is clear. The researchers employed a variation of the F_SETOWN_EX technique with fcntl:

1. F_SETOWN_EX: This fcntl command allows a user to provide a file descriptor and a mask. If the file descriptor is -1, a new file struct is allocated, and the mask is stored in its f_data field. Otherwise, an existing mask can be updated.
2. Control file Structure: By controlling the file structure through the UAF, the researchers can manipulate its fields.
3. Swap Pointers: The goal is to swap the f_data field (which can be user-controlled via the mask) with the f_cred field, which is a pointer to the current process's credentials.
4. Zero Out Credentials: Once f_data points to the credentials, multiple writes can be performed (via F_SETOWN_EX) to set the credential values (UID, GID, etc.) to zero, effectively granting root privileges.
5. Lower Byte Trick: A challenge arises because the lower bytes of the mask cannot be directly controlled. The trick is to use the upper bytes to write backwards, effectively zeroing out the entire credential structure.

This intricate sequence of RB-tree manipulations, memory spray, pointer leaks, and page UAF exploitation demonstrates a profound understanding of kernel internals and data structures.

Demo / Proof of Concept

▶ Watch: Reproducing the CVE: HFSC-Netem Setup (6:10)

The researchers provided compelling live demonstrations of their exploit's effectiveness and stability across various Linux environments. They successfully achieved root privileges on:

• LTS (Long Term Support) Kernel CTF instance: Demonstrated obtaining a reverse shell and extracting the flag.
• COS (Container Optimized OS) Kernel CTF instance: Again, a reverse shell and flag extraction were shown. This is Google's container-optimized version of their Kernel CTF, highlighting the exploit's capability against hardened environments.

A notable aside during the demo section involved the Kernel CTF submission process. At the time, Google's CTF used a Sloth EDF (Equally Difficult Function) proof-of-work (PoW) system to rate-limit submissions, requiring a 5-second computation. The Crusaders of Rust team, driven by a desire to guarantee their bounty, meticulously optimized the PoW solver. They discovered simplifications in the modulus used, reducing computation time to ~3 seconds. Further optimizations, including leveraging Zen 5's AVX512 ifma extensions for multiplication and streamlining the Google Form submission, brought their total submission time down to a record-breaking 3.6 seconds. This aggressive optimization led Google to permanently remove the proof-of-work component from future bounty submissions, a significant "cultural impact" credited to their efforts.

Finally, they demonstrated the exploit against a mitigation-hardened Kernel CTF instance. While the exploit against this target was acknowledged to have an 80% stability rate (implying a higher chance of a kernel crash), the live demo successfully dumped the flag, proving the exploit's ability to bypass modern kernel defenses, even if it resulted in a subsequent kernel crash. This showcases the extreme difficulty of fully neutralizing such complex exploitation techniques.

Defensive Implications

▶ Watch: Initial Code Walkthrough: HFSC-Netem Infinite Loop (6:48)

The talk provided a comprehensive look at how modern Linux kernel mitigations attempt to thwart such exploits and, critically, how the researchers devised strategies to bypass them.

Mitigations Encountered:

1. kalloc_split_var_size: This mitigation separates kernel allocations. Objects with a compile-time constant size go into kmalloc-X slabs, while objects with a runtime-determined size go into den_kmalloc-X slabs.

• Impact: This directly impacts the initial page_vector overlap strategy. The HFSC class (fixed size) would go into kmalloc-1k, but page_vector (runtime size) would go into den_kmalloc-1k, preventing the crucial same-slab overlap required for the pointer duplication technique.

1. slab_virtual (Pwn Apocalypse): A more robust mitigation, inspired by Chrome's PartitionAlloc. Instead of simply preventing slabs from being returned to the buddy allocator, slab_virtual ensures that every new slab allocation receives a new virtual memory address, even if the underlying physical page is reused.

• Impact: This effectively kills pointer-style cross-cache attacks. While physical pages can still be reused, their virtual addresses are randomized, preventing an attacker from predicting where a reclaimed page will appear in memory. Furthermore, slab_virtual also zeroes out pages every time a new slab is allocated, preventing data-only cross-cache attacks. This mitigation was a significant hurdle, forcing the researchers to abandon their original page_vector approach for mitigation-hardened targets.

1. random_k_caches: Upstreamed by Huawei around kernel 6.6, this mitigation introduces 16 random copies of each slab cache. When kmalloc is called, the specific slab cache used is determined by the allocation's return address and a kernel-internal random seed.

• Impact: This aims to diversify slab allocations, making it harder to predict where an object will land. It typically complements cross-cache attacks, but with slab_virtual preventing those, its primary effect is further randomization.

Bypassing Mitigations (Mitigation Exploit Attempt 2):

Given the limitations imposed by kalloc_split_var_size and slab_virtual, the researchers had to adapt their strategy for mitigation-hardened targets. The key insight was to leverage random_k_caches in an unexpected way: while it randomizes slab selection, it also implies that objects of the same slab size allocated from the same allocation site (i.e., the same return address) will consistently land in the same slab. This creates a limited type confusion opportunity.

1. Shared Allocation Code Path: They identified a shared allocation code path among Qdisc classes. Specifically, the TCTL_class Netlink command, when it calls the change function pointer, leads to kmalloc calls for different Qdisc classes (e.g., hfsc_change_class and htb_change_class) that share the same return address.
2. Type Confusion Target: This allows for a type confusion between an HFSC class and an HTB (Hierarchical Token Bucket) class, as they can be forced into the same slab, bypassing random_k_caches.
3. Exploit Flow:

• Construct the same L-tree with the vulnerable HFSC class and cause a UAF.
• Replace the freed HFSC class with an HTB class (type confusion). This creates an rb_node type confusion, as HTB is not meant to be in the HFSC eligible tree.
• Trigger a series of RB-tree transformations (by deleting and inserting other nodes) to achieve the specific goal: overwrite the htbx_stats field of the HTB class with an rb_node pointer.
• Leak Pointer: Dump the HTB class's xstats (extended statistics) via Netlink to leak the rb_left pointer that was written into it.
• Increment Pointer: The lower bytes of the leaked rb_left pointer overlap with the xstats.lens field. By sending packets to the HTB class, the lens variable (and thus the lower bytes of the rb_left pointer) can be incremented. This provides a controlled arbitrary increment primitive on a kernel pointer.
• Fake Pointers: Three layers of fake pointers are created in user space. The incremented kernel pointer is made to point 8 bytes before a controlled quadword.
• Overwrite qdisc Pointer: Through further complex RB-tree transformations (details of which are extensive and referred to the full write-up), the researchers managed to overwrite the HTB qdisc pointer with the incremented pointer.
• Delayed Trigger: A challenge was that the nq (enqueue) function pointer (the first quadword) couldn't be directly controlled. A workaround was a delayed trigger: TBF was set with a rate of 100, allowing ~5 seconds to perform the attack before packets would dequeue.
• Fake DQ Function Pointer: With the qdisc pointer corrupted, a fake DQ (dequeue) function pointer could be inserted.
• ROP Chain and KASLR Bypass: When packets finally dequeue, the fake DQ function pointer executes a ROP (Return-Oriented Programming) chain gadget, leading to a stack pivot into the CPU entry area.
• KASLR Bypass for CPU Entry Area: Since the CPU entry area address is randomized in kernel 6.6+, they used William's prefetch channel implementation (an entry_rb_it variant without a syscall) to reliably prefetch and leak this address, effectively bypassing KASLR (Kernel Address Space Layout Randomization).

This multi-stage, highly intricate bypass demonstrates that even with sophisticated mitigations, specific vulnerabilities in complex subsystems, combined with deep knowledge of data structures and memory management, can still lead to full system compromise.

Key Takeaways

• The Linux network scheduler, particularly Qdiscs like HFSC and NetEm, remains a complex and vulnerable attack surface, susceptible to intricate interactions leading to critical bugs.
• CVE-2025-38001 demonstrates how a seemingly innocuous kernel soft lockup (infinite loop) can be escalated into a powerful Use-After-Free by strategically delaying kernel operations (e.g., using TBF to block dequeuing).
• Sophisticated Red-Black Tree (RB-tree) manipulations are a viable and potent technique for achieving kernel primitives like pointer leaks and pointer duplication, even from a UAF on an rb_node structure.
• Modern kernel mitigations like kalloc_split_var_size, slab_virtual, and random_k_caches significantly raise the bar for exploitation, making direct memory overlaps and cross-cache attacks much harder or impossible.
• However, these mitigations can be bypassed through deep analysis, such as identifying shared allocation code paths to enable controlled type confusion, and leveraging obscure side channels (like prefetch channels for KASLR bypass).
• Even partial control over kernel data structures (e.g., specific fields within an rb_node or xstats) can be sufficient to construct multi-stage exploits leading to full kernel compromise. The exploit's 80% stability on mitigation-hardened targets and 100% stability on standard targets highlights its robustness.

About the Speaker(s)

William Liu is a security researcher at NVIDIA. His work includes significant contributions to Linux kernel vulnerability research, leading to multiple zero-day bounties and CVEs. He conducted his master's thesis research at the Massachusetts Institute of Technology (MIT), where he developed custom fuzzers for identifying kernel vulnerabilities, leading to the discovery of CVE-2025-38001. William is a member of the Crusaders of Rust Security Research Group and is known for previous work such as the entry_rb_it KASLR bypass and message_message attacks.

Savino Dicanosa is an independent security researcher and a key member of the Crusaders of Rust Security Research Group. He specializes in intricate kernel exploitation techniques, particularly those involving data structure manipulations like Red-Black Trees. His previous work includes the development of sophisticated techniques for escalating kernel bugs into full compromise, such as turning an infinite loop into a Use-After-Free. Savino's expertise was instrumental in developing the RB-tree attack presented in "An RbTree Family Drama."