[5] RegExp bytecode compilation was racing between mutator and compiler threads

MediumJSC RegExp and YARRRace

dcf25ed

Severity가 Medium인 이유는 race window가 매우 좁기 때문입니다. commit 자체에서도 이 race를 재현하려면 인위적으로 thread sleep을 추가해야 했다고 밝히고 있습니다. 이 좁은 window 안에서 벌어지는 일은, 이미 interpreter에 넘겨졌을 수도 있는 owning pointer를 두 번째 thread가 새로 설치해버리는 상황입니다.

Lazy initialization에서 발생하는 data race는 가장 오래된 버그 패턴 중 하나입니다. 두 thread가 null field를 검사하고, 둘 다 객체를 생성한 뒤, 한쪽이 다른 쪽의 결과물을 파괴하는 형태입니다. JavaScriptCore는 JavaScript를 실행하는 단일 mutator thread와, 함께 동작하는 백그라운드 compiler thread들로 구성됩니다. Compiler thread는 heap object를 검사할 수 있는데, 여기에는 컴파일된 정규식을 소유하는 객체인 RegExp cell도 포함됩니다. 다만 이미 완성되어 있는 state를 읽는 것만 허용되며, cell 자체의 lock 없이는 이를 수정할 수 없습니다. RegExp는 YARR JIT machine code 또는 interpreted bytecode pattern 중 하나를 보유하며, compiler thread 진입점은 이미 존재하는 code만을 사용하도록 보장해야 합니다.

관전 포인트: JIT code는 있지만 bytecode는 없는 상태로 regexp를 준비한 뒤, compiler thread의 fold와 mutator의 match를 동시에 유발하는 스크립트를 작성하면, 한 thread가 다른 thread가 현재 interpret 중인 bytecode pattern을 파괴하게 만들 수 있습니다.

RegExp::matchConcurrently shouldn't cause any compilation, but bail out if JIT code for the regexp doesn't already exist. However, it is possible that a RegExp has JIT code but no bytecode, in which case matchConcurrently can incorrectly racily attempt to compile bytecode. This PR makes byteCodeCompileIfNecessary threadsafe by taking the cell lock. It also bails out of matchConcurrently if the regexp doesn't already have bytecode when called from the compiler thread. There is no new test because to manifest this race requires artificially adding sleeps to threads. Originally landed as 305413.415@rapid/safari-7624.2.5.110-branch.

Source/JavaScriptCore/runtime/RegExp.cpp

Source/JavaScriptCore/runtime/RegExpInlines.h

Patch Details

변경 사항은 두 곳입니다. RegExp.cpp에서는 RegExp::byteCodeCompileIfNecessary(VM*)의 첫 문장으로 Locker locker { cellLock() };가 추가되었습니다. 이는 if (m_regExpBytecode) return;이라는 early-out과, 이어지는 byteCodeCompilePattern() 호출보다 앞선 위치입니다. 이 호출은 m_regExpBytecode에 결과를 저장하고 m_state를 갱신합니다.

RegExpInlines.h에서는 RegExp::matchInline의 두 template overload — ovector를 채우는 int 버전과 match 여부만 확인하는 MatchResult 버전 — 모두에서 Yarr::JSRegExpResult::JITCodeFailure가 발생했을 때 interpreter로 넘어가는 punt 경로가 재구성되었습니다. 기존에는 byteCodeCompileIfNecessary(&vm); if (m_state == ParseError) return throwError();가 무조건 실행되었지만, 이제는 if constexpr (matchFrom == Yarr::MatchFrom::VMThread)로 감싸져 mutator만이 bytecode를 compile할 수 있도록 제한됩니다. 그 뒤에는 새로운 무조건 bail-out이 추가되었는데, ovector overload에서는 if (!m_regExpBytecode) return -1;, match-only overload에서는 return MatchResult::failed();입니다. 이를 통해 compiler thread가 punt 경로에 도달했지만 아직 bytecode가 완성되어 있지 않은 경우, compile을 시도하는 대신 실패를 보고하게 됩니다. 이 patch에는 별도의 test가 동반되지 않았습니다.

백그라운드 thread가 읽을 수도, 설치할 수도 있는 owning pointer의 lazy initialization이 동기화되지 않아, reader들이 전제하는 single-writer 계약이 깨지는 패턴입니다.

