一种基于DFA的短文本信息过滤算法

有关信息过滤的算法应用广泛,随着微信、微博等社交平台的迅速发展,短文本信息在网络通信中占据了主流,针对短文本信息的过滤也越来越重要。通过比较BF算法、KMP算法、AC算法等经典模式匹配算法的优缺点,选择更适合短文本过滤的DFA算法。介绍DFA算法基本原理,提出一种基于DFA的改进算法,改进后的算法通过敏感词预处理和过滤过程优化来提高检测率。实验结果表明,相比于SWDT-IFA算法,改进后的算法对中文对话数据集检测的查准率提高了3%,误报率降低了0.87%,具有较高的应用价值。

高速邮件监控审计研究

为了满足企业级高速网络中邮件监控需求,提出了基于内存映射和libnids改进框架的邮件监控审计方案。该方案首先通过改进libnids库内核、用户级缓存和内存映射文件技术减小I/O开销,高效捕获存、储原始邮件数据,然后对邮件协议进行了深入地分析,将捕获的数据简化封装成MIME格式,采用多线程技术对其进行还原,最后采用基于Wu_Manber多模式匹配算法对还原的邮件内容进行审计,生成强大的审计报表。测试结果表明,该系统能为企业管理部门提供一个高效的邮件监管工具。

基于电子舌技术的卷烟主流烟气味觉识别

为考察电子舌对不同卷烟烟气味觉的识别效果,利用电子舌系统检测了6个烤烟型和3个混合型卷烟样品主流烟气水处理液的味觉特征,并对其传感器响应信号进行了主成分分析(PCA)和判别因子分析(DFA)。结果表明:①前2维主成分对卷烟品种的味觉识别贡献率达84.82%;②前2维DFA对卷烟品种的味觉识别贡献率达95.42%。结论:在模式识别中,DFA法的区分效果优于PCA法;电子舌能区分不同香型卷烟味觉特征,有望成为一种辅助的卷烟感官质量评价方法。

基于有限自动机的模式匹配算法及其应用研究

针对质量统计过程控制(SPC)中的异常模式快速匹配问题,提出了基于确定有限自动机(DFA)的模式匹配算法,给出了能利用DFA进行匹配的基于多维输入数据的模式串定义。在分析常规质量控制图中的八种异常模式的基础上,给出了基于DFA的模式串匹配算法。该算法在企业计算机辅助质量控制系统(CAQCS)中得到了成功的应用,表明它适于解决SPC中的异常模式的匹配问题,且有简单、快速和准确的特点。

基于改进BM算法的确定型有穷自动机的设计

通过对有穷自动机理论与BM算法进行分析,设计了一个基于改进BM算法的确定型有穷自动机的模型.该模型描述了向基于改进BM算法的确定型有穷自动机输入文本字符串,自动机输出TRUE,说明文本串中存在与模式串相匹配的字符;自动机输出FALSE,说明文本串中不存在与模式串相匹配的字符串.并给出了对比实验及分析.

工程图尺寸标注识别的研究与实现

本文提出了一个识别与理解工程图尺寸标注的算法．根据国标ＧＢ４４５８－８４的规定，尺寸标注可分为２７种模式和４８种子模式．本文提出了箭头匹配的概念，总结了９种箭头匹配模式和１５种箭头匹配的前趋分析模式．一个基于９种箭头匹配模式的网状文法被用于描述尺寸标注，文中给出了与之相对应的有限确定自动机ＤＦＡ及尺寸标注识别的实例．

正则表达式匹配引擎性能分析

正则表达式具有强大的描述能力,在计算机领域,正则表达式匹配技术应用十分广泛。目前,已经有多个正则表达式匹配引擎,在实际应用中,对于不同的匹配规则集和正则语法,不同的匹配引擎会有不同的性能表现。本文通过对PCRE、Greta、Boost、RE2四种常用正则表达式匹配引擎的性能测试,给出在不用的正则语法情况下的匹配速度,并深入分析不同坏境下适用的正则表达式匹配引擎。对实际系统设计中正则表达式库的选择有指导意义。

深度包检测中一种高效的正则表达式压缩算法

提出一种基于确定的有穷状态自动机(deterministic finite automaton,简称DFA)的正则表达式压缩算法.首先,定义了膨胀率DR(distending rate)来描述正则表达式的膨胀特性.然后基于DR提出一种分片的算法RECCADR(regular expressions cut and combine algorithm based on DR),有效地选择出导致DFA状态膨胀的片段并隔离,降低了单个正则表达式存储需求.同时,基于正则表达式的组合关系提出一种选择性分群算法REGADR(regular expressions group algorithm based on DR),在可以接受的存储需求总量下,通过选择性分群大幅度减少了状态机的个数,有效地降低了匹配算法的复杂性.

基于正则表达式的深度包检测算法

