test.test_xml_etree*.XMLPullParserTest.test_simple_xml fails with (system) expat 2.6.0

[mgorny]

Bug report

Bug description:

Expat 2.6.0 was released yesterday, with CVE fixes. After upgrading the system library and building CPython --with-system-expat, I'm getting the following test failures:

======================================================================
FAIL: test_simple_xml (test.test_xml_etree.XMLPullParserTest.test_simple_xml) (chunk_size=1)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1495, in test_simple_xml
    self.assert_event_tags(parser, [('end', 'element')])
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1480, in assert_event_tags
    self.assertEqual([(action, elem.tag) for action, elem in events],
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                     expected)
                     ^^^^^^^^^
AssertionError: Lists differ: [] != [('end', 'element')]

Second list contains 1 additional elements.
First extra element 0:
('end', 'element')

- []
+ [('end', 'element')]

======================================================================
FAIL: test_simple_xml (test.test_xml_etree.XMLPullParserTest.test_simple_xml) (chunk_size=5)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1498, in test_simple_xml
    self.assert_event_tags(parser, [
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^
        ('end', 'element'),
        ^^^^^^^^^^^^^^^^^^^
        ('end', 'empty-element'),
        ^^^^^^^^^^^^^^^^^^^^^^^^^
        ])
        ^^
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1480, in assert_event_tags
    self.assertEqual([(action, elem.tag) for action, elem in events],
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                     expected)
                     ^^^^^^^^^
AssertionError: Lists differ: [('end', 'element')] != [('end', 'element'), ('end', 'empty-element')]

Second list contains 1 additional elements.
First extra element 1:
('end', 'empty-element')

- [('end', 'element')]
+ [('end', 'element'), ('end', 'empty-element')]

----------------------------------------------------------------------
======================================================================
FAIL: test_simple_xml (test.test_xml_etree_c.XMLPullParserTest.test_simple_xml) (chunk_size=1)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1495, in test_simple_xml
    self.assert_event_tags(parser, [('end', 'element')])
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1480, in assert_event_tags
    self.assertEqual([(action, elem.tag) for action, elem in events],
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                     expected)
                     ^^^^^^^^^
AssertionError: Lists differ: [] != [('end', 'element')]

Second list contains 1 additional elements.
First extra element 0:
('end', 'element')

- []
+ [('end', 'element')]

======================================================================
FAIL: test_simple_xml (test.test_xml_etree_c.XMLPullParserTest.test_simple_xml) (chunk_size=5)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1498, in test_simple_xml
    self.assert_event_tags(parser, [
    ~~~~~~~~~~~~~~~~~~~~~~^^^^^^^^^^
        ('end', 'element'),
        ^^^^^^^^^^^^^^^^^^^
        ('end', 'empty-element'),
        ^^^^^^^^^^^^^^^^^^^^^^^^^
        ])
        ^^
  File "/home/mgorny/git/cpython/Lib/test/test_xml_etree.py", line 1480, in assert_event_tags
    self.assertEqual([(action, elem.tag) for action, elem in events],
    ~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                     expected)
                     ^^^^^^^^^
AssertionError: Lists differ: [('end', 'element')] != [('end', 'element'), ('end', 'empty-element')]

Second list contains 1 additional elements.
First extra element 1:
('end', 'empty-element')

- [('end', 'element')]
+ [('end', 'element'), ('end', 'empty-element')]

----------------------------------------------------------------------

I have reproduced with 3.11.8, 3.12.8 and main as of 2afc718, both using Gentoo ebuild and raw git repository. I've tested the latter like this:

./configure -C --with-system-expat
make -j12
./python -u -W default -bb -E -m test -vv test_xml_etree{,_c}

CC @hartwork

CPython versions tested on:

3.11, 3.12, CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-115133: test_xml_etree.py: Fix for Expat >=2.6.0 with reparse deferral (fixes #115133) #115138
• gh-115133: Fix tests for XMLPullParser with Expat 2.6.0 #115164
• [3.12] gh-115133: Fix tests for XMLPullParser with Expat 2.6.0 (GH-115164) #115288
• [3.11] gh-115133: Fix tests for XMLPullParser with Expat 2.6.0 (GH-115164) #115289
• [3.10] gh-115133: Fix tests for XMLPullParser with Expat 2.6.0 (GH-115164) #115525
• [3.9] Fix tests for XMLPullParser with Expat 2.6.0 (GH-115133) #115535
• [3.8] gh-115133: Fix tests for XMLPullParser with Expat 2.6.0 (GH-115164 #115536

[hardfalcon]

I've run into the exact same issue when trying to build/package Python 3.11.8 in a clean chroot on Archlinux with testing repos enabled (expat 2.6.0 is currently only available from the core-testing repo). The error did not occur anymore when I forced expat 2.5.0 (but I'd obviously prefer to avoid that because expat 2.6.0 is a security update).

[serhiy-storchaka]

Note that tests are passed for chunk_size=None. I.e. it works as previously when feed the parser a whole line, but fails when split it on 1- or 5-character chunks.

I wonder whether it was an intentional change (and what was the reason) or a bug in expat.

[hardfalcon]

@serhiy-storchaka: I think this might be the result of the fix for CVE-2023-52425:
https://github.com/libexpat/libexpat/blob/R_2_6_0/expat/Changes#L7C22-L7C27

Not sure if it's intentional, though.

[hartwork]

Just a quick note that libexpat upstream is aware by now. I'll get back to you for more soon-ish.

[hartwork]

I have created candidate pull request #115138 now for review. It fixes the test suite in CPython for Expat >=2.6.0.

[serhiy-storchaka]

I would make the Expat buffering more context depending. For example, when the parser waits for the end of the long attribute, " in new input should set enough=1.

[Snild-Sony]

I wonder whether it was an intentional change (and what was the reason) or a bug in expat.

Expat previously took quadratic time when parsing tokens that required multiple buffer fills (a.k.a. "feeds" in the Python code). Expat 2.6.0 introduces a mitigation for this that does exponential backoff when repeatedly failing to parse the same token due to not having enough data.

This is why it doesn't affect the non-chunked case. It will also not affect the vast majority of usecases, since tokens do not usually require multiple feeds.

While I don't believe Expat ever guaranteed immediate events, I recognize that it is a change in Expat's behavior in practice. However, I expect that the vast majority of apps will not depend on getting immediate feedback (as they won't know what their input is) -- and this was the least intrusive way I could think of to fix this DoS.

when the parser waits for the end of the long attribute, " in new input should set enough=1.

@hartwork and I have discussed something along those lines, but concluded that it would be unnecessarily complex, and possibly difficult to get 100% right.

For example, if we're looking for the end of <hello , we want >. But we can't just force a reparse every time a > shows up in the input: attributex=">>>>>>>>>>> would trivially allow a bad XML file to bypass the mitigation. That means that we need to look at/remember more context (possibly from previous buffer fills), which AFAICT would require a whole lot of new infrastructure in Expat.

---

If this behavior is absolutely unacceptable, it is possible (but not recommended) to disable the mitigation using XML_SetReparseDeferralEnabled(). It is even possible to change mid-document, e.g. if you want to try to flush what's in Expat's buffer, but still mostly benefit from the new attack mitigation.

[serhiy-storchaka]

Does it need to restart parsing from <hello rather of at most ">>>? If it is so, then you have no other way with the current design. Ideally, Expact could be rewritten as a state machine that does not need reparsing, but it may be too much work.

Could you at least only block reparsing for large enough data? I mean that there is a difference between reparsing 100 bytes and 1000000 bytes.

Reducing the factor from 2 to 1.5 or 1.8 could help in some use cases. For example, if the stream consists of massages of approximately equal size N, and we feed the parser by chunks of approximately N bytes, then there is a large chance to block three messages in row (the first chunk is slightly smaller than the first message, and the second chunk is slightly smaller than the first chunk), but if the factor is less than 2, most likely only one message be blocked.

Or maybe combine both approaches: have_now >= A * had_before - B.

[Snild-Sony]

Does it need to restart parsing from <hello rather of at most ">>>?

Yes, that's what it does.

Could you at least only block reparsing for large enough data?

It's possible, but won't that just make the behavior harder to grasp for a user of the library?

Also, since the cost depends on the feed size, it's hard to set a definite threshold. Even a 1000-byte token, fed into Expat 1 byte at a time, will incur an amplification of 500x.

For example, if the stream consists of massages of approximately equal size N ...

Yes, a smaller factor could help that case. But I'm not sure it's a good idea to try to hide this behavior from apps -- for those that don't really need the behavior, it's unnecessary, and for those that do need it, it's not a 100% guarantee.

Do note that the whole first chunk would need to consist of a single token (essentially one big tag or comment) for this example to trigger the deferral logic, since consuming any bytes will reset the heuristic.

[serhiy-storchaka]

#115164 keeps testing with small chunks, so we can test that our code does not introduce additional buffering, but makes some failures tolerable with Expat 2.6.0.

Am I correct that the test with chunk_size=8 is passed with Expat 2.6.0?

[serhiy-storchaka]

Thank you all for discussion.