[1] ObjectCreate constant fold drops its prototype speculation

Constant folding deleted the one check the rest of the compile had already spent

cd30bb7

Critical. Constant folding 과정에서 speculation 하나가 사라지는데, 컴파일의 나머지 부분은 이미 그 speculation을 전제로 특수화된 상태입니다. 결과적으로 컴파일 시점에 죽었다고 판정된 branch가 런타임에 실행되고, 이를 잡아낼 exit는 남아 있지 않습니다. 스크립트로 돌아오는 값은 double의 raw bit pattern이며, 타입만 JSValue로 붙어 있습니다.

Speculative JIT 컴파일은 일종의 거래입니다. optimizer가 값의 타입을 가정하고, 가정이 틀렸을 때 빠져나가는 저렴한 런타임 체크를 emit한 뒤, 그 이후 코드는 가정이 항상 성립하는 것처럼 컴파일합니다. WebKit의 DFG mid-tier optimizer는 여기에 abstract interpreter를 붙입니다. 각 값에 대해 증명 가능한 정보를 control-flow graph를 따라 전파하는 컴파일 타임 pass입니다. 그 접점에 ConstantFoldingPhase가 있습니다. interpreter가 상수라고 증명한 operand를 가진 노드를 다시 쓰는 phase인데, 노드가 지니고 있던 check는 이 rewrite를 넘어서도 살아남아야 합니다. 다른 phase들이 이미 그 증명을 소진해 버렸기 때문입니다.

관전 포인트: DFG profile을 원하는 형태로 유도할 수 있는 스크립트가 loop body를 check 없는 contiguous array load로 컴파일시킵니다. 그 다음 같은 body를 double 형태의 array에 대해 실행하면, raw double bit가 JSValue로 되돌아옵니다.

Patch Details

변경 지점은 ConstantFoldingPhase::foldConstants 안의 ObjectCreate -> NewObject 변환입니다. FixupPhase는 object prediction이 붙은 Object.create(x)를 child1에 ObjectUse edge를 지닌 ObjectCreate 노드로 바꿉니다. 이 edge는 prototype operand가 object가 아니면 런타임에 exit하는 speculation에 해당합니다. abstract interpreter가 child1을 상수로 증명한 경우, fold는 캐시에서 structure를 골라 convertToNewObject()를 호출하는데, 이 함수의 children.reset()이 해당 edge를 통째로 삭제합니다. 패치는 rewrite 과정에서 speculation이 노드의 edge와 함께 사라지지 않고 살아남도록 합니다.

Downstream phase들이 이미 증명으로 활용한 speculation check가 노드 rewrite로 삭제된 패턴.

  Before the fix                        After the fix
  --------------                        -------------
  ObjectCreate @ObjectUse(child1)       ObjectCreate @ObjectUse(child1)
    CFA proves child1 == jsNull           CFA proves child1 == jsNull
    ObjectUse filter contradicts          ObjectUse filter contradicts
        |                                     |
  convertToNewObject()                  the speculation survives the
    children.reset() -> edge gone       rewrite -> exit still reachable
        |                                     |
  else-branch runs with no exit         else-branch exits to baseline
  obj is ArrayWithDouble                before the check-free load runs
  check-free Contiguous GetByVal
    -> double bits returned as JSValue

Background

이 코드가 있는 위치. DFG는 WebKit의 mid-tier JavaScript optimizer입니다. bytecode를 SSA 노드 그래프로 컴파일하고, profiling된 타입을 기반으로 speculation을 수행하며, 런타임에 speculation이 실패하면 baseline JIT로 되돌아갑니다(OSR exit). 이 tier가 빠른 이유가 바로 speculation입니다. 체크가 한 번 emit되고 나면, 그 이후 코드는 타입이 보장된 것처럼 컴파일할 수 있기 때문입니다.

Abstract interpretation and edges. 런타임 체크와 별개로, DFG는 컴파일 타임 abstract interpreter(CFA)를 실행합니다. 각 노드가 생성할 수 있는 값의 집합을 계산하는 pass입니다. edge에는 use kind가 붙는데, ObjectUse는 "이 operand는 object로 speculate된다"는 의미입니다. interpreter는 증명된 값을 edge의 use kind로 filtering합니다. 이 filter가 값 집합을 비워 버리면, 해당 block의 tail에서의 abstract state가 invalid로 표시됩니다. control이 그 block의 끝에 도달할 수 없다고 증명된 셈입니다.

Constant folding. ConstantFoldingPhase는 그래프를 순회하면서, interpreter가 상수로 증명한 operand를 가진 노드를 다시 씁니다. convertToNewObject()가 그런 rewrite 중 하나입니다. prototype이 알려진 상수인 ObjectCreate가 캐시된 structure 위의 단순한 NewObject로 바뀝니다.

