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

許康 宋力 劉遇哲

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

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

許康 宋力 劉遇哲

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

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

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

1 引言

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

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

2 ACSM算法概述

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

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

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

3 ACSM算法改進的實現(xiàn)過程

3.1 定義

①特征id：特征字符串所對應(yīng)的id號；

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

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

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

3.2 ACSM算法改進的原理

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1]張鑫.快速模式串匹配技術(shù)的研究及一個郵件內(nèi)容過濾系統(tǒng)的實現(xiàn)[D].中國科學(xué)院計算技術(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].計算機研究與發(fā)展，2002,39（1）:55-60.

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

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

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

[10]許強，江早，趙宏.基于圖像內(nèi)容過濾的智能防火墻系統(tǒng)研究與實現(xiàn)[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