許康 宋力 劉遇哲

（河北遠(yuǎn)東通信系統(tǒng)工程有限公司，河北石家莊 050000）

ACSM算法在網(wǎng)絡(luò)信息審計(jì)系統(tǒng)中的改進(jìn)研究

許康 宋力 劉遇哲

（河北遠(yuǎn)東通信系統(tǒng)工程有限公司，河北石家莊 050000）

隨著國(guó)家信息化的不斷推進(jìn)和計(jì)算機(jī)網(wǎng)絡(luò)飛速發(fā)展，網(wǎng)絡(luò)信息審計(jì)成為不可或缺的一部分。網(wǎng)絡(luò)信息審計(jì)系統(tǒng)從網(wǎng)絡(luò)關(guān)鍵點(diǎn)采集數(shù)據(jù)包，對(duì)其傳送內(nèi)容進(jìn)行審計(jì)分析，達(dá)到網(wǎng)絡(luò)信息內(nèi)容的監(jiān)控。在網(wǎng)絡(luò)信息審計(jì)系統(tǒng)中，需要對(duì)大量的關(guān)鍵特征串進(jìn)行按序匹配，目前的ACSM算法只是實(shí)現(xiàn)了單字符的跳轉(zhuǎn)狀態(tài)機(jī)，僅能夠匹配出單個(gè)的字符串，卻未實(shí)現(xiàn)特征串的按序跳轉(zhuǎn)，不能滿(mǎn)足網(wǎng)絡(luò)審計(jì)系統(tǒng)識(shí)別網(wǎng)絡(luò)應(yīng)用的需求。經(jīng)過(guò)對(duì)ACSM算法的改造，創(chuàng)建了特征字符串的動(dòng)態(tài)跳轉(zhuǎn)狀態(tài)機(jī)，滿(mǎn)足了網(wǎng)絡(luò)信息審計(jì)系統(tǒng)對(duì)特征字符串按序匹配從而識(shí)別出網(wǎng)絡(luò)應(yīng)用的需求。

ACSM算法模式匹配動(dòng)態(tài)跳轉(zhuǎn)網(wǎng)絡(luò)安全信息審計(jì)特征字符串

1 引言

模式串匹配問(wèn)題就是在一個(gè)符號(hào)序列中查找另一個(gè)符號(hào)序列的搜索問(wèn)題。在計(jì)算機(jī)應(yīng)用系統(tǒng)中，使用模式串匹配技術(shù)的例子隨處可見(jiàn)，例如入侵檢測(cè)系統(tǒng)、計(jì)算機(jī)病毒檢測(cè)、包過(guò)濾防火墻系統(tǒng)中都使用了模式串匹配技術(shù)[1]。模式匹配算法包括單模式匹配算法、多模式匹配算法。單模式匹配算法一次只能對(duì)數(shù)據(jù)串進(jìn)行一個(gè)模式匹配，主要有BF算法、KMP算法、BM算法等[2]。多模式匹配算法一次可對(duì)數(shù)據(jù)串同時(shí)進(jìn)行多個(gè)模式匹配，即找到數(shù)據(jù)串中與模式串完全相等的子串的所有出現(xiàn)位置，如ACSM算法、PCRE算法等。PCRE算法是基于NFA非確定型有窮自動(dòng)機(jī)的，以時(shí)間換取更多的匹配特性；而ACSM算法是基于DFA確定型有窮自動(dòng)機(jī)的，以空間換時(shí)間，從匹配效率上優(yōu)先于PCRE，而網(wǎng)絡(luò)信息審計(jì)系統(tǒng)對(duì)效率的要求較高，ACSM算法就成為其首選。

網(wǎng)絡(luò)信息審計(jì)系統(tǒng)需要對(duì)數(shù)據(jù)包內(nèi)容進(jìn)行審計(jì)，在數(shù)據(jù)包中往往是多個(gè)特征字符串按照一定順序并存的，因此ACSM多模匹配算法需要經(jīng)過(guò)必要的優(yōu)化改造以便能夠應(yīng)用于網(wǎng)絡(luò)信息審計(jì)系統(tǒng)中[3]。

2 ACSM算法概述

ACSM算法是基于自動(dòng)機(jī)的，1975年產(chǎn)生于貝爾實(shí)驗(yàn)室。該算法應(yīng)用有限自動(dòng)機(jī)巧妙地將字符比較轉(zhuǎn)化為了字符間的狀態(tài)轉(zhuǎn)移，根據(jù)模式串集合進(jìn)行預(yù)處理，建立一個(gè)字符跳轉(zhuǎn)自動(dòng)機(jī)[4]。

