AdaptiveStringSearcher good-suffix shift table off-by-one

An ordinary indexOf call writes one int past a heap search table.

Component: WTF Text | 5590f2e

WTF's AdaptiveStringSearcher implements Boyer-Moore(-Horspool) substring search, used internally by JSString operations like indexOf, lastIndexOf, and replace whenever the search pattern is long enough to make the algorithm worthwhile. Boyer-Moore's good-suffix heuristic precomputes a shift table indexed by position within the pattern. Historically these tables were passed around as raw int* with a "biased pointer" — the base pointer offset backward by the search start index — so that a pattern index maps onto a table slot through manual pointer arithmetic that nothing bounds-checks.

Source/WTF/wtf/text/AdaptiveStringSearcher.h

- std::array<int, AdaptiveStringSearcherBase::bmMaxShift> m_goodSuffixShiftTable { };
- std::array<int, AdaptiveStringSearcherBase::bmMaxShift + 1> m_suffixTable { };
+ static constexpr size_t shiftTableSize = AdaptiveStringSearcherBase::bmMaxShift + 1;
+ std::array<int, shiftTableSize> m_goodSuffixShiftTable { };
+ std::array<int, shiftTableSize> m_suffixTable { };
 
+// Maps pattern indices in [start, patternLength] onto a shift table that only covers the last
+// bmMaxShift + 1 positions of the pattern. Unlike a biased pointer, both ends are bounds-checked
+// against the physical table, and the check is against a compile-time constant extent.
+class BiasedShiftTable {
+public:
+    using Table = std::span<int, AdaptiveStringSearcherTables::shiftTableSize>;
+    BiasedShiftTable(Table table, int start) : m_table(table), m_start(start) { }
+    int& operator[](int patternIndex) const { return m_table[static_cast<size_t>(patternIndex - m_start)]; }
+private:
+    Table m_table;
+    int m_start;
+};
 
-    int* goodSuffixShiftTable()
-    {
-        return m_tables.goodSuffixShiftTable() - m_start;
-    }
+    BiasedShiftTable goodSuffixShiftTable() { return { m_tables.goodSuffixShiftTable(), m_start }; }

The m_goodSuffixShiftTable was declared with extent bmMaxShift (250) but the good-suffix computation indexes it by position within the pattern up to patternLength inclusive. A needle of exactly 250 characters therefore drives a write to index [250] in a 250-element array — one int past the end. The fix redefines both tables to bmMaxShift + 1 via a shared shiftTableSize constant, and swaps the raw int* / biased-pointer accessor for a BiasedShiftTable wrapper backed by a fixed-extent std::span. The wrapper still applies the patternIndex - m_start bias, but the underlying std::span bounds-checks both ends against a compile-time constant extent, so the same off-by-one now traps instead of writing OOB.

  Before:                                  After:
  m_goodSuffixShiftTable[250]              m_goodSuffixShiftTable[251]
  index range: [start .. 250]              index range: [start .. 250]
                          │                                       │
       write to [250] ────┴──► past end          write to [250] ──┴──► in bounds
       (one int OOB)                             (250 <= 250, valid)

Significance

The two sizing constants driving allocation (bmMaxShift) versus indexing (an inclusive patternLength) diverged by one, and the biased-pointer accessor hid the divergence because nothing checked the arithmetic against the table's real size. A 250-character attacker-chosen pattern yields a JS-reachable heap out-of-bounds int write through ordinary indexOf/lastIndexOf/replace calls. A single adjacent-int overwrite is a constrained primitive, but it lands at a heap offset the attacker influences via pattern length and search string placement — exactly the shape that gets groomed into something more.

Audit directions

Divergent size-vs-index constants on fixed tables. Any structure sized by one constant and indexed by another — especially where the index bound is stated inclusively — is a candidate off-by-one. Grep WTF for std::array<... , bmMaxShift> and sibling Boyer-Moore state; then widen to any table whose extent constant differs from the constant used in its loop bound. In code review, a [patternLength] (or any inclusive upper bound) indexing an array sized by a different named constant deserves a one-line comment proving the two agree.
Manual biased-pointer table access. The base - m_start idiom that this patch replaced is the real hazard: it moves the base outside the allocation so that in-range indices land back inside, which defeats naive bounds reasoning. Audit populateBoyerMooreTable / populateBoyerMooreHorspoolTable and the Horspool variant for any remaining writes near bmMaxShift boundaries, and hunt the rest of WTF's string/search/hash tables for surviving raw-pointer bias tricks that were not migrated to std::span. The match tell: a pointer accessor that returns something - offset with no length carried alongside is exactly the pattern to convert to a bounds-checked span.