开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

正则表达式模式导致边缘情况下的灾难性回溯

是指在使用正则表达式进行匹配时，某些特定的模式可能会导致匹配过程出现极端缓慢甚至无法完成的情况。这种情况通常发生在输入字符串与正则表达式模式之间存在多种匹配路径，并且模式中包含大量的重复或可选项。

正则表达式是一种强大的文本匹配工具，它使用特定的语法规则来描述字符串的模式。然而，某些模式可能会导致回溯问题，即在尝试匹配时，引擎会尝试多种可能的匹配路径，直到找到匹配或全部路径都尝试完毕。当模式中存在大量的重复或可选项时，回溯问题就会变得尤为严重。

回溯问题的出现主要是由于正则表达式的贪婪匹配特性以及模式中的复杂性所导致的。贪婪匹配意味着引擎会尽可能多地匹配字符，而复杂的模式则增加了匹配路径的数量和长度。当输入字符串与模式不匹配时，引擎会回溯到前面的匹配位置，尝试其他可能的路径。如果模式中存在大量的重复或可选项，回溯的次数将会呈指数级增长，导致匹配过程变得非常缓慢。

为了避免正则表达式模式导致边缘情况下的灾难性回溯，可以采取以下几种方法：

使用非贪婪匹配：在正则表达式中，贪婪匹配是默认的匹配方式，它会尽可能多地匹配字符。而非贪婪匹配则相反，它会尽可能少地匹配字符。通过在重复或可选项后添加问号（?）来实现非贪婪匹配。例如，将""替换为"?"。
使用限定符：限定符可以限制重复的次数，从而减少匹配路径的数量。常用的限定符包括"+"（至少一次）、"?"（零次或一次）和"{n,m}"（至少n次，最多m次）等。
使用具体的匹配规则：尽量避免使用模糊或宽泛的匹配规则，而是使用更具体的规则。例如，使用具体的字符集合代替通配符。
使用原子组：原子组是一种特殊的正则表达式语法，它可以将多个字符组合成一个整体，从而减少回溯的次数。通过在需要组合的字符周围添加"()"来创建原子组。
使用正则表达式引擎的优化选项：一些正则表达式引擎提供了优化选项，可以帮助解决回溯问题。例如，可以通过设置匹配超时时间或限制回溯深度来控制匹配过程。

总之，正则表达式模式导致边缘情况下的灾难性回溯是一种常见的问题，但可以通过使用非贪婪匹配、限定符、具体的匹配规则、原子组以及正则表达式引擎的优化选项来避免或减轻。在实际应用中，需要根据具体的情况选择合适的方法来处理回溯问题。

腾讯云相关产品和产品介绍链接地址：

云服务器（CVM）：https://cloud.tencent.com/product/cvm
云数据库 MySQL 版：https://cloud.tencent.com/product/cdb_mysql
人工智能平台（AI Lab）：https://cloud.tencent.com/product/ailab
腾讯云存储（COS）：https://cloud.tencent.com/product/cos
腾讯云区块链服务（BCS）：https://cloud.tencent.com/product/bcs

相关搜索:有没有办法优化这种灾难性的正则表达式回溯？如何在不使用`(?<!)`的情况下实现负向回溯正则表达式？如何在不出现不匹配的情况下将正则表达式模式放入另一个正则表达式模式正则表达式查找导致紧随其后的组不匹配，但在其他情况下匹配是否可以在不使用调试模式的情况下找到导致ActionScript 3.0错误的函数和/或行号？如何在允许嵌套模式的情况下将整个字符串与正则表达式匹配模块分析失败:严格模式下的八进制文字，可以在不使用构造函数的情况下使用正则表达式微信小程序开发源码微信小程序开发环境微信小程序开发登录

相关搜索:

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

如何彻底避免正则表达式的灾难性回溯？

