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

Introduction

In the e2e/adapter/claude-code end-to-end test package, Orbis AppSec's Trivy scanner flagged a high-severity vulnerability lurking in the pnpm-lock.yaml dependency tree: js-yaml@4.3.0 was subject to GHSA-5p4m-2wfm-xmqj, a quadratic CPU consumption bug in the !!omap (ordered map) type resolution handler. While the vulnerability existed in a transitive dependency pulled in through the autoevals package (visible in the lockfile snapshot), it represented a real exploit primitive — a pattern that automated attack tooling could chain with other weaknesses to achieve denial of service against any service parsing YAML from untrusted sources.

The specific problem: js-yaml's !!omap resolver performs duplicate-key validation using a nested loop that runs in O(n²) time. An attacker who can feed crafted YAML to any code path that eventually calls yaml.load() with the default schema can lock up a Node.js event loop with a surprisingly small payload.

The Vulnerability Explained

What is !!omap and Why Does It Matter?

YAML's !!omap type represents an ordered mapping — essentially an array of single-key objects where duplicate keys are forbidden. When js-yaml encounters a !!omap tag, it must validate that no two entries share the same key. In versions up to 4.3.0, this validation looked conceptually like:

// Simplified representation of the vulnerable pattern in js-yaml <= 4.3.0
for (let i = 0; i < pairs.length; i++) {
  for (let j = i + 1; j < pairs.length; j++) {
    if (pairs[i][0] === pairs[j][0]) {
      throw new Error('duplicate key in !!omap');
    }
  }
}

This nested iteration is O(n²) — for an ordered map with 10,000 entries, the inner comparison runs approximately 50 million times. For 100,000 entries, it's roughly 5 billion comparisons. The CPU time grows quadratically with the number of keys, and because Node.js is single-threaded, this blocks the entire event loop.

The Attack Scenario

Consider the dependency chain visible in the lockfile diff. The autoevals package (pinned at a specific version in the project) depends on js-yaml:

# From pnpm-lock.yaml snapshots section (before fix)
snapshots:
  autoevals:
    dependencies:
      ajv: 8.20.0
      compute-cosine-similarity: 1.1.0
      js-levenshtein: 1.1.6
      js-yaml: 4.3.0        # <-- vulnerable version
      linear-sum-assignment: 1.0.9
      mustache: 4.2.0

If any code path in the e2e adapter or its dependencies parses YAML that could originate from external input — configuration files, API responses, test fixtures loaded from repositories, or webhook payloads — an attacker could craft a YAML document like:

--- !!omap
- key_00001: value
- key_00002: value
- key_00003: value
# ... thousands more unique keys ...
- key_99999: value
- key_100000: value

Even though all keys are unique (so the validation ultimately passes), the O(n²) check must compare every pair before confirming there are no duplicates. A 100KB YAML file with ~10,000 omap entries could freeze a Node.js process for seconds; a 1MB file could hang it for minutes.

Why "Not Confirmed Reachable" Still Matters

The PR assessment notes the vulnerability is "present in dependency tree, not confirmed reachable." This is an honest assessment — the e2e test suite may not directly parse untrusted YAML through autoevals. However, this matters for three reasons:

1. Dependency drift: Future code changes might introduce a path where untrusted YAML reaches js-yaml.
2. Supply chain risk: If autoevals itself processes YAML from external sources, the vulnerability is reachable through the library.
3. Exploit primitive removal: Automated exploit-development tools increasingly scan for known-vulnerable dependency versions and attempt to construct exploit chains. Removing the primitive raises the bar.

The Fix

The fix is surgical and elegant: a pnpm override in package.json forces every copy of js-yaml in the dependency tree to version 4.3.1, regardless of what transitive dependencies request.

Change 1: e2e/adapter/claude-code/package.json

Before:

{
  "devDependencies": {
    "@types/node": "^24.0.0",
    "typescript": "^5.7.2",
    "vitest": "^4.1.11"
  }
}

After:

{
  "devDependencies": {
    "@types/node": "^24.0.0",
    "typescript": "^5.7.2",
    "vitest": "^4.1.11"
  },
  "pnpm": {
    "overrides": {
      "js-yaml": "4.3.1"
    }
  }
}

The pnpm.overrides field is the pnpm equivalent of npm's overrides or Yarn's resolutions. It tells the package manager: "No matter what version any dependency requests for js-yaml, install 4.3.1 instead." This is critical because the project doesn't directly depend on js-yaml — it comes in transitively through autoevals.

Change 2: e2e/adapter/claude-code/pnpm-lock.yaml

The lockfile reflects the override taking effect:

# Before
overrides: {}  # (implicit)

# After
overrides:
  js-yaml: 4.3.1

And in the resolved snapshots:

