[5] YARR RegularExpression out-of-bounds write with duplicate named capture groups

MediumJSC YARROOB

e536815

Medium으로 평가한 이유는, wrapper가 byte-code interpreter에게 넘긴 buffer가 interpreter 자신이 기록한 요구 크기보다 짧아서, pattern이 선택한 index에 대한 write가 buffer 끝을 넘어가기 때문입니다. High band에 들지 않는 이유는, attacker가 영향을 미칠 수 있는 pattern string이 이 façade로 들어가는 in-tree caller가 확인되지 않고, container의 over-allocation이 작은 규모의 overrun을 흡수하기 때문입니다.

JSC의 정규식 매칭은 결과를 "offsets vector"라는 형태로 만들어냅니다. 이는 unsigned 값들의 flat array로, 각 capture group이 두 개의 연속된 slot(start offset, end offset)을 차지하며 slot 0과 1은 전체 match를 위해 예약되어 있습니다. 이 엔진을 사용하는 독립적인 소비자는 두 곳입니다. JavaScript에 노출되는 RegExp 객체를 지원하는 JSC::RegExp와, JavaScriptCore 외부 caller를 위해 export된 더 단순한 wrapper인 JSC::Yarr::RegularExpression입니다. 두 소비자 모두 byte-code의 자체 기록된 요구 크기 이상 길이의 vector를 byte-code interpreter에게 넘겨야 합니다. Interpreter가 compile 시점에 박혀 있는 id로 이 vector를 직접 indexing하기 때문입니다.

관전 포인트: duplicate named capture group을 가진 pattern이 byte-code interpreter로 하여금 wrapper가 할당한 buffer 끝을 넘어선 index에 write하도록 유도합니다. match()의 stack frame에, 또는 pattern이 클 경우 인접한 heap memory에 write가 발생합니다.

RegularExpression의 offsets vector 할당 크기가 잘못되어 있습니다. named captures가 추가될 때 해당 공식이 갱신되었지만, RegularExpression의 계산은 올바르게 갱신되지 않았습니다. 이 patch는 이를 수정합니다.

Source/JavaScriptCore/yarr/RegularExpression.cpp

Tools/TestWebKitAPI/Tests/JavaScriptCore/RegularExpression.cpp

Patch Details

프로덕션 코드 변경은 한 줄입니다. JSC::Yarr::RegularExpression::match()에서, Yarr::interpret()에 output vector로 넘기는 Vector<unsigned, 32> nonReturnedOvector의 크기를 정하는 local 변수 offsetVectorSize는 이전에는 wrapper 자체의 공식인 (d->m_numSubpatterns + 1) * 2로 계산되었습니다. 이 patch는 이를 byte-code compiler 자신이 기록한 크기, 즉 d->m_regExpByteCode->m_offsetsSize로 교체합니다.

match()의 나머지 부분은 변경되지 않습니다. nonReturnedOvector.grow(offsetVectorSize) 호출, offsetNoMatch 초기화 loop(여전히 m_numSubpatterns + 1로 범위가 제한됨), 그리고 interpret() 호출은 그대로입니다. 나머지 hunk들은 부수적인 변경입니다. Flags::UnicodeSets 아래에서 duplicate named capture group을 가진 pattern에 대해 RegularExpression 객체를 생성하는 네 개의 TEST(JavaScriptCore_RegularExpression, DuplicateNamedCaptureGroup*) 케이스를 담은 새로운 API test 파일과, Tools/TestWebKitAPI/CMakeLists.txt의 한 줄짜리 등록이 그것입니다. 이 테스트들이 trigger의 근거입니다. 모두 (?<a>x)|(?<a>y) 형태의 pattern, 즉 같은 group 이름이 여러 alternative에서 재사용되는 형태를 사용합니다.

producer가 기록해 둔 크기를 읽지 않고, consumer가 자신만의 공식으로 buffer 요구 크기를 다시 계산하는 패턴.

Background

Offsets vector. YARR의 match 출력은 unsigned 값들의 flat array입니다. 각 capture group마다 interpreter가 start offset과 end offset을 연속된 두 slot에 저장하며, slot 0/1은 전체 match를 위해 예약되어 있습니다. offsetNoMatch는 참여하지 않은 group의 slot에 기록되는 sentinel 값입니다. YarrPattern::m_numSubpatterns가 capturing group의 개수를 세므로, 전형적인 ovector 길이는 (numSubpatterns + 1) * 2입니다.

