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

Introduction

The .github/ directory of a repository often contains CI/CD workflow scripts that quietly pull in their own dependency trees — separate from the main application. In this project, the GitHub Actions automation scripts declared js-yaml: "^4.1.1" as a direct dependency in .github/package.json. That seemingly innocuous version range locked in a js-yaml build affected by GHSA-5p4m-2wfm-xmqj: a quadratic CPU consumption flaw triggered by YAML documents containing !!omap (ordered map) tags.

Because the vulnerable code lives in CI/CD infrastructure rather than production application code, it is easy to overlook — but it is still reachable by anyone who can influence the YAML content being parsed by those workflows.

The Vulnerability Explained

What is !!omap and why does it matter?

YAML's !!omap tag represents an ordered mapping — a sequence of key-value pairs where insertion order is significant. When js-yaml resolves an !!omap node, it must validate that no duplicate keys exist. In the affected versions (3.x up to 3.15.0, and 4.x up to 4.1.0), this duplicate-key check was implemented as a nested loop: for every new key encountered, the code iterated over all previously seen keys to check for a match.

This is the algorithmic pattern at fault:

// Pseudocode representing the vulnerable !!omap resolution logic
// in js-yaml 3.x / 4.x (before the fix)
function resolveOmap(data) {
  const pairs = parsePairs(data);
  for (let i = 0; i < pairs.length; i++) {
    for (let j = 0; j < i; j++) {          // <-- inner loop over all previous keys
      if (pairs[i].key === pairs[j].key) {
        throw new Error('duplicate key');
      }
    }
  }
  return pairs;
}

For an !!omap block with n entries, this performs n × (n-1) / 2 comparisons — classic O(n²) growth. With 10,000 entries, that is ~50 million comparisons. With 100,000 entries, it is ~5 billion.

The attack scenario

An attacker who can supply YAML input to a workflow that calls js-yaml.load() or js-yaml.safeLoad() on the content can craft a document like:

!!omap
- key_0000001: value
- key_0000002: value
- key_0000003: value
# ... 50,000 more entries ...
- key_0050000: value

Because all keys are unique, the duplicate check never short-circuits — it grinds through every comparison. On a standard CI runner, a 50,000-entry !!omap document can peg a CPU core for tens of seconds, potentially timing out jobs, exhausting runner credits, or being chained with other weaknesses to amplify impact.

Where this surfaces in the repository

The vulnerable dependency was declared in .github/package.json:

// BEFORE — vulnerable range
"js-yaml": "^4.1.1"

The ^4.1.1 range permitted any 4.x release but the highest available patched release in that line was 4.3.1. Because the lock file had resolved to 4.1.0 (note: the PR description references both 4.1.0 and ^4.1.1 — the lock file pinned the installed version), the quadratic flaw was active in the installed build.

The Fix

What changed

The fix touches two files:

1. .github/package.json — the version specifier was changed from a caret range to a pinned version:

// BEFORE
"js-yaml": "^4.1.1"

// AFTER
"js-yaml": "5.2.0"

Pinning to 5.2.0 (rather than ^4.3.1) makes the upgrade explicit and prevents the range resolver from silently downgrading to a vulnerable 4.x build in environments where the lock file is absent.

2. pnpm-lock.yaml — the lock file was regenerated to record the new resolved package and its integrity hash:

# AFTER — new entry added to snapshots
js-yaml@5.2.0:
  dependencies:
    argparse: 2.0.1
  resolution: {integrity: sha512-YeLUMlvR4Ou1B119LIaM0r65JvbOBooJDc9yEu0dClb...}
  hasBin: true

The .github importer block was also explicitly added so pnpm tracks the workspace's dependency resolution:

.github:
  dependencies:
    '@actions/core':
      specifier: ^3.0.1
      version: 3.0.1
    '@actions/github':
      specifier: ^9.1.1
      version: 9.1.1
    js-yaml:
      specifier: 5.2.0
      version: 5.2.0

Why the fix works

js-yaml 5.2.0 replaces the nested-loop duplicate-key check with a Set-based lookup, reducing the complexity from O(n²) to O(n):

