GHSA-93r5-fhx6-vmg9 xmldom: Quadratic-time parsing via the malformed-input recovery path — `parseElementStartPart` re-scan and `normalize()` adjacent-text merge

• npm @xmldom/xmldom: >= 0.7.0, < 0.8.15 → fixed in 0.8.15 • npm @xmldom/xmldom: >= 0.9.0, < 0.9.12 → fixed in 0.9.12 • npm xmldom: >= 0.3.0, <= 0.6.0 (no fix yet)

Summary `xmldom`'s malformed-input error-recovery path has two quadratic-time (O(n²)) behaviors that a single crafted input triggers together, so a tiny, highly compressible document (tens of KB) stalls the Node.js event loop for multiple seconds. It is reachable from `DOMParser.parseFromString` under default options — i.e. from unauthenticated, network-delivered XML — making this an unauthenticated denial of service. One of the two behaviors, the `normalize()` adjacent-text merge, is additionally reachable programmatically — via a plain `normalize()` call on a DOM built with adjacent text nodes, independent of the parser — so its fix must live in `normalize()`, not only in a parser bound. Details Finding A — `parseElementStartPart` quadratic re-scan A `` (or end of input), then validates the accumulated slice as a tag name and throws `invalid tagName:` on failure. The main loop catches this, reports an `error`, sets `end = -1`, and recovers by advancing a single character (`appendText(Math.max(tagStart, start) + 1)`). With a long run of ``, each of the O(n) recovery retries performs an O(n) scan plus an O(n) anchored regex validation over the growing candidate ⇒ O(n²). Code (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`): • `parseElementStartPart` character scan — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L263-L461 • tag-name validation (`setTagName` → throws `invalid tagName`) — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L886-L891 • main-loop `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L234-L242 • single-character recovery fallback — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/sax.js#L247 Code (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`): • `parseElementStartPart` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L227 • `catch` → `error` + `end = -1` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L202-L208 • recovery fallback — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L213 • `setTagName` validation — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/sax.js#L616-L621 Finding B — `normalize()` adjacent-text O(K²) merge `endDocument()` calls `document.normalize()`. For a parent with K adjacent text nodes (produced by the one-character recovery of Finding A), `normalize()` performs K−1 merges. Each merge does a `removeChild` — which re-indexes all child nodes of the parent (O(K)) — and an `appendData` — which rebuilds the accumulator string `this.data + text` (O(K)). Total: O(K²). Well-formed XML cannot produce adjacent text-node siblings *through the parser* (each text run is one node; comments, CDATA, PIs, and elements sit between runs), so the parse-path trigger for Finding B is the malformed-input recovery that emits single-character text nodes. The same O(K²) merge is, however, independently reachable via the public `normalize()` API on a programmatically built tree (see "Finding B is additionally reachable programmatically" below). Code (0.9.x, `bb7a085dc5ba1eea3212388509b97bb4b4af32b9`): • `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom-parser.js#L418-L420 • `normalize()` adjacent-text merge — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1336-L1356 • `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L1788-L1798 • `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/bb7a085dc5ba1eea3212388509b97bb4b4af32b9/lib/dom.js#L2786-L2790 Code (0.8.x, `e5c14802592685bb872c042c54c3f73758875c85`): • `endDocument` → `normalize()` — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom-parser.js#L213-L214 • `normalize()` merge — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L529-L549 • `removeChild` re-index-all branch — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L756-L773 • `appendData` string rebuild — https://github.com/xmldom/xmldom/blob/e5c14802592685bb872c042c54c3f73758875c85/lib/dom.js#L1533 Finding B is additionally reachable programmatically (no parser involved) `Node.prototype.normalize()` is public API on every `Document`/`Element`. A tree built entirely through the ordinary DOM API — `new DOMImplementation().createDocument(...)`, then K× `createTextNode` + `appendChild` on one parent — reaches the same O(K²) merge when the application calls `normalize()`, with no parsing and no error-recovery. The parser is only *one* of the two callers of the vulnerable merge: • the parser's automatic `endDocument()` → `document.normalize()` (the parse-path trigger above), and • any explicit application call to the public `normalize()` on a tree with adjacent text nodes. `XMLSerializer` does not call `normalize()`, so serializing an un-merged tree is O(total text), not O(K²); the O(K²) surface is exactly those two `normalize()` callers. Consequently a parser-side bound alone cannot remediate Finding B — the fix must live in `normalize()`. Affected Versions Both findings are present across the full published `@xmldom/xmldom` history — both currently-maintained versions (`0.8.x` and `0.9.x`) are affected — and across the retired unscoped `xmldom` line. Finding B's `normalize()` merge is additionally reachable programmatically: a direct `normalize()` call on a DOM built with adjacent text nodes hits the same O(K²) merge, independent of the parser — so, unlike Finding A, it does not require the malformed-input recovery path. Proof of Concept Default `DOMParser`, no options. The input is trivially compressible (`a` repeated) and never throws — it is parsed via the recovery path. ```js const { DOMParser } = require('@xmldom/xmldom'); // Silence the expected `error`-level recovery reports (default handler logs // them to console.error without throwing; only fatalError throws). console.error = function () {}; function timeParse(label, xml, mime) { const t0 = process.hrtime.bigint(); new DOMParser().parseFromString(xml, mime); // completes; no exception const ms = Number(process.hrtime.bigint() - t0) / 1e6; console.log(label + ' bytes=' + Buffer.byteLength(xml) + ' time=' + ms.toFixed(1) + ' ms'); } for (const N of [4000, 8000, 16000, 32000]) { // Finding A: long re-scans, O(n^2) during parse. timeParse('A N=' + N, '' + 'a', 'text/xml'); // Finding B: short re-scans (cheap parse) but K adjacent text nodes -> O(K^2) in normalize(). timeParse('B N=' + N, '' + 'a<>'.repeat(N) + '', 'text/html'); // Combined: ONE input hits both A and B under the default parser. timeParse('C N=' + N, '' + 'a', 'text/xml'); } ``` Measured on Node v18.20.8 (absolute ms vary by host; the load-bearing fact is that doubling the input ~quadruples the time — canonical O(n²)): Finding A, isolated (`"" + "a"`, normalize disabled to isolate the re-scan): | N | input bytes | `@xmldom/xmldom` 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 2000 | 4007 | 43 ms | 37 ms | | 4000 | 8007 | 129 ms | 106 ms | | 8000 | 16007 | 434 ms | 424 ms | | 16000 | 32007 | 1629 ms | 1611 ms | Finding B, isolated (`"" + "a<>"×N + ""`, time attributable to `normalize()`): | K (N) | input bytes | 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 4000 | 12007 | 120 m…