Redis fixes glob backtracking and negative random-member counts

A pattern that never matches can consume much more work than one that succeeds. Redis's February security release fixes a glob matcher that repeatedly explored combinations of wildcard matches even after a suffix had proved impossible. The same release fixes an unrelated count boundary in random-member commands. Together they show two ways that accepted inputs can exceed the assumptions of the code processing them.

The 7.0 release notes date Redis 7.0.9 to February 28. They identify CVE-2022-36021 in string-pattern matching and CVE-2023-25155 in SRANDMEMBER, ZRANDMEMBER, and HRANDFIELD. The reported outcomes are excessive CPU consumption and server termination, respectively. Neither fix depends on a new application-facing command.

I have used Redis since its early releases, and its compact command interface is one reason it remains useful. These patches are a reminder that the cost of a command also depends on the structure and range of its arguments. A query that returns no data can still require substantial computation before the server determines that result.

Wildcards can revisit the same failed search

The pattern-matching fix describes exponential time complexity for pathological patterns. Its regression test stores a key composed of repeated instances of one character, then searches with repeated wildcard-separated occurrences of that character followed by a different final character. The required final character is absent, so the answer is empty.

The expensive part is finding that empty answer. A wildcard can consume different lengths of the candidate string. With multiple wildcards, a recursive matcher can reconsider many partitions of the same candidate. Failure at the final literal can lead earlier recursive calls to try longer matches, even where those attempts cannot make the remaining suffix succeed.

The patch introduces a shared skipLongerMatches flag into the recursive implementation. When searching the rest of the pattern from every remaining starting point has failed, it sets that flag. Earlier wildcard calls then return without trying longer prefixes that would require the same suffix to match later in the same string.

The code comment states the reasoning directly. A longer match for an earlier pattern component would require the remainder to match at a later position. The completed suffix search has already ruled out every such position. Passing that knowledge back through recursion prevents redundant exploration.

This is more specific than a generic recursion limit. The matcher records a fact about a failed search and uses it to prune work that cannot change the result. The public stringmatchlen() entry point initializes the flag and calls the internal implementation, so callers retain the same function interface.

A scanning command still invokes the matcher

The release notes name SCAN and KEYS as examples of affected string-matching commands. That matters because choosing an incremental key traversal does not automatically bound the cost of evaluating a particular pattern against a candidate. Traversal strategy and matcher complexity are separate parts of the operation.

The patch does not introduce a new glob language or require application code to rewrite ordinary patterns. Its purpose is to preserve the answer while avoiding repeated searches already known to fail. That makes it an implementation correction with availability consequences for callers sharing the server.

The regression test's expected empty result is useful evidence of intent. Correctness includes both returning no matching keys and completing the computation without the old pathological exploration. A test that checked only matching patterns would miss the failure mode, since the expensive search depends on the final inability to match.

Negating the minimum signed value is different

The random-command fix addresses a different property of its inputs. A signed integer type has one negative value whose positive magnitude exceeds its maximum positive value. Code that accepts the entire signed range and later takes a negative count's magnitude must account for that asymmetry.

The old parser accepted the full signed long range. Replacing that call with a range-aware helper makes the excluded endpoint visible at each command entry point. This avoids relying on an assertion deeper in response construction to discover that the count was unsuitable.

The patch changes count parsing to require a range from -LONG_MAX to LONG_MAX. It thereby excludes the minimum negative value before later operations derive a count from it. The correction applies to the set, hash, and sorted-set random-member implementations.

The source also changes the lower bounds used when replies include values or scores. Those checks now use -LONG_MAX/2 alongside LONG_MAX/2. The bounds protect the expanded reply representation while keeping the accepted negative magnitude within the intended range.

This follows January's arithmetic fixes but addresses a distinct boundary. A parser can reject a number outside the machine type and still accept a value that cannot survive the operation the command performs next. The valid domain for the command is narrower than the domain of its storage type.

The tests express the boundary explicitly

The random-command commit adds error assertions for the minimum 64-bit signed value. Hash and sorted-set tests cover both the plain count form and the form that includes associated values or scores. The set test supplies the same extreme count and expects a range error.

These tests are valuable because the boundary is easy to overlook when reading ordinary small-count examples. Positive counts do not exercise negation. Small negative counts do not reach the asymmetric endpoint. Testing the endpoint expresses the exact condition that the new range parser excludes.

The release also fixes separate crashes and memory-corruption problems, including a FLUSHALL case involving a client watching multiple keys. Those entries have their own mechanisms. They should not be treated as additional consequences of the glob matcher simply because they share a release.

I prefer reading these changes through the invariants they restore. Pattern matching can stop once the remaining suffix has no possible starting position. Count parsing can exclude a signed value whose magnitude cannot be represented. Both fixes move the relevant reasoning into the operation that needs it, while keeping ordinary command use and expected results intact.