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

The Hidden Cost of Parsing Ordered Maps: js-yaml's Quadratic CPU Bug

When your Node.js service parses a YAML configuration file or API payload, you probably assume the operation takes time proportional to the size of the document — parse 100 keys, spend roughly 100 units of work. But a subtle flaw in js-yaml's handling of the !!omap (ordered map) type tag broke that assumption entirely. A crafted YAML document with enough ordered-map entries could force the parser to spend quadratic time — 10,000 units of work for 100 entries, 1,000,000 units for 1,000 entries — turning a routine parse call into a CPU-exhausting denial-of-service vector.

This post breaks down exactly what went wrong, how the fix works, and what you can do to protect your own applications.

The Vulnerability Explained

What is !!omap?

YAML supports a rich set of type tags. The !!omap tag represents an ordered mapping — a sequence of key-value pairs where insertion order is preserved and duplicate keys are forbidden. A valid !!omap document looks like this:

!!omap
- alpha: 1
- beta: 2
- gamma: 3

The js-yaml library must validate this structure: it needs to confirm that no key appears more than once. That duplicate-detection logic is where the vulnerability lives.

The O(n²) Duplicate-Key Check

In js-yaml 4.3.0 (and the 3.x line prior to the fix), the !!omap type resolver iterated over every entry in the ordered map and, for each entry, scanned all previously seen entries to check for a duplicate key. In pseudocode:

// Vulnerable pattern (conceptual — pre-fix behaviour)
for (let i = 0; i < pairs.length; i++) {
  for (let j = 0; j < i; j++) {
    if (pairs[j].key === pairs[i].key) {
      throw new Error('duplicate key');
    }
  }
}

This is a classic O(n²) nested loop. For a document with n key-value pairs:

An attacker who can submit YAML input to your application — via a configuration endpoint, a file upload, a webhook payload, or any other surface — can craft a single !!omap document with tens of thousands of unique keys and peg one CPU core at 100% for seconds or minutes per request.

A Concrete Attack Scenario

Imagine a Node.js service that accepts YAML-formatted rule definitions from authenticated users (a CI/CD platform, a network policy editor, an infrastructure-as-code tool). The route handler calls:

const yaml = require('js-yaml');
app.post('/rules', (req, res) => {
  const rules = yaml.load(req.body.yaml); // ← vulnerable in js-yaml 4.3.0
  applyRules(rules);
  res.json({ ok: true });
});

A malicious user submits:

!!omap
- key_0000001: value
- key_0000002: value
# ... 50,000 more unique keys ...
- key_0050000: value

The yaml.load() call triggers the quadratic duplicate-check loop. With 50,000 entries, the resolver performs ~1.25 billion comparisons. On a modern server this can take 30–60 seconds of pure CPU time — per request. Even a handful of concurrent requests can saturate all available CPU cores, denying service to legitimate users.

Because the vulnerability is in the parsing stage, no application-level business logic needs to be reached. The damage is done before applyRules() is ever called.

The Fix

What Changed in package-lock.json

The pull request makes a targeted, two-file change. In package-lock.json, the pinned version of node_modules/js-yaml moves from the vulnerable 4.3.0 to the patched 4.3.1:

 "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==",

The integrity hash change confirms this is a genuinely different package artifact, not just a metadata update.

Why the package.json Overrides Block Matters

Updating package-lock.json alone protects the direct dependency, but js-yaml is a popular library that frequently appears as a transitive dependency — pulled in by tools like webpack, jest, eslint, or dozens of other packages. Without an explicit override, npm install could silently resolve a transitive path back to 4.3.0.

The fix adds an overrides block to package.json to prevent this:

+  "overrides": {
+    "js-yaml": "4.3.1"
+  }

This npm v8+ feature tells the package manager: regardless of what any dependency requests, always resolve js-yaml to 4.3.1. It is a belt-and-suspenders measure that makes the fix durable across future npm install runs and dependency tree changes.

How 4.3.1 Fixes the Algorithm

js-yaml 4.3.1 replaces the nested-loop duplicate check with a Set-based lookup, which has O(1) average-case insertion and membership testing:

// Fixed pattern (post-4.3.1 behaviour)
const seenKeys = new Set();
for (const pair of pairs) {
  if (seenKeys.has(pair.key)) {
    throw new Error('duplicate key');
  }
  seenKeys.add(pair.key);
}

