What You Need to Know About StackRot – CVE-2023-3269

StackRot, identified as CVE-2023-3269 is a 7.8 HIGH use-after-free vulnerability in the Linux kernel versions 6.1 to 6.4 that can lead to privilege escalation. The vulnerability, which was disclosed by Ruihan Li who also released detailed information about it, is caused by a change in the VMA (Virtual Memory Address) tree structure from using red-black trees to maple trees. 

The maple tree, responsible for managing virtual memory areas, can undergo node replacement without properly acquiring the MM write lock, leading to use-after-free issues. An unprivileged local user could use this flaw to compromise the kernel and escalate their privileges.

Red-Black Trees

Red-black trees are a type of self-balancing binary search tree. They were introduced by Rudolf Bayer and named by Leo J. Guibas in 1972. These trees maintain their balanced structure by enforcing a set of rules that ensure a logarithmic height, resulting in efficient search, insert, and delete operations.

Key properties of red-black trees:

• Each node is assigned a color, either red or black.
• The root node is always black.
• All leaves (null or NIL nodes) are considered black.
• If a red node has children, they must be black.
• Every path from a node to its descendant leaves contains the same number of black nodes (known as the black height).

The balancing rules of red-black trees guarantee that the longest possible path from the root to a leaf is no more than twice as long as the shortest path. This property ensures the tree remains balanced, which in turn guarantees efficient operations.

The rbtree structure provides efficient search, insert, and delete operations but has certain drawbacks.

• The rbtree, which stores the VMAs, requires a doubly linked list for efficient traversal. Walking the nodes in numerical order is not very efficient. 
• The rbtree‘s integration with the VMA structures leads to the entire VMA being loaded into the cache even if it’s not of interest, resulting in suboptimal cache utilization. 

The rbtree also poses challenges for concurrent access and contention due to the mmap_sem lock.

Maple Trees

The Maple Tree method which was developed by Liam Howlett and Matthew Wilcox aims to address limitations in the current Linux Memory Management system’s use of the rbtree (red-black tree) structure to manage virtual memory areas (VMAs). 

The Maple Tree is a range-based B-tree designed to be RCU-safe (Read-Copy-Update) and capable of tracking gaps. It stores VMAs in separate nodes, allowing leaves to be copied and updated without readers having to leave the tree. Gaps in the VMA space are tracked within the tree, and the largest gap in each subtree is reported. The branching factor of the Maple Tree is larger than that of the rbtree, resulting in a shorter tree structure and smaller cache footprint.

The Maple Tree aims to provide a simple interface for basic data storage needs while offering an advanced interface for more complex operations, such as managing VMAs. The advanced interface allows users to optimize operations and pre-allocate storage space. It also aims to replace the doubly linked lists in the kernel subsystem code with iterators that accept limits.

The goal is to improve the performance and scalability of the Linux Memory Management system, particularly for handling VMAs.

StackRot

Maple Trees provide a promising solution, but their implementation is complex. The StackRot vulnerability occurs when using the mmap() system call to establish memory mappings. During this process, the kernel creates a vm_area_struct structure for each virtual memory area (VMA) to store mapping-related information. In the context of maple trees, intervals represent ranges of memory and can either point to a VMA or indicate a gap between allocated memory regions. While writers are required to hold an exclusive lock, there is a specific aspect related to stack expansion that requires attention. The stack, mapped with the MAP_GROWSDOWN flag, automatically expands when an address below the region is accessed.

During stack expansion, the start address of the corresponding VMA and the associated interval within the maple tree are adjusted. Interestingly, these adjustments are made without holding the MM write lock. Typically, a gap exists between the stack VMA and its neighboring VMA due to a stack guard enforced by the kernel. When expanding the stack, only the pivot value in the maple node needs to be updated, which can be done atomically. If the neighboring VMA also has the MAP_GROWSDOWN flag, the stack guard is not enforced, and the stack expansion eliminates the gap between the two VMAs. Removing the gap requires updating the maple node. However, because maple trees are RCU-safe, in-place overwriting of nodes is not possible. Instead, a new node is created, triggering node replacement, and the old node is later destroyed using an RCU callback.

The vulnerability stems from a race condition. While the RCU callback for freeing the old node is scheduled to execute after all pre-existing RCU critical sections, accessing VMAs only requires holding the MM read lock and does not enter the RCU critical section. Consequently, the RCU callback can be invoked, and the old node can be freed while pointers to the old node are still being used elsewhere. This results in a use-after-free vulnerability, where subsequent attempts to access the old node can lead to undefined behavior or security issues.

In summary, the vulnerability occurs during stack expansion when the elimination of a gap triggers node replacement in the maple tree. The asynchronous freeing of the old node through an RCU callback, while pointers to the old node are still accessible, leads to a use-after-free vulnerability. Exploiting this vulnerability could potentially allow an attacker to elevate privileges.

Fix and Remediation

To address this vulnerability, a patch was released on June 28th, 2023, as a fix in the Linux kernel code. The fix ensures proper locking during stack expansion and provides a consistent approach across different architectures. 

Users are advised to patch their systems by upgrading to the fixed versions corresponding to their kernel versions (6.1.37 for 6.1.x, 6.3.11 for 6.3.x, and 6.4.1 for 6.4.x).

You can find a comprehensive list of Linux distributions that utilize kernel version 6.1 or above on DistroWatch.

Recommendations

It is highly recommended to apply the patch promptly since an exploit for the vulnerability is expected to be published by the end of July. The vulnerability has the potential to allow an attacker to escalate privileges, making timely patching essential for maintaining system security.

About the author: Ofri Ouzan is a security researcher with Rezilion.