Security Bug

Important: Please do not change the component of this bug manually.

Please READ THIS FAQ before filing a bug: https://chromium.googlesource.com/chromium/src/+/HEAD/docs/security/faq.md

Please see the following link for instructions on filing security bugs: https://www.chromium.org/Home/chromium-security/reporting-security-bugs

Reports may be eligible for reward payments under the Chrome VRP: https://g.co/chrome/vrp

NOTE: Security bugs are normally made public once a fix has been widely deployed.

VULNERABILITY DETAILS

1 Maglev Graph Build

During optimization, the Graph constructed by Maglev based on bytecode is roughly as follows, and I have annotated the corresponding JS code for each part in the graph.

After graph building
    ...
    Block b2 
     14: ReduceInterruptBudgetForLoop(13)  
         ↳ lazy @22 (4 live vars)
     16: Jump b3
      │  with gap moves:
      │    - n17:(x) → 19: φᵀ r0 (x)
      │    - n18:(x) → 20: φᵀ r3 (x)
      ▼
╭──►Block b3 peeled (effects:)    // for (let i = 0; i < 5; i++) {
│    19: φᵀ r0 (n17, n30) (compressed) → (x), 21 uses
│    20: φᵀ r3 (n18, n31) (compressed) → (x), 2 uses 
│    21: CheckedSmiUntag [n20:(x)] → (x), 3 uses
│    22: Int32Compare(LessThan) [n21:(x), n10:(x)] → (x), 0 uses 🪦 
│╭───23: BranchIfInt32Compare(LessThan) [n21:(x), n10:(x)] b4 b5
││    ↓
││  Block b4     // loop body
││   25: CheckedSmiUntag [n19:(x)] → (x), 1 uses 
││   26: Int32DecrementWithOverflow [n25:(x)] → (x), 2 uses // v3--
││   27: Int32IncrementWithOverflow [n21:(x)] → (x), 2 uses 
││   28: ReduceInterruptBudgetForLoop(13) 
││   30: Int32ToNumber [n26:(x)] → (x), 1 uses
││   31: Int32ToNumber [n27:(x)] → (x), 1 uses
╰──◄─29: JumpLoop b3
 │       with gap moves:
 │         - n30:(x) → 19: φᵀ r0 (x)
 │         - n31:(x) → 20: φᵀ r3 (x)
 │ 
 ╰─►Block b5
        // use_v3 = v3; 
     32: LoadTaggedFieldForContextSlot(0x14, compressed) [n3:(x)] → (x), 1 uses
     33: ThrowReferenceErrorIfHole [n32:(x)] 
     34: CheckSmi [n19:(x)]
     35: StoreTaggedFieldNoWriteBarrier(0x14) [n3:(x), n19:(x)] 
        // Reflect.apply();
     40: 🐢 CallKnownJSFunction(0x09b10025d6a9 <SharedFunctionInfo apply>) [n38:(x), n39:(x), n37:(x), n4:(x)] → (x), 0 uses, but required