// Conceptual representation of the patched approach
function resolveOmap(data) {
  const pairs = parsePairs(data);
  const seen = new Set();                  // O(1) lookup per key
  for (const pair of pairs) {
    if (seen.has(pair.key)) {
      throw new Error('duplicate key');
    }
    seen.add(pair.key);
  }
  return pairs;
}

A 50,000-entry !!omap document that previously caused ~5 billion comparisons now requires exactly 50,000 Set operations — a reduction of five orders of magnitude for that input size. Valid YAML documents parse identically; only the computational cost changes.

Prevention & Best Practices

1. Pin CI/CD dependencies, don't just range-lock them

Caret ranges like ^4.1.1 allow minor and patch upgrades automatically, which sounds safe but means a newly introduced vulnerability in 4.2.x would be silently adopted. For security-sensitive tools in CI/CD, pin to an exact version and automate upgrade PRs via Dependabot or Renovate.

2. Scan lock files, not just package.json

Trivy detected this vulnerability in pnpm-lock.yaml — the resolved version, not the declared range. Many scanners only analyze manifest files and miss the actual installed version. Ensure your pipeline scans lock files:

trivy fs --scanners vuln .github/pnpm-lock.yaml

3. Treat CI/CD dependency trees as production attack surface

Workflows that parse issue bodies, PR titles, release notes, or external API responses as YAML are directly reachable by external contributors or even anonymous users. Apply the same vulnerability management rigor to .github/ dependencies as to application code.

4. Apply input size limits when parsing untrusted YAML

Even with a patched parser, defense-in-depth suggests capping the size of YAML payloads before they reach the parser:

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

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 Dependency Check: Regularly audit third-party dependencies for known CVEs

Key Takeaways

• !!omap is a non-obvious attack surface: Most developers think of YAML DoS in terms of billion-laughs alias expansion; the !!omap duplicate-key check is a separate, less-known O(n²) path that exists in both 3.x and 4.x js-yaml branches.
• The .github/ dependency tree is a real attack surface: The vulnerable js-yaml was not in the application bundle — it was in CI/CD automation. Overlooking this subtree left a DoS primitive in the workflow infrastructure.
• Pinning to 5.2.0 instead of ^4.3.1 closes the window entirely: Rather than staying within the 4.x line where the fix was backported, upgrading to 5.2.0 moves to a branch with the Set-based fix as its original design.
• Lock file scanning caught what manifest scanning would miss: The declared range ^4.1.1 looks acceptable; it was only by scanning the resolved pnpm-lock.yaml that Trivy identified the actually-installed vulnerable version.
• Algorithmic complexity bugs are exploit primitives: Even if no direct exploit chain exists today, O(n²) parsing of attacker-controlled input is a building block that automated exploit-development tooling can leverage alongside other weaknesses.

How Orbis AppSec Detected This

• Source: YAML content supplied to js-yaml's load() / safeLoad() functions within GitHub Actions workflow scripts, potentially including externally-controlled data such as issue bodies or webhook payloads.
• Sink: The !!omap resolution path inside js-yaml@4.1.0 (as pinned in .github/pnpm-lock.yaml), which performs a nested O(n²) duplicate-key scan over attacker-supplied map entries.
• Missing control: No patched version of js-yaml was installed; the lock file resolved ^4.1.1 to 4.1.0, a version predating the algorithmic fix. No input size cap was applied before parsing.
• CWE: CWE-407 — Inefficient Algorithmic Complexity
• Fix: js-yaml was upgraded from ^4.1.1 to the pinned version 5.2.0 in .github/package.json, and pnpm-lock.yaml was regenerated to reflect the resolved, integrity-verified package.

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 algorithmic complexity vulnerabilities are not limited to regular-expression engines — any data structure operation with a hidden O(n²) path is a potential denial-of-service vector. In js-yaml, the !!omap duplicate-key check was that hidden path, silently present in both the 3.x and 4.x release lines until patched.

The fix here is surgical and low-risk: upgrade to 5.2.0, regenerate the lock file, and the quadratic behavior is replaced by a linear Set-based check. No valid YAML documents are affected. The change is entirely confined to the .github/ workspace, meaning zero impact on application behavior.

For teams managing JavaScript projects with YAML parsing in their toolchain — especially in CI/CD infrastructure — this is a good prompt to audit your own lock files and ensure you are running patched versions.

References

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