How Quadratic CPU Consumption Vulnerabilities Happen in JavaScript YAML Parsers and How to Fix Them

Introduction

In a Node.js project's package-lock.json, we discovered a high-severity denial-of-service vulnerability lurking in the js-yaml dependency. The project was using js-yaml version 4.1.1 as a direct dependency and version 3.14.2 as a transitive dependency through @istanbuljs/load-nyc-config. Both versions contained GHSA-5p4m-2wfm-xmqj, a vulnerability that allows attackers to freeze applications by sending specially crafted YAML documents.

This isn't a theoretical risk—any application that parses YAML from untrusted sources (configuration files, API payloads, user uploads) could be completely locked up by a relatively small malicious input. The vulnerability stems from how js-yaml resolves the !!omap (ordered map) YAML tag, using an algorithm with quadratic time complexity that an attacker can exploit.

The Vulnerability Explained

What is the !!omap Tag?

YAML supports ordered maps through the !!omap tag, which guarantees that keys maintain their insertion order. When js-yaml parses an !!omap, it must verify that all keys are unique—a fundamental requirement for valid ordered maps.

The Quadratic Complexity Problem

The vulnerable versions of js-yaml (4.1.1 and 3.14.2) used an inefficient algorithm for duplicate key detection. Instead of using a hash-based lookup (O(1) per check, O(n) total), the implementation compared each new key against all previously seen keys (O(n) per check, O(n²) total).

Here's what the problematic pattern looks like conceptually:

// Vulnerable approach (simplified)
function checkDuplicates(keys) {
  for (let i = 0; i < keys.length; i++) {
    for (let j = 0; j < i; j++) {
      if (keys[i] === keys[j]) {
        throw new Error('Duplicate key');
      }
    }
  }
}

With 1,000 keys, this performs ~500,000 comparisons. With 10,000 keys, it performs ~50,000,000 comparisons. An attacker can craft a YAML document that triggers this worst-case behavior.

Attack Scenario

Consider this application that processes user-submitted configuration:

const yaml = require('js-yaml'); // version 4.1.1

app.post('/api/config', (req, res) => {
  try {
    const config = yaml.load(req.body.yamlContent);
    // Process configuration...
    res.json({ success: true });
  } catch (e) {
    res.status(400).json({ error: 'Invalid YAML' });
  }
});

An attacker could submit a YAML document like:

--- !!omap
- key_00001: value
- key_00002: value
- key_00003: value
# ... thousands more unique keys ...
- key_50000: value

Even though all keys are unique (no actual duplicates), the quadratic duplicate-checking algorithm would consume massive CPU time verifying this. A document with 50,000 keys could lock up the Node.js event loop for minutes, effectively causing a denial of service for all users.

Real-World Impact

For this specific project, the vulnerability existed in two places:

1. Direct dependency: js-yaml@4.1.1 used for parsing application configuration
2. Dev dependency: js-yaml@3.14.2 pulled in by @istanbuljs/load-nyc-config for code coverage configuration

While the dev dependency only affects the build/test environment, the direct dependency poses a production risk if the application processes any YAML from external sources.

The Fix

The fix upgrades both vulnerable js-yaml instances to patched versions that implement efficient O(n) duplicate detection.

Before (Vulnerable)

// package.json
"dependencies": {
  "js-yaml": "^4.1.1",
  // ...
}

// package-lock.json
"node_modules/js-yaml": {
  "version": "4.1.1",
  "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.1.1.tgz",
  // ...
}

"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",
  // ...
}

After (Fixed)

// package.json
"dependencies": {
  "js-yaml": "^4.3.1",
  // ...
}

// package-lock.json
"node_modules/js-yaml": {
  "version": "4.3.1",
  "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.3.1.tgz",
  "integrity": "sha512-CY6crGq313MX8GkwvB7tzgp99vjQxY1++5y10/BKN/GUfHqWaOGQMNZkBvqSzsZKWk/ijwHlWzzkLulsGHhjWQ==",
  // ...
}

"node_modules/@istanbuljs/load-nyc-config/node_modules/js-yaml": {
  "version": "3.15.1",
  "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-3.15.1.tgz",
  "integrity": "sha512-S99WuO3HlhO3XN41EtYUNl9zzXjoJx7QvmipxsJVxtCBT0YHEFy+iOJhjSvrmV12nYhWpZaM8lPHkJm0yUMbag==",
  // ...
}

