1-Way Multihead Quantum Finite State Automata

1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has been shown by Moore and Crutchfield as well as Konadacs and Watrous that 1QFA can’t accept all regular language. In this paper, we show different language recognizing capabilities of our model 1-way multihead QFAs. New results presented in this paper are the following ones: 1) We show that newly introduced 1-way 2-head quantum finite state automaton (1QFA(2)) structure can accept all unary regular languages. 2) A language which can’t be accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition of language.

Xgadget:基于动静结合的二进制Gadget搜索

代码复用技术一直以来都是软件安全研究领域的热点,ROP(return-oriented programming)、JOP(jump-oriented programming)和DOP(data-oriented programming)技术是典型代表。Gadget搜索是代码复用的基础,针对现有静态搜索算法存在支持的Gadget类型不多,不能同时搜索动态链接库等问题,提出了基于动静结合的二进制Gadget搜索方法,基于此开发了搜索工具Xgadget。利用动态映像级插桩,对所有函数进行反汇编;设计了Token级和指令级有穷自动机,实现了基于自动机的静态搜索算法;在五款应用程序中对其进行了测试与评估。实验结果表明,算法支持ROP、JOP、DOP等多种Gadget类型的搜索,能够同时对目标程序动态链接库进行搜索,搜索数量是ROPgadget的12.5倍,单位指令搜索时间较之降低32.1%。算法为不同需求的代码复用提供更为广泛的支持,且输出结果是二进制Gadget,后续复用更直接,有利于代码复用自动化利用。

一种新的DFA状态最小化算法

提出了一种基于状态转换矩阵的适合计算机实现的DFA状态最小化算法,在计算等价状态过程中,通过记录扫描过程中发现的具有相同输入字符和相同转换状态的状态判定链表,算法可以用一遍扫描和与传统算法相近的存储空间实现DFA状态的最小化。与传统的DFA状态最小化算法相比,该算法具有较好的时间复杂度和相同的空间复杂度。

使用DFA的Web会话构造方法

会话识别是Web使用挖掘数据预处理中重要的一个环节。将确定的有限自动机(DFA)思想运用于会话构造,针对一段用户访问日志,通过DFA中各个状态间的转换,实现会话构造。该方法更多考虑页面之间的连续性,关注用户的实际访问序列,有利于后续的用户访问模式的挖掘。

识别幺半群强半格的最少状态DFA

为了研究识别幺半群强半格的最少状态DFA,对幺半群强半格的R类进行了深入探讨,证明了当每个幺半群中只有一个R类时,幺半群强半格中的R类的个数就是幺半群的个数,且半群中的R类是正规语言中的一种右不变等价类.借助这两个结论,证明了识别幺半群强半格的最少状态DFA的终结状态的个数等于幺半群的个数,并建立了识别幺半群强半格的最少状态DFA.

一个完善的基于判定链表的DFA最小化算法

应用判定链表进行DFA最小化方法中只处理无互相依赖等价状态会造成最小化结果不正确。针对此问题,分析了DFA中状态的k次传递等价、含自回路状态的等价以及互相依赖等价等结构特点,将分析结果应用于DFA最小化算法中,提出了一个完善的基于判定链表的DFA最小化算法。该算法涵盖所有等价状态的链表处理,与传统的分割或合并算法的最小化结果一致,保证了基于判定链表的最小化结果的正确性。

面向深度包检测的DFA细粒度并行匹配方法

确定性有限自动机(DFA)是实现正则表达式匹配的一种有效手段,但DFA的状态跳转是串行的,导致匹配速度慢、难以满足高速骨干网环境深度包检测(DPI)的性能需求.提出了一种称为LBDFA(Loopback DFA)的细粒度并行化状态跳转方法,通过将在Loopback状态上的连续跳转并行化,提高了匹配速度.此外,利用Bloom filter消除该并行跳转中的临时偏离现象,进一步提高了并行潜力.在L7-filter以及Snort规则集上的测试结果表明,LBDFA能够满足10Gbps以上的正则表达式匹配需求.

一种针对DFA状态爆炸的正则表达式匹配方法

针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。

基于改进的Trie树和DFA的敏感词过滤算法

通过对文本内容中敏感词过滤方法及相关技术的研究,提出了一种基于改进的Trie树和DFA的敏感词过滤算法,解决了敏感词过滤技术中的人工干扰、分词障碍等关键问题,提高了文本中敏感词过滤的准确性和有效性。提出的算法包括三个步骤:基于排列组合的数学原理对中文词向中拼混合词进行扩充;采用改进的Trie树结构来存储DFA的所有状态,构建敏感词树;根据构建的敏感词树结构以及采用最小匹配规则对文本内容中的敏感词进行检测和过滤。通过分析得到构建敏感词树算法的时间复杂度为O(n×len),敏感词检测及过滤算法时间复杂度为O(L)。实验结果表明,本算法其查准率为100%,查全率约为87%~100%。

