[4] Iterator invalidation in `Page::forEachPage` and its sibling walkers

MediumWebCore PageUAF

60fe8ff

Medium. hash set을 순회하는 도중 호출자가 넘긴 callback이 실행되면, 그 안에서 Page를 생성하거나 파괴할 수 있습니다. 어느 쪽이든 loop cursor 아래에서 컨테이너가 rehash됩니다. 다만 실제로 page를 만들거나 없애는 callback이어야 하므로, 유발 경로는 상당히 좁아집니다.

Iterator invalidation은 C++ 컨테이너의 기본 규칙이지만, 브라우저에서는 특유의 형태로 터집니다. hash set을 순회하는 중에 loop 본문이 원소를 추가하거나 제거하면, 손에 쥔 cursor는 이미 사라진 buffer를 가리키게 됩니다. WebCore는 살아 있는 모든 Page를 process 전역 registry에 모아 둡니다. 여기서 Page는 browsing context 하나의 root 객체로, frame tree와 settings, focus 및 back/forward controller를 소유합니다. Page는 생성과 소멸에 맞춰 이 registry에 들어가고 빠집니다. 그리고 네 개의 static helper가 이 registry를 훑으면서 작업을 퍼뜨리는데, 각각은 모든 Page를 외부 코드에 전달합니다. 그 코드는 무엇이든 할 수 있으며, 또 다른 page를 만드는 일도 여기에 포함됩니다.

관전 포인트: 네 개의 registry 순회 함수 중 하나에서 도달 가능한 callback이 Page를 생성하거나 파괴하면, loop는 해제된 heap을 읽는 동작으로 바뀝니다. 이어지는 iteration에서는 해제된 bucket array에서 읽어온 pointer를 통해 reference count write가 수행됩니다.

Patch Details

네 곳의 호출 지점이 동일한 형태를 공유하며, 네 곳 모두 수정되었습니다. 먼저 Page::forEachPage는 allPages()에 대한 iterator를 유지한 채로, 원소마다 호출자가 넘긴 임의의 Function<void(Page&)>를 실행했고 그때마다 Ref { page.get() }를 생성했습니다. clearPreviousItemFromAllPages도 같은 set을 순회하면서, loop 본문에서 page->localMainFrame()과 back/forward item 상태에 접근했습니다. updateStyleForAllPagesAfterGlobalChangeInEnvironment는 page마다 전체 style update를 수행했고, updateControlTintsForAllPages는 tint update를 수행했습니다. 수정의 핵심은 외부 코드를 호출하는 구간 동안 allPages()에 대한 살아 있는 iterator를 더 이상 유지하지 않도록 한 것입니다. 네 곳 중 세 곳이 이미 가지고 있던 원소별 Ref 임시 객체는 애초에 여기서 필요한 보호 장치가 아니었습니다. 해당 Ref는 현재 Page의 lifetime만 연장할 뿐, 컨테이너의 backing store에 대해서는 아무것도 보장하지 않기 때문입니다.

  for (auto& page : allPages())        allPages() bucket array
  ───────────────────────────────      ───────────────────────
  it ──► bucket[3]                     [ .. .. p0 p1 .. ]  @0xA000
  callback(p1)
    └─ constructs a Page ──► add()     load factor exceeded:
                                       alloc @0xB000, rehash, free(0xA000)
  ++it  ──► 0xA000 + stride            (freed)
  Ref { page.get() }                   refcount write via pointer read
                                       out of the freed bucket array  ← UAF

컨테이너를 순회하는 도중 임의의 callback이 호출되고, 그 callback이 순회 대상 컨테이너의 구조를 변경할 수 있는 패턴.

Background

