Quadratic run time when checking a start tag for duplicate attribute names
| Details |
|
| Package |
quick-xml |
| Version |
0.37.5 |
| URL |
tafia/quick-xml#969 |
| Date |
2026-06-29 |
| Patched versions |
>=0.41.0 |
BytesStart::attributes() returns an Attributes iterator which, by default
(with_checks(true)), rejects a start tag that repeats an attribute name. For
each attribute yielded, the iterator compared the new name against every name
seen so far in the same tag using a linear scan, so a start tag with N
distinct attribute names cost O(N²) byte comparisons. There was no bound on
N other than the size of the buffered start tag.
Impact
Any code that parses untrusted XML and iterates a start tag's attributes with
the default duplicate check enabled can be made to spend CPU time quadratic in
the number of attributes on a single tag. Because the check is pure computation
with no .await/I/O, an I/O-based timeout on the consumer (for example a read
or request timeout) cannot interrupt it while it runs.
Measured cost of a single start tag, release build:
| Attributes on one tag |
Time |
| 80,000 |
~6 s |
| 800,000 |
~10 min |
The cost grows with the square of the attribute count, so a start tag of a few
tens of megabytes can stall a parsing thread for hours. No memory is exhausted
and the parser does not crash; the effect is CPU exhaustion on the thread doing
the parsing: a single crafted start tag can pin a CPU core for minutes to hours,
denying service to that worker. A deployment that places a wall-clock bound on
parsing, or confines it to a non-critical thread, may consider the availability
impact lower.
Affected code paths
BytesStart::attributes() / Attributes iterated with checks enabled (the
default), and BytesStart::try_get_attribute.NsReader, which resolves namespaces by iterating a tag's attributes and so
reaches the same check internally.
Consumers that iterate attributes with .attributes().with_checks(false) and do
not use NsReader are not affected.
This was reported as reachable by a remote, unauthenticated attacker in a
real-world RPKI relying party (NLnet Labs Routinator) via a crafted RRDP
snapshot.xml.
Remediation
Upgrade to quick-xml >= 0.41.0, where the duplicate check keeps the linear
scan for start tags with a small number of attributes and switches to an O(1)
hash pre-filter above a threshold, making the whole tag O(N). The reported
AttrError::Duplicated positions are unchanged.
If upgrading is not possible and duplicate-name detection is not required,
disable it with .attributes().with_checks(false) (this does not help
NsReader consumers, which have no equivalent opt-out before 0.41.0).
See advisory page for additional details.
quick-xml0.37.5>=0.41.0BytesStart::attributes()returns anAttributesiterator which, by default(
with_checks(true)), rejects a start tag that repeats an attribute name. Foreach attribute yielded, the iterator compared the new name against every name
seen so far in the same tag using a linear scan, so a start tag with
Ndistinct attribute names cost
O(N²)byte comparisons. There was no bound onNother than the size of the buffered start tag.Impact
Any code that parses untrusted XML and iterates a start tag's attributes with
the default duplicate check enabled can be made to spend CPU time quadratic in
the number of attributes on a single tag. Because the check is pure computation
with no
.await/I/O, an I/O-based timeout on the consumer (for example a reador request timeout) cannot interrupt it while it runs.
Measured cost of a single start tag, release build:
The cost grows with the square of the attribute count, so a start tag of a few
tens of megabytes can stall a parsing thread for hours. No memory is exhausted
and the parser does not crash; the effect is CPU exhaustion on the thread doing
the parsing: a single crafted start tag can pin a CPU core for minutes to hours,
denying service to that worker. A deployment that places a wall-clock bound on
parsing, or confines it to a non-critical thread, may consider the availability
impact lower.
Affected code paths
BytesStart::attributes()/Attributesiterated with checks enabled (thedefault), and
BytesStart::try_get_attribute.NsReader, which resolves namespaces by iterating a tag's attributes and soreaches the same check internally.
Consumers that iterate attributes with
.attributes().with_checks(false)and donot use
NsReaderare not affected.This was reported as reachable by a remote, unauthenticated attacker in a
real-world RPKI relying party (NLnet Labs Routinator) via a crafted RRDP
snapshot.xml.Remediation
Upgrade to
quick-xml >= 0.41.0, where the duplicate check keeps the linearscan for start tags with a small number of attributes and switches to an
O(1)hash pre-filter above a threshold, making the whole tag
O(N). The reportedAttrError::Duplicatedpositions are unchanged.If upgrading is not possible and duplicate-name detection is not required,
disable it with
.attributes().with_checks(false)(this does not helpNsReaderconsumers, which have no equivalent opt-out before 0.41.0).See advisory page for additional details.