Need

Validation of user input with regular expressions that run in linear time

Context

Description

private val CODE = Regex("(a+)+b")

fun isValidCode(input: String): Boolean =
    // Nested quantifiers backtrack exponentially on inputs like "aaaa...a!"
    CODE.matches(input)

The `isValidCode` function below validates user input against the pattern `(a+)+b`, which contains a quantified group whose content is itself quantified. The JVM regular expression engine uses backtracking. When the input does not match, a pattern with nested quantifiers makes the engine try every way of splitting the input between the inner and outer loops, and that number grows exponentially with the length of the input. A string of about 30 `a` characters without a final `b` keeps a CPU core busy for seconds, and a few concurrent requests like that exhaust the worker threads of the service. Patterns such as `(a|a)*`, `(.*)*` and `(\w+\s?)*$` have the same problem, and they are common in validations of emails, names and paths.

private const val MAX_CODE_LENGTH = 64
private val CODE = Regex("a+b")

fun isValidCode(input: String): Boolean =
    // Bounded length and a single quantifier keep matching linear
    input.length <= MAX_CODE_LENGTH && CODE.matches(input)

The corrected function rewrites the pattern as `a+b`, which accepts exactly the same strings as `(a+)+b` but has a single quantifier, so the engine can only split the input in one way and runs in linear time. It also rejects inputs longer than 64 characters before running the expression. Limiting the length bounds the cost of any pattern, and it is a sensible check for a code field anyway. When a complex pattern is unavoidable, possessive quantifiers such as `a++` or atomic groups `(?>...)` prevent backtracking, and a regular expression library with linear-time matching, such as RE2/J, removes the risk entirely.

References