[發(fā)明專利]一種正則表達(dá)式DFA空間壓縮方法和系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201910134200.9
• 申請(qǐng)日: 2019-02-22
• 公開（公告）號(hào): CN109977275A
• 公開（公告）日: 2019-07-05
• 發(fā)明（設(shè)計(jì)）人: 高曌;孫毅;張志強(qiáng)
• 申請(qǐng)（專利權(quán)）人: 中國(guó)科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;H04L29/06
• 代理公司: 北京律誠(chéng)同業(yè)知識(shí)產(chǎn)權(quán)代理有限公司 11006
• 代理人: 祁建國(guó);梁揮

本發(fā)明涉及一種正則表達(dá)式DFA空間壓縮方法和系統(tǒng)，包括：對(duì)狀態(tài)轉(zhuǎn)移邊進(jìn)行掃描，讀入轉(zhuǎn)移矩陣，將轉(zhuǎn)移矩陣中每一列的值以字符串形式存儲(chǔ)；將相等的字符串對(duì)應(yīng)的字符表元素合并，得到多個(gè)哈希表；計(jì)算正則表達(dá)式的狀態(tài)機(jī)中兩兩狀態(tài)間的相似度和相似度對(duì)應(yīng)的權(quán)值，通過相似度構(gòu)建相似度矩陣；根據(jù)狀態(tài)機(jī)中各狀態(tài)點(diǎn)的狀態(tài)深度，更新相似度矩陣；從相似度矩陣對(duì)應(yīng)的有向圖中的每個(gè)狀態(tài)節(jié)點(diǎn)開始遍歷，選取狀態(tài)節(jié)點(diǎn)對(duì)應(yīng)的最大相似度轉(zhuǎn)移邊，從而完成默認(rèn)路徑的構(gòu)造，保存默認(rèn)路徑作為最大生成樹，以找到默認(rèn)路徑的相似度對(duì)應(yīng)的權(quán)值以及對(duì)應(yīng)的哈希表，刪除在邊壓縮前DFA中的狀態(tài)轉(zhuǎn)移邊，并在刪除前的狀態(tài)轉(zhuǎn)移路徑中增添一條權(quán)值為默認(rèn)路徑權(quán)值的默認(rèn)路徑。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)安全領(lǐng)域，并特別涉及一種正則表達(dá)式DFA空間壓縮方法和系統(tǒng)。

背景技術(shù)

隨著計(jì)算機(jī)網(wǎng)絡(luò)的迅速發(fā)展和廣泛應(yīng)用，互聯(lián)網(wǎng)安全問題不可避免地出現(xiàn)在人們面前。多樣化的網(wǎng)絡(luò)流量和服務(wù)應(yīng)用以及各種入侵手段、攻擊方式層出不窮。因此。深度包檢測(cè)被廣泛應(yīng)用在各類網(wǎng)絡(luò)服務(wù)中，對(duì)網(wǎng)絡(luò)數(shù)據(jù)包進(jìn)行內(nèi)容分析，將網(wǎng)絡(luò)數(shù)據(jù)包內(nèi)攜帶的內(nèi)容(內(nèi)容分析結(jié)果)與事先設(shè)置的表征病毒特征的模式集進(jìn)行特征匹配，從而確定數(shù)據(jù)包中是否攜帶非法內(nèi)容。基于DFA的正則表達(dá)式匹配方法由于其對(duì)實(shí)時(shí)高速到達(dá)的待檢測(cè)數(shù)據(jù)流和大規(guī)模模式匹配有較好的匹配效果的特點(diǎn)，得到了廣泛的應(yīng)用。