此算法有2個(gè)特點(diǎn)，一個(gè)是掃描文本時(shí)完全不需要回溯，另一個(gè)是時(shí)間復(fù)雜度始終為O(n)，與關(guān)鍵字的數(shù)目和長(zhǎng)度無(wú)關(guān)。其中n為主串的長(zhǎng)度[5]。

但是ACSM算法只是將特征字符串添加進(jìn)狀態(tài)機(jī)，能夠匹配出單個(gè)字符串，并沒(méi)有實(shí)現(xiàn)特征字符串間的狀態(tài)跳轉(zhuǎn)，從而也就不能滿(mǎn)足網(wǎng)絡(luò)信息審計(jì)系統(tǒng)實(shí)現(xiàn)網(wǎng)絡(luò)應(yīng)用識(shí)別的目標(biāo)。

3 ACSM算法改進(jìn)的實(shí)現(xiàn)過(guò)程

3.1 定義

①特征id：特征字符串所對(duì)應(yīng)的id號(hào)；

②狀態(tài)跳轉(zhuǎn)id：特征id號(hào)所對(duì)應(yīng)的跳轉(zhuǎn)id號(hào)；

③狀態(tài)跳轉(zhuǎn)源id和目的id：從特征串1跳轉(zhuǎn)到特征串2，特征串1的狀態(tài)跳轉(zhuǎn)目的id即特征串2的狀態(tài)跳轉(zhuǎn)源id；

④樹(shù)節(jié)點(diǎn)：即特征串跳轉(zhuǎn)狀態(tài)機(jī)上的節(jié)點(diǎn)，節(jié)點(diǎn)上存儲(chǔ)著特征id以及狀態(tài)跳轉(zhuǎn)id等信息。

3.2 ACSM算法改進(jìn)的原理

網(wǎng)絡(luò)信息審計(jì)系統(tǒng)需要對(duì)采集的數(shù)據(jù)包進(jìn)行應(yīng)用層識(shí)別，就不可避免使用到多模匹配算法[6]。網(wǎng)絡(luò)應(yīng)用的識(shí)別需要將預(yù)定義的幾個(gè)特征字符串按照指定的順序、固定偏移、深度匹配出來(lái)，即實(shí)現(xiàn)特征字符串的狀態(tài)跳轉(zhuǎn)，因此需要?jiǎng)?chuàng)建一個(gè)字符串跳轉(zhuǎn)狀態(tài)機(jī)，從而滿(mǎn)足需求[7]。

創(chuàng)建的特征字符串跳轉(zhuǎn)狀態(tài)機(jī)如圖1所示。

圖1 特征字符串跳轉(zhuǎn)狀態(tài)機(jī)

3.3 構(gòu)造特征串跳轉(zhuǎn)表函數(shù)

網(wǎng)絡(luò)應(yīng)用的識(shí)別是建立在特征串按照特定順序跳轉(zhuǎn)匹配的基礎(chǔ)上的[8]，現(xiàn)有的ACSM算法不能滿(mǎn)足要求，所以需要構(gòu)造特征串跳轉(zhuǎn)狀態(tài)機(jī)，來(lái)實(shí)現(xiàn)按照指定順序精確匹配字符串來(lái)識(shí)別出具體的應(yīng)用，特征串跳轉(zhuǎn)狀態(tài)機(jī)構(gòu)造函數(shù)流程圖如圖2所示。

圖2 特征串跳轉(zhuǎn)機(jī)構(gòu)造函數(shù)流程圖

3.4 對(duì)ACSM算法的特征串匹配函數(shù)的修改

現(xiàn)有的ACSM算法實(shí)現(xiàn)了單個(gè)特征串的匹配[9]，并沒(méi)有實(shí)現(xiàn)多個(gè)特征串按序跳轉(zhuǎn)匹配的功能，從而不能滿(mǎn)足網(wǎng)絡(luò)信息審計(jì)系統(tǒng)準(zhǔn)確識(shí)別網(wǎng)絡(luò)應(yīng)用的需求。

