深入正则表达式(5):正则表达式回溯填坑笔记—回溯与非回溯
Author：zhoulujun Date：
大部分编程语言如如java、JavaScript、.net、Perl、Python、Ruby、PHP等正则表达式使用的引擎实现是 NFA 自动机，这种正则表达式引擎在进行字符匹配时会发生回溯（backtracking）。而一旦发生回溯，那其消耗的时间就会变得很长，有可能是几分钟，也有可能是几个小时，时间长短取决于回溯的次数和复杂度。
回溯攻击
只用一台机器，发送一个请求，就可以打跨对方的服务器，这简直就是黑客梦寐以求的核武器。与之相比，什么 DDoS 弱爆了，动静大还花钱多。
这种攻击也有自己的名字：ReDoS (RegEx Denial of Service)。
由于正则表达式应用非常广泛，几乎存在于后端服务的各个部分，所以只要找到其中一个漏洞，就有机可趁。
试想一个场景，黑客发现了 WAF 中存在 ReDoS 漏洞，发送一个请求打垮了 WAF；你无法在短时间内定位这个问题，甚至意识不到这是一次攻击；为了保证业务的正常，你选择重启或者暂时关闭 WAF；在 WAF 失效期间，黑客利用 SQL 注入，拖走了你的数据库。而你，可能还完全蒙在鼓里。
回溯情景
使用“(?>…)”方式进行非回溯声明。由于正则表达式引擎的贪婪特性，导致它在某些情况下，将进行回溯以获得匹配
text="abbc"
reg=/ab{1,3}c/
其实在正则表达式中有这么三种模式：贪婪模式、懒惰模式、独占模式。
？:告诉引擎匹配前导字符0次或一次。事实上是表示前导字符是可选的。
+: 告诉引擎匹配前导字符1次或多次。
*: 告诉引擎匹配前导字符0次或多次。
{min, max}:告诉引擎匹配前导字符min次到max次。如果有逗号而max被省略了，则表示max没有限制；如果逗号和max都被省略了，则表示重复min次。
默认情况下，这个几个特殊字符都是贪婪的，也就是说，它会根据前导字符去匹配尽可能多的内容。
所以关于数量的匹配中，有 + ? * {min,max} 四种情况，如果只是单独使用，那么它们就是贪婪模式。
如果在他们之后加多一个 ? 符号，那么原先的贪婪模式就会变成懒惰模式，即尽可能少地匹配。但是懒惰模式还是会发生回溯现象的。例如下面这个例子：
text="abbc"
regex="ab{1,3}?c"正则表达式的第一个操作符 a 与 字符串第一个字符 a 匹配，匹配成功。于是正则表达式的第二个操作符 b{1,3}? 和 字符串第二个字符 b 匹配，匹配成功。因为最小匹配原则，所以拿正则表达式第三个操作符 c 与字符串第三个字符 b 匹配，发现不匹配。于是回溯回去，拿正则表达式第二个操作符 b{1,3}? 和字符串第三个字符 b 匹配，匹配成功。于是再拿正则表达式第三个操作符 c 与字符串第四个字符 c 匹配，匹配成功。于是结束。
如果在他们之后加多一个 + 符号，那么原先的贪婪模式就会变成独占模式，即尽可能多地匹配，但是不回溯。
于是乎，如果要彻底解决问题，就要在保证功能的同时确保不发生回溯。
regex=ab{1,3}+bc
悲观回溯
这次我们的正则改为 /^(a*)b$/。但是把要匹配的字符串改为 aaaaa。去掉了结尾的字符 b。
让我们看看此时的执行流程：
(a*) 首先匹配了所有 aaaaa。
尝试匹配 b。但是匹配失败。
回溯 1 个字符。此时剩余字符串为 a。依然无法匹配字符 b。
回溯一直进行。直到匹配 0 次的情况。此时剩余字符串为 aaaaa。依然无法匹配 b。
所有的可能性均已尝试过，依然无法匹配。最终导致整体匹配失败。
可以看到，虽然我们可以一眼看出二者无法匹配。但正则表达式在执行时还要“傻傻的”逐一回溯所有可能性，才能确定最终结果。这个“傻傻的”回溯过程就叫悲观回溯。
禁止回溯
既然回溯可能有性能问题，那我们是否可以禁止正则表达式进行回溯呢。
答案是：可以。
有两种语法可以防止回溯：
有限量词（Possessive Quantifiers）
原子分组（Atomic Grouping）
关于这两种语法，感兴趣的同学可以自行 Google。在此不详细解释。因为这两种语法在 JavaScript 中均不被支持。
所以对于我这从java跳到前端的，现在也泪崩逃走算了
回溯/懒惰/独占
把以上三种模式的表达式列出如下
贪婪-默认情况 | 懒惰-加个？ | 独占-加个+ |
|---|---|---|
X? | X?? | X?+ |
X* | X*? | X*+ |
X+ | X+? | X++ |
X{n} | X{n}? | X{n}+ |
X{n,} | X{n,}? | X{n,}+ |
X{n,m} | X{n,m}? | X{n,m}+ |
回溯问题
比如
^[允许字符集]+
该字符集大小约为250，而+号表示至少出现一次。按照上面说到的NFA引擎贪婪模式，在用户输入一个过长字符串进行匹配时，一旦发生回溯，计算量将是巨大的。后来采用了独占模式，CPU 100%的问题也得到了解决。
参考文章：
正则表达式中的悲观回溯 https://loveky.github.io/2017/05/31/regular-expressions-catastrophic-backtracking/
正则表达式回溯漏洞 https://www.cnblogs.com/Eleven-Liu/p/10826488.html
藏在正则表达式里的陷阱 https://www.cnblogs.com/chanshuyi/p/the_regex_backtracking_trap.html
一个由正则表达式引发的血案 https://www.cnblogs.com/study-everyday/p/7426862.html
如何彻底避免正则表达式的灾难性回溯？ https://zhuanlan.zhihu.com/p/44425997
正则表达式里的底层原理是什么 https://www.cnblogs.com/Renyi-Fan/p/9694695.html#_label0_3
转载本站文章《深入正则表达式(5):正则表达式回溯填坑笔记—回溯与非回溯》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/IntroductionAlgorithms/8429.html