title: Regex gone wild: java.util.regex.Pattern matcher goes into high CPU loop
body: <p>NOTE:  I have seen this <a href="https://stackoverflow.com/questions/14766620/hibernate-validator-eats-cpu-on-regex-matching">question</a>, 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.)</p>
  
  <p>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.  </p>
  
  <p>(Spring 3.2.1, Spring 3.1.1, Hibernate Validation 4.2.0)</p>
  
  <p>This call is attempting to validate a Spring Framework  @ModelAttribute annotation with an @Valid annotation:</p>
  
  <pre><code>@RequestMapping("/foo/bar")
  public String doFooBar(@Valid @ModelAttribute("fooBarForm") FooBar form) 
  </code></pre>
  
  <p>The fields on the validated FooBar object have @Pattern annotations like this:</p>
  
  <pre><code>public class FooBar implements Serializable{
      @Length(min=0,max=22) @Pattern(regexp=ValidPattern.MYVALIDPATTERN)
      private String myField;
  </code></pre>
  
  <p>Class FooBar also contains other custom objects which have their own cascaded validations.  </p>
  
  <p>The validation pattern in ValidPattern.MYVALIDPATTERN looks like this:</p>
  
  <pre><code>^([\w\-,:'"\.\?+_#~!@#$&amp;*() /]*|(?:&lt;sup&gt;&amp;trade;&lt;/sup&gt;)*|(?:&lt;sup&gt;&amp;reg;&lt;/sup&gt;)*|(?:&lt;sup&gt;&amp;copy;&lt;/sup&gt;)*)*$
  </code></pre>
  
  <p>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.)</p>
  
  <p>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?</p>
  
  <pre><code>[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]
  </code></pre>