如何解決ReDOS問題

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

0x01 概述

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

0x02 知識鋪墊

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

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

而有限狀態自動機還可以分成確定與非確定兩種, 非確定有限狀態自動機可以轉化為確定有限狀態自動機。（小聲bb，其實這不是關鍵）。關鍵在于正則表達式引擎分成兩類：一類稱為DFA（確定性有限狀態自動機），另一類稱為NFA（非確定性有限狀態自動機）。

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

兩個引擎其實存在本質上的差別：

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

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

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

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

5. NFA可能會陷入遞歸調用的陷阱而表現得性能極差。

這里引用別人的例子，因為我覺得舉的很好。

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

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

若是DFA引擎的情況下，它是以文本為導向，針對正則從左開始進行掃描，當掃描到 /p/ 的時候，發現匹配的上了，然后繼續往下匹配，當將第一個子正則 /perl/ 全部匹配上之后，這時候就會把這個正則甩開，去吃第二個子正則式的 /p/ 。這一吃好了，因為又匹配上了，于是接著往下吃。直到把正則式吃完，心滿意足往上報告說成功匹配了  'perlman' 。

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

0x03 漏洞樣例

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

我們來看一個demo。

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

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

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

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

$：\$會匹配行或字符串的結尾。

那么我們通過一段代碼進行一下驗證

根據Regular Expression Denial of Service這個個PPT里面，總結了一下：

• 重復分組構造

• 重復組內應出現：1.重復，2.交替重疊

會出現ReDOS的樣例正則表達式。

1. (a+)+

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

3. (a|aa)+

4. (a|a?)+

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

Payload: “aaaaaaaaaaaaaaaaaaX”

當然我們也可以使用python的re模塊來驗證一下是否存在ReDOS，因為Python的re模塊用的就是NFA的引擎。

該PPT中提供了一些業務場景下可能存在ReDOS的正則表達式寫法

下面我們來展示一些實際業務場景中會用到的缺陷正則。

• 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代碼來輔助驗證。

#!/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!'

最后結果

aaaaaaaaaaaaaaaaa!
0.0207

aaaaaaaaaaaaaaaaaaa!
0.0776

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

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

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

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

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

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

這里的回溯上限是1000000，也就是說我們看看超過回溯上限的執行結果。

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

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

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

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

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

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

這樣，即使正則執行失敗返回false，也不會進入if語句。

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。