题图：negative space from pexels 正则表达式的灾难性回溯（Catastrophic Backtracking）是指，正则在匹配的时候回溯过多，造成 CPU 100%，正常服务被阻塞...背景这里有一篇文章详细的描述了一次正则回溯导致 CPU 100% 的发现和解决过程，原文比较长，我之前也在 OpenResty 的开发中遇到过两次类似的问题。...这里简单归纳下，你就可以不用花费时间去了解背景了：大部分开发语言的正则引擎是用基于回溯的 NFA 来实现（而不是基于 Thompson’s NFA）；如果回溯次数过多，就会导致灾难性回溯，CPU 100%...我们有以下两种自动化的方法来解决：静态检测这类工具可以扫描代码中正则表达式，根据一定的算法，从中找出有灾难性回溯的正则。...我们以 Perl 为例，看下 RE2 是否可以避免灾难性回溯问题。

2.1K1 0

讲给前端的正则表达式(4)：避免灾难性回溯

最近 Cloudfare 的一次停机事故就是由于正则表达式导致全球大量机器上的 CPU 峰值飙升至100％【https://blog.cloudflare.com/cloudflare-outage/】...在本文中，我们将会学习需要注意的情况，例如灾难性的回溯。为了帮助我们理解问题，还分析了贪婪和懒惰量词以及为什么 lookahead 可能会有所帮助。...由于默认情况下量词是贪婪的，因此我们会匹配尽可能多的字母。可以用 match函数来确认这一点。 'Heeeeello!'....>/); // ["", (...) ] 灾难性的回溯要了解量词如何影响正则表达式的行为，我们需要仔细研究被称为回溯的过程。先让我们看一下这段看似清白的代码！...我们还讨论了量词可能导致的另一个问题：灾难性回溯。我们还学习了如何使用先行断言（lookahead）来改善性能，而不仅仅是去重写表达式。

5702 0

由Java正则表达式的灾难性回溯引发的高CPU异常：java.util.regex.Pattern$Loop.match

而这个问题，是由正则表达式的灾难性回溯（Catastrophic Backtracking），或者说回溯陷阱造成的。...这里说的比较抽象，有兴趣的可以自行搜索下正则表达式的回溯以及贪婪模式、懒惰模式（也叫勉强模式）和独占模式（也叫侵占模式），下面附上一篇图文并茂的文章：正则表达式三种模式：贪婪模式、懒惰模式、独占模式总之...，简单地说，由于正则表达式的回溯，如果我们的正则表达式写得不够好，并且被匹配的字符串文本又非常长，就有可能大量触发回溯，导致CPU飙升，甚至是堆栈溢出。...当这条很长的sql被上述的正则表达式匹配时，就会发生灾难性回溯，导致系统长时间假死。这里就不贴出来具体的sql了，就简单分析下上述正则表达式存在什么问题。...正则表达式的失控——回溯循环 正则表达式：java.util.regex.Pattern matcher 循环导致高CPU 正则表达式三种模式：贪婪模式、懒惰模式、独占模式 StackOverflowError

9233 0

藏在正则表达式里的陷阱

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...如果在他们之后加多一个 + 符号，那么原先的贪婪模式就会变成独占模式，即尽可能多地匹配，但是不回溯。于是乎，如果要彻底解决问题，就要在保证功能的同时确保不发生回溯。...：catastrophic backgracking（灾难性回溯）。

1922 0

藏在正则表达式里的陷阱，一个正则表达式导致CPU 利用率居高不下

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...如果在他们之后加多一个 + 符号，那么原先的贪婪模式就会变成独占模式，即尽可能多地匹配，但是不回溯。于是乎，如果要彻底解决问题，就要在保证功能的同时确保不发生回溯。...例如我本文中存在问题的那个 URL 使用该网站检查后会提示：catastrophic backgracking（灾难性回溯）。 ?

1.4K2 0

藏在正则表达式里的陷阱

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...我们发现出现问题的 URL 是有下划线（_）和百分号（%）的，但是对应第三部分的正则表达式里面却没有。这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。...这是这个正则表达式存在的第二个问题。解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...如果在他们之后加多一个 + 符号，那么原先的贪婪模式就会变成独占模式，即尽可能多地匹配，但是不回溯。于是乎，如果要彻底解决问题，就要在保证功能的同时确保不发生回溯。...catastrophic backgracking（灾难性回溯）。

