登录
当前位置： 首页 > 面试题库 >

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

颛孙飞
2023-03-14
问题内容：

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

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

（Spring 3.2.1，Spring 3.1.1，Hibernate Validation 4.2.0）

该调用尝试使用@Valid注释验证Spring Framework @ModelAttribute注释：

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

经过验证的FooBar对象上的字段具有@Pattern注释，如下所示：

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

FooBar类还包含其他具有自定义验证的自定义对象。

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

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

调用此验证时，它可以在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]

问题答案：

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

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

考虑到失控模式： ^(A*|B*|C*|D*)*$有几种解决方法：

  • ^(A|B|C|D)*$ -从组内的四个替代项中删除星号（“零个或多个”量词）。
  • ^(A*+|B*+|C*+|D*+)*$-使每个备选星号量词都 具有所有格 （即，将每个都更改*为*+）。
  • ^(?>A*|B*|C*|D*)*$-使包含替代物的组 原子化 。

后两个的性能应该比第一个快很多，但是所有三个都将解决“ regex变得疯狂”的问题。（是的，最好不要使用正则表达式解析HTML。）



 类似资料：
  • 正则表达式变得疯狂：java.util.regex.Pattern匹配器进入了高CPU循环

    问题内容： 我们在使用Pattern进行正则表达式验证时遇到问题。这些都没有发生在我们的代码中，整个事情都在Spring Framework和Hibernate的验证中发生。 （Spring 3.2.1，Spring 3.1.1，Hibernate Validation 4.2.0） 该调用尝试使用@Valid注释验证Spring Framework @ModelAttribute注释： 经过验证

  • >>正则表达式匹配

    我们得到了一些这样的内容：

  • 与正则表达式匹配的正则表达式

    有没有人试图描述与正则表达式匹配的正则表达式？ 由于重复的关键字，这个主题几乎不可能在网上找到。 它可能在实际应用程序中不可用，因为支持正则表达式的语言通常具有解析它们的方法，我们可以将其用于验证，以及一种在代码中分隔正则表达式的方法，可用于搜索目的。 但是我仍然想知道匹配所有正则表达式的正则表达式是什么样子的。应该可以写一个。

  • 正则表达式 - 匹配规则

    主要内容：基本模式匹配,字符簇,确定重复出现基本模式匹配 一切从最基本的开始。模式，是正则表达式最基本的元素，它们是一组描述字符串特征的字符。模式可以很简单，由普通的字符串组成，也可以非常复杂，往往用特殊的字符表示一个范围内的字符、重复出现，或表示上下文。例如： 这个模式包含一个特殊的字符 ^，表示该模式只匹配那些以 once 开头的字符串。例如该模式与字符串 "once upon a time" 匹配，与 "There once was

  • 正则表达式进入无限循环

    问题内容： 我正在解析（种类）表格的名称： 通常有两个项（二项式），但有时有3个或更多。 我写 大部分时间都有效，但偶尔会陷入无限循环。花了一些时间来查找正则表达式匹配中的内容，然后我才意识到这是一个错字，我应该写 正确执行。 我的问题是： 为什么会发生这种循环？ 有没有办法在运行程序之前检查类似的正则表达式错误？否则，可能很难在prgram分发之前就将它们捕获并引起问题。 [注意：我不需要物种的

  • 正则表达式匹配器在Android

    我无法在Android环境中设置RegEx匹配器。 我的字符串模式： 未转义的模式（匹配所有内容，但西里尔字母和拉丁字母，数字，空格，逗号，感叹号，减号，下划线，方括号，分号和加全局忽略大小写;我认为这些是“合法的”）： 我的代码： 但是，这既不会引发任何错误，也不会起作用。 到目前为止，我尝试过但没有成功（其中string是String变量）： < li> < Li > < code > pat

相关阅读

正则表达式匹配数正则表达式通配符匹配重叠正则表达式匹配匹配键值模式正则表达式Java正则表达式-重叠匹配

相关文章

Perl 正则表达式Ruby 正则表达式MongoDB正则表达式C#正则表达式Java正则表达式

相关问答

STD：：正则表达式不匹配正则表达式匹配年份？与模式匹配的正则表达式Swift提取正则表达式匹配javascript多个正则表达式匹配

相关工具

正则表达式测试器WizTools.org正则表达式测试工具Quartz 表达式生成器卡片式插入列表cocos2d 高仿捕鱼达人

相关文档

正则表达式正则表达式（regular expression）Java 正则表达式教程疯狂的程序员Python 正则表达式操作指南
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.