一个两字节patch导致的off-by-one,最终造成类型混淆,执行shellcode。
编译了一个d8程序用于验证和利用漏洞,相关附件下载

CheckBound优化流程

首先在原有的simplified-lowering阶段,CheckBound节点并不被消除,而是设置为kAbortOnOutOfBounds模式,并替换为CheckedUint32Bounds

void VisitCheckBounds(Node* node, SimplifiedLowering* lowering) {
    CheckParameters const& p = CheckParametersOf(node->op());
    Type const index_type = TypeOf(node->InputAt(0));
    Type const length_type = TypeOf(node->InputAt(1));
    if (length_type.Is(Type::Unsigned31())) {
      if (index_type.Is(Type::Integral32OrMinusZero())) {
        // Map -0 to 0, and the values in the [-2^31,-1] range to the
        // [2^31,2^32-1] range, which will be considered out-of-bounds
        // as well, because the {length_type} is limited to Unsigned31.
        VisitBinop(node, UseInfo::TruncatingWord32(),
                   MachineRepresentation::kWord32);
        if (lower()) {
          CheckBoundsParameters::Mode mode =
              CheckBoundsParameters::kDeoptOnOutOfBounds;
          if (lowering->poisoning_level_ ==
                  PoisoningMitigationLevel::kDontPoison &&
              (index_type.IsNone() || length_type.IsNone() ||
               (index_type.Min() >= 0.0 &&
                index_type.Max() < length_type.Min()))) {
            // The bounds check is redundant if we already know that
            // the index is within the bounds of [0.0, length[.
            mode = CheckBoundsParameters::kAbortOnOutOfBounds;
          }
          NodeProperties::ChangeOp(
              node, simplified()->CheckedUint32Bounds(p.feedback(), mode));
        }
      }

而在此之前,该位置如下,可见原先利用节点消除的漏洞利用方法不能使用了。

if (lower()) {
          if (lowering->poisoning_level_ ==
                  PoisoningMitigationLevel::kDontPoison &&
              (index_type.IsNone() || length_type.IsNone() ||
               (index_type.Min() >= 0.0 &&
                index_type.Max() < length_type.Min()))) {
            // The bounds check is redundant if we already know that
            // the index is within the bounds of [0.0, length[.
            DeferReplacement(node, node->InputAt(0));
          } else {
            NodeProperties::ChangeOp(
                node, simplified()->CheckedUint32Bounds(p.feedback()));
          }
        }

Effect linearization阶段,CheckedUint32Bounds节点会被优化成Uint32LessThan,并绑定上其TrueFalse分支。

Node* EffectControlLinearizer::LowerCheckedUint32Bounds(Node* node,
                                                        Node* frame_state) {
  Node* index = node->InputAt(0);
  Node* limit = node->InputAt(1);
  const CheckBoundsParameters& params = CheckBoundsParametersOf(node->op());

  Node* check = __ Uint32LessThan(index, limit);
  switch (params.mode()) {
    case CheckBoundsParameters::kDeoptOnOutOfBounds:
      __ DeoptimizeIfNot(DeoptimizeReason::kOutOfBounds,
                         params.check_parameters().feedback(), check,
                         frame_state, IsSafetyCheck::kCriticalSafetyCheck);
      break;
    case CheckBoundsParameters::kAbortOnOutOfBounds: {
      auto if_abort = __ MakeDeferredLabel();
      auto done = __ MakeLabel();

      __ Branch(check, &done, &if_abort);

      __ Bind(&if_abort);
      __ Unreachable();
      __ Goto(&done);

      __ Bind(&done);
      break;
    }
  }

  return index;
}

而在lateoptimize阶段,将其优化为左值<右值这个表达式,即一个永真或者永假条件。

// Perform constant folding and strength reduction on machine operators.
Reduction MachineOperatorReducer::Reduce(Node* node) {
  switch (node->opcode()) {
// [...]
    case IrOpcode::kUint32LessThan: {
      Uint32BinopMatcher m(node);
      if (m.left().Is(kMaxUInt32)) return ReplaceBool(false);  // M < x => false
      if (m.right().Is(0)) return ReplaceBool(false);          // x < 0 => false
      if (m.IsFoldable()) {                                    // K < K => K
        return ReplaceBool(m.left().Value() < m.right().Value());
      }
      if (m.LeftEqualsRight()) return ReplaceBool(false);  // x < x => false
      if (m.left().IsWord32Sar() && m.right().HasValue()) {
        Int32BinopMatcher mleft(m.left().node());
        if (mleft.right().HasValue()) {
          // (x >> K) < C => x < (C << K)
          // when C < (M >> K)
          const uint32_t c = m.right().Value();
          const uint32_t k = mleft.right().Value() & 0x1F;
          if (c < static_cast<uint32_t>(kMaxInt >> k)) {
            node->ReplaceInput(0, mleft.left().node());
            node->ReplaceInput(1, Uint32Constant(c << k));
            return Changed(node);
          }
          // TODO(turbofan): else the comparison is always true.
        }
      }
      break;
    }

此后,另一个分支就变成了一个不可达的分支,最终在brancheliminate中被剪掉,达到和早期未patch版本同样的目的,但要求多了很多。

题目分析

而从题目来看,题目只patch了两个字符,就是在上面

return ReplaceBool(m.left().Value() < m.right().Value());

改为了

return ReplaceBool(m.left().Value() < m.right().Value() + 1);

这样的话,就算达到访问一个element的下一个节点,这个checkBound也会被优化掉,从而有个off-by-one,如果能达到这一点,就和*ctf 2019oob这题一模一样了,但那题的实现是增加了一个builtin函数,不需要利用优化,而此题需要在优化的前提下才能用,而且必须使CheckBound达到上述代码的位置。

测试样例分析

测试代码:

var opt_me2 = () => {
  let arr = [1,2,3,4];
  index = 4;
  return arr[index];
};
for (var i = 0; i < 0x10000; ++i)
  opt_me2();

可以发现使用上述测试样例并不能触发OOB,其原因也十分有趣,同样来源于优化过程。

首先通过--trace-turbo对优化过程的IR进行记录,发现在LoopPeeling阶段,44节点是一个值比较结点,而47结点是从element中读取数据,也就是实际执行arr[index]的这个节点。


但在下一阶段loadelimination中,比较4447两个节点都消失了,最终结果将返回2结点(undefined)。


可以查看一下loadelimination都做了什么,从源码中可以看到主要以AddReducer方法添加了10个reducer

void Run(PipelineData* data, Zone* temp_zone) {
    GraphReducer graph_reducer(temp_zone, data->graph(),
                               &data->info()->tick_counter(),
                               data->jsgraph()->Dead());
    BranchElimination branch_condition_elimination(&graph_reducer,
                                                   data->jsgraph(), temp_zone);
    DeadCodeElimination dead_code_elimination(&graph_reducer, data->graph(),
                                              data->common(), temp_zone);
    RedundancyElimination redundancy_elimination(&graph_reducer, temp_zone);
    LoadElimination load_elimination(&graph_reducer, data->jsgraph(),
                                     temp_zone);
    CheckpointElimination checkpoint_elimination(&graph_reducer);
    ValueNumberingReducer value_numbering(temp_zone, data->graph()->zone());
    CommonOperatorReducer common_reducer(&graph_reducer, data->graph(),
                                         data->broker(), data->common(),
                                         data->machine(), temp_zone);
    TypedOptimization typed_optimization(&graph_reducer, data->dependencies(),
                                         data->jsgraph(), data->broker());
    ConstantFoldingReducer constant_folding_reducer(
        &graph_reducer, data->jsgraph(), data->broker());
    TypeNarrowingReducer type_narrowing_reducer(&graph_reducer, data->jsgraph(),
                                                data->broker());
    AddReducer(data, &graph_reducer, &branch_condition_elimination);
    AddReducer(data, &graph_reducer, &dead_code_elimination);
    AddReducer(data, &graph_reducer, &redundancy_elimination);
    AddReducer(data, &graph_reducer, &load_elimination);
    AddReducer(data, &graph_reducer, &type_narrowing_reducer);
    AddReducer(data, &graph_reducer, &constant_folding_reducer);
    AddReducer(data, &graph_reducer, &typed_optimization);
    AddReducer(data, &graph_reducer, &checkpoint_elimination);
    AddReducer(data, &graph_reducer, &common_reducer);
    AddReducer(data, &graph_reducer, &value_numbering);
    graph_reducer.ReduceGraph();
  }

而在graph_reducer.ReduceGraph中将分别对每个节点调用上述添加的10个*::Reduce()方法。

Reduction GraphReducer::Reduce(Node* const node) {
  auto skip = reducers_.end();
  for (auto i = reducers_.begin(); i != reducers_.end();) {
    if (i != skip) {
      tick_counter_->DoTick();
      Reduction reduction = (*i)->Reduce(node);
      if (!reduction.Changed()) {
        // No change from this reducer.
      } else if (reduction.replacement() == node) {
        // {replacement} == {node} represents an in-place reduction. Rerun
        // all the other reducers for this node, as now there may be more
        // opportunities for reduction.
        if (FLAG_trace_turbo_reduction) {
          StdoutStream{} << "- In-place update of " << *node << " by reducer "
                         << (*i)->reducer_name() << std::endl;
        }
        skip = i;
        i = reducers_.begin();
        continue;
      } else {
        // {node} was replaced by another node.
        if (FLAG_trace_turbo_reduction) {
          StdoutStream{} << "- Replacement of " << *node << " with "
                         << *(reduction.replacement()) << " by reducer "
                         << (*i)->reducer_name() << std::endl;
        }
        return reduction;
      }
    }
    ++i;
  }
  if (skip == reducers_.end()) {
    // No change from any reducer.
    return Reducer::NoChange();
  }
  // At least one reducer did some in-place reduction.
  return Reducer::Changed(node);
}

使用trace-turbo-reduction对节点的修改和替换细节进行分析,可以发现在如下部分,首先是NumberLessThan(43, 16)内容被TypeNarrowingReducer更新,然后被ConstantFoldingReducer替换成HeapConstant固定值false,最终导致45节点True的分支变成不可达的节点,最终被DeadCodeElimination清理掉,造成没有触发OOB

- In-place update of 44: NumberLessThan(43, 16) by reducer TypeNarrowingReducer
- Replacement of 44: NumberLessThan(43, 16) with 55: HeapConstant[0x210c2b740709 <false>] by reducer ConstantFoldingReducer
- In-place update of 45: Branch[True|CriticalSafetyCheck](55, 12) by reducer BranchElimination
- Replacement of 45: Branch[True|CriticalSafetyCheck](55, 12) with 70: Dead by reducer CommonOperatorReducer
- Replacement of 47: LoadElement[tagged base, 16, Signed32, kRepTaggedSigned|kTypeInt32, FullWriteBarrier](59, 43, 43, 70) with 70: Dead by reducer DeadCodeElimination

首先跟踪TypeNarrowingReducer,可以看到当opcodekNumberLessThan时,如果左节点的最小值大于右节点的最大值时,类型会被op_typer_.singleton_false();,是一个HeapConstant

Reduction TypeNarrowingReducer::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;

  Type new_type = Type::Any();

  switch (node->opcode()) {
    case IrOpcode::kNumberLessThan: {
      // TODO(turbofan) Reuse the logic from typer.cc (by integrating relational
      // comparisons with the operation typer).
      Type left_type = NodeProperties::GetType(node->InputAt(0));
      Type right_type = NodeProperties::GetType(node->InputAt(1));
      if (left_type.Is(Type::PlainNumber()) &&
          right_type.Is(Type::PlainNumber())) {
        if (left_type.Max() < right_type.Min()) {
          new_type = op_typer_.singleton_true();
        } else if (left_type.Min() >= right_type.Max()) {
          new_type = op_typer_.singleton_false();
        }
      }
      break;
    }
 //[...]         
  Type original_type = NodeProperties::GetType(node);
  Type restricted = Type::Intersect(new_type, original_type, zone());
  if (!original_type.Is(restricted)) {
    NodeProperties::SetType(node, restricted);
    return Changed(node);
  }
  return NoChange();
}

从日志中可以发现其左节点是43,从IR可以发现其范围是[4,4],右节点是16 ,是一个常量值[4]

- Replacement of 41: LoadField[tagged base, 24, Range(0, 134217726), kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](68, 17, 12) with 16: NumberConstant[4] by reducer LoadElimination

因此,在ConstantFoldingReducer::Reduce中,44节点将被生成的一个HeapConstant节点替代。

Reduction ConstantFoldingReducer::Reduce(Node* node) {
  DisallowHeapAccess no_heap_access;
  // Check if the output type is a singleton.  In that case we already know the
  // result value and can simply replace the node if it's eliminable.
  if (!NodeProperties::IsConstant(node) && NodeProperties::IsTyped(node) &&
      node->op()->HasProperty(Operator::kEliminatable)) {
    // TODO(v8:5303): We must not eliminate FinishRegion here. This special
    // case can be removed once we have separate operators for value and
    // effect regions.
    if (node->opcode() == IrOpcode::kFinishRegion) return NoChange();
    // We can only constant-fold nodes here, that are known to not cause any
    // side-effect, may it be a JavaScript observable side-effect or a possible
    // eager deoptimization exit (i.e. {node} has an operator that doesn't have
    // the Operator::kNoDeopt property).
    Type upper = NodeProperties::GetType(node);
    if (!upper.IsNone()) {
      Node* replacement = nullptr;
      if (upper.IsHeapConstant()) {
        replacement = jsgraph()->Constant(upper.AsHeapConstant()->Ref());
 //[...]         
      if (replacement) {
        // Make sure the node has a type.
        if (!NodeProperties::IsTyped(replacement)) {
          NodeProperties::SetType(replacement, upper);
        }
        ReplaceWithValue(node, replacement);
        return Changed(replacement);
      }
    }
  }
  return NoChange();
}

因此,想要触发OOB必须规避掉以上路径。可以从43节点和16节点两方面考虑。首先说16节点,其来自于41节点的优化

- In-place update of 41: LoadField[tagged base, 24, Range(0, 134217726), kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](68, 17, 12) by reducer RedundancyElimination
- Replacement of 41: LoadField[tagged base, 24, Range(0, 134217726), kRepTaggedSigned|kTypeInt32, NoWriteBarrier, mutable](68, 17, 12) with 16: NumberConstant[4] by reducer LoadElimination
点击收藏 | 0 关注 | 1
  • 动动手指,沙发就是你的了!
登录 后跟帖