[YARR] Add auto-possession optimization

2a8223d

Source/JavaScriptCore/yarr/YarrPattern.cpp

+    void optimizePossessiveQuantifiers()
+    {
+        auto followerForcesPossessive = [&](const PatternTerm& greedy, const PatternTerm& next) -> bool {
+            if (next.type != PatternTerm::Type::PatternCharacter)
+                return false;
+            if (next.quantityType != QuantifierType::FixedCount || next.quantityMinCount < 1)
+                return false;
+            char32_t fc = next.patternCharacter;
+            if (termMatchesCharacter(greedy, fc) != TriState::False)
+                return false;
+            if (next.ignoreCase()) {
+                if (!isASCII(fc))
+                    return false;
+                if (termMatchesCharacter(greedy, toASCIIUpper(fc)) != TriState::False)
+                    return false;
+                if (termMatchesCharacter(greedy, toASCIILower(fc)) != TriState::False)
+                    return false;
+            }
+            return true;
+        };

Source/JavaScriptCore/yarr/YarrJIT.cpp

+        if (term->possessive()) {
+            loadFromFrame(term->frameLocation + BackTrackInfoPatternCharacter::matchAmountIndex(), countRegister);
+            if (m_decodeSurrogatePairs && !U_IS_BMP(term->patternCharacter))
+                m_jit.lshift32(MacroAssembler::TrustedImm32(1), countRegister);
+            m_jit.sub32(countRegister, m_regs.index);
+            m_backtrackingState.fallthrough();
+            return;
+        }

YARR (Yet Another Regex Runtime)는 WebKit의 regex 엔진입니다. 패턴을 parser에 통과시켜 YarrPattern IR(PatternTerm 노드로 구성)로 변환한 뒤, interpreter로 처리하거나 YarrJIT을 통해 native code로 컴파일합니다. Possessive quantifier는 최대한 매칭한 뒤, 이미 소모한 문자를 다음 term에 반환하지 않습니다. Greedy quantifier가 backtrack 시 문자를 반환하는 것과 대조됩니다. Auto-possessification은 greedy quantifier를 possessive로 취급해도 된다는 사실을 정적으로 증명하는 분석입니다. Greedy term이 매칭 가능한 문자 집합과 뒤따르는 필수 term이 요구하는 문자 집합이 완전히 disjoint하다면, 모든 backtrack 반복은 어차피 실패합니다. 따라서 give-back loop 자체를 생략할 수 있습니다.

이번 commit은 optimizePossessiveQuantifiers 분석 패스와 대응하는 JIT code path를 추가했습니다. 분석 패스는 컴파일된 PatternTerm을 순회하며, 뒤따르는 필수 term의 문자 집합이 disjoint함이 증명 가능한 경우 greedy 단일 문자 term을 possessive로 표시합니다. 뒤따르는 term에 /i 플래그가 적용된 경우에는 case folding도 함께 고려합니다. 이후 YarrJIT은 해당 term에 대해 backtrack loop를 건너뛰는 코드를 생성하여, /a+b/나 /[0-9a-f]{1,4}:/ 같은 패턴에서 불필요한 give-back 반복을 제거합니다.

Significance

Disjointness 분석의 정확성은 구현 전체를 떠받치는 핵심입니다. 두 문자 집합이 단 하나의 code point만 공유하더라도 disjoint하다고 잘못 판단하는 false positive가 발생하면, JIT은 backtracking을 조용히 건너뛰고 잘못된 non-match를 반환합니다. 이는 regex 기반 security validator를 무력화하는 버그 유형에 정확히 해당합니다.

분석은 Unicode case folding, non-BMP surrogate pair, inverted/variable-width character class를 정확하게 처리해야 합니다. 모두 미묘한 부분이며 세심하게 살펴볼 필요가 있습니다.

Audit directions

optimizePossessiveQuantifiers의 disjointness 분석. 추가된 테스트 파일은 여러 위험한 케이스를 지목합니다. 먼저 /i 모드에서 ASCII follower가 greedy class 내 문자로 case-fold되는 경우입니다. 예를 들어 /i 하의 [a-z]+X에서 X는 x와 매칭됩니다. 한편 /iu 모드에서는 Unicode case folding이 단순하지 않은 케이스도 있습니다. Kelvin 기호 U+212A는 k로 fold되므로, /iu 하의 [\u212A]+k는 literal code point가 disjoint해 보이더라도 possessify해서는 안 됩니다.
Non-BMP surrogate pair. JIT은 code point당 두 개의 code unit을 고려한 give-back 단계를 생성해야 합니다. give-back 경로의 stride 계산이 잘못되면 exploitable한 correctness 버그로 이어집니다.
BMP/non-BMP가 혼재된 inverted character class 및 variable-width class. 분석에서 사용하는 Unicode case-fold 테이블에 누락된 항목이 있으면, 해당 항목은 false-positive disjointness 판단의 후보가 됩니다.