[4] Invalid RegExp memoized and folded into NewRegExp

MediumJSC RegExp runtimeOOB

d5531cc

Medium으로 평가되었습니다. 두 개의 결함이 한 지점에서 만납니다. 먼저 생성이 중단된 constructor가 offset vector를 전혀 갖지 않은 객체를 weak cache에 남깁니다. 그리고 strength reduction은 그 객체가 유효한지 묻지 않은 채 최적화된 코드에 그대로 심습니다. 다만 out-of-bounds store까지 도달하려면 stack depth에 좌우되는 parse 실패가 먼저 맞아떨어져야 합니다.

JavaScript의 정규식은 수명 동안 두 번 처리됩니다. 한 번은 pattern을 parse하는 시점이고, 다른 한 번은 engine이 matcher를 생성하기로 결정하는 시점입니다. 그 사이에는 caching이 끼어듭니다. JSC에서는 이 작업이 두 축으로 나뉘어 있습니다. 하나는 RegExp 객체로, capture 개수와 offset vector를 소유합니다. 모든 match는 start/end 쌍을 이 offset vector에 기록합니다. 다른 하나는 pattern parser이자 matcher generator인 Yarr입니다. 한편 DFG의 strength reduction pass는 operand가 compile time에 알려진 node를 더 싼 형태로 다시 쓰는 정리 단계입니다. 이 pass는 new RegExp(...)를 compile time에 freeze된 RegExp를 감싸는 직접 allocation으로 바꿀 수 있습니다. 이때 cache에서 도달 가능한 객체라면 유효하고 완전히 생성된 객체라는 전제가 깔려 있습니다.

관전 포인트: stack depth 때문에 parse가 중단된 pattern이 절반만 생성된 상태로 memoize될 수 있습니다. 이후 다시 compile되면, 객체가 한 번도 allocate하지 않은 span으로 capture offset을 기록하는 matcher가 생성될 가능성이 있습니다.

Patch Details

변경은 세 가지입니다. 먼저 DFGStrengthReductionPhase::handleNode가 RegExp를 freezeStrong하고 타입이 지정되지 않은 new RegExp node를 NewRegExp로 다시 쓰기 전에 regExp->isValid()를 확인하도록 수정되었습니다. 생성에 실패한 객체가 상수로 최적화된 코드에 박히는 일은 이제 발생하지 않습니다. 다음으로 RegExpCache::lookupOrCreate는 !regExp->isValid()인 경우 weakAdd(m_weakCache, key, Weak<RegExp>(regExp, this)) 이전에 새로 생성한 RegExp를 곧바로 반환합니다. 실패한 pattern은 더 이상 memoize되지 않으므로, 같은 key로 다시 조회해도 절반만 초기화된 객체를 받지 않게 되었습니다. 한편 compile, compileMatchOnly, byteCodeCompileIfNecessary는 새로 re-parse한 Yarr::YarrPattern에서 capture metadata를 함께 가져오도록 변경되었습니다. 이전에는 m_atom과 m_specificPattern만 옮기고, capture 개수는 ASSERT(m_numSubpatterns == pattern.m_numSubpatterns)로만 확인했습니다. release build에서는 이 ASSERT가 제거되므로 debug build에서만 유효한 확인이었습니다.

생성에 실패한 객체가 memoize된 뒤 최적화된 코드에 접혀 들어가고, 그 metadata는 compile된 matcher와 더 이상 일치하지 않는 pattern을 기술한 채 남습니다.

  matcher (freshly re-parsed pattern)      RegExp object (stale)
  ----------------------------------      ---------------------
  writes 2 * (P + 1) offsets  ─────────►  ovectorSpan()  size 0
  P = pattern.m_numSubpatterns            m_numSubpatterns = 0
                                                  |
  createRegExpMatchesArray*  ◄────────────────────┘
  reads numSubpatterns() = 0 pairs

Background

생성 과정과 cache. RegExp::finishCreation은 pattern을 한 번 parse합니다. 실패하면 if (!isValid()) early return을 타면서 m_state = ParseError로 설정합니다. 문제는 객체의 metadata를 채우는 코드가 전부 이 return 뒤에 놓여 있다는 점입니다. m_ovector = FixedVector<int>(offsetVectorSize)도 여기에 포함됩니다. 그럼에도 RegExpCache::lookupOrCreate는 결과 객체를 (flags, pattern) key로 m_weakCache에 그대로 넣습니다.

offset vector. 모든 match는 RegExp마다 존재하는 offset vector에 start/end 쌍을 기록하고, createRegExpMatchesArray*는 regExp->numSubpatterns()를 이용해 이를 다시 읽습니다. capture가 하나도 없는 정상적인 pattern이라도 offsetVectorBaseForNamedCaptures() = (0 + 1) * 2 = 2개의 entry는 할당됩니다. 반면 중단 경로에서는 하나도 할당되지 않습니다. 정상적으로 생성된 어떤 RegExp보다도 반드시 작은 크기입니다.

Yarr의 hard error와 soft error. Yarr::ErrorCode는 영구적인 syntax 실패에 해당하는 hard error와 그렇지 않은 soft error를 구분합니다. TooManyDisjunctions는 YarrErrorCode.h에 "we ran out stack compiling"으로 기술되어 있으며, 명시적으로 hard error가 아닙니다. 즉 어떤 pattern이 parse되는지 여부는 pattern 자체가 아니라 parse 시점에 남아 있는 stack 양에 달려 있습니다.

soft 실패 이후의 재시도. RegExp::matchInline의 throwError lambda는 !hasHardError(m_constructionErrorCode)인 경우 reset()을 호출합니다. 이때 m_state는 NotCompiled로 되돌아가고 error code도 지워집니다. 그 결과 같은 객체가 이후 match에서 compile을 다시 시도하게 됩니다.