DFA即確定有限狀態(tài)自動(dòng)機(jī)，由五個(gè)元素構(gòu)成的數(shù)學(xué)模型(S、Σ、δ、S0、F)。使用基于DFA的模式匹配進(jìn)行正則表達(dá)式匹配過程中，由于DFA的狀態(tài)數(shù)和規(guī)則集密切相關(guān)，海量并不斷增加的規(guī)則集表達(dá)式數(shù)量使DFA狀態(tài)數(shù)量劇增，導(dǎo)致狀態(tài)爆炸。此外，正則表達(dá)式中存在的通配符和長(zhǎng)度限制進(jìn)一步加劇DFA的空間占用，目前的硬件條件無法滿足DFA導(dǎo)致的巨大空間需求。最后，基于DFA的正則表達(dá)式進(jìn)行匹配的過程中需要保存所有可能匹配，又對(duì)匹配過程的速度和實(shí)用性能提出了挑戰(zhàn)。

DFA空間壓縮，將其占用空間減少到可以接受的程度，避免發(fā)生狀態(tài)爆炸，從而利用較小的存儲(chǔ)空間得到高的模式匹配速度，在網(wǎng)絡(luò)應(yīng)用中適用DFA高速完成正則表達(dá)式模式匹配的關(guān)鍵技術(shù)。由于網(wǎng)絡(luò)應(yīng)用中的正則表達(dá)式匹配一般適用擴(kuò)展的ACSCII字符集作為字母表Σ，其大小為256，每個(gè)節(jié)點(diǎn)都存在256條出邊，規(guī)模龐大的狀態(tài)轉(zhuǎn)移圖中存在大量的重復(fù)信息，也就是DFA中存在大量冗余邊，現(xiàn)有的狀態(tài)轉(zhuǎn)移壓縮方法又難以平衡由于需要使用默認(rèn)路徑長(zhǎng)度保證算法最壞情況下的匹配性能和壓縮后無明確的狀態(tài)的匹配的需求兩者之間的關(guān)系所導(dǎo)致的匹配速度和性能問題。

發(fā)明內(nèi)容

為了克服DFA實(shí)現(xiàn)正則表達(dá)式匹配過程中DFA狀態(tài)爆炸導(dǎo)致存儲(chǔ)空間占用無法滿足的問題，本發(fā)明提出了一種正則表達(dá)式DFA空間壓縮方法，從字母表壓縮消除冗余邊和DFA狀態(tài)轉(zhuǎn)移邊壓縮兩方面入手，解決正則表達(dá)式匹配中DFA存儲(chǔ)空間爆炸的問題。冗余邊一定是狀態(tài)轉(zhuǎn)移邊，但是狀態(tài)轉(zhuǎn)移邊不一定是冗余的，去掉冗余邊并不影響其對(duì)正則表達(dá)式的表示，所以可以去掉從而減少DFA所占用的空間，從而減少匹配正則表達(dá)式的時(shí)間。

具體地說，本發(fā)明公開了一種正則表達(dá)式DFA空間壓縮方法，其特征在于，包括：

步驟1、通過對(duì)正則表達(dá)式的狀態(tài)轉(zhuǎn)移邊進(jìn)行掃描，讀入轉(zhuǎn)移矩陣，將該轉(zhuǎn)移矩陣中每一列的值以字符串形式存儲(chǔ)；

步驟2、將該該二維數(shù)組中相等的字符串對(duì)應(yīng)的字符表元素合并，得到多個(gè)等價(jià)類的哈希表；

步驟3、通過偽代碼狀態(tài)轉(zhuǎn)移邊壓縮算法，計(jì)算該正則表達(dá)式的狀態(tài)機(jī)中兩兩狀態(tài)間的相似度和該相似度對(duì)應(yīng)的權(quán)值，通過該相似度構(gòu)建相似度矩陣；

步驟4、根據(jù)該狀態(tài)機(jī)中各狀態(tài)點(diǎn)的狀態(tài)深度，更新該相似度矩陣；

步驟5、計(jì)算得到兩兩狀態(tài)間的相似度對(duì)應(yīng)的字符集合；

步驟6、從該相似度矩陣對(duì)應(yīng)的有向圖中的每個(gè)狀態(tài)節(jié)點(diǎn)開始遍歷，選取該狀態(tài)節(jié)點(diǎn)對(duì)應(yīng)的最大相似度轉(zhuǎn)移邊，從而完成默認(rèn)路徑的構(gòu)造，保存該默認(rèn)路徑作為最大生成樹；