Description

xmldom: Quadratic-time parsing via the malformed-input recovery path — parseElementStartPart re-scan and normalize() adjacent-text merge ## 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 < character is not a delimiter in any tag-parsing state, so parseElementStartPart scans forward character-by-character over any embedded < until it reaches the next > (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 < and a distant >, 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< / 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, '<r>' + 'a<'.repeat(N) + '</r>', 'text/xml'); // Finding B: short re-scans (cheap parse) but K adjacent text nodes -> O(K^2) in normalize(). timeParse('B N=' + N, '<r>' + 'a<>'.repeat(N) + '</r>', 'text/html'); // Combined: ONE input hits both A and B under the default parser. timeParse('C N=' + N, '<r>' + 'a<'.repeat(N) + '</r>', '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 ("<r>" + "a<"×N + "</r>", 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 ("<r>" + "a<>"×N + "</r>", time attributable to normalize()): | K (N) | input bytes | 0.9.10 | 0.8.13 | |--:|--:|--:|--:| | 4000 | 12007 | 120 ms | 165 ms | | 8000 | 24007 | 589 ms | 771 ms | | 16000 | 48007 | 3142 ms |

Mitigation

Aliases

References