Strength reduction. 이 pass는 concurrent compiler thread에서 동작하며, operand가 compile time에 알려진 node를 다시 씁니다. new RegExp를 NewRegExp node로 바꾸는 것도 여기에 포함되는데, 이 node는 freeze된 상수를 감싸는 RegExpObject를 allocate하기만 합니다.

Analysis

지켜지지 않은 invariant는 두 가지입니다. 첫째, 생성에 실패한 객체는 memoize되어서도, 상수로 최적화된 코드에 박혀서도 안 됩니다. new RegExp(...)의 interpreter 경로는 잘못된 pattern에 대해 SyntaxError를 발생시킵니다. 반면 folding된 NewRegExp node는 freeze된 상수를 감싸 allocate할 뿐입니다. 결과적으로 baseline tier가 예외를 던지는 자리에서 JIT tier는 객체를 반환했습니다. 둘째, capture metadata는 Yarr가 실제로 compile한 pattern을 따라가야 합니다.

이 둘을 연결하는 것이 soft error 재시도입니다. TooManyDisjunctions는 pattern 텍스트가 아니라 stack depth에 좌우되므로, 같은 객체가 한 번은 parse에 실패하고 나중에는 성공할 수 있습니다. 패치 이전에는 이 재시도가 전체 capture 집합에 대한 matcher를 생성할 수 있었습니다. 그동안 객체의 m_numSubpatterns는 0에 머물러 있고, m_ovector는 중단된 finishCreation이 끝내 allocate하지 않은 빈 vector로 남습니다.

그러면 match의 양쪽이 서로 다른 개수를 기준으로 동작하게 됩니다. 위 다이어그램이 나타내는 상황입니다. 생성된 matcher는 ovectorSpan()이 반환하는 span으로 2 * (P + 1)개의 offset을 기록합니다. 여기서 P는 새로 re-parse한 Yarr::YarrPattern의 capture 개수입니다. 다만 이 상태에서 해당 span은 비어 있습니다. 반대로 createRegExpMatchesArray*는 낡은 값인 0, 즉 regExp->numSubpatterns()만큼의 쌍을 읽습니다. matchInline에 있는 ASSERT(ovector.size() >= static_cast<size_t>(offsetVectorSize()))는 이 호출 지점들에서 아무 의미가 없습니다. offsetVectorSize()가 m_ovector.size()를 그대로 반환하는데, 넘겨지는 ovector 역시 m_ovector 그 자체이기 때문입니다.

finishCreation이 m_ovector = FixedVector<int>(offsetVectorSize)가 실행되기 전에 반환되기 때문에, 이 store들이 기록될 backing allocation 자체가 존재하지 않습니다. 현실적으로 예상되는 결과는 near-null store에서 fault가 발생하는 것입니다. 즉 attacker가 유발할 수 있는 renderer crash에 해당합니다. 방향을 조종할 수 있는 write까지 가려면, offset이 m_ovector가 아니라 offsetVectorSize() 기준으로 크기가 정해진 caller 소유의 Vector<int>를 거치는 match 경로가 필요합니다. 이는 예상되는 경로일 뿐, 지금 이 상태에서 관찰되는 동작은 아닙니다.

이 vulnerability는 두 개의 경계를 동시에 약화시킵니다. 하나는 tier 간 일관성입니다. interpreter라면 생성 자체를 거부했을 객체를 JIT가 생성했기 때문입니다. 다른 하나는 matcher와 기록 대상 buffer 사이의 길이 계약입니다. 다만 crash를 넘어서는 결과를 얻으려면 stack depth에 좌우되는 parse 실패를 먼저 맞춰야 합니다. severity가 더 높은 구간으로 올라가지 않는 이유입니다.

Audit directions

객체를 그대로 공개하는 early-return constructor. finishCreation이 멤버 초기화 전에 빠져나가면 return 이후의 코드는 조용히 건너뛰어집니다. 그럼에도 절반만 생성된 객체는 cache나 JIT 상수 pool, weak map으로 그대로 전달됩니다. JSC에서 실패 경로를 가진 다른 finishCreation 구현들을 점검해 볼 필요가 있습니다. 각각에 대해, constructor가 설정한 validity flag를 확인하지 않고도 해당 객체를 획득할 수 있는 경로가 있는지 확인하는 것이 핵심입니다. 검토 시 눈에 띄어야 할 신호는 if (!isValid()) return; 아래로 멤버 초기화가 이어지는 형태입니다.
release에서 중요한 invariant를 debug 전용으로만 확인하는 경우. 반드시 일치해야 하는 두 개의 개수를 비교하는 ASSERT는, 그 코드에 서로 다른 두 개의 기준 값이 존재하고 runtime에는 이를 강제하는 수단이 없다는 뜻입니다. cache된 개수와 새로 계산한 개수를 비교하는 ASSERT가 검색 대상입니다. 특히 recompile 경로와 re-parse 경로 주변을 중점적으로 살펴볼 필요가 있습니다. 그리고 값이 실제로 전달되거나 다시 계산되기 전까지는, 각각을 release build의 빈틈으로 간주하는 편이 안전합니다.
재시도를 허용하는 soft 실패. 객체를 reset하고 다시 시도하도록 허용하는 error 분류에서는, metadata가 실패한 시도를 반영하는 동안 생성된 코드는 성공한 시도를 반영하는 구간이 열립니다. hasHardError에서 출발해, 이 함수가 false인 분기에서 reset()을 호출하는 호출 지점들을 열거해 보는 것이 출발점입니다.