GHSA-8jvp-3x96-xpqw: 
Python vulnerability analysis and mitigation

Summary

Some ordinary uses of :has() take time that grows quadratically with the size of the document:

1. :has() with a descendant relative selector, such as div:has(p) or :has(em), is quadratic in how deeply the document is nested.
2. :has() with a child relative selector, used on the parent side of a child combinator, such as div:has(> p) > span, is quadratic in how many children an element has. An attacker who controls the HTML or XML that an application passes to Soup Sieve (directly, or through Beautiful Soup's select(), select_one(), css.select(), etc.) can send a small document, either deeply nested or with many sibling elements, that keeps a CPU busy for seconds to minutes against a selector written by the application.

Details

Descendant relative selectors in :has()

For each candidate element, :has() with a descendant relation searched the candidate's whole subtree for a match. Nothing was reused between candidates. In a chain of n nested elements, each one is a candidate, and the subtree below each is searched again, so matching takes O(n²) time. The worst case is when nothing matches, because no search can stop early. The same happens when the only match is at the very bottom of the chain.

:has() on the parent side of a child combinator

To match a > b, Soup Sieve checks each b and then checks whether its parent matches a. The result for the parent was not reused, so a parent with n children was matched against a once per child. When a contains :has(> x), each of those checks looks at all n children again, so matching takes O(n²) time.

Timings

Example timings with html.parser, before and after the fix:

Proof of concept

import time
import bs4
import soupsieve as sv
cases = [
    ('<div>' * 8000, 'div:has(p)'),
    ('<div>' + '<span></span>' * 5000 + '</div>', 'div:has(> p) > span'),
]
for markup, selector in cases:
    soup = bs4.BeautifulSoup(markup, 'html.parser')
    t = time.process_time()
    sv.select(selector, soup)
    print(selector, time.process_time() - t)

On affected versions, doubling the nesting depth (first case) or the number of children (second case) roughly quadruples the time.

Impact

Applications are affected if they run selectors like the ones above against documents that untrusted users can influence, such as scrapers, HTML sanitizers or filters, and services that process uploaded or fetched markup. A single request can tie up a worker for a long time. Applications that only run such selectors against trusted documents are not affected.

Patches

Fixed in 4.0.1 by:

• facelessuser/soupsieve#352: while matching :has() with a descendant relation, Soup Sieve now caches, per element and relation, whether an element is or contains a match. A subtree that has been searched once is not searched again, which makes the match linear in the size of the document.
• Commit 305fbf6: when matching the child combinator, whether the parent matches is now cached, so it is matched once for all of its children instead of once per child. Results are unchanged, and ordinary documents are no slower. Caching is enabled by default, so no changes are needed beyond upgrading. The NOCACHE flag is a temporary fallback for users who run into problems with caching, and it is planned for removal. It uses the old uncached matching, so selectors compiled with NOCACHE are still subject to quadratic time and shouldn't be used with :has() on untrusted input.

Workarounds

If you can't upgrade:

• Avoid using :has() with a descendant relative selector (:has(x)) on untrusted documents, and avoid putting :has() on the parent side of a child combinator (a:has(> x) > b).
• Ignore :has: https://facelessuser.github.io/soupsieve/api/?h=ignore#ignore-pseudo-class.
• Limit the size, nesting depth, and number of children per element of untrusted documents before selecting on them.
• Run selection on untrusted input with a time limit, for example in a worker process that can be stopped.

References

• Fix: facelessuser/soupsieve#352 (commit 0469c14)
• Fix: commit 305fbf6