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