基于DFA复合式Agent模型的设计与实现

针对机器人团队协作检测与跟踪动态目标的需要,提出1种基于有限状态自动机(DFA)的复合式Agent模型。通过结合有限状态自动机的行为状态模型,对复合式Agent模型进行改进,在固定路线的动态目标跟踪实验中,对改进前后的Agent模型实际实验数据进行比较,并将该模型应用于基于区域的多机器人多目标跟踪实验中。结果表明:改进后的Agent模型通过有限状态自动机中的状态抽象,不仅从目标检测与跟踪的角度提高了Agent个体性能,还从社会的角度,提高了群体团队的协作性能;提出的模型通过行为状态模型将动作、决策等与环境信息进行了有效的分离,从而具有较好的可移植性和高扩展性;改进后的Agent模型跟踪偏差期望值与样本方差均降为改进前的一半,为实时的目标协作检测与跟踪提供了有效途径。

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

提出一种基于确定的有穷状态自动机(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模式集合的网络数据包进行了大量检测实验。结果表明,与已有的正则表达式算法比较,该算法的时间复杂度和空降复杂度最小。

面向存储的正则表达式匹配算法综述

正则表达式匹配是当前深度包检测领域中的关键性技术。介绍了面向存储的正则表达式匹配算法的基本思想和设计方法,给出了算法分类并比较了典型压缩算法间的差异,分析了正则表达式语法对算法设计的影响,最后论述了目前研究中面临的技术难点并对今后算法设计的发展趋势作了展望。

网络流量分析系统的设计与实现

随着网络速度的不断增长及网络应用的不断增多,网络监管的难度大大增加。实现了一种高速网络流量的实时监控系统NTAS——网络流量分析系统。通过PF_RING底层报文捕获模块,捕获网络流量,并对网络流量进行完整会话管理以及在此基础上基于有穷自动机(DFA)的协议识别,解决了同类系统性能不足和协议识别率不高的问题。最后给出了NTAS与同类系统的比较测试。测试结果表明,NTAS具备在高速网络环境下对网络流量的实时分析处理的能力。

基于稀疏矩阵存储的状态表压缩算法

正则表达式匹配对于网络安全应用至关重要。将稀疏矩阵和索引表引入确定的有限自动机的状态转换表,提出了一种稀疏矩阵索引的状态压缩表算法,并给出了稀疏矩阵和索引表的构造方法。而后同字母压缩表算法结合,给出了该算法的优化策略。最后在实际规则集上进行评估,实验结果证明了算法的压缩效果,并进一步得出了算法的适用范围。

基于云模型的网络系统状态评估与预测模型研究

目前,国内外众多网络系统可生存性研究都主要集中在理论上的研究,且均使用经典的数学理论来研究复杂多变环境下的网络系统状态,也没有形成完整的理论体系,而实际上网络系统状态具有不确定性、随机性等特性。以可信网络的可生存性为研究背景,首先分析了网络可生存性等关键问题。考虑到网络系统状态具有不确定性、随机性等特征,引入云模型和有限状态机理论对网络系统状态来进行描述和检测,提出了基于云模型的网络系统状态评估与预测模型,并从理论上进行了具体的分析和求证。最后通过仿真实验与分析,进一步说明了本研究的模型的可行性与合理性,为当前错综复杂的网络系统的可生存性研究提供了一种有价值的新思路。

基于规则模板的正则表达式分组算法

采用规则分组的方法解决确定型有限自动机（Deterministic Finite Automata,DFA）状态爆炸问题,随着分组数目的增加,匹配效率大大降低.本文提出正则表达式的输入驱动特性理论,并基于此提出了基于规则模板的分组算法——模板有限自动机.模板有限自动机算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎.理论分析和实验表明,与典型的DFA改进算法相比,预处理时间和存储空间有2~3个数量级别的缩减,且匹配效率没有明显降低.

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

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

基于模板有限自动机的正则表达式匹配算法

采用规则分组的办法解决DFA状态爆炸问题,随着规则数目的增加,空间压缩效率大大降低。针对此问题提出了模板有限自动机分组算法。该算法基于规则模板对规则集进行分组,各分组分别构建匹配引擎;同时,根据实际规则数目和系统结构改变规则子集的数目,达到更好的匹配效率。理论分析和实验表明,与传统分组算法相比,在存储空间压缩相当情况下,分组数目大大减少;与其他典型的DFA改进算法相比,预处理时间和存储空间有数量级别的缩减,且匹配速率没有明显降低。

一种高效匹配PCRE的扩展自动机

分析现有方法处理状态爆炸的局限性,将条件函数和位图结构引入自动机,提出一种位图移位有限自动机(Bs-FA),并给出由正则表达式到Bs-FA的一般方法。对计数字符组与前缀交迭的情况,仅需引入较小位图空间,就能使整个自动机内存空间明显减少。在实际规则集上评估,并与现有方法进行比较,说明该自动机的应用价值。