How Quadratic CPU Consumption happens in JavaScript YAML parsing and how to fix it

The Hidden Cost of Parsing YAML: A Quadratic Trap in js-yaml

In a Node.js project's package-lock.json, a routine dependency audit surfaced something easy to overlook: a pinned sub-dependency deep in the @istanbuljs/load-nyc-config subtree was pulling in js-yaml version 3.14.2 — a version containing a high-severity denial-of-service flaw that had never been backported with the upstream fix. Meanwhile, the top-level js-yaml dependency sat at 4.1.1, itself also vulnerable. The result: two separate vulnerable instances of the same library living in the same dependency tree, both capable of being triggered by a single crafted YAML document.

This is the story of GHSA-5p4m-2wfm-xmqj — a deceptively simple algorithmic flaw in !!omap resolution that can bring a Node.js service to its knees.

The Vulnerability Explained

What is !!omap and why does it matter?

YAML's !!omap (ordered map) type represents a sequence of key-value pairs where insertion order is preserved and duplicate keys are explicitly forbidden. When js-yaml encounters a !!omap node, it must validate that no key appears more than once. In the vulnerable versions (js-yaml 3.x through 3.14.x and 4.x through 4.1.x), this duplicate-key check was implemented using a nested loop — for every new key encountered, the resolver iterated over all previously seen keys to check for a match.

This is the classic O(n²) pattern:

// Conceptual representation of the vulnerable duplicate-check logic
// in js-yaml's !!omap resolver (pre-fix)
function resolveOmap(data) {
  for (let i = 0; i < data.length; i++) {
    for (let j = 0; j < i; j++) {
      if (data[i].key === data[j].key) {
        throw new Error('duplicate key');
      }
    }
  }
}

For a YAML !!omap with n entries, this performs approximately n²/2 comparisons. With 10,000 entries, that's ~50 million comparisons. With 100,000 entries, it's ~5 billion. The CPU time grows quadratically while the input size only grows linearly.

The Concrete Attack Scenario

An attacker who can supply YAML input to any code path that calls js-yaml's safeLoad(), load(), or parse() functions can craft a payload like:

!!omap
- key_0000001: value
- key_0000002: value
- key_0000003: value
# ... repeated 50,000 times with unique keys
- key_0050000: value

Because all keys are unique, the parser never throws a duplicate error — it simply grinds through all O(n²) comparisons before returning the parsed object. A single HTTP request carrying such a payload could monopolize a Node.js event loop thread for seconds or minutes, effectively denying service to all other requests.

Why Two Vulnerable Versions Were Present

The diff reveals a particularly important detail: the vulnerability existed in two separate locations in the dependency tree:

1. Top-level: js-yaml at version 4.1.1
2. Nested under @istanbuljs/load-nyc-config: a pinned js-yaml at version 3.14.2

// BEFORE — vulnerable nested dependency in package-lock.json
"node_modules/@istanbuljs/load-nyc-config/node_modules/js-yaml": {
  "version": "3.14.2",
  "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-3.14.2.tgz",
  "integrity": "sha512-PMSmkqxr106Xa156c2M265Z+FTrPl+oxd/...",
  "dev": true,
  "dependencies": {
    "argparse": "^1.0.7",
    "esprima": "^4.0.0"
  }
}

The nested 3.14.2 instance was pinned because @istanbuljs/load-nyc-config required the older js-yaml 3.x API. Even though this dependency is marked "dev": true, it is still a real attack surface during CI/CD pipelines and development environments — and in some build configurations, dev dependencies are inadvertently bundled into production artifacts.

The Fix

The fix made two coordinated changes:

1. Upgrade the top-level js-yaml (4.1.1 → 4.3.1)

package.json was updated to require js-yaml@^4.3.1, and package-lock.json was regenerated to reflect the resolved 4.3.1 version. Version 4.3.1 replaces the nested loop duplicate-key check with a Set-based O(n) lookup:

// AFTER — linear duplicate detection using a Set (js-yaml 4.3.1)
function resolveOmap(data) {
  const seen = new Set();
  for (const item of data) {
    if (seen.has(item.key)) {
      throw new Error('duplicate key');
    }
    seen.add(item.key);
  }
}

A Set lookup is O(1) amortized, making the entire loop O(n). A 100,000-entry !!omap now requires 100,000 operations instead of 5 billion.

2. Remove the pinned vulnerable 3.14.2 sub-dependency

The diff removes the entire nested node_modules/@istanbuljs/load-nyc-config/node_modules/js-yaml block (along with its argparse and sprintf-js companions) from package-lock.json:

-    "node_modules/@istanbuljs/load-nyc-config/node_modules/js-yaml": {
-      "version": "3.14.2",
-      "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-3.14.2.tgz",
-      "integrity": "sha512-PMSmkqxr106Xa156c2M265Z+...",
-      "dev": true,
-      "dependencies": {
-        "argparse": "^1.0.7",
-        "esprima": "^4.0.0"
-      }
-    },
-    "node_modules/@istanbuljs/load-nyc-config/node_modules/argparse": { ... },
-    "node_modules/@istanbuljs/load-nyc-config/node_modules/sprintf-js": { ... },
-    "node_modules/esprima": { ... },

