一种基于P—集合筛选过滤的模式匹配算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于P—集合筛选过滤的模式匹配算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：本文实验分析了不同的网络及数据包状态对于不同的模式匹配算法所产生的性能影响；通过对动态数据集的相关性分析，提出了一种新的改进算法，通过最优数据筛选-过滤定理及模式串在文本串中的概率分布，找出模式串的特征字符组成新的匹配模式串；对原始数据集进行分层匹配，并对该算法进行了实验验证及性能分析。
关键词：P-集合；概率分布；模式匹配
中图分类号：TP301.6
1 背景
在网络中，网络安全设备，需要对网络中海量的、复杂的数据包进行匹配分析，如何快速的从海量数据中提取出需要的特征信息，已经成为目前信息安全的重要课题。体现到实际网络环境中海量数据包中的入侵行为的显现，是多种特征数据包动态变化的过程。同时网络数据包集本身的基本属性是不变的，只是增加或减少了部分具有特征恶意的数据包，随着时间的推移各种可能入侵行为的产生，数据集本身的状态也在动态迁移中，对数据包的匹配检测而言，并不关心数据包集本身，其最想了解的而是数据动态迁移的过程。综上所诉我们发现数据包集生产过程是动态的过程且具有可描述性、随机性等特征。本文希望通过对P-数据包集合的特征分析，对海量数据包集进行过滤预处理筛选出可能存在特征模式串的文本区域，以提升模式匹配速率和匹配命中率。
不妨设发生异常入侵情况数据包集的具有的特征集：
其中α1α2α3……αn分别对应的具体的异常属性有出口设备流量突然增大，核心交换CPU突然增大，核心交换内存使用突然增大，出现大量异常小数据包，出现长时间的端口扫描行为等症状属性，针对这些症状和现象在我们的入侵检测系统有对应的匹配检测手段，即通过模式匹配进行检测，其特征模式串及字符串中的字符集：
通过对不同特征模式串的尝试可以使特征集α中的相关现象得以缓解。
当我们α=>0则我们找到了最优的解决方案，但是在发现最优解决方案的之前我们并不知道使用哪种特征模式串组合是我们需要的，即初始状态下元素迁移的概率s1的情况下：
，
为最优筛选-过滤数据集。
通过上面的实验及讨论，分析了整个模式串ρ与算法效率的关系，显然存在当ρ则有ρ（pi）。参考P-集合最优数据筛选-过滤数据集思路：在精确多模式匹配的时候先对数据集进行筛选-过滤，通过最优数据筛选-过滤定理选择最优模式串及字符串组合对数据集进行筛选-过滤，然后在精确匹配的算法设计思路。
又因为：
也就说ρ是由ρ（pi）与其条件概率共同决定的。
ρ（pi）对算法又有什么影响呢？结合AC和WM算法的分析，做如下工作：
以AC算法为例，不妨设状态机及其模式串字符间的概率如下图所示：
所以选择条件概率最小的那个作为特征点，可以减少匹配查找的时间。
由上图可得可以选择A距离为2的C作为共同作为特征点先查找匹配。则根据以上条件设计如下算法：
第一步：
初始化：根据特征字符集的特征字符选择K个有限的字符组合组成新的特征模式串。
第二步：
参考Pi条件概率选取K个Pn…作为模式串的查找序列；如果存在有限状态机存在分支且存在较小的Pn…；则分别且至少每分支上选取上一个Pn…组成新状态机的分支。
第三步：
参考最优数据筛选-过滤定理，对数据集进行筛选-过滤，记录数据集筛选-过滤后的属性集： ，得到最优模式串及字符串组合。如上图最优的字符串组合为A和C。
第四步：
记录Pn…与Pi的间隔字符数n-i=d；即A与C的间隔为2。
第五步：
通过Pi与Pn…组成新的序列通过AC算法比较若成功跳到第四步即AC组成新的有限状态机如图
第六步：
分解原状态机后精确匹配；
3 实验分析
实验条件：
设当字符集大小|Σ|=256，模式串长度m=8字节，模式串个数r=500，文本长度n=1M字节时，在完全随机生成数据。
设分别ρ以{0，0.01，0.02，0.03，0.04，0.05，0.06，0.07，0.08，0.09，0.1}取出模式串以随机的方式分散替换到文本串中。
字符间固定存在如下的ρi{0.1，0.001，0.04，0.03，0.02，0.008}作为字符间的条件概率分布。根据选择与Pi条件概率较小K个Pn…作为模式串的查找序列；如果存在有限状态机存在分支且存在较小的Pn…；则分别且至少每分支上选取上一个Pn…组成新状态机的分支，生成新的模式串查找序列。
本实验从特征模式串及字符串中的字符集中 ，固定只选取2个字符组合作为筛选-过滤参考条件。
实验1：
当选择ρi=0.1的两个字符组合则有得到如下表的实验结果：
通过上表分析：
（1）在ρ较小的情况下WM可以更快的发现随机分布的模式特征串。
（2）随着ρ，AC模式匹配算法匹配过程中性能稳定。
（3）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，算法匹配过程中改进算法性能更加稳定。
实验2：
当选择ρi=0.001的两个字符组合时则有得到如下表的实验结果：
通过上表分析：
（1）在ρ较小的情况下改进算法可以更快的发现随机分布的模式特征串。
（2）随着ρ，改进算法和AC算法模式匹配算法匹配过程中性能稳定。
（3）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，改进算法匹配过程中性能更加稳定。
（4）实验2与实验1在不同ρi的条件概率下，在ρi=0.001是可以的更快的发现随机分布的模式特征串。
实验3：
通过上表分析：
（1）随着ρ，改进算法在整个匹配过程中性能稳定。
（2）改进模式匹配算法在ρ较小的情况下可以较快发现随机分布的模式特征串；同时随着ρ，模式匹配算法匹配过程中性能更加稳定。
（3）通过实验1实验2实验3针对ρi{0.1，0.001，0.04，0.03，0.02，0.008}字符间不同的条件概率我们发现当选取ρi较小时可以更快的发现随机分布的模式特征。
4 结论
当发生异常数据包入侵事件时，大部分入侵事件都具有目的性、趋利性、因果性；为了达到入侵的目的，所采用的手段都是有针对性；从数据包的角度来看也是有特征可循的。所以从这个思路出发，设计了模式串以不同概率随机分布到文本串中的试验环境，分析了AC、WM多模式匹配算法，统计了各种算法在文本串中找出所有特征数据包所需要的时间，分析其在不同概率分布条件下的性能指标；证明了WM概率分布较小时表现最为优秀；但是AC算法在匹配过程中比较稳定；最后提出了一种新的改进的模式匹配算法，通过最优数据筛选-过滤定理选择最优模式串及字符串组合对数据集进行筛选-过滤，找出模式串中的特征字符组成新的匹配模式串，对文本串进行分层匹配。具有较快的匹配速度及更稳定的匹配命中率。
参考文献：
[1]史开泉.P-集合[J].山东大学学报：理学版，2008，43（11）：77-84.
[2]史开泉.函数P-集合[J].山东大学学报：理学版，2011，46（2）：62-69.
[3]郭志林.P-集合的随机特征[J].模糊系统与数学，2011，25（2）：170-174.
[4]郭志林.随机P-集合的数据筛选过滤[J].河南科技大学学报自然科学版，2012，33（2）：83-86.
[5]孙德才.基于匹配区域特征的相似字符串匹配过滤算法[J].计算机研究与发展，2010，47（4）：663-670.
作者简介：韩路（1983.9-），男，安徽宣城人，助理工程师，硕士研究生，研究方向：网络与信息安全。
作者单位：南京航空航天大学信息中心，南京 210016