在深入分析了DFA状态数对算法性能影响的基础上,提出了一种新的基于正则表达式的深度包检测算法,该算法保证在任意有限的系统资源下算法的时间复杂度空间复杂度最小。在Linux下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量检测实验。结果表明,与已有的正则表达式算法比较,该算法的时间复杂度和空降复杂度最小。

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

随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的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%.

一种快速高效的模式匹配算法的应用研究

提出一种高性能的模式匹配算法——MAC算法,它通过使用从确定性有限状态机(DFA)中得到的特征等同态,在保证高速匹配的前提下,极大地减少了内存需求。同时,该算法具有高度的灵活性,即通过调整就可以适应不同的特定性能和资源限制的要求。在软件使用环境中的实验结果表明,MAC算法的内存使用性能相对目前先进的模式匹配算法提高了1.51～2.40倍。

基于多模式匹配的数字识别有限自动机的设计

基于有限自动机的多模式匹配算法(DFSA算法),设计出同时识别多种数的有限自动机。并给出便于实现的状态图和关键c++代码。

面向用户意图的SQL注入检测方法

Web程序安全的首要威胁是SQL注入攻击,动态分析技术可有效防御此类攻击.提出面向用户意图的检测方法,在程序发布前预先定义Web程序期望的所有数据库操作,在运行时拦截提交至数据库的操作,阻止不符合意图的操作.设计并实现描述数据库操作意图的语言SQLIDL,将开发者提供的允许操作集合解释为以确定有限自动机(DFA)表示的字符串集合,并支持表名、列名、列值及存储过程名的正则表示.在Securi Bench测试集的实验表明,该方法可有效检测现有SQL攻击模式且运行开销较小.

基于分布式存储的正则表达式匹配算法设计与实现

深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中。基于正则表达式的模式匹配算法已成为实现DPI的重要方法之一,传统的正则表达式匹配算法的时间复杂度较高,不能实时进行网络安全的防护。为了提高正则表达式匹配算法的实时性,提出一种基于分布式存储的正则表达式匹配并行算法,该算法通过对数据进行步长计数,采用分布式存储,实现了并行处理。实验分析表明,与传统的串行算法相比,该算法匹配速度至少提高5倍,能够有效降低算法时间复杂度,提高匹配效率。

深度包检测中一种正则表达式匹配算法的改进

网络数据包内容检测技术已在网络安全、网络监视、HTTP负载均衡等方面得到广泛的应用,因此,对快速数据包内容的检测就变得异常重要。在数据包内容检测过程中,数据包的净载数据要通过一系列已经定义好的正则表达式模式进行数据匹配。在此,阐述目前数据包检测存在的问题,如传统数据包检测应用程序要求很大的内存空间去存储相应的正则表达式模式,提出一种大大降低对内存空间使用的改进算法。通过将该改进算法应用到以DFA为基础的包检测应用程序中,说明经过真实网络数据来检测算法的改进成果。结果表明了改进算法的有效性。

基于正则表达式的协议识别方案

随着网络服务大量使用随机端口号,传统的基于端口号的协议识别方法不再适用。设计了一种基于正则表达式的协议识别方案。将NFA匹配引擎转换为DFA匹配引擎,提出了构造最优DFA状态数的算法,该算法保证在任意有限的系统资源下具有最小的时间复杂度和空间复杂度。

基于FPGA改进电路的高性能正则表达式匹配算法

针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列（FPGA）逻辑电路的改进确定有限自动机（DFA）匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机（NFA）方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。

一种快速且节约存储器的多模式匹配算法

同时对数百个模式进行比较的多模式匹配算法是入侵侦测/预防系统的一项关键技术.但是在Gbps级的高速网络中,多模式匹配速度仍是一个瓶颈.提出一个基于确定性有限自动机(DFA)的算法,能在一个周期内处理多个字符.该算法将DFA的头部抽取出来,构造一个子DFA,称为HeadDFA(HDFA),将其余部分构成另一个子DFA—GeneralDFA(GDFA).针对这两个子DFA,分别设计了两套硬件,并让它们同时运行,然后根据当前状态和各自的匹配情况决定取用哪套硬件的结果.这样不仅可以提高匹配速度,还可以利用两个子DFA之间的联系较大地减小其存储需求.

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

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

网络入侵检测中多模式匹配的状态编码方法

为了减少网络入侵检测系统的硬件实现方案中自动机占用的存储容量,提出了一种自动机状态的编码方法。该方法通过对自动机状态重新进行编号,使得多个状态能够用一个通配编号来表示,这样自动机中具有相同输入和下一状态的多条变迁就能被聚合为一条,大大减小了需要存储的变迁数目。可以证明状态编码方法能够将变迁数目减小到理论上最小值同时保证自动机恒定的处理速率。实验表明,对于常见特征串集,该方法可以将变迁数目减小98.9%以上。