从一道题看正则最大回溯次数

背景

正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。

开发人员在使用正则时候可能由于疏忽，可能造成业务逻辑异常，或者让正则表达式占用过多 CPU，从而形成拒绝服务攻击。下面从一道题来看下因为正则最大回溯次数造成正则表达式匹配非预期结果。

题目

先看下题目

<?php

error_reporting(0) ;
highlight_file(__FILE__);

$a = $_POST['heizi'];
if (isset($a)) {
    if (substr($a,0,5) == "aikun" and substr($a,-10,10) == "xiaojijiao"){
        if ($a =="aikunxiaojijiao") {
            die (" nononono" ) ;
        }
        if (preg_match('/aikun.+?xiaojijiao/is',$a)){
            die(" Hack!!!") ;
        }
        echo "flag{xxxxx}" ;
    }else{
        die(" what?");
    }
}

题目很简单，就是判断前5个字符为 aikun 和 后10个字符为 xiaojijiao 并且需要绕过 aikunxiaojijiao 和 /aikun.+?xiaojijiao/is 判断。因为正则表达式使用了 is 参数，没办法通过回车等空白字符及大小写绕过。只能通过其他方式获取flag了。

题解

先来看下php 的 preg_match 函数

preg_match(
    string $pattern,
    string $subject,
    array &$matches = null,
    int $flags = 0,
    int $offset = 0
): int|false

返回

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

题意preg_match是匹配到了再返回，则可以通过返回 FALSE 进行绕过。但如何返回False，先来看下正则是如何匹配的。先来看下题目的正则解析树如下：

因为使用的是非贪婪模式，优先匹配"xiaojijiao" 字符，不匹配再进行回溯。回溯过程会造成些许性能消耗，这时候就引入了最大回溯次数限制。可以通过

ini_get('pcre.backtrack_limit');

查看最大回溯次数限制。从帮助文档可以知道，默认回溯次数为 1000000

 以此，此题可以使用如下poc进行bypass

$a = 'aikun'.str_pad("asdr", 10000000, "a").'xiaojijiao';

参考链接：

https://blog.robertelder.org/regular-expression-visualizer/

https://portswigger.net/daily-swig/rust-patches-sneaky-redos-bug