Java Regex Tutorial: Pattern, Matcher, Groups, Lookarounds and ReDoS
A beginner-first guide to java.util.regex: Pattern and Matcher, named groups, flags, lookarounds and replaceAll with a lambda, then the failure mode. Measured on JDK 25: which patterns still blow up exponentially, what the JDK already defuses, and fixes that work (rewriting, possessive quantifiers, atomic groups, a CharSequence timeout, input limits).
A login form passes the username to a validation regex. Somebody submits forty characters, and one thread on the server spins at 100% CPU for longer than anyone is willing to wait. No exception, no log line, just a stuck request — and a few more like it take the service down. That failure has a name, ReDoS (regular-expression denial of service), and it lives in the same java.util.regex package you already use for email checks and log parsing. This article starts from Pattern and Matcher, covers groups, flags, lookarounds and replaceAll with a lambda, and then spends its length on the failure mode: which patterns blow up, how badly, what JDK 25 quietly does about it, and the fixes that work. All timings are measured, with every run capped so nothing hangs.
Versions.JDK 25.0.4.1+1 (Temurin, LTS) and JUnit Jupiter 5.11.0, on a 2-vCPU x86-64 virtual machine. Every code block and line of output below comes from the regex module of the java-core-examples repository. Timings are indicative of growth shape on that machine, not a leaderboard, and they move by tens of percent between runs. The repository has no docs folder on purpose — the deeper material is in the collapsible sections of this article.
A Pattern is compiled once; a Matcher is what you run against one input
A regular expression is a tiny program for describing text. In Java you compile the program once into a Pattern (an immutable, thread-safe object) and then create a cheap, single-use Matcher for each string. Keep Pattern objects in static final fields; calling Pattern.compile inside a loop repeats work you only need to do once.
A Matcher offers three different questions, and mixing them up is the most common beginner bug. matches() asks whether the whole string fits the pattern. lookingAt() asks whether the start fits. find() asks whether the pattern occurs anywhere, and can be called repeatedly to walk through every occurrence. The output below runs all three against order-42 shipped with the pattern \d+ (source: BasicsDemo.java, output 01-basics.txt):
matches() on "order-42 shipped" = false
lookingAt() on "order-42 shipped" = false
find() on "order-42 shipped" = true
The diagram shows why all three exist: they anchor the same pattern to different parts of the input. As a rule of thumb, use matches() for validation (“is this entire field an email?”) and find() for extraction (“pull the numbers out of this line”). The site’s older posts cover the validation side in depth: email validation, credit card validation, and regex with Predicates. This article is about what all of them can do wrong under hostile input.
Going deeper
Groups pull pieces out of a match, and names beat numbers
Parentheses do two jobs: they group part of a pattern, and they capture what that part matched. Group 0 is always the whole match; capturing groups are then numbered by the position of their opening parenthesis. Numbers break the moment someone inserts a group in the middle, so give groups names with (?<name>...) and read them with group("name"). A log-line parser in BasicsDemo.java:
static final Pattern LOG = Pattern.compile(
"(?<date>\\d{4}-\\d{2}-\\d{2}) (?<level>INFO|WARN|ERROR) (?<msg>.+)");
Output (01-basics.txt). Names and numbers refer to the same groups, and namedGroups() hands you the mapping:
matches() = true
group(0) = 2026-03-14 ERROR disk /dev/sda1 is 97% full
group(2) = ERROR
level = ERROR
start(msg) = 17, end(msg) = 43
namedGroups = {date=1, level=2, msg=3}
start("msg") and end("msg") give character offsets into the original string, which is what you need for highlighting or for splicing a replacement in. To process every match as a stream, Matcher.results() returns each one as an immutable MatchResult (same file, output lines 12–15).
Non-capturing groups(?:...) group without capturing. Use them whenever you only need grouping for a quantifier or an alternation; they keep numbers stable and, as the ReDoS sections show, they matter for performance in a way that is not obvious.
Going deeper
Flags are options baked into a Pattern. You pass them as a bit mask to Pattern.compile(regex, flags), or switch them on inside the pattern with (?i)-style markers. The four worth knowing first: CASE_INSENSITIVE (i), MULTILINE (m, makes ^ and $ match at every line, not only the ends of the input), DOTALL (s, lets . match a newline) and COMMENTS (x, ignores whitespace and # comments in the pattern so a long regex can be formatted). The demo counts matches of ^error$ against the three lines Error, error, ERROR (01-basics.txt):
Read the table top to bottom. Without MULTILINE, ^ and $ mean the start and end of the whole input, so ^error$ finds nothing in three lines. Turning on only MULTILINE finds the one line that is exactly lower-case; turning on both finds all three, and the embedded (?im) form gives the same answer as the two constants. . does not cross a newline unless DOTALL is on.
Flags are not free of surprises.CASE_INSENSITIVE on its own only folds ASCII letters. For non-English text you also need UNICODE_CASE. I did not measure that here; it is in the Pattern Javadoc.
Going deeper
All flag constants and their embedded forms: Pattern — flags
Lookarounds test the text around a position without consuming it
A lookaround is a condition about what comes before or after the current position. It matches nothing itself — the match position does not move — which is why it is called zero-width. (?=x) is a positive lookahead (what follows is x), (?!x) negative lookahead, (?<=x) positive lookbehind (what precedes is x), (?<!x) negative lookbehind. They let you say “digits followed by px, but do not include the px” (LookaroundDemo.java, output 02-lookarounds.txt):
// positive lookahead: a digit run that is followed by "px", without including "px"
show("\\d+(?=px)", "width:120px; z-index:7; height:48px");
// negative lookahead: "foo" not followed by "bar"
show("foo(?!bar)", "foobar foobaz foo");
// positive lookbehind: digits preceded by a dollar sign
show("(?<=\\$)\\d+(?:\\.\\d\\d)?", "cost $19.99, tax 3, total $23");
// negative lookbehind: digits NOT preceded by a dollar sign
show("(?<![\\d$.])\\d+", "cost $19.99, tax 3, total $23");
The diagram is the whole idea: the amber letters are inspected and then ignored. A practical consequence is that several lookaheads at one position behave like AND. The classic use is a password policy, where each (?=...) states one requirement and all must hold from the start of the string (02-lookarounds.txt):
// several lookaheads at one position = AND of conditions: a password policy
Pattern policy = Pattern.compile("^(?=.*\\d)(?=.*[a-z])(?=.*[A-Z]).{8,}$");
for (String pw : List.of("abcdefgh", "Abcdefg1", "Ab1", "ABCDEFG1x"))
System.out.printf("policy %-10s -> %s%n", pw, policy.matcher(pw).matches());
Lookarounds also make replacements that insert rather than replace. Adding thousands separators is a match of zero characters at every position that has a digit before it and a multiple of three digits after it, replaced by a comma: 1234567 becomes 1,234,567 (02-lookarounds.txt, line 9).
Lookbehind has limits, and they are not where you might expect. On this JDK (?<=a+)b compiles and (?<=a{1,9})b compiles, but (?<=(?:ab)+)c is rejected with Look-behind group does not have an obvious maximum length (02-lookarounds.txt, lines 10–12). I probed only these shapes; I am not claiming a rule for every pattern, and older JDKs may differ — not checked.
replaceAll takes a replacement string or a lambda, and both parse $ and backslash
Matcher.replaceAll(String) replaces every match. Inside the replacement, $1 means “group 1” and ${name} means a named group, so a pattern can be rearranged (ReplaceDemo.java, output 03-replace.txt):
The same feature is a trap: a literal dollar sign in the replacement is not literal. replaceAll("$") throws, and the fix is Matcher.quoteReplacement:
replaceAll("$") -> IllegalArgumentException: Illegal group reference: group index is missing
price: 5 $, fee: 12 $
When the replacement must be computed, pass a lambda: replaceAll(Function<MatchResult,String>). The function receives each match and returns its replacement, which is how you double every number in a string without a manual loop:
The lambda’s return value is still parsed for $ and \. If the value you return is data — a looked-up template variable, say — a $ inside it is interpreted as a group reference. In the demo a variable whose value is $5 makes the unquoted version fail with No group 5, and wrapping it in Matcher.quoteReplacement fixes it (ReplaceDemo.java, output 03-replace.txt):
unquoted lambda -> IndexOutOfBoundsException: No group 5
hello ankur, you owe $5
hi ${nobody}
The last line above shows the third habit worth having: decide what happens for a missing key (here the placeholder is left as it was) instead of letting null reach replaceAll. For writing into a StringBuilder by hand, appendReplacement and appendTail still work, and produce rEgUlAr ExprEssIOns in the demo’s last line.
Going deeper
Backtracking: a regex that fails can take a very long time to fail
Java’s regex engine is a backtracking engine. At each step it makes a choice (take another repetition, or stop and try what comes next) and remembers the other option. If a later step fails, it returns to the last choice and tries the alternative. That is cheap when failures are local. It becomes catastrophic when a pattern has nested quantifiers over the same characters — like (a+)+b — and the input almost matches: a run of as followed by something that is not b. Now there are many ways to split the as between the inner and outer +, and the engine tries every split before it is allowed to say “no match”. For n letters there are about 2n splits.
The picture shows the cost structure: the work is not in any one attempt, it is in the number of attempts, and every added letter doubles it. A textbook pattern like this one is what most ReDoS tutorials use. But before showing numbers, an important result from running it on JDK 25.
JDK 25 already defuses the textbook pattern, but only some shapes
I expected (a+)+b to hang at 30 characters. It did not. The first surprise while building this article was that the classic example is instant on JDK 25: (a+)+b against 36 letters and a ! took 0 ms in the committed run below. The reason is in Pattern.java: the compiler marks greedy group loops so that, at any input position where an attempt already failed, the engine does not try again. (I did not check which JDK release introduced this, so I am not dating it.) The committed excerpt from the JDK source, with the exact condition (07-jdk-source.txt):
// Optimize the greedy Loop to prevent exponential backtracking, IF there
// is no group ref in this pattern. With a non-negative localTCNCount value,
// the greedy type Loop, Curly will skip the backtracking for any starting
// position "i" that failed in the past.
if (!hasGroupRef) {
for (Node node : topClosureNodes) {
if (node instanceof Loop) {
// non-deterministic-greedy-group
((Loop)node).posIndex = localTCNCount++;
}
}
}
Read the first comment line: the optimisation applies “IF there is no group ref in this pattern”. A single backreference anywhere in the pattern switches it off for all of its loops. The timings in 04-blowup.txt (from BlowupDemo.java) show three things. First, (a+)+b is no longer exponential — it grows gently, about 23, 63 and 161 ms for 1,000, 2,000 and 4,000 letters. Second, adding \1? (an optional backreference that never matters) puts the exponential back. Third, a nested repeat without a capturing group, (?:(?:a+)+)+b, blows up with no backreference at all.
The chart puts the three patterns side by side. The green bars are the tamed textbook pattern at up to 4,000 letters; the amber and red bars are the two shapes the optimisation does not reach, which were already at tens to hundreds of milliseconds by 20 to 22 letters and were aborted by 24 to 26. The measured rows, with the exact cap (04-blowup.txt):
pattern (a+)+\1?b
n=20 27 ms matches=false
n=24 690 ms matches=false
n=26 ABORTED after 2036 ms (cap)
...
pattern (?:(?:a+)+)+b
n=16 3 ms matches=false
n=18 13 ms matches=false
n=20 101 ms matches=false
n=22 896 ms matches=false
n=24 ABORTED after 2000 ms (cap)
What this does and does not prove. It proves that these specific patterns behave this way on JDK 25.0.4.1. It does not prove that any pattern without a backreference is safe: (?:(?:a+)+)+b is a counter-example, and I did not map which pattern shapes the JDK’s memoisation covers — the source comment describes it as applying to greedy group loops, and the rows above are the evidence for what it does and does not catch. Also, the polynomial case is real: a*a*a*a*b has no nesting at all, yet it took 824 ms at just 200 letters, and the rows at 50, 100 and 150 show the growth (04-blowup.txt, last block).
Reference: why the JDK’s fix turns exponential into polynomial, and why it is not a guarantee
The JDK’s Loop node records, per loop, the set of input positions where continuing the loop already failed; on a revisit it skips the retry and goes straight to what follows the loop. That turns “every cut of n letters” into “every position once per loop”, and the growth from 23 to 63 to 161 ms above is consistent with polynomial, not exponential, cost. The price, presumably, is memory — the failed positions have to be remembered — and the gate in the source is !hasGroupRef, so any backreference disables it. Everything else about pattern shape is something I measured, not something I read out of the engine.
// Optimize the greedy Loop to prevent exponential backtracking, IF there
// is no group ref in this pattern. With a non-negative localTCNCount value,
// the greedy type Loop, Curly will skip the backtracking for any starting
// position "i" that failed in the past.
Fixing a vulnerable pattern: rewrite first, then possessive or atomic
The best fix is a pattern that cannot backtrack badly. (?:(?:a+)+)+b matches exactly the same strings as a+b — the nesting adds nothing — so rewriting removes the problem. When the structure has to stay, two operators tell the engine not to go back: a possessive quantifier (a++, *+, ?+) matches as much as it can and never gives any back; an atomic group(?>...) does the same for a whole sub-pattern once it has matched. Both make a failed attempt fail immediately instead of trying alternatives.
The demo runs the vulnerable pattern and three fixes against 40 letters and !, each with a 1,000 ms budget (FixesDemo.java, output 05-fixes.txt):
input: 40 x 'a' + '!' budget 1000 ms
vulnerable (?:(?:a+)+)+b ABORTED after 1019 ms
rewritten a+b 0 ms matches=false
possessive (?:a++)++b 7 ms matches=false
atomic (?>(?:a+)+)b 0 ms matches=false
The vulnerable pattern was aborted at the budget; all three fixes answer in single-digit milliseconds. A test in RegexClaimsTest also checks that the four patterns accept and reject the same short strings, so the fixes are not silently changing what matches — on those inputs; it is a spot check, not a proof of equivalence.
A safe pattern can still be slow: find() is quadratic on this input.a+b has no nesting, yet find() tries to start a match at every position, and each attempt scans to the end of a long run of as. On a string of n letters and !, the measured times for a+b were 139, 489 and 1,906 ms at 5,000, 10,000 and 20,000 letters. Prefixing a negative lookbehind, (?<!a)a+b, stops the engine from starting inside a run and brought the same scan down to 6, 6 and 15 ms (05-fixes.txt). Run-to-run noise on this machine is large, so read the shape, not the digits.
find() a+b n=5000 139 ms found=false
find() a+b n=10000 489 ms found=false
find() a+b n=20000 1906 ms found=false
find() (?<!a)a+b n=5000 6 ms found=false
find() (?<!a)a+b n=10000 6 ms found=false
find() (?<!a)a+b n=20000 15 ms found=false
Java has no regex timeout, so build one from CharSequence
There is no timeout API in java.util.regex. I checked the JDK source rather than trusting memory: the word “timeout” appears zero times in Pattern.java and zero times in Matcher.java (07-jdk-source.txt, last lines), and a test asserts that neither class has a public method with “timeout” in its name. A match runs until it finishes.
Pattern.java: 0
Matcher.java: 0
There is a workaround because of how Matcher is designed: it reads its input only through the CharSequence interface, not just from String. So you can pass your own CharSequence whose charAt checks a deadline and throws when time is up. The exception unwinds out of the matcher and you catch it outside. The class is RegexTimeout.java:
private final CharSequence inner;
private final long deadlineNanos;
private final long budgetMillis;
private int calls;
public RegexTimeout(CharSequence inner, long budgetMillis) {
this.inner = inner;
this.budgetMillis = budgetMillis;
this.deadlineNanos = System.nanoTime() + budgetMillis * 1_000_000L;
}
@Override public char charAt(int index) {
// nanoTime() is cheap but not free; look at the clock once per 1024 reads
if ((++calls & 1023) == 0 && System.nanoTime() > deadlineNanos)
throw new RegexTimeoutException(budgetMillis);
return inner.charAt(index);
}
/** matches() with a budget; returns null when the budget ran out. */
public static Boolean matchesWithin(Pattern p, CharSequence input, long budgetMillis) {
try {
return p.matcher(new RegexTimeout(input, budgetMillis)).matches();
} catch (RegexTimeoutException e) {
return null;
}
}
The diagram shows the control path: the engine never knows about the timeout; it just calls charAt, and one of those calls throws. Because the clock is read only once every 1,024 calls, the abort happens slightly after the budget rather than exactly at it — the vulnerable pattern with a 1,000 ms budget was aborted at 1,019 ms in the committed run, and the 2,000 ms cap in the blowup run fired at 2,000 to 2,036 ms. A test asserts an abort comes within three seconds of a 300 ms budget.
Limits of this workaround. It only fires while the engine is reading characters; a match that is stuck inside something that does not call charAt would not be interrupted (I did not find such a case, but I did not prove there is none). It also costs a counter increment per character read; I did not benchmark that overhead.
Limit the input first: length caps, and the stack that runs out before the clock
A timeout is the last line of defence. The first is refusing input you never intended to process. A username does not need to be 50,000 characters, and every pattern here gets worse with length. The wrapper in Safe.java applies both, length first:
public static boolean matches(Pattern p, String input, int maxLength, long budgetMillis) {
if (input.length() > maxLength)
throw new IllegalArgumentException("input longer than " + maxLength + " characters");
Boolean r = RegexTimeout.matchesWithin(p, input, budgetMillis);
if (r == null) throw new RegexTimeout.RegexTimeoutException(budgetMillis);
return r;
}
Long input has a second, unrelated failure. Alternation inside a repeat, (?:a|b)*, evidently recurses deeply on long input (I did not read the engine to see exactly how), and the JVM’s stack is finite. The demo (LimitsDemo.java, output 06-limits.txt) shows it fail well before any timeout could help:
A character class [ab]* does the same job without recursion, and a possessive (?:a|b)*+ also got through 100,000 characters here. The stack depth at which it fails depends on your JVM’s stack size and frame use, so treat 5,000 as “observed on this machine with default settings”, not a constant. Catching StackOverflowError is possible, as the demo does, but it is better to use a pattern that does not recurse.
Reference: a checklist for regexes that see untrusted input
Cap the length first; reject, do not truncate silently.
Prefer a character class to alternation of single characters: [ab]*, not (?:a|b)*.
Remove nesting that adds nothing; rewrite (?:(?:a+)+)+ to a+ (same language, instant).
Use possessive quantifiers or atomic groups where backtracking cannot help.
Avoid backreferences on untrusted input: one switches off the JDK’s loop optimisation for the whole pattern (source excerpt above).
Bound the time with a deadline CharSequence as shown, and treat a timeout as a rejection.
Test patterns with hostile input in a unit test with a budget, as RegexClaimsTest does.
Should you worry about ReDoS at all? Depends on who writes the input
Honest advice. If the regex only ever sees strings you control — config files, your own logs — ReDoS is a curiosity. If it sees text from users, run it with a length cap at minimum. On JDK 25 the classic nested-quantifier examples from older tutorials are mostly harmless, and I would not spend effort rewriting them purely because of that folklore; but I would still rewrite (?:(?:a+)+)+-style nesting and any pattern that combines backreferences with nested repeats, because the measurements show those are not covered. Where a pattern is complex and input is hostile, consider not using a regex: a small hand-written parser has no backtracking to attack. The choice between those is a judgement call, not something this article measured.
No Comments yet!