[3] Array rematerialization should know how to have a bad time

HighJSC FTL JITTypeConfusion

The array that came back from an OSR exit disagreed with itself about its layout.

eba64ef

High. Exit-time reconstruction 경로는 컴파일 시점에 결정된 layout으로 butterfly를 직접 구성하면서, 동시에 global object에게 structure를 요청합니다. 그런데 이 두 값 모두 스크립트가 제어할 수 있는 대상입니다. 그 결과 JSC의 전형적인 structure/butterfly confusion이 발생하며, pointer 타입인 m_sparseMap 슬롯이 attacker가 작성한 double 값과 겹쳐지게 됩니다.

WebKit의 top-tier JavaScript optimizer는 객체가 컴파일된 영역을 벗어나지 않는 경우, 해당 객체의 allocation 자체를 제거하고 그 내용에 대한 descriptor만 기록할 수 있습니다. 이후 최적화된 코드가 하위 tier로 bail out하게 되면, exit 시점에 이 descriptor를 실제 heap object로 되돌려야 합니다. 이 경로에서는 두 요소가 만나게 됩니다. 하나는 JSArray의 structure로, element가 어떻게 배치되는지 등을 기록하는 type descriptor입니다. 다른 하나는 butterfly로, 실제로 element를 담고 있는 heap block입니다. 여기서 지켜져야 할 invariant는, 재구성된 array에 설치되는 structure가 reconstruction 코드가 실제로 만든 butterfly를 정확히 기술해야 한다는 점입니다.

관전 포인트: 페이지는 엔진이 SlowPutArrayStorage 타입을 가진 JSArray를 생성하도록 유도할 수 있는데, 이때 실제 backing store는 contiguous 형태를 유지합니다. 결과적으로 이후 모든 indexed access는 고정된 displacement 위치에서 읽고 쓰게 되며, attacker가 선택한 double 값을 pointer field를 포함한 array metadata로 재해석하게 됩니다.

Commit message에는 이 구조가 정확히 명시되어 있습니다. Sunk array가 butterfly와 함께 rematerialize될 때는 항상 contiguous butterfly로 재구성되는데, 그 사이 VM이 bad time을 겪어 모든 array structure를 SlowPutArrayStorage로 전환했다면, rematerialization은 이제 ArrayStorage가 된 array를 여전히 contiguous butterfly인 것처럼 다루게 됩니다. 이 fix는 여전히 contiguous butterfly로 rematerialize하는 방식은 유지하되, VM이 bad time 상태라면 이후 SlowPutArrayStorage로 전환하도록 변경합니다.

Source/JavaScriptCore/ftl/FTLOperations.cpp

Source/JavaScriptCore/ftl/FTLOperations.cpp

JSTests/stress/ftl-osr-exit-phantom-new-array-with-butterfly-having-a-bad-time.js

Patch Details

두 production 변경 모두 FTLOperations.cpp의 FTL OSR-exit object rematerialization 중 PhantomNewArrayWithButterfly 경로에 위치합니다.

operationMaterializeObjectInOSR에서는 structure lookup이 globalObject->arrayStructureForIndexingTypeDuringAllocation(materialization->indexingType())에서 globalObject->originalArrayStructureForIndexingType(materialization->indexingType())로 변경됩니다. Rematerialization 코드는 항상 non-ArrayStorage 형태(contiguous, double, 또는 int32 형태)의 butterfly를 직접 만들기 때문에, structure 역시 global object가 현재 allocation 시점에 내주는 값이 아니라 해당 indexing type의 원본 structure여야 합니다. Butterfly가 sentinel 값으로 채워진 뒤에는 새로운 tail block이 추가됩니다. globalObject->isHavingABadTime()이 참이면 result->switchToSlowPutArrayStorage(vm)을 통해 array를 정상적으로 변환하며, ASSERT_ENABLED 빌드에서만 동작하는 cross-check로 arrayStructureForIndexingTypeDuringAllocation이 실제로 그 시점에 hasSlowPutArrayStorage structure를 반환했을지를 검증합니다.

