PHP正则匹配绕过

之前没有从机制上去了解过PHP正则匹配绕过具体是怎么一回事,于是主动去网上找了一些资料来加深理解

NFA与正则表达式

常见的正则引擎,被细分为DFA(确定性有限状态自动机)与NFA(非确定性有限状态自动机)。
由于NFA的执行过程存在回溯,所以其性能会劣于DFA,但它支持更多功能。大多数程序语言都使用了NFA作为正则引擎,其中也包括PHP使用的PCRE库。所以这里详细介绍一下NFA(Nondeterministic Finite Automaton),非确定有限状态自动机。

对于正则表达式 ab|ac,对应 NFA 可以是这样的:

可以看到,在状态 1 这里,如果输入 a,其实有两种可能,如果后面的符号是 b,那么可以匹配成功,后面符号是 c 也能匹配成功。所以状态机在执行过程中,可能要尝试所有的可能性。在尝试一种可能路径匹配失败后,还要回到之前的状态再尝试其他的路径,这就是“回溯”。

所以有限状态机的工作过程,就是从起始状态开始,一个字符一个字符地读取输入串,并与正则表达式进行匹配,如果匹配不上,则进行回溯,尝试其他状态。

回溯的具体流程

设正则为<\?.*[(`;?>].*,假设匹配的输入是<?php phpinfo();//aaaaa,执行的流程如下:

分析

① 第4步,第一个.*指可以匹配任何字符,所以最终匹配到输入串的结尾,即//aaaaa
② 第5步,因正则.*后还有字符[(`;?>],NFA开始回溯,一个一个a地吐出
③ 第12步,最终吐出;,此时.*匹配的是<?php phpinfo(),而后面的;匹配上[(`;?>],结果满足正则表达式的要求,于是不再回溯
④ 第13步往后匹配;
⑤ 第14步匹配.*,此处的.*匹配到了字符串末尾,匹配结束

在正则表达式调试的过程中,吐字符的过程就是相当于NFA的回溯,由此得知上面总共回溯了8次,为第5-12步。

对PHP正则的回溯次数限制的利用

PHP为了防止正则表达式的拒绝服务攻击(reDOS),给pcre设定了一个回溯次数上限pcre.backtrack_limit,次数由PHP5.3.7 版本之前默认值为 10万 ,到PHP5.3.7 版本之后默认值为 100万 ,该值可以通过php.ini设置,也可以通过 phpinfo 页面或var_dump(ini_get('pcre.backtrack_limit'));查看。

利用

PHP手册告诉我们, preg_match 函数的返回值有3种,分别为(安全的写法是使用 === 运算符对返回值进行比较,手册推荐用效率更快的 strpos 函数替代 preg_match 函数):

returns 1;      // 如果匹配到.
returns 0;      // 如果未匹配到.
returns FALSE;  // 发生错误时.

假设我们的回溯次数超过了100万,会出现什么现象呢?比如:

php > var_dump(preg_match('/<\?.*[(`;?>].*/is','<?php phpinfo();//'.str_repeat('c',1000000)));

bool(false)

可见,preg_match返回的非1和0,而是false
我们通过上述技巧绕过 preg_match 函数,通过发送超长字符串的方式,使正则执行失败,最后绕过目标对PHP语言的限制。