刘文涛

(安徽师范大学 计算机与信息学院,安徽 芜湖 241000)

现代网络科技的普及应用给经济及文化等诸多领域造成显著影响．网络空间中流传着大量数据资料，但无法完全规避信息安全风险．根据金融时报报道，网络每隔20秒就会发生一次入侵现象．信息安全是保障互联网继续扩大应用的关键，一旦信息安全受到威胁，丢失敏感数据，可能会损害到国家利益．而如何预防信息外泄与遭受破坏，避免由此出现利益侵害，应当成为我国在不可逆转的网络和信息环境中必须面对和解决的重大战略问题．IDS(入侵检测系统)是一种对网络传输进行即时监视，在发现可疑传输时发出报警或者采取主动反应措施的网络安全设备，它具有维护计算机应用安全的功能，其最初开发设计就是为保障安全，可以支持不间断检测及反馈系统中出现的无权限操作与其他异常指令．其配备的多模式匹配算法在检测过程中发挥关键性作用，在自适应计算网络中、持续扩大的数据规模的情况下，保障模式匹配组合的准确性．

针对大型模式库中的模式集检测问题，提出一种快速高效的模式集检测机制，以避免模式集重复组合的情况．另外，对于数据包，可能会因为计算时效和系统连接的存储器使用情况，导致处理效率不高．所以应用模式匹配方法解决网络安全问题是当前迫切需要研究的．为解决当前网络安全中存在的问题，提出一种基于矢量化技术的网络安全多模式匹配方法，以解决目前存在的问题．

1 多模式匹配预处理阶段

在预处理阶段对模式集中的所有模式进行预处理，从而形成有限状态机，将每个状态转换为状态机，表示模式串字符的跳跃，得到模式串的偏移．该算法在预处理阶段，可同步运用多级散列与动态裁剪处理，形成移位表以及PMT表[1]．在网络安全的预处理时期，系统运行流程为：

(1)基于对模式字符串的准确读取后，按照一定规则保存于数据库内．保留集合内各模式串的最小字符长度，即m；

(2)将SHIFT表以及PMT表进行初始化处理，全部跳转值均调整至m-B+1，把后一个表内的模式数直接调成“0”，并把模式链表调整成NULL；

(3)在首个模式串运行后，把大小是“1”的滑动窗，插到模式串开头，而根据动态切割处理，逐一筛选各模式串上的窗口，得出匹配效率最高的位置．

同时，在 PMT表中添加与窗口长度最佳的后缀字符块相对应的跳转值，在 PMT表条目的模式链表中添加跳转值为零的模式串；

(4)为 SHIFT表和 PMT表(除(3)中处理的后缀字符块外)添加最佳窗口中的每个模式串的字符块，修改相应跳转值，最终得到匹配过程中使用的 PMT表和 PMT表．

在此基础上，确定最有利的m窗口．相应计算流程为：

把字符长度是m的窗口直接放于首个模式串开头，让相应窗口位置的末尾B个字符构成的字符块运行哈希H1．如果对应项的移位值不为零，则检索移位表时所得到的散列值，将窗口中的一个字符移到模式字符串的结尾．依旧按照以上流程进行，假设移位值是“0”，字符块需启动哈希H2，能得到PMT表散列数据．在模式串数不是0，需把对应窗口内某个字符放置在末尾，依旧根据以上流程进行．假设此时串数变成0[2-6]，说明该窗口是最有利的位置，而后将其与模式串相应的开始位置之间的偏移p保存下来．PAT的值等于窗口移动的次数，它记录在模式库 PAT的p偏移域中，该域位于模式库 PAT中．当模式字符串末尾未筛选出最优m，系统会把模式串中首个m当成最优m窗口，此时保存的偏移值是0．

再次执行以上步骤，能得到集合内各模式串相应的最优m与偏移值．另外，该类窗口内字符是B字符块，相应跳转值会直接调至0，在PMT模式链表上，添加模式串，并将 PMT entry skip值 SHIFT设置为零，将模式串的 pnodenum数增加1．

2 网络安全应用多模式匹配实现

在上述多模式匹配基础上，对网络安全应用多模式匹配．在算法的匹配阶段，将匹配的文字作为一组字符流依次扫描，当此流中的每个字符进入状态机后，自动机会自动地改变状态[7-11]，如果匹配成功，就会输出．

为避免匹配失败时不必要的回溯，引入下一个数组，该算法在预处理阶段，根据模式串的特征计算下一个序列，若模式串无法匹配文字字串，则将删除下一个数组的值，下一个序列表达式如下所示：

(1)

式(1)中，j代表文本串的字符.除发生匹配不成功情况外，基本的匹配过程见图1.

图1 基本的匹配过程

匹配过程的具体流程如下：

1)扫描模式集合，基于在匹配过程中用于在窗口中扫描和匹配测试的文本字符串长度不能超过最长模式字符串长度，所以确定模式集中的最长模式字．以下述模式集为例p={he，she，his，hers}，将p中的所有模式添加在状态转移函数图内，整个运行步骤为：其一，确定收割模式串he，添加到相应图表内，基于当下情形编辑字符，而后实现状态转化[12-15]．图2中显示了从0到2的所有状态；

