GHSA-F3MV-FM3P-593V
Quadratic CPU time in attribute selectors *= and $= (unanchored regex with near-match values)
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Divulgación | Publicada | GHSA-F3MV-FM3P-593V divulgada · CVSS 5.3 (GitHub) | |
| Remediación | Parche 4.1.0 | soupsieve · 0 d desde divulgación | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Summary
Attribute selectors using *= (contains) and $= (ends with) are compiled to unanchored regular expressions (".*?<value>.*" and ".*?<value>$"). When the selector value is long and nearly matches a long attribute value, matching is quadratic: doubling both lengths roughly quadruples the time. A selector with a 20 KB value against a document with an 80 KB attribute takes about 1 second per query, versus about 0.0003 seconds for Python's native substring search on the same data. Services that apply a user-supplied selector to a user-supplied document can be stalled with small inputs.
Details
In soupsieve/css_parser.py, parse_attribute_selector() builds these patterns:
*= -> re.compile(r'.*?%s.*' % value, flags)
$= -> re.compile(r'.*?%s$' % value, flags)
(value is passed through re.escape, so this is not injection; the cost comes from the structure of the pattern.)
For every element that has the attribute, the compiled pattern is applied with pattern.match(). The unanchored ".*?" prefix makes the engine retry the literal at every offset in the attribute value. A literal of length m that almost matches an attribute of length n costs O(n * m). Python's native "value in attr" and attr.endswith(value) handle the same comparison in near-linear time.
~= (space-separated list) is not affected in my tests and stays linear.
Observed behavior is the same on every version I tested (1.9.6, 2.5, 2.8.3, 2.9, 2.10, 3.0.2, 3.0.4, 4.0, 4.0.1), so this is long-standing design and not a regression.
Recommended fix: for *= and $=, compare with native string operations ("value in attr", "attr.endswith(value)", with case folding handled separately for the case-insensitive flag) instead of compiling an unanchored regex per selector. Defense in depth: bound the selector length or the attribute length considered.
Proof of concept
import time
import soupsieve as sv
from bs4 import BeautifulSoup
def run(op, attr_len, lit_len):
html = '<div x="%s"></div>' % ('a' * attr_len)
soup = BeautifulSoup(html, 'html.parser')
selector = '[x%s="%sb"]' % (op, 'a' * lit_len) # near-match literal, never matches
t = time.perf_counter()
soup.select(selector)
return time.perf_counter() - t
print("soupsieve", sv.__version__)
for op in ('*', '$'):
for attr_len, lit_len in [(20000, 5000), (40000, 10000), (80000, 20000)]:
print("[x%s=...] attr=%d selector_literal=%d -> %.2fs"
% (op, attr_len, lit_len, run(op, attr_len, lit_len)))
# Control: native substring search on the same data
a, l = 'a' * 80000, 'a' * 20000 + 'b'
t = time.perf_counter(); l in a
print("native 'in' on same data -> %.4fs" % (time.perf_counter() - t))Output on soupsieve 4.0.1 (times vary by machine; the 4x growth per doubling is the point):
soupsieve 4.0.1
[x*=...] attr=20000 selector_literal=5000 -> 0.16s
[x*=...] attr=40000 selector_literal=10000 -> 0.24s
[x*=...] attr=80000 selector_literal=20000 -> 0.99s
[x$=...] attr=20000 selector_literal=5000 -> 0.06s
[x$=...] attr=40000 selector_literal=10000 -> 0.24s
[x$=...] attr=80000 selector_literal=20000 -> 0.97s
native 'in' on same data -> 0.0003sImpact
Applications that let a caller supply a CSS selector and apply it to a caller-influenced document (for example a scraping service that takes a URL and a selector) can be made to spend seconds of CPU per request using tens of kilobytes of input, because the cost grows quadratically with input size. This can hold the Python GIL and starve other requests. No memory corruption or code execution. Applications that only use fixed, short selectors are not meaningfully affected.
Mitigation
In general, BeautifulSoup is best used as a developer tool. Exposing on a time critical server accepting untrusted user input is generally not recommended, but if the desire is to use it in this way, we offer a few suggestions for mitigation.
- Don’t allow `*=` and `$=` in untrusted selectors. Soupsieve only accepts these operators spelled exactly as `*=` and `$=`, with nothing between the two characters. `[x * = "a"]` and `[x*/**/="a"]` are both syntax errors. That makes a plain substring check reliable:
```py
if '*=' in selector or '$=' in selector:
raise ValueError('unsupported attribute operator')
```
It can reject some harmless selectors, such as an escaped name like `[x\*="a"]` or a value containing `*=`. It can’t miss a real use. The other operators `(=, ~=, |=, ^=, !=)` are already linear.
- Limit the selector length and the document size together as the cost is roughly the product of the two.
- Run selection in a separate process with a time limit. Matching holds the GIL, so a thread-based timeout can’t interrupt it. Use a process pool with a timeout, or `resource.setrlimit(resource.RLIMIT_CPU, ...)` in the worker. This also covers other expensive selector and document combinations, not just this one.
Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.
Desglose de métricas
Rangos afectados
Estado del parche por paquete
| Paquete / producto | Estado | Corregida en | Desde divulgación | Última versión |
|---|---|---|---|---|
pypisoupsieve |
Corregida | 4.1.0 | 0 d | 4.1.2 no afectada |
4.1.0Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://github.com/facelessuser/soupsieve/security/advisories/GHSA-f3mv-fm3p-593vLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
