来聊聊正则表达式的回溯陷阱

最近有关注到一些朋友因为正则表达式的原因导致cpu持续飙高的问题,通过dump java进程,发现主要卡在一段正则表达式的代码上,其实这有可能就是遇到了正则表达式的回溯陷阱了。
这个问题遇到的人会比较错愕,没遇到的听到这个结果可能不敢相信。下面我们就来详细分析一下怎么一个正则表达式就会导致cpu飙高了。

正则引擎

正则表达式,其实其实是一种字符串的匹配语法。通过一个算法来解析这个正则表达式从而检验出一个给定的字符串是否能够匹配这个正则表达式。而这个算法,其实就是正则引擎了。
正则引擎有两类,一类是DFA(确定型有穷自动机),一类是NFA(不确定型有穷自动机)。简单的解释就是DFA是纯文本主导的匹配,每个字符只会进行一次匹配;而NFA是正则表达式主导的匹配,对于匹配失败的字符会做吐出(也就是回溯)处理,并且NFA支持更复杂的特性。
举个简单的例子,对于字符串“after tonight”,如果正则表达式为“to”的话。DFA匹配,再匹配到第一个t的时候,继续匹配,发现e与o不相等、匹配失败,那么则会继续从r开始进行后面的匹配。当再次匹配到t的时候,开始匹配后面的字符发现o与o匹配一致,匹配成功,到此完成。NFA匹配,同样的匹配到第一个t的时候,继续匹配发现e与o不等,则需要回溯,也就是吧e回吐,从e开始,重新找t,所以此时e这个字符被匹配了两次,后面的部分就和DFA一样了。
由于DFA没有回溯这个操作,所以DFA的性能是好于NFA的,但是由于DFA过于简单,所以一般语言的实现都是基于NFA实现的正则表达式。

正则表达式的回溯

现在我们来正式认识一下回溯。以字符串“abbc”为例,正则表达式为“ab{1,3}c”,再匹配的时候,a、b、b,匹配完成,这时候,正则表达式会继续用c和b进行比较,发现不符合,这时候就会产生回溯,也就是重新用c继续和正则表达式中的c进行比较,发现匹配成功,后续没有需要匹配的字符,完成匹配。
我再把例子变一下,假设正则表达式还是“ab{1,3}c”,但是字符串变为“abbabc”,这时候,还是和上面一样,只不过再匹配到a、b、b后,匹配a发现与b(因为b可以是1到3个)不符合,这时候产生回溯一位,a继续与c比较,发现仍不匹配,这时候会直接回溯到最前面,即字符串中的第二个字符b再重新与正则表达式开始匹配,这时候的回溯位数就比较多了。

正则表达式的贪婪、懒惰和独占

上面举的例子,为什么已经匹配到b了,还要继续匹配b而不是直接匹配c了呢,这就是因为正则匹配默认是贪婪模式,也就是希望尽可能多的去匹配字符,所以正则表达式中写的b的个数为1到3个,那么它就会尽可能取匹配3个,不行才是2个,再不行才是1个。
懒惰模式,就是尽可能少的匹配字符,所以上面那个例子会从1个b尝试,然后那c取匹配第二个字符,发现c与b不匹配,则回溯一位,用b{1,3}里的第二个b去匹配,然后接着再用c去匹配后面的字符。关键符号是“?”,即正则表达式变为“ab{1,3}?c”
独占模式,正则表达式会尽可能长的进行匹配,一旦匹配错误也不会进行回溯。上面的例子来说,再b{1,3}这部分的时候,他会一次把后面最多3个b拿出来,但是后面只有两个b了,所以它也只能拿两个,结束后再进行c的比较,匹配成功。关键符号是“+”,即“ab{1,3}+c”。这里举个例子,如果正则表达式变为“ab{1,3}+bc”,这里正则表达式的区别是后面多了个b,由于独占模式b{1,3}的部分会尽可能多的匹配,所以b{1,3}会把文本中的两个b都匹配了,则后面继续匹配,b不等于c,由于独占模式也不回溯,所以匹配失败了。(这里如果没有“+”号的话,是会产生回溯可以匹配成功的)

总结

这里推荐一个验证正则表达式的网站:https://regex101.com/,他除了可以检查正则表达式的正确性以外,还能给出匹配步数,并且可以解析出正则表达式的解析步骤(右上角的EXPLANATION),还有更详细的匹配过程(左下角的regex debugger),非常好用。
最后还是给大家举个可能产生回溯陷阱的例子更容易理解吧。一般很多正则都会产生回溯,可能有个几十几百的步数还算正常,但是会产生回溯陷阱的一般都是无法匹配出来的,步数可能上完甚至几十万。正则表达式为“^(([a-zA-Z0-9]+).)+$”,字符串我就随便粘了一段比较长的网址,检测的就是字符串中是否是xxxx~xxxx|这种形式,就是一段[a-zA-Z0-9]字符串中间都要只有一个非[a-zA-Z0-9]的字符,如果有连续两个非[a-zA-Z0-9]的字符的话则匹配失败。(字符串举例“abcdekibana.xxxx.com/app/kibana#/discover/6530ca70-7467-11e8-8473-d1a78e1cb8f0?_g=(refreshInterval:('$$hashKey':'object:6533',display:Off,pause:!f,section:0,value:0),time:(from:now%2Fd,mode:quick,to:now%2Fd))&_a=(columns:!(vfdg,khg,tery,fgdg,fgdfs),filters:!(),index:fghyu98-6f97-11e8-be20-871a42a4e49a,interval:auto,query:(language:lucene,query:'dfgr:fjsdiouion7ee3%3D%3D'),sort:!('@timestamp',desc))”)
通过上面提到的验证网站,会发现产生“Catastrophic Backtracking”提示,点开regex debugger就能看到回溯情况了。
其实正则表达式大家用的很多了,一般用来检验用户名、邮箱、包含字符、url合法等。尤其是对于复杂的正则表达式来说一定要注意到使用的场景与具体回溯情况,如果会产生频繁回溯的正则表达式,那么就会掉入回溯陷阱,导致cpu飙高,严重回溯陷阱可能需要占用非常多的cpu时间,导致进程因为正则验证而假死,这点需要格外注意。

©原创文章,转载请注明来源: 赵伊凡's Blog
©本文链接地址: 来聊聊正则表达式的回溯陷阱

发表评论

电子邮件地址不会被公开。 必填项已用*标注