5837 0

正则表达式 - 选择、分组和向后引用

多数情况下，提到正则表达式中的子模式（subpattern），就是指分组中的一个或多个分组。...子模式就是模式中的模式。多数情况下，子模式中的条件能得到匹配的前提是前面的模式得到匹配，但也有例外。...但是这种情况下，匹配第二个子模式不依赖于是否匹配第一个。（最左边的模式会首先匹配。）...每当正则做类似的决定时，如果有必要，都会记录其他选择，以便匹配不成功时进行回溯，到最后一个决策点，再重新进行匹配。（1）量词导致回溯考虑正则表达式 ab?c 匹配字符串 ac。...正则表达式处理过程缓慢的一个因素就是回溯操作。其原因就是回溯操作会尝试每一种可能性，这会消耗时间和计算资源，有时它会占用大量时间。回溯有可能产生巨大的负面效应，这被称为灾难性回溯。来看下面的例子。

2.1K5 0

一个正则表达式酿成的惨案…

看到这里，我们基本可以推断，这个正则表达式就是导致 CPU 利用率居高不下的凶手！...其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...例如我本文中存在问题的那个 URL 使用该网站检查后会提示：catastrophic backgracking（灾难性回溯）。 ?...这也给平时写程序的我们一个警醒，遇到正则表达式的时候要注意贪婪模式和回溯问题，否则我们每写的一个表达式都是一个雷。

5622 0

正则表达式和 CPU 100%有什么故事？

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...：catastrophic backgracking（灾难性回溯）。...这也给平时写程序的我们一个警醒，遇到正则表达式的时候要注意贪婪模式和回溯问题，否则我们每写的一个表达式都是一个雷。

1.4K2 0

藏在正则表达式里的陷阱

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...：catastrophic backgracking（灾难性回溯）。...这也给平时写程序的我们一个警醒，遇到正则表达式的时候要注意贪婪模式和回溯问题，否则我们每写的一个表达式都是一个雷。

2K21 1

一个正则表达式引发的血案，让线上CPU100%异常！

其实这里导致 CPU 使用率高的关键原因就是：Java 正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。...这样就会导致前面匹配了一长串的字符之后，发现不匹配，最后回溯回去。这是这个正则表达式存在的第二个问题。...解决方案明白了回溯是导致问题的原因之后，其实就是减少这种回溯，你会发现如果我在第三部分加上下划线和百分号之后，程序就正常了。...：catastrophic backgracking（灾难性回溯）。...这也给平时写程序的我们一个警醒，遇到正则表达式的时候要注意贪婪模式和回溯问题，否则我们每写的一个表达式都是一个雷。

7311 0

正则表达式也会导致拒绝服务？探讨 ReDos（可能会中招哦）

另一种情况可能是设计不良的正则表达式模式，这可能导致输入验证失败，在正则表达式运算器解析时会消耗大量时间等。有害正则表达式（Evil Regex）有害正则表达式模式是攻击者可以利用的正则表达式。...标记，因此它会回溯到前面的字母，并查看是否有另一种方法来解析先前的字符，以便可以验证整个字符串。在它最终发现绝不会返回 True 之前，这样的回溯将会一直持续下去。如您所知，回溯会导致大量时间消耗。...攻击者可以使用它来利用有害正则表达式模式。 ---- 译者注看完上述内容后，有些读者可能仍对刚才的示例（回溯）表示不解。...他们创建的许多应用程序可能会包含可利用的正则表达式模式。对于有经验的黑客或安全专家来说，正则表达式模式很容易被猜到，而在有些情况下，源代码是可以在线获得的。...攻击者可以利用这一点来谋取利益，并可能降低被攻击者的利益。糟糕的正则表达式模式也可能会导致绕过许多安全控制，无论是在 Web 应用程序还是网络防火墙上。