Duplicate named capture groups. 같은 group 이름이 pattern 안에서 서로 배타적인 alternative에 속하는 한 여러 번 등장할 수 있도록 허용하는 언어 기능입니다. 예를 들면 (?<a>x)|(?<a>y) 같은 형태입니다. YARR은 이를 이름별 id로 추적하고, BytecodePattern::offsetForDuplicateNamedGroupId(id)를 통해 해당 slot에 접근합니다. 이 slot들은 기존의 start/end 쌍 뒤에 위치합니다. BytecodePattern::m_offsetsSize는 interpreter가 필요로 하는 unsigned slot의 개수를 byte-code 객체가 기록해 둔 값입니다.

하나의 엔진, 두 개의 소비자. JSC::RegExp(runtime/RegExp.cpp)는 offsetVectorBaseForNamedCaptures()와 m_rareData->m_numDuplicateNamedCaptureGroups를 더해 m_ovector의 크기를 정합니다. JSC::Yarr::RegularExpression(yarr/RegularExpression.cpp)은 독립적이고 더 단순한 wrapper입니다. YarrPattern → byteCompile() → interpret()로 이어지는 얇은 façade이며, JS_EXPORT_PRIVATE로 선언되어 JavaScriptCore 외부에서도 호출 가능합니다. 이 wrapper는 match() 호출마다 자체적인 scratch vector를 할당합니다.

Vector<T, N>의 inline capacity와 growth 정책. WTF의 Vector 템플릿에서 두 번째 파라미터는 inline capacity입니다. N개까지의 element는 Vector 객체 자체에 내장된 buffer에 저장되며, N을 넘어서는 요청만이 heap 할당을 유발합니다. grow()는 expandCapacity()를 거치는데, 이 함수는 max(requested, max(16, capacity() + capacity() / 4 + 1))만큼 예약하므로, heap 성장 이후의 예약 capacity는 요청한 크기보다 일반적으로 더 큽니다. WTF의 VectorTraits는 simple/POD element type을 needsInitialization = false로 표시하므로, Vector<unsigned>를 growth시키면 내용이 특정되지 않은(zero가 아닌) element가 노출됩니다. nonReturnedOvector는 match()의 stack local로서 Vector<unsigned, 32>로 선언되어 있습니다.

interpret(). YARR byte-code interpreter의 진입점입니다. BytecodePattern, subject string, start offset, 그리고 raw unsigned* output vector를 받아, byte code에 박혀 있는 id로 이 vector를 직접 indexing합니다.

Analysis

Root cause는 중복된 크기 공식 중 한쪽만 갱신된 것입니다. Duplicate named capture group 지원이 추가되었을 때, offsets vector는 offsetForDuplicateNamedGroupId(id)로 접근하는 추가 trailing 영역만큼 늘어났습니다. Producer는 이 실제 총 크기를 m_offsetsSize에 기록하고, RegExp::finishCreation()은 이 값을 올바르게 사용합니다. 반면 wrapper가 손으로 작성한 (m_numSubpatterns + 1) * 2 공식은 손대지 않은 채 남아 있었습니다.

  Byte code expects (m_offsetsSize):
  [ whole ][ sub1 ][ sub2 ] ... [ dupA ][ dupB ]
  |<------ (numSubpatterns+1)*2 ------>|<--- unallocated --->|
                                        ^
                          offsetForDuplicateNamedGroupId(id)
                          writes here, past what grow() asked for

Interpreter는 이 slot들을 index로 직접 건드립니다. ParenthesesDisjunctionContext의 constructor는 subpatternAndGroupIdBackup[...] = output[m_pattern->offsetForDuplicateNamedGroupId(duplicateNamedGroupId)](read)를 수행한 뒤 output[pattern->offsetForDuplicateNamedGroupId(duplicateNamedGroupId)] = 0(write)을 수행하고, restoreOutput()이 저장된 값을 다시 write합니다. 낡은 공식 하에서는 이런 index 하나하나가 (m_numSubpatterns + 1) * 2 지점 또는 그 이후에 위치하게 됩니다.

