基于AC自动机匹配算法的入侵检测系统研究

基于特征的网络入侵检测系统性能与其所采用的匹配算法息息相关。本文对当前入侵检测系统中几种典型的匹配算法进行了分析，并指出了这些算法在入侵检测系统应用中存在的不足，同时，给出了完整的基于AC自动机匹配算法的入侵检测系统方案，理论分析和实验结果表明该系统能够实施快速高效的入侵检测。     

多模式匹配算法研究和优化

模式匹配在网络安全领域有着重要的应用,随着网络环境的日益复杂,模式集合也随之增加.如何高效处理千万模式集下的字符串匹配成为网络安全的瓶颈之一.本文针对多模式匹配算法AC算法和WM算法进行了研究,采用了新型基于层次扫描和子节点数目搜索的双数组AC算法;从hash函数的选取和模式串的Tree树存储对WM算法进行了优化.能有效减少系统的内存占用,提高匹配效率.     

一种面向入侵检测的改进AC算法

在研究入侵检测系统中AC算法应用3的基础上,提出一种改进的AC算法--双重压缩AC算法.在算法中设计了新的AC状态自动机存储空间压缩方法,并给出与之对应的匹配流程.在Snort中进行测试,测试结果显示双重压缩AC算法的空间和时间性能比基本AC算法分别提升了52.2%和73.5%.     

一种基于访问频率的非结构化P2P复制策略

旨在通过数据复制来提高非结构化P2P系统的数据访问效能,提出了基于访问频率的复制策略—AFRE算法,该算法通过赋予不同时间片的访问记录不同的权重,计算数据的局部访问频率,并将适量的数据副本放置到节点度较大的节点.实验证明,提出的复制策略在副本总数明显减少的情况下,能够获得较好的平均查询长度及优于其他常用复制策略的查询成功率.     

一种基于Aho-Corasick算法改进的多模式匹配算法

目前互联网中以文本存在的数据非常庞大,针对在如此庞大的文本中如何准确、快速地找到多个不同的目标字符串的问题,在介绍常见的模式匹配算法的优点和缺点基础上,结合Trie速多模式匹配算法。根据对比性实验的结果分析得出,改进AC且匹配速度大约是AC算法的5倍,说明改进AC     

双向AC算法及其在入侵检测系统中

经过众多伟大科学家不断地研究,我国在算法领域有了进一步的发展,当前相关的科学家已经在经典的多模式字符串匹配算法-AC算法的基础上提出了双向AC算法。这种双向算法的提出能够在预处理阶段建立正向和反向两种状态的自动机,这种自动机在扫描的过程中使用正向有限自动机从中间向右进行,而反向有限自动机从中间向左进行。这种算法与之前相比具有更高的效率,因此得到了更广泛的使用。     

基于时间自动机的Ad hoc网络入侵检测

该文提出一种基于时间自动机分布式合作的入侵检测算法。首先,将整个网络分为子区域,每一区域随机选出簇头担任监视节点,负责本区域的入侵检测。其次,按照路由协议构筑节点正常行为和入侵行为的时间自动机,监视节点收集其邻居节点的行为信息,利用时间自动机分析节点的行为,识别入侵者。该算法不需要事先进行数据训练并能够实时检测入侵行为。最后,通过模拟实验证实了算法的有效性。     

一种基于超节点和能量优先的无线传感器网络的高效查询算法

文中提出一种基于超节点和能量优先的无线传感器网络的高效查询算法.该算法包括传感器节点的层次聚类算法及基于能量代价模型等支撑技术,主要解决了以下两个问题:(1)数据如何从传感器节点传送到汇聚节点;(2)通过对传感器节点进行聚类,形成超节点,使得在查询过程中减少对无关节点的访问.实验表明该算法在提高无线传感器网络查询效率的情况下,延长网络的使用寿命.     

一种基于用户轨迹的跨社交网络用户身份识别算法

针对现有的基于用户轨迹的跨社交网络用户身份识别算法未考虑用户轨迹中的位置访问顺序特征的缺点,该文提出一种基于Paragraph2vec的跨社交网络用户轨迹匹配算法(CDTraj2vec)。首先将用户轨迹转化为易于处理的网格化表示,并按照一定的时间粒度、距离尺度对原始的用户轨迹进行划分,使用户轨迹中的位置访问顺序特征易于抽取;然后利用Paragraph2vec算法中PV-DM模型抽取轨迹序列中位置访问顺序特征,得到用户轨迹的向量表示。最后通过用户轨迹向量判定轨迹是否匹配。在社交网络BrightKite上的实验结果表明,与基于位置访问频率或者基于轨迹间距离的方法相比,F值提高了2%～4%个百分点,所提算法能够有效地抽取出用户轨迹中的位置访问顺序特征,更加准确地实现了基于用户轨迹的跨社交网络用户身份识别。     

基于ASIFT的图像快速匹配算法

ASIFT特征在图像旋转、尺度变换和视角变化的条件下具有良好的不变性,较传统的SIFT算法具有完全的仿射不变性,且在图像配准中能够获得更多精确的匹配点。但是,ASIFT匹配效率比较低,耗时较长。基于ASIFT的图像快速匹配算法是结合基于BBF查询机制的KD-Tree索引的近似最近邻搜索即先建立数据集索引,然后进行快速匹配的算法。实验结果表明,改进的算法比传统的ASIFT图像匹配算法和SIFT匹配算法在匹配速度、匹配精度方面优势明显。     

基于多维有限自动机的DFA改进算法

多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA, multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1~2个数量级。     

一种无匹配时间损耗的DFA压缩算法的研究与实现

