CVE-2021-43854: Inefficient Regular Expression Complexity in nltk

Background

The nltk package is a popular open-source library for natural language processing (NLP) in Python. It provides various functionalities for tokenizing, tagging, and parsing text. The vulnerable component in nltk is the PunktSentenceTokenizer class, along with the sent_tokenize and word_tokenize functions. These components are used for sentence and word tokenization, respectively. The vulnerability allows for a Regular Expression Denial of Service (ReDoS) attack, where a specially crafted long input can cause the functions to consume a significant amount of execution time. This vulnerability affects versions of nltk prior to 3.6.6.

Vulnerability Detail

The vulnerability arises from inefficient regular expressions used in the nltk package. When provided with a malicious input of significant length, the PunktSentenceTokenizer, sent_tokenize, and word_tokenize functions can experience exponential execution time, leading to a denial of service condition. Attackers can exploit this vulnerability by submitting long inputs to these functions, causing excessive resource consumption and potentially impacting the availability of the application. The impact of this vulnerability can be observed through a simple example that measures the execution time of word_tokenize with increasing input lengths. The vulnerability has been assigned a CVSS score of 7.5, indicating a high severity level.

pip install --upgrade "nltk==3.10.4"

pip install --upgrade "nltk==3.6.6"

Workaround

If upgrading to the patched version is not immediately feasible, a workaround can be implemented by limiting the maximum length of input to the vulnerable functions. By setting a reasonable upper limit, the execution time can be bounded and prevent excessive resource consumption. Here is an example of how to implement such a limit in Python:

from nltk.tokenize import word_tokenize

MAX_INPUT_LENGTH = 10000

def safe_word_tokenize(text):
    if len(text) > MAX_INPUT_LENGTH:
        raise ValueError('Input length exceeds maximum limit')
    return word_tokenize(text)

By using the safe_word_tokenize function instead of word_tokenize, inputs longer than the specified limit will raise an exception, preventing the vulnerability from being exploited.

Conclusion

The vulnerability in nltk's PunktSentenceTokenizer, sent_tokenize, and word_tokenize functions can be exploited through a Regular Expression Denial of Service (ReDoS) attack. Upgrading to nltk version 3.6.6 or later is recommended to fix the vulnerability. Alternatively, a workaround can be implemented by limiting the maximum length of input to the vulnerable functions. For further support on vulnerability remediation, please contact DevNack.com.

See every vulnerability recorded for nltk →

FAQ

from nltk.tokenize import word_tokenize
import time

n = 8
for length in [10**i for i in range(2, n)]:
    # Prepare a malicious input
    text = "a" * length
    start_t = time.time()
    # Call word_tokenize and measure execution time
    word_tokenize(text)
    print(f"A length of {length:<{n}} takes {time.time() - start_t:.4f}s")