From 66f992d2d47fd30779ec386af2ea73f93bcb24c8 Mon Sep 17 00:00:00 2001
From: Dominic Battré <battre@chromium.org>
Date: Mon, 27 Jul 2026 12:19:59 -0700
Subject: [PATCH] [M144] Fix heap-buffer-overflow in SubstringSetMatcher

Original change's description:
> 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}

(cherry picked from commit 6ed29677f1d437e8acb732da6e86b19a3209294b)

Bug: 539345880,533331920
Change-Id: I68933c463aa1a37e210002529c67116aece19523
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/8157159
Auto-Submit: chrome-cherry-picker@chops-service-accounts.iam.gserviceaccount.com <chrome-cherry-picker@chops-service-accounts.iam.gserviceaccount.com>
Bot-Commit: rubber-stamper@appspot.gserviceaccount.com <rubber-stamper@appspot.gserviceaccount.com>
Commit-Queue: rubber-stamper@appspot.gserviceaccount.com <rubber-stamper@appspot.gserviceaccount.com>
Reviewed-by: Dominic Battré <battre@chromium.org>
Cr-Commit-Position: refs/branch-heads/7559@{#5157}
Cr-Branched-From: 223dfbac1c7542a06b422390d954afe5b560b607-refs/heads/main@{#1552494}
---

diff --git a/base/substring_set_matcher/substring_set_matcher.h b/base/substring_set_matcher/substring_set_matcher.h
index cd7d488e1..356e2f1 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

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