CVE-2024-50200
Publication date:
08/11/2024
In the Linux kernel, the following vulnerability has been resolved:<br />
<br />
maple_tree: correct tree corruption on spanning store<br />
<br />
Patch series "maple_tree: correct tree corruption on spanning store", v3.<br />
<br />
There has been a nasty yet subtle maple tree corruption bug that appears<br />
to have been in existence since the inception of the algorithm.<br />
<br />
This bug seems far more likely to happen since commit f8d112a4e657<br />
("mm/mmap: avoid zeroing vma tree in mmap_region()"), which is the point<br />
at which reports started to be submitted concerning this bug.<br />
<br />
We were made definitely aware of the bug thanks to the kind efforts of<br />
Bert Karwatzki who helped enormously in my being able to track this down<br />
and identify the cause of it.<br />
<br />
The bug arises when an attempt is made to perform a spanning store across<br />
two leaf nodes, where the right leaf node is the rightmost child of the<br />
shared parent, AND the store completely consumes the right-mode node.<br />
<br />
This results in mas_wr_spanning_store() mitakenly duplicating the new and<br />
existing entries at the maximum pivot within the range, and thus maple<br />
tree corruption.<br />
<br />
The fix patch corrects this by detecting this scenario and disallowing the<br />
mistaken duplicate copy.<br />
<br />
The fix patch commit message goes into great detail as to how this occurs.<br />
<br />
This series also includes a test which reliably reproduces the issue, and<br />
asserts that the fix works correctly.<br />
<br />
Bert has kindly tested the fix and confirmed it resolved his issues. Also<br />
Mikhail Gavrilov kindly reported what appears to be precisely the same<br />
bug, which this fix should also resolve.<br />
<br />
<br />
This patch (of 2):<br />
<br />
There has been a subtle bug present in the maple tree implementation from<br />
its inception.<br />
<br />
This arises from how stores are performed - when a store occurs, it will<br />
overwrite overlapping ranges and adjust the tree as necessary to<br />
accommodate this.<br />
<br />
A range may always ultimately span two leaf nodes. In this instance we<br />
walk the two leaf nodes, determine which elements are not overwritten to<br />
the left and to the right of the start and end of the ranges respectively<br />
and then rebalance the tree to contain these entries and the newly<br />
inserted one.<br />
<br />
This kind of store is dubbed a &#39;spanning store&#39; and is implemented by<br />
mas_wr_spanning_store().<br />
<br />
In order to reach this stage, mas_store_gfp() invokes<br />
mas_wr_preallocate(), mas_wr_store_type() and mas_wr_walk() in turn to<br />
walk the tree and update the object (mas) to traverse to the location<br />
where the write should be performed, determining its store type.<br />
<br />
When a spanning store is required, this function returns false stopping at<br />
the parent node which contains the target range, and mas_wr_store_type()<br />
marks the mas->store_type as wr_spanning_store to denote this fact.<br />
<br />
When we go to perform the store in mas_wr_spanning_store(), we first<br />
determine the elements AFTER the END of the range we wish to store (that<br />
is, to the right of the entry to be inserted) - we do this by walking to<br />
the NEXT pivot in the tree (i.e. r_mas.last + 1), starting at the node we<br />
have just determined contains the range over which we intend to write.<br />
<br />
We then turn our attention to the entries to the left of the entry we are<br />
inserting, whose state is represented by l_mas, and copy these into a &#39;big<br />
node&#39;, which is a special node which contains enough slots to contain two<br />
leaf node&#39;s worth of data.<br />
<br />
We then copy the entry we wish to store immediately after this - the copy<br />
and the insertion of the new entry is performed by mas_store_b_node().<br />
<br />
After this we copy the elements to the right of the end of the range which<br />
we are inserting, if we have not exceeded the length of the node (i.e. <br />
r_mas.offset
Severity CVSS v4.0: Pending analysis
Last modification:
03/11/2025