Background

JSC's threading model. JSC의 VM은 JavaScript를 실행하는 mutator thread 하나와, 함수를 동시에 최적화하는 백그라운드 compiler thread들로 구성됩니다. Compiler thread는 heap object를 검사할 수 있지만, 무엇을 건드릴 수 있는지를 제한하는 계약 아래서 동작합니다.

cellLock(). 모든 JSCell은 cell별로 lock을 가지며, compiler thread나 GC 같은 동시 reader에 대해 cell 내부 state의 변경을 직렬화하는 데 사용됩니다. WTF::Lock은 non-recursive입니다.

Yarr::MatchFrom. RegExp::matchInline에 template parameter로 전달되는 compile-time enum(VMThread / CompilerThread)으로, 하나의 함수 본문이 서로 다른 권한을 가진 두 개의 specialization으로 컴파일됩니다. RegExp::matchConcurrently는 compiler thread 진입점으로, matchInline<Yarr::MatchFrom::CompilerThread>에 위임합니다.

YARR execution tiers. RegExp는 Yarr::BytecodePattern(m_regExpBytecode, byteCodeCompilePattern이 생성하며 std::unique_ptr<Yarr::BytecodePattern>을 반환)을 통해 interpret되거나, YARR JIT machine code(m_regExpJITCode)로 실행됩니다. RegExp::m_state는 둘 중 어느 쪽인지(NotCompiled / JITCode / ByteCode / ParseError)를 기록합니다. hasCode()는 JITCode 또는 ByteCode 둘 중 하나면 true이며, hasCodeFor(charSize)는 이에 더해 YARR_JIT가 활성화된 경우 JITCode 상황에서 해당 char size에 대한 JIT code가 존재할 것을 추가로 요구합니다.

JSRegExpResult::JITCodeFailure. YARR JIT code가 실행 시점에 match를 완료하지 못했음을 나타내는 sentinel 값으로, 호출자에게 해당 호출에 대해 bytecode interpreter로 fallback하라는 신호를 줍니다.

Lazy initialization and unique_ptr assignment. JSC의 fooIfNecessary() 계열 메서드들은 캐시된 field를 검사하고, 최초 사용 시점에 이를 생성합니다. 이때 생성 결과를 저장하는 store는, 생성자가 이미 실행 완료된 heap object를 외부에 공개하는 동작입니다. std::unique_ptr에 새 값을 assign하면 기존에 소유하고 있던 객체는 파괴됩니다.

Analysis

패치 이전의 byteCodeCompileIfNecessary는 전형적인, lock 없는 double-checked initialization이었습니다. m_regExpBytecode를 검사하고, null이면 byteCodeCompilePattern()을 호출해 결과를 저장하고 m_state를 갱신하는데, 이 과정 전체가 cellLock() 없이 이뤄졌습니다. matchInline은 JITCodeFailure punt 경로에서 이 함수를 무조건 호출했고, matchInline은 MatchFrom::VMThread와 MatchFrom::CompilerThread 양쪽 모두로 인스턴스화됩니다.

  Mutator thread                    Compiler thread (concurrent fold)
  ──────────────                    ─────────────────────────────────
  matchInline<VMThread>             matchConcurrently: hasCodeFor() passes
   JIT run -> JITCodeFailure          (m_state == JITCode, bytecode null)
   byteCodeCompileIfNecessary        matchInline<CompilerThread>
    m_regExpBytecode == null          JIT run -> JITCodeFailure
    compile; assign  ────────┐        byteCodeCompileIfNecessary
   interpret(bytecode.get()) │         m_regExpBytecode == null (stale)
        still walking  ◄─────┴──────── compile; assign -> unique_ptr
                                        destroys the pattern in use

