P-W-N

Analyzing CVE-2021-30513

Analyzing CVE-2021-30513

Blurb

Hello again, its been more than just a few months, I know. But I didnt have anything to write about really - Im not gonna pretend my input is any more valuable than the hundreds of cool blog posts already out there (except when i do ;) ).

Recently, i’ve been trying to understand as much about Turbofan as i can, specifically the typer and bugs relating to the typer. As a stepping stone to do this ive been looking through some older CVE’s - which is something i’d recommend anyone with a similar goal to do. The end goal of this being to find a bug through source review in either the typer OR in simplified-lowering phases.

Anyway - this will most likely be a very, very long blog post. It also requires a lil’ bit of background knowledge on turbofan and V8 (that means a fuckton). I’m just gonna link the standard blog posts:

(The last one is my fav). Now thats over with, lets look at the bug.

The bug

Lets start with the chrome bug report you can find the ccorrect checkout and extra details there.

In SpeculativeNumberMultiply, a |Signed32| type restriction is placed on the feedback type of the node if both inputs are of type |Signed32| and the type hint is |kSignedSmall| [1]. While this is guarded by the |LowerToCheckedInt32Mul| function, the function will not deopt if the truncation is set to |kIdentifyZero| [2]. In this case, the feedback type of the node will be set to |Signed32| and will not deopt even if it becomes -0.

Lets find the code being discussed - its inside the VisitNode function, which is inside simplified-lowering:

    case IrOpcode::kSpeculativeNumberMultiply: {
        // [...]

        // Try to use type feedback.
        NumberOperationHint hint = NumberOperationHintOf(node->op());
        Type input0_type = TypeOf(node->InputAt(0));
        Type input1_type = TypeOf(node->InputAt(1));

        // Handle the case when no int32 checks on inputs are necessary
        // (but an overflow check is needed on the output).
        if (BothInputsAre(node, Type::Signed32())) {
          // If both inputs and feedback are int32, use the overflow op.
          if (hint == NumberOperationHint::kSignedSmall) {
            VisitBinop<T>(node, UseInfo::TruncatingWord32(),
                          MachineRepresentation::kWord32, Type::Signed32());
            if (lower<T>()) {
              // [1] Bug is in here
              LowerToCheckedInt32Mul(node, truncation, input0_type,
                                     input1_type);
            }
            return;
          }
        }
        
        // If both inputs not Signed32. But maybe one of them is? I imagine the bug could also be triggered from here.
        if (hint == NumberOperationHint::kSignedSmall) {
          VisitBinop<T>(node, CheckedUseInfoAsWord32FromHint(hint),
                        MachineRepresentation::kWord32, Type::Signed32());
          if (lower<T>()) {
            LowerToCheckedInt32Mul(node, truncation, input0_type, input1_type);
          }
          return;
        }
        // [...]
		return;
      }

Reaching the code

Firstly, the code is reached by generating a SpeculativeNumberMultiply node. How exactly is this done? Well generating a speculative node is actually the default for most (if not all) of the numerical bytecodes during the Graph Builder Phase:

  Node* TryBuildNumberBinop() {
    NumberOperationHint hint;
    if (GetBinaryNumberOperationHint(&hint)) {
      const Operator* op = SpeculativeNumberOp(hint);
      Node* node = BuildSpeculativeOperation(op);
      return node;
    }
    return nullptr;
  }

This function is then used to attempt construction of a speculative number node inside Js Type Hint lowering - but only if the type hint is correct (that is, the feedback is a numerical type, e.g SignedSmall):

    case IrOpcode::kJSBitwiseOr:
    case IrOpcode::kJSBitwiseXor:
    case IrOpcode::kJSBitwiseAnd:
    case IrOpcode::kJSShiftLeft:
    case IrOpcode::kJSShiftRight:
    case IrOpcode::kJSShiftRightLogical:
    case IrOpcode::kJSAdd:
    case IrOpcode::kJSSubtract:
    case IrOpcode::kJSMultiply:
    case IrOpcode::kJSDivide:
    case IrOpcode::kJSModulus: {
	  // [...]
      if (Node* node = b.TryBuildNumberBinop()) {
        return LoweringResult::SideEffectFree(node, node, control);
      }
      // [...]
      break;
    }

We can find the code which obtains this feedback and builds a basic multiply operation inside ignition:


TNode<Object> BinaryOpAssembler::Generate_MultiplyWithFeedback(
    const LazyNode<Context>& context, TNode<Object> lhs, TNode<Object> rhs,
    TNode<UintPtrT> slot_id, const LazyNode<HeapObject>& maybe_feedback_vector,
    UpdateFeedbackMode update_feedback_mode, bool rhs_known_smi) {
  auto smiFunction = [=](TNode<Smi> lhs, TNode<Smi> rhs,
                         TVariable<Smi>* var_type_feedback) {
    TNode<Number> result = SmiMul(lhs, rhs);
    *var_type_feedback = SelectSmiConstant(
        TaggedIsSmi(result), BinaryOperationFeedback::kSignedSmall,
        BinaryOperationFeedback::kNumber);
    return result;
  };
  // [...]
  return Generate_BinaryOperationWithFeedback( // <-------- [1]
      context, lhs, rhs, slot_id, maybe_feedback_vector, smiFunction,
      floatFunction, Operation::kMultiply, update_feedback_mode, rhs_known_smi);
}

Then at [1] we call into the function which will actually get the feedback for us:

TNode<Object> BinaryOpAssembler::Generate_BinaryOperationWithFeedback(
    const LazyNode<Context>& context, TNode<Object> lhs, TNode<Object> rhs,
    TNode<UintPtrT> slot_id, const LazyNode<HeapObject>& maybe_feedback_vector,
    const SmiOperation& smiOperation, const FloatOperation& floatOperation,
    Operation op, UpdateFeedbackMode update_feedback_mode, bool rhs_known_smi) {
  Label do_float_operation(this), end(this), call_stub(this),
      check_rhsisoddball(this, Label::kDeferred), call_with_any_feedback(this),
      if_lhsisnotnumber(this, Label::kDeferred),
      if_both_bigint(this, Label::kDeferred);
  TVARIABLE(Float64T, var_float_lhs);
  TVARIABLE(Float64T, var_float_rhs);
  TVARIABLE(Smi, var_type_feedback);
  TVARIABLE(Object, var_result);

  Label if_lhsissmi(this);
  // If rhs is known to be an Smi (in the SubSmi, MulSmi, DivSmi, ModSmi
  // bytecode handlers) we want to fast path Smi operation. For the normal
  // operation, we want to fast path both Smi and Number operations, so this
  // path should not be marked as Deferred.

  // [...]

  // Check if the {lhs} is a Smi or a HeapObject.
  BIND(&if_lhsissmi);
  {
    Comment("lhs is Smi");
    TNode<Smi> lhs_smi = CAST(lhs);
    if (!rhs_known_smi) {
	// [...]
      BIND(&if_rhsissmi);
    }

    {
      Comment("perform smi operation"); // [1]
      var_result = smiOperation(lhs_smi, CAST(rhs), &var_type_feedback);
      UpdateFeedback(var_type_feedback.value(), maybe_feedback_vector(),
                     slot_id, update_feedback_mode);
      Goto(&end);
    }
  }

The SignedSmall feedback is given only if the lhs and rhs of the multiplication are smi’s, in which case we call into the smiFunction (@ [1]) created in Generate_MultiplyWithFeedback. Nice.

Returning to SpeculativeNumberMultiply, there is one more thing we need to be aware of - typed optimization. Under certain circumstances after typing of nodes is complete, the next phase, (typed optimization) will attempt to lower our Speculative node to a simpler version with less overhead:

Reduction TypedOptimization::ReduceSpeculativeNumberBinop(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::NumberOrUndefinedOrNullOrBoolean())) {
    // We intentionally do this only in the Number and NumberOrOddball hint case
    // because simplified lowering of these speculative ops may do some clever
    // reductions in the other cases.
    Node* const toNum_lhs = ConvertPlainPrimitiveToNumber(lhs);
    Node* const toNum_rhs = ConvertPlainPrimitiveToNumber(rhs);
    Node* const value = graph()->NewNode(
        NumberOpFromSpeculativeNumberOp(simplified(), node->op()), toNum_lhs,
        toNum_rhs);
    ReplaceWithValue(node, value);
    return Replace(value);
  }
  return NoChange();
}