operationPopulateObjectInOSR에서는 hole-writing fast path에 세 번째 분기가 추가됩니다. else if (hasAnyArrayStorage(array->indexingType()) && !value) array->butterfly()->arrayStorage()->m_vector[index].clear();인데, 이는 array가 이미 SlowPutArrayStorage로 전환된 경우를 처리하기 위한 것입니다. 이 경우 빈 JSValue hole은 contiguous().atUnsafe(index)를 통해 쓰는 대신 ArrayStorage vector에서 clear되어야 합니다. 두 함수의 comment block이 확장되었고, 나머지 파일 변경 사항은 새로 추가된 regression test입니다.

Mutable한 global 상태로부터 객체의 type descriptor를 도출하면서, 정작 메모리 layout은 컴파일 시점의 낡은 가정을 기반으로 구성하여 descriptor와 backing store가 서로 어긋나는 패턴.

Background

Butterfly. JSC는 객체의 indexed element와 out-of-line named property를 butterfly라 불리는 하나의 heap block에 저장합니다. 이 pointer는 block 중간을 가리키며, 아래쪽에는 named property가, 위쪽에는 indexed element가 위치합니다. 그리고 그 앞에는 public length와 vector length를 담은 IndexingHeader가 존재합니다.

Indexing types. Array의 structure는 element 영역이 어떻게 배치되는지를 기록합니다. ArrayWithInt32, ArrayWithDouble, ArrayWithContiguous는 butterfly pointer 자체에서 element를 시작하는 반면, ArrayWithArrayStorage와 ArrayWithSlowPutArrayStorage는 butterfly pointer 위치에 ArrayStorage header(m_sparseMap, write-barrier가 걸린 pointer; m_indexBias; m_numValuesInVector)를 먼저 배치하고, 그 뒤에 element vector m_vector[]를 둡니다.

Having a bad time. 스크립트가 모든 array에 대해 fast indexed access를 더 이상 안전하지 않게 만드는 동작을 수행하면 — 가장 흔한 경우가 Array.prototype이나 Object.prototype에 indexed accessor를 설치하는 것입니다 — global object는 haveABadTime()을 호출합니다. 이 호출은 기존 array들을 SlowPutArrayStorage로 전환시키고, 이후로는 arrayStructureForIndexingTypeDuringAllocation()이 모든 indexing type에 대해 SlowPutArrayStorage structure를 반환하도록 만듭니다. originalArrayStructureForIndexingType()은 주어진 indexing type에 대해 bad-time 이전의 structure를 반환합니다. 실제 변환은 JSObject::switchToSlowPutArrayStorage()가 수행하는데, butterfly를 ArrayStorage 형태로 재할당하고 element들을 이관합니다.

Allocation sinking. 컴파일된 영역을 벗어나지 않는 객체의 allocation을 제거하는 FTL 최적화입니다. 제거된 allocation은 phantom materialization descriptor로 기록되는데, 여기서는 PhantomNewArrayWithButterfly가 그 역할을 하며 register나 stack에 보관된 property와 element 값들을 나열합니다.

OSR exit and rematerialization. 최적화된 코드가 하위 tier로 bail out할 때, observable해지는 sunk object는 heap 상에 재구성되어야 합니다. operationMaterializeObjectInOSR이 object와 butterfly를 allocate하고, 이어서 operationPopulateObjectInOSR이 기록된 element 값들을 그 안에 기록합니다.

Hole sentinels. 아직 쓰이지 않은 element는 int32/contiguous array에서는 empty JSValue, double array에서는 PNaN으로 표현됩니다. Populate 경로는 이 값들을 putDirectIndex를 거치지 않고 butterfly에 직접 기록하는데, 그렇지 않으면 indexing-type 변환이 강제로 발생하기 때문입니다.

Watchpoints. VM이 bad time 상태가 아니라는 가정 하에 컴파일된 FTL 코드는, 이 가정이 깨지는 순간 invalidate됩니다. 이는 OSR exit이 강제되는 경로 중 하나입니다.

Analysis

이것은 structure와 butterfly가 서로 다른 시점에 이루어진 두 개의 lookup에 의해 결정되는 type confusion입니다.

  Compile time                     Exit time (bad time now on)
  ────────────                     ───────────────────────────
  sink new Array(5)                structure := arrayStructureFor...
    indexingType = Double            ──► SlowPutArrayStorage
                                   butterfly := hand-built contiguous
                                     elem[0] at butterfly + 0

  ArrayStorage view of that block:
    butterfly + 0  ─► m_sparseMap      ◄── holds 1.1 (attacker double)
    butterfly + 8  ─► m_indexBias/m_numValuesInVector
    butterfly + 16 ─► m_vector[0]      ◄── reads elem[2]

Bad-time 전환은 FTL 컴파일 시점과 sunk array를 실제로 materialize하는 OSR exit 시점 사이에 발생할 수 있습니다. 정확히 이 window를 regression test가 열고 있는데, opt() 실행 도중 noInline으로 지정된 callee 안에서 Object.defineProperty(Array.prototype, 0, {get(){}})를 호출하는 방식입니다. Exit 시점에 array는 indexing type이 ArrayStorage인 structure를 부여받지만, butterfly는 여전히 contiguous하게 배치되어 있습니다. 이후의 모든 access는 실제로 값이 저장된 위치에서 고정된 양(positive)의 displacement만큼 떨어진 곳을 읽거나 쓰게 되고, element data의 첫 슬롯들은 ArrayStorage header — pointer field인 m_sparseMap을 포함해서 — 로 재해석됩니다.

operationPopulateObjectInOSR은 이 문제를 한층 더 악화시켰습니다. Array가 이제 ArrayStorage 타입으로 취급되면서 hasDouble / hasInt32 / hasContiguous 검사가 모두 실패하게 되고, 그 결과 element 값들이 putDirectIndex를 거쳐 기록됩니다. 이는 contiguous storage 크기로 만들어진 butterfly 위의 m_vector[index]에 쓰기를 수행하는 셈입니다.

테스트가 사용하는 shell helper (gc(), noInline, --jitPolicyScale)를 제외한 나머지 동작은 모두 평범한 JS 코드로도 재현 가능합니다. FTL이 array allocation을 sink한 채로 함수를 컴파일할 때까지 warm-up시킨 다음, 그 함수 중간의 호출 안에서 haveABadTime()을 유발하면 됩니다. 코드 흐름을 따라가 보면, opt()는 new Array(5)를 할당하고 double 값들로 채워 phantom materialization이 ArrayWithDouble을 갖도록 만듭니다. 그리고 최종 합산 이전까지 array를 escape시키지 않기 때문에, allocation sinking이 이를 제거합니다. 1001번째 호출에서 trigger가 true가 되면서 cb()가 indexed accessor를 설치하게 되고, 이에 따라 global object는 bad-time 상태로 진입하며 FTL 코드의 가정이 invalidate되어 sunk array를 반드시 rematerialize해야 하는 exit이 강제됩니다. Fix 이전에는 arrayStructureForIndexingTypeDuringAllocation(ArrayWithDouble)이 SlowPutArrayStorage structure를 응답하는 동안에도, 이어지는 코드는 여전히 butterfly->contiguous().atUnsafe(index)를 통해 butterfly를 구성하고 sentinel 값으로 채웁니다. 이후 기록된 다섯 개의 값은 putDirectIndex를 거치게 되고, 마지막의 gc()가 이 불일치된 view로 array를 순회하게 됩니다. 이 write가 ArrayStorage의 fast path(vector 내부)를 타는지 slow path를 타는지는 canSetIndexQuicklyForPutDirect에 달려 있는데, 이 함수는 vector length와 m_numValuesInVector를 참조하며 이번에 제공된 context에는 포함되어 있지 않습니다.

