The transition from the red-black tree data structure to the maple tree in the Linux kernel 6.1 has led to a vulnerability (CVE-2023-3269) that allows an unprivileged user to execute their code with kernel privileges. This vulnerability, codenamed StackRot, has been present since the release of kernel 6.1 and has been fixed in updates 6.4.1, 6.3.11, and 6.1.37.
The maple tree structure is a variant of the B-tree that supports range-based indexing and is designed for efficient cache utilization on modern processors. Compared to the red-black tree, using the maple tree allows for better performance. The vulnerability arises from an error in the stack expansion handler — in the maple tree structure used for managing virtual memory areas in the kernel, replacing a node in the tree could occur without a write lock, creating conditions for accessing freed memory (use-after-free).
Exploiting the vulnerability was complicated by the fact that nodes in the maple tree structure are freed in a delayed manner using callback calls with RCU (Read-copy-update) locks. Nevertheless, researchers managed to overcome the challenges and prepare a working exploit, which they plan to publish at the end of July to give users time to update their systems. Exploitation is possible in almost all kernel configurations and requires only minimal privileges.
Source: opennet.ru
