php 正则 回溯,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语言的限制。

相关