Understanding the Threat: Quadratic Complexity in YAML Parsing
In November 2024, security researchers identified a critical vulnerability in the popular JS-YAML library—a package downloaded millions of times weekly by Node.js developers. The issue wasn't in how YAML is parsed, but rather in how efficiently certain YAML structures are processed. Specifically, the !!omap (ordered map) tag resolver contained an algorithmic weakness that could be weaponized into a denial-of-service attack.
What makes this vulnerability particularly insidious is that it doesn't require code injection, authentication bypass, or data corruption—just a specifically crafted YAML file that exploits the computational complexity of the parser itself.
The Vulnerability Explained: Inefficient Ordered Map Resolution
What's an OMAP in YAML?
In YAML, the !!omap tag represents an ordered mapping—a data structure that preserves insertion order. Unlike regular YAML maps, omaps guarantee that key order is maintained, which is useful for configuration files and data interchange where order matters.
A typical YAML omap looks like this:
!!omap
- first_key: value1
- second_key: value2
- third_key: value3
This is a legitimate and widely-used YAML feature. However, JS-YAML's implementation of omap resolution contained a hidden performance trap.
The Algorithmic Flaw
The vulnerability lies in how JS-YAML validates and constructs omap structures. The resolver needed to ensure that each key in the omap was unique and properly ordered. However, the implementation used a nested loop pattern that compared each new key against all previously seen keys—a classic O(n²) algorithm.
Here's the problematic pattern (conceptual, from the vulnerable js-yaml 4.3.0):
// Vulnerable pattern: nested loop checking
for (let i = 0; i < pairs.length; i++) {
for (let j = 0; j < i; j++) {
// Compare pairs[i] against pairs[j]
if (pairs[i].key === pairs[j].key) {
// duplicate detection
}
}
}
With 1,000 omap entries, this performs roughly 500,000 comparisons. With 10,000 entries, it performs 50 million comparisons. An attacker can craft YAML with hundreds of thousands of omap entries, forcing the parser to perform billions of operations—consuming CPU until the service becomes unresponsive.
Real-World Attack Scenario
Imagine a Node.js API that accepts YAML configuration uploads:
// Vulnerable service code
const yaml = require('js-yaml');
app.post('/config', (req, res) => {
try {
const config = yaml.load(req.body); // Parses untrusted YAML
applyConfig(config);
res.json({ status: 'success' });
} catch (e) {
res.status(400).json({ error: e.message });
}
});
An attacker sends a 5MB YAML file with 100,000 omap entries:
!!omap
- entry_0: value_0
- entry_1: value_1
- entry_2: value_2
# ... repeated thousands of times
- entry_99999: value_99999
The JS-YAML parser enters the quadratic loop, consuming 100% CPU for 30+ seconds. The service becomes unresponsive to all users. Repeat requests amplify the effect, crashing the server entirely. This is a classic algorithmic complexity denial-of-service attack.
Why This Matters for JS-YAML Users
JS-YAML is a fundamental building block in the Node.js ecosystem:
- Configuration management tools parse YAML configs
- CI/CD pipelines process workflow files in YAML
- API gateways validate YAML policies
- Kubernetes tools process YAML manifests
- Logging and monitoring systems ingest YAML data
Any service that parses untrusted YAML with JS-YAML 4.3.0 or 3.15.0 is vulnerable to this DoS attack.
The Fix: Algorithm Optimization
What Changed in JS-YAML 4.3.1 and 3.15.1
The patch replaced the inefficient nested-loop pattern with an optimized approach using hash-based lookups. Instead of comparing each new entry against all previous entries in a loop, the fixed version uses a JavaScript Set or Map to track seen keys—an O(1) lookup operation.
Here's the conceptual before and after:
Before (4.3.0 - Vulnerable):
function resolveOmap(data) {
const pairs = [];
for (let i = 0; i < data.length; i++) {
const pair = data[i];
// O(n) check: compare against all previous pairs
for (let j = 0; j < pairs.length; j++) {
if (pairs[j][0] === pair[0]) {
throw new Error('Duplicate key');
}
}
pairs.push(pair);
}
return pairs;
}
// Time complexity: O(n²)
After (4.3.1 - Optimized):
function resolveOmap(data) {
const pairs = [];
const seen = new Set(); // O(1) lookup structure
for (let i = 0; i < data.length; i++) {
const pair = data[i];
// O(1) check: hash-based lookup
if (seen.has(pair[0])) {
throw new Error('Duplicate key');
}
seen.add(pair[0]);
pairs.push(pair);
}
return pairs;
}
// Time complexity: O(n)
The improvement is dramatic: parsing 100,000 omap entries now completes in milliseconds instead of seconds.
Actual Package Changes
The fix is implemented in your dependency tree through a version bump:
"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==",
+ "version": "4.3.2",
+ "resolved": "https://registry.npmjs.org/js-yaml/-/js-yaml-4.3.2.tgz",
+ "integrity": "sha512-SFNOvSJ+Dgf/9An904Yx+CgSlIPCkIpao4qo51lpee25TIRejdH3rhR4EZMGoNx3/TP3O+wzWuiTFl4sqbltzA==",
}
Update Action Required:
1. Update your package.json to require js-yaml@^4.3.1 or js-yaml@^3.15.1
2. Run npm install or npm ci to update package-lock.json
3. No code changes are required—the fix is transparent to your application
Why Both 3.x and 4.x Were Patched
JS-YAML maintains two active branches:
- 3.x (stable): Used by legacy projects and conservative deployments
- 4.x (current): Newer API, active development
The vulnerability affected both branches identically because both inherited the same inefficient omap resolver. The patches (3.15.1 and 4.3.1) address the same algorithmic flaw in both code paths.
Prevention & Best Practices
1. Always Validate Input Size
Even with the fix, never blindly parse arbitrary YAML without size limits:
const MAX_YAML_SIZE = 1024 * 1024; // 1MB limit
app.post('/config', (req, res) => {
if (req.body.length > MAX_YAML_SIZE) {
return res.status(413).json({ error: 'Payload too large' });
}
try {
const config = yaml.load(req.body);
applyConfig(config);
res.json({ status: 'success' });
} catch (e) {
res.status(400).json({ error: e.message });
}
});
2. Implement Parsing Timeouts
Use timeouts to detect unexpectedly slow parsing operations:
const parseWithTimeout = (input, timeoutMs = 5000) => {
return new Promise((resolve, reject) => {
const timer = setTimeout(
() => reject(new Error('YAML parsing timeout')),
timeoutMs
);
try {
const result = yaml.load(input);
clearTimeout(timer);
resolve(result);
} catch (e) {
clearTimeout(timer);
reject(e);
}
});
};
// Usage
try {
const config = await parseWithTimeout(req.body);
} catch (e) {
res.status(408).json({ error: 'Parsing timeout' });
}
3. Use Safe YAML Loading Options
JS-YAML provides different load functions for safety levels:
// Safest: only basic YAML types, no tags
const config = yaml.load(input, {
schema: yaml.FAILSAFE_SCHEMA // Restricts available tags
});
// Safer: standard types with no arbitrary function execution
const config = yaml.load(input, {
schema: yaml.SAFE_SCHEMA // Default safe mode
});
// Avoid unless you trust the input completely
const config = yaml.load(input, {
schema: yaml.UNSAFE_SCHEMA // Can execute arbitrary code
});
4. Monitor for Algorithmic Complexity Attacks
Implement metrics to detect unusual parser behavior:
const yaml = require('js-yaml');
const parseWithMetrics = (input) => {
const startTime = process.hrtime.bigint();
const startMem = process.memoryUsage().heapUsed;
try {
const result = yaml.load(input);
const duration = Number(process.hrtime.bigint() - startTime) / 1e6; // ms
const memDelta = process.memoryUsage().heapUsed - startMem;
// Log suspicious patterns
if (duration > 1000) {
console.warn(`Slow YAML parse: ${duration}ms, size: ${input.length} bytes`);
}
if (memDelta > 50 * 1024 * 1024) {
console.warn(`Large memory allocation: ${memDelta / 1024 / 1024}MB`);
}
return result;
} catch (e) {
throw e;
}
};
5. Keep Dependencies Updated
Use automated dependency scanning tools:
# Check for vulnerabilities
npm audit
# Fix automatically
npm audit fix
# Keep js-yaml specifically updated
npm outdated js-yaml
References for Algorithmic Complexity Attacks
- CWE-407: Algorithmic Complexity - https://cwe.mitre.org/data/definitions/407.html
- CWE-1333: Inefficient Regular Expression Complexity - https://cwe.mitre.org/data/definitions/1333.html
- OWASP Algorithmic Complexity: https://owasp.org/www-community/attacks/Algorithmic_Complexity
Key Takeaways
-
Quadratic algorithms hide in resolvers: The omap resolver looked straightforward but contained nested loops that became expensive at scale. Always review nested iteration in parsing logic.
-
Size alone doesn't indicate safety: A 5MB YAML file with 100,000 entries can be crafted to be smaller than a benign 10MB config. Input size limits alone won't prevent algorithmic DoS.
-
Hash-based lookups are essential: When validating uniqueness in lists, always use Set or Map data structures instead of nested loops. This is a foundational optimization in parser design.
-
Both maintained branches needed patching: Upgrading to 4.3.1 isn't enough if your transitive dependencies use 3.x. Verify your entire dependency tree includes the patched versions.
-
Timeouts are a safety net: Even with algorithmic fixes, implement parsing timeouts as a defense-in-depth measure against future complexity bugs.
How Orbis AppSec Detected This
Source: YAML data from configuration files, API requests, or CI/CD workflows processed by yaml.load() in user applications
Sink: The !!omap tag resolver in js-yaml's lib/type/pairs.js calling inefficient array comparison operations during tag resolution
Missing Control: No algorithmic complexity validation; no hash-based duplicate detection; the resolver assumed O(n²) performance was acceptable for all input sizes
CWE: CWE-407 (Algorithmic Complexity)
Fix: Replaced nested-loop key comparison with Set-based O(1) duplicate detection in the omap resolver, reducing overall complexity from O(n²) to O(n)
Orbis AppSec automatically detected this vulnerability in your dependency tree and opened a pull request with the fix. The security scanner identified that js-yaml 4.3.0 was present in package-lock.json and flagged GHSA-5p4m-2wfm-xmqj as a known high-severity issue. The automated fix upgraded the package to 4.3.2, which includes the algorithmic optimization. Try Orbis AppSec on your repositories to find and fix issues like this automatically.
Conclusion
The quadratic complexity vulnerability in JS-YAML's omap resolver demonstrates a critical security principle: efficiency and security are intertwined. Code that appears functionally correct can harbor performance vulnerabilities that attackers exploit for denial-of-service attacks.
By upgrading to JS-YAML 4.3.1 or 3.15.1, you eliminate an algorithmic complexity attack vector and reduce resource consumption for all users. But the broader lesson applies to all parsers and resolvers: algorithmic efficiency during parsing is a security property, not just a performance optimization.
Make dependency updates a routine practice in your development workflow. Tools like Orbis AppSec can automate this, but awareness is your first defense. Review your package-lock.json today, ensure js-yaml is at version 4.3.2 (or 3.15.1), and deploy the update promptly.