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

Introduction

In a recent security scan of package-lock.json, Trivy identified a high-severity vulnerability in the js-yaml dependency. The application was using js-yaml version 4.3.0, which contains a critical algorithmic complexity flaw in how it resolves !!omap (ordered map) YAML types.

This vulnerability, tracked as GHSA-5p4m-2wfm-xmqj, represents a classic denial-of-service vector where the fix for CVE-2026-59870 was not properly backported to the 3.x and 4.x branches. The problematic code pattern affects any application that parses YAML documents from untrusted sources—a common scenario in configuration management, API endpoints, and data import features.

The vulnerable dependency was pinned at version 4.3.0:

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

The Vulnerability Explained

What is !!omap and Why Does It Matter?

In YAML, !!omap is a special type tag that represents an ordered mapping—essentially an array of key-value pairs that preserves insertion order. Unlike regular YAML mappings (which are unordered), ordered maps guarantee that keys appear in a specific sequence.

When js-yaml encounters a !!omap type, it must:
1. Parse each key-value pair
2. Validate that keys are unique (ordered maps cannot have duplicate keys)
3. Build the resulting data structure

The Quadratic Complexity Bug

The vulnerability exists in the uniqueness validation step. In affected versions, the algorithm used to check for duplicate keys has O(n²) time complexity. For each new key added to the ordered map, the code iterates through all previously added keys to check for duplicates.

Consider this pseudocode representation of the vulnerable pattern:

// Vulnerable pattern (simplified)
function resolveOmap(data) {
  const result = [];
  for (const pair of data) {
    const key = Object.keys(pair)[0];
    // O(n) lookup for EACH of n items = O(n²) total
    for (const existing of result) {
      if (Object.keys(existing)[0] === key) {
        throw new Error('Duplicate key in omap');
      }
    }
    result.push(pair);
  }
  return result;
}

Attack Scenario

An attacker can craft a malicious YAML document with a large !!omap containing thousands of unique keys:

--- !!omap
- key0001: value
- key0002: value
- key0003: value
# ... thousands more unique keys ...
- key9999: value

With 10,000 keys, the vulnerable algorithm performs approximately 50 million comparisons (n × (n-1) / 2). This can freeze a Node.js event loop for seconds or even minutes, effectively denying service to all users of the application.

Real-World Impact

For this specific application, any endpoint or feature that accepts YAML input becomes a denial-of-service vector. Common attack surfaces include:

• Configuration file uploads
• API endpoints accepting YAML payloads
• CI/CD pipeline configurations
• Data import/export features
• Webhook handlers processing YAML

A single malicious request could exhaust server CPU resources, causing timeouts for legitimate users and potentially triggering cascading failures in distributed systems.

The Fix

The fix was straightforward but critical: upgrade js-yaml from version 4.3.0 to 4.3.1, where the !!omap resolution algorithm has been optimized to use a Set or Map for O(1) key lookups, reducing overall complexity from O(n²) to O(n).

Before (Vulnerable)

// package-lock.json
"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=="
}

After (Fixed)

// 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=="
}

Package Override Addition

The fix also added an explicit override in package.json to ensure transitive dependencies also use the patched version:

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

This override is crucial because js-yaml is often pulled in as a transitive dependency by other packages. Without the override, a nested dependency could still use the vulnerable version.

Why This Fix Works

The patched version 4.3.1 replaces the nested loop with a hash-based lookup:

// Fixed pattern (simplified)
function resolveOmap(data) {
  const result = [];
  const seenKeys = new Set();  // O(1) lookups
  for (const pair of data) {
    const key = Object.keys(pair)[0];
    if (seenKeys.has(key)) {  // O(1) instead of O(n)
      throw new Error('Duplicate key in omap');
    }
    seenKeys.add(key);
    result.push(pair);
  }
  return result;
}

This reduces the total time complexity from O(n²) to O(n), making the parser resilient to large inputs.

