Description

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.

Executive Summary

Technical Details

Mitigations

References

Additional Metadata

{
  "score": "7.5",
  "pubDate": "2026-08-27T17:21:02.800Z",
  "pubdate": "2026-08-27T17:21:02.800Z",
  "executiveSummary": "NLTK PorterStemmer versions 3.10.2 and earlier are susceptible to an Inefficient Algorithmic Complexity vulnerability, specifically categorized as a Denial of Service (DoS) condition.\nThe vulnerability arises from inefficient processing within the stem() method, where the _is_consonant() helper function exhibits O(n^2) time complexity when handling specific input patterns.\nAn unauthenticated attacker can exploit this by providing a specially crafted, relatively small input string—typically a 20-50 KB sequence of the character 'y'—which triggers excessive CPU consumption.\nSuccessful exploitation results in the pinning of a CPU core for extended durations, effectively causing an availability impact on the service hosting the affected NLTK implementation.\nThis vulnerability poses a significant risk to applications that process untrusted natural language input, as it allows for resource exhaustion without requiring high-privilege access or complex attack vectors.",
  "technicalDetails": "The vulnerability is rooted in the implementation of the _is_consonant() helper function within the PorterStemmer module. During the stemming process, the algorithm must frequently evaluate character properties to determine stem boundaries and rules application.\nThe _is_consonant() function, as implemented in versions <= 3.10.2, performs a backward traversal over the entire sequence of trailing 'y' characters every time it is invoked. Because _is_consonant() is called repeatedly by the _measure() function for each prospective stem position, the cumulative complexity degrades to O(n^2) relative to the length of the trailing 'y' sequence.\nExploitation is achieved by supplying an input payload consisting of a long string of 'y' characters (approximately 20-50 KB) terminated by a suffix recognized by the Porter stemmer, such as 'ness'. When PorterStemmer.stem() processes this payload, the _measure() function performs numerous iterations that force the redundant, backward-walking logic in _is_consonant() to execute thousands of times.\nThis behavior forces the CPU to perform extensive, unnecessary character comparisons for each iteration of the stemming logic. On a standard execution thread, this results in high CPU utilization that can persist for seconds or even minutes depending on the string length and host hardware.\nThe attack is remotely exploitable as it relies solely on the processing of untrusted input. No specific authentication, user interaction, or elevated privileges are required to induce the algorithmic DoS. Any network-exposed endpoint that parses user-provided text using NLTK PorterStemmer is vulnerable to this resource exhaustion technique.\nThe post-exploitation impact is limited to a Denial of Service, as the excessive CPU usage effectively stalls the application thread or worker process. This disrupts service availability for legitimate users. There is no evidence of arbitrary code execution or memory corruption, as the issue is strictly related to computational complexity and logical performance degradation."
}