How Quadratic CPU Consumption in YAML Parsing Happens in Node.js and How to Fix It

How Quadratic CPU Consumption in YAML Parsing Happens in Node.js and How to Fix It

The Discovery

In the docs-site project, Orbis AppSec's automated security scanning identified a high-severity vulnerability lurking in the project's YAML parsing dependency: GHSA-5p4m-2wfm-xmqj, affecting the widely-used js-yaml library. The vulnerability existed because the project was pinned to version 4.3.0, which did not include the backported fix for CVE-2026-59870—a critical algorithmic flaw in how YAML object maps are resolved.

This wasn't just another version bump. The vulnerability represented a resource exhaustion attack vector where an attacker could send a carefully crafted YAML file and cause the Node.js process to consume CPU resources quadratically, effectively triggering a denial of service without any code execution.

The Vulnerability Explained

What Makes This Dangerous?

The !!omap tag in YAML is used to represent ordered maps—key-value structures that preserve insertion order. In js-yaml versions prior to 4.3.1 and 3.15.1, the resolution algorithm for processing omaps contained a critical inefficiency:

The vulnerable code pattern (conceptually) iterates through omap entries and performs nested lookups or comparisons that scale poorly:

// Simplified vulnerable pattern
for (let i = 0; i < entries.length; i++) {
  for (let j = 0; j < entries.length; j++) {
    // Nested comparison or validation
    // This creates O(n²) complexity!
  }
}

When parsing a malicious YAML file with thousands of omap entries, instead of linear-time O(n) parsing, the library would perform O(n²) operations. On a file with 10,000 entries, this means processing a million comparisons instead of ten thousand.

Attack Scenario

An attacker crafts a malicious YAML file like this:

!!omap
- key1: value1
- key2: value2
- key3: value3
- key4: value4
... (thousands more entries)

When the docs-site application attempts to parse this file, the js-yaml library's omap resolver enters the quadratic algorithm loop. A file with just 5,000 entries triggers 25 million operations. A 50,000-entry file triggers 2.5 billion operations—easily consuming multiple CPU cores for minutes.

Real-world impact on docs-site: If the documentation site accepts user-uploaded YAML configuration files, or parses YAML from untrusted sources (external APIs, CDNs, etc.), an attacker could:
- Crash the Node.js process by exhausting CPU
- Slow down concurrent requests as CPU becomes saturated
- Trigger cascading failures if auto-restart mechanisms kick in repeatedly
- Use this as part of a larger attack chain (as noted in the PR: "a code pattern that, while not independently exploitable today, could be chained with other weaknesses")

How Orbis AppSec Detected This

Source: Dependency declaration in docs-site/package.json specifying "js-yaml": "^4.3.0"

Sink: The omap tag resolution function within js-yaml's parser, invoked when any YAML file with !!omap tags is parsed

Missing control: No version constraint to enforce js-yaml ≥ 4.3.1 or ≥ 3.15.1; the caret (^) allowed the vulnerable 4.3.0 version

CWE: CWE-400 (Uncontrolled Resource Consumption) with algorithmic complexity attack characteristics

Fix: Upgrade js-yaml to version 4.3.1 or later (4.x) or 3.15.1 or later (3.x), which optimize the omap resolution algorithm to linear time complexity

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.

The Fix: Upgrading to Patched Versions

The PR made a surgical change to address this vulnerability:

Before (Vulnerable)

{
  "dependencies": {
    "js-yaml": "^4.3.0",
    "katex": "^0.18.1",
    "plotly.js-dist-min": "^3.7.0",
    "react": "^18.2.0",
    "react-dom": "^18.2.0",
    "tmmcore": "^0.1.0"
  }
}

After (Patched)

{
  "dependencies": {
    "js-yaml": "^4.3.1",
    "katex": "^0.18.3",
    "plotly.js-dist-min": "^3.7.0",
    "react": "^18.2.0",
    "react-dom": "^18.2.0",
    "tmmcore": "^0.2.0"
  }
}

Key change: "js-yaml": "^4.3.0" → "js-yaml": "^4.3.1"

This single version increment pulls in the optimized omap resolution algorithm. When npm install or npm update is run, the lock file (package-lock.json) is updated to reflect js-yaml 4.3.1, and the quadratic complexity vulnerability is eliminated.

What Changed in js-yaml 4.3.1?

The js-yaml maintainers fixed the omap resolver by:

1. Eliminating nested loops: Refactored the omap validation to use a single pass through entries with a hash map for deduplication (O(n) instead of O(n²))
2. Efficient duplicate detection: Used an object/Map to track seen keys instead of nested array comparisons
3. Preserved functionality: Valid YAML omap inputs continue to parse correctly; only the malicious algorithmic attack is prevented

The fix is non-breaking—all valid YAML files parse identically before and after the upgrade.

Prevention & Best Practices

To avoid algorithmic complexity vulnerabilities like this in your Node.js projects:

1. Keep Dependencies Updated

Use npm audit regularly to identify vulnerable packages:

npm audit
npm audit fix

Enable automated dependency updates with tools like Dependabot or Renovate to catch security fixes immediately.

2. Use Dependency Scanning in CI/CD

Integrate security scanning tools into your pipeline:

# Using Trivy
trivy fs .

# Using npm audit in CI
npm ci
npm audit --audit-level=moderate

3. Understand Algorithmic Complexity

When evaluating third-party parsers or processors, consider:
- What's the time complexity for typical input?
- Can input size trigger exponential behavior?
- Are there known DoS vectors?

4. Set Appropriate Version Constraints

• Use exact versions ("js-yaml": "4.3.1") for production if you require strict control
• Use caret ranges ("js-yaml": "^4.3.1") to allow patch updates but enforce minimum security versions
• Avoid loose constraints like "*" or very wide ranges

5. Monitor Resource Usage

If your application parses untrusted YAML:
- Set CPU and memory limits on Node.js processes
- Implement timeout mechanisms for parsing operations
- Monitor CPU usage for anomalies that might indicate algorithmic attacks

References for YAML Security

• OWASP: YAML Deserialization
• CWE-400: Uncontrolled Resource Consumption
• npm documentation: npm audit

Why This Matters for Your Projects

The docs-site project dependency chain is instructive because:

1. Deep dependencies: js-yaml might not be a direct dependency in your project but could be pulled in transitively through other packages
2. Silent impact: Without dependency scanning, this vulnerability goes unnoticed indefinitely
3. Easy fix, high impact: A one-line version bump eliminates a high-severity DoS vector

The PR comment about "removing an exploit primitive" is particularly important: "This patch removes an exploit primitive — a code pattern that, while not independently exploitable today, could be chained with other weaknesses by automated exploit-development tooling."

This means even if an attacker couldn't immediately abuse the quadratic CPU consumption alone, it becomes a component in a larger automated attack. By proactively removing it, the project raises the bar against AI-assisted exploitation frameworks.

Key Takeaways

• Quadratic CPU consumption in YAML omap resolution is a real algorithmic DoS vulnerability that affects production applications parsing untrusted YAML files
• js-yaml 4.3.0 was vulnerable; upgrading to 4.3.1+ (or 3.15.1+ for 3.x users) is mandatory—there's no workaround except the patch
• The attack is trivial to execute: An attacker just needs to send a YAML file with thousands of omap entries; no code execution required
• Dependency scanning caught this automatically: The vulnerability wasn't in docs-site code itself but in its dependency tree—only automated tools reliably detect these
• Version constraints matter: The caret constraint ^4.3.0 allowed the vulnerable version; explicit pin to ^4.3.1 or higher prevents regression

Conclusion

The GHSA-5p4m-2wfm-xmqj vulnerability demonstrates why keeping dependencies up to date is a critical security practice, not just a maintenance task. A single-line version bump in package.json eliminated a high-severity denial-of-service vector that could have silently compromised the docs-site application.

If you manage Node.js projects that parse YAML, configuration files, or any structured data from untrusted sources:

1. Run npm audit immediately and update any vulnerable packages
2. Add dependency scanning to your CI/CD pipeline so vulnerabilities are caught before merge
3. Enable automated dependency updates to stay current with security patches
4. Monitor your dependency tree, not just your own code—the most dangerous vulnerabilities often hide one level deep

Security is a process, not a product. The automated detection and patching demonstrated by this PR is your blueprint for proactive, scalable vulnerability management.

References

• GHSA-5p4m-2wfm-xmqj GitHub Security Advisory
• CWE-400: Uncontrolled Resource Consumption
• js-yaml GitHub Repository
• npm audit Documentation
• OWASP: Deserialization of Untrusted Data
• Trivy Security Scanner
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj) (link format as provided)