GHSA-724G-MXRG-4QVM
Vulnerability from github – Published: 2026-07-20 21:18 – Updated: 2026-07-20 21:18
VLAI
Summary
js-yaml: Quadratic-complexity (O(n^2)) DoS via !!omap tag in YAML11_SCHEMA
Details
Summary
js-yaml v5.x introduces YAML11_SCHEMA support with the !!omap (ordered map) tag. The omapTag.addItem() function performs a linear O(n) scan for duplicate key detection on every insertion, resulting in O(n^2) total time to parse a document with n omap entries. An attacker can send a small crafted YAML document to trigger a multi-second CPU stall in any application that uses yaml.load() with { schema: yaml.YAML11_SCHEMA }.
Details
In src/tag/sequence/omap.ts (compiled: dist/js-yaml.cjs.js:510-525):
var omapTag = defineSequenceTag('tag:yaml.org,2002:omap', {
create: () => [],
addItem: (container, item) => {
// ...
for (const existing of container) // O(n) per insertion!
if (hasOwnProperty(existing, itemKeys[0]))
return 'cannot resolve an ordered map item';
container.push(object); // n insertions → O(n^2) total
return '';
}
});
For a document with n unique entries, insertion i scans i−1 existing entries, yielding 1+2+…+n = O(n²) total work.
PoC (runtime-confirmed on v5.2.0)
const yaml = require('js-yaml');
function buildOmapPayload(n) {
let p = '!!omap\n';
for (let i = 0; i < n; i++) p += '- key' + i + ': val' + i + '\n';
return p;
}
// Timing results on v5.2.0:
// n=1000: 9ms
// n=5000: 73ms (5x n → 8x time)
// n=10000: 255ms (2x n → 3.5x time — supralinear)
// n=20000: 997ms (2x n → 3.9x time — O(n²) confirmed)
// n=50000: 10613ms ← blocks event loop for >10 seconds
yaml.load(buildOmapPayload(50000), { schema: yaml.YAML11_SCHEMA });
Impact
Any application that parses untrusted YAML using yaml.load(input, { schema: yaml.YAML11_SCHEMA }) is vulnerable to Denial of Service. A ~2 MB payload of 50,000 entries blocks the Node.js event loop for 10+ seconds. Smaller payloads (5,000 entries, ~100 KB) already cause noticeable slowdowns (73 ms per parse, amplified under concurrent load).
This affects the newly released 5.x series (first published 2026-06-20) which adds YAML 1.1/1.2 schema support including !!omap. The 4.x series is unaffected (no YAML11_SCHEMA export).
Fix
Replace the O(n) linear scan in addItem with an O(1) Set-based lookup:
var omapTag = defineSequenceTag('tag:yaml.org,2002:omap', {
create: () => ({ list: [], seen: new Set() }),
addItem: (state, item) => {
const key = Object.keys(item)[0];
if (state.seen.has(key)) return 'duplicate omap key';
state.seen.add(key);
state.list.push(item);
return '';
},
resolve: (state) => state.list
});
Severity
5.3 (Medium)
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 5.2.0"
},
"package": {
"ecosystem": "npm",
"name": "js-yaml"
},
"ranges": [
{
"events": [
{
"introduced": "5.0.0"
},
{
"fixed": "5.2.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-59870"
],
"database_specific": {
"cwe_ids": [
"CWE-407",
"CWE-770"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-20T21:18:51Z",
"nvd_published_at": "2026-07-08T16:16:33Z",
"severity": "MODERATE"
},
"details": "### Summary\n`js-yaml` v5.x introduces `YAML11_SCHEMA` support with the `!!omap` (ordered map) tag. The `omapTag.addItem()` function performs a linear O(n) scan for duplicate key detection on every insertion, resulting in O(n^2) total time to parse a document with n omap entries. An attacker can send a small crafted YAML document to trigger a multi-second CPU stall in any application that uses `yaml.load()` with `{ schema: yaml.YAML11_SCHEMA }`.\n\n### Details\nIn `src/tag/sequence/omap.ts` (compiled: `dist/js-yaml.cjs.js:510-525`):\n```js\nvar omapTag = defineSequenceTag(\u0027tag:yaml.org,2002:omap\u0027, {\n create: () =\u003e [],\n addItem: (container, item) =\u003e {\n // ...\n for (const existing of container) // O(n) per insertion!\n if (hasOwnProperty(existing, itemKeys[0]))\n return \u0027cannot resolve an ordered map item\u0027;\n container.push(object); // n insertions \u2192 O(n^2) total\n return \u0027\u0027;\n }\n});\n```\nFor a document with `n` unique entries, insertion i scans i\u22121 existing entries, yielding 1+2+\u2026+n = **O(n\u00b2)** total work.\n\n### PoC (runtime-confirmed on v5.2.0)\n```js\nconst yaml = require(\u0027js-yaml\u0027);\nfunction buildOmapPayload(n) {\n let p = \u0027!!omap\\n\u0027;\n for (let i = 0; i \u003c n; i++) p += \u0027- key\u0027 + i + \u0027: val\u0027 + i + \u0027\\n\u0027;\n return p;\n}\n// Timing results on v5.2.0:\n// n=1000: 9ms\n// n=5000: 73ms (5x n \u2192 8x time)\n// n=10000: 255ms (2x n \u2192 3.5x time \u2014 supralinear)\n// n=20000: 997ms (2x n \u2192 3.9x time \u2014 O(n\u00b2) confirmed)\n// n=50000: 10613ms \u2190 blocks event loop for \u003e10 seconds\nyaml.load(buildOmapPayload(50000), { schema: yaml.YAML11_SCHEMA });\n```\n\n### Impact\nAny application that parses untrusted YAML using `yaml.load(input, { schema: yaml.YAML11_SCHEMA })` is vulnerable to Denial of Service. A ~2 MB payload of 50,000 entries blocks the Node.js event loop for 10+ seconds. Smaller payloads (5,000 entries, ~100 KB) already cause noticeable slowdowns (73 ms per parse, amplified under concurrent load).\n\nThis affects the newly released 5.x series (first published 2026-06-20) which adds YAML 1.1/1.2 schema support including `!!omap`. The 4.x series is unaffected (no `YAML11_SCHEMA` export).\n\n### Fix\nReplace the O(n) linear scan in `addItem` with an O(1) `Set`-based lookup:\n```js\nvar omapTag = defineSequenceTag(\u0027tag:yaml.org,2002:omap\u0027, {\n create: () =\u003e ({ list: [], seen: new Set() }),\n addItem: (state, item) =\u003e {\n const key = Object.keys(item)[0];\n if (state.seen.has(key)) return \u0027duplicate omap key\u0027;\n state.seen.add(key);\n state.list.push(item);\n return \u0027\u0027;\n },\n resolve: (state) =\u003e state.list\n});\n```",
"id": "GHSA-724g-mxrg-4qvm",
"modified": "2026-07-20T21:18:51Z",
"published": "2026-07-20T21:18:51Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/nodeca/js-yaml/security/advisories/GHSA-724g-mxrg-4qvm"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59870"
},
{
"type": "WEB",
"url": "https://github.com/nodeca/js-yaml/commit/39f3211a2f01b3c6982710cf21434ab7060acefe"
},
{
"type": "PACKAGE",
"url": "https://github.com/nodeca/js-yaml"
},
{
"type": "WEB",
"url": "https://github.com/nodeca/js-yaml/releases/tag/5.2.1"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
"type": "CVSS_V3"
}
],
"summary": "js-yaml: Quadratic-complexity (O(n^2)) DoS via !!omap tag in YAML11_SCHEMA"
}
Loading…
Loading…
Experimental. This forecast is provided for visualization only and may change without notice. Do not use it for operational decisions.
Forecast uses a logistic model when the trend is rising, or an exponential decay model when the trend is falling. Fitted via linearized least squares.
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
Loading…
The MITRE ATT&CK techniques below are AI-generated suggestions, inferred from the description of the
vulnerability by the CIRCL/vulnerability-attack-technique-classification-roberta-base
model, served locally by ML-Gateway.
They have not been verified by an analyst and are provided for guidance only.
Loading…
Loading…