Why Both Files Changed

1. package.json: Updates the declared dependency range from ^4.1.1 to ^4.3.1, ensuring new installs get the patched version
2. package-lock.json: Locks the exact resolved versions (4.3.1 and 3.15.1) and updates integrity hashes, ensuring reproducible builds with the secure versions

The patched versions replace the O(n²) comparison loop with a hash-based Set lookup:

// Fixed approach (simplified)
function checkDuplicates(keys) {
  const seen = new Set();
  for (const key of keys) {
    if (seen.has(key)) {
      throw new Error('Duplicate key');
    }
    seen.add(key);
  }
}

This reduces 50,000,000 operations back down to 50,000—a 1000x improvement that eliminates the denial-of-service vector.

Prevention & Best Practices

1. Keep Dependencies Updated

Use automated dependency scanning tools to catch vulnerable packages:

# npm audit
npm audit

# Or use dedicated security scanners
trivy fs --scanners vuln .

2. Implement Parsing Timeouts

Even with patched libraries, defense in depth matters:

const { Worker } = require('worker_threads');

function parseYamlWithTimeout(content, timeoutMs = 5000) {
  return new Promise((resolve, reject) => {
    const worker = new Worker(`
      const yaml = require('js-yaml');
      const { parentPort } = require('worker_threads');
      parentPort.on('message', (content) => {
        parentPort.postMessage(yaml.load(content));
      });
    `, { eval: true });

    const timeout = setTimeout(() => {
      worker.terminate();
      reject(new Error('YAML parsing timeout'));
    }, timeoutMs);

    worker.on('message', (result) => {
      clearTimeout(timeout);
      resolve(result);
    });

    worker.postMessage(content);
  });
}

3. Limit Input Size

Reject oversized YAML documents before parsing:

const MAX_YAML_SIZE = 1024 * 1024; // 1MB

app.post('/api/config', (req, res) => {
  if (req.body.yamlContent.length > MAX_YAML_SIZE) {
    return res.status(413).json({ error: 'YAML document too large' });
  }
  // Parse YAML...
});

4. Use Dependabot or Renovate

Configure automated dependency updates to catch security patches quickly:

# .github/dependabot.yml
version: 2
updates:
  - package-ecosystem: "npm"
    directory: "/"
    schedule:
      interval: "daily"
    open-pull-requests-limit: 10

Key Takeaways

• js-yaml versions before 4.3.1 and 3.15.1 contain a DoS vulnerability in !!omap resolution that can freeze your application
• Transitive dependencies matter: The vulnerability existed in both direct and dev dependencies through @istanbuljs/load-nyc-config
• Algorithmic complexity attacks bypass input validation: The malicious YAML is syntactically valid, so schema validation won't help
• Both package.json AND package-lock.json must be updated to ensure the fix is applied consistently across environments
• Defense in depth is essential: Even with patched libraries, implement timeouts and size limits for parsing untrusted input

How Orbis AppSec Detected This

• Source: YAML content from external input (configuration files, API payloads)
• Sink: yaml.load() call in application code using vulnerable js-yaml versions
• Missing control: No patched version of js-yaml that implements efficient duplicate key detection
• CWE: CWE-407 (Inefficient Algorithmic Complexity)
• Fix: Upgraded js-yaml from 4.1.1 to 4.3.1 and from 3.14.2 to 3.15.1 in package.json and package-lock.json

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

The js-yaml quadratic CPU consumption vulnerability (GHSA-5p4m-2wfm-xmqj) demonstrates how algorithmic complexity issues can turn seemingly innocent parsing operations into denial-of-service vectors. By upgrading to js-yaml 4.3.1 (or 3.15.1 for the 3.x branch), you eliminate this attack surface while maintaining full backward compatibility for valid YAML documents.

Remember that dependency security is an ongoing process. Automated scanning tools like Trivy, combined with proactive dependency management, help ensure vulnerabilities like this are caught and fixed before they can be exploited. Always treat YAML parsing of untrusted input as a potential attack vector and implement appropriate safeguards.

References

• CWE-407: Inefficient Algorithmic Complexity
• OWASP Denial of Service Cheat Sheet
• js-yaml npm package
• GitHub Advisory GHSA-5p4m-2wfm-xmqj
• Semgrep YAML security rules
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj)