如何解決ReDOS問題

如何解決ReDOS問題，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)是網(wǎng)站建設(shè)技術(shù)企業(yè)，為成都企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)，網(wǎng)站設(shè)計，網(wǎng)站制作，網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例，為您定制適合企業(yè)的網(wǎng)站。10多年品質(zhì)，值得信賴！

0x01 概述

其實(shí)也是在做一次Code Review項(xiàng)目的時候，發(fā)現(xiàn)了一個ReDos的問題，但是由于惰性，沒記錄一下。最近比較有空了，所以抽個時間記錄一下。

0x02 知識鋪墊

所謂的 ReDOS(Regular expression Denial of Service) 正則表達(dá)式拒絕服務(wù)攻擊。實(shí)際上開發(fā)人員使用了正則表達(dá)式來對用戶輸入的數(shù)據(jù)進(jìn)行有效性校驗(yàn), 當(dāng)編寫校驗(yàn)的正則表達(dá)式存在缺陷或者不嚴(yán)謹(jǐn)時, 攻擊者可以構(gòu)造特殊的字符串來大量消耗服務(wù)器的系統(tǒng)資源，造成服務(wù)器的服務(wù)中斷或停止。
正則表達(dá)式是什么，其實(shí)大家應(yīng)該都知道，或者都用到過，但是這里需要提及一些東西就是正則表達(dá)式的引擎。這里首先涉及到一個概念： 有限狀態(tài)自動機(jī)。

（FSM “finite state machine” 或者FSA “finite state automaton” ）是為研究有限內(nèi)存的計算過程和某些語言類而抽象出的一種計算模型。有限狀態(tài)自動機(jī)擁有有限數(shù)量的狀態(tài)，每個狀態(tài)可以遷移到零個或多個狀態(tài)，輸入字串決定執(zhí)行哪個狀態(tài)的遷移。

而有限狀態(tài)自動機(jī)還可以分成確定與非確定兩種, 非確定有限狀態(tài)自動機(jī)可以轉(zhuǎn)化為確定有限狀態(tài)自動機(jī)。（小聲bb，其實(shí)這不是關(guān)鍵）。關(guān)鍵在于正則表達(dá)式引擎分成兩類：一類稱為DFA（確定性有限狀態(tài)自動機(jī)），另一類稱為NFA（非確定性有限狀態(tài)自動機(jī)）。

兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手里，一個吃下去。DFA捏著文本串去比較正則式，看到一個子正則式，就把可能的匹配串全標(biāo)注出來，然后再看正則式的下一個部分，根據(jù)新的匹配結(jié)果更新標(biāo)注。而NFA是捏著正則式去比文本，吃掉一個字符，就把它跟正則式比較，匹配就記下來：“某年某月某日在某處匹配上了！”，然后接著往下干。一旦不匹配，就把剛吃的這個字符吐出來，一個個的吐，直到回到上一次匹配的地方。

兩個引擎其實(shí)存在本質(zhì)上的差別：

1. DFA對于文本串里的每一個字符只需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字符、吐字符，速度慢，但是特性豐富，所以反而應(yīng)用廣泛，當(dāng)今主要的正則表達(dá)式引擎，如Perl、Ruby、Python的re模塊、Java和.NET的regex庫，都是NFA的。

2. 只有NFA才支持lazy和backreference等特性；

3. NFA急于邀功請賞，所以最左子正則式優(yōu)先匹配成功，因此偶爾會錯過最佳匹配結(jié)果；DFA則是“最長的左子正則式優(yōu)先匹配成功”。

4. NFA缺省采用greedy量詞（見item 4）；

5. NFA可能會陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。

這里引用別人的例子，因?yàn)槲矣X得舉的很好。

現(xiàn)在有個文本為： perlmanbook，一個正則表達(dá)式為 /perl|perlman/，而這個正則表達(dá)式在兩種引擎下的匹配結(jié)果我們可以看下。

首先是NFA，它是以正則為導(dǎo)向，怎么說呢，這時候我們手上第一個子正則表達(dá)式為 /perl/，而該引擎針對 perlmanbook字符串進(jìn)行掃描，從左開始，當(dāng)進(jìn)度進(jìn)行到 perl manbook的時候，最開始部分的 perl已經(jīng)和第一個子正則表達(dá)式匹配而上，而當(dāng)引擎進(jìn)度掃描到m字符的時候，發(fā)現(xiàn)與第一個子正則表達(dá)式不匹配，于是把m吐出來，向上匯報說成功匹配 perl，不再關(guān)心其他，也不嘗試第二個子正則式 /perlman/。

若是DFA引擎的情況下，它是以文本為導(dǎo)向，針對正則從左開始進(jìn)行掃描，當(dāng)掃描到 /p/的時候，發(fā)現(xiàn)匹配的上了，然后繼續(xù)往下匹配，當(dāng)將第一個子正則 /perl/全部匹配上之后，這時候就會把這個正則甩開，去吃第二個子正則式的 /p/。這一吃好了，因?yàn)橛制ヅ渖狭耍谑墙又鲁?。直到把正則式吃完，心滿意足往上報告說成功匹配了  'perlman'。

也就是說我們可以總結(jié)一下，NFA引擎要翻來覆去吃字符、吐字符，速度慢，且可能會陷入遞歸險境導(dǎo)致性能極差。因此使用NFA引擎的正則表達(dá)式就可能出現(xiàn) ReDOS的問題了。

0x03 漏洞樣例

目前正則引擎支持的語言種類：

引擎類型	程序
DFA	awk(大多數(shù)版本)、egrep（大多數(shù)版本）、flex、lex、MySQL、Procmail
傳統(tǒng)型 NFA	GNU Emacs、Java、grep（大多數(shù)版本）、less、more、.NET語言、PCRE library、Perl、PHP（所有三套正則庫）、Python、Ruby、set（大多數(shù)版本）、vi
POSIX NFA	mawk、Mortice Lern System's utilities、GUN Emacs（明確指定時使用）
DFA/NFA混合	GNU awk、 GNU grep/egrep、 Tcl

我們來看一個demo。

簡單說明一下這個^(a+)+$正則的作用是什么：

^：匹配輸入字符串的開始位置，也就是說從下面str_list字符串中的最開頭開始匹配。

a：就是字符a，這里不多做說明

+："+"(懶惰)  重復(fù)一次或更多次，例如"aaaaaaaa" 匹配字符串中所有的a。

$：\$會匹配行或字符串的結(jié)尾。

那么我們通過一段代碼進(jìn)行一下驗(yàn)證

根據(jù)Regular Expression Denial of Service這個個PPT里面，總結(jié)了一下：

• 重復(fù)分組構(gòu)造

• 重復(fù)組內(nèi)應(yīng)出現(xiàn)：1.重復(fù)，2.交替重疊

會出現(xiàn)ReDOS的樣例正則表達(dá)式。

1. (a+)+

2. ([a-zA-Z]+)*

3. (a|aa)+

4. (a|a?)+

5. (.*a){x}   | for x > 10

Payload: “aaaaaaaaaaaaaaaaaaX”

當(dāng)然我們也可以使用python的re模塊來驗(yàn)證一下是否存在ReDOS，因?yàn)镻ython的re模塊用的就是NFA的引擎。

該P(yáng)PT中提供了一些業(yè)務(wù)場景下可能存在ReDOS的正則表達(dá)式寫法

下面我們來展示一些實(shí)際業(yè)務(wù)場景中會用到的缺陷正則。

• Person Name:

• Regex: ^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$

• Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• Java Classname

• Regex: ^(([a-z])+.)+[A-Z]([a-z])+$

• Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• Email Validation

• Regex: ^([0-9a-zA-Z]([-.\w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+[a-zA-Z]{2,9})$

• Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

• Multiple Email address validation

• Regex: ^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*\s+&amplt;(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})&ampgt;$|^(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})$

• Payload: aaaaaaaaaaaaaaaaaaaaaaaa!

• Decimal validator

• Regex: ^\d*[0-9](|.\d*[0-9]|)*$

• Payload: 1111111111111111111111111!

• Pattern Matcher

• Regex: ^([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?\.){0,}([a-z0-9]+([\-a-z0-9]*[a-z0-9]+)?){1,63}(\.[a-z0-9]{2,7})+$

• Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

我們可以用下面這段python代碼來輔助驗(yàn)證。

#!/usr/bin/env python
# coding: utf-8

import re
import time

s1 = time.time()
regex = re.compile('^[a-zA-Z]+(([\'\,\.\-][a-zA-Z ])?[a-zA-Z]*)*$')
str='aaaaaaaaaaaaaaaaa!'        
#str='aaaaaaaaaaaaaaaaaaa!'
regex.match(str)
s2=time.time()
print(str)
print(s2-s1)

分別定義

str='aaaaaaaaaaaaaaaaa!'          
str='aaaaaaaaaaaaaaaaaaa!'

最后結(jié)果

aaaaaaaaaaaaaaaaa!
0.0207

aaaaaaaaaaaaaaaaaaa!
0.0776

之前Ph師傅的 code-breaking題目里面就有一題 prefwaf，這題實(shí)際上就涉及到這個問題，首先源碼是這樣的。

<?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);
}

其實(shí)這里很明顯我們要寫入webshell，但是要繞過 is_php函數(shù)中的 /<\?.*[(`;?>].*/is正則表達(dá)式，假設(shè)我們輸入的字符是 <?php phpinfo();//aaaaa，那么這個字符串匹配流程我們看一下這個動圖。

我們看到，到第4步開始由于?.*是貪婪模式匹配，因此抓取到了這個字符串也就是 //aaaaa的末尾，而立實(shí)際上還有部分內(nèi)容是 [(`;?>]等特殊字符，也就是說這部分代碼里面如果存在這些字符就匹配成功，而該NFA引擎的正則表達(dá)式目前沒有找到，因此它從第5步開始回溯，先吐出一個a，輸入變成第5步顯示的//aaaa，但仍然匹配不上正則，繼續(xù)吐出a，變成//aaa，仍然匹配不上……。直到第12步回溯的 ;匹配上了字符 [(`;?>]中的 ;。

然后 第13步又匹配 .*，執(zhí)行貪婪匹配，通過 ;將回溯源 <?php phpinfo();全部抓了出來，并返回匹配成功。

PHP為了防止正則表達(dá)式的拒絕服務(wù)攻擊（reDOS），給pcre設(shè)定了一個回溯次數(shù)上限pcre.backtrack_limit。我們可以通過var_dump(ini_get('pcre.backtrack_limit'));的方式查看當(dāng)前環(huán)境下的上限。

這里的回溯上限是1000000，也就是說我們看看超過回溯上限的執(zhí)行結(jié)果。

php > var_dump(preg_match('/<\?.*[(`;?>].*/is','<?php phpinfo();//'.str_repeat('a',1000000)));
bool(false)

preg_match返回的非1和0，而是false。preg_match函數(shù)返回false表示此次執(zhí)行失敗了，我們可以調(diào)用var_dump(preg_last_error() === PREG_BACKTRACK_LIMIT_ERROR);，發(fā)現(xiàn)失敗的原因的確是回溯次數(shù)超出了限制。

這里修復(fù)的話，php.net針對這個函數(shù)提及到了修復(fù)建議。

如果用preg_match對字符串進(jìn)行匹配，一定要使用===全等號來判斷返回值，如：

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

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

這樣，即使正則執(zhí)行失敗返回false，也不會進(jìn)入if語句。

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

當(dāng)前文章：如何解決ReDOS問題
分享路徑：http://bm7419.com/article28/igehcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、定制網(wǎng)站、ChatGPT、營銷型網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)