正则表达式疯狂：java.util.regex.Pattern matcher进入高CPU循环

注意：我已经看到了这个问题 ，但没有人回答它，所以它没有多大帮助。 奇怪的是，被标记为“可能重复”的问题已被删除（我第一次看到它。）

我们使用Pattern进行正则表达式validation时遇到问题。 我们的代码中没有发生这种情况，整个事情都发生在Spring Framework和Hibernate的validation中。

（Spring 3.2.1，Spring 3.1.1，Hibernate Validation 4.2.0）

此调用尝试使用@Valid注释validationSpring Framework @ModelAttribute注释：

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

validation的FooBar对象上的字段具有如下的@Pattern注释：

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

类FooBar还包含其他自定义对象，这些对象具有自己的级联validation。

ValidPattern.MYVALIDPATTERN中的validation模式如下所示：

 ^([\w\-,:'"\.\?+_#~!@#$&*() /]*|(?:™)*|(?:®)*|(?:©)*)*$ 

调用此validation时，它可以在99.99％的时间内正常工作。 但至少每天一次，一个线程以某种方式与整个服务器“逃跑”，我们必须手动杀死它（否则最终导致堆栈溢出。）

当我们杀死线程时，我们发现线程已经卡在这个Pattern类中，反复做一些事情（下面的堆栈跟踪）。 关于如何修复（甚至陷阱）这个的任何想法？

 [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] 

Answer 1

请注意pobrelkey和David Wallace的答案都是正确的，但这里有更多的解释……

这个正则表达式“疯狂”（伟大的标题BTW）的原因是因为它受到灾难性的回溯 。 它有经典： /^(A*)*$/ form。 请注意，仅当模式与目标字符串不匹配时才会发生此失控行为。

鉴于失控模式： ^(A*|B*|C*|D*)*$有几个选项可以解决它：

• ^(A|B|C|D)*$ – 从组中的四个备选项中的每一个中删除星号（“零或更多”量词）。
• ^(A*+|B*+|C*+|D*+)*$ – 使每个替代星号量词占有 （即将每个*改为*+ ）。
• ^(?>A*|B*|C*|D*)*$ – 使包含替代primefaces的组成为primefaces 。

第二个应该比第一个执行得快一点，但这三个都将解决“正则表达式疯狂”的问题。 （是的，最好不用正则表达式解析HTML。）

Answer 2

不要写一个可能无限多次包含零长度子匹配的正则表达式（即forms(X*)* ）。

固定版本的模式：

 ^(?:[\w\-,:'"\.\?+_#~!@#$&*() /]|™|®|©)*$ 

Answer 3

尝试在每个子图案后删除星星。 它们对模式匹配没有任何影响，但它们会导致JVM沿着各种路径寻找匹配。