正则与PCRE回溯

正则表达式

PHP利用PCRE回溯次数限制绕过

起源

20世纪40年代：正则表达式最初的想法来自两位神经学家：沃尔特·皮茨与麦卡洛克，他们研究出了一种用数学方式来描述神经网络的模型。

1956年：一位名叫Stephen Kleene的数学科学家发表了一篇题目是《神经网事件的表示法》的论文，利用称之为正则集合的数学符号来描述此模型，引入了正则表达式的概念。正则表达式被作为用来描述其称之为“正则集的代数”的一种表达式，因而采用了“正则表达式”这个术语。

1968年：C语言之父、UNIX之父肯·汤普森把这个“正则表达式”的理论成果用于做一些搜索算法的研究，他描述了一种正则表达式的编译器，于是出现了应该算是最早的正则表达式的编译器qed（这也就成为后来的grep编辑器）。

Unix使用正则之后，正则表达式不断的发展壮大，然后大规模应用于各种领域，根据这些领域各自的条件需要，又发展出了许多版本的正则表达式，出现了许多的分支。我们把这些分支叫做“流派”。

1987年：Perl语言诞生了，它综合了其他的语言，用正则表达式作为基础，开创了一个新的流派，Perl流派。之后很多编程语言如：Python、Java、Ruby、.Net、PHP等等在设计正则式支持的时候都参考Perl正则表达式。

到这里我们也就知道为什么众多编程语言的正则表达式基本一样，因为他们都师从Perl。

执行过程:由正则表达引擎编译执行,可以有预编译

引擎:

解释下确定型、有穷、自动机这几个名词：

确定型与非确定型：假设有一个字符串（text=abc）需要匹配，在没有编写正则表达式的前提下，就直接可以确定字符匹配顺序的就是确定型，不能确定字符匹配顺序的则为非确定型。
有穷：有穷即表示有限的意思，这里表示有限次数内能得到结果。
自动机：自动机便是自动完成，在我们设置好匹配规则后由引擎自动完成，不需要人为干预！

DFA文本主导,按照文本的顺序执行

NFA表达式主导,按照表达式的一部分执行，如果不匹配换其他部分继续匹配，直到表达式匹配完成。

绝大多数编程语言都选择NFA引擎,因为更灵活些.

当某个正则分支匹配不成功之后，文本的位置需要回退，然后换另一个分支匹配，而回退这步专业术语就叫：回溯。

回溯陷阱：

举个例子：text=aaaaa，pattern=/^(a*)b$/，匹配过程大致是

引擎会要求*匹配的东西一点一点吐回，我们假设如果文本长度为几万，那引擎就要回溯几万次，这对机器的CPU来说简直是灾难。

这就是回溯陷阱

PHP为了防止正则表达式的拒绝服务攻击（reDOS），给pcre设定了一个回溯次数上限pcre.backtrack_limit。我们可以通过var_dump(ini_get('pcre.backtrack_limit'));的方式查看当前环境下的上限

可见，回溯次数上限默认是100万。那么，假设我们的回溯次数超过了100万,那么preg_match返回的不是1和0，而是false。

eg:放进xunt里面了,题目名PCRE

如果用preg_match对字符串进行匹配，一定要使用===全等号来判断返回值

function is_php($data){  
    return preg_match('/<\?.*[(`;?>].*/is', $data);  
}

if(is_php($input) === 0) {
    // fwrite($f, $input); ...
}

参考