[2] Distinguish named and numbered backreferences in Yarr

Severity: High | Component: JSC Yarr regex engine | 12ef604

조작된 regex를 통해 web content에서 heap에 할당된 backtrack stack에 대한 out-of-bounds 접근이 발생할 수 있어 High로 평가되었습니다. Commit message에 서술된 frame size mismatch 메커니즘과 diff에 드러난 gating fix를 바탕으로, attacker가 offset 크기를 제어할 수 있는 OOB read/write primitive가 가능하다고 confidence 0.82로 판단됩니다.

Duplicate named capture group 기능은 서로 다른 disjunct에 위치한다면 동일한 capture group 이름을 허용합니다. 그런데 backreference가 명시적인 번호 형태(예: \1)로 작성된 경우, engine이 이를 duplicate named group indirection table을 통해 잘못 resolve하는 문제가 있었습니다. 이 misresolution은 재귀적으로 발생할 수 있습니다. Commit message에서 설명하듯, 이 재귀는 backtracking 중 out-of-bounds로 이어집니다. 크기 N의 group을 match하고 크기 M의 disjunct를 match한 뒤, backtrack 시에는 크기 N을 되돌리려 하지만 실제로는 크기 M이 rewind되는 상황이 발생하기 때문입니다.

이 fix는 PatternTerm::Type enum을 분리하고, duplicate named group resolve 로직을 새로운 isNamed 파라미터로 gate하는 방식으로 named와 numbered backreference를 구분합니다.

Source/JavaScriptCore/yarr/YarrInterpreter.cpp

Source/JavaScriptCore/yarr/YarrPattern.h

JSTests/stress/regexp-duplicate-named-captures.js

Patch Details

이 fix는 PatternTerm::Type::BackReference와 ForwardReference를 네 가지 변형으로 분리합니다: NumberedBackReference, NamedBackReference, NumberedForwardReference, NamedForwardReference입니다. 핵심 변경 사항은 ByteCompiler::atomBackReference()와 YarrGenerator::generateBackReference()에 있습니다. 두 함수에서 m_duplicateNamedGroupForSubpatternId를 조회하는 duplicate named capture group resolve 로직이 새로운 isNamed 파라미터로 gate되었습니다. 동일한 구분은 YarrPatternConstructor에도 전파되었으며, convertToNumberedBackreference / convertToNamedBackreference 변환 함수를 통해 forward reference가 올바른 타입 변형으로 resolve됩니다.

Named와 numbered backreference를 구분하지 않으면 duplicate group indirection이 잘못 동작하여 backtrack frame accounting이 손상됩니다.

Background

ES2025부터는 서로 다른 alternative(disjunct)에 위치하는 경우 여러 capture group이 동일한 이름을 가질 수 있습니다. 예를 들어 /(?<k>a)|(?<k>b)/는 유효한 패턴으로, 매 순간 일치할 수 있는 k는 최대 하나입니다. Duplicate named group이 존재하면 Yarr는 특별한 duplicateNamedGroupId를 부여하고, subpattern ID를 duplicate group ID에 매핑하는 indirection table(m_duplicateNamedGroupForSubpatternId)을 구성합니다. Match 시, named backreference는 이 indirection을 통해 동일한 이름을 공유하는 모든 group을 확인합니다.

Named와 numbered backreference는 근본적으로 다른 semantics를 가집니다. \k<name>은 group 이름을 기준으로 resolve되며, 해당 이름을 공유하는 모든 group을 확인해야 합니다. 반면 \1은 capture group index를 기준으로 resolve되며, 항상 정확히 하나의 group을 참조합니다. 이 fix 이전에는 둘 다 동일한 PatternTerm::Type::BackReference로 컴파일되었고, named group은 해당 numeric index로 사전에 resolve되었습니다.

Yarr의 interpreter는 backtrack stack을 유지합니다. Disjunct 또는 group이 match될 때마다 match된 내용에 따라 크기가 결정된 frame이 push됩니다. Backtracking 중에는 실제로 취한 match 경로에 해당하는 크기의 frame을 pop합니다. 이 stack은 BumpPointerAllocator를 통해 heap에 할당됩니다.

Analysis

fix 이전에는 Yarr가 named와 numbered backreference를 동일한 BackReference term으로 컴파일했습니다. Duplicate named capture group을 포함한 패턴에서는 atomBackReference가 모든 backreference의 subpattern ID를 무조건 m_duplicateNamedGroupForSubpatternId table을 통해 resolve했습니다. /(?<l>x)|((?<l>(|)\1?.){2})x/ 패턴의 경우, 두 번째 disjunct 안의 numbered backreference \1은 첫 번째 capture group만을 참조해야 합니다. 그러나 fix 이전 코드는 이를 두 disjunct에 걸쳐 있는 duplicate named group l을 참조하는 것처럼 잘못 resolve했습니다.

Commit message는 이로 인한 결과를 다음과 같이 설명합니다. 이 misresolution은 재귀적으로 발생할 수 있으며, 그 재귀가 backtrack frame accounting을 손상시킵니다. Engine은 크기 N의 group을 match하고 크기 M의 disjunct를 match하지만, backtracking 시에는 크기 N을 rewind하려다 실제로는 크기 M이 rewind됩니다. 결과적으로 backtrack stack에 대한 out-of-bounds 접근이 발생합니다. 이 trigger 패턴은 duplicate named capture group grammar rule을 사용한 regex fuzzing을 통해 발견되었을 가능성이 높습니다. Duplicate named group과 numbered backreference를 중첩된 quantified group 안에 결합한 구조로, grammar 기반 fuzzer가 생성하는 특이한 조합에 해당합니다.

Audit directions