CVE-2026-81722 in NLTK
Summary
by MITRE • 08/27/2026
nltk PorterStemmer in versions <= 3.10.2 (fixed in 3.10.3) contains an inefficient-algorithmic-complexity denial of service in PorterStemmer.stem(). The _is_consonant() helper walks backward over the entire run of trailing 'y' characters on every call, and _measure() invokes it for each stem position, causing O(n^2) behavior. A single ~20-50 KB untrusted token consisting of a long run of the letter 'y' followed by a matching suffix (e.g., 'ness') can pin a CPU core for seconds to minutes, causing availability impact.
If you want to get best quality of vulnerability data, you may have to visit VulDB.
Analysis
by VulDB Data Team • 08/27/2026
The Natural Language Toolkit version 3.10.2 and earlier contains a significant algorithmic complexity vulnerability within its PorterStemmer implementation that leads to denial of service conditions. This flaw is specifically located in the internal helper functions _is_consonant() and _measure(), which are critical components for determining word stems during text processing operations. The core issue arises from how these functions handle trailing characters, particularly the letter 'y'. When the stemmer processes a token containing a long sequence of consecutive 'y' characters followed by a standard suffix such as ness, the algorithm exhibits quadratic time complexity relative to the input length rather than linear or logarithmic growth expected in efficient text processing algorithms.
The technical mechanism behind this vulnerability involves the _is_consonant() function walking backward over every single trailing character in the run of 'y's on each invocation. Because the _measure() function calls _is_consonant() for each position within the stem, the total number of operations scales with the square of the input length. This results in an O(n^2) computational complexity profile where n represents the length of the trailing character sequence. For typical English text this is rarely problematic as words do not contain long runs of identical characters. However, when processing untrusted or synthetic inputs designed to exploit this behavior, such as a token consisting of thousands of 'y' characters followed by ness, the computational load becomes excessive.
The operational impact of this vulnerability is severe availability degradation for systems relying on NLTK for natural language processing tasks. A single maliciously crafted input string approximately twenty to fifty kilobytes in size can consume one CPU core entirely for several seconds up to minutes depending on system specifications and concurrent workload levels. In production environments where high-throughput text analysis is performed, such as log parsing, social media monitoring, or search engine indexing pipelines, this behavior can lead to thread starvation, increased latency across the entire application stack, and potential service outages if multiple requests trigger this condition simultaneously. The vulnerability effectively allows an attacker with access to input vectors processed by NLTK to perform a resource exhaustion attack without requiring authentication in many deployment scenarios.
This issue is classified under CWE-400 which covers Uncontrolled Resource Consumption due to algorithmic complexity flaws that allow attackers to force excessive use of system resources like CPU time or memory. From an offensive security perspective, this vulnerability aligns with ATT&CK technique T1496 which involves resource exhaustion attacks aimed at disrupting service availability by overwhelming computational capacity. The specific pattern of exploiting string processing inefficiencies is a known category of application layer denial of service that targets parsers and text manipulation libraries commonly used in web applications and data pipelines.
Mitigation strategies primarily involve upgrading the NLTK library to version 3.10.3 or later where this algorithmic flaw has been resolved through optimization of the consonant checking logic. For environments unable to immediately upgrade, input validation should be implemented at the application boundary before passing tokens to the stemmer. This includes enforcing maximum length limits on individual words or token segments and rejecting inputs that contain excessive runs of identical characters which are statistically improbable in natural language text but common in crafted attack payloads. Additionally implementing timeout mechanisms for long-running string processing operations can provide a secondary layer of defense against resource exhaustion attempts while ensuring system stability remains intact during peak load conditions.