We can see here, that if our hint is NOT kNumber, then we can bypass the reduction of the node. Which thankfully will always be the case if we keep our hint == SignedSmall, and our inputs are not both NumberOrUndefinedOrNullOrBoolean.

If this and all the previous facts align, then we can enter the kSpeculativeNumberMultiply case in simplified-lowering. Good. Now lets take a look deeper.

Wheres the bug?

To enter the next bit of code and trigger the bug, both inputs to our node must be of type Signed32, and our feedback must be SignedSmall:

        NumberOperationHint hint = NumberOperationHintOf(node->op());
        Type input0_type = TypeOf(node->InputAt(0));
        Type input1_type = TypeOf(node->InputAt(1));

        // Handle the case when no int32 checks on inputs are necessary
        // (but an overflow check is needed on the output).
        if (BothInputsAre(node, Type::Signed32())) {
          // If both inputs and feedback are int32, use the overflow op.
          if (hint == NumberOperationHint::kSignedSmall) {
            VisitBinop<T>(node, UseInfo::TruncatingWord32(),
                          MachineRepresentation::kWord32, Type::Signed32());
            if (lower<T>()) {
              // [1] Bug is in here
              LowerToCheckedInt32Mul(node, truncation, input0_type,
                                     input1_type);
            }
            return;
          }
        }

If this is the case, we visit this node - and depending on what sub-phase we will do a few different things:

Simplified-lowering overview

This is stuff which is covered at length in Faraz’ blog post, so I wont discuss it much more - the one key takeaway is that the nodes type WILL adhere to the restriction type specified in the VisitBinop call (Signed32).

Moving on, if we are in the lowering phase (aka, the final phase of simplified-lowering) we enter the LowerToCheckedInt32Mul function:

  void LowerToCheckedInt32Mul(Node* node, Truncation truncation,
                              Type input0_type, Type input1_type) {
    // If one of the inputs is positive and/or truncation is being applied,
    // there is no need to return -0.
    // Read the above, basically if the truncation identifies -0 (rather than distinguishing it), we set the CheckForMinusZero to kDontCheckForMinusZero
    CheckForMinusZeroMode mz_mode =
        truncation.IdentifiesZeroAndMinusZero() ||
                IsSomePositiveOrderedNumber(input0_type) ||
                IsSomePositiveOrderedNumber(input1_type)
            ? CheckForMinusZeroMode::kDontCheckForMinusZero
            : CheckForMinusZeroMode::kCheckForMinusZero;
    ChangeOp(node, simplified()->CheckedInt32Mul(mz_mode));
  }

We can see that IF the node happens to have a truncation which IdentifiesZeroAndMinusZero, then we set the mz_mode to DontCheckForMinusZero, and pass this mode into new CheckedInt32Mul node which will replace our Speculative node.

Before I talk about this further, its probably best to mention the key difference between 0 and -0 in V8. 0 is a part of the Signed32 type, whereas -0 is entirely its own, and as such has some different behaviours.

Inside of a node’s truncation, the IdentifyZero’s can have 2 values:

enum IdentifyZeros { kIdentifyZeros, kDistinguishZeros };

The former, which we have already talked about is used to show when a node doesn’t need to care about differences between 0 and -0, as we can see inside the code responsible for lowering the CheckedInt32Mul node:


Node* EffectControlLinearizer::LowerCheckedInt32Mul(Node* node,
                                                    Node* frame_state) {
  CheckForMinusZeroMode mode = CheckMinusZeroModeOf(node->op());
  Node* lhs = node->InputAt(0);
  Node* rhs = node->InputAt(1);

  Node* projection = __ Int32MulWithOverflow(lhs, rhs);
  Node* check = __ Projection(1, projection);
  __ DeoptimizeIf(DeoptimizeReason::kOverflow, FeedbackSource(), check,
                  frame_state);

  Node* value = __ Projection(0, projection);

  if (mode == CheckForMinusZeroMode::kCheckForMinusZero) {
    auto if_zero = __ MakeDeferredLabel();
    auto check_done = __ MakeLabel();
    Node* zero = __ Int32Constant(0);
    Node* check_zero = __ Word32Equal(value, zero);
    __ GotoIf(check_zero, &if_zero);
    __ Goto(&check_done);

    __ Bind(&if_zero);
    // We may need to return negative zero.
    Node* check_or = __ Int32LessThan(__ Word32Or(lhs, rhs), zero);
    __ DeoptimizeIf(DeoptimizeReason::kMinusZero, FeedbackSource(), check_or,
                    frame_state);
    __ Goto(&check_done);

    __ Bind(&check_done);
  }

  return value;
}

