How Quadratic CPU Consumption Happens in js-yaml and How to Fix It

Introduction

The package-lock.json file in this project pinned js-yaml at version 4.1.1, a widely-used YAML parser for Node.js applications. While js-yaml handles configuration files, API responses, and data serialization across countless applications, a flaw in its !!omap (ordered map) type resolution created a severe denial-of-service vulnerability. An attacker who could supply YAML input to the application could craft a document that would cause the parser to consume quadratic CPU time, effectively freezing the Node.js event loop.

This vulnerability, tracked as GHSA-5p4m-2wfm-xmqj and related to CVE-2026-59870, affects both the 3.x and 4.x branches of js-yaml. The fix was not automatically backported to older versions, leaving applications on version 4.1.1 exposed until explicitly upgraded.

The Vulnerability Explained

What is !!omap in YAML?

YAML supports custom type tags that instruct parsers how to interpret data. The !!omap tag represents an ordered map—a sequence of key-value pairs where order matters. Here's what valid !!omap YAML looks like:

!!omap
- first: 1
- second: 2
- third: 3

The Quadratic Complexity Problem

The vulnerable versions of js-yaml (prior to 4.3.1 and 3.15.1) implemented the !!omap resolution with an algorithm that had O(n²) time complexity. When parsing an ordered map, the code would perform nested iterations to validate uniqueness of keys or maintain ordering guarantees. For each of the n entries, it would iterate through up to n other entries.

For small inputs, this is imperceptible. But consider what happens with malicious input:

An attacker could craft a YAML document with thousands of !!omap entries. When parsed by the vulnerable js-yaml version, this would:

1. Block the Node.js event loop during parsing
2. Consume 100% CPU on the parsing thread
3. Prevent the application from handling any other requests
4. Potentially trigger watchdog timeouts or container restarts

Attack Scenario

Imagine this application accepts YAML configuration uploads or processes YAML-formatted webhook payloads. An attacker submits:

!!omap
- key0: value0
- key1: value1
- key2: value2
# ... repeated 10,000 times
- key9999: value9999

The js-yaml 4.1.1 parser begins processing this document. Due to the quadratic resolution algorithm, parsing takes exponentially longer as the document grows. A document that would parse in milliseconds with a linear algorithm now takes minutes or hours, effectively denying service to all users.

The Fix

What Changed

The fix involves two coordinated changes to upgrade js-yaml from 4.1.1 to 4.3.1:

Before (package-lock.json):

"node_modules/js-yaml": {
  "version": "4.1.1",
  "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.1.1.tgz",
  "integrity": "sha512-qQKT4zQxXl8lLwBtHMWwaTcGfFOZviOJet3Oy/xmGk2gZH677CJM9EvtfdSkgWcATZhj/55JZ0rmy3myCT5lsA==",

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

Before (package.json overrides):

"overrides": {
  "basic-ftp": "5.3.1"
}

After (package.json overrides):

"overrides": {
  "basic-ftp": "5.3.1",
  "js-yaml": "4.3.1"
}

Why the Override?

The overrides field in package.json is crucial here. js-yaml might be a transitive dependency—pulled in by other packages in the dependency tree. Simply updating a direct dependency wouldn't force nested dependencies to use the patched version. The override ensures that every instance of js-yaml in the entire dependency tree uses version 4.3.1, regardless of what version other packages request.

How 4.3.1 Fixes the Issue

Version 4.3.1 of js-yaml includes a rewritten !!omap resolution algorithm with O(n) time complexity. The fix likely uses a hash-based data structure (like a JavaScript Set or Map) for key uniqueness checks instead of nested array iterations, reducing the algorithmic complexity from quadratic to linear.

Prevention & Best Practices

Dependency Management

1. Use lockfile scanning: Tools like Trivy, Snyk, or npm audit can detect known vulnerable versions in your dependency tree
2. Implement npm overrides: When transitive dependencies are vulnerable, use overrides to force patched versions
3. Regular updates: Schedule regular dependency updates rather than waiting for security alerts

Input Handling

1. Size limits: Implement maximum document size limits before parsing YAML
2. Timeouts: Wrap parsing operations in timeouts to prevent indefinite blocking
3. Sandboxing: Consider parsing untrusted YAML in worker threads or separate processes

Code Example: Safe YAML Parsing

const yaml = require('js-yaml'); // Must be 4.3.1+
const { setTimeout } = require('timers/promises');

async function safeYamlParse(input, maxSize = 1024 * 1024) {
  // Limit input size
  if (input.length > maxSize) {
    throw new Error('YAML document exceeds maximum size');
  }

  // Parse with timeout protection
  const parsePromise = new Promise((resolve, reject) => {
    try {
      resolve(yaml.load(input));
    } catch (e) {
      reject(e);
    }
  });

  const timeoutPromise = setTimeout(5000).then(() => {
    throw new Error('YAML parsing timeout');
  });

  return Promise.race([parsePromise, timeoutPromise]);
}

Key Takeaways

• Transitive dependencies matter: The vulnerable js-yaml 4.1.1 was in the dependency tree, requiring npm overrides to ensure all instances were upgraded
• Algorithmic complexity is a security concern: O(n²) algorithms on untrusted input create denial-of-service attack surfaces
• YAML's type system expands attack surface: Custom type tags like !!omap introduce parsing complexity that can be exploited
• Version pinning requires active maintenance: The lockfile pinned a specific version, but security patches require explicit upgrades
• Defense in depth: Even with patched libraries, implement input size limits and parsing timeouts for untrusted data

How Orbis AppSec Detected This

• Source: YAML document input parsed by the application (potentially from user uploads, API requests, or configuration files)
• Sink: yaml.load() call using js-yaml 4.1.1 in the dependency tree
• Missing control: Patched library version with linear-time !!omap resolution
• CWE: CWE-407 (Inefficient Algorithmic Complexity)
• Fix: Upgraded js-yaml to 4.3.1 via package.json overrides, ensuring all instances in the dependency tree use the patched version with O(n) resolution

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

This js-yaml vulnerability demonstrates how algorithmic complexity in trusted libraries can create severe security risks. The quadratic CPU consumption in !!omap resolution might seem like an obscure edge case, but it represents a real denial-of-service vector for any application processing untrusted YAML.

The fix was straightforward—a version upgrade with npm overrides—but required awareness that the vulnerability existed and affected transitive dependencies. This underscores the importance of automated dependency scanning and proactive security patching in modern JavaScript applications.

When working with YAML parsing or any data serialization format, always consider: What happens when an attacker controls the input? Libraries like js-yaml are battle-tested, but even well-maintained projects occasionally ship algorithmic vulnerabilities. Keep your dependencies updated, implement defense in depth, and never assume that parsing untrusted input is safe without additional protections.

References

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