이 코드가 있는 위치. Page는 browsing context 하나를 대표하는 renderer 쪽 root 객체입니다. frame tree, settings 객체, 브라우저 UI 셸을 담당하는 client, 그리고 focus와 back/forward controller를 소유합니다. 한편 WebCore의 전역 상태 상당수는 명목상 page 단위로 관리됩니다. style environment, control tint, back/forward item 등이 여기에 해당합니다. 그래서 process 안의 모든 Page에 변경을 적용하는 helper들이 존재하고, 이런 helper에는 순회할 registry가 필요합니다.

전역 registry. allPages()가 바로 그 registry입니다. process 전역 hash set이며, Page는 생성될 때 여기에 등록되고 파괴될 때 빠집니다. 이 set이 담는 것은 강한 Ref<Page> 항목이 아니라 소유권 없는 reference wrapper입니다. 패치 이전 코드의 page.get() 및 page-> 사용, 그리고 네 곳 중 세 곳이 별도로 만들어야 했던 Ref { ... } 임시 객체가 그 근거입니다. Page.h가 <wtf/WeakHashSet.h>와 <wtf/RobinHoodHashSet.h>를 모두 include한다는 점과도 일치합니다.

Open addressing과 rehashing. WTF의 hash set은 항목을 하나의 연속된 bucket array에 저장합니다. 삽입으로 table이 load factor를 넘어서면, 더 큰 array를 할당하고 기존 항목을 그쪽으로 rehash한 뒤 이전 array를 해제합니다. 제거 역시 같은 방식으로 축소와 rehash를 유발할 수 있습니다. 이때 iterator는 그 array를 가리키는 raw cursor일 뿐이며, 컨테이너가 관리하는 handle이 아닙니다. 그래서 재할당이 일어나면 살아 있는 모든 iterator가 해제된 메모리를 가리키게 되고, 아무런 진단도 남지 않습니다.

Ref가 보호하는 대상. Ref<T>는 WebKit의 non-null 강한 참조입니다. 생성 시 대상의 count를 증가시키고, 소멸 시 감소시킵니다. 즉 Ref가 살려 두는 것은 자신이 가리키는 객체뿐입니다. 그 객체를 찾아낸 컨테이너와는 아무 관계가 없으며, 여기서 중요한 구분이 바로 이 지점입니다.

Analysis

Bug class는 iterator invalidation으로 인한 use-after-free이며, re-entrancy가 그 계기입니다. 빠져 있던 invariant는 open addressing 기반 hash 컨테이너라면 모두 요구하는 조건입니다. iterator가 살아 있는 동안 컨테이너의 구조를 변경해서는 안 된다는 규칙입니다. 그런데 Page는 생성될 때 스스로를 allPages()에 등록하고 파괴될 때 등록을 해제합니다. 따라서 Page를 동기적으로 생성하거나 파괴하는 callback은 지금 순회 중인 바로 그 set을 변경하게 됩니다.

위 도식의 순서를 따라가 보면 흐름이 분명해집니다. for loop의 cursor는 0xA000에 있는 bucket array를 가리키는 raw pointer입니다. loop 본문에서는 callback을 통해 도달한 Page 생성이 add()를 호출합니다. 이때 table이 load factor를 넘어서면 0xB000에 더 큰 array가 할당되고, 항목들이 그쪽으로 rehash된 뒤 0xA000이 해제됩니다. loop는 여전히 해제된 영역을 가리키는 cursor를 쥐고 있습니다. 결과적으로 다음 증가 연산과 다음 원소 읽기는 해제된 heap을 건드립니다. forEachPage에서는 패치 이전 코드가 그 해제된 블록에 남아 있던 값으로 Ref { page.get() }를 구성했습니다. 해제된 메모리에서 읽어온 pointer를 통해 reference count 연산이 수행된 셈입니다. clearPreviousItemFromAllPages에서는 해제된 블록에서 읽은 값이 곧바로 page->localMainFrame()으로 들어갔습니다. 파괴는 그 반대 경우로, 제거가 축소와 rehash를 유발하면서 같은 결과로 이어집니다.

