How Quadratic CPU Consumption Happens in JavaScript YAML Parsing and How to Fix It

How Quadratic CPU Consumption Happens in JavaScript YAML Parsing and How to Fix It

Introduction

The package-lock.json file in this Node.js application pins js-yaml at version 4.3.0 — a version that harbors a subtle but dangerous algorithmic flaw. When the YAML parser encounters a !!omap (ordered map) tag, it validates that no duplicate keys exist by iterating over every previously seen key for each new key it processes. That nested loop is O(n²): a crafted YAML document with 10,000 ordered-map entries forces roughly 50 million comparisons before parsing completes. An attacker who can supply YAML to any endpoint that calls js-yaml can weaponize this behaviour to pin a CPU core and deny service to legitimate users.

This post dissects exactly how the !!omap resolver creates that quadratic path, shows the one-line dependency bump that closes it, and explains what developers should watch for in their own YAML-processing code.

The Vulnerability Explained

What is !!omap and why does it need duplicate checking?

YAML's !!omap tag represents an ordered mapping — a sequence of single-entry mappings that preserves insertion order while still requiring unique keys. The js-yaml library implements this as a custom type resolver. During resolution, it must verify that no key appears more than once.

In js-yaml ≤ 4.3.0 (and ≤ 3.14.x), the duplicate-key check was implemented with a pattern equivalent to:

// Pseudocode reflecting the vulnerable logic in js-yaml ≤ 4.3.0
function resolveOmap(data) {
  const pairs = parsePairs(data);        // n entries
  for (let i = 0; i < pairs.length; i++) {
    const key = pairs[i][0];
    for (let j = 0; j < i; j++) {       // ← inner loop grows with i
      if (pairs[j][0] === key) {
        throw new YAMLException('duplicate key in !!omap');
      }
    }
  }
  return pairs;
}

The inner loop compares the current key against all previously seen keys. For n entries, the total number of comparisons is 1 + 2 + 3 + … + (n-1) = n(n-1)/2 — classic O(n²) behaviour.

Crafting the attack

An attacker needs nothing more than a YAML document like this:

!!omap
- key_0001: value
- key_0002: value
- key_0003: value
# ... 10,000 more unique keys ...
- key_9999: value

Because every key is unique, the parser never throws an exception — it grinds through all ~50 million comparisons before returning a result. On a modern server, parsing a 10,000-entry !!omap can consume several seconds of CPU time per request. A handful of concurrent requests is enough to saturate a single-core worker process.

Why this application is at risk

The package.json in this repository lists js-yaml as a direct, production dependency ("js-yaml": "^4.3.0"), sitting alongside better-sqlite3, dompurify, and pg. Any code path that calls yaml.load(), yaml.loadAll(), or yaml.safeLoad() on externally supplied content — configuration uploads, API payloads, webhook bodies — is a potential trigger. Because dompurify is also present, this appears to be a full-stack web application where user-generated content is a realistic attack surface.

The Fix

What changed

The fix is a two-file dependency bump:

package.json — tighten the minimum required version:

-    "js-yaml": "^4.3.0",
+    "js-yaml": "^4.3.1",

