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>

1 files changed, 6 insertions, 0 deletions

diff --git a/tests/unit/keyspace.tcl b/tests/unit/keyspace.tcl
index b173e0efc..43690d06b 100644
--- a/tests/unit/keyspace.tcl
+++ b/tests/unit/keyspace.tcl
@@ -493,4 +493,10 @@ foreach {type large} [array get largevalue] {
         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"
+    } {}
 }