실제로 어떤 메모리가 손상되는지는 grow()에 넘긴 크기가 아니라 vector의 예약된 capacity가 결정하며, 이 둘은 서로 다른 방향으로 어긋납니다. 낡은 크기 값이 32 이하로 유지되는 동안에는 storage가 embedded inline buffer이고 그 capacity는 정확히 32입니다. 이때 touched index가 32 이상이면 — 대략 열다섯 개의 subpattern에 몇 개의 duplicate named group이 더해진 정도면 — embedded buffer를 넘어 match()를 감싸는 stack frame에 write가 발생합니다. 반면 낡은 크기 값이 32를 넘어서면 grow()가 expandCapacity()를 거치게 되고, 32 element짜리 inline buffer에서 벗어나는 성장은 최소 41개의 element를 예약합니다. 32를 살짝 넘는 낡은 크기 값에서 몇 slot 정도 overrun이 발생하는 정도라면, 여전히 vector 자신의 heap 할당 안, 즉 초기화되지 않은 여유 공간 안에 머무르게 됩니다. 인접한 heap memory에 도달하려면 touched index의 최댓값이 실제 예약된 capacity를 넘어서야 하는데, 큰 pattern의 경우 이 capacity는 대략 낡은 크기 값의 1.25배 수준을 따라갑니다. 결과적으로 조용히 넘어가는 구간은 heap path에서는 단순한 추정보다 넓고, inline path에서는 보이는 것보다 좁습니다.

Fix 이후에도 눈여겨볼 만한 잔여 문제가 하나 있습니다. Buffer는 이제 m_offsetsSize 길이가 되었지만, 명시적인 offsetNoMatch seeding loop는 여전히 m_numSubpatterns + 1에서 멈추기 때문에, trailing duplicate-group slot들은 wrapper에 의해 seeding되지 않은 채 남습니다. WTF의 VectorTraits는 simple/POD type을 초기화가 필요 없다고 표시하므로 grow()가 이 slot들을 zero로 채우지 않습니다. 이 부분의 정확성은 결국 interpreter가 read 이전에 해당 slot을 초기화한다는 전제에 의존하는데, 적어도 ParenthesesDisjunctionContext 경로에서는 그렇게 동작하는 것으로 보이지만, interpret()의 모든 경로에서 이 조건이 성립하는지는 확인되지 않습니다.

발견 경로는 fuzzing보다는 pattern auditing이나 variant analysis에 가까운 것으로 보입니다. Fix 자체가 낡은 공식 한 줄이고, 추가된 테스트들은 모두 Flags::UnicodeSets 아래 duplicate named capture group을 사용하는 손으로 작성한 API test라는 점이, 기능이 merge된 이후 누군가가 offsets-vector layout의 소비자들을 의도적으로 하나씩 점검한 흔적에 해당합니다. Fuzzing이 이 버그를 찾기 어려운 이유는, 새로 추가된 테스트를 포함한 가장 작은 pattern들조차 touched index를 inline buffer 안쪽에 머물게 하고, heap growth 정책이 요청 크기보다 넉넉히 over-allocation하기 때문입니다. 결국 pattern이 touched index를 예약 capacity 너머로 밀어내기 전까지는 sanitizer 리포트가 나타나지 않습니다.

이 vulnerability는 RegularExpression façade를 통해 정규식을 compile하는 프로세스 내부의 memory safety를 약화시킵니다. Fix 이전에 깨져 있던 invariant는 byteCompile()과 interpret() 사이의 계약입니다. Output vector는 최소한 m_offsetsSize개의 unsigned를 담아야 하는데, wrapper는 pattern에 duplicate named capture group이 포함될 때마다 이보다 더 적은 크기를 조용히 넘겼습니다. Pattern string을 이 API에 흘려넣을 수 있는 attacker라면, touched index가 vector의 예약 capacity를 넘어설 때마다 pattern이 선택한 index에 대한 out-of-bounds write를 얻을 수 있습니다. Storage가 여전히 embedded 32-element inline buffer인 경우라면 match()의 stack frame에, touched index가 over-allocated된 예약 heap capacity를 넘어서는 경우라면 인접한 heap memory에 write가 발생하는 형태입니다. 두 경우 모두 직접 사용되기보다는 grooming이나 stack-layout 지식과 결합되는, 제한적인 memory corruption 발판에 해당할 것으로 보입니다. Attacker가 영향을 미치는 pattern string을 이 façade에 넘기는 in-tree caller는 여기서 확인되지 않으며, 이 점이 JS-visible RegExp 경로에 있는 동등한 버그보다 실질적인 severity를 낮게 유지시키는 요인입니다.

Takeaway: Vector<T, N>의 "작은 overflow"를 triage할 때는 요청한 길이가 아니라 container의 예약 capacity를 계산해야 합니다. Inline capacity 이하에서는 경계가 정확히 N이며 overrun이 감싸는 stack frame으로 그대로 새어 나가지만, 그 이상에서는 expandCapacity()의 over-allocation이 소규모 overrun을 조용히 흡수해 ASan으로부터 숨겨버립니다.

Audit directions