package-lock.json — pin the resolved version and update the integrity hash:

     "node_modules/js-yaml": {
-      "version": "4.3.0",
-      "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.3.0.tgz",
-      "integrity": "sha512-1td788aAnnZ5qs7V2QIRl1owjtYpbKt749Y3xauqQgwIIGF/xXWz1wMTEBx5O3LK3lXLVuqXPdPxj2BoFHaW9Q==",
+      "version": "4.3.1",
+      "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.3.1.tgz",
+      "integrity": "sha512-CY6crGq313MX8GkwvB7tzgp99vjQxY1++5y10/BKN/GUfHqWaOGQMNZkBvqSzsZKWk/ijwHlWzzkLulsGHhjWQ==",

Both files must be updated together: package.json ensures npm install never resolves back to 4.3.0, and package-lock.json ensures the exact resolved URL and integrity hash match the patched release, preventing supply-chain substitution.

How js-yaml 4.3.1 fixes the algorithm

The patched release replaces the O(n²) nested loop with an O(n) Set-based lookup:

// Pseudocode reflecting the fixed logic in js-yaml 4.3.1
function resolveOmap(data) {
  const pairs = parsePairs(data);
  const seenKeys = new Set();            // ← O(1) lookup
  for (const [key] of pairs) {
    if (seenKeys.has(key)) {
      throw new YAMLException('duplicate key in !!omap');
    }
    seenKeys.add(key);
  }
  return pairs;
}

A Set.has() call is O(1) on average. The total work is now O(n) — doubling the number of entries doubles the work, not quadruples it. A 10,000-entry !!omap that previously required ~50 million comparisons now requires exactly 10,000 hash lookups.

Behaviour preservation

Valid YAML documents — including those with !!omap tags — parse identically after the upgrade. The only observable difference is that maliciously large inputs are rejected or processed in linear time rather than quadratic time.

Prevention & Best Practices

1. Audit all YAML entry points for untrusted input

Any call to yaml.load() that accepts externally supplied data is a potential DoS vector. Even with the algorithmic fix in place, consider adding a size cap before parsing:

import yaml from 'js-yaml';

const MAX_YAML_BYTES = 1_000_000; // 1 MB

function safeParseYaml(raw) {
  if (Buffer.byteLength(raw, 'utf8') > MAX_YAML_BYTES) {
    throw new Error('YAML payload exceeds maximum allowed size');
  }
  return yaml.load(raw);
}

2. Keep dependency lock files in version control and CI

The package-lock.json change is as important as the package.json change. Without committing the lock file, npm ci cannot guarantee the patched version is installed. Enforce npm ci (not npm install) in CI pipelines to honour the lock file exactly.

3. Run automated dependency scanning on every PR

Tools like Trivy (which detected this vulnerability), npm audit, Dependabot, and Snyk can flag known CVEs in package-lock.json before they reach production. Configure them to fail the build on HIGH or CRITICAL findings.

4. Watch for O(n²) patterns in custom type resolvers

If your project defines custom YAML types via js-yaml's Type API, audit the resolve, construct, and represent callbacks for nested loops over attacker-controlled collections. Prefer Map and Set over array-scan patterns.

5. Reference standards

• CWE-407: Inefficient Algorithmic Complexity — https://cwe.mitre.org/data/definitions/407.html
• OWASP: Denial of Service Cheat Sheet — https://cheatsheetseries.owasp.org/cheatsheets/Denial_of_Service_Cheat_Sheet.html
• OWASP: Vulnerable and Outdated Components (A06:2021) — https://owasp.org/Top10/A06_2021-Vulnerable_and_Outdated_Components/

Key Takeaways

• The !!omap resolver in js-yaml ≤ 4.3.0 uses an O(n²) duplicate-key scan — a single crafted YAML document with thousands of ordered-map entries is enough to saturate a CPU core.
• Both package.json and package-lock.json must be updated together — updating only one leaves a gap where the wrong version can be resolved during npm install.
• The integrity hash in package-lock.json changed (sha512-1td788... → sha512-CY6crG...) — this is the cryptographic proof that the installed package matches the patched release, not the vulnerable one.
• Algorithmic DoS is distinct from traditional ReDoS — there is no regular expression involved; the attack surface is the YAML type-resolution pipeline itself, making regex-focused scanners insufficient on their own.
• Linear-time alternatives (Set, Map) should always replace nested-loop duplicate checks over attacker-controlled data, regardless of the language or framework.

How Orbis AppSec Detected This

• Source: Externally supplied YAML content parsed by js-yaml — any HTTP request body, file upload, or configuration payload that reaches yaml.load() or yaml.loadAll().
• Sink: The !!omap type resolver inside node_modules/js-yaml (resolved to version 4.3.0 via package-lock.json), which performs an O(n²) duplicate-key scan on attacker-controlled key arrays.
• Missing control: No algorithmic complexity bound on the !!omap duplicate-key detection loop; no upstream patch (CVE-2026-59870) applied to the pinned version.
• CWE: CWE-407 — Inefficient Algorithmic Complexity.
• Fix: Bumped js-yaml from 4.3.0 to 4.3.1 in both package.json and package-lock.json, replacing the O(n²) loop with an O(n) Set-based check.

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 reminder that security vulnerabilities do not always look like memory corruption or injection flaws. A quietly inefficient algorithm hidden inside a YAML type resolver can be just as dangerous as an SQL injection when it sits on the path of untrusted input. The fix — a one-version bump from js-yaml@4.3.0 to 4.3.1 — is minimal, non-breaking, and eliminates the quadratic work entirely by swapping a nested loop for a Set lookup.

The broader lesson: treat your package-lock.json as a first-class security artefact. Keep it committed, keep it scanned, and keep it current. Automated tools like Orbis AppSec can watch that file continuously and open targeted, context-rich pull requests the moment a patched version is available — before an attacker finds the gap.

References

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