Common Weakness Enumeration

CWE-1333

Allowed

Inefficient 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-C3PH-4HJ5-R598

Vulnerability from github – Published: 2024-06-27 00:31 – Updated: 2024-06-27 00:31
VLAI
Details

An issue was discovered in GitLab CE/EE affecting all versions starting from 9.2 prior to 16.11.5, starting from 17.0 prior to 17.0.3, and starting from 17.1 prior to 17.1.1, with the processing logic for generating link in dependency files can lead to a regular expression DoS attack on the server

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2024-1493"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-400"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2024-06-27T00:15:10Z",
    "severity": "MODERATE"
  },
  "details": "An issue was discovered in GitLab CE/EE affecting all versions starting from 9.2 prior to 16.11.5, starting from 17.0 prior to 17.0.3, and starting from 17.1 prior to 17.1.1, with the processing logic for generating link in dependency files can lead to a regular  expression DoS attack on the server",
  "id": "GHSA-c3ph-4hj5-r598",
  "modified": "2024-06-27T00:31:04Z",
  "published": "2024-06-27T00:31:04Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2024-1493"
    },
    {
      "type": "WEB",
      "url": "https://hackerone.com/reports/2370084"
    },
    {
      "type": "WEB",
      "url": "https://gitlab.com/gitlab-org/gitlab/-/issues/441806"
    }
  ],
  "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:H",
      "type": "CVSS_V3"
    }
  ]
}

GHSA-C4RQ-3M3G-8WGX

Vulnerability from github – Published: 2026-05-06 18:24 – Updated: 2026-05-06 18:24
VLAI
Summary
Nokogiri CSS selector tokenizer has regular expression backtracking
Details

Summary

Nokogiri's CSS selector tokenizer contains regular expressions whose construction may result in exponential regex backtracking on adversarial selectors. Three ReDoS vectors are addressed in this release:

  1. String-literal tokenization on certain unterminated quoted-string input.
  2. String-literal tokenization on a separate class of hex-escape-rich input.
  3. Identifier tokenization on hex-escape-rich input.

The public CSS selector methods that funnel through the affected tokenizer are Nokogiri::CSS.xpath_for, Node#css, Node#at_css, Searchable#search, and CSS::Parser#parse.

Mitigation

Upgrade to Nokogiri >= 1.19.3.

If users are unable to upgrade, two options are available:

  • Avoid the use of attacker-controlled text in CSS selectors. Applications that only pass developer-authored selectors to Nokogiri are not directly exposed.
  • Set global Regexp.timeout (Ruby 3.2+, JRuby 9.4+) to bound parse time.

Severity

The Nokogiri maintainers have evaluated this as High Severity (CVSS 7.5, AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H).

An attacker able to inject user-supplied text into a CSS selector parse method can cause exponential backtracking, resulting in a potential denial of service.

Resources

Credit

Vector 1 was responsibly reported by @colby-swandale. Vectors 2 and 3 were discovered by @flavorjones during the response to the original report.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "RubyGems",
        "name": "nokogiri"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "1.19.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-05-06T18:24:18Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "## Summary\n\nNokogiri\u0027s CSS selector tokenizer contains regular expressions whose construction may result in exponential regex backtracking on adversarial selectors. Three ReDoS vectors are addressed in this release:\n\n1. String-literal tokenization on certain unterminated quoted-string input.\n2. String-literal tokenization on a separate class of hex-escape-rich input.\n3. Identifier tokenization on hex-escape-rich input.\n\nThe public CSS selector methods that funnel through the affected tokenizer are `Nokogiri::CSS.xpath_for`, `Node#css`, `Node#at_css`, `Searchable#search`, and `CSS::Parser#parse`.\n\n\n## Mitigation\n\nUpgrade to Nokogiri `\u003e= 1.19.3`.\n\nIf users are unable to upgrade, two options are available:\n\n- Avoid the use of attacker-controlled text in CSS selectors. Applications that only pass developer-authored selectors to Nokogiri are not directly exposed.\n- Set global `Regexp.timeout` (Ruby 3.2+, JRuby 9.4+) to bound parse time.\n\n## Severity\n\nThe Nokogiri maintainers have evaluated this as **High Severity** (CVSS 7.5, `AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H`).\n\nAn attacker able to inject user-supplied text into a CSS selector parse method can cause exponential backtracking, resulting in a potential denial of service.\n\n\n## Resources\n\n- [CWE-1333: Inefficient Regular Expression Complexity](https://cwe.mitre.org/data/definitions/1333.html)\n\n\n## Credit\n\nVector 1 was responsibly reported by @colby-swandale. Vectors 2 and 3 were discovered by @flavorjones during the response to the original report.",
  "id": "GHSA-c4rq-3m3g-8wgx",
  "modified": "2026-05-06T18:24:18Z",
  "published": "2026-05-06T18:24:18Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/sparklemotion/nokogiri/security/advisories/GHSA-c4rq-3m3g-8wgx"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/sparklemotion/nokogiri"
    }
  ],
  "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": "Nokogiri CSS selector tokenizer has regular expression backtracking"
}

