Soup Sieve: Polynomial-time denial of service in the descendant combinator

Summary

Matching a selector that uses the descendant combinator (a b) takes time that grows polynomially with how deeply the document is nested, and each extra descendant combinator in the selector raises the degree by one. A selector with k descendant combinators takes O(n^(k+1)) time on a chain of n nested elements.

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 very small, deeply nested document that keeps a CPU busy for seconds to minutes against an ordinary selector such as section div div.

Details

To match a b, Soup Sieve checks each element against b and then walks up through its ancestors looking for one that matches a. When the selector has more descendant combinators, the rest of the selector is tried again from each ancestor on that walk, and so on for every combinator. Nothing was reused between walks, so the same ancestors were matched against the same part of the selector over and over.

The worst case is when the leftmost part of the selector never matches, as in section div div against a document of nested <div> with no <section>: every walk goes all the way to the root and no search can stop early.

Timings

Example timings with html.parser on Soup Sieve 3.0.4 and 4.0, using a document of nested <div> (5 bytes each) and no matches:

| Nesting depth | Input size | Selector | 3.0.4 | 4.0 | | --- | --- | --- | --- | --- | | 2,000 | 10 KB | section div | 1.6 s | 0.05 s | | 4,000 | 20 KB | section div | 5.1 s | 0.01 s | | 400 | 2 KB | section div div | 6.7 s | < 0.01 s | | 800 | 4 KB | section div div | 53.0 s | < 0.01 s | | 100 | 0.5 KB | section div div div | 2.5 s | < 0.01 s | | 200 | 1 KB | section div div div | 40.9 s | < 0.01 s |

None of these selectors use unusual syntax.

Proof of concept

import time
import bs4
import soupsieve as sv

soup = bs4.BeautifulSoup('<div>' * 200, 'html.parser')
t = time.process_time()
sv.select('section div div div', soup)
print(time.process_time() - t)

On affected versions, doubling the nesting depth multiplies the time by about 2^(k+1), where k is the number of descendant combinators: about 4x for section div, 8x for section div div, and 16x for section div div div.

Impact

Applications are affected if they run selectors with descendant combinators against documents that untrusted users can influence, such as scrapers, HTML sanitizers or filters, and services that process uploaded or fetched markup. Descendant combinators are among the most common parts of CSS selectors, and a document of about 1 KB is enough to tie up a worker for close to a minute. Applications that only run selectors against trusted documents are not affected.

Patches

Fixed in 4.0 by facelessuser/soupsieve#351. Whether an element is, or has an ancestor that is, a match for part of a selector depends only on its parent, so Soup Sieve now caches that result per element and relation for every element visited on the walk. Each descendant combinator is then linear in the size of the document. 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 polynomial time and shouldn't be used with descendant combinators on untrusted input.

Workarounds

If users can't upgrade:

• Use as few descendant combinators as they can in selectors that run on untrusted documents. Where the structure of the document is known, the child combinator (a > b) only looks at the parent and is not affected.
• Limit the size and nesting depth 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.