修改ACSM算法的特征串匹配函數(shù)，首先需要根據(jù)匹配上的字符串的位置進(jìn)行深度匹配，如果能夠滿(mǎn)足其特征串所對(duì)應(yīng)的偏移、深度等進(jìn)一步的匹配信息，就記錄該特征對(duì)應(yīng)的狀態(tài)跳轉(zhuǎn)目的id，直到按特征串跳轉(zhuǎn)機(jī)預(yù)定義的順序匹配到所有指定字符串，標(biāo)記著某一種具體網(wǎng)絡(luò)應(yīng)用被識(shí)別出[10]。特征串規(guī)則匹配完成即代表著某一網(wǎng)絡(luò)應(yīng)用被識(shí)別出就立即返回，主串中剩余的字符串就不再進(jìn)行匹配。流程如圖3所示。

圖3 特征串匹配函數(shù)流程

4 結(jié)束語(yǔ)

經(jīng)過(guò)對(duì)ACSM算法的研究及改進(jìn)，創(chuàng)建了特征字符串跳轉(zhuǎn)狀態(tài)機(jī)，實(shí)現(xiàn)了將特征串按照指定的順序、固定的偏移進(jìn)行動(dòng)態(tài)且精確的匹配，滿(mǎn)足了網(wǎng)絡(luò)信息審計(jì)系統(tǒng)準(zhǔn)確識(shí)別多種網(wǎng)絡(luò)應(yīng)用的要求。優(yōu)化之后的ACSM算法對(duì)于需要同時(shí)進(jìn)行多個(gè)模式按序匹配的其它應(yīng)用系統(tǒng)如入侵檢測(cè)、病毒檢測(cè)等也具有重大實(shí)用價(jià)值。

[1]張?chǎng)?快速模式串匹配技術(shù)的研究及一個(gè)郵件內(nèi)容過(guò)濾系統(tǒng)的實(shí)現(xiàn)[D].中國(guó)科學(xué)院計(jì)算技術(shù)研究所碩士論文,2003.

[2]Alfred V.Aho,Margaret J,Corasik Bell Laboratories[J].Efficient String Matching:An Aid to Bibliographic Search.Comm. ACM 1975,18(6):333-340.

[3]Marc Norton.Optimizing Pattern Matching for Instruction Detection[EB/OL],SourceFire,Inc,September 2004.

[4]Tarjan,R.E.,and Yao,A.C.-C.Storing a sparse table[J]. Commun,ACM 1979(21):11.

[5]Thomas H.Cormen.Charles E.Leiserson.Ronald L.Rivest. Clifford Stein,Introduction to Algorithms(Second Edition)[M].北京：Higher Education Press&The MIT Press,2002:909-923.

[6]王永成，沈州，許一震.改進(jìn)的多模式匹配算法[J].計(jì)算機(jī)研究與發(fā)展，2002,39（1）:55-60.

[7]張光云,田麗.傳統(tǒng)NIDS漏報(bào)和誤報(bào)起因及改進(jìn)技術(shù)[J]計(jì)算機(jī)信息2006(1-3):36-38,18.

[8]陳國(guó)龍,陳火旺,康仲生.基于內(nèi)容的網(wǎng)絡(luò)信息安全審計(jì)中的匹配算法研究[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25(9): 1676-1679.

[9]趙鈴濤.基于內(nèi)容的安全審計(jì)跟蹤算法及其應(yīng)用研究[D].上海交通大學(xué)碩士論文，2007,2-3.

[10]許強(qiáng)，江早，趙宏.基于圖像內(nèi)容過(guò)濾的智能防火墻系統(tǒng)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)研究與發(fā)展，2000,37(4):458-464.

Research and Improvement of ACSM Algorithm in Network Information Audit System

XU Kang,SONG Li,LIU Yu-Zhe
(Hebei Far-east Communication System Engineering Co.Ltd,Shijiazhuang Hebei 050000,China)

with the continuous progress of national informatization and the rapid development of computer network,the network information audit has become an indispensable part of network information audit system.The network information audit system collects data package from the key point of network,performs audit and analysis for transfer content and monitors network information content. In the network information audit system,it is necessary to perform matching in sequence for various key feature strings.The existing ACSM algorithm only realizes the jump state machine which can only match single character strings,not realize jumping in order of feature string,and thus not meet the requirements of network application identification of network audit system.The dynamic jump state machine of feature character string is created by improving ACSM algorithm to meet the requirement of feature character string matching in order and network application identification of network information audit system.

ACSM algorithm;pattern matching;dynamic jump;network security;information audit;feature character string

TP391.4

A

1008-1739（2015）09-39-3

定稿日期：2015-04-12