1. References and PoC

This bug was found by saelo(Thanks saelo for always being really great!).

https://bugs.chromium.org/p/project-zero/issues/detail?id=1775

https://github.com/WebKit/webkit/commit/62f770031bdb15b59041257e60ab93765d5ee6ca

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

2. the Crash

This bug crashes at “v8[-698666199]”, which corresponds to a dfg node GetByVal.

  • Before LICM phase, @70 GetByVal resides in Block#3, with a @137 CheckInBounds ahead of it.

  • After LICM, it resides in Block#1, with @137 CheckInBounds still in Block#3.

It means that @70 GetByVal is hoisted during LICM. So read operation happens before check. Thus crash happens.

3. the Patch & the Analysis

After implementing the patch, @70 GetByVal is never hoisted because of it won’t pass edgesDominate in DFGLICMPhase.cpp:

1
2
3
4
5
6
7
if (!edgesDominate(m_graph, node, data.preHeader)) {
	if (verbose) {
		dataLog(
			"    Not hoisting ", node, " because it isn't loop invariant.n");
	}
	return tryHoistChecks();
}

(jsc’s LICM does not strictly implement traditional fundamentals of compiling. It checks doesWrites, readsOverlap, safeToExecute and sort of things. It does not really rely on defs and uses but AbstractHeap.)

And here is the calling stack:

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
if (!edgesDominate(m_graph, node, data.preHeader)) {

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

    	->
            
        void DFGEdgeDominates::operator()(Node*, Edge edge)
        {
            bool result = m_graph.m_ssaDominators->dominates(edge.node()->owner, m_block); // It's operation between blocks
            if (verbose) {
                dataLog(
                    "Checking if ", edge, " in ", *edge.node()->owner,
                    " dominates ", *m_block, ": ", result, "n");
            }
            m_result &= result; //All node has to have a true as result.
        }

    		->
                
            bool dominates(typename Graph::Node from, typename Graph::Node to) const
            {
                return from == to || strictlyDominates(from, to);
            }
            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;
            }

So at function dominates,

  • the vuln version(the index are the blocks’):

    to 0 from 0

    to 0 from 0

    to 0 from 0

  • the fixed version:

    to 0 from 0

    to 0 from 0

    to 0 from 0

    to 0 from 3

    m_data[to].preNumber 0 m_data[from].preNumber 3

    m_data[to].postNumber 17 m_data[from].postNumber 0