여기서 핵심 전제는, compiler thread가 애초에 어떻게 쓰기 경로에 도달할 수 있었는가입니다. commit 메시지에 따르면 matchConcurrently는 위임에 앞서 이미 code가 존재하는지 사전 검사한다고 설명합니다. 다만 제공된 RegExp.cpp/RegExpInlines.h 발췌본에는 이 함수 자체가 포함되어 있지 않으므로, 이 사전 검사 존재 여부는 commit 메시지를 그대로 인용한 것입니다. 반면 제공된 header 코드에서 확인할 수 있는 사실은, 그런 사전 검사만으로는 bytecode의 존재를 보장할 수 없다는 점입니다. YARR_JIT가 활성화된 상태에서 hasCodeFor()는 hasCode()(m_state == JITCode || m_state == ByteCode)를 요구하는데, JITCode 분기에서는 m_regExpJITCode가 요청된 char size에 대한 code를 가지고 있기만 하면 조건이 충족되며, 이때 m_regExpBytecode는 여전히 null일 수 있습니다. 즉 도달 가능한 케이스는 JIT code는 있지만 bytecode는 없는 RegExp이며, 이는 진입점의 precondition을 만족시키는 상태입니다. 그리고 JITCodeFailure punt는 런타임에 발견되는 tier downgrade로서, 사후적으로 그 precondition을 무효화합니다.

여기서 두 가지 서로 다른 memory-safety 결과가 이어집니다. 첫 번째는 lost-update로 인한 파괴입니다. 두 thread가 모두 m_regExpBytecode를 null로 관찰하고, 둘 다 byteCodeCompilePattern을 실행한 뒤, 각각 assign을 수행합니다. 이때 두 번째 unique_ptr assignment가 첫 번째 thread가 설치한 pattern을 파괴합니다. 만약 첫 번째 thread가 이미 m_regExpBytecode.get()을 Yarr::interpret에 넘긴 상태라면, 이 interpreter는 raw pointer를 한 번 로드해서 match가 끝날 때까지 이를 따라 순회하므로, 이미 해제된 BytecodePattern을 계속 참조하게 됩니다. 두 번째는 partial publication입니다. 패치 이전 store들에 release/acquire pairing이 없었다고 가정하면 — 제공된 source에서는 early-out 이후 본문이 잘려 있어 직접 확인되지는 않으며, fix의 형태로부터 추론한 것입니다 — 어떤 thread는 non-null m_regExpBytecode를 관찰하면서도 그 대상 객체의 생성이 아직 눈에 보이지 않는 상태를 마주할 수 있습니다. 그리고 lock 없이 이뤄지던 m_state write는 reader 측의 if (m_state == ParseError) 검사 및 tier 분기 결정과 race 관계에 놓이게 됩니다.

이 취약점은 web content로부터 도달 가능합니다. 스크립트가 pattern과 subject string을 선택하고, 어떤 함수가 충분히 hot해져서 DFG/FTL이 regexp 연산에 대한 constant-folding을 matchConcurrently를 통해 시도할지도 결정합니다. Trigger sequence를 구성한다면, 먼저 YARR가 JIT code로 컴파일하는 pattern으로 RegExp를 생성해 m_state == JITCode이면서 bytecode는 아직 null인 상태를 만듭니다. 이어서 literal subject에 대한 match를 hot 함수 안에 배치해 optimizer가 compile-time folding 대상으로 큐에 넣도록 유도합니다. 그다음 compiler thread에서의 JIT 실행이 JITCodeFailure를 반환하도록 조작하는데, JIT의 runtime budget을 소진시키는 pattern이 그 수단이 될 수 있습니다. 마지막으로 mutator에서 동일한 RegExp를 같은 punt 경로로 몰아넣어 두 thread가 null 검사를 두고 race하도록 만듭니다. 다만 구체적인 folding call site나 JITCodeFailure를 유발하는 정확한 조건은 제공된 context에 나타나 있지 않으므로, 둘 다 직접 확인된 사실이 아니라 유도된 내용입니다.

공격자가 race에서 승리했을 때 최선의 시나리오는, Yarr::interpret가 사용하는 BytecodePattern 그래프에 대한 use-after-free일 것입니다. 이 interpreter는 해제된 구조체에서 포인터를 역참조하고 벡터를 인덱싱하므로, 해제된 메모리가 성공적으로 재사용될 경우 제어된 relative read, 나아가 ovector에 대한 제어된 write로 이어질 가능성도 존재합니다. 이를 실현하려면 heap grooming이 필요합니다. 해제된 allocation은 term/disjunction vector와 character-class table을 담고 있어 그 크기를 공격자가 pattern의 복잡도로 조정할 수 있는데, 이 allocation이 interpreter가 역참조하기 전에 공격자가 제어하는 데이터로 재사용되도록 만들어야 합니다. 이보다 약하고 더 가능성이 높은 결과는 m_state/m_regExpBytecode가 뒤섞인 상태에서 발생하는 불안정한 crash입니다. commit 메시지에서는 이 race가 인위적으로 sleep을 추가해야만 재현된다고 밝히고 있으므로, 실제 환경에서 이 window를 넓히려면 같은 캐시된 RegExp에 대해 compiler thread의 fold와 mutator의 match를 다수 동시에 유발해야 할 것으로 보입니다.