1.1K3 0

正则表达式的回溯

结果上线之后，发现线上机器时有发生CPU飙到100%的情况，导致整个站点响应异常缓慢。通过dump线程trace，才发现线程全部卡在了这个正则表达式的校验上： ?...在这种情况下，第3步发生不匹配之后，整个匹配流程并没有走完，而是像栈一样，将字符c吐出来，然后去用正则表达式中的c去和文本中的c进行匹配。这样就发生了一次回溯。 4....同贪婪模式一样，独占模式一样会匹配最长。不过在独占模式下，正则表达式尽可能长地去匹配字符串，一旦匹配不成功就会结束匹配而不会回溯。...按照上面说到的NFA引擎贪婪模式，在用户输入一个过长字符串进行匹配时，一旦发生回溯，计算量将是巨大的。后来采用了独占模式，CPU 100%的问题也得到了解决。...因此，在自己写正则表达式的时候，一定不能大意，在实现功能的情况下，还要仔细考虑是否会带来性能隐患。转自：不死码农

1K1 0

maccms v8 80w 字符的 RCE 分析

，利用 80w 长度的垃圾字符填充，使正则回溯次数超过一定限度，导致绕过了360 模块的防御，本文主要介绍了正则回溯以及maccms v8 80w 字符RCE的详细分析。...说回溯前，要先谈一谈正则表达式的引擎，正则引擎主要可以分为基本不同的两大类：一种是DFA（确定型有穷自动机），另一种是NFA（不确定型有穷自动机），NFA 对应的是正则表达式主导的匹配，而 DFA 对应的是文本主导的匹配...NFA则是从正则表达式入手，并且不断读入字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试，在最坏情况下，它的执行速度可能非常慢，但NFA支持更多的特性，因而绝大多数编程场景下，比如 PHP、Java...，导致回溯次数超过了pcre.backtrack_limit的限制，那么就可能绕过这个正则表达式，从而导致绕过 waf 之类的限制。...——匹配所有字符，且只匹配一次但是这句话中开起来非贪婪模式，导致这段正则不断回溯，如我定义一个文本为：UNION(panda)SELECT 其匹配过程大致如下：首先匹配到UNION 进入子表达式检测

6873 0

终于可以彻底告别手写正则表达式了

可以彻底告别手写正则表达式了这篇文章的目的是让你能得到完美的正则表达式，而且还不用自己拼。...后来才知道，那是因为正则写的不合理，发生了回溯现象，越不合理，回溯越严重，加上当时的 PDF 内容很多，所以导致开发工具都卡了，这要是整到线上，那怕是混不下去了。...关于回溯的问题，可以参考下面这篇文章《失控的正则表达式：灾难性的回溯》 https://www.regular-expressions.info/catastrophic.html 后来就不至于那么菜了...，知道了一些关于正则表达式的在线网站，上面有一些常用的正则表达式，不用自己捣鼓了，能偷懒当然要偷懒了。...如果你写的正则在工作的时候发生了明显的回溯，这里也会给出提示，告诉你问题，让你去优化。总结君子善假于物也，虽然我很菜，但是工具好用啊，我+好用的工具，等于我也很厉害了。

3605 0

一文带你读懂：Google 和 JDK 的正则表达式引擎有何不同

经过一顿排查，原因竟然是：开发人员选择了不同的正则表达式引擎，导致了用户使用上的体验差异。...JDK 的 Regex 正则表达式引擎 Java 的标准正则表达式包java.util.regex，以及许多其他广泛使用的正则表达式包，如 PCRE、Perl 和 Python，都使用回溯实现策略：当一个模式呈现两个备选方案...当接受来自不受信任的源（如 web 应用程序的用户）的正则表达式模式时，这会产生安全风险。...在最坏的情况下，java.util.regex匹配器可能永远运行，或者超过可用堆栈空间而失败；这在 RE2/J 中永远不会发生。...务必确保所有的模块都使用同一个技术栈，避免因为引擎选择不同，而导致的功能性兼容问题。

