Skip to content

Commit ef2012a

Browse files
andialbrechtandialbrecht
committed
Fix quadratic DoS in group_comments (GHSA-f2ff-p2ww-7p4p)
A comment-only statement ('-- c\n' repeated) made group_comments rescan the whole remaining token tail once per comment token, costing O(n^2). Because group_comments runs before the MAX_GROUPING_TOKENS guard, the cost was paid even on oversized input. Stop as soon as token_not_matching finds no terminator in the remaining tokens: from that point on nothing can group, so re-scanning the tail is wasted work. This makes the pass O(n) while preserving grouping output. Add benchmarks/validate_group_comments_dos.py to check the scaling. Reported by sanktjodel. Co-Authored-By: Claude Opus 4.8 <[email protected]>
1 parent 26112dd commit ef2012a

3 files changed

Lines changed: 96 additions & 3 deletions

File tree

‎CHANGELOG‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,9 @@ Security Fixes
2525
(e.g. SELECT with thousands of columns) therefore cost O(N²) in the
2626
number of columns. Fix: append only the newly added tokens' values.
2727

28+
* Fix quadratic CPU consumption in ``group_comments`` on comment-only input
29+
(CVE-2026-71491, GHSA-f2ff-p2ww-7p4p, reported by sanktjodel).
30+
2831
* Escape backslashes in the ``python`` and ``php`` output formats to prevent
2932
string-literal breakout (CVE-2026-59894, GHSA-3496-9g83-7v6x, reported by 7thParkk).
3033

‎benchmarks/validate_group_comments_dos.py‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
"""Validate that ``group_comments`` scales linearly on comment-only input.
2+
3+
Regression check for the quadratic O(n^2) DoS in ``group_comments``
4+
(sqlparse/engine/grouping.py), reported as GHSA-f2ff-p2ww-7p4p.
5+
6+
A statement made only of single-line comments (``'-- c\\n'`` repeated n times)
7+
lexes in O(n) but ``group_comments`` rescans the O(n) remaining tokens for every
8+
comment token, giving O(n^2) total work. ``group_comments`` runs first in
9+
``group()``, before the ``MAX_GROUPING_TOKENS`` guard, so the token cap does not
10+
protect this vector. The path is reachable via ``sqlparse.parse()`` and
11+
``sqlparse.format(sql, strip_comments=True)``.
12+
13+
This script measures the scaling of the vulnerable path and reports whether the
14+
observed growth is quadratic (vulnerable) or roughly linear (patched).
15+
16+
Run with: python benchmarks/validate_group_comments_dos.py
17+
18+
Exit code 0 => behaviour looks linear (advisory mitigated).
19+
Exit code 1 => behaviour looks quadratic (advisory reproduced).
20+
"""
21+
22+
import sys
23+
import time
24+
25+
import sqlparse
26+
27+
28+
def payload(n):
29+
"""A comment-only statement of n single-line comments."""
30+
return '-- c\n' * n
31+
32+
33+
def measure(fn, sql):
34+
t0 = time.perf_counter()
35+
fn(sql)
36+
return (time.perf_counter() - t0) * 1000
37+
38+
39+
def run(label, fn):
40+
print(f'{label}:')
41+
sizes = (1000, 2000, 4000, 8000)
42+
timings = []
43+
for n in sizes:
44+
dt = measure(fn, payload(n))
45+
timings.append(dt)
46+
print(f' n={n:5d} {dt:8.1f} ms ({len(payload(n))} B)')
47+
48+
# For each doubling of the input, quadratic growth ~4x, linear ~2x.
49+
ratios = [b / a for a, b in zip(timings, timings[1:]) if a > 0]
50+
print(f' doubling ratios: {", ".join(f"{r:.2f}x" for r in ratios)}')
51+
return ratios
52+
53+
54+
def classify(ratios):
55+
"""Quadratic if the average per-doubling ratio is closer to 4x than 2x."""
56+
if not ratios:
57+
return 'inconclusive', 0.0
58+
avg = sum(ratios) / len(ratios)
59+
# Midpoint between linear (2x) and quadratic (4x) is 3x.
60+
return ('quadratic' if avg >= 3.0 else 'linear'), avg
61+
62+
63+
def main():
64+
print('GHSA-f2ff-p2ww-7p4p: quadratic DoS in group_comments\n')
65+
66+
all_ratios = []
67+
all_ratios += run('sqlparse.parse', sqlparse.parse)
68+
print()
69+
all_ratios += run(
70+
'sqlparse.format(strip_comments=True)',
71+
lambda s: sqlparse.format(s, strip_comments=True),
72+
)
73+
print()
74+
75+
verdict, avg = classify(all_ratios)
76+
print(f'Average doubling ratio: {avg:.2f}x => {verdict}')
77+
if verdict == 'quadratic':
78+
print('VULNERABLE: growth is quadratic, advisory reproduced.')
79+
return 1
80+
print('OK: growth is roughly linear, advisory mitigated.')
81+
return 0
82+
83+
84+
if __name__ == '__main__':
85+
sys.exit(main())

‎sqlparse/engine/grouping.py‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -334,9 +334,14 @@ def group_comments(tlist):
334334
while token:
335335
eidx, end = tlist.token_not_matching(
336336
lambda tk: imt(tk, t=T.Comment) or tk.is_newline, idx=tidx)
337-
if end is not None:
338-
eidx, end = tlist.token_prev(eidx, skip_ws=False)
339-
tlist.group_tokens(sql.Comment, tidx, eidx)
337+
if end is None:
338+
# From tidx onward everything is comment/newline: there is no
339+
# terminator to group against, and every later start would hit
340+
# the same dead end. Stop instead of re-scanning the tail once
341+
# per remaining comment token (which is O(n**2)).
342+
break
343+
eidx, end = tlist.token_prev(eidx, skip_ws=False)
344+
tlist.group_tokens(sql.Comment, tidx, eidx)
340345

341346
tidx, token = tlist.token_next_by(t=T.Comment, idx=tidx)
342347

0 commit comments

Comments
 (0)