Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

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

Tags:

java

regex

validation

spring

hibernate

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]
like image 786
user1071914 Avatar asked Nov 14 '13 23:11

user1071914

2 Answers

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.)

like image 180
ridgerunner Avatar answered Nov 05 '22 01:11

ridgerunner

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>)*$
like image 45
pobrelkey Avatar answered Nov 05 '22 00:11

pobrelkey
Sign in to Comment

Related questions

Adding interceptors in struts.xml for all Action classes
JPA Creation - Hibernate not showing in platform
Java IPv6 Address String to Bytes
How to find where javaw.exe is installed?
java.lang.NoSuchMethodError: org.eclipse.jdt.internal.compiler.CompilationResult
How to reload a JPanel?
Varargs method modifies caller's array instead of its own copy?
Adjusting size of JPanels in JSplitPane
RSA read PublicKey
Closing A JOptionPane Programmatically
Java priority queues and comparable interface
Android: Disable checkboxes without graphical change?
Java JTextArea KeyListener
Access is denied when using FileOutputStream
MySQLSyntaxErrorException when trying to execute PreparedStatement [duplicate]
Java: Best way to store and access a list of objects
how to call a stored function from jdbc?
"which java" in CentOS prints wrong java path
How to get a random point on the interior of an irregular polygon? [closed]
How to download an HttpResponse into a file?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!