梁興開，趙澤茂，黃 亮

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

0 引言

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

1 相關(guān)背景

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

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

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

1.2 ReDoS 攻擊原理

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

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

2 ReDoS攻擊的檢測模型

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

圖1 ReDoS檢測模型

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

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

2.2 ReDoS 測試模塊

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

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

圖2 測試流程圖

3 實例分析

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

表1 檢測實例與用時

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

4 結(jié)束語

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

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

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

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

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

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

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