Skip to content

Commit a51df6d

Browse files
andialbrechtandialbrecht
committed
Measure reindent offsets backwards to avoid quadratic CPU use
ReindentFilter._get_offset() reports the column a token starts on and is called once per group. It rebuilt the statement prefix from the start of the statement on every call, so reindenting a list of N parenthesized tuples cost O(N^2). A ~12 KB payload sized just below MAX_GROUPING_TOKENS occupied a worker for seconds (CWE-1333, GHSA-cfqr-cjx5-5jcm). Measure the current line by walking backwards from the token and counting characters instead, which stops at the preceding line break rather than touching the whole statement. Formatting output is unchanged, verified byte for byte over the test corpus and 147 option combinations. Both vectors reaching the offset calculation are covered by the new benchmark: IN (...) tuple lists via _process_parenthesis() and _process_identifierlist(), VALUES lists via _process_values(). Co-Authored-By: Claude Opus 5 <noreply@anthropic.com>
1 parent 73d9ccd commit a51df6d

3 files changed

Lines changed: 157 additions & 13 deletions

File tree

‎CHANGELOG‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,11 @@ Security Fixes
3636
(e.g. SELECT with thousands of columns) therefore cost O(N²) in the
3737
number of columns. Fix: append only the newly added tokens' values.
3838

39+
* Fix uncontrolled CPU consumption when reindenting long tuple lists
40+
(CWE-1333, GHSA-cfqr-cjx5-5jcm). ``ReindentFilter._get_offset()`` rebuilt
41+
the statement prefix from its start on every call, making ``format()`` with
42+
``reindent=True`` O(N²) in the number of tuples. Fix: measure the current
43+
line by walking backwards from the token. Output is unchanged.
3944
* Fix quadratic CPU consumption in ``group_comments`` on comment-only input
4045
(CVE-2026-71491, GHSA-f2ff-p2ww-7p4p, reported by sanktjodel).
4146

‎benchmarks/bench_reindent_offset.py‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
"""Reindentation offset benchmarks (GHSA-cfqr-cjx5-5jcm, CWE-1333).
2+
3+
Measures ``format(sql, reindent=True)`` for SQL that stresses
4+
``ReindentFilter._get_offset()``, which reports the column a token starts on.
5+
6+
It used to rebuild the statement prefix from the start of the statement on
7+
every call, and it is called once per group -- so reindenting a list of N
8+
parenthesized tuples cost O(N^2). An attacker who controls SQL sent to this
9+
opt-in path can size a tuple list to stay just below the grouping-token cap
10+
(``MAX_GROUPING_TOKENS = 10000``), so grouping succeeds and the expensive
11+
reindentation path is entered. A payload of ~12 KB then pinned a CPU for
12+
seconds.
13+
14+
Both shapes below reach the same offset calculation but through different
15+
filters -- ``IN (...)`` tuple lists via ``_process_parenthesis()`` and
16+
``_process_identifierlist()``, ``VALUES`` lists via ``_process_values()``.
17+
18+
Run with: python benchmarks/bench_reindent_offset.py
19+
"""
20+
21+
import math
22+
import signal
23+
import time
24+
25+
import sqlparse
26+
27+
TIMEOUT_SECONDS = 60
28+
29+
30+
def _alarm_handler(signum, frame):
31+
raise TimeoutError()
32+
33+
34+
signal.signal(signal.SIGALRM, _alarm_handler)
35+
36+
37+
def in_tuple_list_sql(n_tuples):
38+
"""WHERE ... IN with n_tuples tuples -- the shape from the advisory."""
39+
tuples = ', '.join(f'({i}, {i * 2})' for i in range(n_tuples))
40+
return f'SELECT a FROM t WHERE (col1, col2) IN ({tuples})'
41+
42+
43+
def values_list_sql(n_tuples):
44+
"""INSERT ... VALUES with n_tuples tuples -- reaches _process_values()."""
45+
tuples = ', '.join(f'({i})' for i in range(n_tuples))
46+
return f'INSERT INTO t VALUES {tuples}'
47+
48+
49+
def measure(label, sql):
50+
signal.alarm(TIMEOUT_SECONDS)
51+
t0 = time.perf_counter()
52+
status = 'OK'
53+
try:
54+
# The vulnerable, opt-in path: reindentation.
55+
sqlparse.format(sql, reindent=True)
56+
except sqlparse.exceptions.SQLParseError:
57+
status = 'CAP' # grouping token/depth cap fired before reindenting
58+
except TimeoutError:
59+
status = 'TIMEOUT'
60+
finally:
61+
signal.alarm(0)
62+
dt = time.perf_counter() - t0
63+
print(f' {status:8} {dt:8.3f} s {label} ({len(sql)} B)')
64+
return dt
65+
66+
67+
# Absolute wall-clock is host dependent, so compare growth instead: the work
68+
# scales linearly with the number of tuples, so a patched build should grow
69+
# with an exponent near 1 and the O(N^2) bug with an exponent near 2. Sizes
70+
# stay below the grouping-token cap; a larger input is rejected quickly by the
71+
# cap instead of reaching the reindentation path.
72+
VECTORS = (
73+
('IN-tuple list ', in_tuple_list_sql, (150, 300, 600, 1200)),
74+
('VALUES list ', values_list_sql, (250, 500, 1000, 1950)),
75+
)
76+
77+
verdicts = []
78+
for name, build, sizes in VECTORS:
79+
print(f'{name.strip()} (format reindent=True):')
80+
times = [measure(f'{name} n={n:<5}', build(n)) for n in sizes]
81+
82+
if times[0] > 0 and times[-1] > 0:
83+
exponent = math.log(times[-1] / times[0]) / math.log(sizes[-1]
84+
/ sizes[0])
85+
else:
86+
exponent = 0.0
87+
print(f' n grew {sizes[-1] / sizes[0]:.1f}x; '
88+
f'time grew {times[-1] / times[0]:.1f}x; '
89+
f'empirical scaling exponent ~= {exponent:.2f}\n')
90+
verdicts.append((name.strip(), exponent))
91+
92+
vulnerable = [name for name, exponent in verdicts if exponent >= 1.5]
93+
if vulnerable:
94+
print('EVOHUNT_REINDENT_DOS_VERIFIED: super-linear (>= quadratic) CPU '
95+
f'growth via {", ".join(vulnerable)} -> ReindentFilter._get_offset '
96+
'DoS is present (unpatched).')
97+
else:
98+
print('Growth is ~linear for every vector -> the ReindentFilter offset '
99+
'fix appears to be present.')

