800k Attributes Pins a CPU for 10 Minutes in Rust's quick-xml

800,000 attributes on a single XML start tag stalls a CPU core for 10 minutes—pure math, no disk or network involved.

That's the quadratic time bomb in quick-xml, a popular Rust XML parsing library. The advisory (RUSTSEC-0000-0000) filed in the RustSec advisory-db lays out exactly how a linear scan for duplicate attribute names turns a crafted tag into a denial-of-service weapon.

How a Linear Scan Becomes a Quadratic CPU Trap

BytesStart::attributes() returns an Attributes iterator. By default, with_checks(true), it rejects a start tag with a repeated attribute name. The problem: for each attribute yielded, the iterator compared the new name against every name seen so far using a linear scan. A start tag with N distinct attribute names costs O(N²) byte comparisons, with no bound on N beyond the size of the buffered tag.

Measured costs from the advisory, release build:

Because the check is pure computation with no .await or I/O, an I/O-based timeout—like a read or request timeout—cannot interrupt it while it runs. A start tag of a few tens of megabytes can pin a parsing thread for hours, exhausting no memory, just CPU.

Real-World Exploit Path: Routinator and RRDP

This isn't theoretical. The advisory notes the bug was reported as reachable by a remote, unauthenticated attacker in a real-world RPKI relying party: NLnet Labs Routinator. The attack vector is a crafted RRDP snapshot.xml. One XML file, one crafted tag, and a core spins for minutes to hours.

Affected code paths include BytesStart::attributes() with checks enabled (the default) and BytesStart::try_get_attribute. NsReader is also vulnerable because it resolves namespaces by iterating a tag's attributes internally, hitting the same check.

The Fix: O(1) Pre-Filter Above a Threshold

Upgrade to quick-xml >= 0.41.0. The fix keeps the linear scan for start tags with a small number of attributes, then switches to an O(1) hash pre-filter above a threshold. That makes the whole tag O(N) instead of O(N²). The reported AttrError::Duplicated positions remain unchanged.

If you can't upgrade and don't need duplicate-name detection, you can disable it with .attributes().with_checks(false)—but that doesn't help NsReader consumers, which have no equivalent opt-out before 0.41.0.

Every XML parser that does a pairwise uniqueness check on attributes should take notes. This is the kind of algorithmic complexity bug that flies under the radar until someone sends you an 800,000-attribute tag.

Source: Add advisory for quick-xml: quadratic attribute duplicate-check (CPU ...
Domain: github.com