详解PCRE正则匹配的引擎、回溯、贪婪问题

阅读量    224383 |

分享到: QQ空间 新浪微博 微信 QQ facebook twitter

 

前言:

本篇文章字数较多,并且有大量篇幅讲解正则匹配的过程,如果有疏忽(字母标错),请多多海涵~

本文重点研究PCRE的正则匹配,并且使用PHP代码进行相关阐述。

 

正则匹配的两种引擎:

对于人来说,想要比较一个字符串是否满足某一个条件,通常是对字符串和条件反复比较,这其中并没有一定的规则,通常随着人的心情波动。而对于正则匹配,其存在的意义同样也是比较一个字符串是否满足某一个条件,但是对于机器语言来说,必须满足一定的规则,不能模棱两可。

因此在比较字符串是否满足某一条件时,就存在两种比较方法:NFA(确定型有穷自动机)、DFA(不确定型有穷自动机)。说白了就是:以正则表达式主导还是以字符串主导

NFA

首先对于PHP语言来说,正则匹配往往采用的是PCRE的模式,而PCRE采用的正是NFA的引擎。对于NFA来说,通俗的讲就是以正则表达式主导。接下来就给出一个正则表达式以及一个待匹配字符串进行阐述。

text = 'after tonight' 
regex = 'to(nite|nighta|night)'

对于NFA来说,以正则表达式主导,也就是拿着正则表达式去比较待匹配字符串。匹配的过程如下:

  • 最开始,正则拿出t字符与待匹配字符串中的a进行匹配,匹配失败
  • 然后同理匹配f也失败,直到匹配到f后面的t字符
  • 这个时候正则会拿出第二个字符o进行匹配,然而oe字符不一样,匹配失败,这个时候正则表达式回溯到第一个字符t
  • 因为上方匹配失败,接下去匹配下一个t字符,直到匹配到空格后面的t字符
  • 同理,这个时候正则拿出第二个字符o进行匹配,发现与上一步匹配到的o字符一样,匹配成功
  • 接着匹配后面三个待匹配字符,依次类推

通过这一个示例,我们大概可以从中理解NFA引擎是怎么个运作方式了。

接下来我们研究DFA匹配引擎。

DFA

对于DFA引擎来说,就是以字符串主导的匹配模式,接下来还是用上方的这一个例子来描述DFA引擎的匹配过程是怎么样的。

text = 'after tonight'
regex = 'to(nite|nighta|night)'

同样的还是这一个例子,对于DFA引擎,匹配过程如下:

  • 最开始,待匹配字符串拿出第一个字符a来与正则的第一个字符t匹配,匹配失败
  • 匹配失败后,待匹配字符串拿出第二个字符f与正则的第一个字符t匹配,匹配失败
  • 匹配失败后,待匹配字符串拿出第三个字符t与正则的第一个字符t匹配,匹配成功
  • 此时待匹配字符串拿出第四个字符e与正则的第二个字符o进行匹配,匹配失败,正则回溯t
  • 同理,直到待匹配字符串拿出空格后面的t字符匹配时,才匹配成功
  • 同理o也匹配成功
  • 匹配成功后待匹配字符串就会拿出n与正则中的三项可选匹配进行并行匹配
  • 以此类推

同样通过这一个示例,也大致能了解DFA引擎的运作方式。

接下来分析NFADFA这两者的异同。

异同

很明显,NFA引擎以正则表达式主导DFA引擎以字符串主导,这其实就是这两者最大的不同点。对于初学正则表达式的人来说(我也是),往往不会在乎他们的引擎到底是什么,差距在哪,通常都会用人最通常的思维去衡量正则表达式,也就是说能匹配到就好了,能满足业务逻辑即可,但是对于程序来说,必须要给它指明一个方向,到底以什么参数主导,必须选一个,不能不选,也不能都选。(上升到哲学问题了。

除此之外,还有一个不同点就是:NFA引擎对于待匹配字符串中的某个字符可能会产生多次匹配,而DFA引擎对于待匹配字符串只会遍历一次。因此DFA的匹配与正则表达式无关,而NFA的匹配与正则表达式有关。

相比找不同,往往人们并不会关注相同点,而这片文章后续要研究的正则匹配回溯问题,其实这个问题就出现在人们会忽略的正则表达式回溯问题上。

可以看到,无论是哪一种引擎,对于正则表达式而言,都会产生回溯,而在数据结构中,产生回溯其实是一件很危险的事,因为如果产生的回溯过多,就会造成栈溢出,爆栈等等,造成业务系统卡顿。因此接下来的篇幅就会着重探讨回溯的问题。

 

回溯:

虽然前面的示例中已经出现了回溯问题,但是不够明显,不够直观。因此这里再用一个示例来看一下回溯的过程。

假设我们这个时候有一个正则表达式如下:

ab{1,3}c

很明显,上方的正则表达式是需要匹配abc,其中b可以出现1-3

情况1

当我们的待匹配字符串为abbbc时,很正常,全程一次就匹配成功,没有产生回溯。

情况2

当我们的待匹配字符串为abc时,我们来看看这一个匹配过程是怎样的:

正则表达式 待匹配字符串 备注
1 a a
2 ab ab
3 ab{1,3}b abc 匹配不成功,回溯
4 ab{1,3} ab
5 ab{1,3}c abc

可以看到,在第三步的时候出现了回溯。

但是这个时候,就会有个问题,既然第2步已经匹配到了一个b,为啥这个正则表达式这么贪心,匹配一个就够了呀,直接匹配c不就好了,还想着去匹配第2个b,不匹配第2个b不就不回溯了嘛。

这个问题就涉及到正则表达式匹配的贪婪模式以及非贪婪模式

 

贪婪模式与非贪婪模式:

对于PCRE,其中有4个比较常用的元字符:

  • *匹配前面的子表达式零次或多次
  • + 匹配前面的子表达式一次或多次
  • ?匹配前面的子表达式零次或一次
  • {n,m}匹配前面的子表达式n-m次,{n,}匹配前面的子表达式至少n次,{n}匹配前面的子表达式n

贪婪模式

对于待匹配字符串abbbc,有如下正则表达式:

/ab{2,3}+bc/

整一个匹配过程如下:

正则表达式 待匹配字符串 备注
1 a a
2 ab{2,3}+ ab
3 ab{2,3}+ abb 贪婪模式继续匹配
4 ab{2,3}+ abbb 贪婪模式继续匹配
5 ab{2,3}+b abbbc 正则需要b,但是待匹配字符串没有b,匹配结束

可以看到,整一个过程中因为是贪婪模式,所以正则表达式第1个b就已经把待匹配字符串中的3个b吞掉了,而正则表达式第2个b就没得匹配了,所以在这个匹配过程中,匹配不到任何字符。

非贪婪模式

同样的还是一样的字符串abbbc,但是不一样的正则表达式。

/ab{2,3}?bc/
正则表达式 待匹配字符串 备注
1 a a
2 ab{2,3}? ab
3 ab{2,3}? abb 匹配了两个b,非贪婪,见好就收,下面不匹配
4 ab{2,3}?b abbb 成功匹配b
5 ab{2,3}?bc abbbc 成功匹配整个字符串

在非贪婪模式下,成功匹配整个字符串,在正则表达式测试网站上结果如下:

 

贪婪、回溯问题引发的漏洞:

上面的篇幅主要探讨了两个方面的东西:贪婪回溯。试想一下,如果将这两者结合在一起是否会产生漏洞。

首先,在PHP中,对正则表达式回溯问题有做防备,在php.ini中有下方两个设置:

pcre.backtrack_limit //最大回溯数
pcre.recursion_limit //最大嵌套数

其中默认情况下,pcre.backtrack_limit的值为100000,那如果我们超过这个值的时候,正则函数会返回什么呢?

问题

假设我们有以下代码:

<?php
$a = $_POST["a"];
if(preg_match('/.+?Lxxx/i', $a)){
    die('no!');
}
if(stripos($a,"ttLxxx")===FALSE){
    die("no!!");
}
echo "Yes!";

上方代码正则不允许Lxxx前面有字母,但是又需要字符串中包含ttLxxx

在这一段代码,如何才能让程序输出Yes?

分析

既然正则不允许,并且正则前面是.+?的非贪婪匹配,所以我们可以添加足够多的字母造成回溯。

假设我们传入ttLxxx,由于是非贪婪匹配,.+?匹配到字符t的时候,并不会很贪心地把字符t拿走,而会留给后面的字符L,但是t没办法匹配L,导致一次回溯,同理,第2个t也会造成回溯,由此可见,只要我们拥有足够多的t,就会造成足够多次的回溯。当回溯达到我们php.ini中的设置时,正则就会返回false

所以我们生成足够多的字符POST传给a

<?php
$a = str_repeat("tian",250000);
$a .= "ttLxxx";
echo $a;

将生成的字符传给a,程序就输出Yes。

分享到: QQ空间 新浪微博 微信 QQ facebook twitter
|推荐阅读
|发表评论
|评论列表
加载更多