‎sqlparse/filters/reindent.py‎

Lines changed: 53 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -27,25 +27,65 @@ def __init__(self, width=2, char=' ', wrap_after=0, n='\n',
2727
self._last_stmt = None
2828
self._last_func = None
2929

30-
def _flatten_up_to_token(self, token):
31-
"""Yields all tokens up to token but excluding current."""
32-
if token.is_group:
33-
token = next(token.flatten())
34-
35-
for t in self._curr_stmt.flatten():
36-
if t == token:
37-
break
38-
yield t
39-
4030
@property
4131
def leading_ws(self):
4232
return self.offset + self.indent * self.width
4333

34+
def _current_line_len(self, token):
35+
"""Returns the width of what's already emitted on *token*'s line.
36+
37+
The tokens preceding *token* are visited last one first, so the walk
38+
stops at the line break that starts the current line. Rebuilding the
39+
statement prefix from its start instead made every caller
40+
O(statement), and the callers running once per group (tuple lists,
41+
identifier lists) quadratic in the number of groups -- a CPU
42+
exhaustion vector (GHSA-cfqr-cjx5-5jcm). The walk is inlined and
43+
counts characters rather than collecting them: both matter, since a
44+
line without any break still has to be measured token by token.
45+
"""
46+
length = 0
47+
node = token
48+
while node is not self._curr_stmt and node.parent is not None:
49+
parent = node.parent
50+
# ``Token`` doesn't implement ``__eq__``, so ``index()`` is an
51+
# identity lookup and safe against tokens sharing a value.
52+
stack = parent.tokens[:parent.tokens.index(node)]
53+
while stack:
54+
prev_ = stack.pop()
55+
if prev_.is_group:
56+
stack.extend(prev_.tokens)
57+
continue
58+
59+
value = prev_.value
60+
size = len(value)
61+
if not size:
62+
continue
63+
lines = value.splitlines()
64+
if len(lines) == 1 and len(lines[0]) == size:
65+
# No break in here. ``splitlines()`` hands back the value
66+
# itself in that case, so this costs a scan but no copy --
67+
# which is what keeps a long break-free line affordable.
68+
length += size
69+
continue
70+
71+
# ``value`` holds the break that starts the current line. The
72+
# sentinel keeps a trailing break from collapsing, so ``lines``
73+
# always has one entry more than the number of breaks.
74+
lines = (value + '.').splitlines()
75+
tail = len(lines[-1]) - 1 + length
76+
if tail:
77+
return tail
78+
# Nothing but a break to our right, and ``splitlines()`` drops
79+
# that empty line -- so the line to measure is the one before.
80+
if len(lines) > 2:
81+
return len(lines[-2])
82+
length = len(lines[0])
83+
node = parent
84+
return length
85+
4486
def _get_offset(self, token):
45-
raw = ''.join(map(str, self._flatten_up_to_token(token)))
46-
line = (raw or '\n').splitlines()[-1]
4787
# Now take current offset into account and return relative offset.
48-
return len(line) - len(self.char * self.leading_ws)
88+
return self._current_line_len(token) - len(self.char * self.leading_ws)
4989

5090
def nl(self, offset=0):
5191
return sql.Token(

0 commit comments

Comments
 (0)