Inefficient Algorithmic Complexity in Natural Language Toolkit - #VU159482
Published: November 5, 2026
Vulnerability details
The vulnerability allows an unauthenticated remote attacker to cause CPU exhaustion and denial of service in applications that parse attacker-influenced CCG lexicon text using the Natural Language Toolkit (NLTK). A few-megabyte input can occupy a single parsing thread for tens of seconds, and concurrent requests can exhaust request workers. No user interaction is required, and confidentiality and integrity are not affected.
The vulnerability exists due to two quadratic-time string-processing loops in nltk/ccg/lexicon.py. In matchBrackets, consuming a wide, flat bracket body repeatedly executes rest = rest[1:], copying the remaining string for each character. Separately, augParseCategory processes long operator chains by repeatedly copying the regular-expression match tail through rest = app[3]. A remote attacker can submit lexicon text containing either a wide bracket body or a long operator chain to an application that exposes parsing of untrusted lexicons, causing sustained CPU consumption. Neither line length nor category width is bounded before these loops execute, and a downstream parse error does not prevent the preceding CPU expenditure.
The public entry point is nltk.ccg.lexicon.fromstring, also exported as nltk.ccg.chart.fromstring; it splits lexicon text into lines and routes categories through nextCategory to the affected processing loops. The recursion-depth guard, MAX_PARSE_DEPTH = 500, limits deeply nested categories but does not constrain these flat, width-based inputs. NLTK's regular-expression wall-clock timeout covers regex matching rather than the pure-Python slicing loops, and its regex source-length limit constrains patterns rather than lexicon text, so neither prevents this resource exhaustion.