roxmltree Quadratic-time XML Parsing DoS: O(n²) Attribute & Namespace Checks (CWE-407/1333)

Vulnerability Overview Title: Quadratic-time XML parsing DoS: duplicate-attribute & namespace-declaration checks are O(n²) (CWE-407/CWE-1333) Issue: (and / ) exhibits O(n²) runtime when parsing XML containing a large number of duplicate attributes or namespace declarations, leading to a single-threaded CPU-exhaustion Denial of Service (DoS). Root Cause: 1. Duplicate Attribute Detection ( , ): Each attribute is compared against all previously pushed attributes within the same element. The number of comparisons is n(n-1)/2. 2. Namespace Declaration Deduplication ( , / ): performs a linear scan of , and additionally performs (O(n) shifts). When a single element has a large number of namespaces, this also results in O(n²) complexity. Scope of Impact: - Affected Versions: Unfixed since 1.0.0 (2022), persists in 0.20.0 and 0.21.1. - Affected Components: , , and in roxmltree. - Impact Surface: All downstream consumers of untrusted XML (SVG pipelines, EPUB readers, xmllint-docx tools, sitemap parsers, etc.). - Memory Usage: 100% safe (no memory growth); purely CPU-compute-bound DoS. - Mitigation Measures: roxmltree has no hard limits, and no related CVE or advisory has been issued. - Reporter: Mo (trickyfalcon), locally verified on 2026-09-11. POC / Reproduction Code Valid XML, parsing succeeds (no error path triggered): Extrapolation: 256k attributes (8.7 MB) ≈ 50 s; 1M attributes (34 MB) ≈ 12 min single-core CPU. Proposed Fix Duplicate Attributes: Maintain a small Vec (≤16 items) as a semi-deduplicated set for each element, then switch to or a sorted Vec + binary search (O(n log n) or O(n)). Namespaces: Use a small per-element map for ; replace with one using double pointers or quicksort (O(n) insertion). Defense in Depth: Set a configurable limit on the number of attributes/namespaces per element (following the existing unique namespace limit). Alternative Under Discussion: Hard caps are considered the most reasonable mitigation measure, as the input, while technically valid, is unrealistic. Rejecting such input is simpler than maintaining hash tables; roxmltree currently has no hard caps.

Goal Reached Thanks to every supporter — we hit 100%!

roxmltree Quadratic-time XML Parsing DoS: O(n²) Attribute & Namespace Checks (CWE-407/1333)

More from this source