How Quadratic CPU Consumption in !!omap Resolution Happens in js-yaml and How to Fix It

How Quadratic CPU Consumption in !!omap Resolution Happens in js-yaml and How to Fix It

Introduction

The bun.lock file in this project pinned js-yaml to version 4.3.0 — a version that harbors a subtle but dangerous algorithmic flaw in how it resolves the YAML !!omap (ordered map) tag. Unlike memory-corruption bugs or injection flaws, this vulnerability does not crash a process or leak data. Instead, it quietly consumes CPU cycles at a quadratic rate, turning a carefully crafted YAML document into a denial-of-service weapon. The issue is tracked as GHSA-5p4m-2wfm-xmqj and affects both the 3.x and 4.x release lines of js-yaml; the CVE-2026-59870 fix was not backported until the releases addressed in this patch.

For developers who use js-yaml to parse configuration files, API payloads, or any other user-supplied YAML, this is a direct path to service unavailability — no authentication required, no memory corruption needed, just a well-formed YAML document with a long !!omap block.

The Vulnerability Explained

What is !!omap?

YAML's !!omap tag represents an ordered mapping — a sequence of key/value pairs where the order of insertion is significant and duplicate keys are explicitly forbidden. js-yaml supports this tag as part of its type system, and when it encounters !!omap during parsing, it runs a resolution function that, among other things, validates that no key appears more than once.

The Quadratic Algorithm

The flaw lives in the duplicate-key detection logic inside the !!omap type resolver. In the vulnerable versions (js-yaml <4.3.1 and <3.15.1), the check was implemented as a linear scan of a growing array:

// Simplified representation of the vulnerable pattern in js-yaml !!omap resolver
function resolveYamlOmap(data) {
  const objectKeys = [];
  for (const pair of data) {
    const key = Object.keys(pair)[0];
    // For each new key, scan the entire previously-seen array
    if (objectKeys.indexOf(key) !== -1) {
      return false; // duplicate found
    }
    objectKeys.push(key);
  }
  return true;
}

The critical line is objectKeys.indexOf(key). For every new key encountered, this call scans the entire objectKeys array from the beginning. With n entries in the !!omap:

• Entry 1: 0 comparisons
• Entry 2: 1 comparison
• Entry 3: 2 comparisons
• …
• Entry n: n-1 comparisons

Total comparisons: 0 + 1 + 2 + … + (n-1) = n(n-1)/2 → O(n²)

This is a classic algorithmic complexity vulnerability. For a document with 10 entries it is imperceptible. For 100,000 entries, it requires roughly 5 billion comparisons.

Concrete Attack Scenario

An attacker targeting a web application that accepts YAML configuration or data payloads could POST a request body like:

!!omap
- key_00001: value
- key_00002: value
- key_00003: value
# ... 100,000 unique keys ...
- key_99999: value

Because all keys are unique, the !!omap resolver never short-circuits — it must compare every new key against every previously-seen key. A single such request on a commodity server can peg one CPU core for several seconds. Sending a handful of these requests concurrently can exhaust all available CPU, making the service unresponsive to legitimate traffic.

This is particularly dangerous in this project because:

1. It is a web application (noted in the PR threat model), meaning YAML input paths may be reachable from the internet.
2. The vulnerability requires no authentication or special privileges — only the ability to send a request containing YAML.
3. The attack is deterministic and repeatable: the attacker does not need to guess memory addresses or race conditions.

Why Both 3.x and 4.x Are Affected

The !!omap resolver code was present in both major release lines with the same algorithmic pattern. The CVE-2026-59870 fix corrected the issue in the upstream codebase but was not backported to the 3.x branch until 3.15.1, leaving users of either line exposed if they had not upgraded.

The Fix

What Changed

The fix upgrades js-yaml in two places within this repository:

The patch in bun.lock ensures that Bun's deterministic installer will pull the patched release rather than the cached 4.3.0 artifact.

The Algorithmic Fix Inside js-yaml

In js-yaml 4.3.1 / 3.15.1, the !!omap resolver replaces the array-scan pattern with a Set-based lookup:

// BEFORE (vulnerable — O(n²))
function resolveYamlOmap(data) {
  const objectKeys = [];
  for (const pair of data) {
    const key = Object.keys(pair)[0];
    if (objectKeys.indexOf(key) !== -1) {  // ← linear scan every iteration
      return false;
    }
    objectKeys.push(key);
  }
  return true;
}

// AFTER (patched — O(n))
function resolveYamlOmap(data) {
  const seenKeys = new Set();              // ← O(1) lookup
  for (const pair of data) {
    const key = Object.keys(pair)[0];
    if (seenKeys.has(key)) {               // ← constant-time membership test
      return false;
    }
    seenKeys.add(key);
  }
  return true;
}

A JavaScript Set uses a hash table internally, so has() and add() are both O(1) amortized. The total work for resolving an !!omap with n entries drops from O(n²) to O(n) — a fundamental improvement that makes the attack economically unviable regardless of document size.

Why the bun.lock Change Matters

Locking files like bun.lock (and package-lock.json, yarn.lock) record the exact resolved version of every dependency. Even if package.json is updated to allow 4.3.1, the lock file continues to install 4.3.0 until it is regenerated. This PR correctly updates both files, ensuring the patched version is installed in all environments — local development, CI, and production — without ambiguity.