╭────41: Jump b7
│        with gap moves:
│          - n36:(x) → 56: φᵀ r1 (x)
│  
│   Block b6 (exception handler)
│    42: φᵀₑ <accumulator> (compressed) → (x), 1 uses
│    ...
│    55: Jump b7
│     │  with gap moves:
│     │    - n36:(x) → 56: φᵀ r1 (x)
│     ▼
╰┬─►Block b7 (effects: ua)    // the body of the do-while loop
 │   56: φᵀ r1 (n36, n36, n19) (compressed) → (x), 1 uses     // This phi node represents v15 and v3
 │   58: 🐢 CallBuiltin(KeyedStoreIC_Megamorphic) [n57:(x), n56:(x), n18:(x), n3:(x)] → (x), 0 uses, but required 
 │   61: ReduceInterruptBudgetForLoop(7) 
 │   62: Jump b8
 │    │  with gap moves:
 │    │    - n63:(x) → 64: φᵀ r2 (x)
 │    ▼
 │╭►Block b8 peeled (effects:)    // empty loop: for (let i40 = 100; i40; --i40) {}
 ││  64: φᵀ r2 (n63, n70) (compressed) → (x), 3 uses 
 ││╭──65: BranchIfToBooleanTrue [n64:(x)] b9 b10
 │││   ↓
 │││ Block b9 
 │││  66: CheckedSmiUntag [n64:(x)] → (x), 1 uses
 │││  67: Int32DecrementWithOverflow [n66:(x)] → (x), 2 uses 
 │││  68: ReduceInterruptBudgetForLoop(7) 
 │╰─◄─69: JumpLoop b8
 │ │      with gap moves:
 │ │        - n70:(x) → 64: φᵀ r2 (x)
 │ │
 │ ╰►Block b10
 │╭───71: BranchIfReferenceEqual [n19:(x), n8:(x)] b12 b11    // Determine whether the do-while loop should continue
 ││    ↓
 ││  Block b11
 ││   72: ReduceInterruptBudgetForLoop(27) 
 ╰──◄─73: JumpLoop b7    // backedge for do-while loop
  │       with gap moves:
  │         - n19:(x) → 56: φᵀ r1 (x)
  │ 
  ╰─►Block b12
    ...

The above Maglev Graph can be represented as the following CFG.

    B3 <--+    // for (let i = 0; i < 5; i++) { ... }
    |\    |  
    | +-->B4 
    |
    V
    B5        B6 (exception handler)    // try-catch
    |         |
    +---------+
        |
        V
   +--> B7    // do { ... }while();
   |    |
   |    V
   |    B8<---+    // for (let i40 = 100; i40; --i40) { }
   |    |\    |
   |    | +->B9
   |    V  
   |    B10
   |    |
   |    V
   +----B11

We need to pay special attention to 56: φᵀ r1 (n36, n36, n19) node in B7, this special Phi has three input nodes.

2 Maglev Phi Untagging

MaglevPhiRepresentationSelector::PreProcessBasicBlock() is applied to every BasicBlock in the Maglev Graph, and the function is as follows.

BlockProcessResult MaglevPhiRepresentationSelector::PreProcessBasicBlock(
    BasicBlock* block) {
  // Previously processing current_block_, now preparing to handle block
  PreparePhiTaggings(current_block_, block);
  current_block_ = block;

  if (block->has_phi()) {  
    auto& phis = *block->phis();

    auto first_retry = phis.begin();
    auto end_retry = first_retry;
    bool any_change = false;

    for (auto it = phis.begin(); it != phis.end(); ++it) { 
      Phi* phi = *it;
      switch (ProcessPhi(phi)) {   // Optimizing the type of phi node
        ...
      }
    }
    ...
  }

  return BlockProcessResult::kContinue;
}

The crash occurs during the process of PreProcessBasicBlock() handling B7.

We need to pay attention to two functions within it: PreparePhiTaggings() and ProcessPhi().

3 Add elements to merge_values_

1. MaglevPhiRepresentationSelector::PreparePhiTaggings()

void MaglevPhiRepresentationSelector::PreparePhiTaggings(
    BasicBlock* old_block, const BasicBlock* new_block) {
  ...
  // Clear the predecessor list
  predecessors_.clear();

  if (!new_block->is_merge_block()) {    // If it's not a merge block, this block only has one predecessor
    BasicBlock* pred = new_block->predecessor();    // Get the predecessor of this block
    predecessors_.push_back(pred->snapshot());    // Put it into predecessors_
  } else {    // If it's a merge block, the merge block must have multiple predecessors (such as back edge or merge edge of if)
    int skip_backedge = new_block->is_loop();    // Determine if it is a loop
    for (int i = 0; i < new_block->predecessor_count() - skip_backedge; i++) {
      BasicBlock* pred = new_block->predecessor_at(i);    // Get the predecessor of new_block
      predecessors_.push_back(pred->snapshot());    // Only two elements will be placed in predecessors_
    }
  }
  ...

  // Start a new snapshot based on predecessors_ 
  phi_taggings_.StartNewSnapshot(base::VectorOf(predecessors_), merge_taggings);
}

