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.
1000 vulnerabilities reference this CWE, most recent first.
GHSA-RQV2-275X-2JQ5
Vulnerability from github – Published: 2023-01-18 18:19 – Updated: 2023-10-23 19:17There is a denial of service vulnerability in the multipart parsing component of Rack. This vulnerability has been assigned the CVE identifier CVE-2022-44572.
Versions Affected: >= 2.0.0 Not affected: None. Fixed Versions: 2.0.9.2, 2.1.4.2, 2.2.6.1, 3.0.0.1 Impact
Carefully crafted input can cause RFC2183 multipart boundary parsing in Rack to take an unexpected amount of time, possibly resulting in a denial of service attack vector. Any applications that parse multipart posts using Rack (virtually all Rails applications) are impacted. Releases
The fixed releases are available at the normal locations. Workarounds
There are no feasible workarounds for this issue. Patches
To aid users who aren’t able to upgrade immediately we have provided patches for the two supported release series. They are in git-am format and consist of a single changeset.
2-0-Forbid-control-characters-in-attributes.patch - Patch for 2.0 series
2-1-Forbid-control-characters-in-attributes.patch - Patch for 2.1 series
2-2-Forbid-control-characters-in-attributes.patch - Patch for 2.2 series
3-0-Forbid-control-characters-in-attributes.patch - Patch for 3.0 series
{
"affected": [
{
"package": {
"ecosystem": "RubyGems",
"name": "rack"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0"
},
{
"fixed": "2.0.9.2"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "RubyGems",
"name": "rack"
},
"ranges": [
{
"events": [
{
"introduced": "2.1.0.0"
},
{
"fixed": "2.1.4.2"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "RubyGems",
"name": "rack"
},
"ranges": [
{
"events": [
{
"introduced": "2.2.0.0"
},
{
"fixed": "2.2.6.1"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "RubyGems",
"name": "rack"
},
"ranges": [
{
"events": [
{
"introduced": "3.0.0.0"
},
{
"fixed": "3.0.4.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2022-44572"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2023-01-18T18:19:21Z",
"nvd_published_at": "2023-02-09T20:15:00Z",
"severity": "LOW"
},
"details": "There is a denial of service vulnerability in the multipart parsing component of Rack. This vulnerability has been assigned the CVE identifier CVE-2022-44572.\n\nVersions Affected: \u003e= 2.0.0 Not affected: None. Fixed Versions: 2.0.9.2, 2.1.4.2, 2.2.6.1, 3.0.0.1\nImpact\n\nCarefully crafted input can cause RFC2183 multipart boundary parsing in Rack to take an unexpected amount of time, possibly resulting in a denial of service attack vector. Any applications that parse multipart posts using Rack (virtually all Rails applications) are impacted.\nReleases\n\nThe fixed releases are available at the normal locations.\nWorkarounds\n\nThere are no feasible workarounds for this issue.\nPatches\n\nTo aid users who aren\u2019t able to upgrade immediately we have provided patches for the two supported release series. They are in git-am format and consist of a single changeset.\n\n 2-0-Forbid-control-characters-in-attributes.patch - Patch for 2.0 series\n 2-1-Forbid-control-characters-in-attributes.patch - Patch for 2.1 series\n 2-2-Forbid-control-characters-in-attributes.patch - Patch for 2.2 series\n 3-0-Forbid-control-characters-in-attributes.patch - Patch for 3.0 series\n",
"id": "GHSA-rqv2-275x-2jq5",
"modified": "2023-10-23T19:17:24Z",
"published": "2023-01-18T18:19:21Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2022-44572"
},
{
"type": "WEB",
"url": "https://hackerone.com/reports/1639882"
},
{
"type": "PACKAGE",
"url": "https://github.com/rack/rack"
},
{
"type": "WEB",
"url": "https://github.com/rack/rack/releases/tag/v3.0.4.1"
},
{
"type": "WEB",
"url": "https://github.com/rubysec/ruby-advisory-db/blob/master/gems/rack/CVE-2022-44572.yml"
},
{
"type": "WEB",
"url": "https://www.debian.org/security/2023/dsa-5530"
}
],
"schema_version": "1.4.0",
"severity": [],
"summary": "Denial of service via multipart parsing in Rack"
}
GHSA-RR4Q-H87Q-GM3V
Vulnerability from github – Published: 2026-02-26 18:31 – Updated: 2026-02-26 18:31Inefficient Regular Expression Complexity (CWE-1333) in the AI Inference Anonymization Engine in Kibana can lead Denial of Service via Regular Expression Exponential Blowup (CAPEC-492).
{
"affected": [],
"aliases": [
"CVE-2026-26936"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2026-02-26T18:23:07Z",
"severity": "MODERATE"
},
"details": "Inefficient Regular Expression Complexity (CWE-1333) in the AI Inference Anonymization Engine in Kibana can lead Denial of Service via Regular Expression Exponential Blowup (CAPEC-492).",
"id": "GHSA-rr4q-h87q-gm3v",
"modified": "2026-02-26T18:31:42Z",
"published": "2026-02-26T18:31:42Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-26936"
},
{
"type": "WEB",
"url": "https://discuss.elastic.co/t/kibana-8-19-11-9-2-5-security-update-esa-2026-14/385250"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:H/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
]
}
GHSA-RRF6-PXG8-684G
Vulnerability from github – Published: 2025-07-23 15:31 – Updated: 2025-07-24 12:46Summary
The regular expression patched to mitigate the ReDoS vulnerability by limiting the length of string fails to catch inputs that exceed this limit.
Details
In version 3.0.1, you can find a commit like the one in the link below, which was made to prevent ReDoS. https://github.com/rennf93/fastapi-guard/commit/d9d50e8130b7b434cdc1b001b8cfd03a06729f7f
This commit mitigates the vulnerability by limiting the length of the input string, as shown in the example below.
r"<script[^>]*>[^<]*<\\/script\\s*>" -> <script[^>]{0,100}>[^<]{0,1000}<\\/script\\s{0,10}>
This type of patch fails to catch cases where the string representing the attributes of a tag exceeds 100 characters. Therefore, most of the regex patterns present in version 3.0.1 can be bypassed.
PoC
- clone the fastapi-guard repository
- Navigate to the examples directory and modify the main.py source code. Change the HTTP method for the root route from GET to POST.
- After that, set up the example app environment by running the docker-compose up command. Then, run the Python code below to verify that the two requests return different results.
import requests
URL = "<http://localhost:8000>"
obvious_payload = {
"obvious" : "<script>alert(1);</script>"
}
response = requests.post(url=URL, json=obvious_payload)
print(f"[+] response of first request: {response.text}")
bypassed_payload = {
"suspicious" : f'<script id="i_can_bypass_regex_filtering{'a'*100}">alert(1)</script>'
}
response = requests.post(url=URL, json=bypassed_payload)
print(f"[+] response of second request: {response.text}")
Impact
Due to this vulnerability, most of the regex patterns can potentially be bypassed, making the application vulnerable to attacks such as XSS and SQL Injection.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "fastapi-guard"
},
"ranges": [
{
"events": [
{
"introduced": "3.0.1"
},
{
"fixed": "3.0.2"
}
],
"type": "ECOSYSTEM"
}
],
"versions": [
"3.0.1"
]
}
],
"aliases": [
"CVE-2025-54365"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-185",
"CWE-20"
],
"github_reviewed": true,
"github_reviewed_at": "2025-07-23T15:31:12Z",
"nvd_published_at": "2025-07-23T23:15:24Z",
"severity": "HIGH"
},
"details": "### Summary\n\nThe regular expression patched to mitigate the ReDoS vulnerability by limiting the length of string fails to catch inputs that exceed this limit.\n\n### Details\n\nIn version 3.0.1, you can find a commit like the one in the link below, which was made to prevent ReDoS.\nhttps://github.com/rennf93/fastapi-guard/commit/d9d50e8130b7b434cdc1b001b8cfd03a06729f7f\n\nThis commit mitigates the vulnerability by limiting the length of the input string, as shown in the example below.\n`r\"\u003cscript[^\u003e]*\u003e[^\u003c]*\u003c\\\\/script\\\\s*\u003e\"` -\u003e `\u003cscript[^\u003e]{0,100}\u003e[^\u003c]{0,1000}\u003c\\\\/script\\\\s{0,10}\u003e`\n\nThis type of patch fails to catch cases where the string representing the attributes of a \u003cscript\u003e tag exceeds 100 characters.\nTherefore, most of the regex patterns present in version 3.0.1 can be bypassed.\n\n### PoC\n\n1. clone the fastapi-guard repository\n2. Navigate to the examples directory and modify the main.py source code. Change the HTTP method for the root route from GET to POST.\n\u003cimg width=\"1013\" height=\"554\" alt=\"image\" src=\"https://github.com/user-attachments/assets/cf93ea37-2fd7-4251-abb6-b55f88685f54\" /\u003e\n3. After that, set up the example app environment by running the docker-compose up command. Then, run the Python code below to verify that the two requests return different results.\n\n```python\nimport requests\n\nURL = \"\u003chttp://localhost:8000\u003e\"\n\nobvious_payload = {\n \"obvious\" : \"\u003cscript\u003ealert(1);\u003c/script\u003e\"\n}\nresponse = requests.post(url=URL, json=obvious_payload)\nprint(f\"[+] response of first request: {response.text}\")\n\nbypassed_payload = {\n \"suspicious\" : f\u0027\u003cscript id=\"i_can_bypass_regex_filtering{\u0027a\u0027*100}\"\u003ealert(1)\u003c/script\u003e\u0027\n}\n\nresponse = requests.post(url=URL, json=bypassed_payload)\nprint(f\"[+] response of second request: {response.text}\")\n\n```\n\u003cimg width=\"836\" height=\"112\" alt=\"image\" src=\"https://github.com/user-attachments/assets/11dcccb2-6179-44b1-9628-ae0a787e3bb7\" /\u003e\n\n### Impact\n\nDue to this vulnerability, most of the regex patterns can potentially be bypassed, making the application vulnerable to attacks such as XSS and SQL Injection.",
"id": "GHSA-rrf6-pxg8-684g",
"modified": "2025-07-24T12:46:22Z",
"published": "2025-07-23T15:31:12Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/rennf93/fastapi-guard/security/advisories/GHSA-rrf6-pxg8-684g"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-54365"
},
{
"type": "WEB",
"url": "https://github.com/rennf93/fastapi-guard/commit/0829292c322d33dc14ab00c5451c5c138148035a"
},
{
"type": "WEB",
"url": "https://github.com/rennf93/fastapi-guard/commit/d9d50e8130b7b434cdc1b001b8cfd03a06729f7f"
},
{
"type": "PACKAGE",
"url": "https://github.com/rennf93/fastapi-guard"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:L/VA:H/SC:N/SI:N/SA:N/E:P",
"type": "CVSS_V4"
}
],
"summary": "FastAPI Guard has a regex bypass"
}
GHSA-RRM6-WVJ7-CWH2
Vulnerability from github – Published: 2023-04-21 20:24 – Updated: 2025-11-04 16:43Impact
The SQL parser contains a regular expression that is vulnerable to ReDoS (Regular Expression Denial of Service). The vulnerability may lead to Denial of Service (DoS).
Patches
This issues has been fixed in sqlparse 0.4.4.
Workarounds
None.
References
This issue was discovered and reported by GHSL team member @erik-krogh (Erik Krogh Kristensen). - Commit that introduced the vulnerability: e75e35869473832a1eb67772b1adfee2db11b85a
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "sqlparse"
},
"ranges": [
{
"events": [
{
"introduced": "0.1.15"
},
{
"fixed": "0.4.4"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2023-30608"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2023-04-21T20:24:21Z",
"nvd_published_at": "2023-04-18T22:15:08Z",
"severity": "MODERATE"
},
"details": "### Impact\nThe SQL parser contains a regular expression that is vulnerable to [ReDoS](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS) (Regular Expression Denial of Service). The vulnerability may lead to Denial of Service (DoS).\n\n### Patches\nThis issues has been fixed in sqlparse 0.4.4.\n\n### Workarounds\nNone. \n\n### References\nThis issue was discovered and reported by GHSL team member [@erik-krogh (Erik Krogh Kristensen)](https://github.com/erik-krogh).\n- Commit that introduced the vulnerability: e75e35869473832a1eb67772b1adfee2db11b85a",
"id": "GHSA-rrm6-wvj7-cwh2",
"modified": "2025-11-04T16:43:46Z",
"published": "2023-04-21T20:24:21Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/security/advisories/GHSA-rrm6-wvj7-cwh2"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2023-30608"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/commit/c457abd5f097dd13fb21543381e7cfafe7d31cfb"
},
{
"type": "WEB",
"url": "https://github.com/andialbrecht/sqlparse/commit/e75e35869473832a1eb67772b1adfee2db11b85a"
},
{
"type": "PACKAGE",
"url": "https://github.com/andialbrecht/sqlparse"
},
{
"type": "WEB",
"url": "https://github.com/pypa/advisory-database/tree/main/vulns/sqlparse/PYSEC-2023-87.yaml"
},
{
"type": "WEB",
"url": "https://lists.debian.org/debian-lts-announce/2023/05/msg00017.html"
},
{
"type": "WEB",
"url": "https://lists.debian.org/debian-lts-announce/2024/12/msg00022.html"
},
{
"type": "WEB",
"url": "https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:L/AC:L/PR:N/UI:R/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
},
{
"score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:A/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
"type": "CVSS_V4"
}
],
"summary": "sqlparse contains a regular expression that is vulnerable to Regular Expression Denial of Service"
}
GHSA-RRR8-F88R-H8Q6
Vulnerability from github – Published: 2024-09-18 15:52 – Updated: 2024-10-07 21:52Impact
A bad regular expression is generated any time you have two parameters within a single segment, when adding a - at the end, like /:a-:b-.
Patches
Update to find-my-way v8.2.2 or v9.0.1. or subsequent versions.
Workarounds
No known workarounds.
References
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "find-my-way"
},
"ranges": [
{
"events": [
{
"introduced": "5.5.0"
},
{
"fixed": "8.2.2"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "npm",
"name": "find-my-way"
},
"ranges": [
{
"events": [
{
"introduced": "9.0.0"
},
{
"fixed": "9.0.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2024-45813"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2024-09-18T15:52:33Z",
"nvd_published_at": "2024-09-18T17:15:19Z",
"severity": "HIGH"
},
"details": "### Impact\n\nA bad regular expression is generated any time you have two parameters within a single segment, when adding a `-` at the end, like `/:a-:b-`.\n\n### Patches\n\nUpdate to find-my-way v8.2.2 or v9.0.1. or subsequent versions.\n\n### Workarounds\n\nNo known workarounds.\n\n### References\n\n- [CVE-2024-45296](https://github.com/advisories/GHSA-9wv6-86v2-598j)\n- [Detailed blog post about `path-to-regexp` vulnerability](https://blakeembrey.com/posts/2024-09-web-redos/)",
"id": "GHSA-rrr8-f88r-h8q6",
"modified": "2024-10-07T21:52:21Z",
"published": "2024-09-18T15:52:33Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/delvedor/find-my-way/security/advisories/GHSA-rrr8-f88r-h8q6"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-45813"
},
{
"type": "WEB",
"url": "https://github.com/delvedor/find-my-way/commit/17fae694dcefc056045da201681c1530f0f80518"
},
{
"type": "WEB",
"url": "https://github.com/delvedor/find-my-way/commit/5e9e0eb5d8d438e06a185d5e536a896572dd0440"
},
{
"type": "WEB",
"url": "https://github.com/delvedor/find-my-way/commit/66fa03923355b8da1db4ba572d66a4fee4a57cf5"
},
{
"type": "WEB",
"url": "https://blakeembrey.com/posts/2024-09-web-redos"
},
{
"type": "ADVISORY",
"url": "https://github.com/advisories/GHSA-9wv6-86v2-598j"
},
{
"type": "PACKAGE",
"url": "https://github.com/delvedor/find-my-way"
}
],
"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",
"type": "CVSS_V4"
}
],
"summary": "find-my-way has a ReDoS vulnerability in multiparametric routes"
}
GHSA-RRRM-QJM4-V8HF
Vulnerability from github – Published: 2022-01-14 21:04 – Updated: 2022-01-14 19:56Impact
What kind of vulnerability is it?
Denial of service.
The regular expression block.def may cause catastrophic backtracking against some strings.
PoC is the following.
import * as marked from "marked";
marked.parse(`[x]:${' '.repeat(1500)}x ${' '.repeat(1500)} x`);
Who is impacted?
Anyone who runs untrusted markdown through marked and does not use a worker with a time limit.
Patches
Has the problem been patched?
Yes
What versions should users upgrade to?
4.0.10
Workarounds
Is there a way for users to fix or remediate the vulnerability without upgrading?
Do not run untrusted markdown through marked or run marked on a worker thread and set a reasonable time limit to prevent draining resources.
References
Are there any links users can visit to find out more?
- https://marked.js.org/using_advanced#workers
- https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
For more information
If you have any questions or comments about this advisory:
- Open an issue in marked
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "marked"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "4.0.10"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2022-21680"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2022-01-14T19:56:20Z",
"nvd_published_at": "2022-01-14T17:15:00Z",
"severity": "HIGH"
},
"details": "### Impact\n\n_What kind of vulnerability is it?_\n\nDenial of service.\n\nThe regular expression `block.def` may cause catastrophic backtracking against some strings.\nPoC is the following.\n\n```javascript\nimport * as marked from \"marked\";\n\nmarked.parse(`[x]:${\u0027 \u0027.repeat(1500)}x ${\u0027 \u0027.repeat(1500)} x`);\n```\n\n_Who is impacted?_\n\nAnyone who runs untrusted markdown through marked and does not use a worker with a time limit.\n\n### Patches\n\n_Has the problem been patched?_\n\nYes\n\n_What versions should users upgrade to?_\n\n4.0.10\n\n### Workarounds\n\n_Is there a way for users to fix or remediate the vulnerability without upgrading?_\n\nDo not run untrusted markdown through marked or run marked on a [worker](https://marked.js.org/using_advanced#workers) thread and set a reasonable time limit to prevent draining resources.\n\n### References\n\n_Are there any links users can visit to find out more?_\n\n- https://marked.js.org/using_advanced#workers\n- https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS\n\n### For more information\n\nIf you have any questions or comments about this advisory:\n\n* Open an issue in [marked](https://github.com/markedjs/marked)\n",
"id": "GHSA-rrrm-qjm4-v8hf",
"modified": "2022-01-14T19:56:20Z",
"published": "2022-01-14T21:04:41Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/markedjs/marked/security/advisories/GHSA-rrrm-qjm4-v8hf"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2022-21680"
},
{
"type": "WEB",
"url": "https://github.com/markedjs/marked/commit/c4a3ccd344b6929afa8a1d50ac54a721e57012c0"
},
{
"type": "PACKAGE",
"url": "https://github.com/markedjs/marked"
},
{
"type": "WEB",
"url": "https://github.com/markedjs/marked/releases/tag/v4.0.10"
},
{
"type": "WEB",
"url": "https://lists.fedoraproject.org/archives/list/package-announce@lists.fedoraproject.org/message/AIXDMC3CSHYW3YWVSQOXAWLUYQHAO5UX"
}
],
"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": "Inefficient Regular Expression Complexity in marked"
}
GHSA-RRV8-H7P8-RX55
Vulnerability from github – Published: 2026-09-08 20:28 – Updated: 2026-09-08 20:28Summary
NLTK's Text.findall() and TokenSearcher.findall() methods accept user-supplied regular expressions and pass them to the Python re engine without timeout or validation, enabling catastrophic backtracking (ReDoS). This issue is isolated to the nltk.text module and was resolved in a prior commit.
Affected Code
nltk/text.py — TokenSearcher.findall() (line 255) / Text.findall() (line 620)
TokenSearcher.__init__ builds an internal string by wrapping each token in angle brackets. The findall() method preprocesses the caller-supplied regexp and runs it directly against this string with no timeout:
def findall(self, regexp):
# Preprocessing does NOT prevent catastrophic backtracking
regexp = re.sub(r"\s", "", regexp)
regexp = re.sub(r"<", "(?:<(?:", regexp)
regexp = re.sub(r">", ")>)", regexp)
regexp = re.sub(r"(?<!\\)\.", "[^>]", regexp)
# User-controlled regexp executed with no timeout
hits = re.findall(regexp, self._raw)
The preprocessing transforms < and > angle-bracket syntax but does not inspect or reject catastrophically backtracking patterns.
Proof of Concept
import nltk
import time
# Token of 25 'a' characters produces self._raw = "<aaaaaaaaaaaaaaaaaaaaaaaa!>"
# The trailing '!' ensures no match, forcing full backtracking.
text = nltk.Text(["a" * 25 + "!"])
# Pattern after transformation:
# < → (?:<(?:
# > → )>)
# Becomes: (?:<(?:((a+)+)b)>)
# re.findall runs this against "<aaaaaaaaaaaaaaaaaaaaaaaa!>" — hangs.
start = time.time()
text.findall(r"<((a+)+)b>") # Never returns
Impact
Applications that expose Text.findall() to external input are vulnerable to a denial of service. An unauthenticated attacker can cause indefinite CPU saturation with one request, denying service to all other users of the Python process.
Remediation
This vulnerability was patched in commit d8e4753. Users should update to the patched version.
Credit
Tool: Kira by Offgrid Security
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 3.9.4"
},
"package": {
"ecosystem": "PyPI",
"name": "nltk"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "3.10.0"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-80205"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2026-09-08T20:28:13Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "### Summary\nNLTK\u0027s `Text.findall()` and `TokenSearcher.findall()` methods accept user-supplied regular expressions and pass them to the Python `re` engine without timeout or validation, enabling catastrophic backtracking (ReDoS). This issue is isolated to the `nltk.text` module and was resolved in a prior commit.\n\n### Affected Code\n`nltk/text.py` \u2014 `TokenSearcher.findall()` (line 255) / `Text.findall()` (line 620)\n\n`TokenSearcher.__init__` builds an internal string by wrapping each token in angle brackets. The `findall()` method preprocesses the caller-supplied regexp and runs it directly against this string with no timeout:\n\n```python\ndef findall(self, regexp):\n # Preprocessing does NOT prevent catastrophic backtracking\n regexp = re.sub(r\"\\s\", \"\", regexp)\n regexp = re.sub(r\"\u003c\", \"(?:\u003c(?:\", regexp)\n regexp = re.sub(r\"\u003e\", \")\u003e)\", regexp)\n regexp = re.sub(r\"(?\u003c!\\\\)\\.\", \"[^\u003e]\", regexp)\n\n # User-controlled regexp executed with no timeout\n hits = re.findall(regexp, self._raw)\n```\nThe preprocessing transforms `\u003c` and `\u003e` angle-bracket syntax but does not inspect or reject catastrophically backtracking patterns.\n\n### Proof of Concept\n```python\nimport nltk\nimport time\n\n# Token of 25 \u0027a\u0027 characters produces self._raw = \"\u003caaaaaaaaaaaaaaaaaaaaaaaa!\u003e\"\n# The trailing \u0027!\u0027 ensures no match, forcing full backtracking.\ntext = nltk.Text([\"a\" * 25 + \"!\"])\n\n# Pattern after transformation:\n# \u003c \u2192 (?:\u003c(?:\n# \u003e \u2192 )\u003e)\n# Becomes: (?:\u003c(?:((a+)+)b)\u003e)\n# re.findall runs this against \"\u003caaaaaaaaaaaaaaaaaaaaaaaa!\u003e\" \u2014 hangs.\n\nstart = time.time()\ntext.findall(r\"\u003c((a+)+)b\u003e\") # Never returns\n```\n\n### Impact\nApplications that expose `Text.findall()` to external input are vulnerable to a denial of service. An unauthenticated attacker can cause indefinite CPU saturation with one request, denying service to all other users of the Python process.\n\n### Remediation\nThis vulnerability was patched in commit `d8e4753`. Users should update to the patched version.\n\n### Credit\nTool: Kira by [Offgrid Security](https://www.offgridsec.com)",
"id": "GHSA-rrv8-h7p8-rx55",
"modified": "2026-09-08T20:28:13Z",
"published": "2026-09-08T20:28:13Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/security/advisories/GHSA-rrv8-h7p8-rx55"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-80205"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/pull/3674"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/commit/d8e47539317b571ab1422981f5b9653d5eae1249"
},
{
"type": "PACKAGE",
"url": "https://github.com/nltk/nltk"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/releases/tag/v3.10.0"
},
{
"type": "WEB",
"url": "https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3750.yaml"
},
{
"type": "WEB",
"url": "https://www.vulncheck.com/advisories/nltk-before-3.10.0-redos-via-text-findall-unvalidated-regex"
},
{
"type": "WEB",
"url": "http://www.openwall.com/lists/oss-security/2026/09/01/3"
}
],
"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",
"type": "CVSS_V4"
}
],
"summary": " NLTK: ReDoS in nltk.text.Text.findall() via unvalidated user-supplied regular expressions"
}
GHSA-RV73-9C8W-JP4C
Vulnerability from github – Published: 2024-10-26 21:30 – Updated: 2024-10-28 14:51Validate.js provides a declarative way of validating javascript objects. Versions 0.13.1 and prior contain one or more regular expressions that are vulnerable to Regular Expression Denial of Service (ReDoS). As of time of publication, no known patches are available.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "validate.js"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"last_affected": "0.13.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2020-26308"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2024-10-28T14:51:32Z",
"nvd_published_at": "2024-10-26T21:15:14Z",
"severity": "MODERATE"
},
"details": "Validate.js provides a declarative way of validating javascript objects. Versions 0.13.1 and prior contain one or more regular expressions that are vulnerable to Regular Expression Denial of Service (ReDoS). As of time of publication, no known patches are available.",
"id": "GHSA-rv73-9c8w-jp4c",
"modified": "2024-10-28T14:51:32Z",
"published": "2024-10-26T21:30:46Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2020-26308"
},
{
"type": "WEB",
"url": "https://github.com/ansman/validate.js/issues/342"
},
{
"type": "PACKAGE",
"url": "https://github.com/ansman/validate.js"
},
{
"type": "ADVISORY",
"url": "https://securitylab.github.com/advisories/GHSL-2020-302-redos-validate.js"
}
],
"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/E:U/U:Green",
"type": "CVSS_V4"
}
],
"summary": "validate.js Regular Expression Denial of Service vulnerability"
}
GHSA-RVGH-PR46-X7GG
Vulnerability from github – Published: 2025-03-20 12:32 – Updated: 2025-03-20 20:39A Regular Expression Denial of Service (ReDoS) vulnerability exists in the gradio-app/gradio repository, affecting the gr.Datetime component. The affected version is git commit 98cbcae. The vulnerability arises from the use of a regular expression ^(?:\s*now\s*(?:-\s*(\d+)\s*([dmhs]))?)?\s*$ to process user input. In Python's default regex engine, this regular expression can take polynomial time to match certain crafted inputs. An attacker can exploit this by sending a crafted HTTP request, causing the gradio process to consume 100% CPU and potentially leading to a Denial of Service (DoS) condition on the server.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "gradio"
},
"ranges": [
{
"events": [
{
"introduced": "4.38.0"
},
{
"last_affected": "5.0.0-beta.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2024-10624"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2025-03-20T20:39:00Z",
"nvd_published_at": "2025-03-20T10:15:17Z",
"severity": "HIGH"
},
"details": "A Regular Expression Denial of Service (ReDoS) vulnerability exists in the gradio-app/gradio repository, affecting the gr.Datetime component. The affected version is git commit 98cbcae. The vulnerability arises from the use of a regular expression `^(?:\\s*now\\s*(?:-\\s*(\\d+)\\s*([dmhs]))?)?\\s*$` to process user input. In Python\u0027s default regex engine, this regular expression can take polynomial time to match certain crafted inputs. An attacker can exploit this by sending a crafted HTTP request, causing the gradio process to consume 100% CPU and potentially leading to a Denial of Service (DoS) condition on the server.",
"id": "GHSA-rvgh-pr46-x7gg",
"modified": "2025-03-20T20:39:00Z",
"published": "2025-03-20T12:32:39Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-10624"
},
{
"type": "PACKAGE",
"url": "https://github.com/gradio-app/gradio"
},
{
"type": "WEB",
"url": "https://github.com/gradio-app/gradio/blob/98cbcaef827de7267462ccba180c7b2ffb1e825d/gradio/components/datetime.py#L133-L136"
},
{
"type": "WEB",
"url": "https://huntr.com/bounties/e8d0b248-8feb-4c23-9ef9-be4d1e868374"
}
],
"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": "Gradio Vulnerable to Denial of Service (DoS) via Crafted HTTP Request"
}
GHSA-RW72-V6C7-HF9R
Vulnerability from github – Published: 2024-09-02 18:31 – Updated: 2024-09-03 21:03A vulnerability was found in nescalante urlregex up to 0.5.0 and classified as problematic. This issue affects some unknown processing of the file index.js of the component Backtracking. The manipulation leads to inefficient regular expression complexity. The attack may be initiated remotely. The exploit has been disclosed to the public and may be used. Upgrading to version 0.5.1 is able to address this issue. The identifier of the patch is e5a085afe6abfaea1d1a78f54c45af9ef43ca1f9. It is recommended to upgrade the affected component.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "urlregex"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "0.5.1"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2020-36830"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2024-09-03T21:03:07Z",
"nvd_published_at": "2024-09-02T18:15:20Z",
"severity": "MODERATE"
},
"details": "A vulnerability was found in nescalante urlregex up to 0.5.0 and classified as problematic. This issue affects some unknown processing of the file index.js of the component Backtracking. The manipulation leads to inefficient regular expression complexity. The attack may be initiated remotely. The exploit has been disclosed to the public and may be used. Upgrading to version 0.5.1 is able to address this issue. The identifier of the patch is e5a085afe6abfaea1d1a78f54c45af9ef43ca1f9. It is recommended to upgrade the affected component.",
"id": "GHSA-rw72-v6c7-hf9r",
"modified": "2024-09-03T21:03:07Z",
"published": "2024-09-02T18:31:24Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2020-36830"
},
{
"type": "WEB",
"url": "https://github.com/nescalante/urlregex/pull/8"
},
{
"type": "WEB",
"url": "https://github.com/nescalante/urlregex/commit/e5a085afe6abfaea1d1a78f54c45af9ef43ca1f9"
},
{
"type": "PACKAGE",
"url": "https://github.com/nescalante/urlregex"
},
{
"type": "WEB",
"url": "https://github.com/nescalante/urlregex/releases/tag/v0.5.1"
},
{
"type": "WEB",
"url": "https://vuldb.com/?ctiid.276269"
},
{
"type": "WEB",
"url": "https://vuldb.com/?id.276269"
}
],
"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: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"
}
],
"summary": "ReDoS in urlregex"
}
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.