Inefficient Algorithmic Complexity in Natural Language Toolkit - #VU159480
Published: November 5, 2026
Vulnerability details
The vulnerability allows an unauthenticated remote attacker to cause denial of service through sustained single-threaded CPU exhaustion in Natural Language Toolkit (NLTK) applications that load attacker-supplied CoNLL semantic-role-labeling corpora and iterate them with ConllCorpusReader.srl_instances(). A crafted corpus of roughly one megabyte can block the processing thread for tens of seconds, with larger inputs extending processing to minutes. No user interaction is required, and confidentiality and integrity are not affected.
The vulnerability exists due to repeated nested scanning in ConllCorpusReader._get_srl_instances: for each of P predicates, the builder searches up to P span columns containing R spans each, resulting in O(P^2 * R) work. A remote attacker can submit a well-formed CoNLL block through an application's corpus-ingestion surface, control its predicate and span-column counts, and place the sole head span in the last span column to force full scans of earlier columns for every predicate. The search stops only upon finding a V or C-V span containing the predicate word; the inner break and loop continuation therefore do not prevent repeated traversal under this arrangement. Blocks are read whole without a size cap, and grid validation checks only uniform column counts rather than bounding predicates, spans, or total work.
The affected implementation is in nltk/corpus/reader/conll.py and is reached through the SRL-specific API when processing untrusted data with words, pos, tree, and srl columns. Applications that never call srl_instances() are not exposed to this failure case. The path-containment sandbox restricts file locations but not processing cost, while the regular-expression wall-clock timeout covers regex matching rather than this pure-Python loop. Constant-time range-membership checks do not eliminate the excessive work because they are repeated for every traversed span.