题目链接：https://github.com/saelo/v9
这是一个跟 V8 优化（冗余消除）相关的 CTF 题目。首先了解一下 V8 相关的冗余消除部分。
TurboFan 优化之基本流程
TurboFan 的优化部分的逻辑主要由 src/compiler/pipeline.cc 中实现，由多个阶段进行。以本题相关的 Load Elimination 阶段为例，在 pipeline.cc 中的 OptimizeGraph 函数中，会调用 Run<LoadEliminationPhase>(); 函数，这个调用实际上调用了结构体 LoadEliminationPhase 的 Run 函数。在 LoadEliminationPhase 的 Run 函数中，首先会创建一个 GraphReducer 的对象，然后会添加一系列的优化器到该对象中，最后调用 GraphReducer 对象的 ReduceGraph 函数（src/compiler/graph-reducer.cc）。
struct LoadEliminationPhase {
void Run(PipelineData* data, Zone* temp_zone) {
GraphReducer graph_reducer(temp_zone, data->graph(), data->jsgraph()->Dead());
// 省略添加一系列优化器
RedundancyElimination redundancy_elimination(&graph_reducer, temp_zone);
LoadElimination load_elimination(&graph_reducer, data->jsgraph(), temp_zone);
AddReducer(data, &graph_reducer, &redundancy_elimination);
AddReducer(data, &graph_reducer, &load_elimination);
graph_reducer.ReduceGraph();
}
};而 ReduceGraph 函数非常简单，直接调用 ReduceNode(graph()->end()); 函数，即将图中最后一个节点传递给 ReduceNode 函数，之后进入该阶段（Load Elimination）的优化过程。整个优化过程采用的是 DFS 遍历的模式，从最底部节点开始遍历整个图中的节点。
在 ReduceNode 函数中（src/compiler/graph-reducer.cc），会进入一个 for(;;) 的逻辑，在该循环中，首先将当前节点压入栈中，然后遍历栈。如果栈不为空，调用 ReduceTop 函数。这个函数会获取栈顶的节点，之后主要遍历该节点的所有输入节点（前继节点），由于采用的是 DFS 遍历的方式，因此每获得一个输入节点之后，如果该节点没有被遍历过（实际上这个说法不准确，因为有些节点还具有 kRevisit 状态，也能被压入栈中），则将该节点压入栈中，之后直接返回。
void GraphReducer::ReduceTop() {
// …
Node::Inputs node_inputs = node->inputs();
// Recurse on an input if necessary.
// 这里遍历输入节点，如果存在则递归
int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
for (int i = start; i < node_inputs.count(); ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}
for (int i = 0; i < start; ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}
// …
}从 ReduceTop 函数返回之后，回到 for(;;) 逻辑，这时栈顶节点为刚刚压入栈中的节点，仍然重复上述流程，直到栈顶节点为 Start 节点（没有输入节点），这时，会进入 Reduce 函数。在 Reduce 函数中，会遍历最开始添加到 GraphReducer 对象中的优化器，针对每一个优化器，对当前节点调用优化器的 Reduce 函数，该函数返回一个 Reduction 对象，Reduction 类的结构比较简单，内部存储一个名为 replacement_ 的节点，根据 replacement_ 是否为空等来判断当前节点是否被替换。
void GraphReducer::ReduceTop() {
// …
// 如果没有需要递归的输入节点
// All inputs should be visited or on stack. Apply reductions to node.
Reduction reduction = Reduce(node); // 这里遍历优化器，获得 Reduction 对象
// If there was no reduction, pop {node} and continue.
if (!reduction.Changed()) return Pop();
// Check if the reduction is an in-place update of the {node}.
Node* const replacement = reduction.replacement();
if (replacement == node) {
// In-place update of {node}, may need to recurse on an input.
Node::Inputs node_inputs = node->inputs();
for (int i = 0; i < node_inputs.count(); ++i) {
Node* input = node_inputs[i];
if (input != node && Recurse(input)) {
entry.input_index = i + 1;
return;
}
}
}
// After reducing the node, pop it off the stack.
Pop();
// Check if we have a new replacement.
if (replacement != node) {
Replace(node, replacement, max_id);
} else {
// Revisit all uses of the node.
// 重新遍历后续节点
for (Node* const user : node->uses()) {
// Don't revisit this node if it refers to itself.
if (user != node) Revisit(user);
}
}如果当前节点没有被替换，但是做了一些改变（即注释里提到的 in-place update），则会对未访问过的且未在栈中的输入节点进行递归，而且在最后会遍历其后续节点（uses）。如果当前节点被替换了，则会调用 Replace 函数，将当前节点替换成 replacement 节点。
最终，通过上述遍历完成某一阶段的优化。对于一些细节可以参考：https://mem2019.github.io/jekyll/update/2019/08/28/V8-GraphReducer-Notes.html
Redundancy-Elimination 以及题目漏洞
这道题目主要问题发生在 Redundancy Elimination（冗余消除）优化的过程中，查看 RedundancyElimination 类的 Reduce 方法（src/compiler/redundancy-elimination.cc），可以发现会根据节点类型进入不同调用分支。由于刚才提到，最初进入优化器调用 Reduce 函数的是 Start 节点，因此最初进入 ReduceStart 函数中。ReduceStart 函数的逻辑非常简单，调用 UpdateChecks 函数，在该函数中，用于更新当前节点对应的 checks，首先从 node_checks_（一个容器）获得节点对应的 checks（一个单向链表数据结构），如果需要更新的 checks 跟原来的 checks 不同，则直接进行更新。
Reduction RedundancyElimination::UpdateChecks(Node* node, EffectPathChecks const* checks) {
EffectPathChecks const* original = node_checks_.Get(node);
// Only signal that the {node} has Changed, if the information about {checks}
// has changed wrt. the {original}.
if (checks != original) {
if (original == nullptr || !checks->Equals(original)) {
node_checks_.Set(node, checks);
return Changed(node);
}
}
return NoChange();
}而 ReduceStart 就是创建一个空链表来更新 Start 节点对应的 checks。
在 Start 节点完成 Reduce 逻辑之后，由于没有替换原 Start 节点，因此会对使用 Start 节点的后续节点进行遍历，并会对这些节点进行 Reduce 操作。我们假设当前已经遍历到了一个 Check 相关的节点，该节点在进入 RedundancyElimination 类的 Reduce 方法时，会进入 ReduceCheckNode 函数调用。该函数首先获得其 Effect 输入节点，然后获得该输入节点的对应的 checks 链表。在获得了 checks 链表之后，会在该链表上查找是否有可以囊括当前节点的检查类型的节点（比如当前节点是 kCheckNumber 类型，而链表中存在 kCheckSmi 类型的节点），则认为当前节点是多余的，可以删除。如果没有找到这样的检查节点，则继续调用 UpdateChecks 函数，将当前节点加入到拿到的检查链表中，然后用得到的检查链表更新当前节点对应的 checks。（因此检查链表可以看作是到当前节点位置的那条 effect 路径上的所有检查）
Reduction RedundancyElimination::ReduceCheckNode(Node* node) {
Node* const effect = NodeProperties::GetEffectInput(node);
EffectPathChecks const* checks = node_checks_.Get(effect);
// If we do not know anything about the predecessor, do not propagate just yet
// because we will have to recompute anyway once we compute the predecessor.
if (checks == nullptr) return NoChange();
// See if we have another check that dominates us.
if (Node* check = checks->LookupCheck(node)) {
ReplaceWithValue(node, check
return Replace(check);
}
// Learn from this check.
return UpdateChecks(node, checks->AddCheck(zone(), node));
}问题就出在查找过程中，查找过程由函数 LookupCheck 进行（src/compiler/redundancy-elimination.cc），该函数调用 CheckSubsumes 来确定检查链表中的节点是否满足要求。这个函数中通过 Switch-Case 和 If-Else 来决定当前节点是否满足要求。如果节点满足了操作码的条件，再判断其值输入是否相等，如果相等则可以考虑消除当前的节点。但是该函数中本来是没有 CheckMaps 这一分支的，题目提供的 patch 提供了 CheckMaps 的分支，在该分支中，消除逻辑是如果发现后面的 CheckMaps 的 maps 可以包含前面的 CheckMaps，而且这两个 CheckMaps 的值输入节点是相同的，则可以消除后面的 CheckMaps 节点。这个逻辑忽略了在两个 CheckMaps 之间，可以改变某个对象的 Maps，这样就会造成 Type-Confusion。
利用
利用过程参考了 https://mem2019.github.io/jekyll/update/2019/08/28/V8-Redundancy-Elimination.html。
这个利用的思路是通过 __defineGetter__ 函数来改变对象的 Maps 以及对象的 Property 为 Name Dictionary，而且在改变为 Name Dictionary 之后，对象原来的 Inline Property 的空间会被回收（这一块还没有搞清楚原因，因为使用 ObjectCreate 来实现对象的 Maps 的改变的时候，Inline Property 的内存空间并不会），这样就可以在这块空间上存放 Array。然后由于 V8 中的 IC 机制，对原来 Inline Property 的写入仍然会写入对应的偏移处，这就可以更改 Array 的 length 字段，从而造成越界读写。之后使用越界读写实现地址泄漏，并借助 ArrayBuffer 实现任意内存读写即可。
在利用过程中还存在一些问题没有解决：
- 为什么使用 __defineGetter__ 定义属性（两次相同）之后对象的属性会变成 Name Dictionary 来存储，而且 Inline Property 的空间会被回收（因为使用 Object.create 来将对象的属性变成 Name Dictionary 来存储的时候，Inline Property 好像并不会被回收？）
- 一开始想直接使用 Type Confusion 来实现 addr_of 原语和 fake_obj 原语（类似 CVE-2018-17463 的利用方法），但是 addr_of 只有第一次调用可以，在之后调用 addr_of 的时候就会发生去优化，而且是在第一次访问属性时发生的（即还没有对类的 Map 进行更改）。