GHSA-C6HR-W26Q-C636

Vulnerability from github – Published: 2026-03-02 22:17 – Updated: 2026-03-19 18:33
VLAI
Summary
OpenClaw has ReDoS and regex injection via unescaped Feishu mention metadata in RegExp construction
Details

Summary

extensions/feishu/src/bot.ts constructed new RegExp() directly from Feishu mention metadata (mention.name, mention.key) in stripBotMention() without escaping regex metacharacters.

Affected Packages / Versions

  • Package: npm openclaw
  • Affected versions: <= 2026.2.17
  • First affected release: 2026.2.6
  • Patched version: 2026.2.19

Impact

  • ReDoS: crafted nested-quantifier patterns in mention metadata can trigger catastrophic backtracking and block message processing.
  • Regex injection: metacharacters in mention metadata can remove unintended message content before it is sent to the model.

Fix Commit(s)

  • 7e67ab75cc2f0e93569d12fecd1411c2961fcc8c
  • 74268489137510b6f6349919d1e197b17290d92c

Thanks @allsmog for reporting.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "openclaw"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "2026.2.19"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-22178"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-03-02T22:17:30Z",
    "nvd_published_at": "2026-03-18T02:16:22Z",
    "severity": "MODERATE"
  },
  "details": "## Summary\n\n`extensions/feishu/src/bot.ts` constructed `new RegExp()` directly from Feishu mention metadata (`mention.name`, `mention.key`) in `stripBotMention()` without escaping regex metacharacters.\n\n## Affected Packages / Versions\n\n- Package: npm `openclaw`\n- Affected versions: `\u003c= 2026.2.17`\n- First affected release: `2026.2.6`\n- Patched version: `2026.2.19`\n\n## Impact\n\n- ReDoS: crafted nested-quantifier patterns in mention metadata can trigger catastrophic backtracking and block message processing.\n- Regex injection: metacharacters in mention metadata can remove unintended message content before it is sent to the model.\n\n## Fix Commit(s)\n\n- `7e67ab75cc2f0e93569d12fecd1411c2961fcc8c`\n- `74268489137510b6f6349919d1e197b17290d92c`\n\nThanks @allsmog for reporting.",
  "id": "GHSA-c6hr-w26q-c636",
  "modified": "2026-03-19T18:33:51Z",
  "published": "2026-03-02T22:17:30Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/openclaw/openclaw/security/advisories/GHSA-c6hr-w26q-c636"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-22178"
    },
    {
      "type": "WEB",
      "url": "https://github.com/openclaw/openclaw/commit/74268489137510b6f6349919d1e197b17290d92c"
    },
    {
      "type": "WEB",
      "url": "https://github.com/openclaw/openclaw/commit/7e67ab75cc2f0e93569d12fecd1411c2961fcc8c"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/openclaw/openclaw"
    },
    {
      "type": "WEB",
      "url": "https://www.vulncheck.com/advisories/openclaw-redos-and-regex-injection-via-unescaped-feishu-mention-metadata"
    }
  ],
  "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:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "OpenClaw has ReDoS and regex injection via unescaped Feishu mention metadata in RegExp construction"
}

