{"id":"GHSA-93r5-fhx6-vmg9","summary":"xmldom: Quadratic-time parsing via the malformed-input recovery path — `parseElementStartPart` re-scan and `normalize()` adjacent-text merge","details":"## Summary\n\n`xmldom`'s malformed-input **error-recovery path** has two quadratic-time (O(n²)) behaviors that a\nsingle crafted input triggers together, so a tiny, highly compressible document (tens of KB) stalls\nthe Node.js event loop for multiple seconds. It is reachable from `DOMParser.parseFromString` under\n**default options** — i.e. from unauthenticated, network-delivered XML — making this an unauthenticated\ndenial of service. One of the two behaviors, the `normalize()` adjacent-text merge, is **additionally\nreachable programmatically** — via a plain `normalize()` call on a DOM built with adjacent text nodes,\nindependent of the parser — so its fix must live in `normalize()`, not only in a parser bound.\n\n## Details\n\n### Finding A — `parseElementStartPart` quadratic re-scan\n\nA `\u003c` character is not a delimiter in any tag-parsing state, so `parseElementStartPart` scans\nforward character-by-character over any embedded `\u003c` until it reaches the next `\u003e` (or end of\ninput), then validates the accumulated slice as a tag name and throws `invalid tagName:` on failure.\nThe main loop catches this, reports an `error`, sets `end = -1`, and recovers by advancing a single\ncharacter (`appendText(Math.max(tagStart, start) + 1)`). With a long run of `\u003c` and a distant `\u003e`,\neach of the O(n) recovery retries performs an O(n) scan plus an O(n) anchored regex validation over\nthe growing candidate ⇒ **O(n²)**.\n\nCode (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`):\n\n- `parseElementStartPart` character scan — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L263-L461\n- tag-name validation (`setTagName` → throws `invalid tagName`) — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L886-L891\n- main-loop `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L234-L242\n- single-character recovery fallback — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L247\n\nCode (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`):\n\n- `parseElementStartPart` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L227\n- `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L202-L208\n- recovery fallback — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L213\n- `setTagName` validation — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L616-L621\n\n### Finding B — `normalize()` adjacent-text O(K²) merge\n\n`endDocument()` calls `document.normalize()`. For a parent with K adjacent text nodes (produced by\nthe one-character recovery of Finding A), `normalize()` performs K−1 merges. Each merge does a\n`removeChild` — which re-indexes **all** child nodes of the parent (O(K)) — and an `appendData` —\nwhich rebuilds the accumulator string `this.data + text` (O(K)). Total: **O(K²)**.\n\nWell-formed XML cannot produce adjacent text-node siblings *through the parser* (each text run is one\nnode; comments, CDATA, PIs, and elements sit between runs), so the **parse-path** trigger for Finding B\nis the malformed-input recovery that emits single-character text nodes. The same O(K²) merge is,\nhowever, independently reachable via the public `normalize()` API on a programmatically built tree\n(see \"Finding B is additionally reachable programmatically\" below).\n\nCode (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`):\n\n- `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom-parser.js#L418-L420\n- `normalize()` adjacent-text merge — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1336-L1356\n- `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1788-L1798\n- `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L2786-L2790\n\nCode (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`):\n\n- `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom-parser.js#L213-L214\n- `normalize()` merge — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L529-L549\n- `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L756-L773\n- `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L1533\n\n### Finding B is additionally reachable programmatically (no parser involved)\n\n`Node.prototype.normalize()` is public API on every `Document`/`Element`. A tree built entirely through\nthe ordinary DOM API — `new DOMImplementation().createDocument(...)`, then K× `createTextNode` +\n`appendChild` on one parent — reaches the **same** O(K²) merge when the application calls `normalize()`,\nwith **no** parsing and **no** error-recovery. The parser is only *one* of the two callers of the\nvulnerable merge:\n\n- the parser's automatic `endDocument()` → `document.normalize()` (the parse-path trigger above), and\n- any explicit application call to the public `normalize()` on a tree with adjacent text nodes.\n\n`XMLSerializer` does **not** call `normalize()`, so serializing an un-merged tree is O(total text), not\nO(K²); the O(K²) surface is exactly those two `normalize()` callers. Consequently a parser-side bound\nalone cannot remediate Finding B — the fix must live in `normalize()`.\n\n## Affected Versions\n\nBoth findings are present across the full published `@xmldom/xmldom` history — both\ncurrently-maintained versions (`0.8.x` and `0.9.x`) are affected — and across the retired unscoped\n`xmldom` line. Finding B's `normalize()` merge is additionally reachable **programmatically**: a\ndirect `normalize()` call on a DOM built with adjacent text nodes hits the same O(K²) merge,\nindependent of the parser — so, unlike Finding A, it does not require the malformed-input recovery\npath.\n\n## Proof of Concept\n\nDefault `DOMParser`, no options. The input is trivially compressible (`a\u003c` / `a\u003c\u003e` repeated) and\nnever throws — it is parsed via the recovery path.\n\n```js\nconst { DOMParser } = require('@xmldom/xmldom');\n\n// Silence the expected `error`-level recovery reports (default handler logs\n// them to console.error without throwing; only fatalError throws).\nconsole.error = function () {};\n\nfunction timeParse(label, xml, mime) {\n  const t0 = process.hrtime.bigint();\n  new DOMParser().parseFromString(xml, mime); // completes; no exception\n  const ms = Number(process.hrtime.bigint() - t0) / 1e6;\n  console.log(label + '  bytes=' + Buffer.byteLength(xml) + '  time=' + ms.toFixed(1) + ' ms');\n}\n\nfor (const N of [4000, 8000, 16000, 32000]) {\n  // Finding A: long re-scans, O(n^2) during parse.\n  timeParse('A N=' + N, '\u003cr\u003e' + 'a\u003c'.repeat(N) + '\u003c/r\u003e', 'text/xml');\n  // Finding B: short re-scans (cheap parse) but K adjacent text nodes -\u003e O(K^2) in normalize().\n  timeParse('B N=' + N, '\u003cr\u003e' + 'a\u003c\u003e'.repeat(N) + '\u003c/r\u003e', 'text/html');\n  // Combined: ONE input hits both A and B under the default parser.\n  timeParse('C N=' + N, '\u003cr\u003e' + 'a\u003c'.repeat(N) + '\u003c/r\u003e', 'text/xml');\n}\n```\n\nMeasured on Node v18.20.8 (absolute ms vary by host; the load-bearing fact is that doubling the\ninput ~quadruples the time — canonical O(n²)):\n\nFinding A, isolated (`\"\u003cr\u003e\" + \"a\u003c\"×N + \"\u003c/r\u003e\"`, normalize disabled to isolate the re-scan):\n\n| N | input bytes | `@xmldom/xmldom` 0.9.10 | 0.8.13 |\n|--:|--:|--:|--:|\n| 2000 | 4007 | 43 ms | 37 ms |\n| 4000 | 8007 | 129 ms | 106 ms |\n| 8000 | 16007 | 434 ms | 424 ms |\n| 16000 | 32007 | 1629 ms | 1611 ms |\n\nFinding B, isolated (`\"\u003cr\u003e\" + \"a\u003c\u003e\"×N + \"\u003c/r\u003e\"`, time attributable to `normalize()`):\n\n| K (N) | input bytes | 0.9.10 | 0.8.13 |\n|--:|--:|--:|--:|\n| 4000 | 12007 | 120 ms | 165 ms |\n| 8000 | 24007 | 589 ms | 771 ms |\n| 16000 | 48007 | 3142 ms | 4448 ms |\n| 32000 | 96007 | 12127 ms | 12951 ms |\n\nCombined (default parser, both findings; `\"\u003cr\u003e\" + \"a\u003c\"×N + \"\u003c/r\u003e\"`):\n\n| N | input bytes | 0.9.10 | 0.8.13 |\n|--:|--:|--:|--:|\n| 4000 | 8007 | 341 ms | 397 ms |\n| 8000 | 16007 | 1894 ms | 1641 ms |\n| 16000 | 32007 | 4398 ms | 7661 ms |\n\n~32 KB of input → several seconds of single-threaded event-loop stall.\n\n### Finding B via the public `normalize()` API (no parser)\n\n```js\nconst { DOMImplementation } = require('@xmldom/xmldom');\n\nfunction timeNormalize(K) {\n  const doc = new DOMImplementation().createDocument(null, 'r', null);\n  const el = doc.documentElement;\n  for (let i = 0; i \u003c K; i++) el.appendChild(doc.createTextNode('x')); // K adjacent text nodes\n  const t0 = process.hrtime.bigint();\n  doc.normalize();                                    // O(K^2) merge — no parsing involved\n  const ms = Number(process.hrtime.bigint() - t0) / 1e6;\n  console.log('K=' + K + '  time=' + ms.toFixed(1) + ' ms');\n}\nfor (const K of [2000, 4000, 8000, 16000, 32000]) timeNormalize(K);\n```\n\nMeasured on Node v18.20.8 (doubling K ~quadruples the time — O(K²)):\n\n| K | 0.9.10 | 0.8.13 |\n|--:|--:|--:|\n| 2000 | 5.7 ms | 5.6 ms |\n| 32000 | 1263 ms | 1704 ms |\n\nThis path is reachable by any application that builds a DOM from attacker-influenced data and calls\n`normalize()`, entirely independent of `DOMParser`.\n\n## Impact\n\nAvailability only: a single parse of a small crafted document blocks the Node.js event loop for the\nduration of the quadratic work (multiple seconds at tens of KB; larger inputs scale as O(n²)). No\nmemory blow-up beyond transient strings, no data exposure, no integrity impact. Because XML is\nroutinely accepted from untrusted sources and parsed with default options, one request can stall a\nserver. The payloads are highly compressible, so any endpoint accepting compressed XML faces\nadditional amplification. Finding B is additionally reachable via an explicit `normalize()` call on a\nprogrammatically built DOM (see Proof of Concept), so applications that construct a document from attacker-influenced\ndata and normalize it are exposed even without parsing.\n\n## Severity note\n\nThe complexity is **quadratic**, not exponential, so a multi-second stall requires\ntens-to-hundreds of KB of input. `VA:H` reflects that xmldom applies **no** input-size limit and the\npath runs on default-options parsing, so a single unbounded parse can fully stall the event loop.\n\n## Fix Applied\n\nTwo independent, non-breaking fixes shipped together — each alone leaves the other's quadratic cost dominating the default parse.\nFinding A — terminate the malformed tag-name scan at an embedded `\u003c`, so error recovery is linear instead of O(n²). DOM output is unchanged; only the reported error-message text differs (error strings are not a semver contract).\nFinding B — merge adjacent text nodes in `normalize()` in O(K) instead of O(K²), which also closes the same slowdown reachable programmatically through a direct `normalize()` call. Both ship on both maintained versions.","aliases":["CVE-2026-83614"],"modified":"2026-09-08T21:15:04.187745360Z","published":"2026-09-08T21:00:41Z","database_specific":{"cwe_ids":["CWE-400","CWE-407"],"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"2026-09-08T21:00:41Z","nvd_published_at":"2026-09-01T15:17:39Z"},"references":[{"type":"WEB","url":"https://github.com/xmldom/xmldom/security/advisories/GHSA-93r5-fhx6-vmg9"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-83614"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/pull/1071"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/pull/1072"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/commit/0748720b620555f8c222782dcab575cf0cf403b4"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/commit/f40ccb861eee0acbf5ee4feb9a34932e87b329c9"},{"type":"PACKAGE","url":"https://github.com/xmldom/xmldom"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/releases/tag/0.8.15"},{"type":"WEB","url":"https://github.com/xmldom/xmldom/releases/tag/0.9.12"}],"affected":[{"package":{"name":"@xmldom/xmldom","ecosystem":"npm","purl":"pkg:npm/%40xmldom/xmldom"},"ranges":[{"type":"SEMVER","events":[{"introduced":"0.7.0"},{"fixed":"0.8.15"}]}],"database_specific":{"last_known_affected_version_range":"\u003c= 0.8.14","source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-93r5-fhx6-vmg9/GHSA-93r5-fhx6-vmg9.json"}},{"package":{"name":"@xmldom/xmldom","ecosystem":"npm","purl":"pkg:npm/%40xmldom/xmldom"},"ranges":[{"type":"SEMVER","events":[{"introduced":"0.9.0"},{"fixed":"0.9.12"}]}],"database_specific":{"last_known_affected_version_range":"\u003c= 0.9.11","source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-93r5-fhx6-vmg9/GHSA-93r5-fhx6-vmg9.json"}},{"package":{"name":"xmldom","ecosystem":"npm","purl":"pkg:npm/xmldom"},"ranges":[{"type":"SEMVER","events":[{"introduced":"0.3.0"},{"last_affected":"0.6.0"}]}],"database_specific":{"source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-93r5-fhx6-vmg9/GHSA-93r5-fhx6-vmg9.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V4","score":"CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N"}]}