基于正则表达式的动态应用层协议识别方案

传统依赖于端口号的应用层协议识别方法对大量具有随机端口的应用不再适用,设计一种基于正则表达式的动态应用层协议识别方案。在深入分析DFA状态数对算法性能影响的基础上,提出了构造最优DFA状态数的算法,该算法保证在任意有限的系统资源下具有最小的时间复杂度和空间复杂度,并且将报文匹配方式和One-Pass扫描算法相结合进行测试。实验表明此方案具有较低的资源消耗率,较高识别效率和识别精度。     

正则表达式方程组的最小解

网络安全检测中,正则表达式匹配是深度包检测的主要手段,匹配算法则是其关键技术。目前,正则表达式匹配算法可以大体分为转换压缩、状态压缩和字母表压缩三类。文章讨论正则表达式方程组最小解及其求解算法,证明了正则表达式方程组的最小解的存在性和基于Gauss消元法的求解算法的正确性,给出了最小解的构造,分析了求解算法的时间复杂度...     

一类受限正则表达式的推断算法

XML模式推断问题的主要任务可以归约为从一个句子集合中推断出对应的确定型正则表达式。提出了一类在XML模式中大量出现的受限正则表达式,给出了该类正则表达式的推断算法。该算法首先根据给定的句子集合构造自动机,然后根据自动机和句子集合推断出对应的正则表达式。该算法的时间复杂度为max(O(|V|+|E|),O(L)),其中V和E分别表示自动机的节点集合和边集合,L表示句子集合中所有句子的长度之和。对算法的终止性和正确性进行了证明。     

基于正则表达式构建学习的网页信息抽取方法

正则表达式作为信息抽取领域中的一种常用方法已经被广泛应用多年。然而构建高质量并且复杂度较高的正则表达式通常需要耗费大量人工成本,为此,提出一种基于正则表达式状态转换的算法来学习复杂正则表达式的构建过程。该算法需要给定输入初始正则以及正反例样本,初始正则表达式在经过析取分离与合并交叉两大类正则表达式状态转换之后,得到候选正则表达式集合,利用F值评估候选项的信息抽取效果,通过贪心的启发式策略选择一个最优正则表达式作为输出。在多种数据集上对算法进行测评。实验表明,该算法性能与准确度均优于常规的机器学习方法。尤其在较小规模训练集和跨数据集上依然有较好的效果。     

基于预分类的标签传播分组算法

针对已有正则表达式分组算法的分组效果与分组时间难以平衡的问题,本文提出了基于预分类的标签传播分组算法。该算法首先分析了规则间膨胀特征,基于此对正则表达式集合进行预分类;然后借鉴标签传播思想对包含克林闭包的正则表达式集合分组,通过改进初始标签分配和传播过程实现快速聚敛。仿真实验证明,该算法与当前的正则表达式分组算法相比,在相同分组数情况下,有着较少的状态数和更短的分组时间。     

高性能正则表达式匹配算法综述

深度检测在维护网络安全、保证服务质量等方面扮演着重要的角色。正则表达式匹配算法作为高性能深度检测的核心技术,具有重要的研究价值和实践意义。随着网络流量不断增长、规则数目持续增多以及网络结构日趋灵活和动态,现有的正则表达式匹配算法面临着匹配速度、内存占用和更新能力等多方面的挑战。介绍了正则表达式匹配算法的研究背景,从空间压缩、匹配加速、新型自动机设计以及规则拆分和分组四个角度入手,分类总结了学术界具有影响力的研究成果。通过基于真实网络流量的评测,比较了几种经典匹配算法在不同规则集上的匹配速度、内存占用和预处理时间等性能指标,并给出了不同需求场景下高效正则表达式匹配算法的选择建议,归纳了高性能正则表达式匹配算法的下一步发展方向。     

MC-CDMA系统中的自适应半盲多用户检测算法

研究多载波CDMA(MC-CDMA)上行半盲多用户检测技术,对基于Chebyshev逼近算法实现的最小输出能量(MOE)盲多用户检测进行改进,提出MC-CDMA系统下一种基于子空间跟踪和Chebyshev逼近的自适应半盲多用户检测算法。该算法基于MOE线性检测器原理,充分利用小区内所有用户的扩频码,设计了一种基于MOE准则的半盲检测器,很好地消除了多址干扰。为了减少计算复杂度,将修正的PASTd算法应用于Chebyshev逼近算法估计MOE半盲检测器的最优权向量。该算法计算复杂度低,具有较好的抗多址干扰性能和检测性能。仿真结果验证了该算法的可行性和优越性。     

基于正则表达式的图像目标特征提取方法研究

针对图像匹配过程中生成匹配模板复杂度高的问题,根据应用场景下被识别物轮廓、颜色和空间相对位置等物理特征不变的特性,通过建立基于颜色、线条、位置等信息的基础像元素库,并利用正则表达式的组织语法对这些基础元素进行先验知识的有序组织,赋予它们描述待匹配目标匹配特征的能力,从而能够快速构建出被识别物的匹配模板,缩短图像识别过程中模板生成时间,提高图像识别效率。实验结果表明:基于正则表达式特征提取的目标识别方法能够快速、准确对目标进行识别。在固定视角下其识别率为87.5%,平均识别时间为60.3 ms。相比较于尺度不变特征变换(SIFT)和加速鲁莽特征(SURF)算法,该算法在固定视角下的识别精度和识别效率均有所提高。     