We can see that if the CheckForMinusZeroMode is CheckForMinusZero (as it would be if we did end up with the IdentifyZero mode on our truncation), then we insert a deoptimize node which triggers should its output be -0.

This lack of checking is the bug, although it may be hard to understand at first. To this end, lets take a look at the patch, so we can understand why this is insufficient:

-  void LowerToCheckedInt32Mul(Node* node, Truncation truncation,
-                              Type input0_type, Type input1_type) {
-    // If one of the inputs is positive and/or truncation is being applied,
-    // there is no need to return -0.
-    CheckForMinusZeroMode mz_mode =
-        truncation.IdentifiesZeroAndMinusZero() ||
-                IsSomePositiveOrderedNumber(input0_type) ||
-                IsSomePositiveOrderedNumber(input1_type)
-            ? CheckForMinusZeroMode::kDontCheckForMinusZero
-            : CheckForMinusZeroMode::kCheckForMinusZero;
-    ChangeOp(node, simplified()->CheckedInt32Mul(mz_mode));
+  template <Phase T>
+  void VisitForCheckedInt32Mul(Node* node, Truncation truncation,
+                               Type input0_type, Type input1_type,
+                               UseInfo input_use) {
+    DCHECK_EQ(node->opcode(), IrOpcode::kSpeculativeNumberMultiply);
+    // A -0 input is impossible or will cause a deopt.
+    DCHECK(BothInputsAre(node, Type::Signed32()) ||
+           !input_use.truncation().IdentifiesZeroAndMinusZero());
+
+    CheckForMinusZeroMode mz_mode;
+    Type restriction;
+    if (IsSomePositiveOrderedNumber(input0_type) ||
+        IsSomePositiveOrderedNumber(input1_type)) {
+      mz_mode = CheckForMinusZeroMode::kDontCheckForMinusZero;
+      restriction = Type::Signed32();
+    } else if (truncation.IdentifiesZeroAndMinusZero()) {
+      mz_mode = CheckForMinusZeroMode::kDontCheckForMinusZero;
+      restriction = Type::Signed32OrMinusZero();
+    } else {
+      mz_mode = CheckForMinusZeroMode::kCheckForMinusZero;
+      restriction = Type::Signed32();
+    }
+
+    VisitBinop<T>(node, input_use, MachineRepresentation::kWord32, restriction);
+    if (lower<T>()) ChangeOp(node, simplified()->CheckedInt32Mul(mz_mode));
   }

Now it should hopefully be apparent what is wrong; just checking if the current node is given the IdentifiesZeroAndMinusZero truncation is not sufficient to ensure that the node cannot have an output of -0 (obviously).

So what can we do with this? Well, since our new node will NOT check/deoptimize for -0 if we give our SpeculativeNumberMultiply node a IdentifiesZeroAndMinusZero truncation, we may be able to confuse the output of said node - Minus Zero and Signed32 are 2 entirely non-compatible types, and as such one will not survive intersection with the other.

Like I said earlier our node output is restricted to Signed32, and as such should not be able to transition from this - but since it doesnt deoptimize, nothing is stopping us. To show this a little better, heres the representation output from turbofan during the Retype phase:

#57:SpeculativeNumberMultiply[SignedSmall](#15:NumberConstant, #42:Phi, #69:LoadField, #38:Merge)  [Static type: (MinusZero | Range(0, 0)), Feedback type: Range(0, 0)]
 visit #57: SpeculativeNumberMultiply
  ==> output kRepWord32

We can see that although the static type (this is the type computed by the actual typer phase, which will be the one displayed in turbolyzer) is correct, our feedback type (aka, the new type we just created during Retype) fails to include -0, owing to the intersection discussed earlier.

This of course begs the question - how does one give our node the required truncation? Some nodes will give this truncation to its inputs fairly readily. As discussed in the bug report, one such node is SpeculativeSafeIntegerAdd:

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

	// [...]
	Type left_constraint_type =
        node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd
            ? Type::Signed32OrMinusZero()
            : Type::Signed32();
    if (left_upper.Is(left_constraint_type) &&
        right_upper.Is(Type::Signed32OrMinusZero()) &&
        (left_upper.Is(Type::Signed32()) || right_upper.Is(Type::Signed32()))) {
      VisitBinop<T>(node, UseInfo::TruncatingWord32(),
                    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
      // right-hand side is not minus zero, we do not have to distinguish
      // between 0 and -0.
      IdentifyZeros left_identify_zeros = truncation.identify_zeros();
      if (node->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd &&
          !right_feedback_type.Maybe(Type::MinusZero())) {
        left_identify_zeros = kIdentifyZeros;
      }
      UseInfo left_use = CheckedUseInfoAsWord32FromHint(hint, FeedbackSource(),
                                                        left_identify_zeros);
      // For CheckedInt32Add and CheckedInt32Sub, we don't need to do
      // a minus zero check for the right hand side, since we already
      // know that the left hand side is a proper Signed32 value,
      // potentially guarded by a check.
      UseInfo right_use = CheckedUseInfoAsWord32FromHint(hint, FeedbackSource(),
                                                         kIdentifyZeros);
      VisitBinop<T>(node, left_use, right_use, MachineRepresentation::kWord32,
                    restriction);
    }

    // [...]

    return;
  }

We want to enter the else branch, because as you see it is here where the correct truncations/UseInfo’s are given out. The right_use is automatically given the kIdentifyZero property, thus if our multiply node is on the right hand side, we can trigger our type confusion.

Putting the pieces together

Here is the POC listed on the bug report:

function foo(a) {
  var y = 1;
  var x = 0;
  var z = 0;
  if (a == NaN) z = NaN;
  if (a) {
    x = 0;
    y = -1;
    z = -0;
  }
  
  return Object.is(z + (x * y), -0);
}
console.log(foo(true));
%PrepareFunctionForOptimization(foo);
foo(false);
%OptimizeFunctionOnNextCall(foo);
foo(false);
console.log(foo(true));

Lets break it down piece by piece. First we have if (a == NaN) z = NaN;, this is so we can keep our SpeculativeSafeIntegerAdd node instead of just demoting to a regular NumberAdd node. If you scroll back up you can see this working in the ReduceSpeculativeNumberBinop function. This allows us to reach the correct code to pass on our truncation.

Next we add a switch so we can change the values on the fly, after this we trigger the bug. The graph for the equation looks something like this:


        ┌────────────────┐  ┌────────────────┐
        │Phi (-0 | 0)    │  │SpecNumMul      │
        └───────────────┬┘ ┌┴────────────────┘
                        │  │
                        │  │
                        │  │
                       ┌▼──▼────────────┐
                       │SpecSafeIntAdd  │
                       └────────────────┘

We can see our multiplication (x * y) on the right, if you remember from earlier this is the correct place for it to be to recieve the IdentifyZero truncation. On the other side is z which can be 0 OR -0. Taking another look at the representation output we can see:

#58:SpeculativeSafeIntegerAdd[SignedSmall](#43:Phi, #57:SpeculativeNumberMultiply, #57:SpeculativeNumberMultiply, #38:Merge)  [Static type: (MinusZero | Range(0, 0)), Feedback type: Range(0, 0)]
 visit #58: SpeculativeSafeIntegerAdd
  ==> output kRepWord32

Because of the incorrect feedback type generated by the multiply node, the output of the add node has also been confused, as it believes that the multiply can only produce 0, and -0 + 0 or 0 + 0 will always be zero… BUT not -0 + -0.

Exploitation

I tried a couple things, but haven’t yet found a way to exploit this - if you do have a method for this please reach out. If i end up finding a way, I’ll update this section.

There are a few ways you can differentiate between 0 and -0 which are relevant in a context like this, if you read the post linked at the beginning of the blog about Math.expm1 then you know they are:

Object.is being preferable, as the typing code for atan2 doesnt deal with -0. However I havent found a way to meaningfully use this assumption for anything. Maybe you can :).

Closing thoughts

It feels great to put something up which might help someone else in their pursuit of understanding, though im not gonna pretend if you did read and understand Faraz’ blog you wouldnt be able to do this all yourself. I learned alot from analyzing this bug, and I hope you did too.

And damn, some typer bugs are ALOT harder to exploit that others.

Happy hacking.