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.
724 vulnerabilities reference this CWE, most recent first.
GHSA-V3J6-JV37-286J
Vulnerability from github – Published: 2024-05-14 15:32 – Updated: 2024-05-14 15:32An issue has been discovered in GitLab CE/EE affecting all versions before 16.9.7, all versions starting from 16.10 before 16.10.5, all versions starting from 16.11 before 16.11.2. It was possible for an attacker to cause a denial of service using maliciously crafted markdown content.
{
"affected": [],
"aliases": [
"CVE-2024-2651"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2024-05-14T15:20:14Z",
"severity": "MODERATE"
},
"details": "An issue has been discovered in GitLab CE/EE affecting all versions before 16.9.7, all versions starting from 16.10 before 16.10.5, all versions starting from 16.11 before 16.11.2. It was possible for an attacker to cause a denial of service using maliciously crafted markdown content.",
"id": "GHSA-v3j6-jv37-286j",
"modified": "2024-05-14T15:32:54Z",
"published": "2024-05-14T15:32:54Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2024-2651"
},
{
"type": "WEB",
"url": "https://hackerone.com/reports/2408619"
},
{
"type": "WEB",
"url": "https://gitlab.com/gitlab-org/gitlab/-/issues/450830"
}
],
"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-V3QF-493X-25P9
Vulnerability from github – Published: 2025-11-13 18:31 – Updated: 2025-11-13 18:31Inefficient regular expression complexity in certain Zoom Workplace Clients before version 6.5.10 may allow an unauthenticated user to conduct an escalation of privilege via network access.
{
"affected": [],
"aliases": [
"CVE-2025-62484"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2025-11-13T16:15:53Z",
"severity": "HIGH"
},
"details": "Inefficient regular expression complexity in certain Zoom Workplace Clients before version 6.5.10 may allow an unauthenticated user to conduct an escalation of privilege via network access.",
"id": "GHSA-v3qf-493x-25p9",
"modified": "2025-11-13T18:31:04Z",
"published": "2025-11-13T18:31:04Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-62484"
},
{
"type": "WEB",
"url": "https://www.zoom.com/en/trust/security-bulletin/zsb-25048"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:R/S:U/C:H/I:H/A:N",
"type": "CVSS_V3"
}
]
}
GHSA-V638-Q856-GRG8
Vulnerability from github – Published: 2023-08-29 21:30 – Updated: 2024-01-31 00:02Mathjax up to v2.7.9 was discovered to contain two Regular expression Denial of Service (ReDoS) vulnerabilities in MathJax.js via the components pattern and markdownPattern. NOTE: the vendor disputes this because the regular expressions are not applied to user input; thus, there is no risk.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "mathjax"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"last_affected": "2.7.9"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2023-39663"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2024-01-31T00:02:46Z",
"nvd_published_at": "2023-08-29T20:15:09Z",
"severity": "HIGH"
},
"details": "Mathjax up to v2.7.9 was discovered to contain two Regular expression Denial of Service (ReDoS) vulnerabilities in MathJax.js via the components pattern and markdownPattern. NOTE: the vendor disputes this because the regular expressions are not applied to user input; thus, there is no risk.\n\n",
"id": "GHSA-v638-q856-grg8",
"modified": "2024-01-31T00:02:46Z",
"published": "2023-08-29T21:30:21Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2023-39663"
},
{
"type": "WEB",
"url": "https://github.com/mathjax/MathJax/issues/3074"
}
],
"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": "MathJax Regular expression Denial of Service (ReDoS)"
}
GHSA-V63Q-HGQC-QVPG
Vulnerability from github – Published: 2023-01-03 18:30 – Updated: 2024-04-02 14:07MooTools is a collection of JavaScript utilities for JavaScript developers. All known versions include a CSS selector parser that is vulnerable to Regular Expression Denial of Service (ReDoS). An attack requires that an attacker can inject a string into a CSS selector at runtime, which is quite common with e.g. jQuery CSS selectors. No patches are available for this issue.
{
"affected": [
{
"package": {
"ecosystem": "npm",
"name": "mootools"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"last_affected": "1.5.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2021-32821"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": true,
"github_reviewed_at": "2024-04-02T14:06:51Z",
"nvd_published_at": "2023-01-03T17:15:00Z",
"severity": "HIGH"
},
"details": "MooTools is a collection of JavaScript utilities for JavaScript developers. All known versions include a CSS selector parser that is vulnerable to Regular Expression Denial of Service (ReDoS). An attack requires that an attacker can inject a string into a CSS selector at runtime, which is quite common with e.g. jQuery CSS selectors. No patches are available for this issue.",
"id": "GHSA-v63q-hgqc-qvpg",
"modified": "2024-04-02T14:07:06Z",
"published": "2023-01-03T18:30:25Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2021-32821"
},
{
"type": "PACKAGE",
"url": "https://github.com/vsviridov/mootools-node"
},
{
"type": "ADVISORY",
"url": "https://securitylab.github.com/advisories/GHSL-2020-345-redos-mootools"
}
],
"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": "MooTools Regular Expression Denial of Service"
}
GHSA-V648-CF9R-9M29
Vulnerability from github – Published: 2023-08-02 00:30 – Updated: 2024-04-04 06:29An issue has been discovered in GitLab affecting all versions starting from 15.2 before 16.0.8, all versions starting from 16.1 before 16.1.3, all versions starting from 16.2 before 16.2.2. A Regular Expression Denial of Service was possible by using crafted payloads to search Harbor Registry.
{
"affected": [],
"aliases": [
"CVE-2023-0632"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-400"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2023-08-02T00:15:16Z",
"severity": "HIGH"
},
"details": "An issue has been discovered in GitLab affecting all versions starting from 15.2 before 16.0.8, all versions starting from 16.1 before 16.1.3, all versions starting from 16.2 before 16.2.2. A Regular Expression Denial of Service was possible by using crafted payloads to search Harbor Registry.",
"id": "GHSA-v648-cf9r-9m29",
"modified": "2024-04-04T06:29:11Z",
"published": "2023-08-02T00:30:40Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2023-0632"
},
{
"type": "WEB",
"url": "https://hackerone.com/reports/1852677"
},
{
"type": "WEB",
"url": "https://gitlab.com/gitlab-org/gitlab/-/issues/390148"
}
],
"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-V65G-F3CJ-FJP4
Vulnerability from github – Published: 2022-08-23 00:00 – Updated: 2022-08-30 20:20An exponential ReDoS (Regular Expression Denial of Service) can be triggered in the eth-account PyPI package, when an attacker is able to supply arbitrary input to the encode_structured_data method
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "eth-account"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "0.5.9"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2022-1930"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-697"
],
"github_reviewed": true,
"github_reviewed_at": "2022-08-30T20:20:59Z",
"nvd_published_at": "2022-08-22T19:15:00Z",
"severity": "MODERATE"
},
"details": "An exponential ReDoS (Regular Expression Denial of Service) can be triggered in the eth-account PyPI package, when an attacker is able to supply arbitrary input to the encode_structured_data method",
"id": "GHSA-v65g-f3cj-fjp4",
"modified": "2022-08-30T20:20:59Z",
"published": "2022-08-23T00:00:13Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2022-1930"
},
{
"type": "WEB",
"url": "https://github.com/ethereum/eth-account/commit/70f89be700df0d5f08ef696252c88741f8414060"
},
{
"type": "PACKAGE",
"url": "https://github.com/ethereum/eth-account"
},
{
"type": "WEB",
"url": "https://research.jfrog.com/vulnerabilities/eth-account-redos-xray-248681"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "Regular expression denial of service in eth-account"
}
GHSA-V6Q3-CJ4X-H42R
Vulnerability from github – Published: 2022-10-11 12:00 – Updated: 2022-10-12 19:00Dell Wyse ThinOS 2205 contains a Regular Expression Denial of Service Vulnerability in UI. An admin privilege attacker could potentially exploit this vulnerability, leading to denial-of-service.
{
"affected": [],
"aliases": [
"CVE-2022-34402"
],
"database_specific": {
"cwe_ids": [
"CWE-1333",
"CWE-697"
],
"github_reviewed": false,
"github_reviewed_at": null,
"nvd_published_at": "2022-10-10T21:15:00Z",
"severity": "MODERATE"
},
"details": "Dell Wyse ThinOS 2205 contains a Regular Expression Denial of Service Vulnerability in UI. An admin privilege attacker could potentially exploit this vulnerability, leading to denial-of-service.",
"id": "GHSA-v6q3-cj4x-h42r",
"modified": "2022-10-12T19:00:35Z",
"published": "2022-10-11T12:00:49Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2022-34402"
},
{
"type": "WEB",
"url": "https://www.dell.com/support/kbdoc/en-us/000203376/dsa-2022-247-dell-wyse-thinos-security-update-for-a-regular-expression-vulnerability"
}
],
"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-V77V-X634-9M56
Vulnerability from github – Published: 2024-05-30 00:38 – Updated: 2024-05-30 00:38All 2.0.X, 2.1.X, 2.2.X, 2.3.X, 2.4.X, and 2.5.X versions of the Symfony HttpFoundation component are affected by this security issue.
This issue has been fixed in Symfony 2.3.19, 2.4.9, and 2.5.4. Note that no fixes are provided for Symfony 2.0, 2.1, and 2.2 as they are not maintained anymore.
Description
When an arbitrarily long hostname is sent by a client, its parsing in Request::getHost() can lead to a DoS attack, due to the way we validate the hostname via a regular expression.
Resolution The regular expression used to parse and validate the hostname from the HTTP request has been modified to avoid too much sensitivity to the submitted value length.
The patch for this issue is available here: https://github.com/symfony/symfony/pull/11828
{
"affected": [
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/http-foundation"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0"
},
{
"fixed": "2.3.19"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/http-foundation"
},
"ranges": [
{
"events": [
{
"introduced": "2.4.0"
},
{
"fixed": "2.4.9"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/http-foundation"
},
"ranges": [
{
"events": [
{
"introduced": "2.5.0"
},
{
"fixed": "2.5.4"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/symfony"
},
"ranges": [
{
"events": [
{
"introduced": "2.0.0"
},
{
"fixed": "2.3.19"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/symfony"
},
"ranges": [
{
"events": [
{
"introduced": "2.4.0"
},
{
"fixed": "2.4.9"
}
],
"type": "ECOSYSTEM"
}
]
},
{
"package": {
"ecosystem": "Packagist",
"name": "symfony/symfony"
},
"ranges": [
{
"events": [
{
"introduced": "2.5.0"
},
{
"fixed": "2.5.4"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2014-5244"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2024-05-30T00:38:38Z",
"nvd_published_at": null,
"severity": "HIGH"
},
"details": "All 2.0.X, 2.1.X, 2.2.X, 2.3.X, 2.4.X, and 2.5.X versions of the Symfony HttpFoundation component are affected by this security issue.\n\nThis issue has been fixed in Symfony 2.3.19, 2.4.9, and 2.5.4. Note that no fixes are provided for Symfony 2.0, 2.1, and 2.2 as they are not maintained anymore.\n\nDescription\nWhen an arbitrarily long hostname is sent by a client, its parsing in `Request::getHost()` can lead to a DoS attack, due to the way we validate the hostname via a regular expression.\n\nResolution\nThe regular expression used to parse and validate the hostname from the HTTP request has been modified to avoid too much sensitivity to the submitted value length.\n\nThe patch for this issue is available here: https://github.com/symfony/symfony/pull/11828",
"id": "GHSA-v77v-x634-9m56",
"modified": "2024-05-30T00:38:38Z",
"published": "2024-05-30T00:38:38Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/symfony/symfony/pull/11828"
},
{
"type": "WEB",
"url": "https://github.com/symfony/symfony/commit/1ee96a8b1b0987ffe2a62dca7ad268bf9edfa9b8"
},
{
"type": "WEB",
"url": "https://github.com/FriendsOfPHP/security-advisories/blob/master/symfony/http-foundation/CVE-2014-5244.yaml"
},
{
"type": "WEB",
"url": "https://github.com/FriendsOfPHP/security-advisories/blob/master/symfony/symfony/CVE-2014-5244.yaml"
},
{
"type": "WEB",
"url": "https://symfony.com/blog/cve-2014-5244-denial-of-service-with-a-malicious-http-host-header"
},
{
"type": "WEB",
"url": "https://symfony.com/cve-2014-5244"
}
],
"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": "Symfony vulnerable to denial of service via a malicious HTTP Host header"
}
GHSA-V973-FXGF-6XHP
Vulnerability from github – Published: 2022-09-16 17:20 – Updated: 2025-12-03 15:11Sqlalchemy mako before 1.2.2 is vulnerable to Regular expression Denial of Service when using the Lexer class to parse. This also affects babelplugin and linguaplugin.
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "mako"
},
"ranges": [
{
"events": [
{
"introduced": "0"
},
{
"fixed": "1.2.2"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2022-40023"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2022-09-16T17:20:25Z",
"nvd_published_at": "2022-09-07T13:15:00Z",
"severity": "HIGH"
},
"details": "Sqlalchemy mako before 1.2.2 is vulnerable to Regular expression Denial of Service when using the Lexer class to parse. This also affects babelplugin and linguaplugin.",
"id": "GHSA-v973-fxgf-6xhp",
"modified": "2025-12-03T15:11:43Z",
"published": "2022-09-16T17:20:25Z",
"references": [
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2022-40023"
},
{
"type": "WEB",
"url": "https://github.com/sqlalchemy/mako/issues/366"
},
{
"type": "WEB",
"url": "https://github.com/sqlalchemy/mako/commit/925760291d6efec64fda6e9dd1fd9cfbd5be068c"
},
{
"type": "ADVISORY",
"url": "https://github.com/advisories/GHSA-v973-fxgf-6xhp"
},
{
"type": "WEB",
"url": "https://github.com/pypa/advisory-database/tree/main/vulns/mako/PYSEC-2022-260.yaml"
},
{
"type": "WEB",
"url": "https://github.com/sqlalchemy/mako"
},
{
"type": "WEB",
"url": "https://github.com/sqlalchemy/mako/blob/c2f392e0be52dc67d1b9770ab8cce6a9c736d547/mako/ext/extract.py#L21"
},
{
"type": "WEB",
"url": "https://lists.debian.org/debian-lts-announce/2022/09/msg00026.html"
},
{
"type": "WEB",
"url": "https://lists.debian.org/debian-lts-announce/2025/12/msg00004.html"
},
{
"type": "WEB",
"url": "https://pyup.io/posts/pyup-discovers-redos-vulnerabilities-in-top-python-packages"
},
{
"type": "WEB",
"url": "https://pyup.io/vulnerabilities/CVE-2022-40023/50870"
}
],
"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": "mako is vulnerable to Regular Expression Denial of Service"
}
GHSA-VC6M-HM49-G9QG
Vulnerability from github – Published: 2025-04-29 16:43 – Updated: 2025-04-30 17:27Summary
A critical performance vulnerability has been identified in the input preprocessing logic of the multimodal tokenizer. The code dynamically replaces placeholder tokens (e.g., <|audio_|>, <|image_|>) with repeated tokens based on precomputed lengths. Due to inefficient list concatenation operations, the algorithm exhibits quadratic time complexity (O(n²)), allowing malicious actors to trigger resource exhaustion via specially crafted inputs.
Details
Affected Component: input_processor_for_phi4mm function. https://github.com/vllm-project/vllm/blob/8cac35ba435906fb7eb07e44fe1a8c26e8744f4e/vllm/model_executor/models/phi4mm.py#L1182-L1197
The code modifies the input_ids list in-place using input_ids = input_ids[:i] + tokens + input_ids[i+1:]. Each concatenation operation copies the entire list, leading to O(n) operations per replacement. For k placeholders expanding to m tokens, total time becomes O(kmn), approximating O(n²) in worst-case scenarios.
PoC
Test data demonstrates exponential time growth:
test_cases = [100, 200, 400, 800, 1600, 3200, 6400]
run_times = [0.002, 0.007, 0.028, 0.136, 0.616, 2.707, 11.854] # seconds
Doubling input size increases runtime by ~4x (consistent with O(n²)).
Impact
Denial-of-Service (DoS): An attacker could submit inputs with many placeholders (e.g., 10,000 <|audio_1|> tokens), causing CPU/memory exhaustion. Example: 10,000 placeholders → ~100 million operations.
Remediation Recommendations
Precompute all placeholder positions and expansion lengths upfront. Replace dynamic list concatenation with a single preallocated array.
# Pseudocode for O(n) solution
new_input_ids = []
for token in input_ids:
if token is placeholder:
new_input_ids.extend([token] * precomputed_length)
else:
new_input_ids.append(token)
{
"affected": [
{
"package": {
"ecosystem": "PyPI",
"name": "vllm"
},
"ranges": [
{
"events": [
{
"introduced": "0.8.0"
},
{
"fixed": "0.8.5"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2025-46560"
],
"database_specific": {
"cwe_ids": [
"CWE-1333"
],
"github_reviewed": true,
"github_reviewed_at": "2025-04-29T16:43:10Z",
"nvd_published_at": "2025-04-30T01:15:52Z",
"severity": "MODERATE"
},
"details": "### Summary\nA critical performance vulnerability has been identified in the input preprocessing logic of the multimodal tokenizer. The code dynamically replaces placeholder tokens (e.g., \u003c|audio_*|\u003e, \u003c|image_*|\u003e) with repeated tokens based on precomputed lengths. Due to \u200b\u200binefficient list concatenation operations\u200b\u200b, the algorithm exhibits \u200b\u200bquadratic time complexity (O(n\u00b2))\u200b\u200b, allowing malicious actors to trigger resource exhaustion via specially crafted inputs.\n\n### Details\n\u200b\u200bAffected Component\u200b\u200b: input_processor_for_phi4mm function.\nhttps://github.com/vllm-project/vllm/blob/8cac35ba435906fb7eb07e44fe1a8c26e8744f4e/vllm/model_executor/models/phi4mm.py#L1182-L1197\n\nThe code modifies the input_ids list in-place using input_ids = input_ids[:i] + tokens + input_ids[i+1:]. Each concatenation operation copies the entire list, leading to O(n) operations per replacement. For k placeholders expanding to m tokens, total time becomes O(kmn), approximating O(n\u00b2) in worst-case scenarios.\n\n### PoC\nTest data demonstrates exponential time growth:\n```python\ntest_cases = [100, 200, 400, 800, 1600, 3200, 6400]\nrun_times = [0.002, 0.007, 0.028, 0.136, 0.616, 2.707, 11.854] # seconds\n```\nDoubling input size increases runtime by ~4x (consistent with O(n\u00b2)).\n\n### Impact\n\u200b\u200bDenial-of-Service (DoS):\u200b\u200b An attacker could submit inputs with many placeholders (e.g., 10,000 \u003c|audio_1|\u003e tokens), causing CPU/memory exhaustion.\nExample: 10,000 placeholders \u2192 ~100 million operations.\n\n\n### Remediation Recommendations\u200b\nPrecompute all placeholder positions and expansion lengths upfront.\nReplace dynamic list concatenation with a single preallocated array.\n```python\n# Pseudocode for O(n) solution\nnew_input_ids = []\nfor token in input_ids:\n if token is placeholder:\n new_input_ids.extend([token] * precomputed_length)\n else:\n new_input_ids.append(token)\n```",
"id": "GHSA-vc6m-hm49-g9qg",
"modified": "2025-04-30T17:27:16Z",
"published": "2025-04-29T16:43:10Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/vllm-project/vllm/security/advisories/GHSA-vc6m-hm49-g9qg"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2025-46560"
},
{
"type": "PACKAGE",
"url": "https://github.com/vllm-project/vllm"
},
{
"type": "WEB",
"url": "https://github.com/vllm-project/vllm/blob/8cac35ba435906fb7eb07e44fe1a8c26e8744f4e/vllm/model_executor/models/phi4mm.py#L1182-L1197"
}
],
"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"
}
],
"summary": "phi4mm: Quadratic Time Complexity in Input Token Processing\u200b leads to denial of service"
}
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.