This function collects predecessor nodes other than LoopJump. B7 has three predecessor BasicBlocks: B5, B6, B11. Among them, B11 is LoopJump, which will be skipped, so the predecessors_ = {B5->snapshot(), B6->snapshot()} is passed into StartNewSnapshot() (later written as B5->snapshot() as S5, the rest is the same).

Debugging found that since B6 has no input nodes, S6 = root_snapshot_. The SnapshotTable at this time is as follows.

    root_snapshot_, S6, log: [0, 0)
            |
           /
          /
         /
       S5, log: [0, 1) 

2. SnapshotTable::StartNewSnapshot() will call two functions for processing.

template <class Value, class KeyData = NoKeyData>
class SnapshotTable {
  void StartNewSnapshot(base::Vector<const Snapshot> predecessors,
                        const MergeFun& merge_fun,
                        const ChangeCallback& change_callback = {}) {
    StartNewSnapshot(predecessors, change_callback);
    MergePredecessors(predecessors, merge_fun, change_callback);
  }
}

3. StartNewSnapshot() will find the nearest common ancestor node of {S5, S6}, which is root_snapshot_, and then create S7 with root_snapshot_ as the parent node. The SnapshotTable is as follows.

    root_snapshot_, S6, log: [0, 0)
            |        |
           /          \
          /            \
         /              \
       S5, log: [0, 1)   \
                        S7, log: [1, Invaild)

4. MergePredecessors()

template <class Value, class KeyData>
template <class MergeFun, class ChangeCallback>
void SnapshotTable<Value, KeyData>::MergePredecessors(
    base::Vector<const Snapshot> predecessors, const MergeFun& merge_fun,
    const ChangeCallback& change_callback) {
  ...

  SnapshotData* common_ancestor = current_snapshot_->parent;    // root_snapshot_

  for (uint32_t i = 0; i < predecessor_count; ++i) {
    for (SnapshotData* predecessor = predecessors[i].data_; 
         predecessor != common_ancestor; predecessor = predecessor->parent) { 
      base::Vector<LogEntry> log_entries = LogEntries(predecessor);
      for (const LogEntry& entry : base::Reversed(log_entries)) {
        RecordMergeValue(entry.table_entry, entry.new_value, i,
                         predecessor_count);
      }
    }
  }
  ...
}

This method will traverse the LogEntry of SnapshotData between [predecessor, common_ancestor). In this case,

• For S5, it will access [S5, root_snapshot_), which is the LogEntry in S5, and then call RecordMergeValue() for processing.
• For S6, [S6, root_snapshot_) is empty.

    root_snapshot_, S6, log: [0, 0)    <== common_ancestor
            |        |
           /          \
          /            \
         /              \
       S5, log: [0, 1)   \
                        S7, log: [1, Invaild)    <== current_snapshot_

5. RecordMergeValue()

template <class Value, class KeyData>
void SnapshotTable<Value, KeyData>::RecordMergeValue(
    TableEntry& entry,  
    const Value& value, 
    uint32_t predecessor_index,    // 0
    uint32_t predecessor_count    // 2
) {

  if (predecessor_index == entry.last_merged_predecessor) {
    ...
  }

  if (entry.merge_offset == kNoMergeOffset) { 
    // Reserve predecessor_count elements in merge_values_
    entry.merge_offset = static_cast<uint32_t>(merge_values_.size());
    merging_entries_.push_back(&entry);
    merge_values_.insert(merge_values_.end(), predecessor_count, entry.value);
  }

  merge_values_[entry.merge_offset + predecessor_index] = value;
  entry.last_merged_predecessor = predecessor_index;
}