GHSA-C8HV-77R5-H5F7

Vulnerability from github – Published: 2026-07-13 09:31 – Updated: 2026-07-13 09:31
VLAI
Details

Mattermost versions 11.7.x <= 11.7.2, 11.6.x <= 11.6.4, 10.11.x <= 10.11.19 fail to validate the length and content of message attachment field values, which allows an authenticated attacker to cause a denial of service for all users in a channel via a post containing a specially crafted payload that triggers catastrophic backtracking in the client-side markdown parser.. Mattermost Advisory ID: MMSA-2026-00658

Show details on source website

{
  "affected": [],
  "aliases": [
    "CVE-2026-6850"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": false,
    "github_reviewed_at": null,
    "nvd_published_at": "2026-07-13T09:16:24Z",
    "severity": "MODERATE"
  },
  "details": "Mattermost versions 11.7.x \u003c= 11.7.2, 11.6.x \u003c= 11.6.4, 10.11.x \u003c= 10.11.19 fail to validate the length and content of message attachment field values, which allows an authenticated attacker to cause a denial of service for all users in a channel via a post containing a specially crafted payload that triggers catastrophic backtracking in the client-side markdown parser.. Mattermost Advisory ID: MMSA-2026-00658",
  "id": "GHSA-c8hv-77r5-h5f7",
  "modified": "2026-07-13T09:31:43Z",
  "published": "2026-07-13T09:31:43Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-6850"
    },
    {
      "type": "WEB",
      "url": "https://mattermost.com/security-updates"
    }
  ],
  "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:H",
      "type": "CVSS_V3"
    }
  ]
}

GHSA-C8J7-8CV4-2XMQ

Vulnerability from github – Published: 2026-07-20 21:34 – Updated: 2026-07-20 21:34
VLAI
Summary
Mistune plugins/formatting: quadratic-time parsing on long runs of `~~x~~`, `==x==`, and `^^x^^` markers (strikethrough / mark / insert)
Details

Summary

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

  1. 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.
  2. 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 == / ^^).
  3. 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.
  4. 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.

Show details on source website

{
  "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-C9F4-XJ24-8JQX

Vulnerability from github – Published: 2017-10-24 18:33 – Updated: 2021-09-08 21:59
VLAI
Summary
Regular Expression Denial of Service in uglify-js
Details

Versions of uglify-js prior to 2.6.0 are affected by a regular expression denial of service vulnerability when malicious inputs are passed into the parse() method.

Proof of Concept

var u = require('uglify-js');
var genstr = function (len, chr) {
    var result = "";
    for (i=0; i<=len; i++) {
        result = result + chr;
    }

    return result;
}

u.parse("var a = " + genstr(process.argv[2], "1") + ".1ee7;");

Results

$ time node test.js 10000
real    0m1.091s
user    0m1.047s
sys 0m0.039s

$ time node test.js 80000
real    0m6.486s
user    0m6.229s
sys 0m0.094s

Recommendation

Update to version 2.6.0 or later.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "uglify-js"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "2.6.0"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2015-8858"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2020-06-16T21:30:50Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "Versions of `uglify-js` prior to 2.6.0 are affected by a regular expression denial of service vulnerability when malicious inputs are passed into the `parse()` method.\n\n\n### Proof of Concept\n\n```\nvar u = require(\u0027uglify-js\u0027);\nvar genstr = function (len, chr) {\n    var result = \"\";\n    for (i=0; i\u003c=len; i++) {\n        result = result + chr;\n    }\n\n    return result;\n}\n\nu.parse(\"var a = \" + genstr(process.argv[2], \"1\") + \".1ee7;\");\n```\n\n### Results\n```\n$ time node test.js 10000\nreal\t0m1.091s\nuser\t0m1.047s\nsys\t0m0.039s\n\n$ time node test.js 80000\nreal\t0m6.486s\nuser\t0m6.229s\nsys\t0m0.094s\n```\n\n\n## Recommendation\n\nUpdate to version 2.6.0 or later.",
  "id": "GHSA-c9f4-xj24-8jqx",
  "modified": "2021-09-08T21:59:09Z",
  "published": "2017-10-24T18:33:36Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2015-8858"
    },
    {
      "type": "ADVISORY",
      "url": "https://github.com/advisories/GHSA-c9f4-xj24-8jqx"
    },
    {
      "type": "WEB",
      "url": "https://www.npmjs.com/advisories/48"
    },
    {
      "type": "WEB",
      "url": "http://www.openwall.com/lists/oss-security/2016/04/20/11"
    },
    {
      "type": "WEB",
      "url": "http://www.securityfocus.com/bid/96409"
    }
  ],
  "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"
    }
  ],
  "summary": "Regular Expression Denial of Service in uglify-js"
}