一种改进的自动机压缩算法在深度包检测中的应用

传统的基于自动机的深度包检测算法是把正则表达式转化成确定有限自动机,在转化过程中会导致自动机状态消耗巨大运算空间。针对这个缺点,本文提出了一种改进的、基于确定有限自动机的状态压缩算法。该算法在牺牲少量运算时间的情况下,能极大地减少算法所需的运算空间。最后,本文把此算法应用于深度包检测中,设计了对比实验,验证了该算法的有效性。     

Pathfinder算法优化研究

Pathfinder算法是复杂网络分析及可视化的重要方法,但现有算法时间复杂度大,难以在大数据环境下广泛应用。提出一种基于Prim算法的Pathfinder优化算法,在求解复杂网络图的最小生成树的过程中,通过距离矩阵计算得到Pathfinder算法的结果图。算法时间复杂度可稳定为O(n2)。实验结果表明,在顶点数为500的稠密网络上,该算法的运行时间有较大的优势。     

Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation

The canonical firefly algorithm is basically developed for continuous optimization problems. However, lots of practical problems are formulated as discrete optimization problems. The main purpose of this paper is to present the discrete firefly algorithm (DFA) to solve discrete optimization problems. In the DFA, we define a firefly's position in terms of changes of probabilities that will be in one state or the other. Then by using this metaheuristic algorithm, the manufacturing cell formation problem is solved. To illustrate the behavior of the proposed model and verify the performance of the algorithm, we introduce a number of numerical examples to illustrate the use of the foregoing algorithm. The performance evaluation shows the effectiveness of the DFA. The proposed metaheuristic algorithm should thus be useful to both researchers and practitioners.     

离散萤火虫优化算法求解概率旅行商问题

对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解.其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能.实验中用TSPLIB中的经典实例进行测试来验证其可行性.考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较.实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值.     

一组提高存储效率的深度包检测算法

随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的DFA(deterministic finite automata,确定的有限自动机)进行高效的存储.一方面,对DFA的状态点数目进行压缩,提出了一种复合的FSM(有限自动机)的构造方法,通过对正则表达转化成DFA的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建DFA,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对DFA的状态转移数目进行压缩,给出了一种高效的压缩算法,即WD2FA(weighted delayed input DFA,带权延迟DFA)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于D2FA(delayed input DFA,延迟的DFA)有更好的压缩能力,并且使得D2FA是WD2FA在权值为0情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.     

基于膨胀系数的正则表达式分组算法

确定性有限自动机(Det­erministic Finite Automata, DFA)匹配速度远快于非确定性有限状态自动机(Non-deterministic Finite state Autom­ata, NFA),但大量正则表达式转换为DFA时会引起状态爆炸而占用巨大的存储空间。首先定义膨胀系数(Expansion Coefficient, EC)来描述正则表达式的膨胀特性,然后在膨胀系数这一概念基础上,提出一种高效的分组算法--IGA(Improved Grouping Algorithm)算法对正则表达式进行有效分组,将容易引起状态爆炸的正则表达式相互隔离,从而节省存储空间。实验结果表明,与原有算法相比,在相同分组数目时IGA算法平均能够减少25%的状态数。     

基于正则表达式的DFA拆分算法研究

深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表：间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。     

基于图划分的正则表达式分组算法

针对多条正则表达式转换为确定型有限自动机带来的状态空间膨胀问题,借鉴图划分的思想,提出一种改进的分组算法。与原分组算法相比,该算法在分组数相同时状态数平均减少30%,在某些情况下能获得更少的分组数。实验结果证明,该算法能有效降低匹配算法的复杂度。     

DFA最小化算法研究

本文指出了现有DFA最小化算法的缺陷,并给出使用这些算法对DFA限制条件以及将不满足限制条件DFA等价转换成满足限制条件的DFA一般方法;在研究状态等价的充分条件基础上,提出了一种新的适用任何DFA的最小化算法及其算法的正确性证明。     

基于动态默认转移的深度包检测算法

由于基于确定性有限自动机（DFA）的多模式匹配算法对内存的需求比较大,因此需要对DFA进行优化,以减少其对内存的需求量。算法通过用动态默认转移来替代DFA的failto转移,将DFA中大量的failto转移删掉,从而达到优化DFA的目的。实验结果证明,该算法能有效地优化DFA对内存的需求。     

基于信息系统的确定有限自动机最小化算法

目前,确定有限自动机(DFA)最小化问题多侧重于理论研究,尚无太多便于实现的算法,为此,对确定有限自动机最小化方法进行了研究,提出将DFA转换为信息系统,基于等价类划分方法简化信息系统,再将简化的信息系统转换为最小化DFA;针对上述处理过程,给出一个基于分治思想的DFA最小化算法,在平均情况下该算法的时间复杂度为O(n log n),空间复杂度为O(n)。最后通过实例验证了所提算法的正确性。