CVE-2022-36021: Inefficient Algorithmic Complexity (CWE-407)
value: Redis is an in-memory database that persists on disk. Authenticated users can use string matching commands (like `SCAN` or `KEYS`) with a specially crafted pattern to trigger a denial-of-service attack on Redis, causing it to hang and consume 100% CPU time. The problem is fixed in Redis versions 6.0.18, 6.2.11, 7.0.9.

CWE description: An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
CVSS v3 base score: 5.5
Published: 2023-03-01T16:15Z
Repository: https://github.com/redis/redis
Language: Other
Files changed: src/util.c, tests/unit/keyspace.tcl
Commit date: 2023-02-28 15:15:26 +0200
Commit message: String pattern matching had exponential time complexity on pathological patterns (CVE-2022-36021) (#11858)

Authenticated users can use string matching commands with a
specially crafted pattern to trigger a denial-of-service attack on Redis,
causing it to hang and consume 100% CPU time.

Co-authored-by: Tom Levy <tomlevy93@gmail.com>
Diff: diff --git a/src/util.c b/src/util.c
index d33f4522a5..26d92b9229 100644
--- a/src/util.c
+++ b/src/util.c
@@ -51,12 +51,12 @@
 #include "config.h"
 
 #define UNUSED(x) ((void)(x))
 
 /* Glob-style pattern matching. */
-int stringmatchlen(const char *pattern, int patternLen,
-        const char *string, int stringLen, int nocase)
+static int stringmatchlen_impl(const char *pattern, int patternLen,
+        const char *string, int stringLen, int nocase, int *skipLongerMatches)
 {
     while(patternLen && stringLen) {
         switch(pattern[0]) {
         case '*':
             while (patternLen && pattern[1] == '*') {
@@ -64,16 +64,29 @@ int stringmatchlen(const char *pattern, int patternLen,
                 patternLen--;
             }
             if (patternLen == 1)
                 return 1; /* match */
             while(stringLen) {
-                if (stringmatchlen(pattern+1, patternLen-1,
-                            string, stringLen, nocase))
+                if (stringmatchlen_impl(pattern+1, patternLen-1,
+                            string, stringLen, nocase, skipLongerMatches))
                     return 1; /* match */
+                if (*skipLongerMatches)
+                    return 0; /* no match */
                 string++;
                 stringLen--;
             }
+            /* There was no match for the rest of the pattern starting
+             * from anywhere in the rest of the string. If there were
+             * any '*' earlier in the pattern, we can terminate the
+             * search early without trying to match them to longer
+             * substrings. This is because a longer match for the
+             * earlier part of the pattern would require the rest of the
+             * pattern to match starting later in the string, and we
+             * have just determined that there is no match for the rest
+             * of the pattern starting from anywhere in the current
+             * string. */
+            *skipLongerMatches = 1;
             return 0; /* no match */
             break;
         case '?':
             string++;
             stringLen--;
@@ -171,10 +184,16 @@ int stringmatchlen(const char *pattern, int patternLen,
     if (patternLen == 0 && stringLen == 0)
         return 1;
     return 0;
 }
 
+int stringmatchlen(const char *pattern, int patternLen,
+        const char *string, int stringLen, int nocase) {
+    int skipLongerMatches = 0;
+    return stringmatchlen_impl(pattern,patternLen,string,stringLen,nocase,&skipLongerMatches);
+}
+
 int stringmatch(const char *pattern, const char *string, int nocase) {
     return stringmatchlen(pattern,strlen(pattern),string,strlen(string),nocase);
 }
 
 /* Fuzz stringmatchlen() trying to crash it with bad input. */
diff --git a/tests/unit/keyspace.tcl b/tests/unit/keyspace.tcl
index b173e0efca..43690d06b3 100644
--- a/tests/unit/keyspace.tcl
+++ b/tests/unit/keyspace.tcl
@@ -491,6 +491,12 @@ foreach {type large} [array get largevalue] {
         r flushdb
         r set dlskeriewrioeuwqoirueioqwrueoqwrueqw test
         r keys *
         r keys *
     } {dlskeriewrioeuwqoirueioqwrueoqwrueqw}
+
+    test {Regression for pattern matching long nested loops} {
+        r flushdb
+        r SET aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 1
+        r KEYS "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"
+    } {}
 }

Vulnerable code: int stringmatchlen(const char *pattern, int patternLen,
        const char *string, int stringLen, int nocase)
                if (stringmatchlen(pattern+1, patternLen-1,
                            string, stringLen, nocase))
Fixed code: static int stringmatchlen_impl(const char *pattern, int patternLen,
        const char *string, int stringLen, int nocase, int *skipLongerMatches)
                if (stringmatchlen_impl(pattern+1, patternLen-1,
                            string, stringLen, nocase, skipLongerMatches))
                if (*skipLongerMatches)
                    return 0; /* no match */
            /* There was no match for the rest of the pattern starting
             * from anywhere in the rest of the string. If there were
             * any '*' earlier in the pattern, we can terminate the
             * search early without trying to match them to longer
             * substrings. This is because a longer match for the
             * earlier part of the pattern would require the rest of the
             * pattern to match starting later in the string, and we
             * have just determined that there is no match for the rest
             * of the pattern starting from anywhere in the current
             * string. */
            *skipLongerMatches = 1;
int stringmatchlen(const char *pattern, int patternLen,
        const char *string, int stringLen, int nocase) {
    int skipLongerMatches = 0;
    return stringmatchlen_impl(pattern,patternLen,string,stringLen,nocase,&skipLongerMatches);
}


    test {Regression for pattern matching long nested loops} {
        r flushdb
        r SET aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa 1
        r KEYS "a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b"
    } {}