GHSA-C9GM-7RFJ-8W5H

Vulnerability from github – Published: 2022-05-25 00:00 – Updated: 2024-05-03 20:39
VLAI
Summary
Duplicate Advisory: ReDoS via crafted JSON input in GJSON
Details

Duplicate Advisory

This advisory has been withdrawn because it is a duplicate of GHSA-ppj4-34rq-v8j9. This link is maintained to preserve external references.

Original Description

GJSON <= 1.9.2 allows attackers to cause a redos via crafted JSON input.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "Go",
        "name": "github.com/tidwall/gjson"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "1.9.3"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2021-42248"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2022-06-06T21:20:02Z",
    "nvd_published_at": "2022-05-24T15:15:00Z",
    "severity": "HIGH"
  },
  "details": "## Duplicate Advisory\nThis advisory has been withdrawn because it is a duplicate of GHSA-ppj4-34rq-v8j9. This link is maintained to preserve external references.\n\n## Original Description\nGJSON \u003c= 1.9.2 allows attackers to cause a redos via crafted JSON input.",
  "id": "GHSA-c9gm-7rfj-8w5h",
  "modified": "2024-05-03T20:39:36Z",
  "published": "2022-05-25T00:00:38Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2021-42248"
    },
    {
      "type": "WEB",
      "url": "https://github.com/tidwall/gjson/issues/236"
    },
    {
      "type": "WEB",
      "url": "https://github.com/tidwall/gjson/issues/237"
    },
    {
      "type": "WEB",
      "url": "https://github.com/tidwall/gjson/commit/590010fdac311cc8990ef5c97448d4fec8f29944"
    },
    {
      "type": "WEB",
      "url": "https://github.com/tidwall/gjson/commit/77a57fda87dca6d0d7d4627d512a630f89a91c96"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/tidwall/gjson"
    },
    {
      "type": "WEB",
      "url": "https://pkg.go.dev/vuln/GO-2021-0265"
    }
  ],
  "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": "Duplicate Advisory: ReDoS via crafted JSON input in GJSON",
  "withdrawn": "2024-05-03T20:39:36Z"
}

GHSA-CC65-XXVF-F7R9

Vulnerability from github – Published: 2024-02-15 15:22 – Updated: 2025-01-14 16:35
VLAI
Summary
Scrapy vulnerable to ReDoS via XMLFeedSpider
Details

Impact

The following parts of the Scrapy API were found to be vulnerable to a ReDoS attack:

  • The XMLFeedSpider class or any subclass that uses the default node iterator: iternodes, as well as direct uses of the scrapy.utils.iterators.xmliter function.

  • Scrapy 2.6.0 to 2.11.0: The open_in_browser function for a response without a base tag.

Handling a malicious response could cause extreme CPU and memory usage during the parsing of its content, due to the use of vulnerable regular expressions for that parsing.

Patches

Upgrade to Scrapy 2.11.1.

If you are using Scrapy 1.8 or a lower version, and upgrading to Scrapy 2.11.1 is not an option, you may upgrade to Scrapy 1.8.4 instead.