Note: When RecordMergeValue() processes the LogEntry in S5, predecessor_index = 0, and predecessor_count = 2. Therefore, merge_values_.insert() will insert two slots in the array.

4 Access merge_values_

Then, it will enter the ProcessPhi() method to optimize phi. The crash occurs when ProcessPhi() handles 56: φᵀ r1 (n36, n36, n19) in B7.

By adding the --trace-maglev-phi-untagging option, you can see that before optimizing n56, its input phi node n19: phi will be optimized to the Int32 type by ProcessPhi().

Considering for untagging: n19
  + use_reprs  : {Int32}
  + input_reprs: {Int32}
  + intersection reprs: {Int32}
  => Untagging to Int32
    @ Input 0 (n17): Making Int32 instead of Smi
    @ Input 1 (n30): Bypassing conversion
...

Considering for untagging: n56
  + use_reprs  : {Tagged}
  + input_reprs: {Int32, Float64}
  => Leaving tagged [incompatible uses]

1. ProcessPhi()

MaglevPhiRepresentationSelector::ProcessPhiResult
MaglevPhiRepresentationSelector::ProcessPhi(Phi* node) {
  ...
  ValueRepresentationSet input_reprs;   
  ...
  bool has_tagged_phi_input = false;   
  for (int i = 0; i < node->input_count(); i++) {  
    ValueNode* input = node->input(i).node();
    if (input->Is<SmiConstant>()) {   
      ...
    } else if (Constant* constant = input->TryCast<Constant>()) { 
      ...
    } else if (input->properties().is_conversion()) {  
      ...
    } else if (Phi* input_phi = input->TryCast<Phi>()) {   
      ...
    } else { 
      ...  
      // If the input is tagged, and it is not required to perform tagging operations to become tagged
      // Then we will not perform hosit operations, nor will we carry out untag optimizations
      input_reprs.RemoveAll();
      break;
    }
  }

  // Get the usage information of phi
  UseRepresentationSet use_reprs;
  if (node->is_loop_phi() && !node->get_same_loop_uses_repr_hints().empty()) {
    // {node} is a loop phi that has uses inside the loop; we will tag/untag
    // based on those uses, ignoring uses after the loop.
    use_reprs = node->get_same_loop_uses_repr_hints();
  } else {
    use_reprs = node->get_uses_repr_hints();
  }
  ...
  
  if (use_reprs.contains(UseRepresentation::kTagged) ||
      use_reprs.contains(UseRepresentation::kUint32) || use_reprs.empty()) {
    // For phi nodes used as tagged types, we will not perform untagged operations
    TRACE_UNTAGGING("  => Leaving tagged [incompatible uses]");
    EnsurePhiInputsTagged(node);
    return default_result;
  }
  ...
}

ProcessPhi() first calculates two sets of types:

• input_reprs: The representation of the input nodes of phi. The input node n36 of n56 is of Int32 type, and n19 is also a phi node, but it has been optimized to Float64 type. So for n56, input_reprs={Int32, Float64}.
• use_reprs: The value of phi will be used as what type. In this case, the value of n56 will only be used as tagged.

Since the value of n56 is used as a tagged type, ProcessPhi() gives up the optimization for this node, calls EnsurePhiInputsTagged() to ensure that all input nodes of n56 are tagged, and then exits.

2. EnsurePhiInputsTagged()

void MaglevPhiRepresentationSelector::EnsurePhiInputsTagged(Phi* phi) { 
  for (int i = 0; i < phi->input_count(); i++) {    // Traverse all inputs of Phi
    ValueNode* input = phi->input(i).node();    // Get the input node  
    if (Phi* phi_input = input->TryCast<Phi>()) {    // If it is a phi node
      phi->change_input(    // Perform tagging operation for this input phi node
          i, EnsurePhiTagged(phi_input, phi->predecessor_at(i),
                             NewNodePosition::kEndOfBlock, nullptr, i));
    } else {
      ...
    }
  }
}