By removing the nested override, @istanbuljs/load-nyc-config is now resolved to use the hoisted, patched js-yaml rather than its own pinned vulnerable copy. The esprima package (a dependency of js-yaml 3.x that is no longer needed by the patched version) is also removed, trimming unnecessary weight from the dependency tree.

Before and After at a Glance

Prevention & Best Practices

1. Audit transitive dependencies, not just direct ones

This vulnerability existed in a nested dependency that would not have been caught by only inspecting package.json. Always audit package-lock.json or yarn.lock for vulnerable versions:

# Using npm audit
npm audit

# Using Trivy for comprehensive SCA
trivy fs --scanners vuln .

2. Treat dev dependencies as a real attack surface

The vulnerable js-yaml@3.14.2 was marked "dev": true, but dev dependencies can:
- Be exploited in CI/CD pipelines
- Be accidentally bundled into production builds
- Introduce supply-chain risks via postinstall scripts

Apply the same patching discipline to dev dependencies as to production ones.

3. Use npm dedupe after upgrades

After resolving version conflicts, run:

npm dedupe

This collapses redundant nested copies of packages into a single hoisted version, reducing both attack surface and bundle size.

4. Set upper bounds cautiously, lower bounds firmly

Avoid pinning exact versions of transitive dependencies in package.json unless absolutely necessary. Prefer semver ranges (^4.3.1) that allow patch updates to flow through automatically.

5. Relevant Standards

• CWE-407: Inefficient Algorithmic Complexity — the root cause of this vulnerability
• OWASP A06:2021 – Vulnerable and Outdated Components — keeping dependencies patched is a top-10 security priority
• OWASP Denial of Service Cheat Sheet — guidance on preventing resource exhaustion attacks

Key Takeaways

• The !!omap type resolver in js-yaml ≤3.14.x and ≤4.1.x uses O(n²) duplicate-key detection — a single large YAML document can exhaust CPU on the Node.js event loop thread.
• Nested dependency pins in package-lock.json can silently reintroduce patched-out vulnerabilities — the @istanbuljs/load-nyc-config subtree was carrying 3.14.2 even after the top-level dependency was upgraded.
• Removing the nested js-yaml@3.14.2 block also eliminated esprima@4.0.1 — a previously required but now-unnecessary parser dependency, reducing the overall attack surface.
• Dev-only dependencies are not safe to ignore — the vulnerable instance was "dev": true but remained a real risk in CI environments and misconfigured builds.
• The fix is backward-compatible: js-yaml 4.3.1 and 3.15.1 parse all valid YAML documents identically to their predecessors; only the internal complexity of the omap resolver changed.

How Orbis AppSec Detected This

• Source: Any code path passing untrusted or user-controlled YAML strings into js-yaml's load() or parse() functions — including configuration file readers, API endpoints accepting YAML payloads, and test harnesses using @istanbuljs/load-nyc-config.
• Sink: The !!omap type resolver inside js-yaml's type system, invoked whenever a YAML document contains an !!omap tag — present in both the node_modules/js-yaml (v4.1.1) and node_modules/@istanbuljs/load-nyc-config/node_modules/js-yaml (v3.14.2) instances.
• Missing control: No upper bound on !!omap entry count, and no O(1) data structure (such as a Set or Map) used for duplicate-key detection — allowing the nested loop to run to completion on arbitrarily large inputs.
• CWE: CWE-407 — Inefficient Algorithmic Complexity
• Fix: Upgraded js-yaml to 4.3.1 and removed the pinned vulnerable 3.14.2 sub-dependency from the @istanbuljs/load-nyc-config subtree in package-lock.json, replacing quadratic duplicate detection with a linear Set-based approach.

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 how algorithmic complexity vulnerabilities hide in plain sight. The !!omap flaw in js-yaml wasn't a memory corruption bug or an injection vector — it was simply the wrong data structure for a duplicate-key check. But in a language like JavaScript, where a single-threaded event loop handles all I/O, even a few seconds of CPU saturation translates directly into a service outage.

What makes this case particularly instructive is the double exposure: the top-level dependency was vulnerable, and a nested transitive pin was also vulnerable — independently. Neither would have been caught by a developer who only reviewed package.json. This is why automated SCA scanning of lock files, not just manifest files, is non-negotiable in modern Node.js security practice.

Upgrade to js-yaml@4.3.1 or js-yaml@3.15.1, audit your lock files for nested pins, and let your tooling catch what your eyes will miss.

References

• CWE-407: Inefficient Algorithmic Complexity
• OWASP Denial of Service Cheat Sheet
• OWASP A06:2021 – Vulnerable and Outdated Components
• js-yaml npm package (official)
• Semgrep rules for vulnerable dependency detection
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj)