Inefficient Algorithmic Complexity in Natural Language Toolkit - #VU159481
Published: November 5, 2026
Vulnerability details
The vulnerability allows an unauthenticated remote attacker to cause sustained single-threaded CPU exhaustion and denial of service in applications that normalize attacker-controlled parse trees using the Natural Language Toolkit (NLTK). A single wide, flat tree can block the processing thread for tens of seconds, with processing cost growing quadratically with the number of children. No user interaction is required, and confidentiality and integrity are not affected.
The vulnerability exists due to repeated front removal from a Python list in the default right-factor branch of nltk.tree.transforms.chomsky_normal_form in nltk/tree/transforms.py. The loop executes curNode[0:] = [nodeCopy.pop(0), newNode], shifting all remaining list elements on each removal. For a node with N children, N-2 such removals produce O(N^2) work. A remote attacker can submit a bracketed tree with an excessive number of children to an application that parses untrusted input with Tree.fromstring and normalizes it with Tree.chomsky_normal_form() using right factoring. Neither the parser nor the transform limits the child count.
Tree.chomsky_normal_form() delegates to the transform with factor="right" by default. The left-factor branch instead uses nodeCopy.pop(), which removes the last element in constant time and yields linear overall processing; the shared node-copying and bounded head-string operations do not explain the quadratic behavior. The regular-expression wall-clock timeout covers regex matching only, not this pure-Python list loop. The advisory reports that roughly 1.5 MB of treebank input can consume about 14 seconds on one CPU core.