네 곳 중 세 곳에 들어 있던 원소별 Ref 임시 객체는 검토자를 가장 쉽게 오도하는 부분입니다. lifetime을 챙긴 코드처럼 보이고, 실제로 현재 Page에 한해서는 그 역할을 합니다. 다만 실제로 해제되는 대상은 bucket array이며, 이 코드의 어떤 Ref도 그 array를 가리키지 않습니다.

Exploitability는 도달 가능한 callback이 무엇까지 할 수 있는지에 달려 있습니다. 가장 직접적인 primitive는 forEachPage의 refcount write입니다. 해제된 allocation 안의 특정 offset에 증가가 적용되고 이후 감소가 적용되는 형태인데, 해당 블록을 무엇이 회수할지 제어할 수 있는 공격자가 노리는 전형적인 모양입니다. 다만 여기서 더 나아가려면 재할당 시점과 회수된 블록의 내용을 모두 매번 동일하게 제어할 수 있어야 하고, 이번 변경만으로는 어느 쪽도 확인되지 않습니다. 또한 도달 가능한 유발 지점은 page를 생성하거나 파괴하는 callback으로 한정되므로, "script로 호출 가능한 모든 것"에 비하면 훨씬 좁은 surface입니다.

결과적으로 이 vulnerability는 process 전역 registry의 무결성을 약화시킵니다. WebCore에서 page 전체를 대상으로 하는 모든 broadcast가 이 컨테이너를 순회합니다. 그래서 컨테이너가 손상되면, 문제의 callback이 작성된 위치와는 한참 떨어진 코드에서 그 영향이 관찰됩니다.

Audit directions

컨테이너 순회 중의 외부 호출. 위험한 형태는 컨테이너를 도는 for loop의 본문에서 Function이나 client delegate, JS callback, 혹은 loop 작성자가 짜지 않은 코드에 도달할 수 있는 virtual 호출이 실행되는 경우입니다. 도달 가능한 변경이 항상 눈에 띄는 형태인 것도 아닙니다. 이번 사례에서 변경을 일으킨 것은 add() 호출이 아니라 객체 생성자였습니다. 점검은 WebCore에서 forEach 형태의 broadcast 함수를 가진 다른 process 전역 registry부터 시작하면 됩니다. WTF hash 컨테이너를 순회하면서 Function<...> 파라미터를 호출하는 loop도 함께 살펴볼 필요가 있습니다. 코드 리뷰에서의 단서는 전역 accessor 함수를 대상으로 하는 range-for이면서 본문이 callable 파라미터를 받는 경우입니다. 특히 본문에 방어적인 Ref/RefPtr 임시 객체가 이미 들어 있다면 더 주의할 만합니다. 그 임시 객체는 작성자가 lifetime을 의식했다는 뜻이지만, 동시에 한 단계 얕은 수준에서 멈췄다는 신호이기도 합니다.
컨테이너가 아니라 원소를 지키는 보호 장치. 순회 안에 들어 있는 원소별 강한 참조는 lifetime을 의식했다는 근거이지만, 그 대상이 잘못 잡혀 있다는 신호이기도 합니다. 점검할 때는 두 질문을 분명히 나눠서 던져야 합니다. 첫째, loop 도중 이 원소가 죽을 수 있는가. 둘째, loop 도중 컨테이너 자체가 재할당될 수 있는가. 이번 세 곳은 첫 번째 질문에만 답하고 두 번째는 놓쳤습니다.
생성자와 소멸자에서의 등록. 스스로 등록하는 객체는 호출 지점에서 컨테이너 변경을 보이지 않게 만듭니다. 변경이 컨테이너 메서드가 아니라 new의 side effect로 발생하기 때문입니다. 어떤 타입이 전역 collection에 스스로를 등록한다면, 그 collection을 순회하는 경로에서 도달 가능한 모든 생성과 파괴를 구조 변경으로 간주해야 합니다. 아울러 어떤 broadcast helper가 객체 생성까지 도달할 수 있는지 추적할 필요가 있습니다.