CVE-2021-43854 (Python, published 2021-12-23T18:15Z)
Description: value: NLTK (Natural Language Toolkit) is a suite of open source Python modules, data sets, and tutorials supporting research and development in Natural Language Processing. Versions prior to 3.6.5 are vulnerable to regular expression denial of service (ReDoS) attacks. The vulnerability is present in PunktSentenceTokenizer, sent_tokenize and word_tokenize. Any users of this class, or these two functions, are vulnerable to the ReDoS attack. In short, a specifically crafted long input to any of these vulnerable functions will cause them to take a significant amount of execution time. If your program relies on any of the vulnerable functions for tokenizing unpredictable user input, then we would strongly recommend upgrading to a version of NLTK without the vulnerability. For users unable to upgrade the execution time can be bounded by limiting the maximum length of an input to any of the vulnerable functions. Our recommendation is to implement such a limit.
Severity: MEDIUM (CVSS v3 base score: 7.5)
Weakness: CWE-400 \u2014 Uncontrolled Resource Consumption
The product does not properly control the allocation and maintenance of a limited resource, thereby enabling an actor to influence the amount of resources consumed, eventually leading to the exhaustion of available resources.
Repository: https://github.com/nltk/nltk
Files changed:
nltk/tokenize/punkt.py
Commit message: Resolved serious ReDoS in PunktSentenceTokenizer (#2869)

* Resolved serious ReDOS in PunktSentenceTokenizer

* Improve performance by relying on string split instead of re.search

* Solved issue if sentence contains just one token

Vulnerable code:
        \S*                          # some word material
        for match in self._lang_vars.period_context_re().finditer(text):
            decision_text = match.group() + match.group("after_tok")
        for match in self._lang_vars.period_context_re().finditer(text):
            context = match.group() + match.group("after_tok")

Fixed code:
        for match, decision_text in self._match_potential_end_contexts(text):
    def _match_potential_end_contexts(self, text):
        """
        Given a text, find the matches of potential sentence breaks,
        alongside the contexts surrounding these sentence breaks.

        Since the fix for the ReDOS discovered in issue #2866, we no longer match
        the word before a potential end of sentence token. Instead, we use a separate
        regex for this. As a consequence, `finditer`'s desire to find non-overlapping
        matches no longer aids us in finding the single longest match.
        Where previously, we could use::

            >>> pst = PunktSentenceTokenizer()
            >>> text = "Very bad acting!!! I promise."
            >>> list(pst._lang_vars.period_context_re().finditer(text)) # doctest: +SKIP
            [<re.Match object; span=(9, 18), match='acting!!!'>]

        Now we have to find the word before (i.e. 'acting') separately, and `finditer`
        returns::

            >>> pst = PunktSentenceTokenizer()
            >>> text = "Very bad acting!!! I promise."
            >>> list(pst._lang_vars.period_context_re().finditer(text)) # doctest: +NORMALIZE_WHITESPACE
            [<re.Match object; span=(15, 16), match='!'>,
            <re.Match object; span=(16, 17), match='!'>,
            <re.Match object; span=(17, 18), match='!'>]

        So, we need to find the word before the match from right to left, and then manually remove
        the overlaps. That is what this method does::

            >>> pst = PunktSentenceTokenizer()
            >>> text = "Very bad acting!!! I promise."
            >>> pst._match_potential_end_contexts(text)
            [(<re.Match object; span=(17, 18), match='!'>, 'acting!!! I')]

        :param text: String of one or more sentences
        :type text: str
        :return: List of match-context tuples.
        :rtype: List[Tuple[re.Match, str]]
        """
        before_words = {}
        matches = []
        for match in reversed(list(self._lang_vars.period_context_re().finditer(text))):
            # Ignore matches that have already been captured by matches to the right of this match
            if matches and match.end() > before_start:
                continue
            # Find the word before the current match
            split = text[: match.start()].rsplit(maxsplit=1)
            before_start = len(split[0]) if len(split) == 2 else 0
            before_words[match] = split[-1]
            matches.append(match)

        return [
            (
                match,
                before_words[match] + match.group() + match.group("after_tok"),
            )
            for match in matches[::-1]
        ]

        for match, context in self._match_potential_end_contexts(text):