CVE-2021-3828: Incorrect Comparison (CWE-697)
value: nltk is vulnerable to Inefficient Regular Expression Complexity
CWE description: The product compares two entities in a security-relevant context, but the comparison is incorrect, which may lead to resultant weaknesses.
CVSS v3 base score: 7.5
Published: 2021-09-27T13:15Z
Repository: https://github.com/nltk/nltk
Language: Python
Files changed: nltk/corpus/reader/comparative_sents.py, nltk/test/corpus.doctest
Commit date: 2021-09-25 08:44:32 +0930
Commit message: Resolved ReDoS vulnerability in Corpus Reader (#2816)

* Resolved ReDoS vulnerability in the Corpus Reader for the Comparative Sentence Dataset

* Solidified performance tests
Diff: diff --git a/nltk/corpus/reader/comparative_sents.py b/nltk/corpus/reader/comparative_sents.py
index cbfac4c13..ed295e4e0 100644
--- a/nltk/corpus/reader/comparative_sents.py
+++ b/nltk/corpus/reader/comparative_sents.py
@@ -43,11 +43,11 @@ STARS = re.compile(r"^\*+$")
 COMPARISON = re.compile(r"<cs-[1234]>")
 CLOSE_COMPARISON = re.compile(r"</cs-[1234]>")
 GRAD_COMPARISON = re.compile(r"<cs-[123]>")
 NON_GRAD_COMPARISON = re.compile(r"<cs-4>")
 ENTITIES_FEATS = re.compile(r"(\d)_((?:[\.\w\s/-](?!\d_))+)")
-KEYWORD = re.compile(r"\((?!.*\()(.*)\)$")
+KEYWORD = re.compile(r"\(([^\(]*)\)$")
 
 
 class Comparison:
     """
     A Comparison represents a comparative sentence and its constituents.
diff --git a/nltk/test/corpus.doctest b/nltk/test/corpus.doctest
index 82b17f8a5..560e641a6 100644
--- a/nltk/test/corpus.doctest
+++ b/nltk/test/corpus.doctest
@@ -2160,5 +2160,37 @@ svn 7227 fixed a bug in the qc corpus reader, which prevented
 access to its tuples() method
 
     >>> from nltk.corpus import qc
     >>> qc.tuples('test.txt')
     [('NUM:dist', 'How far is it from Denver to Aspen ?'), ('LOC:city', 'What county is Modesto , California in ?'), ...]
+
+Ensure that KEYWORD from `comparative_sents.py` no longer contains a ReDoS vulnerability.
+
+    >>> import re
+    >>> import time
+    >>> from nltk.corpus.reader.comparative_sents import KEYWORD
+    >>> sizes = {
+    ...     "short": 4000,
+    ...     "long": 40000
+    ... }
+    >>> exec_times = {
+    ...     "short": [],
+    ...     "long": [],
+    ... }
+    >>> for size_name, size in sizes.items():
+    ...     for j in range(9):
+    ...         start_t = time.perf_counter()
+    ...         payload = "( " + "(" * size
+    ...         output = KEYWORD.findall(payload)
+    ...         exec_times[size_name].append(time.perf_counter() - start_t)
+    ...     exec_times[size_name] = sorted(exec_times[size_name])[4] # Get the mean
+
+Ideally, the execution time of such a regular expression is linear
+in the length of the input. As such, we would expect exec_times["long"]
+to be roughly 10 times as big as exec_times["short"].
+With the ReDoS in place, it took roughly 80 times as long.
+For now, we accept values below 30 (times as long), due to the potential
+for variance. This ensures that the ReDoS has certainly been reduced,
+if not removed.
+
+    >>> exec_times["long"] / exec_times["short"] < 30
+    True

Vulnerable code: KEYWORD = re.compile(r"\((?!.*\()(.*)\)$")
Fixed code: KEYWORD = re.compile(r"\(([^\(]*)\)$")

Ensure that KEYWORD from `comparative_sents.py` no longer contains a ReDoS vulnerability.

    >>> import re
    >>> import time
    >>> from nltk.corpus.reader.comparative_sents import KEYWORD
    >>> sizes = {
    ...     "short": 4000,
    ...     "long": 40000
    ... }
    >>> exec_times = {
    ...     "short": [],
    ...     "long": [],
    ... }
    >>> for size_name, size in sizes.items():
    ...     for j in range(9):
    ...         start_t = time.perf_counter()
    ...         payload = "( " + "(" * size
    ...         output = KEYWORD.findall(payload)
    ...         exec_times[size_name].append(time.perf_counter() - start_t)
    ...     exec_times[size_name] = sorted(exec_times[size_name])[4] # Get the mean

Ideally, the execution time of such a regular expression is linear
in the length of the input. As such, we would expect exec_times["long"]
to be roughly 10 times as big as exec_times["short"].
With the ReDoS in place, it took roughly 80 times as long.
For now, we accept values below 30 (times as long), due to the potential
for variance. This ensures that the ReDoS has certainly been reduced,
if not removed.

    >>> exec_times["long"] / exec_times["short"] < 30
    True