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의 AdaptiveStringSearcher는 Boyer-Moore(-Horspool) substring search를 구현하며, JSString의 indexOf, lastIndexOf, replace 연산에서 search pattern이 알고리즘을 쓸 만큼 충분히 긴 경우 내부적으로 사용됩니다. Boyer-Moore의 good-suffix heuristic은 pattern 내 위치로 인덱싱되는 shift table을 미리 계산합니다. 기존에는 이 table들이 raw int*로, 그것도 "biased pointer" 형태로 전달되었습니다. Base pointer를 search 시작 인덱스만큼 뒤로 offset시켜서, pattern index가 수동 pointer 연산을 통해 table slot으로 매핑되는 방식이었고, 이 연산은 아무런 bounds check도 거치지 않았습니다.

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 { };
 
+// [start, patternLength] 범위의 pattern index를 shift table에 매핑한다. 이 table은 pattern의
+// 마지막 bmMaxShift + 1개 위치만 커버한다. Biased pointer와 달리 양쪽 끝 모두 물리적인 table을
+// 기준으로 bounds-check되며, 이 check는 컴파일 타임 상수 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 }; }

m_goodSuffixShiftTable은 extent 250(bmMaxShift)으로 선언되어 있었습니다. 하지만 good-suffix 계산은 pattern 내 위치를 patternLength 이하까지 포함해서 인덱싱합니다. 결과적으로 정확히 250자인 needle은 250개 원소짜리 배열에서 인덱스 [250], 즉 배열 끝을 int 하나만큼 초과하는 위치에 쓰기를 수행하게 됩니다. 패치는 두 table 모두 공유 상수 shiftTableSize를 통해 bmMaxShift + 1로 재정의하고, raw int* / biased-pointer accessor를 고정 extent std::span 기반의 BiasedShiftTable wrapper로 교체합니다. Wrapper는 여전히 patternIndex - m_start bias를 적용하지만, 내부 std::span이 컴파일 타임 상수 extent를 기준으로 양쪽 끝을 bounds-check하기 때문에, 동일한 off-by-one이 발생해도 이제는 OOB write 대신 trap이 발생합니다.

  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

Allocation 크기를 결정하는 상수(bmMaxShift)와 인덱싱을 결정하는 상수(inclusive한 patternLength)가 1만큼 어긋나 있었습니다. 게다가 biased-pointer accessor는 아무 것도 table의 실제 크기와 대조해 연산을 검증하지 않았기 때문에, 이 어긋남이 그대로 가려져 있었습니다. 공격자가 선택한 250자 pattern은 일반적인 indexOf/lastIndexOf/replace 호출을 통해 JS에서 도달 가능한 heap OOB int write로 이어집니다. 인접한 int 하나를 덮어쓰는 것 자체는 제한적인 primitive이지만, 그 위치는 attacker가 pattern 길이와 search string 배치를 통해 조정할 수 있는 heap offset입니다. 이는 정확히 더 강력한 primitive로 grooming될 수 있는 형태에 해당합니다.

Audit directions

고정 table에서 크기 상수와 인덱스 상수가 어긋나는 패턴. 하나의 상수로 크기가 정해지고 다른 상수로 인덱싱되는 구조는, 특히 인덱스 상한이 inclusive로 명시된 경우 off-by-one의 후보입니다. WTF 전반에서 std::array<... , bmMaxShift>와 이와 유사한 Boyer-Moore state를 검색한 뒤, table의 extent 상수가 loop bound에 쓰인 상수와 다른 경우로 범위를 넓혀 점검할 필요가 있습니다. Code review 시, [patternLength](또는 다른 inclusive upper bound)로 인덱싱되는 배열이 다른 named constant로 크기가 지정되어 있다면, 두 상수가 실제로 일치하는지 증명하는 한 줄짜리 comment가 필요합니다.
수동 biased-pointer table access. 이번 패치가 대체한 base - m_start idiom 자체가 진짜 위험 지점입니다. Base를 allocation 바깥으로 이동시켜 in-range index가 다시 allocation 안쪽으로 들어오도록 만들기 때문에, 단순한 bounds 추론으로는 문제를 놓치게 됩니다. populateBoyerMooreTable / populateBoyerMooreHorspoolTable과 Horspool variant를 대상으로 bmMaxShift 경계 근처에 남아 있는 write가 없는지 점검하고, WTF의 나머지 string/search/hash table들 중 std::span으로 이관되지 않은 raw-pointer bias trick이 남아 있는지도 확인할 필요가 있습니다. 식별 포인트는, length 정보 없이 something - offset만 반환하는 pointer accessor입니다. 이런 형태는 bounds-checked span으로 전환해야 할 대상입니다.