CVE-2021-3842: Inefficient Regular Expression Complexity (CWE-1333)
value: nltk is vulnerable to Inefficient Regular Expression Complexity
CWE description: The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
CVSS v3 base score: 7.5
Published: 2022-01-04T15:15Z
Repository: https://github.com/nltk/nltk
Language: Python
Files changed: nltk/parse/malt.py, nltk/sem/glue.py, nltk/tag/brill.py, nltk/tag/brill_trainer.py, nltk/tag/sequential.py, nltk/tbl/demo.py
Commit date: 2021-12-08 15:19:56 +0100
Commit message: Resolve ReDoS opportunity by fixing incorrectly specified regex (#2906)


Diff: diff --git a/nltk/parse/malt.py b/nltk/parse/malt.py
index 768f4846b..9393f113f 100644
--- a/nltk/parse/malt.py
+++ b/nltk/parse/malt.py
@@ -30,11 +30,11 @@ def malt_regex_tagger():
             (r"\?$", "?"),  # fullstop, comma, Qmark
             (r"\($", "("),
             (r"\)$", ")"),  # round brackets
             (r"\[$", "["),
             (r"\]$", "]"),  # square brackets
-            (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
+            (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers
             (r"(The|the|A|a|An|an)$", "DT"),  # articles
             (r"(He|he|She|she|It|it|I|me|Me|You|you)$", "PRP"),  # pronouns
             (r"(His|his|Her|her|Its|its)$", "PRP$"),  # possessive
             (r"(my|Your|your|Yours|yours)$", "PRP$"),  # possessive
             (r"(on|On|in|In|at|At|since|Since)$", "IN"),  # time prepopsitions
diff --git a/nltk/sem/glue.py b/nltk/sem/glue.py
index 5b3c94557..a627aaa3f 100644
--- a/nltk/sem/glue.py
+++ b/nltk/sem/glue.py
@@ -701,11 +701,11 @@ class Glue:
     def get_pos_tagger(self):
         from nltk.corpus import brown
 
         regexp_tagger = RegexpTagger(
             [
-                (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
+                (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers
                 (r"(The|the|A|a|An|an)$", "AT"),  # articles
                 (r".*able$", "JJ"),  # adjectives
                 (r".*ness$", "NN"),  # nouns formed from adjectives
                 (r".*ly$", "RB"),  # adverbs
                 (r".*s$", "NNS"),  # plural nouns
diff --git a/nltk/tag/brill.py b/nltk/tag/brill.py
index b0b7607ea..05a8dd5f4 100644
--- a/nltk/tag/brill.py
+++ b/nltk/tag/brill.py
@@ -327,11 +327,11 @@ class BrillTagger(TaggerI):
                     len(template_counts), len(tids)
                 )
             )
             print(
                 "TRAIN ({tokencount:7d} tokens) initial {initialerrors:5d} {initialacc:.4f} "
-                "final: {finalerrors:5d} {finalacc:.4f} ".format(**train_stats)
+                "final: {finalerrors:5d} {finalacc:.4f}".format(**train_stats)
             )
             head = "#ID | Score (train) |  #Rules     | Template"
             print(head, "\n", "-" * len(head), sep="")
             train_tplscores = sorted(
                 weighted_traincounts.items(), key=det_tplsort, reverse=True
diff --git a/nltk/tag/brill_trainer.py b/nltk/tag/brill_trainer.py
index 3e18a22b1..0f1c5bea8 100644
--- a/nltk/tag/brill_trainer.py
+++ b/nltk/tag/brill_trainer.py
@@ -89,11 +89,11 @@ class BrillTaggerTrainer:
            need to check to see if the rule messed anything up."""
 
     # Training
 
     def train(self, train_sents, max_rules=200, min_score=2, min_acc=None):
-        """
+        r"""
         Trains the Brill tagger on the corpus *train_sents*,
         producing at most *max_rules* transformations, each of which
         reduces the net number of errors in the corpus by at least
         *min_score*, and each of which has accuracy not lower than
         *min_acc*.
@@ -109,11 +109,11 @@ class BrillTaggerTrainer:
         >>> baseline_data = treebank.tagged_sents()[100:200]
         >>> gold_data = treebank.tagged_sents()[200:300]
         >>> testing_data = [untag(s) for s in gold_data]
 
         >>> backoff = RegexpTagger([
-        ... (r'^-?[0-9]+(.[0-9]+)?$', 'CD'),   # cardinal numbers
+        ... (r'^-?[0-9]+(\.[0-9]+)?$', 'CD'),  # cardinal numbers
         ... (r'(The|the|A|a|An|an)$', 'AT'),   # articles
         ... (r'.*able$', 'JJ'),                # adjectives
         ... (r'.*ness$', 'NN'),                # nouns formed from adjectives
         ... (r'.*ly$', 'RB'),                  # adverbs
         ... (r'.*s$', 'NNS'),                  # plural nouns
@@ -123,11 +123,11 @@ class BrillTaggerTrainer:
         ... ])
 
         >>> baseline = backoff #see NOTE1
 
         >>> baseline.evaluate(gold_data) #doctest: +ELLIPSIS
-        0.2450142...
+        0.2433862...
 
         >>> # Set up templates
         >>> Template._cleartemplates() #clear any templates created in earlier tests
         >>> templates = [Template(Pos([-1])), Template(Pos([-1]), Word([0]))]
 
@@ -135,11 +135,11 @@ class BrillTaggerTrainer:
         >>> tt = BrillTaggerTrainer(baseline, templates, trace=3)
 
         >>> tagger1 = tt.train(training_data, max_rules=10)
         TBL train (fast) (seqs: 100; tokens: 2417; tpls: 2; min score: 2; min acc: None)
         Finding initial useful rules...
-            Found 845 useful rules.
+            Found 847 useful rules.
         <BLANKLINE>
                    B      |
            S   F   r   O  |        Score = Fixed - Broken
            c   i   o   t  |  R     Fixed = num tags changed incorrect -> correct
            o   x   k   h  |  u     Broken = num tags changed correct -> incorrect
@@ -148,11 +148,11 @@ class BrillTaggerTrainer:
         ------------------+-------------------------------------------------------
          132 132   0   0  | AT->DT if Pos:NN@[-1]
           85  85   0   0  | NN->, if Pos:NN@[-1] & Word:,@[0]
           69  69   0   0  | NN->. if Pos:NN@[-1] & Word:.@[0]
           51  51   0   0  | NN->IN if Pos:NN@[-1] & Word:of@[0]
-          47  63  16 161  | NN->IN if Pos:NNS@[-1]
+          47  63  16 162  | NN->IN if Pos:NNS@[-1]
           33  33   0   0  | NN->TO if Pos:NN@[-1] & Word:to@[0]
           26  26   0   0  | IN->. if Pos:NNS@[-1] & Word:.@[0]
           24  24   0   0  | IN->, if Pos:NNS@[-1] & Word:,@[0]
           22  27   5  24  | NN->-NONE- if Pos:VBD@[-1]
           17  17   0   0  | NN->CC if Pos:NN@[-1] & Word:and@[0]
@@ -160,40 +160,40 @@ class BrillTaggerTrainer:
         >>> tagger1.rules()[1:3]
         (Rule('001', 'NN', ',', [(Pos([-1]),'NN'), (Word([0]),',')]), Rule('001', 'NN', '.', [(Pos([-1]),'NN'), (Word([0]),'.')]))
 
         >>> train_stats = tagger1.train_stats()
         >>> [train_stats[stat] for stat in ['initialerrors', 'finalerrors', 'rulescores']]
-        [1775, 1269, [132, 85, 69, 51, 47, 33, 26, 24, 22, 17]]
+        [1776, 1270, [132, 85, 69, 51, 47, 33, 26, 24, 22, 17]]
 
         >>> tagger1.print_template_statistics(printunused=False)
         TEMPLATE STATISTICS (TRAIN)  2 templates, 10 rules)
-        TRAIN (   2417 tokens) initial  1775 0.2656 final:  1269 0.4750
+        TRAIN (   2417 tokens) initial  1776 0.2652 final:  1270 0.4746
         #ID | Score (train) |  #Rules     | Template
         --------------------------------------------
         001 |   305   0.603 |   7   0.700 | Template(Pos([-1]),Word([0]))
         000 |   201   0.397 |   3   0.300 | Template(Pos([-1]))
         <BLANKLINE>
         <BLANKLINE>
 
         >>> tagger1.evaluate(gold_data) # doctest: +ELLIPSIS
-        0.43996...
+        0.43833...
 
         >>> tagged, test_stats = tagger1.batch_tag_incremental(testing_data, gold_data)
 
         >>> tagged[33][12:] == [('foreign', 'IN'), ('debt', 'NN'), ('of', 'IN'), ('$', 'NN'), ('64', 'CD'),
         ... ('billion', 'NN'), ('*U*', 'NN'), ('--', 'NN'), ('the', 'DT'), ('third-highest', 'NN'), ('in', 'NN'),
         ... ('the', 'DT'), ('developing', 'VBG'), ('world', 'NN'), ('.', '.')]
         True
 
         >>> [test_stats[stat] for stat in ['initialerrors', 'finalerrors', 'rulescores']]
-        [1855, 1376, [100, 85, 67, 58, 27, 36, 27, 16, 31, 32]]
+        [1859, 1380, [100, 85, 67, 58, 27, 36, 27, 16, 31, 32]]
 
         >>> # A high-accuracy tagger
         >>> tagger2 = tt.train(training_data, max_rules=10, min_acc=0.99)
         TBL train (fast) (seqs: 100; tokens: 2417; tpls: 2; min score: 2; min acc: 0.99)
         Finding initial useful rules...
-            Found 845 useful rules.
+            Found 847 useful rules.
         <BLANKLINE>
                    B      |
            S   F   r   O  |        Score = Fixed - Broken
            c   i   o   t  |  R     Fixed = num tags changed incorrect -> correct
            o   x   k   h  |  u     Broken = num tags changed correct -> incorrect
@@ -210,11 +210,11 @@ class BrillTaggerTrainer:
           19  19   0   6  | NN->VB if Pos:TO@[-1]
           18  18   0   0  | CD->-NONE- if Pos:NN@[-1] & Word:0@[0]
           18  18   0   0  | NN->CC if Pos:NN@[-1] & Word:and@[0]
 
         >>> tagger2.evaluate(gold_data)  # doctest: +ELLIPSIS
-        0.44159544...
+        0.43996743...
         >>> tagger2.rules()[2:4]
         (Rule('001', 'NN', '.', [(Pos([-1]),'NN'), (Word([0]),'.')]), Rule('001', 'NN', 'IN', [(Pos([-1]),'NN'), (Word([0]),'of')]))
 
         # NOTE1: (!!FIXME) A far better baseline uses nltk.tag.UnigramTagger,
         # with a RegexpTagger only as backoff. For instance,
diff --git a/nltk/tag/sequential.py b/nltk/tag/sequential.py
index 3576d2d8a..0ce5ee683 100644
--- a/nltk/tag/sequential.py
+++ b/nltk/tag/sequential.py
@@ -335,11 +335,11 @@ class UnigramTagger(NgramTagger):
         >>> from nltk.corpus import brown
         >>> from nltk.tag import UnigramTagger
         >>> test_sent = brown.sents(categories='news')[0]
         >>> unigram_tagger = UnigramTagger(brown.tagged_sents(categories='news')[:500])
         >>> for tok, tag in unigram_tagger.tag(test_sent):
-        ...     print("({}, {}), ".format(tok, tag))
+        ...     print("({}, {}), ".format(tok, tag)) # doctest: +NORMALIZE_WHITESPACE
         (The, AT), (Fulton, NP-TL), (County, NN-TL), (Grand, JJ-TL),
         (Jury, NN-TL), (said, VBD), (Friday, NR), (an, AT),
         (investigation, NN), (of, IN), (Atlanta's, NP$), (recent, JJ),
         (primary, NN), (election, NN), (produced, VBD), (``, ``),
         (no, AT), (evidence, NN), ('', ''), (that, CS), (any, DTI),
@@ -489,11 +489,11 @@ class AffixTagger(ContextTagger):
             return token[self._affix_length :]
 
 
 @jsontags.register_tag
 class RegexpTagger(SequentialBackoffTagger):
-    """
+    r"""
     Regular Expression Tagger
 
     The RegexpTagger assigns tags to tokens by comparing their
     word strings to a series of regular expressions.  The following tagger
     uses word suffixes to make guesses about the correct Brown Corpus part
@@ -501,11 +501,11 @@ class RegexpTagger(SequentialBackoffTagger):
 
         >>> from nltk.corpus import brown
         >>> from nltk.tag import RegexpTagger
         >>> test_sent = brown.sents(categories='news')[0]
         >>> regexp_tagger = RegexpTagger(
-        ...     [(r'^-?[0-9]+(.[0-9]+)?$', 'CD'),   # cardinal numbers
+        ...     [(r'^-?[0-9]+(\.[0-9]+)?$', 'CD'),  # cardinal numbers
         ...      (r'(The|the|A|a|An|an)$', 'AT'),   # articles
         ...      (r'.*able$', 'JJ'),                # adjectives
         ...      (r'.*ness$', 'NN'),                # nouns formed from adjectives
         ...      (r'.*ly$', 'RB'),                  # adverbs
         ...      (r'.*s$', 'NNS'),                  # plural nouns
@@ -513,11 +513,11 @@ class RegexpTagger(SequentialBackoffTagger):
         ...      (r'.*ed$', 'VBD'),                 # past tense verbs
         ...      (r'.*', 'NN')                      # nouns (default)
         ... ])
         >>> regexp_tagger
         <Regexp Tagger: size=9>
-        >>> regexp_tagger.tag(test_sent)
+        >>> regexp_tagger.tag(test_sent) # doctest: +NORMALIZE_WHITESPACE
         [('The', 'AT'), ('Fulton', 'NN'), ('County', 'NN'), ('Grand', 'NN'), ('Jury', 'NN'),
         ('said', 'NN'), ('Friday', 'NN'), ('an', 'AT'), ('investigation', 'NN'), ('of', 'NN'),
         ("Atlanta's", 'NNS'), ('recent', 'NN'), ('primary', 'NN'), ('election', 'NN'),
         ('produced', 'VBD'), ('``', 'NN'), ('no', 'NN'), ('evidence', 'NN'), ("''", 'NN'),
         ('that', 'NN'), ('any', 'NN'), ('irregularities', 'NNS'), ('took', 'NN'),
diff --git a/nltk/tbl/demo.py b/nltk/tbl/demo.py
index 613351b03..8bdb8d360 100644
--- a/nltk/tbl/demo.py
+++ b/nltk/tbl/demo.py
@@ -391,15 +391,15 @@ def _demo_plot(learning_curve_output, teststats, trainstats=None, take=None):
     plt.plot(r, testcurve, r, traincurve)
     plt.axis([None, None, None, 1.0])
     plt.savefig(learning_curve_output)
 
 
-NN_CD_TAGGER = RegexpTagger([(r"^-?[0-9]+(.[0-9]+)?$", "CD"), (r".*", "NN")])
+NN_CD_TAGGER = RegexpTagger([(r"^-?[0-9]+(\.[0-9]+)?$", "CD"), (r".*", "NN")])
 
 REGEXP_TAGGER = RegexpTagger(
     [
-        (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
+        (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers
         (r"(The|the|A|a|An|an)$", "AT"),  # articles
         (r".*able$", "JJ"),  # adjectives
         (r".*ness$", "NN"),  # nouns formed from adjectives
         (r".*ly$", "RB"),  # adverbs
         (r".*s$", "NNS"),  # plural nouns

Vulnerable code:             (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
                (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
                "final: {finalerrors:5d} {finalacc:.4f} ".format(**train_stats)
        """
        ... (r'^-?[0-9]+(.[0-9]+)?$', 'CD'),   # cardinal numbers
        0.2450142...
            Found 845 useful rules.
          47  63  16 161  | NN->IN if Pos:NNS@[-1]
        [1775, 1269, [132, 85, 69, 51, 47, 33, 26, 24, 22, 17]]
        TRAIN (   2417 tokens) initial  1775 0.2656 final:  1269 0.4750
        0.43996...
        [1855, 1376, [100, 85, 67, 58, 27, 36, 27, 16, 31, 32]]
            Found 845 useful rules.
        0.44159544...
        ...     print("({}, {}), ".format(tok, tag))
    """
        ...     [(r'^-?[0-9]+(.[0-9]+)?$', 'CD'),   # cardinal numbers
        >>> regexp_tagger.tag(test_sent)
NN_CD_TAGGER = RegexpTagger([(r"^-?[0-9]+(.[0-9]+)?$", "CD"), (r".*", "NN")])
        (r"^-?[0-9]+(.[0-9]+)?$", "CD"),  # cardinal numbers
Fixed code:             (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers
                (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers
                "final: {finalerrors:5d} {finalacc:.4f}".format(**train_stats)
        r"""
        ... (r'^-?[0-9]+(\.[0-9]+)?$', 'CD'),  # cardinal numbers
        0.2433862...
            Found 847 useful rules.
          47  63  16 162  | NN->IN if Pos:NNS@[-1]
        [1776, 1270, [132, 85, 69, 51, 47, 33, 26, 24, 22, 17]]
        TRAIN (   2417 tokens) initial  1776 0.2652 final:  1270 0.4746
        0.43833...
        [1859, 1380, [100, 85, 67, 58, 27, 36, 27, 16, 31, 32]]
            Found 847 useful rules.
        0.43996743...
        ...     print("({}, {}), ".format(tok, tag)) # doctest: +NORMALIZE_WHITESPACE
    r"""
        ...     [(r'^-?[0-9]+(\.[0-9]+)?$', 'CD'),  # cardinal numbers
        >>> regexp_tagger.tag(test_sent) # doctest: +NORMALIZE_WHITESPACE
NN_CD_TAGGER = RegexpTagger([(r"^-?[0-9]+(\.[0-9]+)?$", "CD"), (r".*", "NN")])
        (r"^-?[0-9]+(\.[0-9]+)?$", "CD"),  # cardinal numbers