[3] B3 `LowerToAir` CAS miscompilation — atomic sunk past interfering effects

HighJSC B3→Air instruction selectionMemoryCorruption

The canvas save stack hit its cap, and the cap stopped being a resource limit.

4dcc426

High. 이 lowering은 compare-and-swap을 이를 사용하는 branch 위치로 sink합니다. 그런데 sink 가능 여부를 판단할 때 single-use인지만 확인합니다. 그 사이에 무엇이 실행되는지는 확인하지 않습니다. 그래서 CAS가 memory.grow나 call을 넘어 이동할 수 있습니다. Correctness 결함은 interference check 누락만으로 성립합니다. Backing store 재할당으로 이어지는 확장은 추론에 해당하지만, 앞뒤 정황과 일관된 결과입니다.

B3의 LowerToAir는 pattern matching으로 B3 IR을 machine-level IR인 Air로 lowering하는 단계입니다. FTL JIT와 WebAssembly OMG optimizing tier가 모두 이 단계를 거칩니다. 관련된 요소는 세 가지입니다. 먼저 유일한 사용처가 branch인 CAS value가 있습니다. 다음으로 canBeInternal은 value가 use를 하나만 갖고 아직 materialize되지 않았는지만 확인하는 predicate입니다. 한편 crossesInterference는 짝을 이루는 predicate입니다. 후보 value의 Effects를 그 사이에 있는 모든 value와 Effects::interferes로 비교합니다. 여기서 지켜져야 할 invariant가 있습니다. Heap을 읽고 쓰는 연산은 그 사이에 충돌하는 effect가 실행되지 않을 때에만 consumer 위치로 옮길 수 있습니다.

관전 포인트: OMG가 컴파일한 WebAssembly atomic memory instruction에서는 CAS가 memory.grow를 넘어 sink될 수 있습니다. BoundsChecking mode에서 memory.grow는 backing store를 재할당하고 기존 영역을 해제합니다. 이 경우 atomic 연산은 stale pointer를 통해 engine이 이미 해제한 메모리를 읽고, 조건에 따라 쓰기까지 수행합니다.

Commit message에 따르면, LowerToAir는 canBeInternal만 확인한 채 consumer 위치에 CAS를 emit했습니다. 다섯 곳의 CAS 지점 모두에서 crossesInterference가 빠져 있었습니다. 이번 fix는 각 지점에 !crossesInterference(...)를 추가했습니다.

Source/JavaScriptCore/b3/B3LowerToAir.cpp