# Before
js-yaml@4.3.0:
  resolution: {integrity: sha512-1td788aAnnZ5qs7V2QIRl1owjtYpbKt749Y3xauqQgwIIGF/xXWz1wMTEBx5O3LK3lXLVuqXPdPxj2BoFHaW9Q==}

# After
js-yaml@4.3.1:
  resolution: {integrity: sha512-CY6crGq313MX8GkwvB7tzgp99vjQxY1++5y10/BKN/GUfHqWaOGQMNZkBvqSzsZKWk/ijwHlWzzkLulsGHhjWQ==}

The integrity hash change confirms a genuinely different package is being installed. In the snapshots section, autoevals now resolves to the patched version:

# Before
autoevals:
  dependencies:
    js-yaml: 4.3.0

# After
autoevals:
  dependencies:
    js-yaml: 4.3.1

What js-yaml 4.3.1 Changes Internally

Version 4.3.1 replaces the nested-loop duplicate-key check in the !!omap resolver with a Set-based or hash-based lookup, reducing the complexity from O(n²) to O(n). The same 100,000-key omap that would freeze a process for minutes now resolves in milliseconds.

Prevention & Best Practices

1. Use Dependency Override Mechanisms

When a vulnerability exists in a transitive dependency you don't control directly, use your package manager's override feature:

2. Treat YAML Parsing as a Security Boundary

If your application parses YAML from any external source:
- Use yaml.load() with the JSON_SCHEMA or FAILSAFE_SCHEMA to disable type coercion including !!omap
- Set resource limits (timeouts, input size caps) around parsing operations
- Consider using JSON.parse() instead if your data doesn't require YAML-specific features

3. Automate Dependency Scanning

Tools like Trivy, Snyk, and Dependabot catch known vulnerabilities in lockfiles. Integrate them into CI/CD pipelines so that PRs with vulnerable dependencies are flagged before merge.

4. Audit Transitive Dependencies

Run pnpm why js-yaml (or npm explain js-yaml) regularly to understand why a package is in your tree and whether you can upgrade or replace the parent dependency.

Key Takeaways

• js-yaml's !!omap handler in versions ≤4.3.0 uses O(n²) duplicate-key validation, making it trivially exploitable for CPU-based denial of service with crafted YAML input containing thousands of ordered map entries.
• Transitive dependencies are attack surface too: the vulnerable js-yaml@4.3.0 wasn't a direct dependency of e2e/adapter/claude-code — it came in through autoevals, making it invisible without lockfile scanning.
• pnpm overrides are the correct tool for forcing a patched version across all transitive consumers when you can't wait for upstream to bump their dependency.
• "Not confirmed reachable" doesn't mean safe: exploit primitives in the dependency tree should be removed proactively, especially as automated exploit-development tools grow more capable of chaining weaknesses.
• The fix changed only 2 files (package.json and pnpm-lock.yaml) with zero functional impact on valid YAML inputs — a minimal, low-risk patch with high security value.

How Orbis AppSec Detected This

• Source: The js-yaml package resolved in e2e/adapter/claude-code/pnpm-lock.yaml as a transitive dependency of autoevals, potentially exposed to YAML input from test fixtures, configuration files, or external data sources.
• Sink: The !!omap type resolver inside js-yaml@4.3.0's load() function, which executes a quadratic duplicate-key validation loop on any YAML document containing ordered map sequences.
• Missing control: No version pinning or override existed to enforce a patched js-yaml version across the transitive dependency tree; the lockfile resolved to the vulnerable 4.3.0 release.
• CWE: CWE-407 (Inefficient Algorithmic Complexity)
• Fix: Added a pnpm.overrides entry in package.json to force js-yaml@4.3.1 across all dependencies, and regenerated the lockfile to reflect the patched resolution.

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

The js-yaml !!omap quadratic complexity vulnerability (GHSA-5p4m-2wfm-xmqj) is a textbook example of how algorithmic inefficiency becomes a security issue. A simple nested loop for duplicate-key detection — code that works correctly for small inputs — becomes a denial-of-service vector when exposed to adversarial input. The fix was straightforward: upgrade to 4.3.1 where the check runs in linear time, and use pnpm overrides to ensure the patch reaches every consumer in the dependency tree.

For developers maintaining Node.js projects: audit your lockfiles regularly, understand your transitive dependency tree, and treat YAML parsing with the same caution you'd give to any input deserialization boundary. The next vulnerability in your dependency tree might not be "confirmed reachable" today — but tomorrow's code change or tomorrow's automated attack tool might close that gap.

References

• CWE-407: Inefficient Algorithmic Complexity
• GHSA-5p4m-2wfm-xmqj — GitHub Security Advisory
• OWASP Denial of Service Cheat Sheet
• js-yaml npm package documentation
• pnpm overrides documentation
• Semgrep rules for YAML parsing
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj)