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.

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:32
VLAI
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.

Show details on source website

{
  "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:31
VLAI
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.

Show details on source website

{
  "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:02
VLAI
Summary
MathJax Regular expression Denial of Service (ReDoS)
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.

Show details on source website

{
  "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:07
VLAI
Summary
MooTools Regular Expression Denial of Service
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.

Show details on source website

{
  "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:29
VLAI
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.

Show details on source website

{
  "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:20
VLAI
Summary
Regular expression denial of service in eth-account
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

Show details on source website

{
  "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:00
VLAI
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.

Show details on source website

{
  "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:38
VLAI
Summary
Symfony vulnerable to denial of service via a malicious HTTP Host header
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.

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

Show details on source website

{
  "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:11
VLAI
Summary
mako is vulnerable to Regular Expression Denial of Service
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.

Show details on source website

{
  "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:27
VLAI
Summary
phi4mm: Quadratic Time Complexity in Input Token Processing​ leads to denial of service
Details

Summary

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)
Show details on source website

{
  "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
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.