NLTK TweetTokenizer URL Pattern Backtracks Catastrophically on Naked-Domain-Like Input

{
  "id": "c4bde865d287a6b31a1a070c05e7c4bc1e14cd0f64bb52744d2dd97625240c92",
  "url": "https://osv.dev/vulnerability/CVE-2026-72818",
  "method": "structured",
  "payload": {
    "kind": "advisory",
    "title": "NLTK TweetTokenizer URL Pattern Backtracks Catastrophically on Naked-Domain-Like Input",
    "summary": "The URLS regular expression in nltk/tokenize/casual.py, compiled into TweetTokenizer.WORD_RE and applied by TweetTokenizer.tokenize, contains a naked-domain branch whose domain-label prefix [a-z0-9]+(?:[.\\-][a-z0-9]+)* is unbounded. Input consisting of many alternating label separators can be partitioned in exponentially many ways, and because the branch also requires a trailing top-level domain that such input never supplies, the engine explores those partitions before failing at each offset. A few kilobytes of input therefore consumes seconds to minutes of single-threaded CPU, and the HANG_RE substitution performed before matching does not collapse the pattern. TweetTokenizer is intended for tokenizing untrusted social-media text, so any service that applies it, or the module-level casual_tokenize, to submitted text can be stalled per request without authentication. Version 3.10.1 bounds the label repetition.",
    "evidence": "osv:CVE-2026-72818",
    "products": [],
    "severity": "high",
    "structured": {
      "id": "CVE-2026-72818",
      "aliases": [
        "CVE-2026-72818",
        "GHSA-qx2g-xrx7-vfh8",
        "PYSEC-2026-3870"
      ],
      "metrics": [
        {
          "type": "CVSS_V4",
          "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"
        }
      ],
      "affected": [
        {
          "ranges": [
            {
              "repo": "https://github.com/nltk/nltk",
              "type": "GIT",
              "events": [
                {
                  "introduced": "0"
                },
                {
                  "fixed": "35813c85af3f13d4f7196085854eafb3d0c5db02"
                }
              ],
              "database_specific": {
                "extracted_events": [
                  {
                    "range": [
                      {
                        "introduced": "0"
                      },
                      {
                        "fixed": "3.10.1"
                      }
                    ],
                    "source": "AFFECTED_FIELD",
                    "strategy": "StandardRange"
                  },
                  {
                    "range": [
                      {
                        "fixed": "35813c85af3f13d4f7196085854eafb3d0c5db02"
                      }
                    ],
                    "source": "REFERENCES_TAG",
                    "original_tag": "v3.10.1"
                  }
                ]
              }
            }
          ],
          "versions": [
            "v3.10.1-rc2",
            "v3.10.0-rc2",
            "v3.10.0",
            "v3.10.1-rc1",
            "v3.10.0-rc1",
            "3.9.4",
            "3.9.3",
            "v3.9.2",
            "3.9.2",
            "3.9.1",
            "3.9",
            "3.8.2",
            "3.8.1",
            "3.8",
            "3.7",
            "3.6.7",
            "3.6.6",
            "3.6.5",
            "3.6.2",
            "3.6.1",
            "3.6",
            "3.5",
            "3.5b1",
            "3.4.4",
            "3.4.3",
            "3.4.1",
            "3.4",
            "3.3",
            "3.2.5",
            "3.2.4",
            "3.2.3",
            "3.2.2",
            "3.2.1",
            "3.2",
            "3.1",
            "3.0.5",
            "3.0.4",
            "3.0.3",
            "3.0.2",
            "3.0.0b1",
            "3.0a4",
            "2.0.1rc4",
            "2.0.1rc3",
            "2.0.1rc2",
            "2.0.1rc1"
          ],
          "database_specific": {
            "source": "https://storage.googleapis.com/cve-osv-conversion/osv-output/CVE-2026-72818.json"
          }
        }
      ],
      "modified": "2026-10-28T02:30:52.414636100Z",
      "provider": "osv",
      "references": [
        "https://pypi.org",
        "https://github.com/CVEProject/cvelistV5/tree/main/cves/2026/72xxx/CVE-2026-72818.json",
        "https://github.com/nltk/nltk/releases/tag/v3.10.1",
        "https://nvd.nist.gov/vuln/detail/CVE-2026-72818",
        "https://www.vulncheck.com/advisories/nltk-tweettokenizer-url-pattern-backtracks-catastrophically-on-naked-domain-like-input",
        "https://github.com/nltk/nltk/issues/3704",
        "https://github.com/nltk/nltk",
        "https://github.com/nltk/nltk/blob/3.9.4/nltk/tokenize/casual.py"
      ],
      "provider_metadata": {
        "cwe_ids": [
          "CWE-1333"
        ],
        "cna_assigner": "VulnCheck",
        "osv_generated_from": "https://github.com/CVEProject/cvelistV5/tree/main/cves/2026/72xxx/CVE-2026-72818.json"
      }
    },
    "related_cves": [
      {
        "value": "CVE-2026-72818",
        "evidence": "/id"
      }
    ],
    "security_relevant": true,
    "severity_evidence": "/severity/0/score"
  },
  "source_id": "core-osv",
  "document_id": 521291,
  "published_at": "2026-08-20T21:57:34.23+00:00"
}