高性能深度包检测系统使用确定型有穷自动机DFA（Deterministic Finite Automata）来执行数据包的检测过程.然而,DFA所带来的存储消耗问题使其难以适用于片内资源稀缺的FPGA.目前已存在多种算法着眼于解决DFA的空间爆炸问题,但是其在带来较好压缩率的同时,也在一定程度上影响到了系统的检测速度.本文提出了一种无匹配时间损耗的DFA压缩算法,并在此基础上,基于FPGA硬件平台,设计实现了单个DFA匹配引擎.实验测试结果表明,本文所设计的算法,在未影响整个系统匹配性能的前提下,可以实现10%~30%左右的压缩率.     

FilterFA: a multiple string matching algorithm based on specification of character set

Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O(|P||Σ′|). Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%.     

基于特征描述子的匹配方法

利用一种效率和匹配率均较高且存储空间小的基于特征描述子的指纹识别算法,实现了指纹匹配且可应用到嵌入式系统。由于自动指纹识别系统一般在嵌入式系统上实现,对算法的复杂度、运算速度、存储空间需要等均有较高要求,因此选用普遍使用的基于细节特征的匹配算法。该算法运算速度快,一幅300×300像素的指纹图像,仅需几十个特征向量。实验证明,算法克服了点匹配计算量大、速度慢和参考点确定难等缺点,且对图像的旋转和平移具有较好的鲁棒性。可以使基于特征描述子的随机局部区域描述子特征的匹配性能进一步提高。     

HashTrie：一种空间高效的多模式串匹配算法

The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths.     

一种大容量模式匹配算法

模式匹配技术是入侵检测与信息监管等网络应用的重要手段。针对现有模式匹配算法在大规模模式集下无法支持高速处理的情况,提出了一种两级三态内容可寻址寄存器（TCAM）的模式匹配算法。利用TCAM特性,提出一种子串编码方法压缩表项空间,提高空间利用率。通过性能分析和实验仿真表明,算法在支持大容量模式库的同时,可以获得较高的搜索速率。     

字典学习中字典尺度对DICOM图像压缩的影响

随着医院数字化医疗进程的加快,医学影像的数据量日益增大,医学影像资料的存储空间和获取速度受到很大的限制。文章在研究主流字典学习算法基础上,提出使用不同尺度的MOD、K-SVD、ILS-DLA、RLS-DLA字典算法对DICOM图像进行压缩存储,以及恢复再现的方法。与经典的JPEG和JPEG2000压缩算法相比,字典学习算法压缩和恢复效果较好,特别是采用较小尺度的字典时,压缩效果更为突出:当压缩比为20时,采用4×4尺度的RLS-DLA字典,论文算法的峰值信噪比(PSNR)较JPEG算法高出7.8dB,比JPEG2000算法高出1dB。     

基于多尺度分析的快速相位立体匹配

基于相位的立体匹配是双目投影光栅相位法中的重要步骤,但传统的相位匹配方法在处理高分辨率图像时因存储空间大大增加,难以达到匹配速度与精度的平衡。文章提出了一种基于多尺度分析的快速相位立体匹配算法,采用分层匹配的策略,对预处理后的左右绝对相位图进行降采样以生成图像金字塔,利用低分辨率的视差匹配结果以预测下一层视差,以此降低下层高分辨率图像的视差搜索范围,达到匹配速度与精度的平衡。实验结果表明,所提算法在保证精度的情况下能有效提升相位立体匹配速度,实现高分辨率相位图快速准确的立体匹配。     

Minimizing data access latency in data grids by neighborhood‐based data replication and job scheduling

In Data Grid systems, quick data access is a challenging issue due to the high latency. The failure of requests is one of the most common matters in these systems that has an impact on performance and access delay. Job scheduling and data replication are two main techniques in reducing access latency. In this paper, we propose two new neighborhood‐based job scheduling strategies and a novel neighborhood‐based dynamic data replication algorithm (NDDR). The proposed algorithms reduce the access latency by considering a variety of practical parameters for decision making and the access delay by considering the failure probability of a node in job scheduling, replica selection, and replica placement. The proposed neighborhood concept in job scheduling includes all the nodes with low data transmission costs. Therefore, we can select the best computational node and reduce the search time by running a hierarchical and parallel search. NDDR reduces the access latency through selecting the best replica by performing a hierarchical search established based on the access time, storage queue workload, storage speed, and failure probability. NDDR improves the load balancing and data locality by selecting the best replication place considering the workload, temporal locality, geographical locality, and spatial locality. We evaluate our proposed algorithms by using Optorsim Simulator in two scenarios. The simulations confirm that the proposed algorithms improve the results compared with similar existing algorithms by 11%, 15%, 12%, and 10% in terms of mean job time, replication frequency, mean data access latency, and effective network usage, respectively.     

一种新的基于值函数迁移的快速Sarsa算法

知识迁移是当前机器学习领域的一个新的研究热点.其基本思想是通过将经验知识从历史任务到目标任务的迁移,达到提高算法收敛速度和收敛精度的目的.针对当前强化学习领域中经典算法收敛速度慢的问题,提出在学习过程中通过迁移值函数信息,减少算法收敛所需要的样本数量,加快算法的收敛速度.基于强化学习中经典的在策略Sarsa算法的学习框架,结合值函数迁移方法,优化算法初始值函数的设置,提出一种新的基于值函数迁移的快速Sarsa算法--VFT-Sarsa.该算法在执行前期,通过引入自模拟度量方法,在状态空间以及动作空间一致的情况下,对目标任务中的状态与历史任务中的状态之间的距离进行度量,对其中相似并满足一定条件的状态进行值函数迁移,而后再通过学习算法进行学习.将VTF-Sarsa算法用于Random Walk问题,并与经典的Sarsa算法、Q学习算法以及具有较好收敛速度的QV算法进行比较,实验结果表明,该算法在保证收敛精度的基础上,具有更快的收敛速度.