XPath sorting asserts on node-sets with nodes from different trees
Component: WebCore XPath | 5f78a99
Source/WebCore/xml/XPathNodeSet.cpp
XPath의 location path와 union은 node-set을 생성하며, 이 결과는 document order로 정렬되어 반환되어야 합니다. 먼저 node-set이 작을 때는 각 node마다 ancestor chain을 구성한 뒤 chain끼리 비교합니다. 반면 node가 대략 10,000개를 넘으면 traversal sort로 전환됩니다. 이 방식은 하나의 root에서 tree를 순회하며 만나는 순서대로 node를 내보내므로, 모든 node가 해당 root에서 도달 가능해야만 정상적으로 동작합니다.
문제는 detached attribute나 disconnected subtree가 각자 별도의 root를 갖는다는 점입니다. 그래서 document와의 union 하나에 여러 tree가 섞일 수 있습니다. 한편 shadow tree의 root는 document가 아니라 해당 ShadowRoot입니다.
이번 수정으로 NodeSet::sort()는 tree별로 따로 정렬한 뒤, 처음 등장한 순서대로 tree들을 이어 붙이도록 변경되었습니다. 17129@main 이후로는 모든 node가 하나의 tree에 속한다고 가정해 왔습니다. 이 때문에 (id("x") | .)처럼 document node와 detached attribute 또는 disconnected node가 섞인 union에서 crash나 out-of-bounds read가 발생했습니다.
이와 별개로, shadow tree 내부의 대형 node-set은 이제 shadow root를 기준으로 정렬됩니다. 91446@main 이후 traversal sort는 document에서 출발했기 때문에 shadow node에 끝내 도달하지 못했습니다.
After (mixed trees):
NodeSet {doc node, detachedAttr, ...}
└─► allNodesAreInOneTree()? no
└─► sortEachTree()
├─ tree A (first seen) ─► sortOneTree()
├─ tree B (detached) ─► sortOneTree()
└─ concatenate in first-seen order
Shadow tree (>10000 nodes):
Before: traversalSort ─► findRootNode(first) ─► Document
After: traversalSort ─► treeRoot(first) ─► ShadowRoot
Significance
Attacker가 XPath와 DOM을 직접 구성해 document.evaluate를 호출하면, web JS에서 해당 out-of-bounds read에 도달할 수 있었습니다. 같은 invariant에서 두 개의 commit에 걸쳐 regression이 두 번 발생했습니다. node-set 정렬이 기대는 tree 소속 가정이 그만큼 취약하다는 점을 시사합니다.
Audit directions
단일 tree 가정은 다른 곳에도 남아 있을 가능성이 높습니다. 먼저 하나의 tree를 전제할 수 있는 다른 NodeSet 사용처를 살펴볼 필요가 있습니다. union, predicate, position()/last() 처리, 그리고 iterator 및 snapshot 결과 타입이 대상입니다.
root 선택 로직도 점검해야 합니다. 평가 도중 ownerElement가 바뀌거나 제거되는 attribute node가 우선 후보입니다. disconnected subtree 안에 중첩된 shadow root, slotted node도 확인할 필요가 있습니다. 또한 정렬 전략이 바뀌는 10,000-node 경계 바로 근처에서 여러 tree가 섞이는 경우도 시험해 볼 만합니다.
한편 XPath 함수나 custom resolver가 DOM을 변경하는 동안 정렬이 실행될 수 있는지도 확인해야 합니다. 테스트 케이스가 id()로 union을 구성하므로, disconnected content를 대상으로 id()와 document.evaluate를 조합해 fuzzing하는 것이 자연스러운 출발점입니다.