Structure checks and array modes. 한편 array-mode 선택 pass와 structure-check 제거 pass는 동일한 abstract state를 읽어, indexed load에 런타임 structure check가 필요한지 여부를 판단합니다. TypeCheckHoistingPhase도 어떤 변수에 대한 vote가 하나의 structure로 일치하면 SetLocal 위로 CheckStructure를 hoist할 수 있습니다. 둘 다 interpreter의 결론을 소비하는 downstream 쪽입니다.

Watchpoints and constant properties. Graph::tryGetConstantProperty는 아직 유효한 replacement watchpoint가 "watchpoint 생성 이후 해당 slot이 다시 쓰인 적이 없음"을 보장하는 경우, property load를 컴파일 타임 상수로 fold합니다.

Analysis

root cause는 컴파일 타임 증명과 그 증명을 만들어 낸 런타임 체크 사이의 순서 문제입니다. CFA가 도는 동안 PoC는 tryGetConstantProperty가 getKey(G)를 jsNull()로 fold하도록 유도합니다. 마지막 write 이후에 생성된 G.k의 replacement watchpoint를 이용하는 방식입니다. 이때 증명된 null을 ObjectUse edge로 filtering하면 모순이 발생하므로, 해당 block의 tail state가 invalid가 되고 그 predecessor는 loop header의 valuesAtHead에 아무것도 merge하지 않게 됩니다.

여기서부터가 핵심적인 결과입니다. loop header에는 이제 다른 predecessor가 기여한 ArrayWithContiguous structure set만 남습니다. 그리고 이것이 바로 payload인 obj[0]을 structure check가 제거된 Contiguous GetByVal로 컴파일해도 된다는 근거가 됩니다. 동시에 TypeCheckHoistingPhase는 두 개의 obj === o vote 때문에 무력화되므로, else-branch의 SetLocal 위로도 CheckStructure가 hoist되지 않습니다.

그 다음 ConstantFoldingPhase가 같은 ObjectCreate에 도달해 forNode(child1).m_value == jsNull을 확인하고 convertToNewObject()를 호출합니다. children.reset()이 ObjectUse edge를 삭제하는데, 이를 보존하기 위한 Check는 삽입되지 않습니다. 컴파일 시점에 죽었던 branch가 런타임에는 살아 있는 상태가 되고, 더 이상 빠져나갈 exit도 남지 않습니다.

런타임에는 else-branch가 실행되어 obj가 ArrayWithDouble이 됩니다. fold된 NewObject는 exit 없이 무조건 실행되고, 다음 iteration의 check 없는 Contiguous load가 double butterfly의 8바이트 slot을 읽어 raw bit pattern을 JSValue로 반환합니다. 즉 스크립트가 고른 64비트 패턴이 cell로 JavaScript에 전달되는 primitive입니다. 객체를 위조하는 출발점으로는 표준적인 형태지만, 그 위에 read/write primitive를 쌓으려면 heap layout 제어가 필요하며 이 버그 자체가 그것까지 제공하지는 않습니다.

이 vulnerability는 DFG의 근본적인 soundness 속성을 무너뜨립니다. 어떤 phase가 의존하는 모든 가정은 emit된 코드에 여전히 존재하는 체크로 뒷받침되어야 한다는 속성입니다. 이런 식으로 만들어지는 type confusion은 특별한 API를 필요로 하지 않습니다. profile을 원하는 형태로 유도하는 것도, watchpoint로 보호되는 constant property도 평범한 스크립트에서 모두 도달 가능하기 때문입니다.

Audit directions

Node rewrites that discard edges. children.reset()을 호출하거나 노드의 edge를 통째로 갈아치우는 변환 helper는, 그 edge가 인코딩하고 있던 speculation을 파괴합니다. 특히 위험한 경우는 fold가 정당한 이유 자체가, 지금 없애려는 edge로부터 abstract interpreter가 도출한 증명일 때입니다. DFGNode.h의 convertTo* 계열과 ConstantFoldingPhase 안의 호출 지점에서 시작해, 각각에 대해 이렇게 물어볼 필요가 있습니다. 이 rewrite가 CFA의 증명 덕분에만 정당하다면, emit된 코드에 그 증명이 의존했던 체크가 아직 남아 있는가? 코드 리뷰 관점에서는, 삽입된 Check 바로 옆에 붙어 있지 않은 convertTo* 호출이라면 어떤 speculation이 어디에서 보존되는지 설명하는 주석이 있어야 합니다.
Contradiction-driven state invalidation. abstract state가 invalid가 된 block은 successor의 merged state에 아무것도 기여하지 않습니다. 그래서 loop header가 실제 런타임에 어떤 단일 predecessor도 보장하지 않는 더 좁은 structure set을 갖는 상황이 만들어집니다. valuesAtHead를 소비하는 다른 쪽들, 즉 array-mode 선택과 structure-check 제거, TypeCheckHoistingPhase를 살펴볼 필요가 있습니다. 좁혀진 집합을 근거로 런타임 체크를 제거하는 지점을 찾고, 그 집합을 좁힌 모순이 downstream의 exit로 여전히 강제되고 있는지 확인해야 합니다.