2)每一个处理器核心依次读取被匹配的文本并提取第二个模式串she，将它添加到状态转移函数图(图3)；

3)接着输入第三个模式串his，将其加入到状态转移函数图(图4)；

以上各节的主要意义是，继续向后读待测文本，并在2)中选中的自动机中完成跳转；

4)输入第四个模式串hers，将其加入到状态转移函数图(图5)；

5)除上述外，循环结束时应该添加状态0，这意味着除了状态h和s之外，没有任何模式字符串以s或h开头，其他所有状态都与状态0连接．状态从故障函数0到状态0省略了连接，图6为完全状态转换功能图；

图3 输入she 的状态转移函数

图4 输入his的状态转移函数

每一种状态达到一个新状态，就需要对其进行状态检查，如有，表示模式匹配发生，匹配结果需要记录；

6)阅读最后的文本字符，依次返回步骤2)，直到阅读到待测试的字符串的末尾，或阅读到窗口字符串超出了最长模式字符串，即完成网络安全应用程序的多模式匹配．

3 实验对比

为验证所研究的基于矢量化加速的网络安全应用多模式匹配方法的有效性，进行实验，并将传统匹配方法与所研究方法做对比．

图5 输入hers 的状态转移函数

图6 完整的状态转移函数

3.1 实验数据准备

在程序中，随机生成字符串 T. txt和 p. txt．在这种情况下，匹配数据 T. txt是固定的字符串， p. txt是要匹配的模式字符串， p通过程序进一步处理，得到一个具有不同长度和编号的文件．本仿真实验包括实验一和实验二两组实验，其数据分别如表1、表2所示.

表1 实验一的模式串数据

表2 实验二的模式串数据

3.2 实验一结果分析

以表1中不同数字和随机长度的模式字符串作为模式字符串集合的数据源，随机生成40 000字符的 T字串，作为文本字符串．schema字符串被分成5个文件，分别是1 000,2 000,3 000,4 000和5 000．使用同一实验环境，测试了五个不同模式的字符串文件，并将其与文本字符串文件 T匹配．研究方法和传统方法的实际匹配时间见图7.

图7 运行时间测试结果对比

从实验结果的对比可以得出：

在同一实验环境中模式串数量比较少的情况下，此次研究算法与传统算法时间消耗相差不大，但是对于此次研究算法来说，其匹配时间始终比其他两个算法的匹配时间低．随着模式串数量不断增加，所测试的两个算法的时间消耗都随之增大，但所研究算法的时间增加幅度比传统算法要小．随着模式串数量的不断增多，改进算法的匹配时间与传统方法的匹配时间消耗相差越大，从中可看出所研究算法在匹配时间上的优越性.表3为三种算法测试时间与成功匹配次数结果对比情况．

表3 三种算法测试时间与成功匹配次数结果对比

表3为两种方法分别在不同模式串个数情况下的匹配结果，本次研究方法能成功匹配，成功匹配次数与从文本串中随机抽取的模式串个数相等，这表明所研究方法具有较高的检测准确率，而传统的匹配方法成功次数相对较低，没有本研究方法应用效果好．

3.3 实验二结果分析

实验一中算法的运行时间测试是根据模式串的长度和个数随机进行的，为更全面地比较和分析这两种算法的性能，在第二个实验中，改变了模式串的特征，即当模式串的长度和数目是固定的时候，进一步测试算法的性能．

(1)确定模式字符串的数目，改变模式字符串的长度，用5 000个文件中的模式字符串进行测试，并将长度分别设置为4、7、10、13和20．两种方法的匹配时间如图8所示.

图8 模式串长度不同情况时的匹配时间

图9 模式串数量不同情况时的匹配时间

实验结果表明，当模式串长度不同且数目固定时，两种方法的匹配时间都随模式串长度的增加而增大，但幅度不大．从以上数据可以看出，无论模式串的长度如何变化，所研究方法的所需匹配时间最少，匹配效率最高．

(2)定出模式字符串的长度，改变模式字符串数目．其中，固定模块串个数分为5种，分别为1 000、2 000、3 000、4 000和5 000．图9中显示了不同模式串长度与匹配时间的关系.

由本次实验结果可知，当模式串长度或模式串数量固定时，传统算法与所研究方法随着模式串数量的增加，算法匹配消耗的时间也都随之增长，而本文提出的改进算法的匹配时间随着模式串数量的增加其增长的幅度最小，表明相比于传统算法，所研究方法对模式串数量或长度变化的敏感度较低，匹配效率最高．

4 结束语

针对网络数据量的不断增大，对模式匹配算法性能的要求更高的问题，设计了一个基于矢量化加速的网络安全应用多模式匹配方法，并通过实验证明，该系统提高了匹配效率．本文在研究方法上进行两方面改进，取得了较好的效果．同时本文提出的改进算法还存在很多不足，后续还需进一步优化．