Regex gone wild: java.util.regex.Pattern matcher goes into high CPU loop

7
votes

NOTE: I have seen this question, but no one has answered it yet so it's not much help. And strangely, the question that was marked as "possible duplicate" has been deleted (first time I've seen that.)

We are having a problem with a regex validation using Pattern. None of this is happening in our code, the whole thing is happening in Spring Framework and Hibernate's validation.

(Spring 3.2.1, Spring 3.1.1, Hibernate Validation 4.2.0)

This call is attempting to validate a Spring Framework @ModelAttribute annotation with an @Valid annotation:

@RequestMapping("/foo/bar")
public String doFooBar(@Valid @ModelAttribute("fooBarForm") FooBar form)

The fields on the validated FooBar object have @Pattern annotations like this:

public class FooBar implements Serializable{
    @Length(min=0,max=22) @Pattern(regexp=ValidPattern.MYVALIDPATTERN)
    private String myField;

Class FooBar also contains other custom objects which have their own cascaded validations.

The validation pattern in ValidPattern.MYVALIDPATTERN looks like this:

^([\w\-,:'"\.\?+_#~!@#$&*() /]*|(?:<sup>&trade;</sup>)*|(?:<sup>&reg;</sup>)*|(?:<sup>&copy;</sup>)*)*$

When this validation is called, it works fine 99.99% of the time. But at least once a day, a thread "runs away" with the whole server somehow and we have to kill it manually (or else it eventually causes a stack overflow.)

When we kill the thread, we find that the thread has been stuck in this Pattern class, doing something over and over (stack trace below). Any ideas on how to fix (or even trap) this?

[Top of stack]

java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$6.isSatisfiedBy(Pattern.java:4780)
java.util.regex.Pattern$CharProperty.match(Pattern.java:3362)
java.util.regex.Pattern$Curly.match0(Pattern.java:3777)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.match(Pattern.java:4312)
java.util.regex.Pattern$GroupTail.match(Pattern.java:4244)
java.util.regex.Pattern$BranchConn.match(Pattern.java:4095)
java.util.regex.Pattern$Curly.match0(Pattern.java:3799)
java.util.regex.Pattern$Curly.match(Pattern.java:3761)
java.util.regex.Pattern$Branch.match(Pattern.java:4131)
java.util.regex.Pattern$GroupHead.match(Pattern.java:4185)
java.util.regex.Pattern$Loop.matchInit(Pattern.java:4331)
java.util.regex.Pattern$Prolog.match(Pattern.java:4268)
java.util.regex.Pattern$Begin.match(Pattern.java:3137)
java.util.regex.Matcher.match(Matcher.java:1138)
java.util.regex.Matcher.matches(Matcher.java:519)
org.hibernate.validator.constraints.impl.PatternValidator.isValid(PatternValidator.java:52)
org.hibernate.validator.constraints.impl.PatternValidator.isValid(PatternValidator.java:28)
org.hibernate.validator.engine.ConstraintTree.validateSingleConstraint(ConstraintTree.java:278)
org.hibernate.validator.engine.ConstraintTree.validateConstraints(ConstraintTree.java:153)
org.hibernate.validator.engine.ConstraintTree.validateConstraints(ConstraintTree.java:117)
org.hibernate.validator.metadata.MetaConstraint.validateConstraint(MetaConstraint.java:84)
org.hibernate.validator.engine.ValidatorImpl.validateConstraint(ValidatorImpl.java:452)
org.hibernate.validator.engine.ValidatorImpl.validateConstraintsForDefaultGroup(ValidatorImpl.java:397)
org.hibernate.validator.engine.ValidatorImpl.validateConstraintsForCurrentGroup(ValidatorImpl.java:361)
org.hibernate.validator.engine.ValidatorImpl.validateInContext(ValidatorImpl.java:313)
org.hibernate.validator.engine.ValidatorImpl.validateCascadedConstraint(ValidatorImpl.java:613)
org.hibernate.validator.engine.ValidatorImpl.validateCascadedConstraints(ValidatorImpl.java:478)
org.hibernate.validator.engine.ValidatorImpl.validateInContext(ValidatorImpl.java:322)
org.hibernate.validator.engine.ValidatorImpl.validateCascadedConstraint(ValidatorImpl.java:613)
org.hibernate.validator.engine.ValidatorImpl.validateCascadedConstraints(ValidatorImpl.java:478)
org.hibernate.validator.engine.ValidatorImpl.validateInContext(ValidatorImpl.java:322)
org.hibernate.validator.engine.ValidatorImpl.validate(ValidatorImpl.java:139)
org.springframework.validation.beanvalidation.SpringValidatorAdapter.validate(SpringValidatorAdapter.java:102)
org.springframework.validation.DataBinder.validate(DataBinder.java:772)
org.springframework.web.method.annotation.ModelAttributeMethodProcessor.validateIfApplicable(ModelAttributeMethodProcessor.java:159)
org.springframework.web.method.annotation.ModelAttributeMethodProcessor.resolveArgument(ModelAttributeMethodProcessor.java:107)

[Abbreviated for brevity]
3
javaregexspringhibernatevalidation
If I'm understanding correctly you are using a RegEx to validate/parse HTML? - Mitch Wheat
Oh, no, @Mitch, you're not going to link to THAT question are you? - Dawood ibn Kareem
He comes, he comes.... - Mitch Wheat
I would read this. Your pattern is a mess... - Boris the Spider
@BoristheSpider I was about to link that. - Justin

3 Answers

9
votes

Note that pobrelkey's and David Wallace's answers are both correct but here's a bit more explanation...

The reason this regex is "going wild" (great title BTW) is because it is subject to catastrophic backtracking. It has the classic: /^(A*)*$/ form. Note that this runaway behavior only occurs when the pattern does NOT match the target string.

Given the runaway pattern: ^(A*|B*|C*|D*)*$ there are several options to fix it:

  • ^(A|B|C|D)*$ - Remove the asterisk (the "zero or more" quantifier) from each of the four alternatives within the group.
  • ^(A*+|B*+|C*+|D*+)*$ - Make each alternative asterisk quantifier possessive (i.e. Change each * to *+).
  • ^(?>A*|B*|C*|D*)*$ - Make the group containing the alternatives atomic.

The second two should perform quite a bit faster than the first, but all three will fix the "regex gone wild" problem. (And yes, its best to NOT parse HTML with regex.)

5
votes

Don't write a regexp that can potentially contain a zero-length submatch infinitely many times (i.e. something of the form (X*)*).

Fixed version of your pattern:

^(?:[\w\-,:'"\.\?+_#~!@#$&*() /]|<sup>&trade;</sup>|<sup>&reg;</sup>|<sup>&copy;</sup>)*$
4
votes

Try removing the stars after each sub-pattern. They don't make any difference to what the pattern matches, but they will cause the JVM to go down all sorts of paths looking for matches.