Workarounds

For XMLFeedSpider, switch the node iterator to xml or html.

For open_in_browser, before using the function, either manually review the response content to discard a ReDos attack or manually define the base tag to avoid its automatic definition by open_in_browser later.

Acknowledgements

This security issue was reported by @nicecatch2000 through huntr.com.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "scrapy"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "2"
            },
            {
              "fixed": "2.11.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "PyPI",
        "name": "scrapy"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "1.8.4"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2024-1892"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2024-02-15T15:22:02Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "### Impact\n\nThe following parts of the Scrapy API were found to be vulnerable to a [ReDoS attack](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS):\n\n- The [`XMLFeedSpider`](https://docs.scrapy.org/en/latest/topics/spiders.html#scrapy.spiders.XMLFeedSpider) class or any subclass that uses the default node iterator: `iternodes`, as well as direct uses of the `scrapy.utils.iterators.xmliter` function.\n\n- **Scrapy 2.6.0 to 2.11.0**: The [`open_in_browser`](https://docs.scrapy.org/en/latest/topics/debug.html#scrapy.utils.response.open_in_browser) function for a response without a [base tag](https://www.w3schools.com/tags/tag_base.asp). \n\nHandling a malicious response could cause extreme CPU and memory usage during the parsing of its content, due to the use of vulnerable regular expressions for that parsing.\n\n### Patches\n\nUpgrade to Scrapy 2.11.1.\n\nIf you are using Scrapy 1.8 or a lower version, and upgrading to Scrapy 2.11.1 is not an option, you may upgrade to Scrapy 1.8.4 instead.\n\n### Workarounds\n\nFor `XMLFeedSpider`, switch the node iterator to ``xml`` or ``html``.\n\nFor `open_in_browser`, before using the function, either manually review the response content to discard a ReDos attack or manually define the base tag to avoid its automatic definition by `open_in_browser` later.\n\n### Acknowledgements\n\nThis security issue was reported by @nicecatch2000  [through huntr.com](https://huntr.com/bounties/271f94f2-1e05-4616-ac43-41752389e26b/).\n",
  "id": "GHSA-cc65-xxvf-f7r9",
  "modified": "2025-01-14T16:35:57Z",
  "published": "2024-02-15T15:22:02Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/scrapy/scrapy/security/advisories/GHSA-cc65-xxvf-f7r9"
    },
    {
      "type": "WEB",
      "url": "https://github.com/scrapy/scrapy/commit/479619b340f197a8f24c5db45bc068fb8755f2c5"
    },
    {
      "type": "WEB",
      "url": "https://github.com/scrapy/scrapy/commit/73e7c0ed011a0565a1584b8052ec757b54e5270b"
    },
    {
      "type": "WEB",
      "url": "https://docs.scrapy.org/en/latest/news.html#scrapy-1-8-4-2024-02-14"
    },
    {
      "type": "WEB",
      "url": "https://docs.scrapy.org/en/latest/news.html#scrapy-2-11-1-2024-02-14"
    },
    {
      "type": "WEB",
      "url": "https://github.com/pypa/advisory-database/tree/main/vulns/scrapy/PYSEC-2024-162.yaml"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/scrapy/scrapy"
    },
    {
      "type": "WEB",
      "url": "https://huntr.com/bounties/271f94f2-1e05-4616-ac43-41752389e26b"
    }
  ],
  "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": "Scrapy vulnerable to ReDoS via XMLFeedSpider"
}

GHSA-CG4J-Q9V8-6V38

Vulnerability from github – Published: 2026-03-23 20:52 – Updated: 2026-05-13 16:15
VLAI
Summary
Rails Active Support has a possible ReDoS vulnerability in number_to_delimited
Details

Impact

NumberToDelimitedConverter used a regular expression with gsub! to insert thousands delimiters. This could produce quadratic time complexity on long digit strings.

Releases

The fixed releases are available at the normal locations.

Credit