Prevention & Best Practices

1. Keep Dependencies Updated

Regularly update your dependencies and monitor security advisories. Use tools like:
- npm audit for vulnerability scanning
- Dependabot or Renovate for automated updates
- Trivy for container and dependency scanning

2. Implement Input Limits

Even with patched libraries, implement defense-in-depth:

const yaml = require('js-yaml');

function parseYamlSafely(input, maxSize = 1024 * 1024) {
  if (input.length > maxSize) {
    throw new Error('YAML input exceeds maximum allowed size');
  }
  return yaml.load(input, { schema: yaml.SAFE_SCHEMA });
}

3. Use Safe Schemas

js-yaml provides different schemas with varying levels of type support:

// Prefer SAFE_SCHEMA when possible - it excludes potentially dangerous types
const data = yaml.load(input, { schema: yaml.SAFE_SCHEMA });

4. Add Parsing Timeouts

For critical applications, wrap parsing in a timeout:

const { setTimeout } = require('timers/promises');

async function parseWithTimeout(input, timeoutMs = 5000) {
  const parsePromise = new Promise((resolve, reject) => {
    try {
      resolve(yaml.load(input));
    } catch (e) {
      reject(e);
    }
  });

  return Promise.race([
    parsePromise,
    setTimeout(timeoutMs).then(() => {
      throw new Error('YAML parsing timeout');
    })
  ]);
}

5. Lock Transitive Dependencies

Use npm overrides or yarn resolutions to ensure all instances of a vulnerable package are updated:

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

Key Takeaways

• Never assume YAML parsing is cheap: The !!omap type in js-yaml 4.3.0 had O(n²) complexity, making it a DoS vector even for moderately-sized inputs
• Transitive dependencies need explicit overrides: The package.json override for js-yaml ensures nested dependencies also use the patched version
• Algorithmic complexity attacks bypass traditional input validation: A 100KB YAML file is small by most standards but can contain enough !!omap entries to freeze a server
• Security scanners catch what manual review misses: Trivy identified this vulnerability in package-lock.json automatically
• Defense-in-depth matters: Even with patched libraries, implement input size limits and parsing timeouts

How Orbis AppSec Detected This

• Source: YAML input processed by the application (configuration files, API payloads, or data imports)
• Sink: js-yaml.load() or js-yaml.loadAll() calls using the vulnerable !!omap type resolver in node_modules/js-yaml
• Missing control: The js-yaml 4.3.0 library lacked an efficient algorithm for duplicate key detection in ordered maps
• CWE: CWE-400 (Uncontrolled Resource Consumption) / CWE-1333 (Inefficient Regular Expression Complexity)
• Fix: Upgraded js-yaml from 4.3.0 to 4.3.1 in both package-lock.json and added an override in package.json to ensure consistent patching across all dependency trees

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 !!omap quadratic complexity vulnerability (GHSA-5p4m-2wfm-xmqj) demonstrates how algorithmic inefficiencies in widely-used libraries can create serious security risks. What appears to be a simple YAML parsing operation can become a denial-of-service vector when attackers understand the underlying implementation details.

The fix—upgrading to js-yaml 4.3.1—is simple, but the broader lesson is more nuanced: dependency management is a critical security practice. Automated scanning tools like Trivy catch these issues before they reach production, and automated patching ensures fixes are applied consistently across your codebase.

Keep your dependencies updated, implement defense-in-depth with input validation and timeouts, and trust but verify your parsing libraries' performance characteristics.

References

• CWE-400: Uncontrolled Resource Consumption
• CWE-1333: Inefficient Regular Expression Complexity
• OWASP Denial of Service Cheat Sheet
• js-yaml Documentation
• npm audit Documentation
• Semgrep YAML Security Rules
• fix: upgrade js-yaml to 4.3.1, 3.15.1 (GHSA-5p4m-2wfm-xmqj)