diff options
author | Oran Agra <oran@redislabs.com> | 2023-02-28 15:15:26 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-02-28 15:15:26 +0200 |
commit | dcbfcb916ca1a269b3feef86ee86835294758f84 (patch) | |
tree | 2df3290d73d6a1bfe68fdcfe546dbc7a18e19912 /src/util.c | |
parent | 18017df7c1407bc025741c64a90f20f4a8098bd2 (diff) | |
download | redis-dcbfcb916ca1a269b3feef86ee86835294758f84.tar.gz |
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>
Diffstat (limited to 'src/util.c')
-rw-r--r-- | src/util.c | 27 |
1 files changed, 23 insertions, 4 deletions
diff --git a/src/util.c b/src/util.c index d33f4522a..26d92b922 100644 --- a/src/util.c +++ b/src/util.c @@ -53,8 +53,8 @@ #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]) { @@ -66,12 +66,25 @@ int stringmatchlen(const char *pattern, int 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 '?': @@ -173,6 +186,12 @@ int stringmatchlen(const char *pattern, int patternLen, 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); } |