Regex Stack Overflow On Repeated Group
ID |
java.regex_stack_overflow |
Severity |
high |
Remediation Complexity |
medium |
Remediation Risk |
low |
Remediation Effort |
low |
Resource |
Reliability |
Language |
Java |
Tags |
code-style |
Description
Reports a repetition (*, +, {n,}) applied to a group whose body offers more than one way to match: an alternation, an optional element, or a repetition of its own.
Rationale
The JDK regex engine backtracks with recursive method calls. A repeated group whose body has only one way to match consumes no extra stack per iteration, but a group with several ways to match — an alternation, an optional element, or a nested repetition — pushes another stack frame for every iteration of the outer repetition while the engine explores its options:
Pattern.compile("(m|n)*"); // each iteration recurses to try 'm', then 'n'
Pattern.compile("(mn?)*"); // each iteration recurses to try with, then without, the 'n'On a large enough input, matching either pattern overflows the stack instead of failing gracefully.
Remediation
Fold the alternatives into a character class when they are single characters — a class is one atom, not a group, and has nothing to backtrack into:
Pattern.compile("[mn]*");Or use a possessive quantifier, which never backtracks in the first place:
Pattern.compile("(mn?)*+");What is not reported
A repetition over a character class () is never reported — a class is a single atom. A possessive quantifier is never reported — it disables backtracking entirely. A repetition over a group whose body is a fixed sequence with no alternation, optional element or nested repeat ((mno)) is fine as it stands.