Web應用中的ReDoS檢測方法研究

梁興開，趙澤茂，黃 亮

(杭州電子科技大學通信工程學院，浙江杭州310018)

0 引言

正則表達式大量應用于Web應用中，其在表單數(shù)據(jù)校驗、替換和文本處理中發(fā)揮靈活而又強大的功能［1］。而拒絕服務(wù)攻擊通過向目標發(fā)送大量的攻擊數(shù)據(jù)包來消耗目標的資源，這類攻擊通常被稱為數(shù)據(jù)包洪泛攻擊。由于不合理的正則表達式語句大量部署于Web應用中，這將可能引入一種新型的拒絕服務(wù)攻擊－正則表達式拒絕服務(wù)攻擊(Regular Expression Deny of Service，ReDoS)［3］。由于采用不嚴謹?shù)恼齽t表達式而對其可能造成的危害了解甚少，開發(fā)者無法對Web應用中構(gòu)建的正則表達式語句進行安全驗證，不輕易間就可能導致系統(tǒng)受到拒絕服務(wù)攻擊。因此，研究一種能夠有效檢測和抵御ReDoS攻擊的檢測模型是迫切的現(xiàn)實需要，本文提出了一種基于靜態(tài)代碼分析與滲透測試技術(shù)的防御ReDoS模型。

1 相關(guān)背景

正則表達式描述一種字符串匹配模式，一般其運用于兩種情況:一種是在文本或字符串中查找特定的子串(搜索、匹配);另一種是查找符合特定條件的子串并編輯子串(替換、校驗)。

1.1 正則表達式設(shè)計

正則表達式的語法由基本的元字符、數(shù)量和位置元字符、特殊元字符以及一些條件模式字符構(gòu)成。具體的語法要點可參考文獻1。Web應用中一般需要校驗電子郵件的合法性，可以構(gòu)建如下的正則表達式:w+(［－ +.′］w+)*@w+(［－.］w+)*.w+(［－.］w+)* 。這個模式使用的嵌套子表達式模式。

1.2 ReDoS 攻擊原理

正則表達式匹配技術(shù)主要有基于非確定性有限狀態(tài)機(Nondeterministic Finite Automaton，NFA)的技術(shù)、基于確定性有限狀態(tài)機(Deterministic Finite Automaton，DFA)的匹配技術(shù)、基于NFA和DFA的混合技術(shù)［4－6］。許多Web開發(fā)環(huán)境都是基于NFA實現(xiàn)正則表達式的?；贜FA引擎是回溯引擎，可以處理更復雜的正則表達式，比如前后向引用和捕獲括號的正則表達式等。與對輸入字符串中的每個字符最多計算一次的DFA不同，NFA跳轉(zhuǎn)到新的狀態(tài)并對輸入字符串中的字符計算多次，直到所有的輸入符號都消費完。它檢驗每一個可能的路徑直到它到達可接受的狀態(tài)(成功匹配)或者檢驗完所有的路徑(匹配失敗)。這意味著必須對所有路徑進行測試?；厮莸囊粋€負面影響是，雖然正則表達式可以快速地確定正向匹配(輸入字符串與給定正則表達式匹配)，但確定反向匹配(輸入字符串與正則表達式不匹配)所需的時間更長。這將導致正則表達式引擎的執(zhí)行計算量呈現(xiàn)指數(shù)增加。攻擊者只需提供簡單的構(gòu)造好的語句就可強制NFA引擎對所有可能的大量的路徑進行匹配嘗試直到不成功匹配，即可造成ReDoS攻擊。

通過分析發(fā)現(xiàn)，不嚴謹?shù)恼齽t表達式一般包含以下兩個要點:(1)包含重復捕獲分組;(2)在重復捕獲分組中包含替換或者重復匹配現(xiàn)象。而這兩個要點也是防范ReDos攻擊的檢測模型中的靜態(tài)分析模塊的核心。其執(zhí)行的路徑復雜度就由引擎的路徑匹配時間來表示并將消耗的匹配時間作為滲透測試模塊中的一個判決條件。

2 ReDoS攻擊的檢測模型

構(gòu)造完全健壯的正則表達式是比較困難的。一個原因是目前還沒有合適的工具來驗證開發(fā)者使用的正則表達式的嚴謹性。因此，本文構(gòu)建一個安全的檢測模型，由靜態(tài)分析模塊和滲透測試模塊兩部分構(gòu)成。靜態(tài)測試模塊主要完成對可疑式子的定義和Web源代碼的分析，并提取網(wǎng)頁源代碼中的正則表達式。滲透測試模塊主要完成對靜態(tài)模塊獲取到的正則表達式進行模糊測試并給出相應的防護措施。模型如圖1所示。

圖1 ReDoS檢測模型

2.1 ReDoS靜態(tài)分析模塊

靜態(tài)分析模塊主要負責抓取網(wǎng)頁源代碼中所有的正則表達式，并依據(jù)可疑特征庫來提取所有可疑正則表達式集合。此模塊的關(guān)鍵部分是對可疑正則表達式的定義，因為其提取到的正則表達式集準確與否將直接影響測試模塊。為了減少漏報，本模塊將可疑正則表達式定義成如下:任何包含重復分組或者替換的正則表達式R稱為可疑表達式，標記為Rs。Web源代碼中的正則表達式一般都會包含特定的字符(比如“+”、“*”、“?”)，靜態(tài)分析模塊只需提取并篩選出所有可疑的正則表達式Rs，整合成可疑正則表達式集Rs－。

2.2 ReDoS 測試模塊

測試模塊中用到的關(guān)鍵的符號和數(shù)據(jù)如下:Tout為滲透測試中匹配測試設(shè)定的時間閥;T為對Rs進行匹配測試所消耗的時間。人工測試庫:在模塊中人工的自定義一些攻擊測試用例，能夠比較快速而有針對性的對可疑正則表達式Rs進行測試。將數(shù)字、字母和一些常見的特殊字符組合成人工的測試數(shù)據(jù)。隨機測試庫:用于產(chǎn)生大量的隨機測試數(shù)據(jù)，對可疑正則表達式集合Rs－進行模糊測試。測試數(shù)據(jù)主要為隨機的數(shù)字、字符或兩者的組合等。攻擊字符庫:將攻擊字符疊加到隨機產(chǎn)生的測試數(shù)據(jù)之后，在反向匹配測試進行盡可能多的模糊測試。字符庫包含數(shù)字、字母、標點符號、特殊符號和非可打印的ASICC字符等。

滲透測試模塊的功能是對正則表達式集Rs－進行模糊測試，驗證其嚴謹性，評判Rs是否容易導致拒絕服務(wù)攻擊。此模塊的一個判決因素是反向匹配時間T。如果正則表達式不能在特定的時間內(nèi)完成匹配，即可被認定為不嚴謹?shù)恼齽t表達式。本模塊設(shè)定Tout為1s。模塊提供測試數(shù)據(jù)來計算反向匹配時間，并以此作為Rs的嚴謹性判決依據(jù)。測試分為2步:第1步是人工提供的測試數(shù)據(jù)，用于更快捷的檢測可疑正則表達式Rs;第2步是機器自動化的模糊測試。自動化模糊測試需要隨機產(chǎn)生大量的測試數(shù)據(jù)。如果提供的測試數(shù)據(jù)的開始部分就包含不符合正則表達式的匹配項，NFA引擎可以很容易的搜索完路徑而直接拒絕測試數(shù)據(jù)，可疑正則表達式Rs就無法得到合理檢測。因此，需人為的在隨機測試數(shù)據(jù)后面疊加上特殊的攻擊字符來組合成一系列的測試用例。滲透測試模塊的具體流程圖如圖2所示。

圖2 測試流程圖

3 實例分析

人工選取了幾個Web應用中常用的正則表達式來進行嚴謹性試驗，待測試的用例來自于開源社區(qū)，測試的度量為正則引擎匹配的時間。在.NET環(huán)境下進行了初步測試，結(jié)果如表1所示。

表1 檢測實例與用時

在軟件測試過程中，程序被隨機產(chǎn)生的數(shù)據(jù)大量驗證，稱為模糊測試。如果程序在應對這類數(shù)據(jù)上失效，開發(fā)者就知道程序某處出現(xiàn)了Bug。本文使用了模糊測試方法來驗證正則表達式的安全性。在數(shù)據(jù)校驗和過濾定義中，所使用的正則表達式必定是常規(guī)的ASCII字符組合，也就是數(shù)字、字母和常用的符號組合。在構(gòu)造和選取測試數(shù)據(jù)時，如果提供地數(shù)據(jù)完全是常規(guī)的ASCII字符，則很容易經(jīng)過正向匹配測試得出不合理的測試結(jié)果。而針對具體的正則式子將常規(guī)字符、特殊字符、非打印ASCII字符等組合成多個測試數(shù)據(jù)，按照模糊測試的思想，通過不斷地反向匹配和迭代測試，最后得出比較合理的測試結(jié)果。

4 結(jié)束語

本文提出了防范正則表達式拒絕服務(wù)攻擊的檢測模型，通過靜態(tài)分析和滲透測試方法對Web應用程序中的正則表達式的嚴謹性進行模糊測試，給出了本模塊的檢測算法和初步的測試數(shù)據(jù)。實例表明，引擎匹配的時間可以作為一個判斷度量，可以通過模糊測試來校驗正則表達式的嚴謹性。在使用正則表達式時需要遵循以下2點:(1)接受已知的合法數(shù)據(jù)，太過嚴格的正則表達式有可能產(chǎn)生誤報;(2)拒絕已知的非法數(shù)據(jù)，太過松散的正則表達式會產(chǎn)生漏報。

［1］ Jeffrey E F.精通正則表達式［M］.北京:電子工業(yè)出版社，2006:143－162.

［2］ Skoudies E d.反擊黑客［M］.北京:機械工業(yè)出版社，2002:120－170.

［3］ Adar Weidman.基于源代碼分析保護應用程序的安全［EB/OL］.http://www.checkmarx.com/NewsDetails.aspx?id=23＆cat=3，2009 －10 －09.

［4］ Yuan M，袁真.構(gòu)造正則表達式的幾種NFA算法分析與比較［J］.計算機科學，2006，33(8):212－214.

［5］ 周啟海.NFA→FA→GFA自動機轉(zhuǎn)換算法［J］.電子科技大學學報，2005，34(3):363－365.

［6］ 徐克付，齊德昱，鄭偉平，等.一種基于Bloom Filter的正則表達式集合快速搜索算法［J］.華南理工大學學報，2009，37(4):37－41.