Repository navigation
2.7.18.16: ElementPath index predicates are O(n^2) (CVE-2026-6879) - #101
Merged
Merged
Conversation
…ates (CVE-2026-6879) Backport of python/cpython pythongh-152674 (2ffab08) to 2.7.18.x. For an index predicate ([1], [last()], [last()-N]) ElementPath called parent.findall(elem.tag) once per candidate element, so findall() and a fully consumed iterfind() over n same-tag siblings did O(n^2) work. A crafted document plus a query like ".//item[last()]" could burn CPU. select() now caches the selected sibling per (parent, tag) pair. 2.7.18.x: cElementTree's find()/findall() also go through this Python ElementPath module, so the fix covers both implementations. The test counts findall() calls through an Element subclass; cElementTree's Element is a factory function in 2.7 and cannot be subclassed, so the test is skipped there. super(Class, self) and %-formatting replace the 3.x spellings. Without the fix, findall() calls grow as 1025/2049/4097 for 1024/2048/4096 siblings; with it they are constant. Co-Authored-By: Claude Opus 5.5 <[email protected]>
ezequielp-activestate
approved these changes
Oct 28, 2026
ezequielp-activestate
left a comment
ezequielp-activestate
left a comment
There was a problem hiding this comment.
No blockers. The change is upstream's pythongh-152674 fix (2ffab08). The only difference is a harmless list(), and ElementPath.py hasn't changed upstream since.
-
Repro:
findallwithc[1],c[last()]andc[last()-3]over N same-tag siblings:N base this branch 1,024 3,075 findallcalls, 0.9 s6 calls, 0.01 s 4,096 12,291 calls, 22 s 6 calls, 0.04 s 16,384 49,155 calls, 458 s 6 calls, 0.15 s -
Correctness: on 300 random trees, index predicates (
[1],[2],[last()],[last()-1],*/b[1],.//*[1]) give the same elements as a naive reference, on both base and this branch. -
Tests:
test_xml_etreeandtest_xml_etree_cpass. The new test fails against the baseElementPath.py.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Backport of python/cpython pythongh-152674 (CVE-2026-6879, PSF-2026-34) to 2.7.18.x.
Problem: for index predicates (
[1],[last()],[last()-N]), ElementPath calledparent.findall(elem.tag)once for every candidate element. That makesfindall()/iterfind()quadratic in the number of same-tag siblings.Fix: cache the selected sibling for each
(parent, tag)pair.2.7 notes:
find()/findall()also go through this PythonElementPath, so the fix covers both implementations.Elementis a factory function in 2.7 and can't be subclassed.Test:
test_find_xpath_index_no_quadratic_complexity.findallcalls grow as 1025/2049/4097 for 1024/2048/4096 siblings, so the test fails.test_xml_etreeandtest_xml_etree_cpass.Part of 2.7.18.16. It targets the
2.7.18.16integration branch.