CWE-407
Allowed-with-ReviewInefficient Algorithmic Complexity
Abstraction: Class · Status: Incomplete
An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
584 vulnerabilities reference this CWE, most recent first.
GHSA-C2FH-M553-M5HP
Vulnerability from github – Published: 2022-05-14 01:14 – Updated: 2022-05-14 01:14The parse() method in the Email::Address module through 1.909 for Perl is vulnerable to Algorithmic complexity on specially prepared input, leading to Denial of Service. Prepared special input that caused this problem contained 30 form-field characters ("\f").
{
"affected": [],
"aliases": [
"CVE-2018-12558"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2018-06-20T14:29:00Z",
"severity": "HIGH"
},
"details": "The parse() method in the Email::Address module through 1.909 for Perl is vulnerable to Algorithmic complexity on specially prepared input, leading to Denial of Service. Prepared special input that caused this problem contained 30 form-field characters (\"\\f\").",
"id": "GHSA-c2fh-m553-m5hp",
"modified": "2022-05-14T01:14:04Z",
"published": "2022-05-14T01:14:04Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2018-12558"
},
{
"type": "WEB",
"url": "https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=901873"
},
{
"type": "WEB",
"url": "http://lists.opensuse.org/opensuse-security-announce/2019-04/msg00012.html"
},
{
"type": "WEB",
"url": "http://www.openwall.com/lists/oss-security/2018/06/19/3"
}
],
"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:H",
"type": "CVSS_V3"
}
]
}
GHSA-C2PC-G5QF-RFRF
Vulnerability from github – Published: 2024-12-09 20:42 – Updated: 2024-12-09 20:42Impact
Several polynomial time complexity issues in league/commonmark may lead to unbounded resource exhaustion and subsequent denial of service.
Malicious users could trigger that inefficient code with carefully crafted Markdown inputs that are specifically designed to ensure the worst-case performance is reached. Sending multiple such requests in parallel could tie up all available CPU resources and/or PHP-FPM processes, leading to denial of service for legitimate users.
Patches
These vulnerabilities have been patched in version 2.6.0. All users on older versions are highly encouraged to upgrade as soon as possible.
Workarounds
If you cannot upgrade, you may be able to mitigate the issues by:
- Setting very low
memory_limitandmax_execution_timePHP configurations to prevent runaway resource usage - Implementing rate-limiting, bot protection, or other approaches to reduce the risk of simultaneous bad requests hitting your site
- Limiting the size of inputs fed into this library (specifically the max length of each line)
- Limiting the use of this library to trusted users
References
Most of these issues were discovered in other Markdown parsers. You can read more about them here:
- https://github.com/commonmark/commonmark.js/issues/129
- https://github.com/commonmark/commonmark.js/issues/157
- https://github.com/commonmark/commonmark.js/issues/172
- https://github.com/github/cmark-gfm/security/advisories/GHSA-r572-jvj2-3m8p
- https://github.com/github/cmark-gfm/security/advisories/GHSA-24f7-9frr-5h2r
- https://github.com/github/cmark-gfm/security/advisories/GHSA-29g3-96g3-jg6c
- https://github.com/github/cmark-gfm/security/advisories/GHSA-r8vr-c48j-fcc5
- https://github.com/github/cmark-gfm/security/advisories/GHSA-w4qg-3vf7-m9x5
- https://github.com/github/cmark-gfm/security/advisories/GHSA-66g8-4hjf-77xh
For general information about this type of issue:
- https://en.wikipedia.org/wiki/Time_complexity
- https://cwe.mitre.org/data/definitions/407.html
{
"affected": [
{
"package": {
"ecosystem": "Packagist",
"name": "league/commonmark"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "2.6.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2024-12-09T20:42:07Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Impact\n\nSeveral polynomial time complexity issues in league/commonmark may lead to unbounded resource exhaustion and subsequent denial of service.\n\nMalicious users could trigger that inefficient code with carefully crafted Markdown inputs that are specifically designed to ensure the worst-case performance is reached. Sending multiple such requests in parallel could tie up all available CPU resources and/or PHP-FPM processes, leading to denial of service for legitimate users.\n\n### Patches\n\nThese vulnerabilities have been patched in version 2.6.0. All users on older versions are highly encouraged to upgrade as soon as possible.\n\n### Workarounds\n\nIf you cannot upgrade, you may be able to mitigate the issues by:\n\n- Setting very low `memory_limit` and `max_execution_time` PHP configurations to prevent runaway resource usage\n- Implementing rate-limiting, bot protection, or other approaches to reduce the risk of simultaneous bad requests hitting your site\n- Limiting the size of inputs fed into this library (specifically the max length of each line)\n- Limiting the use of this library to trusted users\n\n### References\n\nMost of these issues were discovered in other Markdown parsers. You can read more about them here:\n\n* https://github.com/commonmark/commonmark.js/issues/129\n* https://github.com/commonmark/commonmark.js/issues/157\n* https://github.com/commonmark/commonmark.js/issues/172\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-r572-jvj2-3m8p\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-24f7-9frr-5h2r\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-29g3-96g3-jg6c\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-r8vr-c48j-fcc5\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-w4qg-3vf7-m9x5\n* https://github.com/github/cmark-gfm/security/advisories/GHSA-66g8-4hjf-77xh\n\nFor general information about this type of issue:\n\n* https://en.wikipedia.org/wiki/Time_complexity\n* https://cwe.mitre.org/data/definitions/407.html\n",
"id": "GHSA-c2pc-g5qf-rfrf",
"modified": "2024-12-09T20:42:08Z",
"published": "2024-12-09T20:42:07Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-24f7-9frr-5h2r"
},
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-29g3-96g3-jg6c"
},
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-66g8-4hjf-77xh"
},
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-r572-jvj2-3m8p"
},
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-r8vr-c48j-fcc5"
},
{
"type": "WEB",
"url": "https://github.com/github/cmark-gfm/security/advisories/GHSA-w4qg-3vf7-m9x5"
},
{
"type": "WEB",
"url": "https://github.com/thephpleague/commonmark/security/advisories/GHSA-c2pc-g5qf-rfrf"
},
{
"type": "WEB",
"url": "https://github.com/commonmark/commonmark.js/issues/129"
},
{
"type": "WEB",
"url": "https://github.com/commonmark/commonmark.js/issues/157"
},
{
"type": "WEB",
"url": "https://github.com/commonmark/commonmark.js/issues/172"
},
{
"type": "PACKAGE",
"url": "https://github.com/thephpleague/commonmark"
}
],
"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": "league/commonmark\u0027s quadratic complexity bugs may lead to a denial of service"
}
GHSA-C3JG-QH8M-J3H2
Vulnerability from github – Published: 2026-10-08 19:41 – Updated: 2026-10-08 19:41Summary
Rendering an untrusted SVG whose <path d="..."> contains many segments is O(n²) CPU. A single <path> under 1 MiB burns tens of seconds. Two independent O(n²) sites in cairosvg/path.py:
- Tokenizer — the path-data parser consumes the
dstring with awhile string:loop that repeatedly slices/re-scans the remaining string (each step is O(len remaining)), giving O(n²) over the whole attribute. - draw_markers — marker handling drains
node.verticeswithwhile node.vertices: ... node.vertices.pop(0);list.pop(0)is O(n), so draining n vertices is O(n²).
Both are hit on a normal render path (svg2png/svg2pdf), attacker controls only the SVG document.
PoC (installed cairosvg 2.9.0)
import cairosvg
d = "M0 0 " + "L1 1 " * 100000
svg = f'<svg xmlns="http://www.w3.org/2000/svg" width="10" height="10"><path d="{d}"/></svg>'
cairosvg.svg2png(bytestring=svg.encode()) # ~4.4 s for a 488 KB doc
| path segments | SVG size | time |
|---|---|---|
| 50,000 | 244 KB | 1.14 s |
| 100,000 | 488 KB | 4.36 s |
| 200,000 | ~960 KB | ~18 s |
Doubling segments ≈ 4× time ⇒ quadratic. Sub-MiB input ⇒ ~18 s CPU; any service rendering user-supplied SVG (thumbnails, avatars, PDF export) is a DoS target.
Reachability
Public API svg2png / svg2pdf / svg2ps on an untrusted SVG string.
Suggested fix
Tokenize with a single forward scan / index (or re.finditer) instead of re-slicing the remainder; drain vertices with an index or collections.deque.popleft instead of list.pop(0). Optionally cap path-segment count.
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 2.9.0"
},
"package": {
"ecosystem": "PyPI",
"name": "cairosvg"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "2.9.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-107378"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-10-08T19:41:22Z",
"nvd_published_at": "2026-10-08T18:17:23Z",
"severity": "HIGH"
},
"details": "## Summary\n\nRendering an untrusted SVG whose `\u003cpath d=\"...\"\u003e` contains many segments is O(n\u00b2) CPU. A single `\u003cpath\u003e` under 1 MiB burns tens of seconds. Two independent O(n\u00b2) sites in `cairosvg/path.py`:\n\n1. **Tokenizer** \u2014 the path-data parser consumes the `d` string with a `while string:` loop that repeatedly slices/re-scans the *remaining* string (each step is O(len remaining)), giving O(n\u00b2) over the whole attribute.\n2. **draw_markers** \u2014 marker handling drains `node.vertices` with `while node.vertices: ... node.vertices.pop(0)`; `list.pop(0)` is O(n), so draining n vertices is O(n\u00b2).\n\nBoth are hit on a normal render path (`svg2png`/`svg2pdf`), attacker controls only the SVG document.\n\n## PoC (installed cairosvg 2.9.0)\n\n```python\nimport cairosvg\nd = \"M0 0 \" + \"L1 1 \" * 100000\nsvg = f\u0027\u003csvg xmlns=\"http://www.w3.org/2000/svg\" width=\"10\" height=\"10\"\u003e\u003cpath d=\"{d}\"/\u003e\u003c/svg\u003e\u0027\ncairosvg.svg2png(bytestring=svg.encode()) # ~4.4 s for a 488 KB doc\n```\n\n| path segments | SVG size | time |\n|---|---|---|\n| 50,000 | 244 KB | 1.14 s |\n| 100,000 | 488 KB | 4.36 s |\n| 200,000 | ~960 KB | ~18 s |\n\nDoubling segments \u2248 4\u00d7 time \u21d2 quadratic. Sub-MiB input \u21d2 ~18 s CPU; any service rendering user-supplied SVG (thumbnails, avatars, PDF export) is a DoS target.\n\n## Reachability\n\nPublic API `svg2png` / `svg2pdf` / `svg2ps` on an untrusted SVG string.\n\n## Suggested fix\n\nTokenize with a single forward scan / index (or `re.finditer`) instead of re-slicing the remainder; drain `vertices` with an index or `collections.deque.popleft` instead of `list.pop(0)`. Optionally cap path-segment count.",
"id": "GHSA-c3jg-qh8m-j3h2",
"modified": "2026-10-08T19:41:22Z",
"published": "2026-10-08T19:41:22Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/Kozea/CairoSVG/security/advisories/GHSA-c3jg-qh8m-j3h2"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-107378"
},
{
"type": "WEB",
"url": "https://github.com/Kozea/CairoSVG/commit/9d63f049f9988d0ddda3eb94564ac3a50a286523"
},
{
"type": "WEB",
"url": "https://github.com/Kozea/CairoSVG/commit/a4d585eb374724b79676e9cceaa9e9a1a4358565"
},
{
"type": "PACKAGE",
"url": "https://github.com/Kozea/CairoSVG"
},
{
"type": "WEB",
"url": "https://github.com/Kozea/CairoSVG/releases/tag/2.9.1"
}
],
"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": "CairoSVG: Quadratic-time DoS parsing a crafted SVG \u003cpath\u003e"
}
GHSA-C7VW-FRHJ-6H9J
Vulnerability from github – Published: 2026-09-26 15:31 – Updated: 2026-09-26 15:31nodemailer before 10.0.6 contains a denial of service vulnerability in the addressparser free-text fallback regex pattern that exhibits quadratic backtracking behavior. Attackers can supply crafted email header values with long whitespace-free runs to block the Node.js event loop for tens of seconds, causing service unavailability.
{
"affected": [],
"aliases": [
"CVE-2026-100700"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-09-26T14:16:55Z",
"severity": "HIGH"
},
"details": "nodemailer before 10.0.6 contains a denial of service vulnerability in the addressparser free-text fallback regex pattern that exhibits quadratic backtracking behavior. Attackers can supply crafted email header values with long whitespace-free runs to block the Node.js event loop for tens of seconds, causing service unavailability.",
"id": "GHSA-c7vw-frhj-6h9j",
"modified": "2026-09-26T15:31:22Z",
"published": "2026-09-26T15:31:22Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/nodemailer/nodemailer/security/advisories/GHSA-v53p-9fqp-m79j"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-100700"
},
{
"type": "WEB",
"url": "https://www.vulncheck.com/advisories/nodemailer-before-10.0.6-denial-of-service-via-addressparser"
}
],
"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"
},
{
"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/E:X/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-C8J7-8CV4-2XMQ
Vulnerability from github – Published: 2026-07-20 21:34 – Updated: 2026-07-20 21:34Summary
Type: Algorithmic-complexity denial of service. A run of N closed pairs ~~x~~~~x~~... (or the analogous ==x== for mark, ^^x^^ for insert) causes O(N²) work in the formatting parser. With the strikethrough, mark, or insert plugin enabled, an 8 KB input pegs the CPU for ~4 seconds; 16 KB → ~17 seconds.
File: src/mistune/plugins/formatting.py, lines 13-15 (the _STRIKE_END / _MARK_END / _INSERT_END patterns and their per-position scan).
Root cause: for each opening ~~/==/^^ the parser scans forward for the matching close pattern. The scan itself uses a bounded regex, but the parser tries the close-scan at every potential start position. For input shaped like ~~x~~ repeated N times, every ~~ is examined as a possible start, each scan covers up to the end of input. Total work is O(N²). Default config without these plugins handles the same input in linear time (4 ms for 4000 reps), confirming the cost is in the formatting plugin's per-marker scan, not in core parsing.
Affected Code
File: src/mistune/plugins/formatting.py, lines 12-16.
_STRIKE_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\~|[^\s~])~~(?!~)")
_MARK_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\=|[^\s=])==(?!=)")
_INSERT_END = re.compile(r"(?:" + PREVENT_BACKSLASH + r"\\\^|[^\s^])\^\^(?!\^)")
# Each pattern is scanned forward from every start position fired by the
# corresponding inline rule. The end-pattern itself is bounded; the cost
# comes from the surrounding parser invoking the scan at every '~~' / '==' / '^^'
# token in the input, giving N starts × O(N) per scan = O(N^2) total.
Why it's wrong: the same algorithmic-complexity flaw class as [ / [a parsing in core: a per-token retry loop without memoisation of failed positions. Each formatting marker is tried as both a potential start and as a continuation. A linear-pass delimiter-stack algorithm (matching how commonmark-py and markdown-it-py handle emphasis) would do this work in O(N) total. The bounded regex on each individual scan does not bound the parser-level repetition.
Exploit Chain
- Application uses mistune to render user-supplied markdown and has any of the formatting plugins enabled (
plugins=['strikethrough'],['mark'],['insert'], or any superset). These plugins are commonly enabled because GitHub-flavoured-Markdown compatibility requires~~strikethrough~~and many editors emit==highlighting==and^^underline^^shortcuts. - Attacker submits an 8 KB markdown payload of the form
~~x~~~~x~~~~x~~...(40 000 characters of~~x~~repeated 8000 times, or the analogous shape with==/^^). - Server calls
mistune.create_markdown(plugins=['strikethrough'])(payload). CPU pegs for ~4 seconds; 16 KB → ~17 seconds; 32 KB → ~70 seconds. Pure CPU cost, no significant memory growth. - Repeating the request floods the worker pool. On a single-thread WSGI handler this is one request per outage; on a thread pool, a small number of concurrent attackers exhausts capacity.
Security Impact
Severity: sec-high. Network-reachable, no authentication, predictable scaling, single-payload primitive. Only requires a user-supplied markdown sink and a formatting plugin enabled — both are common.
Attacker capability: small input → large CPU. Doubling input size quadruples CPU time. Sustained requests deny service to other users.
Preconditions: application uses mistune with any of strikethrough, mark, or insert plugins enabled. Default config does NOT enable these (so the attack only fires against the substantial deployed population that turns them on for GFM/markdown-extra compatibility).
Differential: PoC-verified against mistune@3.2.1:
import mistune, time
md = mistune.create_markdown(plugins=['strikethrough'])
for n in [500, 1000, 2000, 4000, 8000]:
s = '~~x~~' * n
t = time.time()
md(s)
print(f' ~~x~~ * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms')
# Output (Python 3.13, Linux, 2.5GHz CPU):
# ~~x~~ * 500 (2500b): 19ms
# ~~x~~ * 1000 (5000b): 71ms
# ~~x~~ * 2000 (10000b): 272ms
# ~~x~~ * 4000 (20000b): 1090ms
# ~~x~~ * 8000 (40000b): 4302ms
# Identical scaling for `==x==` (mark) and `^^x^^` (insert):
md = mistune.create_markdown(plugins=['mark'])
md('==x==' * 4000) # ~1100ms
md = mistune.create_markdown(plugins=['insert'])
md('^^x^^' * 4000) # ~1080ms
# Without the plugin, the same input parses in linear time:
md = mistune.create_markdown() # no plugins
md('~~x~~' * 4000) # 4ms (1000x faster)
The patched build (with the suggested fix below — either a delimiter-stack rewrite or a hard cap on the number of unmatched markers tracked) keeps the time linear in N.
Suggested Fix
The minimal fix is to cap the number of simultaneously-tracked unmatched markers, treating extras as literal text. The proper fix is a single-pass delimiter-stack algorithm matching the CommonMark reference implementation. Surgical patch:
--- a/src/mistune/plugins/formatting.py
+++ b/src/mistune/plugins/formatting.py
@@ ... in the parse_strikethrough / parse_mark / parse_insert functions
+ # Bound the number of open markers the parser will track concurrently.
+ # Inputs with more than this many open ~~ / == / ^^ in flight are
+ # almost certainly adversarial; CommonMark gives no semantics to
+ # deeply nested unmatched markers.
+ MAX_OPEN_MARKERS = 100
+ if open_marker_count > MAX_OPEN_MARKERS:
+ # treat remaining markers as literal text, do not invoke the
+ # forward-scan to find a close
+ ...
A regression test should assert that md('~~x~~' * 50_000) completes in under 1 second. The same fix shape applies to _MARK_END and _INSERT_END.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "mistune"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.3.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-59922"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-07-20T21:34:37Z",
"nvd_published_at": "2026-07-08T17:17:27Z",
"severity": "HIGH"
},
"details": "## Summary\n\n**Type:** Algorithmic-complexity denial of service. A run of N closed pairs `~~x~~~~x~~...` (or the analogous `==x==` for `mark`, `^^x^^` for `insert`) causes O(N\u00b2) work in the formatting parser. With the `strikethrough`, `mark`, or `insert` plugin enabled, an 8 KB input pegs the CPU for ~4 seconds; 16 KB \u2192 ~17 seconds. \n**File:** `src/mistune/plugins/formatting.py`, lines 13-15 (the `_STRIKE_END` / `_MARK_END` / `_INSERT_END` patterns and their per-position scan).\n**Root cause:** for each opening `~~`/`==`/`^^` the parser scans forward for the matching close pattern. The scan itself uses a bounded regex, but the parser tries the close-scan at every potential start position. For input shaped like `~~x~~` repeated N times, every `~~` is examined as a possible start, each scan covers up to the end of input. Total work is O(N\u00b2). Default config without these plugins handles the same input in linear time (4 ms for 4000 reps), confirming the cost is in the formatting plugin\u0027s per-marker scan, not in core parsing.\n\n## Affected Code\n\n**File:** `src/mistune/plugins/formatting.py`, lines 12-16.\n\n```python\n_STRIKE_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\~|[^\\s~])~~(?!~)\")\n_MARK_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\=|[^\\s=])==(?!=)\")\n_INSERT_END = re.compile(r\"(?:\" + PREVENT_BACKSLASH + r\"\\\\\\^|[^\\s^])\\^\\^(?!\\^)\")\n# Each pattern is scanned forward from every start position fired by the\n# corresponding inline rule. The end-pattern itself is bounded; the cost\n# comes from the surrounding parser invoking the scan at every \u0027~~\u0027 / \u0027==\u0027 / \u0027^^\u0027\n# token in the input, giving N starts \u00d7 O(N) per scan = O(N^2) total.\n```\n\n**Why it\u0027s wrong:** the same algorithmic-complexity flaw class as `[` / `[a` parsing in core: a per-token retry loop without memoisation of failed positions. Each formatting marker is tried as both a potential start and as a continuation. A linear-pass delimiter-stack algorithm (matching how `commonmark-py` and `markdown-it-py` handle emphasis) would do this work in O(N) total. The bounded regex on each individual scan does not bound the parser-level repetition.\n\n## Exploit Chain\n\n1. Application uses mistune to render user-supplied markdown and has any of the formatting plugins enabled (`plugins=[\u0027strikethrough\u0027]`, `[\u0027mark\u0027]`, `[\u0027insert\u0027]`, or any superset). These plugins are commonly enabled because GitHub-flavoured-Markdown compatibility requires `~~strikethrough~~` and many editors emit `==highlighting==` and `^^underline^^` shortcuts.\n2. Attacker submits an 8 KB markdown payload of the form `~~x~~~~x~~~~x~~...` (40 000 characters of `~~x~~` repeated 8000 times, or the analogous shape with `==` / `^^`).\n3. Server calls `mistune.create_markdown(plugins=[\u0027strikethrough\u0027])(payload)`. CPU pegs for ~4 seconds; 16 KB \u2192 ~17 seconds; 32 KB \u2192 ~70 seconds. Pure CPU cost, no significant memory growth.\n4. Repeating the request floods the worker pool. On a single-thread WSGI handler this is one request per outage; on a thread pool, a small number of concurrent attackers exhausts capacity.\n\n## Security Impact\n\n**Severity:** sec-high. Network-reachable, no authentication, predictable scaling, single-payload primitive. Only requires a user-supplied markdown sink and a formatting plugin enabled \u2014 both are common.\n**Attacker capability:** small input \u2192 large CPU. Doubling input size quadruples CPU time. Sustained requests deny service to other users.\n**Preconditions:** application uses mistune with any of `strikethrough`, `mark`, or `insert` plugins enabled. Default config does NOT enable these (so the attack only fires against the substantial deployed population that turns them on for GFM/markdown-extra compatibility).\n**Differential:** PoC-verified against mistune@3.2.1:\n\n```python\nimport mistune, time\nmd = mistune.create_markdown(plugins=[\u0027strikethrough\u0027])\nfor n in [500, 1000, 2000, 4000, 8000]:\n s = \u0027~~x~~\u0027 * n\n t = time.time()\n md(s)\n print(f\u0027 ~~x~~ * {n} ({len(s)}b): {(time.time() - t) * 1000:.0f}ms\u0027)\n\n# Output (Python 3.13, Linux, 2.5GHz CPU):\n# ~~x~~ * 500 (2500b): 19ms\n# ~~x~~ * 1000 (5000b): 71ms\n# ~~x~~ * 2000 (10000b): 272ms\n# ~~x~~ * 4000 (20000b): 1090ms\n# ~~x~~ * 8000 (40000b): 4302ms\n\n# Identical scaling for `==x==` (mark) and `^^x^^` (insert):\nmd = mistune.create_markdown(plugins=[\u0027mark\u0027])\nmd(\u0027==x==\u0027 * 4000) # ~1100ms\nmd = mistune.create_markdown(plugins=[\u0027insert\u0027])\nmd(\u0027^^x^^\u0027 * 4000) # ~1080ms\n\n# Without the plugin, the same input parses in linear time:\nmd = mistune.create_markdown() # no plugins\nmd(\u0027~~x~~\u0027 * 4000) # 4ms (1000x faster)\n```\n\nThe patched build (with the suggested fix below \u2014 either a delimiter-stack rewrite or a hard cap on the number of unmatched markers tracked) keeps the time linear in N.\n\n## Suggested Fix\n\nThe minimal fix is to cap the number of simultaneously-tracked unmatched markers, treating extras as literal text. The proper fix is a single-pass delimiter-stack algorithm matching the CommonMark reference implementation. Surgical patch:\n\n```diff\n--- a/src/mistune/plugins/formatting.py\n+++ b/src/mistune/plugins/formatting.py\n@@ ... in the parse_strikethrough / parse_mark / parse_insert functions\n+ # Bound the number of open markers the parser will track concurrently.\n+ # Inputs with more than this many open ~~ / == / ^^ in flight are\n+ # almost certainly adversarial; CommonMark gives no semantics to\n+ # deeply nested unmatched markers.\n+ MAX_OPEN_MARKERS = 100\n+ if open_marker_count \u003e MAX_OPEN_MARKERS:\n+ # treat remaining markers as literal text, do not invoke the\n+ # forward-scan to find a close\n+ ...\n```\n\nA regression test should assert that `md(\u0027~~x~~\u0027 * 50_000)` completes in under 1 second. The same fix shape applies to `_MARK_END` and `_INSERT_END`.",
"id": "GHSA-c8j7-8cv4-2xmq",
"modified": "2026-07-20T21:34:37Z",
"published": "2026-07-20T21:34:37Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/lepture/mistune/security/advisories/GHSA-c8j7-8cv4-2xmq"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-59922"
},
{
"type": "WEB",
"url": "https://github.com/lepture/mistune/commit/96d0f57f8fe9eeb06bb4cff521962a27d7c402e7"
},
{
"type": "PACKAGE",
"url": "https://github.com/lepture/mistune"
},
{
"type": "WEB",
"url": "https://github.com/lepture/mistune/releases/tag/v3.3.0"
},
{
"type": "WEB",
"url": "https://github.com/pypa/advisory-database/tree/main/vulns/mistune/PYSEC-2026-2210.yaml"
}
],
"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": "Mistune plugins/formatting: quadratic-time parsing on long runs of `~~x~~`, `==x==`, and `^^x^^` markers (strikethrough / mark / insert)"
}
GHSA-C9G6-HVJW-WVMP
Vulnerability from github – Published: 2026-10-02 12:31 – Updated: 2026-10-02 12:31Inefficient regular expression complexity, Inefficient Algorithmic Complexity vulnerability in Apache Thrift Lua bindings.
This issue affects Apache Thrift: before 0.25.0.
Users are recommended to upgrade to version 0.25.0, which fixes the issue.
{
"affected": [],
"aliases": [
"CVE-2026-96292"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-10-02T12:17:24Z",
"severity": "HIGH"
},
"details": "Inefficient regular expression complexity, Inefficient Algorithmic Complexity vulnerability in Apache Thrift Lua bindings.\n\n\n\nThis issue affects Apache Thrift: before 0.25.0.\n\n\n\nUsers are recommended to upgrade to version 0.25.0, which fixes the issue.",
"id": "GHSA-c9g6-hvjw-wvmp",
"modified": "2026-10-02T12:31:19Z",
"published": "2026-10-02T12:31:19Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-96292"
},
{
"type": "WEB",
"url": "https://lists.apache.org/thread/33otcgbqd27wf6qq810q56znzbomnhg1"
},
{
"type": "WEB",
"url": "https://lists.apache.org/thread/3wmvtvv56rky5wtszn4zr8w12kg928qn"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:N/AC:L/AT:P/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/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-CFQR-CJX5-5JCM
Vulnerability from github – Published: 2026-09-01 21:20 – Updated: 2026-09-01 21:20Summary
When SQL is formatted with reindentation enabled, ReindentFilter repeatedly rebuilds prefixes of the current statement to calculate token offsets. An attacker who controls SQL sent to this opt-in formatting path can supply a parenthesized tuple list that remains just below the grouping-token cap. Thousands of offset calculations then traverse an expanding token tree, causing multi-second CPU consumption from an input of roughly 16 KB and degrading service availability.
Details
ReindentFilter._get_offset() joins the tokens returned by _flatten_up_to_token() to calculate the current output position. Each call begins by flattening the current statement from its start and walks until the target token. Tuple-list reindentation invokes this calculation repeatedly as it processes many parenthesized values, so later calls redo an increasingly large amount of prior work.
The vulnerable path is reached through sqlparse.format(sql, reindent=True) and sqlformat --reindent. A carefully sized tuple list completes grouping below the configured token cap and then enters the expensive reindentation path; a slightly larger input may instead be rejected quickly by the cap.
Relevant code locations:
sqlparse/formatter.py:170— enablingReindentFiltersqlparse/filters/reindent.py:30— repeated flattening from the statement startsqlparse/filters/reindent.py:44— prefix joining for offset calculationsqlparse/filters/reindent.py:216— tuple-list processing path
PoC
A complete validated reproduction is attached as reindent_tuple_list_cpu_dos-poc.zip. The archive contains reproduction/ at its root, uses Git and Docker, and compares two same-shape tuple-list inputs formatted with reindentation enabled.
Extract the archive beside this report, then run:
./reproduction/run.sh
Observed result:
The 600-tuple baseline completed in 0.649 seconds, while the below-cap 1,425-tuple input completed in 4.999 seconds. The run emitted EVOHUNT_REINDENT_DOS_VERIFIED and completed successfully.
Verification method:
The verification helper formats two same-shape tuple-list payloads with reindent=True and fails unless the larger payload completes successfully, takes at least 2.0 seconds, and takes at least 4x the baseline.
Limitations:
No reproduction blocker was recorded. Timing varies by host, and exploitation requires the reindentation option or corresponding CLI mode to be enabled.
Impact
This is a CPU resource-exhaustion vulnerability in workflows that reindent attacker-controlled SQL. A small crafted tuple-list input can occupy a worker for several seconds, enabling request delays, reduced throughput, or worker starvation when payloads are processed repeatedly or concurrently.
The affected reindentation behavior is opt-in, and sqlparse itself does not provide network exposure; reachability depends on the consuming application or CLI workflow. The demonstrated effect is CPU consumption in a single formatting call, not process termination, code execution, or confidentiality or integrity impact.
{
"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-84305"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-09-01T21:20:11Z",
"nvd_published_at": null,
"severity": "MODERATE"
},
"details": "### Summary\n\nWhen SQL is formatted with reindentation enabled, `ReindentFilter` repeatedly rebuilds prefixes of the current statement to calculate token offsets. An attacker who controls SQL sent to this opt-in formatting path can supply a parenthesized tuple list that remains just below the grouping-token cap. Thousands of offset calculations then traverse an expanding token tree, causing multi-second CPU consumption from an input of roughly 16 KB and degrading service availability.\n\n### Details\n\n`ReindentFilter._get_offset()` joins the tokens returned by `_flatten_up_to_token()` to calculate the current output position. Each call begins by flattening the current statement from its start and walks until the target token. Tuple-list reindentation invokes this calculation repeatedly as it processes many parenthesized values, so later calls redo an increasingly large amount of prior work.\n\nThe vulnerable path is reached through `sqlparse.format(sql, reindent=True)` and `sqlformat --reindent`. A carefully sized tuple list completes grouping below the configured token cap and then enters the expensive reindentation path; a slightly larger input may instead be rejected quickly by the cap.\n\nRelevant code locations:\n\n- `sqlparse/formatter.py:170` \u2014 enabling `ReindentFilter`\n- `sqlparse/filters/reindent.py:30` \u2014 repeated flattening from the statement start\n- `sqlparse/filters/reindent.py:44` \u2014 prefix joining for offset calculation\n- `sqlparse/filters/reindent.py:216` \u2014 tuple-list processing path\n\n### PoC\n\nA complete validated reproduction is attached as [reindent_tuple_list_cpu_dos-poc.zip](https://github.com/user-attachments/files/29410152/reindent_tuple_list_cpu_dos-poc.zip). The archive contains `reproduction/` at its root, uses Git and Docker, and compares two same-shape tuple-list inputs formatted with reindentation enabled.\n\nExtract the archive beside this report, then run:\n\n```console\n./reproduction/run.sh\n```\n\nObserved result:\n\nThe 600-tuple baseline completed in 0.649 seconds, while the below-cap 1,425-tuple input completed in 4.999 seconds. The run emitted `EVOHUNT_REINDENT_DOS_VERIFIED` and completed successfully.\n\nVerification method:\n\nThe verification helper formats two same-shape tuple-list payloads with `reindent=True` and fails unless the larger payload completes successfully, takes at least 2.0 seconds, and takes at least 4x the baseline.\n\nLimitations:\n\nNo reproduction blocker was recorded. Timing varies by host, and exploitation requires the reindentation option or corresponding CLI mode to be enabled.\n\n### Impact\n\nThis is a CPU resource-exhaustion vulnerability in workflows that reindent attacker-controlled SQL. A small crafted tuple-list input can occupy a worker for several seconds, enabling request delays, reduced throughput, or worker starvation when payloads are processed repeatedly or concurrently.\n\nThe affected reindentation behavior is opt-in, and sqlparse itself does not provide network exposure; reachability depends on the consuming application or CLI workflow. The demonstrated effect is CPU consumption in a single formatting call, not process termination, code execution, or confidentiality or integrity impact.",
"id": "GHSA-cfqr-cjx5-5jcm",
"modified": "2026-09-01T21:20:11Z",
"published": "2026-09-01T21:20:11Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/security/advisories/GHSA-cfqr-cjx5-5jcm"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/commit/a51df6d9e2d31b44be9adb6bc8732517db6bf96b"
},
{
"type": "PACKAGE",
"url": "https://github.com/andialbrecht/sqlparse"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/releases/tag/0.6.0"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:L/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": "sqlparse: Reindentation of tuple lists causes near-cap quadratic CPU consumption"
}
GHSA-CGX7-QMCG-22W3
Vulnerability from github – Published: 2026-10-02 15:31 – Updated: 2026-10-02 15:31Allocation of resources without limits or throttling, Inefficient Algorithmic Complexity vulnerability in Apache Thrift Lua bindings.
This issue affects Apache Thrift: before 0.25.0.
Users are recommended to upgrade to version 0.25.0, which fixes the issue.
{
"affected": [],
"aliases": [
"CVE-2026-94655"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-10-02T13:18:02Z",
"severity": "HIGH"
},
"details": "Allocation of resources without limits or throttling, Inefficient Algorithmic Complexity vulnerability in Apache Thrift Lua bindings.\n\n\n\nThis issue affects Apache Thrift: before 0.25.0.\n\n\n\nUsers are recommended to upgrade to version 0.25.0, which fixes the issue.",
"id": "GHSA-cgx7-qmcg-22w3",
"modified": "2026-10-02T15:31:24Z",
"published": "2026-10-02T15:31:24Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-94655"
},
{
"type": "WEB",
"url": "https://lists.apache.org/thread/33otcgbqd27wf6qq810q56znzbomnhg1"
},
{
"type": "WEB",
"url": "https://lists.apache.org/thread/wdjyf4y115ybgdzz5m3gspo97lcmz1dt"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:N/AC:L/AT:P/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N/E:X/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-CGXM-VR2F-6FJ8
Vulnerability from github – Published: 2026-06-19 14:50 – Updated: 2026-06-19 14:50Impact
Parse Server is vulnerable to denial of service. A remote attacker can send a single, small query (~1 KB) containing deeply nested query condition operators. Parse Server processes the nested structure with exponential time complexity, which blocks the Node.js event loop and makes the server unresponsive to all clients for the duration of processing. A single request can occupy the event loop for many seconds, and the request is repeatable. The issue affects the REST API and LiveQuery query handling and is reachable in the default configuration. Exploitation requires only the public application identifier; no user authentication is needed.
Patches
The internal query-traversal helper that previously re-walked nested arrays — causing exponential-time processing of nested $or/$and/$nor operators — was corrected to traverse queries in linear time. Additionally, the optional requestComplexity.queryDepth limit was generalized so that nested logical operators are counted even when wrapped inside field-level operators (e.g. $elemMatch, $not) or plain field names, closing a bypass of the limit on both the REST API and LiveQuery.
Workarounds
There is no complete configuration-only workaround on affected versions. Setting requestComplexity.queryDepth to a small positive integer reduces exposure but does not fully prevent the issue, because the limit can be bypassed by nesting the operators inside a field-level operator. Upgrading is strongly recommended.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "parse-server"
},
"ranges": [
{
"events": [
{
"introduced": "9.0.0"
},
{
"fixed": "9.9.1-alpha.12"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "npm",
"name": "parse-server"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "8.6.82"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-06-19T14:50:14Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Impact\n\nParse Server is vulnerable to denial of service. A remote attacker can send a single, small query (~1 KB) containing deeply nested query condition operators. Parse Server processes the nested structure with exponential time complexity, which blocks the Node.js event loop and makes the server unresponsive to all clients for the duration of processing. A single request can occupy the event loop for many seconds, and the request is repeatable. The issue affects the REST API and LiveQuery query handling and is reachable in the default configuration. Exploitation requires only the public application identifier; no user authentication is needed.\n\n### Patches\n\nThe internal query-traversal helper that previously re-walked nested arrays \u2014 causing exponential-time processing of nested `$or`/`$and`/`$nor` operators \u2014 was corrected to traverse queries in linear time. Additionally, the optional `requestComplexity.queryDepth` limit was generalized so that nested logical operators are counted even when wrapped inside field-level operators (e.g. `$elemMatch`, `$not`) or plain field names, closing a bypass of the limit on both the REST API and LiveQuery.\n\n### Workarounds\n\nThere is no complete configuration-only workaround on affected versions. Setting `requestComplexity.queryDepth` to a small positive integer reduces exposure but does not fully prevent the issue, because the limit can be bypassed by nesting the operators inside a field-level operator. Upgrading is strongly recommended.",
"id": "GHSA-cgxm-vr2f-6fj8",
"modified": "2026-06-19T14:50:14Z",
"published": "2026-06-19T14:50:14Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/parse-community/parse-server/security/advisories/GHSA-cgxm-vr2f-6fj8"
},
{
"type": "WEB",
"url": "https://github.com/parse-community/parse-server/pull/10511"
},
{
"type": "WEB",
"url": "https://github.com/parse-community/parse-server/pull/10512"
},
{
"type": "PACKAGE",
"url": "https://github.com/parse-community/parse-server"
}
],
"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": "parse-server: Denial of service via exponential-time processing of deeply nested query operators"
}
GHSA-CHCW-QM6Q-PG64
Vulnerability from github – Published: 2026-10-17 00:31 – Updated: 2026-10-20 21:30Text::CSV_XS versions before 1.65 for Perl allow quadratic CPU use by copying the unparsed remainder per record of CR-only input in getline.
With eol unset, the default, getline reads with Perl's default line separator, so input with CR-only line endings arrives as one chunk. After each record the parser copies the whole unparsed remainder into a new buffer, which the next call parses and copies again, so the work grows with the square of the input size.
A reader with default options that is sent CSV with classic Mac line endings spends seconds of CPU time on a megabyte of input.
{
"affected": [],
"aliases": [
"CVE-2026-110755"
],
"database_specific": {
"cwe_ids": [
"CWE-407"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-10-16T23:17:00Z",
"severity": "HIGH"
},
"details": "Text::CSV_XS versions before 1.65 for Perl allow quadratic CPU use by copying the unparsed remainder per record of CR-only input in getline.\n\nWith eol unset, the default, getline reads with Perl\u0027s default line separator, so input with CR-only line endings arrives as one chunk. After each record the parser copies the whole unparsed remainder into a new buffer, which the next call parses and copies again, so the work grows with the square of the input size.\n\nA reader with default options that is sent CSV with classic Mac line endings spends seconds of CPU time on a megabyte of input.",
"id": "GHSA-chcw-qm6q-pg64",
"modified": "2026-10-20T21:30:43Z",
"published": "2026-10-17T00:31:19Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-110755"
},
{
"type": "WEB",
"url": "https://github.com/cpan-authors/Text-CSV_XS/commit/f25e00aacd6fc15857b22487cb2e5ca263f377e0.patch"
},
{
"type": "WEB",
"url": "https://metacpan.org/release/HMBRAND/Text-CSV_XS-1.65/changes"
}
],
"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"
}
]
}
No mitigation information available for this CWE.
No CAPEC attack patterns related to this CWE.