• Producer가 이미 authoritative한 크기를 기록해 두었는데, consumer가 자신만의 공식으로 할당 크기를 다시 계산하는 패턴. 여기서 지켜야 할 invariant는 layout을 결정하는 쪽이 크기를 소유하고, consumer는 그 값을 읽을 뿐 다시 계산해서는 안 된다는 것입니다. 좁게 보면: JavaScriptCore 전역에서 ovector 산술 리터럴(+ 1) * 2), offsetVectorBaseForNamedCaptures, 그리고 BytecodePattern::m_offsetsSize의 모든 reader를 검색해야 합니다. RegExpInlines.h, RegExp::matchInline/matchConcurrently, RegExpMatchesArray, 그리고 YarrJIT의 진입점들을 확인할 필요가 있습니다. 이들 모두 caller가 할당한 unsigned*를, baked-in id로 indexing하는 matcher에 넘기기 때문입니다. 넓게 보면: 어떤 객체에 크기가 공개되어 있음에도 caller가 자기 나름의 크기를 계산하는 모든 위치가 대상입니다. ByteDisjunction::m_frameSize와 DisjunctionContext::allocationSize()의 관계, 또는 count 필드로부터 계산되지 않고 구조체를 채우는 쪽에서 직접 읽어야 할 WebKit의 모든 할당이 그 예입니다. 가장 넓게 보면: compiler나 serializer가 데이터와 required-buffer-size 필드를 동시에 emit하는 모든 코드베이스가 대상입니다. LLVM의 stack frame size와 prologue emitter의 관계, protobuf/flatbuffer의 arena sizing, Chromium command buffer에서의 GPU descriptor-table sizing 등이 해당됩니다. 코드 리뷰에서의 tell은 어느 rung에서든 동일합니다. Allocation argument가 count에 대한 산술 표현식으로 되어 있고, 넘겨질 대상 객체가 그 산술식이 재현하려는 ...Size member를 이미 노출하고 있다면 의심해야 합니다.

• 기존 layout을 확장하는 언어 또는 format 기능이 도입되었는데, layout-size consumer 중 일부만 갱신된 패턴. 여기서 지켜야 할 invariant는 struct의 tail을 확장하는 것은 local한 변경이 아니라 프로그램 전체에 걸친 변경이라는 것입니다. 좁게 보면: duplicate-named-capture-group 지원 도입으로 새로 생기거나 수정된 모든 consumer를 나열해야 합니다. offsetForDuplicateNamedGroupId, m_numDuplicateNamedCaptureGroups, m_namedGroupToParenIndices 등이 그 대상이며, yarr/YarrJIT.cpp, yarr/YarrInterpreter.cpp, runtime/RegExp*.cpp 전반에서 이 index들을 사용하는 할당이 numSubpatterns가 아닌 m_offsetsSize로부터 도출되는지 확인해야 합니다. 넓게 보면: 기존의 count 기반 array에 trailing 영역이 덧붙여진 다른 최근 JSC layout 확장에 대해서도 같은 점검을 반복할 필요가 있습니다. Modifier와 v-flag 추가, match-result rare data 등이 해당됩니다. 가장 넓게 보면: "tail이 확장된 structure에 legacy 크기 공식이 남아 있는" 일반적인 클래스 전체가 대상입니다. 버전이 있는 kernel/syscall struct, Vulkan의 pNext 형태의 extension chain, v1 length 계산 뒤에 v2 필드가 덧붙여지는 모든 wire format이 여기에 속합니다. Tell: 같은 buffer에 대해 트리 안에 두 개의 크기 표현식이 존재하고, 그중 하나만 새 기능의 count를 언급하고 있는 경우입니다.

이 코드가 있는 위치가 아니라 audit direction 번역이므로, 별도 스킬 없이 바로 번역 규칙에 따라 처리하겠습니다.