This issue was responsibly reported by Hackerone researcher scyoon.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "RubyGems",
        "name": "activesupport"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "8.1.0.beta1"
            },
            {
              "fixed": "8.1.2.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "RubyGems",
        "name": "activesupport"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "8.0.0.beta1"
            },
            {
              "fixed": "8.0.4.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    },
    {
      "package": {
        "ecosystem": "RubyGems",
        "name": "activesupport"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "7.2.3.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-33169"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333",
      "CWE-400"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-03-23T20:52:40Z",
    "nvd_published_at": "2026-03-24T00:16:28Z",
    "severity": "MODERATE"
  },
  "details": "### Impact\n`NumberToDelimitedConverter` used a regular expression with `gsub!` to insert thousands delimiters. This could produce quadratic time complexity on long digit strings.\n\n### Releases\nThe fixed releases are available at the normal locations.\n\n### Credit\nThis issue was responsibly reported by Hackerone researcher [scyoon](https://hackerone.com/scyoon).",
  "id": "GHSA-cg4j-q9v8-6v38",
  "modified": "2026-05-13T16:15:32Z",
  "published": "2026-03-23T20:52:40Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/security/advisories/GHSA-cg4j-q9v8-6v38"
    },
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2026-33169"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/commit/29154f1097da13d48fdb3200760b3e3da66dcb11"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/commit/b54a4b373c6f042cab6ee2033246b1c9ecc38974"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/commit/ec1a0e215efd27a3b3911aae6df978a80f456a49"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/rails/rails"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/releases/tag/v7.2.3.1"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/releases/tag/v8.0.4.1"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rails/rails/releases/tag/v8.1.2.1"
    },
    {
      "type": "WEB",
      "url": "https://github.com/rubysec/ruby-advisory-db/blob/master/gems/activesupport/CVE-2026-33169.yml"
    }
  ],
  "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:L/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "Rails Active Support has a possible ReDoS vulnerability in number_to_delimited"
}

GHSA-CGFM-XWP7-2CVR

Vulnerability from github – Published: 2022-08-31 00:00 – Updated: 2024-04-22 23:16
VLAI
Summary
Sanitize-html Vulnerable To REDoS Attacks
Details

The package sanitize-html before 2.7.1 are vulnerable to Regular Expression Denial of Service (ReDoS) due to insecure global regular expression replacement logic of HTML comment removal.

Show details on source website

{
  "affected": [
    {
      "package": {
        "ecosystem": "npm",
        "name": "sanitize-html"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "2.7.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2022-25887"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2024-04-22T23:16:47Z",
    "nvd_published_at": "2022-08-30T05:15:00Z",
    "severity": "HIGH"
  },
  "details": "The package sanitize-html before 2.7.1 are vulnerable to Regular Expression Denial of Service (ReDoS) due to insecure global regular expression replacement logic of HTML comment removal.",
  "id": "GHSA-cgfm-xwp7-2cvr",
  "modified": "2024-04-22T23:16:47Z",
  "published": "2022-08-31T00:00:24Z",
  "references": [
    {
      "type": "ADVISORY",
      "url": "https://nvd.nist.gov/vuln/detail/CVE-2022-25887"
    },
    {
      "type": "WEB",
      "url": "https://github.com/apostrophecms/sanitize-html/pull/557"
    },
    {
      "type": "WEB",
      "url": "https://github.com/apostrophecms/sanitize-html/commit/b4682c12fd30e12e82fa2d9b766de91d7d2cd23c"
    },
    {
      "type": "WEB",
      "url": "https://security.snyk.io/vuln/SNYK-JAVA-ORGWEBJARSNPM-3008102"
    },
    {
      "type": "WEB",
      "url": "https://security.snyk.io/vuln/SNYK-JS-SANITIZEHTML-2957526"
    }
  ],
  "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": "Sanitize-html Vulnerable To REDoS Attacks"
}

Mitigation
Architecture and Design

Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.

Mitigation
System Configuration

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
Implementation

Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.

Mitigation
Implementation

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.