The total work is now O(n) — linear in the number of entries. The same 50,000-entry !!omap document that previously triggered billions of comparisons now requires exactly 50,000 Set operations. The attack surface collapses entirely.

Prevention & Best Practices

1. Pin and Override Transitive Dependencies

Direct dependencies are only part of the story. Use npm's overrides (npm ≥ 8), Yarn's resolutions, or pnpm's overrides to force safe versions of security-sensitive libraries across your entire dependency tree.

// package.json
{
  "overrides": {
    "js-yaml": "4.3.1"
  }
}

2. Enforce Input Size Limits Before Parsing

Even with a patched library, applying a size cap before handing untrusted data to any parser is good defence-in-depth:

const MAX_YAML_BYTES = 1_000_000; // 1 MB
if (Buffer.byteLength(rawInput) > MAX_YAML_BYTES) {
  return res.status(413).json({ error: 'Payload too large' });
}
const parsed = yaml.load(rawInput);

3. Use Automated Dependency Scanning

This vulnerability was detected by Trivy, a container and filesystem vulnerability scanner. Integrate similar tools into your CI pipeline:

• Trivy — scans package-lock.json, container images, and IaC files
• npm audit — built-in, catches advisories in the npm registry
• Dependabot / Renovate — automated PRs when new patched versions are released
• Semgrep — rule-based static analysis; see the js-yaml Semgrep rules

4. Understand Algorithmic Complexity Vulnerabilities

Quadratic-complexity bugs are often invisible in testing because test inputs are small. Consider:

• Fuzz testing with large, structured inputs to surface O(n²) behaviour
• Profiling YAML/JSON/XML parse paths under load
• Treating any parser that touches untrusted input as a potential DoS vector

5. OWASP and CWE Alignment

This vulnerability maps to:

• CWE-407: Inefficient Algorithmic Complexity
• OWASP A05:2021 — Security Misconfiguration (using outdated, vulnerable library versions)
• OWASP A06:2021 — Vulnerable and Outdated Components

Key Takeaways

• !!omap is a legitimate YAML attack surface: Any application that parses YAML from untrusted sources and uses js-yaml 4.3.0 or 3.x is exposed to CPU exhaustion via crafted ordered-map documents.
• The package-lock.json version alone is not enough: Without the "overrides" block in package.json, future npm install runs can silently reintroduce the vulnerable 4.3.0 through transitive dependencies.
• O(n²) bugs are invisible at test scale: The duplicate-key loop in js-yaml's !!omap resolver looked correct and passed all unit tests — the problem only manifests with large inputs designed to trigger worst-case behaviour.
• Set-based lookups are the right fix for uniqueness checks: Replacing the nested array scan with a Set drops the complexity from O(n²) to O(n) and eliminates the attack entirely.
• Integrity hashes in package-lock.json are your tamper-evidence: The SHA-512 change from sha512-1td788... to sha512-CY6crG... confirms you are running genuinely different (patched) code, not just a metadata change.

How Orbis AppSec Detected This

• Source: Untrusted YAML content supplied to yaml.load() calls anywhere in the application or its dependency chain that processes external input.
• Sink: The !!omap type resolver inside node_modules/js-yaml (version 4.3.0 as recorded in package-lock.json), which performed a quadratic duplicate-key scan during ordered-map construction.
• Missing control: No algorithmic complexity guard existed in the !!omap resolver; the library used a nested array iteration instead of a constant-time Set lookup, and no input-size limit was enforced upstream.
• CWE: CWE-407 — Inefficient Algorithmic Complexity
• Fix: package-lock.json was updated to resolve node_modules/js-yaml to version 4.3.1, and a "overrides": { "js-yaml": "4.3.1" } block was added to package.json to pin the patched version across all transitive dependency paths.

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 denial-of-service vulnerabilities don't always look dramatic. There is no memory corruption, no remote code execution, no leaked secrets — just a nested loop that grows quadratically and a YAML tag that most developers have never typed. Yet the impact is real: a single HTTP request carrying a crafted !!omap document can saturate a CPU core for tens of seconds, and a handful of concurrent requests can take down a service entirely.

The fix is surgical: two files changed, one version bumped, one overrides entry added. The patched algorithm is O(n) instead of O(n²), and the overrides block ensures the fix survives future dependency tree changes. If your project depends on js-yaml — directly or transitively — verify you are on 4.3.1 (or 3.15.1 for the 3.x line) today.

References

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