여기서 한 단계 더 나아가 생각해 보면, ArrayStorage header가 attacker가 선택한 double 값으로 채워진 슬롯과 겹치기 때문에 m_sparseMap의 WriteBarrier field가 완전히 attacker 통제 하의 bit pattern을 갖게 될 가능성이 있고, m_numValuesInVector / m_indexBias 역시 임의의 32-bit 값으로 설정될 가능성이 있습니다. 이후 slow-put이나 sparse-map lookup이 이 field를 dereference한다면 attacker는 fake-object read primitive를 얻게 될 가능성이 있고, m_indexBias 기반 연산이 vector base를 재계산하는 데 사용된다면 access 위치가 추가로 displacement될 가능성도 있습니다. 다만 이 두 확장 시나리오는 예상되는 방향일 뿐 확립된 동작은 아닙니다. 이를 실제로 달성하려면 out-of-bounds write가 m_vector[] 상단에서 원하는 인접 객체 위에 정확히 놓이도록 하는 heap grooming과, confused array를 JS에서 처음 소비하는 연산을 통제하는 능력이 모두 필요한데, 이번 변경 사항만으로는 이 두 조건 중 어느 것도 성립하지 않습니다.

이 vulnerability는 WebContent process 내부에서 JSC의 type-safety boundary를 약화시킵니다. 여기서 지켜져야 할 invariant는 JSObject의 structure가 butterfly layout을 정확히 반영해야 한다는 것입니다. Fix 이전에는 평범한 스크립트만으로도 structure는 SlowPutArrayStorage라고 말하지만 실제 backing store는 contiguous인 JSArray를 만들어낼 수 있었습니다. 그 결과 이후의 모든 indexed access — JS 코드에서든, inline cache에서든, GC의 visit routine에서든 — 는 attacker가 작성한 element data를 ArrayStorage metadata로 해석하게 됩니다. 이 상태를 안정적으로 유발할 수 있는 attacker라면 butterfly에 인접한 out-of-bounds access와, controlled double로부터 채워진 pointer field를 함께 확보할 수 있습니다. 이는 renderer 내에서 arbitrary read/write를 구축하는 전형적인 출발점에 해당합니다. 다만 그 이상으로 나아가려면 별도의 sandbox escape가 여전히 필요합니다.

주목할 만한 점은, 이 버그가 allocation 경로가 아니라 reconstruction 경로에 존재한다는 사실입니다. operationMaterializeObjectInOSR은 exit 시점에, 컴파일 시점에 결정된 shape를 가진 객체를 재현해야 하는 구조상 그 사이에 발생하는 어떠한 global VM 상태 변화에도 노출됩니다. arrayStructureForIndexingTypeDuringAllocation()이 일반적인 allocation site에서는 정확한 선택인 이유는, 이 함수가 현재의 bad-time 상태를 따라가기 때문입니다. 반대로 caller가 이미 구체적인 메모리 layout에 commit한 지점에서는 이 함수 호출이 잘못된 선택이 됩니다. 이번 fix의 핵심 방향은 일반적인 해법이기도 합니다. Layout 변환은 실제로 메모리를 재작성하는 routine을 통해서만 이루어져야 하며, type descriptor를 단순히 바꿔치기해서는 안 됩니다. 한 가지 더 눈여겨볼 부분은 이 fix가 만든 파급 효과입니다. Materialize 쪽을 수정하자 populate 쪽에도 대응하는 분기가 필요해졌는데, 이는 그쪽의 hole-writing fast path 역시 "rematerialize된 array는 절대 ArrayStorage가 아니다"라는 동일한 가정 위에 작성되어 있었기 때문입니다. "이 경로는 오직 layout X만 볼 수 있다"는 형태의 invariant는 대체로 여러 함수에 중복되어 존재하는 경향이 있으며, 그 함수들은 한꺼번에 함께 깨지곤 합니다.

Audit directions

• 컴파일 시점에 정해지는 레이아웃과, 이후 mutable global state에서 조회되는 type descriptor가 짝을 이루는 패턴. descriptor는 world의 변화를 추적하지만, layout은 그렇지 않습니다. 좁게 보면, Source/JavaScriptCore/ftl/FTLOperations.cpp와 Source/JavaScriptCore/dfg/DFGOSRExit*.cpp에서 arrayStructureForIndexingTypeDuringAllocation, arrayStructureForProfileDuringAllocation 및 OSR-exit나 rematerialization 코드에서 호출되는 유사한 accessor를 모두 검색해볼 필요가 있습니다. 이 호출들을 storage를 직접 구성하는 다른 Phantom* materialization case들 — PhantomNewArrayBuffer, PhantomNewArrayWithSpread, PhantomCreateRest, PhantomSpread — 과 하나씩 대조해봐야 합니다. 코드 리뷰 시 눈여겨볼 신호는, 같은 함수 안에서 global-object structure accessor를 조회하면서 동시에 contiguous(), contiguousDouble(), arrayStorage()와 같은 layout 특정 accessor로 값을 기록하는 경우입니다. 이 두 사실이 같은 source에서 유도되지 않는다면 의심해볼 후보에 해당합니다. 넓게 보면, 이전 시점의 결정으로 shape이 고정된 채 지연되는 모든 객체 생성에서 같은 부류의 문제가 나타날 수 있습니다. structure를 caching한 뒤 나중에 storage를 기록하는 DFG/FTL inline-cache stub 생성이 그 예이며, backing store를 재할당하지 않으면서 type tag만 바꾸는 Structure-swapping helper 역시 마찬가지입니다. setStructure / setStructureIDDirectly 호출이 이를 정당화하는 재할당 코드와 바로 인접해 있지 않은 경우를 찾아볼 필요가 있습니다. 가장 넓게 보면, type tag와 그 memory layout은 반드시 하나의 원자적 결정으로 만들어져야 하며, 시간차를 두고 이루어지는 두 번의 조회로 만들어져서는 안 됩니다. 이 원칙은 V8의 Turbofan escape-analysis materialization, SpiderMonkey의 bailout object reconstruction, HotSpot의 scalar-replacement reallocation, 그리고 일반적인 serialization/deserialization 쌍에도 동일하게 적용됩니다.

• consumer가 직접 allocate하지 않은 객체에 대한 indexing-type dispatch. 좁게 보면, operationPopulateObjectInOSR와 그에 대응하는 DFG 코드에서 hasDouble / hasInt32 / hasContiguous / hasAnyArrayStorage 체인이 직접적인 butterfly()->...atUnsafe() 기록으로 끝나는 부분을 모두 나열해볼 필요가 있습니다. 이때 indexing type의 집합이 닫혀 있다고 가정하지 말고, 각 체인이 실제로 모든 경우를 빠짐없이 다루는지 확인해야 합니다. 새로 추가된 hasAnyArrayStorage(...) && !value 분기는, 이전 체인이 예상하지 못한 type에 대해 조용히 putDirectIndex로 흘러들어갔기 때문에 정확히 존재하는 코드입니다. 코드 리뷰 시 눈여겨볼 신호는, has*(indexingType())에 대한 if/else-if 사다리 구조에서 마지막 else가 남은 case들을 처리하는 대신 의미적으로 전혀 다른 동작을 수행하는 경우입니다. 넓게 보면, WebKit이 값의 집합이 닫혀 있다고 가정한 채 tag를 기준으로 dispatch하는 곳이라면 어디서든 같은 형태의 문제가 나타날 수 있습니다. GC의 visitChildren에 있는 JSType switch, DFG fixup의 ArrayMode 처리, JSObject 변환 helper의 IndexingType switch가 그 예입니다. default: RELEASE_ASSERT_NOT_REACHED()가 없는 switch 문을 찾아볼 필요가 있습니다. 가장 넓게 보면, tag의 case를 나열하는 모든 dispatch는 반드시 모든 경우를 다루거나, 그렇지 않으면 남은 경우에서 확실하게 fail해야 합니다. Rust match의 arm이 _ =>로 뭉뚱그려지는 경우, default가 없는 C switch, protobuf oneof 처리 등이 모두 같은 원칙의 적용 대상입니다.

• compile-to-exit window 내부에서 변경되는 global VM state. 좁게 보면, JSGlobalObject::haveABadTime()의 호출부와 array fast path를 보호하는 watchpoint set들 — havingABadTimeWatchpoint, arrayIteratorProtocolWatchpointSet, prototype-chain structure watchpoint — 을 추적해볼 필요가 있습니다. 그리고 Source/JavaScriptCore/ftl/과 Source/JavaScriptCore/dfg/의 exit-time runtime helper 중, exit가 시작된 이후에 이 watchpoint들이 보호하던 state를 읽는 코드가 있는지 확인해야 합니다. 일치 여부를 확인할 신호는, compiled code에서 watchpoint로 보호되는 값을 exit-time helper가 그대로 읽는 JSGlobalObject accessor입니다. 코드가 invalidate된 시점부터는 watchpoint가 더 이상 아무것도 보호하지 못합니다. 넓게 보면, "invalidate된 assumption이 recovery path까지 살아남는" 모든 경우로 일반화할 수 있습니다. 지연된 destructor와 finalizer callback, 그리고 DFG exit recovery가 사용하는 sentinel/scratch-buffer의 내용 역시, 컴파일 시점의 가정 하에 기록된 뒤 나중에 사용된다는 점에서 같은 패턴에 해당합니다. 가장 넓게 보면, recovery path는 recovery를 유발한 바로 그 사건이 방금 무효화시킨 assumption을 사용해서는 안 됩니다. 이 원칙은 database의 query-plan invalidation을 포함해, speculate-and-deoptimize 방식을 사용하는 모든 시스템에 동일하게 적용됩니다.

• layout 변환 과정에서의 hole 및 sentinel 처리. 좁게 보면, FTLOperations.cpp와 JSObject.cpp의 변환 helper (convertContiguousToArrayStorage, switchToSlowPutArrayStorage 등)에서 butterfly에 hole sentinel을 직접 기록하는 모든 지점을 살펴볼 필요가 있습니다. int32/contiguous에는 setStartingValue(JSValue()), double에는 PNaN, ArrayStorage vector에는 .clear()가 사용됩니다. 이때 기록되는 sentinel이, 함수 시작 시점이 아니라 실제로 기록이 이루어지는 시점에 객체가 갖고 있는 indexing type과 일치하는지 확인해야 합니다. 코드 리뷰 시 눈여겨볼 신호는, hole을 기록할 때 사용하는 layout accessor가 실제 기록 코드보다 앞선 시점에 평가된 조건으로 선택되는 경우입니다. 넓게 보면, representation을 caching해둔 코드가 representation마다 다른 sentinel encoding을 기록하는 경우도 같은 범주에 속하며, m_numValuesInVector bookkeeping과 sparse-map transition에도 동일하게 적용됩니다. 가장 넓게 보면, 같은 논리적 값("absent")이 representation에 따라 다르게 encoding된다면, encoding의 선택은 반드시 기록이 이루어지는 그 시점에 다시 도출되어야 합니다. hash-table의 tombstone, columnar storage의 null encoding, 다른 엔진들의 tagged-pointer NaN boxing이 모두 이 원칙의 적용 대상입니다.