- if (canBeInternal(value)) {
+ if (canBeInternal(value) && !crossesInterference(value, cas)) {
      commitInternal(value);
      appendCAS(value, invert);
      return true;
  }

Patch Details

이번 diff는 다섯 곳의 CAS lowering 지점에서 sink 가능 조건에 !crossesInterference(...)를 AND 조건으로 추가했습니다. Branch switch의 case AtomicWeakCAS: arm에는 원래 자체 조건이 없었습니다. 곧바로 commitInternal(branchChild)/appendCAS(branchChild, false)로 진행했고, 바깥 case Branch: handler가 거는 전제 조건에 의존했습니다. 옆의 Equal/NotEqual arm은 branchChild가 아니라 branchChild->child(0)에 canBeInternal을 적용합니다. 이 점으로 보아 switch 바깥에 canBeInternal(branchChild) gate가 있는 것으로 보입니다. 다만 제공된 발췌는 case Branch: handler 이전에서 잘려 있어, 이 바깥 guard는 추론에 해당합니다. Diff로 분명히 드러나는 것은 해당 arm에 interference check가 없었다는 사실입니다.

Single-use 여부만으로 heap read-modify-write를 아래로 옮기면서, value와 consumer 사이에 간섭하는 effect가 있는지는 확인하지 않은 패턴.

Background

B3, Air, 그리고 OMG. B3는 JSC의 SSA 기반 optimizing IR이고, Air는 그보다 낮은 machine-level IR입니다. LowerToAir는 FTL JIT와 WebAssembly OMG tier를 위해 B3에서 Air로 instruction을 선택합니다. OMG는 Wasm의 최상위 tier입니다. 따라서 Wasm atomic instruction도 이 lowering을 거치게 됩니다.

Internalization. canBeInternal은 value가 use를 하나만 갖고 아직 materialize되지 않았는지를 알려줍니다. 이 조건은 value를 consumer에 fold하기 위한 전제 조건입니다. 다만 그 사이에 끼어 있는 instruction에 대해서는 아무것도 확인하지 않습니다.

crossesInterference와 Effects. crossesInterference는 후보 value의 Effects를 consumer까지의 모든 value와 Effects::interferes로 비교합니다. Call은 Effects::forCall()을 가집니다. B3Effects.h에 따르면 이는 HeapRange::top() 범위의 writes/reads와 writesPinned/readsPinned로 구성됩니다. 같은 파일의 다른 지점에서는 heap에 닿는 code motion마다 이 predicate를 canBeInternal과 함께 사용합니다.

BoundsChecking memory mode. --useWasmFaultSignalHandler=false이면 Wasm은 MemoryMode::BoundsChecking을 사용합니다. 이때 미리 확보된 여유 공간이 없는 memory를 grow하면 backing store가 재할당되고, 기존 영역은 해제됩니다.

Analysis

이번 버그는 JIT miscompilation입니다. 허용되지 않는 instruction scheduling 변환이 일어나고, 그 결과 stale pointer를 통한 atomic access가 발생합니다. 성격상 use-after-free 계열에 속합니다.

  B3 order:            After illegal sink:
  CAS @ addr(base0)    ... (CAS not yet emitted)
  memory.grow  ───────► reallocates store, frees region(base0)
  Branch(cas)          Branch: emit CAS @ addr(base0)   ← stale

이동하는 것은 CAS instruction뿐입니다. Operand는 원래 위치에서 Air Tmp로 materialize되는 것으로 볼 수 있습니다. 그렇다면 Wasm atomic access의 address operand는 이동 이전 시점의 memory base에서 계산된 값입니다. CAS의 원래 위치와 branch 사이에 memory.grow, 혹은 임의의 call이 실행될 수 있습니다. 이 경우 해당 operand는 더 이상 유효한 메모리를 가리키지 않습니다.

이동되는 것은 CAS instruction 하나뿐입니다. 그 address operand는 grow 이전 위치에서 Air Tmp로 materialize되었으므로 여전히 이전 memory base를 가리킵니다. MemoryMode::BoundsChecking에서 최대값이 선언되지 않은 module은 headroom을 예약하지 않습니다(reservedMaximumBytes == 0). 따라서 grow 시에는 새 영역을 확보하고 기존 영역을 해제해야 합니다. 두 세부사항 모두 결함의 핵심은 아닙니다. 핵심은 같은 전제 조건 누락이 atomic read-modify-write를 임의 호출 너머로 sink시킨다는 것이며, 이는 호출이 작성한 내용과의 ordering을 파괴합니다 — 바로 crossesInterference가 막으려는 상황입니다.

한편 correctness 결함 자체는 두 추론 어느 쪽에도 의존하지 않습니다. 같은 전제 조건 누락 때문에 atomic read-modify-write가 임의의 call을 넘어 sink될 수도 있습니다. 그러면 해당 call이 기록한 내용과 CAS 사이의 ordering이 깨집니다. crossesInterference가 막으려는 상황이 바로 이것입니다. BoundsChecking mode에서는 sink된 CAS가 stale pointer를 통해 이미 회수된 메모리를 읽고, 조건에 따라 쓰기도 합니다. Stale access를 넘어 weaponize하려면 추가 조건이 필요합니다. 재할당 layout을 제어하고, 해제된 영역을 다시 점유해야 합니다. 이 부분은 예상되는 방향에 해당합니다.

Audit directions

Heap effect가 있는 value의 이동을 canBeInternal 하나로 정당화하는 경우. Load, store, atomic을 consumer로 sink하는 lowering 지점은 반드시 canBeInternal과 crossesInterference를 함께 확인해야 합니다. B3LowerToAir.cpp에서 남은 appendCAS/atomic lowering arm을 점검할 필요가 있습니다. Effects가 비어 있지 않은 value에 대한 commitInternal도 함께 살펴봐야 합니다. Code review에서는 메모리에 닿는 value에 canBeInternal(x) guard만 있고 바로 옆에 crossesInterference(x, ...)가 없는 경우가 눈에 띄는 신호입니다.
바깥 case에서 guard를 물려받는 switch arm. AtomicWeakCAS arm은 바깥 Branch gate에 전적으로 의존했습니다. Effect가 있는 value에 대해 자체 전제 조건이 없는 arm은 refactoring 과정에서 쉽게 깨집니다. 자체 interference test 없이 곧바로 emit 단계로 넘어가는 atomic arm은 모두 표시해 둘 필요가 있습니다.