深度分析正则(pcre)最大回溯/递归限制

深度分析正则（pcre）最大回溯/递归限制

正则表达式是一种描述字符模式的工具，由于其强大的表达能力和广泛的应用场景，成为了数据分析、文本挖掘等领域的重要工具。正则表达式引擎可以进行的匹配步骤是有限的，当模式中包含递归或回溯时，引擎可能会一直重复步骤，导致匹配效率降低，甚至出现崩溃等问题。

为了避免这种状况，正则表达式引擎实现了最大回溯/递归限制，即“PCRE recursion limit”和“PCRE backtracking limit”参数。

PCRE为Perl Compatible Regular Expressions（Perl兼容正则表达式），是一个库，由C语言编写。

PCRE Recursion Limit

PCRE Recursion Limit用来限制正则表达式中递归调用的深度，避免无限递归，消耗过多的系统资源并导致应用程序崩溃。缺省值是100000，也就是说当递归调用次数达到100000时程序会停止运行。

PCRE回溯限制

PCRE Backtracking limit用来限制正则表达式的回溯操作的深度，避免重复回溯而导致性能问题和运行程序崩溃。缺省值是1000000，也就是达到1000000次回溯时程序会停止运行。

当超过限制时，PCRE将会返回一个错误：PCRE_ERROR_RECURSIONLIMIT 或 PCRE_ERROR_BACKTRACKLIMIT。通过在调用编译/匹配函数时提供合适的限制，可以避免由于正则表达式中过多的递归或过多的回溯，导致应用程序无响应或崩溃等问题。

示例

假设我们要查找字符串“a”重复出现的字符串，“a”重复的次数不确定，可以使用“/a+ /”正则表达式。

当a的数目比较小的时候，该正则表达式可以很快的匹配成功。然而，当a的数目变大时，匹配就会花费更多的时间。这是因为正则表达式引擎在执行回溯过程中，不断的试图寻找更多的匹配结果。这就是“回溯/递归”错误/问题。

可以通过限制匹配的递归深度和回溯深度来解决这个问题。

下面是一个具体的例子。我们的目标是在由三组 a 组成，中间由连字符 - 分割的字符串中查找匹配串。

$input = 'aaa-bbbbb-aaaaaaa';
echo preg_match('/((a+)+)-((a+)+)-((a+)+)/', $input);  // 输出1

//增加限制
echo preg_match('/((a+){1,' . ini_get("pcre.recursion_limit") . '})-((a+){1,' . ini_get("pcre.recursion_limit") . '})-((a+){1,' . ini_get("pcre.recursion_limit") . '})/', $input); // 输出1

//触发回溯限制
$input = 'aaaaaaaaaaaaaaaaaaaaaa-x';
echo preg_match('/((a+)+)-x/', $input); // 出现回溯错误

//增加限制
echo preg_match('/((a+){1,' . ini_get("pcre.backtrack_limit") . '})+-x/', $input); // 处理正常

上面的这个例子是PHP实现的，但其他语言的实现也会有同样的问题和限制。在编写正则表达式时，应该谨慎地使用回溯和递归，以避免漏洞和性能问题。