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

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)
}

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

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