ACSM算法在網絡信息審計系統中的改進研究

許康 宋力 劉遇哲

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

ACSM算法在網絡信息審計系統中的改進研究

許康 宋力 劉遇哲

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

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

ACSM算法模式匹配動態跳轉網絡安全信息審計特征字符串

1 引言

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

網絡信息審計系統需要對數據包內容進行審計，在數據包中往往是多個特征字符串按照一定順序并存的，因此ACSM多模匹配算法需要經過必要的優化改造以便能夠應用于網絡信息審計系統中[3]。

2 ACSM算法概述

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

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

但是ACSM算法只是將特征字符串添加進狀態機，能夠匹配出單個字符串，并沒有實現特征字符串間的狀態跳轉，從而也就不能滿足網絡信息審計系統實現網絡應用識別的目標。

3 ACSM算法改進的實現過程

3.1 定義

①特征id：特征字符串所對應的id號；

②狀態跳轉id：特征id號所對應的跳轉id號；

③狀態跳轉源id和目的id：從特征串1跳轉到特征串2，特征串1的狀態跳轉目的id即特征串2的狀態跳轉源id；

④樹節點：即特征串跳轉狀態機上的節點，節點上存儲著特征id以及狀態跳轉id等信息。

3.2 ACSM算法改進的原理

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

創建的特征字符串跳轉狀態機如圖1所示。

圖1 特征字符串跳轉狀態機

3.3 構造特征串跳轉表函數

網絡應用的識別是建立在特征串按照特定順序跳轉匹配的基礎上的[8]，現有的ACSM算法不能滿足要求，所以需要構造特征串跳轉狀態機，來實現按照指定順序精確匹配字符串來識別出具體的應用，特征串跳轉狀態機構造函數流程圖如圖2所示。

圖2 特征串跳轉機構造函數流程圖

3.4 對ACSM算法的特征串匹配函數的修改

現有的ACSM算法實現了單個特征串的匹配[9]，并沒有實現多個特征串按序跳轉匹配的功能，從而不能滿足網絡信息審計系統準確識別網絡應用的需求。

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

圖3 特征串匹配函數流程

4 結束語

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

[1]張鑫.快速模式串匹配技術的研究及一個郵件內容過濾系統的實現[D].中國科學院計算技術研究所碩士論文,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].計算機研究與發展，2002,39（1）:55-60.

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

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

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

[10]許強，江早，趙宏.基于圖像內容過濾的智能防火墻系統研究與實現[J].計算機研究與發展，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