• 엔진 setup 과정을 공유하지 않고 재구현한 뒤, 시간이 지나며 어긋나는 단순화된 façade. 여기서 지켜야 할 invariant는 두 entry point가 동일한 callee contract를 만족해야 한다면, contract를 만족시키는 코드는 한 곳에만 존재해야 한다는 것입니다. Narrow 범위에서는 RegularExpression::match()와 RegExp::finishCreation/matchInline을 줄 단위로 diff해 볼 필요가 있습니다. 이번에 수정된 sizing 버그 외에도, match()의 offsetNoMatch 초기화 루프가 여전히 m_numSubpatterns + 1을 기준으로 동작하는 반면 버퍼는 이제 m_offsetsSize 길이라는 점에 주목해야 합니다. 게다가 WTF의 VectorTraits는 grow() 시 POD 원소를 초기화하지 않은 채로 남겨두므로, interpret()을 읽어 모든 경로가 duplicate-group slot을 읽기 전에 반드시 기록하는지 확인해야 합니다. Wider 범위에서는 embedder가 직접 호출하는 다른 thin JSC/WTF 레벨 wrapper들 — Yarr::checkSyntax 경로, WTF 레벨 문자열 및 URL matching helper — 을 같은 관점에서 점검할 필요가 있습니다. 즉 주 호출자가 이후 추가 setup 단계를 갖게 된 엔진에 대해, 더 단순한 두 번째 호출자가 존재하는 형태를 찾는 것입니다. Widest 범위는 "lite façade drift"로 일반화되며, syscall 위의 libc wrapper, protocol layer 위의 고수준 SDK client, driver 위의 ORM query builder 등에도 동일하게 적용됩니다. 판별 기준은 동일한 저수준 함수를 호출하는 두 지점 중 한쪽이 다른 쪽보다 명백히 더 많은 setup을 수행하며, 그 추가 setup이 더 단순한 호출 지점이 작성된 이후에 추가되었다는 패턴입니다.

• 큰 inline capacity를 가진 Vector<T, N>을 사용하는 코드에서 out-of-bounds write가 얼마나 숨어 있는지 점검할 필요가 있습니다. 이때 기준으로 삼아야 할 값은 요청된 길이가 아니라 컨테이너의 실제 예약 capacity입니다. inline capacity 이하 구간에서는 경계가 정확히 N이며, heap으로 growth가 일어난 이후에는 expandCapacity()가 max(requested, max(16, capacity() + capacity() / 4 + 1))를 예약합니다. 따라서 요청된 크기를 살짝 벗어나는 정도의 overrun은 vector 자체의 여유 공간 안에 묻히게 됩니다. Narrow 범위에서는 JavaScriptCore와 WTF 전반에서 inline capacity가 16 이상인 Vector< 선언을 검색하고, 이후 계산된 크기로 grow()된 뒤 mutableSpan().data()나 data()를 통해 raw pointer로 넘겨지는 사례를 찾아야 합니다. 각 사례마다 callee가 사용하는 최대 index가 두 regime(inline / heap) 중 어느 쪽에서든 예약 capacity를 초과할 수 있는지 확인해야 하며, 특히 inline regime은 write가 감싸고 있는 stack frame으로 새어 나갈 수 있는 지점입니다. Wider 범위에서는, raw pointer로 넘겨진 뒤 callee가 별도로 index를 계산해 접근하는 small-buffer-optimised 컨테이너 전반 (SmallVector 계열 타입, 별도 길이 변수를 가진 고정 크기 stack array 등)과, over-allocate 방식으로 작은 overrun을 ASan으로부터 가려버리는 growth policy 전반에서 동일한 사각지대가 존재합니다. 판별 기준은 예약 capacity와 논리적 크기가 서로 달라질 수 있는 컨테이너에서 raw pointer가 빠져나가고, callee가 별도로 도출한 값으로 index 접근을 수행하는 패턴입니다. 이 클래스의 문제를 정적으로 검증하는 작업은 간단하지 않으며, corruption을 재현하려면 대체로 기존 테스트를 실행하는 것만으로는 부족하고 ASan 하에서 해당 index를 예약 capacity 너머로 직접 밀어붙여야 합니다.

• YARR interpreter에서 duplicate-named-group index에 대한 output[...] 읽기 중, 도달 가능한 모든 경로에서 write가 선행되지 않는 지점을 검색할 필요가 있습니다. 이는 이번 fix가 버퍼는 확장하면서도 wrapper의 offsetNoMatch seeding 루프는 여전히 m_numSubpatterns + 1까지만 동작하도록 남겨두었고, WTF는 grow() 시 POD 원소를 초기화하지 않은 채로 두기 때문입니다. yarr/YarrInterpreter.cpp의 ParenthesesDisjunctionContext 생성자와 restoreOutput()부터 시작해 term-dispatch 코드 쪽으로 범위를 넓혀가며 점검해야 합니다. Wider 범위에서는, "caller가 버퍼를 부분적으로만 초기화했는데 callee는 완전히 초기화되어 있다고 가정하는" 동일한 형태가 JSC 내 out-parameter 배열 전반에서 나타날 수 있습니다. 특히 seeding 루프의 bound와 allocation 길이가 서로 다른 expression으로 작성된 경우가 이에 해당합니다. 판별 기준은 같은 함수 안에서 allocation 길이와 초기화 루프의 bound가 서로 다른 두 expression으로 작성되어 있는 패턴입니다.