CVE-2026-19156
Overview
Background
- `SubstringSetMatcher`
- A
baseutility that builds an Aho-Corasick automaton from a set ofMatcherStringPatterns so that one pass over an input string reports every registered pattern it contains. - `AhoCorasickNode` edges
- Each trie node stores its outgoing edges (character transitions, plus special labels such as the failure link and
kMatchIDLabel) in a per-node buffer whose maximum capacity, per the commit message, is 260 edges. - `kMatchIDLabel` edge
- A pseudo-edge added by
SetMatchID()that marks a node as the end of a pattern and records that pattern’s ID;IsEndOfPattern()reports whether one already exists. - `DCHECK` vs. release builds
DCHECKs are compiled out of release builds, so an API contract that is enforced only by aDCHECK(here: “all pattern strings must be unique”) is not enforced in shipped Chrome.
Root Cause Analysis
Build() documents that all pattern strings must be unique, and AhoCorasickNode::SetMatchID() enforced the matching per-node invariant (“a node ends at most one pattern”) only with DCHECK(!IsEndOfPattern()). In release builds that check vanishes, so when a caller passes the same pattern string several times, each copy reaches the same terminal node and SetMatchID() calls SetEdge(kMatchIDLabel, id) again, appending an extra kMatchIDLabel edge each time. The edge-capacity budget (260, per the commit message) assumes at most one such edge per node, so a node that also has a full set of 256 character children plus a failure edge can be pushed past its allocated storage, and the next SetEdge() (e.g. for the failure edge) writes out of bounds on the heap.
The fix replaces the DCHECK with a release-mode early return when IsEndOfPattern() is already true, making SetMatchID() idempotent: only the first duplicate is registered and no extra edge is ever added, so the capacity assumption holds. The regression test (only built when !DCHECK_IS_ON()) confirms the intended behaviour: duplicate IDs 2–4 are ignored and only IDs 0 and 1 match.
kMatchIDLabel edge per node, which the fixed edge-capacity depends on) was guarded only by a DCHECK, so release builds silently accepted duplicate patterns and overflowed the node’s edge buffer. The fix turns the debug assertion into an unconditional early return that drops duplicates before SetEdge() is called.Attack Path
- Supply duplicate patterns
A caller of
SubstringSetMatcher::Build()passes a pattern list in which the same string appears more than once; the advisory and diff do not say which caller or input source supplies such a list. - Saturate one node
Per the regression test, the list also makes the duplicated pattern’s terminal node carry 256 distinct one-character children and gives it a non-root failure edge (via a shorter pattern like
"a"that is a suffix of it). - Extra match-ID edges
In a release build each duplicate reaches
SetMatchID()on the same node and appends anotherkMatchIDLabeledge, because theDCHECK(!IsEndOfPattern())is compiled out. - Heap overflow on a later edge
Once the node has more edges than its allocated capacity, a subsequent
SetEdge()(e.g. the failure edge) writes past the end of the node’s heap storage, which is the heap-buffer-overflow the advisory describes; turning that write into a controlled primitive is not shown by the patch (inferred).
Impact Assessment
DCHECK) builds; the patch does not show which SubstringSetMatcher caller is affected, so it is unknown whether the pattern set can be influenced by ordinary web content, or only by more privileged inputs such as extension-supplied URL filters or enterprise policy lists (inferred candidates, not shown in the diff). Triggering it requires the attacker to control the pattern set, not just the string being matched, including duplicate entries and about 256 sibling patterns under the same prefix. The advisory gives no in-the-wild exploitation status in the material provided; memory corruption leading to code execution in the host process (likely the browser process for most URL-matching users) is possible but not demonstrated (inferred).Changed Functions
| Function | Change | Notes |
|---|---|---|
TESTbase/substring_set_matcher/substring_set_matcher_unittest.cc |
modified | |
forbase/substring_set_matcher/substring_set_matcher_unittest.cc |
modified |
Files Changed
base/substring_set_matcher/substring_set_matcher_unittest.ccbase/substring_set_matcher/substring_set_matcher.h
Audit Directions
- `DCHECK`-only invariants that bound buffersSearch for
DCHECKs that protect a fixed-capacity array, inline storage or size calculation (for example “at most one X per node” or “IDs are unique”). In release builds these become unchecked assumptions, so they should beCHECKs or explicit early returns. - Fixed per-node capacity in tries/automataReview other trie, DFA or Aho-Corasick builders (e.g. URL matchers and filter-list compilers) whose node edge storage is sized for “alphabet + N special edges”. Confirm that every special-edge insertion is idempotent or explicitly counted.
- Uniqueness preconditions on caller-supplied listsAudit the callers of
SubstringSetMatcher::Build()and similarBuild(patterns)APIs that document “patterns must be unique” without de-duplicating. Check where those lists come from (extensions, policy, downloaded rule sets) and whether duplicates can reach the builder.
Patch
From 6ed29677f1d437e8acb732da6e86b19a3209294b Mon Sep 17 00:00:00 2001
From: Dominic Battré <battre@chromium.org>
Date: Tue, 14 Jul 2026 01:33:47 -0700
Subject: [PATCH] Fix heap-buffer-overflow in SubstringSetMatcher
SubstringSetMatcher::AhoCorasickNode::SetEdge could overflow its
allocated edge capacity when duplicate patterns are provided in release
builds. In release builds (without DCHECKs), duplicate patterns are not
rejected and can result in multiple kMatchIDLabel edges being added to
the same node. This can exceed the maximum capacity of 260 edges and
cause an out-of-bounds write when subsequent edges (like failure edges)
are added.
This CL makes SetMatchID idempotent. If a node is already marked as the
end of a pattern, we return early and do not add a duplicate
kMatchIDLabel edge.
This behavior is now documented in Build(), and a regression test has
been added to verify that duplicate patterns are handled safely by
ignoring subsequent duplicates in release builds.
Bug: 533331920
TAG=agy
CONV=95405c0a-c9e1-4622-aefd-20ac03e2cd86
Change-Id: I68933c463aa1a37e210002529c67116aece19523
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/8076938
Commit-Queue: Dominic Battré <battre@chromium.org>
Reviewed-by: Jan Keitel <jkeitel@google.com>
Cr-Commit-Position: refs/heads/main@{#1661676}
---
diff --git a/base/substring_set_matcher/substring_set_matcher.h b/base/substring_set_matcher/substring_set_matcher.h
index e59071a..003ceb5 100644
--- a/base/substring_set_matcher/substring_set_matcher.h
+++ b/base/substring_set_matcher/substring_set_matcher.h
@@ -31,8 +31,11 @@
~SubstringSetMatcher();
// Registers all |patterns|. Each pattern needs to have a unique ID and all
- // pattern strings must be unique. Build() should be called exactly once
- // (before it is called, the tree is empty).
+ // pattern strings must be unique. If duplicate pattern strings are passed,
+ // it will trigger a CHECK failure in DCHECK-enabled builds. In release
+ // builds, duplicate patterns are silently ignored (only the first one is
+ // registered) to prevent memory corruption. Build() should be called
+ // exactly once (before it is called, the tree is empty).
//
// Complexity:
// Let n = number of patterns.
@@ -202,7 +205,11 @@
void SetFailure(NodeID failure);
void SetMatchID(MatcherStringPattern::ID id) {
- DCHECK(!IsEndOfPattern());
+ // A node ends at most one pattern; a duplicate would add a second
+ // kMatchIDLabel edge that can overflow the node's storage in SetEdge().
+ if (IsEndOfPattern()) {
+ return;
+ }
DCHECK(id < kInvalidNodeID); // This is enforced by Build().
SetEdge(kMatchIDLabel, static_cast<NodeID>(id));
has_outputs_ = true;
diff --git a/base/substring_set_matcher/substring_set_matcher_unittest.cc b/base/substring_set_matcher/substring_set_matcher_unittest.cc
index a253fc80..bb51fa2 100644
--- a/base/substring_set_matcher/substring_set_matcher_unittest.cc
+++ b/base/substring_set_matcher/substring_set_matcher_unittest.cc
@@ -228,4 +228,47 @@
matcher.Build(patterns);
}
+// In DCHECK-enabled builds, duplicate patterns trigger a CHECK failure as they
+// violate the API contract. In release builds, duplicate patterns are silently
+// ignored (only the first one is registered) to prevent memory corruption.
+#if !DCHECK_IS_ON()
+TEST(SubstringSetMatcherTest, DuplicatePatterns) {
+ std::vector<MatcherStringPattern> patterns;
+ MatcherStringPattern::ID id = 0;
+
+ // "a" is a pattern so node "ba" gets a non-root failure edge.
+ patterns.emplace_back("a", id++); // ID 0
+
+ // Four identical "ba" patterns.
+ patterns.emplace_back("ba", id++); // ID 1
+ patterns.emplace_back("ba", id++); // ID 2
+ patterns.emplace_back("ba", id++); // ID 3
+ patterns.emplace_back("ba", id++); // ID 4
+
+ // 256 character children on node "ba" to fill capacity.
+ for (int i = 0; i < 256; ++i) {
+ std::string str;
+ str.push_back('b');
+ str.push_back('a');
+ str.push_back(static_cast<char>(i));
+ patterns.emplace_back(str, id++);
+ }
+
+ SubstringSetMatcher matcher;
+ ASSERT_TRUE(matcher.Build(patterns));
+
+ std::set<MatcherStringPattern::ID> matches;
+ matcher.Match("ba", &matches);
+
+ // We expect to match "a" (ID 0) and the first "ba" pattern (ID 1).
+ // Duplicate "ba" patterns (IDs 2-4) should be ignored.
+ EXPECT_EQ(2u, matches.size());
+ EXPECT_TRUE(matches.find(0) != matches.end());
+ EXPECT_TRUE(matches.find(1) != matches.end());
+ EXPECT_TRUE(matches.find(2) == matches.end());
+ EXPECT_TRUE(matches.find(3) == matches.end());
+ EXPECT_TRUE(matches.find(4) == matches.end());
+}
+#endif // !DCHECK_IS_ON()
+
} // namespace base
Regression Test / PoC
diff --git a/base/substring_set_matcher/substring_set_matcher_unittest.cc b/base/substring_set_matcher/substring_set_matcher_unittest.cc
index a253fc80..bb51fa2 100644
--- a/base/substring_set_matcher/substring_set_matcher_unittest.cc
+++ b/base/substring_set_matcher/substring_set_matcher_unittest.cc
@@ -228,4 +228,47 @@
matcher.Build(patterns);
}
+// In DCHECK-enabled builds, duplicate patterns trigger a CHECK failure as they
+// violate the API contract. In release builds, duplicate patterns are silently
+// ignored (only the first one is registered) to prevent memory corruption.
+#if !DCHECK_IS_ON()
+TEST(SubstringSetMatcherTest, DuplicatePatterns) {
+ std::vector<MatcherStringPattern> patterns;
+ MatcherStringPattern::ID id = 0;
+
+ // "a" is a pattern so node "ba" gets a non-root failure edge.
+ patterns.emplace_back("a", id++); // ID 0
+
+ // Four identical "ba" patterns.
+ patterns.emplace_back("ba", id++); // ID 1
+ patterns.emplace_back("ba", id++); // ID 2
+ patterns.emplace_back("ba", id++); // ID 3
+ patterns.emplace_back("ba", id++); // ID 4
+
+ // 256 character children on node "ba" to fill capacity.
+ for (int i = 0; i < 256; ++i) {
+ std::string str;
+ str.push_back('b');
+ str.push_back('a');
+ str.push_back(static_cast<char>(i));
+ patterns.emplace_back(str, id++);
+ }
+
+ SubstringSetMatcher matcher;
+ ASSERT_TRUE(matcher.Build(patterns));
+
+ std::set<MatcherStringPattern::ID> matches;
+ matcher.Match("ba", &matches);
+
+ // We expect to match "a" (ID 0) and the first "ba" pattern (ID 1).
+ // Duplicate "ba" patterns (IDs 2-4) should be ignored.
+ EXPECT_EQ(2u, matches.size());
+ EXPECT_TRUE(matches.find(0) != matches.end());
+ EXPECT_TRUE(matches.find(1) != matches.end());
+ EXPECT_TRUE(matches.find(2) == matches.end());
+ EXPECT_TRUE(matches.find(3) == matches.end());
+ EXPECT_TRUE(matches.find(4) == matches.end());
+}
+#endif // !DCHECK_IS_ON()
+
} // namespace base
Original Bug Report
Security: heap-buffer-overflow in base::SubstringSetMatcher::AhoCorasickNode::SetEdge (OOB write on duplicate patterns)
VULNERABILITY DETAILS
Heap-buffer-overflow (4-byte out-of-bounds write) in base::SubstringSetMatcher during tree construction (Build()), reported by GWP-ASan: WRITE of size 4, 0 bytes to the right of a 1040-byte region.
Root cause: SubstringSetMatcher::Build() requires unique pattern strings, but its uniqueness CHECK is compiled only in DCHECK-enabled builds and is absent from release builds. Duplicate strings terminate at the same Aho-Corasick node, causing repeated calls to SetMatchID() and redundant kMatchIDLabel edges. Each node’s edge array is capped at 260 four-byte entries (1040 bytes). In the repro, 256 character edges plus one valid and three duplicate match-id edges fill the array. When Build() subsequently adds the failure edge, SetFailure() calls SetEdge() to write the 261st edge, four bytes past the allocation.
The debug-only uniqueness check is compiled out of release builds, so nothing prevents the corruption there. GWP-ASan caught it via a guard page; without the guard page (the common, unsampled case) it is a silent 4-byte corruption of the adjacent heap allocation. The write value is a packed AhoCorasickEdge (9-bit label + 23-bit node index), and both the location and the node-index value are influenced by the input pattern set.
Reachability: SubstringSetMatcher is a shared //base primitive. It is fed attacker-influenceable input through the extension declarativeNetRequest regex path (RegexRulesMatcher/RegexSetMatcher) – FilteredRE2 emits candidate “atom” substrings that are passed to SubstringSetMatcher::Build() – and is also used by components/url_matcher.
VERSION
Chrome Version: 152.0.4141.0; the vulnerable code is long-standing, so all current stable/beta/dev channels are affected. Operating System: Observed on Windows via GWP-ASan. The affected code is platform-independent C++ in //base, so it is not OS-specific.
REPRODUCTION CASE
This is not a web-page bug; it triggers in the browser process during matcher construction.
Minimal deterministic repro (unit test): register the following patterns and call SubstringSetMatcher::Build():
- “a” (one pattern) - so node “ba” gets a stored non-root failure edge,
- “ba” four times (distinct IDs) — the duplicate strings that add extra match-id edges,
- “ba” + <byte> for all 256 byte values — fills node “ba” to its 256 character-edge maximum.
Node “ba” reaches 256 + 4 = 260 edges (the cap); the failure edge added next is the overflowing 261st write. Must be built without DCHECKs (e.g. ASan with dcheck_always_on=false), because Build()’s debug-only uniqueness check otherwise aborts before the release path is reached.
Ready-to-run test (drop into base/substring_set_matcher/substring_set_matcher_unittest.cc):
// Regression test for a heap-buffer-overflow in AhoCorasickNode::SetEdge().
// Duplicate pattern strings give one node multiple kMatchIDLabel edges. Node
// "ba" reaches 256 char edges + 4 duplicate match IDs = 260 (the storage cap),
// so the failure edge added next is the overflowing 261st SetEdge() call.
// Built only without DCHECKs: the duplicate strings trip Build()'s DCHECK-only
// uniqueness check before this release-only overflow path is reached.
#if !DCHECK_IS_ON()
TEST(SubstringSetMatcherTest, DuplicatePatternEdgeOverflow) {
std::vector<MatcherStringPattern> patterns;
MatcherStringPattern::ID id = 0;
// "a" is a pattern so node "ba" gets a non-root failure edge.
patterns.emplace_back("a", id++);
// Four identical "ba" patterns -> four match-ID edges (three illegal dups).
patterns.emplace_back("ba", id++);
patterns.emplace_back("ba", id++);
patterns.emplace_back("ba", id++);
patterns.emplace_back("ba", id++);
// 256 character children on node "ba".
for (int i = 0; i < 256; ++i) {
std::string str;
str.push_back('b');
str.push_back('a');
str.push_back(static_cast<char>(i));
patterns.emplace_back(str, id++);
}
SubstringSetMatcher matcher;
matcher.Build(patterns);
}
#endif // !DCHECK_IS_ON()
POTENTIAL FIX
Make SetMatchID() idempotent. A node can end at most one pattern, so repeated calls for a duplicate string should keep the first match ID and add no further edge.
File: base/substring_set_matcher/substring_set_matcher.h
void SetMatchID(MatcherStringPattern::ID id) {
// A node ends at most one pattern; a duplicate would add a second
// kMatchIDLabel edge that can overflow the node's storage in SetEdge().
if (IsEndOfPattern()) {
return;
}
DCHECK(id < kInvalidNodeID); // This is enforced by Build().
SetEdge(kMatchIDLabel, static_cast<NodeID>(id));
has_outputs_ = true;
}
This preserves behavior for valid unique inputs while preventing redundant match-ID edges from exhausting the node’s edge storage in release builds.
FOR CRASHES, PLEASE INCLUDE THE FOLLOWING ADDITIONAL INFORMATION
Type of crash: browser process Crash State:
#0 base::SubstringSetMatcher::AhoCorasickNode::SetEdge
base/substring_set_matcher/substring_set_matcher.cc:479
#1 base::SubstringSetMatcher::AhoCorasickNode::SetFailure
base/substring_set_matcher/substring_set_matcher.cc:490
#2 base::SubstringSetMatcher::CreateFailureAndOutputEdges
base/substring_set_matcher/substring_set_matcher.cc:318
#3 base::SubstringSetMatcher::BuildAhoCorasickTree
base/substring_set_matcher/substring_set_matcher.cc:224
#4 base::SubstringSetMatcher::Build
base/substring_set_matcher/substring_set_matcher.cc:90
#5 base::SubstringSetMatcher::Build
base/substring_set_matcher/substring_set_matcher.cc:51
#6 extensions::declarative_net_request::RegexRulesMatcher::MatchHelper::InitializeMatcher
extensions/browser/api/declarative_net_request/regex_rules_matcher.cc:331
#7 extensions::declarative_net_request::RegexRulesMatcher::MatchHelper::MatchHelper
extensions/browser/api/declarative_net_request/regex_rules_matcher.cc:194
#8 extensions::declarative_net_request::RegexRulesMatcher::RegexRulesMatcher
extensions/browser/api/declarative_net_request/regex_rules_matcher.cc:110
#9 extensions::declarative_net_request::RulesetMatcher::RulesetMatcher
extensions/browser/api/declarative_net_request/ruleset_matcher.cc:257
#10 std::__Cr::make_unique
third_party/libc++/src/include/__memory/unique_ptr.h:756
#11 extensions::declarative_net_request::RulesetSource::CreateVerifiedMatcher
extensions/browser/api/declarative_net_request/ruleset_source.cc:142
#12 extensions::declarative_net_request::FileBackedRulesetSource::CreateVerifiedMatcher
extensions/browser/api/declarative_net_request/file_backed_ruleset_source.cc:465
#13 extensions::declarative_net_request::RulesetInfo::CreateVerifiedMatcher
extensions/browser/api/declarative_net_request/file_sequence_helper.cc:386
#14 extensions::declarative_net_request::FileSequenceHelper::UpdateDynamicRules
extensions/browser/api/declarative_net_request/file_sequence_helper.cc:489
FileSequenceHelper::UpdateDynamicRules was dispatched asynchronously through base::OnceCallback on a base::ThreadPool worker. Generic callback and worker-thread frames are omitted
CREDIT INFORMATION
Externally reported security bugs may appear in Chrome release notes. If this bug is included, how would you like to be credited? Reporter credit: Viktoria Zlatinova