CVE-2026-5290
Overview
Background
- `cc::RTree`
- the compositor’s spatial index (built in
cc/base/rtree.h) over rectangles, used by compositing/paint to look up display items by region; its nodes live in a singlestd::vectormembernodes_. - STR build / `Build`
cc::RTree<T>::Buildbulk-loads the tree with the Sort-Tile-Recursive algorithm, firstreserve()-ingnodes_to a predicted node count and then populating it viaBuildRecursive/AllocateNodeAtLevel.- `kMaxChildren` / `kMinChildren`
- the branch factor bounds (11 and 6); STR’s “remainder” logic sometimes creates nodes with
kMinChildreninstead ofkMaxChildren, producing more nodes than a perfectly balanced tree. - Reserve-then-point invariant
- after
nodes_.reserve(node_count), the build stores raw pointers (root_, child links) intonodes_; if the vector ever reallocates, every such pointer dangles.
Root Cause Analysis
Verify before building a PoC
What the commit does not establish: FP-underestimation root cause is confirmed by the diff/commit message, but the reallocation->UAF chain is not shown in the hunk, and the retained CHECK_GT is described as catching miscounts before reallocation, so the corruption primitive is inferred not proven.
Pre-patch, Build estimated the node count with a floating-point formula using std::log and std::pow ((n^d − 1)/(n − 1) + kMinChildren) and reserved exactly that many entries in nodes_. For certain input sizes this estimate was too small — the commit documents 1,771,562 rects (11^6 + 1) needing 177,163 nodes while the formula returned 177,162 — because of floating-point precision limits for large N and STR’s remainder logic inflating the true count. When the reserved capacity was exceeded during BuildRecursive, nodes_ reallocated, invalidating the raw node pointers already stored into it, giving a use-after-free of the moved-from nodes_ buffer. The prior if (node_count > nodes_.max_size()) guard only caught the opposite (over-estimation) failure and did nothing for under-estimation.
The fix replaces the transcendental formula with a precise integer bottom-up sum — iterating n = (n + kMaxChildren - 1) / kMaxChildren and accumulating node_count at each level — so the reserve never underestimates, and relies on the retained CHECK_GT in AllocateNodeAtLevel to turn any residual miscount into a safe crash rather than a reallocation.
nodes_ reallocate mid-build and invalidate stored node pointers, and the fix computes the exact bound with pure integer arithmetic.Attack Path
- Produce a large rect set
Cause the renderer/compositor to build an
RTreeover a very large number of rectangles (e.g., a paint/display-item list yielding ~1.77M rects), reaching an input size the floating-point estimate underestimates. - Under-reserve `nodes_`
Buildreserves fewer entries than STR actually needs for that size, leaving the capacity short of the true node count. - Reallocation during build
BuildRecursive/AllocateNodeAtLevelpush beyond the reserved capacity, sonodes_reallocates and frees its old backing buffer. - Use-after-free
Raw node pointers previously stored into
nodes_(root_and child links) now reference the freed buffer, and continued build/traversal dereferences them. The exact dangling access and any exploitation primitive are(inferred); the diff establishes the reallocation-invalidation mechanism, and the regression/fuzz tests assertBuildmust not crash.
Impact Assessment
nodes_ during cc::RTree::Build, causing a use-after-free of node memory in the process that runs compositing. The vendor advisory rates this high severity and describes it as a use-after-free in Compositing; it does not report in-the-wild exploitation. Exact exploitability (controlled reuse, read/write primitive, or code execution) is (inferred) — historically such crashes were triaged via DisplayItemList::Finalize() crash keys rather than demonstrated as exploited.Changed Functions
| Function | Change | Notes |
|---|---|---|
cc_testcc/BUILD.gn |
modified | |
forcc/base/rtree.h |
modified |
Files Changed
cc/BUILD.gncc/base/DEPScc/base/rtree.hcc/base/rtree_unittest.cc
Audit Directions
- Floating-point math backing memory sizingFlag any capacity/reserve/allocation count derived from
std::pow,std::log, or other floating-point operations; architecture- and optimization-dependent rounding can under- or over-shoot a size that must be exact. - Reserve-then-store-raw-pointersAudit containers (especially
std::vector) that are reserved once and then have interior pointers/raw_ptrs stored into them; any reallocation invalidates those pointers, so the reserve must provably bound all later insertions. - Guards that catch only one failure directionReview bounds checks like
count > max_size()that defend against over-estimation while silently permitting the under-estimation that actually corrupts memory; ensure the dangerous direction is the one that is checked (or made impossible, as here, with a precise computation plus aCHECKat the allocation site).
Patch
From d7f98463b2b85ef614b0bf50a9dfaafc505b0802 Mon Sep 17 00:00:00 2001
From: Andrew Paseltiner <apaseltiner@chromium.org>
Date: Thu, 26 Mar 2026 13:40:26 -0700
Subject: [PATCH] [cc] Fix RTree node count underestimation
This is a followup to crrev.com/c/7704355.
The previous formula for estimating the number of nodes required for
the STR algorithm in cc::RTree::Build underestimated the count for
certain inputs (e.g., 1,771,562 rects).
This CL replaces the floating-point formula with a precise bottom-up
calculation of the required nodes at each level. The specialized
crash keys (crbug.com/447555058) are removed because they were
diagnostic scaffolding for the previous floating-point approximation.
Floating-point operations can exhibit non-deterministic behavior
across different architectures and compiler optimizations, which
likely explains the 'inexplicable' math errors, such as node count
estimates exceeding `max_size()`, that the keys were designed to
triage. Since the new calculation uses pure integer arithmetic to
deterministically simulate the exact allocation pattern, these
categories of non-deterministic or 'impossible' errors are
eliminated by design. Should similar issues crop up again in the
future, the diagnostic keys can be re-introduced.
The failure of the original calculation was due to:
1. Floating-point precision limits in std::pow and std::log for
large N.
2. The STR algorithm's 'remainder' logic, which avoids sparse nodes
by occasionally creating nodes with kMinChildren (6) instead of
kMaxChildren (11), leading to a higher node count than a
perfectly balanced tree.
Comparison for power-of-11+1 sizes:
| Size (N) | Old Est | Actual | Diff | Status |
|--------------|----------|----------|------|--------|
| 12 | 7 | 3 | 4 | PASS |
| 122 | 18 | 15 | 3 | PASS |
| 1332 | 139 | 137 | 2 | PASS |
| 14642 | 1470 | 1469 | 1 | PASS |
| 161052 | 16111 | 16111 | 0 | PASS |
| 1771562 | 177162 | 177163 | -1 | FAIL |
| 19487172 | 1948723 | 1948725 | -2 | FAIL |
While the new node count calculation is O(log n) compared to the
previous O(1) estimate, the performance impact should be
negligible as it replaces expensive transcendental floating-point
operations (pow, log) with a handful of simple integer operations,
and is dwarfed by the O(n) work in the rest of the Build function.
The CHECK_GT in AllocateNodeAtLevel is retained to prevent future
regressions. A followup change may replace the vector of nodes
with a fixed-size heap array once the node count is known.
A regression test for the 1.77M rects case and a new fuzz test for
cc::RTree::Build are included in cc_unittests.
Fixed: 496205576, 447555058
Change-Id: Ib055f9e21f195d5526b1f73c4dc958c10bfff259
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/7704300
Reviewed-by: Vladimir Levin <vmpstr@chromium.org>
Commit-Queue: Andrew Paseltiner <apaseltiner@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1605754}
---
diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index a6732cf..779790b0 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn
@@ -775,6 +775,8 @@
cc_test("cc_unittests") {
use_xvfb = use_xvfb_in_this_config
+ fuzztests = [ "RTreeTest.BuildDoesNotCrash" ]
+
sources = [
"base/delayed_unique_notifier_unittest.cc",
"base/histograms_unittest.cc",
diff --git a/cc/base/DEPS b/cc/base/DEPS
index 909b4a27..2e99d3c 100644
--- a/cc/base/DEPS
+++ b/cc/base/DEPS
@@ -8,5 +8,6 @@
specific_include_rules = {
".*unittest\.cc": [
"+cc/test",
+ "+third_party/fuzztest",
],
}
diff --git a/cc/base/rtree.h b/cc/base/rtree.h
index bcd48886..a7fc6d4 100644
--- a/cc/base/rtree.h
+++ b/cc/base/rtree.h
@@ -17,9 +17,7 @@
#include <vector>
#include "base/check_op.h"
-#include "base/debug/crash_logging.h"
#include "base/memory/raw_ptr_exclusion.h"
-#include "base/notreached.h"
#include "base/numerics/clamped_math.h"
#include "ui/gfx/geometry/rect.h"
@@ -152,8 +150,6 @@
void GetAllBoundsRecursive(const Node<T>& node,
std::map<T, gfx::Rect>* results) const;
- NOINLINE void AddCrashKeysForTreeSizeAndCrash(size_t node_count) const;
-
// This is the count of data elements (rather than total nodes in the
// tree)
size_t num_data_elements_ = 0u;
@@ -205,31 +201,21 @@
node->num_children = 1;
node->children[0] = std::move(branches[0]);
} else if (num_data_elements_ > 1u) {
- // Determine a reasonable upper bound on the number of nodes to prevent
- // reallocations. This is basically (n**d - 1) / (n - 1), which is the
- // number of nodes in a complete tree with n branches at each node. In the
- // code n = |branch_count|, d = |depth|. However, we normally would have
- // kMaxChildren branch factor, but that can be broken if some children
- // don't have enough nodes. That can happen for at most kMinChildren nodes
- // (since otherwise, we'd create a new node).
- size_t branch_count = kMaxChildren;
- double depth = log(branches.size()) / log(branch_count);
- size_t node_count =
- static_cast<size_t>((std::pow(branch_count, depth) - 1) /
- (branch_count - 1)) +
- kMinChildren;
-
- // TODO(crbug.com/447555058): This check merely exists to replicate the
- // check in Vector<RTree<T>::Node<T>>::reserve(). This check should never
- // fail but, inexplicably, is failing for some users. If additional debug
- // data shows this bug is non-actionable, this code should be removed. Until
- // then, the perf impact should be minimal, since it is comparing a value in
- // a register to a const.
- if (node_count > nodes_.max_size()) [[unlikely]] {
- AddCrashKeysForTreeSizeAndCrash(node_count);
- NOTREACHED();
+ // Determine a precise upper bound on the number of nodes to prevent
+ // reallocations. This is a bottom-up calculation that determines the number
+ // of nodes required at each level of the tree.
+ //
+ // The total node count is the sum of a geometric series that converges to
+ // N / (kMaxChildren - 1). Since N is the size of a vector, and each element
+ // is at least 24 bytes, the sum will never overflow SIZE_MAX.
+ //
+ // If this calculation is ever wrong, the CHECK_GT in AllocateNodeAtLevel
+ // will catch it before a reallocation invalidates node pointers.
+ size_t node_count = 0;
+ for (size_t n = num_data_elements_; n > 1;) {
+ n = (n + kMaxChildren - 1) / kMaxChildren;
+ node_count += n;
}
-
nodes_.reserve(node_count);
root_ = BuildRecursive(&branches, 0);
}
@@ -440,33 +426,6 @@
}
}
-// See comment in RTree<T>::Build. For triage: This is not a new bug. Previous
-// crashes may have been filed under DisplayItemList::Finalize(). This function
-// was written to collect these crashes with additional telemetry for
-// investigation. Please be sure that calling this function is causing a novel
-// crash before reverting/removing it.
-template <typename T>
-void RTree<T>::AddCrashKeysForTreeSizeAndCrash(size_t node_count) const {
- double branches_log = log(num_data_elements_);
- double depth = branches_log / log(kMaxChildren);
- double branch_pow = std::pow(kMaxChildren, depth);
- size_t node_count_recalculated =
- static_cast<size_t>((branch_pow - 1) / (kMaxChildren - 1)) + kMinChildren;
-
- SCOPED_CRASH_KEY_STRING32("Bug447555058", "initial_calcd_node_count",
- base::NumberToString(node_count));
- SCOPED_CRASH_KEY_STRING32("Bug447555058", "recalc_ln_data_elements",
- base::NumberToString(branches_log));
- SCOPED_CRASH_KEY_STRING32("Bug447555058", "recalculated_depth",
- base::NumberToString(depth));
- SCOPED_CRASH_KEY_STRING32("Bug447555058", "recalculated_branch_pow",
- base::NumberToString(branch_pow));
- SCOPED_CRASH_KEY_STRING32("Bug447555058", "recalculated_node_count",
- base::NumberToString(node_count_recalculated));
-
- NOTREACHED();
-}
-
} // namespace cc
#endif // CC_BASE_RTREE_H_
diff --git a/cc/base/rtree_unittest.cc b/cc/base/rtree_unittest.cc
index 430df49..5954083c3 100644
--- a/cc/base/rtree_unittest.cc
+++ b/cc/base/rtree_unittest.cc
@@ -5,9 +5,12 @@
#include "cc/base/rtree.h"
#include <stddef.h>
Regression Test / PoC
diff --git a/cc/base/rtree_unittest.cc b/cc/base/rtree_unittest.cc
index 430df49..5954083c3 100644
--- a/cc/base/rtree_unittest.cc
+++ b/cc/base/rtree_unittest.cc
@@ -5,9 +5,12 @@
#include "cc/base/rtree.h"
#include <stddef.h>
+
#include <utility>
+#include <vector>
#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/fuzztest/src/fuzztest/fuzztest.h"
namespace cc {
namespace {
@@ -284,4 +287,36 @@
EXPECT_EQ(all_bounds, expected_all_bounds);
}
+TEST(RTreeTest, LargeTreeDoesntCrash) {
+ // 11^6 + 1 = 1,771,562. This specific number was reported to cause a
+ // math error in the node_count calculation (crbug.com/447555058).
+ static constexpr size_t kLargeNodeCount = 1771562;
+ std::vector<gfx::Rect> rects;
+ rects.reserve(kLargeNodeCount);
+ for (size_t i = 0; i < kLargeNodeCount; ++i) {
+ rects.emplace_back(i, 0, 1, 1);
+ }
+ RTree<size_t> rtree;
+ // This should not trigger the CHECK_GT in AllocateNodeAtLevel because the
+ // capacity calculation is now correct.
+ rtree.Build(rects);
+}
+
+void BuildDoesNotCrash(const std::vector<gfx::Rect>& rects) {
+ RTree<size_t> rtree;
+ rtree.Build(rects);
+}
+
+auto ArbitraryRect() {
+ return fuzztest::Map(
+ [](int x, int y, int width, int height) {
+ return gfx::Rect(x, y, width, height);
+ },
+ fuzztest::Arbitrary<int>(), fuzztest::Arbitrary<int>(),
+ fuzztest::Arbitrary<int>(), fuzztest::Arbitrary<int>());
+}
+
+FUZZ_TEST(RTreeTest, BuildDoesNotCrash)
+ .WithDomains(fuzztest::VectorOf(ArbitraryRect()));
+
} // namespace cc
Original Bug Report
Browser-process Use-After-Free in cc::RTree via unbounded Paint Preview LinkData
Project Fortify, an experimental security project, has identified the following potential security issue.
Overview: A compromised renderer can send a malicious PaintPreviewCaptureResponse IPC with a specific number of link entries (e.g., 1,771,562). This triggers a subtle math error in cc::RTree::Build during Paint Preview playback, causing a std::vector reallocation that leaves RAW_PTR_EXCLUSION pointers dangling. When the user taps the preview, a Use-After-Free occurs in the browser process.
Affected files:
cc/base/rtree.hcomponents/paint_preview/browser/paint_preview_client.ccchrome/browser/paint_preview/services/paint_preview_tab_service.cc
Estimated timestamp from git blame: 2024-04-18
Summary
A potential Use-After-Free (UAF) vulnerability exists in the Chrome browser process when viewing large Paint Previews. A compromised renderer can provide a malicious PaintPreviewCaptureResponse with a specific number of LinkData entries that causes an underestimation of required memory in cc::RTree. This leads to a vector reallocation that invalidates raw pointers to tree nodes, subsequently resulting in a UAF when the tree is traversed during hit testing on Android.
Technical Analysis
1. Unbounded IPC Processing
During a Paint Preview capture, PaintPreviewClient::InProgressDocumentCaptureState::RecordSuccessfulFrame calls PaintPreviewCaptureResponseToPaintPreviewFrameProto to process LinkData from a renderer-provided response.
for (const auto& link : response->links) {
auto* link_proto = proto->add_links();
link_proto->set_url(link->url.spec());
RectToRectProto(link->rect, link_proto->mutable_rect());
}
There is no validation on the size of response->links against the expected max_capture_size. A compromised renderer can send an IPC message with exactly 1,771,562 link entries, which easily fits within Mojo/Protobuf limits (~70MB).
2. RTree Construction Underestimation
When the captured preview is loaded for viewing (e.g., during hit testing on Android), cc::RTree::Build is called. The function calculates a node_count to reserve in its nodes_ vector:
size_t branch_count = kMaxChildren;
double depth = log(branches.size()) / log(branch_count);
size_t node_count =
static_cast<size_t>((std::pow(branch_count, depth) - 1) /
(branch_count - 1)) +
kMinChildren;
// ...
nodes_.reserve(node_count);
This formula calculates the number of internal nodes in a perfectly balanced tree but underestimates the actual number of nodes required by the STR (Sort-Tile-Recursive) algorithm in BuildRecursive. For N = 1,771,562 (which is 11^6 + 1), the required node count is exactly 177,163. However, the formula calculates node_count as 177156 + 6 = 177,162.
3. Use-After-Free (UAF)
Because nodes_.reserve() was called with 177,162, allocating the 177,163rd node (the root node) via nodes_.emplace_back(level) forces the std::vector<Node<T>> nodes_ to reallocate its backing buffer to a larger capacity.
cc::RTree uses a Branch structure that stores a raw pointer to a child Node:
struct Branch {
// ...
// RAW_PTR_EXCLUSION: Performance reasons (based on analysis of speedometer3).
RAW_PTR_EXCLUSION Node<U>* subtree = nullptr;
// ...
};
These subtree pointers are explicitly excluded from MiraclePtr protection (RAW_PTR_EXCLUSION). During the std::vector reallocation, the nodes are moved to the new buffer, but the raw subtree pointers within those nodes are not updated. They are left pointing to the freed memory buffer.
When the user subsequently taps the Paint Preview on Android, PlayerCompositorDelegateAndroid::OnClick is invoked, which calls HitTester::HitTest, and finally rtree_.SearchRefs. This function traverses the dangling subtree pointers, leading to a Use-After-Free in the browser process.
Impact
A compromised renderer can trigger this UAF to achieve arbitrary code execution or memory leaking in the context of the browser process.
Potential Reproduction Steps
Note: These steps are suggested based on code analysis, as our setup cannot run exploit code.
- Compromise a renderer process (e.g., on Android).
- Wait for or induce tab backgrounding/loading states to trigger a Paint Preview capture.
- Respond to the
CapturePaintPreviewIPC with aPaintPreviewCaptureResponsecontaining exactly 1,771,562LinkDataentries. - Spray the browser process heap with forged
Node<GURL>structures using other available IPCs. - Wait for the user to open the Paint Preview and tap the screen.
HitTester::HitTestwill traverse the R-Tree, dereference the danglingsubtreepointers, and return a forgedGURLfrom the sprayed memory.- Java native code reads
GURL::spec(), leaking arbitrary memory or triggering further exploits.
Suggested Fix
Fix the math in cc::RTree::Build to correctly bound the maximum number of nodes. The worst-case node count for the BuildRecursive STR algorithm requires up to kMinChildren additional nodes per tree level, not just a flat kMinChildren addition at the end. Alternatively, use an index-based referencing system (like wtf_size_t indices) instead of raw Node<U>* subtree pointers to avoid pointer invalidation entirely.
Evaluated with Chrome root at commit: 0eb4855bda702feaaa8b899336664f97e3df88b8
Results so far have been promising, but there can be wrong deductions. If this proves to be a false positive, please close as WAI; data from false positives will be used to improve accuracy over time. Please feel free to reach out to me if you have concerns or feedback.