이 취약점은 단일 mutator와 JSC의 concurrent compiler thread 사이의 thread-safety 계약을 깨뜨림으로써 WebContent process 내부의 memory safety를 약화시킵니다. 이번 fix는 오직 mutator만이 m_regExpBytecode에 write하며, check-and-install이 cellLock()으로 직렬화된다는 invariant를 복원합니다.

이번 fix는 눈에 띄게 이중으로 안전장치를 두고 있습니다. Lock을 추가하는 동시에, compiler thread를 writer 자리에서 아예 배제한 것입니다. commit 메시지의 계약 설명대로 matchConcurrently가 호출 전체 구간에서 이미 cellLock()을 잡고 있다고 가정하면, if constexpr gate는 단순한 중복이 아니라 load-bearing한 장치가 됩니다. WTF::Lock은 non-recursive이기 때문에, lock만 추가했다면 이 race는 compiler thread의 self-deadlock으로 바뀌었을 것이기 때문입니다. 다만 제공된 발췌본에는 해당 함수가 포함되어 있지 않으므로, 이 해석은 여기서 직접 검증되지는 않습니다. 또한 눈여겨볼 부분은, patch된 hunk 바로 아래 있는 ENABLE(YARR_JIT_DEBUG) 블록이 여전히 새 gate 없이 byteCodeCompileIfNecessary(&vm)를 호출한다는 점입니다. Debug build 전용 코드이긴 하지만, 이번 patch가 production에서 방금 제거한 것과 동일한 형태가 그대로 남아 있습니다.

Audit directions

• 읽기 전용 권한만 부여받은 백그라운드 thread가 lazy-materialization 경로에 도달하는 문제로, 진입점의 precondition이 실제로 필요한 조건보다 더 넓은 superset을 증명해버리기 때문에 발생합니다. Invariant: 백그라운드 thread를 허용하는 경계 검사는 내부 경로가 실제로 소비할 정확한 자원을 증명해야 하며, 단순히 그와 동등한 자원이 어딘가 존재한다는 것만으로는 부족합니다. 좁게 보면: RegExp의 다른 *IfNecessary 멤버들도 점검해야 합니다. compileIfNecessary와 compileIfNecessaryMatchOnly는 matchFrom과 무관하게 여전히 matchInline 상단 근처에서 호출되며, 이들의 compiler thread 안전성은 전적으로 진입점의 사전 검사에 의존하고 있습니다. 또한 ENABLE(YARR_JIT_DEBUG) 블록도 확인해야 하는데, 여기서는 여전히 gate 없이 byteCodeCompileIfNecessary를 호출합니다. Review 시 MatchFrom::CompilerThread / ConcurrentJSLocker 계열 진입점에서 transitively 도달 가능한 함수 안에 if (m_x) return; m_x = build(); 형태의 본문이 있다면 이것이 tell입니다. 넓게 보면: 같은 클래스의 문제는 백그라운드 compilation이 heap에 상주하는 derived state를 건드리는 곳이라면 어디서든 나타날 수 있습니다. JSString의 rope resolution, Structure의 property-table materialization, 캐시된 string/number 변환 등이 해당하므로, DFGAbstractInterpreterInlines.h와 DFGConstantFoldingPhase.cpp 안의 concurrent-folding call site들을 정리하고, 각 callee의 happy path뿐 아니라 모든 fallback 분기가 읽기 전용인지 확인해야 합니다. 가장 넓게 보면: 경계에서 수행된 capability check는 내부의 각 tier downgrade 지점에서도 다시 확립되어야 한다는 원칙은, V8의 background compile / LocalHeap 접근, SpiderMonkey의 offthread parsing, 그리고 대략적인 hasSomething() predicate 하나로 caller를 승인하는 모든 permission gate에 동일하게 적용됩니다. 코드베이스 간 공통 tell: permission check 이후에 등장하는 fast-path/slow-path 분기 중, slow path가 allocation을 수행하거나 state를 설치하는 경우입니다.

