一种网络内容快速动态检测方法

高速网络内容检测与过滤依赖于快速多模式匹配算法按预先定义的模式集对分组的任意位置内容进行匹配。模式集往往有成千上万条,长短不一且十分复杂。多模式匹配算法对存贮器的访问速度很敏感,算法的好坏往往成为系统的性能瓶颈。另外,新的攻击层出不穷导致模式内容不断变化,如何在检测的同时有效地更新模式集合对网络安全设备在不停机检测条件下实现规则的升级与更新尤其重要。针对上述问题,提出了一种松散耦合的双通道线速动态内容检测方法,快速通道利用可动态查询的并行Counting Bloom filter引擎过滤网络分组。过滤出的嫌疑分组送慢速通道利用高效动态模式匹配算法一步准确鉴别和分析,从而避免对正常分组的阻碍达到线速检测。基于程序局部性原理,采用了额定长度前缀的方法实现了对长模式的可扩展性。分析与模拟试验表明,检测方法具有较高的吞吐性能,可以实现线速动态深度分组检测,同时减少了硬件资源开销,提高了可扩展性。     

一种网络分组内容线速动态检测方法

针对高速网络内容检测中多模式匹配算法性能差和模式集不断动态变化的问题,提出了一种松散耦合的双通道线速动态内容检测方法.该方法包含快速通道和慢速通道两部分,快速通道利用可动态查询的并行Counting Bloom filter引擎过滤网络分组,过滤出的嫌疑分组送慢速通道利用高效动态模式匹配算法一步准确鉴别和分析,从而避免对正常分组的阻碍,达到线速检测.基于程序局部性原理,采用额定长度前缀的方法实现了对长模式的可扩展性.分析与模拟试验表明,该检测方法具有较高的吞吐性能,可以实现线速动态内容检测,同时减少了硬件资源开销,提高了可扩展性.     

粗等价类融合禁忌搜索的最小约简完备算法

提出粗等价类融合禁忌搜索的最小约简完备算法.首先用全局等价类替换元组作为基本计算单位,给出3类粗等价类定义,结合0-粗等价类在约简的渐增式计算中递减至空的性质,推导出求正区域的等价方法,并设计求解中双向缩减计算域的优化策略,从而提供快速求初始解、验证解等基础算法;然后面向约简特性设计禁忌搜索下的多种策略,包括双向邻域搜索、藐视准则、有限随机搜索、有限解检验等,最后给出高效的最小约简完备算法.用UCI中20个决策表、KDDCup海量数据集从多个性能指标进行验证,实验结果证明粗等价类理论和禁忌搜索从双方面保证本文算法的完备和高效性,大多数情况下可有效求得最小约简,并在跳出局部最优解、收敛速度和处理海量数据效率等方面优于现有算法.     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

一种正则表达式集合快速搜索算法

正则表达式由于其强描述能力和灵活性,在信息检索,程序设计,数据挖掘,深度分组检测,生物信息处理等领域得到了广泛而深入的应用,然而正则表达式,尤其是正则表达式集合,由于搜索速度慢往往成为系统的性能瓶颈。现有的正则表达式搜索算法性能较好的是多模式过滤类型的算法,此类算法严重依赖于两个因素,从NFA的初始状态到终止状态的最短路径Lmin和正则表达式所表达的语言的前缀集合Pref（RE）的大小,Lmin越长,搜索速度越快,Pref（RE）越大,搜索速度越慢。针对上述问题提出了一种基于Bloom filter的正则表达式集合搜索算法,此方法利用Bloom filter的集合查询时间集合大小无关的特点,使得正则表达式搜索速度不受Pref（RE）大小的影响,如果采用多个Bloom filter并行,还可以间接增大Lmin的长度。分析与测试结果表明,本算法较大的加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,可以实现大规模正则表达式集合的快速搜索。     

基于树型代理透明服务模型的流媒体复本放置

针对树型网络的路由机制和流媒体数据访问的分布特点,建立了树型代理透明服务模型,提出该模型上的流媒体复本放置问题.分析了常用的前缀放置算法在树型代理模型上的局限生,提出了非定长、可非连续的放置策略,并给出两种贪婪式的复本放置算法:自底向上逐层放置的层次型贪婪式复本放置算法( HGPA)和在全树范围逐块贪婪放置的全局贪婪式放置算法(GGPA).仿真实验结果表明:HGPA和GGPA算法均能有效降低服务器负荷,减少网络访问成本,性能均优于前缀放置算法;GGPA算法性能略优于HGPA算法,但时间代价过高;综合来看,HGPA是树型代理上较理想的放置方案.     

粗等价类双边递减下多次Hash的渐增式求核与约简算法

为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析1,0,-1三类粗等价类的性质,把求正区域等价转化为0-粗等价类双边递减下的渐增式计算,结合1和-1-粗等价类的传递性,设计双边横向删减实体和纵向删减属性的优化规则,可在每一轮增量计算中缩减计算域,基于此设计多次Hash的属性增量划分方法;最后给出新的渐增式快速求核与约简算法,其中求核基于纵向优化规则,可在一次计算中求得多个非核属性,无需遍历全部属性.基于UCI、海量和超高维3类数据集进行多个实验,实验结果证明本文求核与约简算法是高效完备的,在海量数据与超高维数据集下有较大优势.