That’s because an Edge is added in the Graph in the fixed version.

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
before LICM
Block #3 (bc#39):
Execution count: 10.000000
Predecessors: #2
Successors: #5
Dominated by: #0 #1 #2 #3
Dominates: #3
Dominance Frontier: #5
Iterated Dominance Frontier: #1 #5
States: StructuresAreWatched
Live: @2, @4, @22, @24, @26, @30, @33, @36, @63, @69, @75, @98, @159
Values: @2=>(Other, Undefined, 1:StructuresAreWatched), @4=>(None, none:StructuresAreClobbered), @22=>(Cell, ArrayWithInt32|CopyOnWriteArrayWithInt32, TOP, 1:StructuresAreWatched), @24=>(|Empty, 1:StructuresAreWatched), @26=>(Int32, 1:StructuresAreWatched), @30=>(Cell, TOP, TOP, 1:StructuresAreWatched), @33=>(Int32, 1:StructuresAreWatched), @36=>(BoolInt32, Int32: 0, 1:StructuresAreWatched), @63=>(NonBoolInt32, Int32: 42, 1:StructuresAreWatched), @69=>(NonBoolInt32, Int32: -698666199, 1:StructuresAreWatched), @75=>(BoolInt32, Int32: 1, 1:StructuresAreWatched), @98=>(Other, Null, 1:StructuresAreWatched), @159=>(Int32, 1:StructuresAreWatched)
85:<!0:-> ExitOK(MustGen, W:SideState, bc#39, ExitValid)
55:< 2:-> ToIndexString(KnownInt32:@26, JS|PureInt, String, Exits, bc#39, ExitValid)
89:<!0:-> KillStack(MustGen, loc12, W:Stack(-13), ClobbersExit, bc#39, ExitValid)
56:<!0:-> MovHint(Check:Untyped:@55, MustGen, loc12, W:SideState, ClobbersExit, bc#39, ExitInvalid)
90:<!0:-> KillStack(MustGen, loc7, W:Stack(-8), ClobbersExit, bc#42, ExitValid)
58:<!0:-> MovHint(Check:Untyped:Kill:@55, MustGen, loc7, W:SideState, ClobbersExit, bc#42, ExitInvalid)
93:<!0:-> KillStack(MustGen, loc14, W:Stack(-15), ClobbersExit, bc#45, ExitValid)
61:<!0:-> MovHint(Check:Untyped:@24, MustGen, loc14, W:SideState, ClobbersExit, bc#45, ExitInvalid)
65:<!0:-> FilterPutByIdStatus(Check:Untyped:@22, MustGen, (<Replace: [0x128cafbf0:[Array, {a:100}, ArrayWithInt32, Proto:0x128cf00c0, Leaf]], offset = 100, >), W:SideState, bc#48, ExitValid)
66:<!0:-> CheckStructure(Cell:@22, MustGen, [%Bv:Array], R:JSCell_structureID, Exits, bc#48, ExitValid)
68:<!0:-> PutByOffset(Check:Untyped:@4, KnownCell:@22, Check:Untyped:@63, MustGen, id0{a}, 100, W:NamedProperties(0), ClobbersExit, bc#48, ExitValid)

137:<!1:-> CheckInBounds(Int32:@69, KnownInt32:Kill:@159, JS|MustGen|PureInt, Int32, Exits, bc#54, ExitValid)

vuln:
70:<!1:-> GetByVal(KnownCell:@22, Int32:@69, Check:Untyped:Kill:@4, JS|MustGen|VarArgs|PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other

fixed:
70:<!1:-> GetByVal(KnownCell:@22(Block#0), Int32:@69(Block#0), Check:Untyped:Kill:@4(Block#0), Check:Untyped:Kill:@137(Block#3), JS|MustGen|VarArgs|PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other

97:<!0:-> KillStack(MustGen, loc14, W:Stack(-15), ClobbersExit, bc#54, ExitInvalid)
71:<!0:-> MovHint(Check:Untyped:Kill:@70, MustGen, loc14, W:SideState, ClobbersExit, bc#54, ExitInvalid)
73:<!0:-> Jump(MustGen, T:#5, W:SideState, bc#59, ExitValid)
States: InvalidBranchDirection, StructuresAreWatched
Live: @2, @22, @24, @26, @30, @33, @36, @63, @69, @75, @98
Values: @2=>(Other, Undefined, 1:StructuresAreWatched), @22=>(Array, ArrayWithInt32, [%Bv:Array], 1:StructuresAreWatched), @24=>(|Empty, 1:StructuresAreWatched), @26=>(Int32, 1:StructuresAreWatched), @30=>(Cell, TOP, TOP, 1:StructuresAreWatched), @33=>(Int32, 1:StructuresAreWatched), @36=>(BoolInt32, Int32: 0, 1:StructuresAreWatched), @63=>(NonBoolInt32, Int32: 42, 1:StructuresAreWatched), @69=>(NonBoolInt32, Int32: -698666199, 1:StructuresAreWatched), @75=>(BoolInt32, Int32: 1, 1:StructuresAreWatched), @98=>(Other, Null, 1:StructuresAreWatched)

So we could know that the core of the patch is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 @@ -135,9 +135,14 @@ class SSALoweringPhase : public Phase {
	        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;
	    }

(The HasIndexedProperty stuff has nothing to do with this bug. It is modified in the patch because in lowerBoundsCheck is modified in DFGSSALowingPhase.cpp because it relies on that function.)

So there is a first one condition that a node should meet if the node would be hoisted during LICM phase:

  • All of the nodes’ children should dominates the loop’s preheader.

In this case, Block#0 is definately loop’s preheader. And GetByVal has children:

  • base@22
  • index@69
  • storage@4

Those children all belong to Block#0. And the 4th child in the fixed version:

  • @137 CheckInBounds

What makes @137 CheckInBounds the 4th child of GetByVal is an artificial (because there isn’t actually any data dependency) dataflow edge between the CheckInBounds and the GetByVal.

So in the vuln verison, we have Block#0 not-strictly dominate Block#0, and in the vuln version Block#3 not dominate Block#0 which determines the existence of the vulnerability. Thus GetByVal can never be hoisted in front of the check.

(Thanks for saelo’s advice on emphasizing the artificial dataflow edge here. )

4. about CheckInBounds

@137 CheckInBounds is never hoisted. Because before LICM phase(the 42th phase) it is like:

1
137:<!0:->	CheckInBounds(Int32:@69, KnownInt32:Kill:@159, MustGen, Int32, Exits, bc#54, ExitValid)

And @69 resides in Block#0 and @159 resides in Block#2. And Block#2 does not dominate Block#0. So.

There is a @224 CheckInBounds inserted before @70 GetByVal during DFGSSALoweringPhase (the 25th phase):

1
2
224:<!0:->	CheckInBounds(Int32:@69, Check:KnownInt32:@256, JS|MustGen|PureInt, Int32, Exits, bc#54, ExitValid)
70:<!0:->	GetByVal(KnownCell:@303, Int32:@69, Check:Untyped:@67, Check:Untyped:@224, JS|MustGen|VarArgs|PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid)  predicting Other

And @224 CheckInBounds is then changed to @137 CheckInBounds during some modification on index of graph in DFGObjectAllocationSinkingPhase(DFG phase object allocation elimination):

1
2
137:<!1:->	CheckInBounds(Int32:@69, KnownInt32:Kill:@159, JS|MustGen|PureInt, Int32, Exits, bc#54, ExitValid)
70:<!1:->	GetByVal(KnownCell:@22, Int32:@69, Check:Untyped:Kill:@4, Check:Untyped:Kill:@137, JS|MustGen|VarArgs|PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid)  predicting Other
vuln fixed
25th phase: DFGSSALoweringPhase 224:<!0:-> CheckInBounds(Int32:@69, Check:KnownInt32:@256, MustGen, Int32, Exits, bc#54, ExitValid) 224:<!0:-> CheckInBounds(Int32:@69, Check:KnownInt32:@256, JSMustGenPureInt, Int32, Exits, bc#54, ExitValid)
70:<!0:-> GetByVal(KnownCell:@303, Int32:@69, Check:Untyped:@67, JSMustGen VarArgs PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other 70:<!0:-> GetByVal(KnownCell:@303, Int32:@69, Check:Untyped:@67, **Check:Untyped:@224**, JS MustGen VarArgs PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other
36th phase: DFGObjectAlloactionSinkingPhase 137:<!0:-> CheckInBounds(Int32:@69, KnownInt32:Kill:@159, MustGen, Int32, Exits, bc#54, ExitValid) 137:<!1:-> CheckInBounds(Int32:@69, KnownInt32:Kill:@159, JS MustGen PureInt, Int32, Exits, bc#54, ExitValid)
70:<!1:-> GetByVal(KnownCell:@22, Int32:@69, Check:Untyped:Kill:@4, JS MustGen VarArgs PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other 70:<!1:-> GetByVal(KnownCell:@22, Int32:@69, Check:Untyped:Kill:@4, **Check:Untyped:Kill:@137**, JS MustGen VarArgs PureInt, Int32, Int32+Array+InBounds+AsIs+Read, R:Butterfly_publicLength,IndexedInt32Properties, Exits, bc#54, ExitValid) predicting Other