Prevention & Best Practices

1. Audit Algorithmic Complexity in Parser Code

Any code that processes unbounded user input and uses nested loops or linear-scan membership tests is a candidate for this class of vulnerability. Review parsers, deserializers, and validators for patterns like:

// Red flag: array.indexOf() or array.includes() inside a loop over user data
for (const item of userSuppliedData) {
  if (seenItems.indexOf(item) !== -1) { ... }  // O(n) inside O(n) loop = O(n²)
}

Replace with Set or Map for O(1) lookups.

2. Enforce Input Size Limits Before Parsing

Even with the fix applied, it is good practice to cap YAML document size before handing it to any parser:

const MAX_YAML_BYTES = 1_000_000; // 1 MB
if (Buffer.byteLength(rawInput) > MAX_YAML_BYTES) {
  throw new Error('YAML input exceeds maximum allowed size');
}
const parsed = yaml.load(rawInput);

This provides defense-in-depth against future unknown complexity vulnerabilities.

3. Keep Lock Files in Version Control and Update Them

A lock file that is not committed, or is committed but never updated, creates a false sense of security. Automate dependency updates with tools like Dependabot or Renovate, and ensure your CI pipeline verifies that the lock file matches package.json.

4. Use Vulnerability Scanners on Lock Files

Tools like Trivy (which detected this issue), Snyk, and npm audit can scan lock files for known-vulnerable versions. Integrate these into your CI pipeline as a required check:

# Example: fail the build if any high/critical vulnerabilities are found
trivy fs --exit-code 1 --severity HIGH,CRITICAL .

5. Reference Security Standards

• CWE-407: Inefficient Algorithmic Complexity — the canonical classification for this class of bug.
• OWASP A05:2021 – Security Misconfiguration: Includes using components with known vulnerabilities.
• OWASP Dependency-Check: A tool specifically designed to identify known-vulnerable dependencies.

Key Takeaways

• !!omap is a non-obvious attack surface: Most developers think of YAML parsing risks as code execution (via unsafe yaml.load), but the !!omap tag creates a CPU exhaustion path even when using the safe yaml.safeLoad / yaml.load (safe mode) API.
• Array .indexOf() inside a parsing loop is an O(n²) smell: In the vulnerable js-yaml code, replacing objectKeys.indexOf(key) with seenKeys.has(key) (using a Set) was the entire fix — a one-line change with massive security impact.
• Lock file updates are as important as package.json updates: Pinning package.json to ^4.3.1 without regenerating bun.lock would have left the vulnerable version installed in production.
• Both 3.x and 4.x users are affected: Do not assume a major version upgrade automatically resolves all security issues in a library; always check the specific advisory for affected version ranges.
• Trivy's lock file scanning caught what code review would miss: The vulnerability is not visible in application source code — it lives inside the library itself. Automated SCA (Software Composition Analysis) scanning of bun.lock was the detection mechanism here.

How Orbis AppSec Detected This

• Source: Any code path that calls yaml.load() or yaml.safeLoad() with input containing a !!omap tag — in a web application, this originates from HTTP request bodies, file uploads, or configuration endpoints that accept YAML.
• Sink: The resolveYamlOmap function inside js-yaml's type resolver, invoked during YAML document parsing whenever the !!omap tag is encountered.
• Missing control: No bound on the number of !!omap entries processed, combined with an O(n²) duplicate-key detection algorithm — no per-request CPU budget or input size cap was enforced before the fix.
• CWE: CWE-407 — Inefficient Algorithmic Complexity.
• Fix: Upgraded js-yaml from 4.3.0 to 4.3.1 (and 3.x to 3.15.1) in package.json and bun.lock, replacing the quadratic duplicate-key detection with a constant-time Set-based lookup.

Orbis AppSec automatically detected this vulnerability and opened a pull request with the fix. Try Orbis AppSec on your repositories to find and fix issues like this automatically.

Conclusion

GHSA-5p4m-2wfm-xmqj is a textbook example of why algorithmic complexity matters in security contexts. The !!omap duplicate-key check in js-yaml looked completely reasonable — scan a list for duplicates before accepting a value — but at scale it becomes a denial-of-service primitive that requires no special knowledge to exploit. A single well-formed YAML document is all an attacker needs.

The fix is straightforward: upgrade to js-yaml 4.3.1 or 3.15.1, update your lock file, and let a Set do what arrays were never meant to do. Pair that with input size limits and automated SCA scanning in CI, and you have a robust defense against this entire class of vulnerability.

Algorithmic complexity bugs are easy to overlook in code review because the code is correct — it just isn't efficient. That is precisely why automated tooling that tracks known-vulnerable dependency versions is an essential layer of a modern security program.

References

• CWE-407: Inefficient Algorithmic Complexity
• OWASP A06:2021 – Vulnerable and Outdated Components
• OWASP Dependency-Check
• js-yaml 4.3.1 Release Notes
• js-yaml Safe Load API Documentation
• Semgrep rules for js-yaml vulnerabilities
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj)
• GHSA-5p4m-2wfm-xmqj Advisory