EnsurePhiInputsTagged() traverses the phi nodes in the input nodes of n56, that is, n19, and calls EnsurePhiTagged() to ensure that the value of the phi node n19 is tagged.

Note: n19 is the third input node of n56, so the predecessor_index parameter passed into EnsurePhiTagged() is 2.

3. EnsurePhiTagged()

ValueNode* MaglevPhiRepresentationSelector::EnsurePhiTagged(
    Phi* phi,     // n19
    BasicBlock* block, 
    NewNodePosition pos,
    const ProcessingState* state, 
    std::optional<int> predecessor_index    // 2
  ) {
  ...

  // Try to find an existing Tagged conversion for {phi} in {phi_taggings_}.
  if (phi->has_key()) {
    if (predecessor_index.has_value()) {    // 2
      if (ValueNode* tagging = phi_taggings_.GetPredecessorValue(    // <==
              phi->key(), predecessor_index.value())) {
        return tagging;
      }
    } else {
      if (ValueNode* tagging = phi_taggings_.Get(phi->key())) {
        return tagging;
      }
    }
  }
  ...
}

EnsurePhiTagged() first calls phi_taggings_.GetPredecessorValue() to query whether the untagged phi node n19 has been tagged before. If it has, it gets the node and directly returns it.

4. GetPredecessorValue()

template <class Value, class KeyData = NoKeyData>
class SnapshotTable {
  ...
  const Value& GetPredecessorValue(Key key, int predecessor_index) {
    if (key.entry_->merge_offset == kNoMergeOffset)  return Get(key);
    return merge_values_[key.entry_->merge_offset + predecessor_index];
  }
}

Finally, we’ve arrived at the point where an array out-of-bounds error occurs. The SnapshotTable::RecordMergeValue() method inserts two elements into merge_values_. However, when querying, key.entry_->merge_offset=0, predecessor_index = 2, so it will access merge_values_[2], leading to an array out-of-bounds error.

This out-of-bounds range might lead to the construction of an incorrect Maglev Graph in the phi untagging, which is a complex vulnerability. I’m not sure if it can be exploited.

5 Commit Bisect

After analyzing the source code, I am confident that this vulnerability originates from commit: c3935610c0f95c93b48e5647ec59bf855df58c64.

This means that this vulnerability was introduced on 5/8/2023, at a time when the maglev compiler was not even enabled by default. I am surprised that this vulnerability has survived for so long.

VERSION

V8: from commit c3935610c0f95c93b48e5647ec59bf855df58c64 to the latest version.

REPRODUCTION CASE

poc.js:

let use_v3;
let obj = {};

function f1() {
  
    // Create a phi node and trigger the maglev untagged optimization
    let v3 = 5;
    for (let i = 0; i < 5; i++) {
        v3--;
    }
    use_v3 = v3;    // Prevent v3 from being deleted

    let v15 = 1.2;

    // The try statement and the catch statement each have a path that leads to do{...}while()
    try {
        Reflect.apply();    // Used to throw an exception
    } catch(e) {
    }

    // The BasicBlock corresponding to do{...}while() has three incoming edges: 
    // the try statement, the catch statement, and the loop's back edge
    do {
        obj[v15] = 1;   // tagged use of v3
        v15 = v3;
        for (let i40 = 100; i40; --i40) {
        }
    } while (v3);
}

%PrepareFunctionForOptimization(f1);
f1();
f1();
%OptimizeMaglevOnNextCall(f1);
f1();

Run the following with a debug-compiled version of V8:

./d8 \
    --allow-natives-syntax \
    ./poc.js

You will get the following crash:

#
# Fatal error in ../../src/zone/zone-containers.h, line 247
# Debug check failed: pos < size() (2 vs. 2).
#

CREDIT INFORMATION

Externally reported security bugs may appear in Chrome release notes. If this bug is included, how would you like to be credited? Reporter credit: 303f06e3