• 다른 thread가 소유 포인터를 통해 읽는 heap object의 non-atomic publication. Invariant는 다음과 같습니다. 두 번째 thread가 로드할 수 있는 포인터 필드는, 그 로드를 보호하는 것과 동일한 lock 하에서 설치되거나, release/acquire semantics를 갖는 atomic이어야 합니다. 좁게 보면, Source/JavaScriptCore/runtime과 Source/JavaScriptCore/yarr에서 std::unique_ptr 멤버를 검색해볼 필요가 있습니다. 특히 메서드 본문이 동일한 멤버에 대한 null 검사로 시작하는 곳에서 그 멤버가 할당되는 경우를 찾고, 해당 메서드가 cellLock()이나 ConcurrentJSLocker를 잡는지 확인해야 합니다. RegExp::m_rareData와 m_ovector는 같은 cell에 있는 인접 필드로, sanity-check 대상이 됩니다. 넓게 보면, 같은 클래스가 다른 지연 초기화 메커니즘에서도 나타날 수 있습니다. std::once_flag 없이 이루어지는 memoization, 지연 설치되는 Box/Ref 필드, enum discriminant가 payload pointer와 별도로 기록되어 두 값이 순서 없이 관찰될 수 있는 cached-derived-value 패턴 등이 그 예입니다. 리뷰 과정에서는 lock도 없고 WTF::storeStoreFence도 없이 포인터 하나, state flag 하나에 연달아 이루어지는 평범한 store 두 개가 시각적인 단서가 됩니다. 가장 넓게 보면, 이는 Java의 non-volatile double-checked locking이나 Rust에서 Arc + OnceLock이 필요한 코드와 형태가 동일한 고전적인 unsafe-publication 클래스에 해당합니다. Reader가 포인터를 볼 수 있다면, constructor가 기록한 모든 내용 또한 보일 수 있다는 보장이 있어야 합니다.

• 이미 lock을 보유하고 있을 수 있는 caller를 점검하지 않은 채 leaf function에 lock을 추가하는 패턴. WTF::Lock은 non-recursive이기 때문에, 이는 race에 대한 표준적인 fix 자체가 만들어내는 hazard에 해당합니다. Invariant는 다음과 같습니다. 각 lock에 대해, 그것을 획득하는 함수들의 집합은 call graph 상에서 antichain을 이루어야 합니다. 좁게 보면, RegExp::byteCodeCompileIfNecessary의 모든 caller를 추적해야 합니다. matchInline 오버로드 두 개와 ENABLE(YARR_JIT_DEBUG) 경로가 여기 해당하며, 이 중 어느 것도 이미 해당 cell의 cellLock()을 보유한 stack 위에 있지 않은지 확인해야 합니다. 먼저 제공된 발췌 코드에서 다루지 않는 caller인 RegExp::matchConcurrently를 읽는 것으로 시작하고, debug 경로는 코드를 읽는 것만으로 판단하지 말고 YARR_JIT_DEBUG build 하에서 직접 검증해야 합니다. 넓게 보면, 이전에는 lock이 없던 helper에 Locker locker { cellLock() }나 ConcurrentJSLocker를 추가하는 모든 commit이 같은 클래스에 속합니다. 각 신규 획득 지점을 그 caller들과 대조해서 점검해야 합니다. Race와 달리 deadlock은 리뷰만으로는 드러나지 않고, fix가 직렬화하려던 바로 그 interleaving 하에서만 나타나기 때문입니다. 리뷰 과정에서는 ALWAYS_INLINE으로 표시되어 있거나 더 큰 orchestration 함수들의 callee로 설계된 것이 명백한 함수에 Locker가 추가된 경우가 단서가 됩니다. 가장 넓게 보면, 이는 non-reentrant mutex를 사용하고 locking을 helper 쪽으로 밀어넣는 습관이 있는 모든 코드베이스에 적용됩니다. Chromium의 base::Lock, Rust의 Mutex가 그 예입니다. Lock 획득 위치를 옮기면 그 lock의 call-graph 상 위치가 바뀌게 되고, 그 결과 모든 상위 caller가 deadlock 후보가 됩니다.