摘 要：经典的关键词表达式(query expressiont keywords expression)是搜索引擎(web retrieve)和数据库等使用的查询语言。但是在网络内容分析系统中，如果单纯使用关键词作为查询条件，会存在很多误报情况，所以网络内容分析系统-般采用表达式作为查询条件。提出了一种新关键词表达式匹配算法。这种算法改进了经典计数算法(predicate counting algorithm)中不适合网络内容分析环境的数据结构，对比计数算法需要平方级的算法复杂度，新算法可以在线性复杂度内容扫描阶段完成关键词表达式匹配工作。新算法去除了底层多串匹配性能的影响，并通过更多的内存占用，在匹配速度方面可以提高近200%。�
关键词：内容过滤；多模式串匹配；自动机；DFA�
中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2012）003-0057-02��
�
基金项目：湖南省科技计划项目（2009JT3003）;长沙市科技计划重点项目（K1104022-11）�
作者简介：宋云（1974-），男，硕士，长沙理工大学计算机与通信工程学院副教授，研究方向为信息与网络安全、模式识别；龙际珍（1974-），女，硕士，长沙理工大学计算机与通信工程学院讲师，研究方向为信息与网络安全。
0 引言�
串匹配是计算机研究领域的一个经典问题，是许多网络安全系统的关键技术之一。随着信息量的急剧膨胀，应用系统要求更准确、更快速地对海量信息进行分析过滤，采用简单关键词来描述规则的方法已经无法满足需求，往往需要将多个关键词进行组合描述规则，从而获得更精确的信息过滤。因此需要在传统串匹配技术基础上作进一步的扩展和研究。�
最近对面向数据流的应用提出了许多新的算法。在布尔表达式匹配方面，1990年Erzc N Hanson提出了在规则库中IBS-tree算法。在序列匹配方面，相关的工作有实现的有限窗口内的模糊序列后向匹配算法和实现了有限窗口内的前向匹配算法。文献\[7\]提出了布尔表达式匹配技术,给出了算法框架,在此框架上实现了2种常用的实现方式。为了进一步增加布尔表达式的描述功能,增加了定序和窗口 2个限制条件,提出了BitCount_OWBE算法,通过理论分析和实验数据证明该算法在多数情况下仍然可以达到原先的性能,从而很好地解决了上万规模的复杂规则匹配问题。其中文献\[7\]介绍计数算法（双映射表算法，counting algorithm））是简单直接的方式是直接对匹配关键词序列进行逻辑计算，即直接判断关键词是否满足布尔表达式的布尔逻辑关系。双映射表算法主要通过构建两张映射表来简化逻辑计算。表达式映射表中索引为布尔表达式序号，内容为该布尔表达式包含所有关键词序号（不包括标志符号，标志符号用Flag标志数组来表示）；关键词映射表中索引为关键词序号，内容包含该关键词的所有布尔表达式的序号。�
本文提出的ExprAuto算法是一个有限窗口内的布尔表达式匹配算法，保证了扫描匹配阶段的算法复杂度为O（1），对单个网络连接的空间复杂度也是O(1)。�
1 自动机算法ExprAuto�
ExprAuto算法是只支持滑动窗口w的布尔表达式匹配算法。一个规则在窗口中被满足，就是窗口w中出现了这个规则的全部事件。对于文本的布尔表达式匹配来说，就是在一段文字中出现了w个关键词，并且这些关键词包含了规则所要求的全部关键词。一般来说，在网络内容分析系统中，一条规则中只包含两个关键词，窗口的大小为4。�
构造共享自动机分为3个步骤：首先构造一个多叉完全树，其次增加转移指针，最后对各个状态增加这个状态满足的规则。 对于m_pKeySize个事件，我们实现一个w层的m_pKeySize叉完全树。构造算法如下：�
2 复杂度分析�
对比于经典的计数算法，ExprAuto的主要缺点在于它的所有网络连接所共享的自动机的空间复杂度和时间复杂度都是O(m_KeySizew)，但是在扫描匹配阶段它的时间和空间复杂度都为O（1）。但是在面对千万级别的网络连接和千级别的规则的应用环境中，对比计数算法在扫描的时间和空间复杂度都是O（m_KeySize＋m_ExprSize）和时间复杂度是O（m_ExprSize/m_KeySize），ExprAuto算法具有一定的优势。同时ExprAuto的扫描匹配的空间复杂性低也导致它更适合海量网络连接的应用场合。�
3 实验结果与分析�
实验平台：实验平台为一台使用奔腾IV I．6GHz CPU，128M SDRam的个人电脑，操作系统为WindowsXP．我们的测试是从红楼梦文本(l，741，168字节)中随机抽取长度为6个字母（3个汉字）的关键词，每个表达式由两个关键词构成，测试速度的文本同样使用红楼梦，定义加速比为除掉串匹配执行时间后，算法执行时间的比值：
4 结束语�
本文从面向网络内容分析的应用角度出发，分析了面向网络内容分析系统的算法设计需要考虑的新问题，提出了基于自动机的布尔表达式匹配算法。自动机布尔表达式匹配算法可以保证在内容扫描阶段的时间复杂度为O（1），空间复杂度也是O(1)。去除了底层多串匹配性能的影响， ExprAuto比ExprCount算法通过更多的内存占用，在匹配速度方面可以提高接近200%的性能提高。同时自动机布尔表达式匹配算法的设计思路，也可以使用在面向网络内容分析领域的其它算法设计上。�
参考文献：�
\[1\] N ALON, Y MATIAS,M SZEGEDY. The space complexity of Approximating the Frequency Moments\[C\]. In Proc. of the 1996 Annual ACM Symp. on Theory of Computing, 1996.�
\[2\] A ARASU,B BABCOCK, S BABU, J MCALISTER, et al.Characterizing memory requirements for queries over continuous data streams\[C\]. In Proc. of the 2002 ACM Symp. on Principles of Database Systems, June 2002.�
\[3\] A DOBRA, J GEHRKE, M GAROFALAKIS,et al.Processing complex aggregate queries over data streams\[C\]. In Proc. of the 2002 ACM SIGMOD Intl. Conf. on Management of Data，2002.�
\[4\] YOAV FREUND, ROBERT E. SCHAPIRE, YORAM SINGER,MANFRED K. WARMUTH.Using and combining predictors that specialize\[C\], Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, El Paso, Texas, United States,1997