1.4K3 0

一文掌握开发利器：正则表达式

回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案在尝试了所有可能的分步方法后宣告该问题没有答案在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算...; // => ["12345", "123", "45", index: 0, input: "12345"] 3.3.2 惰性量词贪婪是导致回溯的重要原因，那我们尽量以懒惰匹配的方式去匹配文本，是否就能避免回溯了呢...:) 5.3 分支优化分支也是导致正则回溯的重要原因，所以，针对正则分支，我们也需要作出必要的优化。 5.3.1 减少分支数量首先，需要减少分支数量。...我们会发现第一个正则的执行步骤比第一个正则多两步，那是因为第一个正则的回溯路径比第二个正则的回溯路径更长了，最终导致执行步骤变长。 5.4 锚点优化在能使用锚点的情况下尽量使用锚点。...结语曾经有一次因为写一个性能恶劣的正则表达式，导致代码执行过程因为性能问题挂掉。

Java性能调优--代码篇：优化正则表达式的匹配效率

）: ef{1,3}g 贪婪模式是正则表达式的默认匹配方式，在该模式下，对于涉及数量的表达式，正则表达式会尽量匹配更多的内容，我用模型图来演示一下匹配逻辑 ?...关于回溯机制回溯是造成正则表达式效率问题的根本原因，每次匹配失败，都需要将之前比对过的数据复位且指针调回到数据的上一位置，想要优化正则表达式的匹配效率，减少回溯是关键。...3、独占模式（Possessive）: ef{1,3}+g 独占模式应该算是贪婪模式的一种变种，它同样会尽量匹配更多的内容，区别在于在匹配失败的情况下不会触发回溯机制，而是继续向后判断，所以该模式效率最佳...在了解了三种匹配方式的匹配逻辑之后，给出第一个优化建议 ? 优化建议推荐在使用正则表达式的时候，采用独占模式效率最佳，因为触发回溯的概率最小。 ?...4 总结本篇针对正则表达式的三个点：匹配模式、选择分支、捕获组，分析出了三个优化建议： 1、推荐在使用正则表达式的时候，采用懒惰模式和独占模式效率最佳，因为触发回溯的概率最小。

5.2K1 1

深入正则表达式(3):正则表达式工作引擎流程分析与原理释义

作为正则的使用者也一样，不懂正则引擎原理的情况下，同样可以写出满足需求的正则，但是不知道原理，却很难写出高效且没有隐患的正则。...但是，因为传统的 NFA 回溯，所以它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。...因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现。...因此，POSIX NFA 引擎的速度慢于传统的 NFA 引擎；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索。...《精通正则表达式》书中说POSIX NFA引擎不支持非贪婪模式，很明显JavaScript不是POSIX NFA引擎。

1.8K0 0

正则表达式是如何让你的网页卡住的

这就导致了大部分人对正则表达式其实并不是太了解。在正则表达式出现问题以后也不知道如何去解决。...在这里我们简单介绍一下回溯回溯的原因：正则表达式在匹配的过程中需要往回走重新进行匹配，这就会导致回溯。一般产生回溯的有这么几种情况，一种是分支，一种是量词。...我们可以看看上面两个正则表达式，会议是这个正则比较简单，他其实是很多分支的集合体；引用的这个正则就不同了，他的回溯主要是来源于量词。尤其是[^「]*这种的存在，导致了大量的回溯情况。...反过来说，如果一个正则表达式虽然很长很复杂，但是它能够尽可能的避免回溯。需要匹配的文本也尽可能的清晰，那么这种情况下它的性能其实是很不错的。解决方案遇到这个问题，我们一般会有以下两个解决方案。...同时，还有个规则：在不需要捕获组的情况下，括号尽可能的使用非捕获组（与回溯无）。总体上来说就是：如果一个正则表达式越精确，捕获的元素越少，那么它的性能就会越好。

6401 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