ReDoS in like/nlike filter operators via unbounded %-to-.* translation #408

Summary

The like and nlike query-filter operators in @triplit/client's filter engine build a JS regular expression from the SQL-LIKE pattern by turning every % wildcard into .*. Escaping is correct (no regex metacharacter injection), but the resulting anchored pattern ^.*x.*x...$ backtracks super-linearly in the number of % wildcards when the target string does not match. A pattern with ~12-16 % wildcards freezes the JS event loop / worker thread for 3-7 seconds (measured).

Reachable whenever host-application code routes untrusted input into a like/nlike filter (a "search flags" box, an admin-panel filter field, a value taken from a URL/query param).

Root cause

packages/db/src/filters.ts, ilike(), called from evaluateFilterStatement() on the 'like' (line 209) and 'nlike' (line 217) operator branches:

function ilike(text: string, pattern: string): boolean {
  pattern = pattern.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, '\\$&'); // escape specials
  pattern = pattern.replace(/%/g, '.*');   // % -> .*
  pattern = pattern.replace(/_/g, '.');    // _ -> .
  const regex = new RegExp(`^${pattern}$`, 'i');
  return regex.test(text);
}

Each % contributes one .*. A pattern such as %a%a%a...z becomes ^.*a.*a.*a...z$. Against a target that does not end in z, V8 must explore exponentially many ways to partition the matched prefix across the .* units before failing. Specific to the like/nlike regex path -- other operators use a type-strict compareValue() that is unaffected.

Proof of concept

ilike() copied verbatim (pure function of its two arguments), measured wall-clock time against a fixed non-matching target of length 30:

N(wildcards)  time
8               171 ms
10              987 ms
12             3220 ms
14             6025 ms
16             6719 ms

Time grows roughly quadratically/exponentially with wildcard count, plateauing only once V8's internal backtracking heuristics kick in (N>=18).

Minimal in-app trigger, q from user input:

client.query('flags').where('title', 'like', '%' + q + '%').fetchOne();

Impact

Client-side denial of service. In a browser this blocks the main thread (UI freeze); in a Node/worker deployment it blocks the event loop / worker, stalling all concurrent requests served by that thread. Low severity: no data exposure, no memory corruption, requires the host app to pass an attacker-influenced pattern into a like/nlike filter.

Suggested fix

• Collapse a run of consecutive % into a single .* before compiling, so N % doesn't yield N .*.
• Linear matcher: single-pass DP / two-pointer scan, O(text*pattern), no backtracking (standard fix for LIKE ReDoS).
• Cap the number of wildcards / pattern length before compiling.

Disclosure note

No SECURITY.md / private vulnerability reporting found on this repo, so filing as a public issue.

This report was produced with AI assistance (Claude, Anthropic). The PoC copies the library's ilike() function verbatim and measures its timing directly (source-trace + standalone timing repro, not a full live-fire against a running Triplit deployment).