带通配符的多模式匹配算法

发布时间：2018-02-04 19:22

本文关键词： 多模式匹配 FFT 散列函数欧几里得距离　出处：《吉林大学》2017年博士论文　论文类型：学位论文

【摘要】：人们每天需要处理的信息量正快速增长。若要为所有授权用户保存这些信息时实现高机密性、完整性和可用性,则需要强大的技术和稳健的工具。而信息安全与管理工具直接取决于其算法的有效性和熟练度。多模式匹配算法主要用于大量信息处理和信息安全的应用程序,比如,入侵检测/预防系统、杀毒系统、数据挖掘应用和数据分析应用,这些应用都主要以多模式匹配算法为基础,都需要强大和高效的算法,从而可以同时准确搜索成千上万的模式,然后报告每个模式出现的位置。直接应用在非常长的字符串中逐一搜索成千上万模式的单模式匹配算法,不能算是高效的操作,特别是当我们处理大量信息时。必须开发高效的多模式匹配算法,不仅运行及时,而且不会对信息转化有任何延误。否则,安全或处理工具就会变成影响整个应用程序性能的瓶颈。多模式匹配被定义为如果一组k个模式P={p0,p1,p2...pk}的总长度为｜P｜,每个模式的长度为m。长度为n的文本t的串链都位于相同的有限字母集∑,这里,n、｜P｜0和n ≥m。如果模式p出现在文本t内,则它们决定其出现位置和出现次数。有许多技术用于改进模式匹配算法的性能,比如,主要采用一般线性乘积、位并行、压缩字符串、汉明距离、素数编码、正则表达式、散列函数和AC自动机等。带通配符的模式匹配算法可以视作一般线性乘积的特殊情形,可以按照布尔卷积或多项式卷积处理它。多项式卷积可以通过离散傅里.叶变换(Discrete Fourier transform,DFT)有效计算,主要包括四个步骤,即预处理、计算有两个多项式系数的DFT、对DFT结果做简单分量乘法、以及计算乘法乘积的离散傅里叶逆变换(Inverse Discrete Fourier transform,IDFT),如下所示。假设a和b是两个向量,长度为n,我们需要使用快速傅里叶变换(Fast Fourier Transform,FFT),即DFT及其IDFT,来计算这两个向量之间的卷积,因此,必须完成如下步骤:1、为a和b的末端都填补0,定义a'和b'为:a'=[a0,a1,...,an-1,0,0,...,0]Tb' =[b0,b1,...,bn-1,0,0,...0]T2、计算a'和b'的离散傅里叶变换:y = Fa' 和z= Fb'.3、乘以向量y和z,以分量方式定义简单乘积:y.z = Fa'.Fb'4、计算这个简单乘积的离散傅里叶逆转换:c=F-1(Fa'.Fb')结果c是向量α和b之间的卷积结果,可以在时间复杂度O(n log n)内予以计算。以上四个步骤被称为卷积定理,可以用于计算相同时间复杂度O(n log m)内的模式和文本之间的卷积,这里,n是较长向量多项式系数的数量或文本t的长度,而m是较短向量多项式系数的数量或模式m的长度。某些情况下,模式是长的,这时不能使用FFT以单机运算计算卷积。乘以大整数是展示如何把长模式变成小部分的良好示例,可以在单机运算中完成处理。散列函数是有效的计算函数,它把任意长度的二进制串映射成一些固定长度的二进制串,称为散列值,这里,一个散列值用作一个输入串的紧凑代表。计算上,散列函数无法找到两个不同的输入散列为相同的值。散列函数根据其所使用的运算主要有三种方案,前两种是通过除法散列和通过乘法散列,第三种是全域散列。在模式匹配中,散列值用于降低计算成本,模式和每个文本联配都散列成小数值,仅用于核查匹配。位并行算法以利用单机指令可以运算有w位的位向量为基础。如果一个算法的数据项可以压缩成w位,这个算法就可以通过在一个单机指令内处理许多数据,从而实现在时间和空间上有盈余。如下符号用于描述本文中所使用的主要基本位运算:(?)表示逐位"OR",''表示逐位"AND",'!'表示逐位"NOT",''表示向右移动位向量,''表示向左移动位向量,移动时,两个方向上都进行零填补。压缩串匹配技术以计算机字长w大于字母集字符log2α的事实为基础。单机字可以容纳至多α = w/log2α个字符。压缩串匹配保证可以把许多数据压缩成一个单机字,从而可以用单机指令进行运算。模式匹配算法中用作位运算指令的主要机器指令包括:逻辑指令、算术指令和控制指令。字符串匹配有特殊指令。字长匹配指令wsmatch(a,b)和字长计较指令wscmp(a,b)被认为是字符串匹配的重要特殊指令。特殊字长压缩串匹配指令以英特尔单指令多数据流扩展(streaming SIMD extension,SSE)技术为基础。最近,提出用中国剩余定理(Chinese Remainder Theorem,CRT)素数编码来改善带通配符的模式匹配的性能。开发多模式匹配算法时需要考虑许多问题,主要包括模式组大小、搜索文本大小、字母集大小、单个模式大小、模式字符大小写敏感性、算法攻击抵抗能力、搜索运行时间、不中断模式更新、最差大小写性能、以及是否存在通配符。比如,在入侵检测系统中,开发高效多模式匹配算法时的一个重要问题是更新签名时不中断入侵检测系统。这里所说的问题是由基于诸如AC自动机等结构化数据所引起的。最近,有许多让人有兴趣开发的模式匹配算法,分标准形式和非标准形式。非标准形式指的是模式、或文本、或两者都包括通配符,而通配符符号与字符集中的任何字符、包括其本身都匹配。本文中,我们研究了带通配符的多模式匹配问题。首先,介绍四种以往工作中作为主要算法的、带通配符的多模式匹配算法。这四种算法具有四种不同技术,依靠快速傅里叶转换(FFT)计算模式和文件间的卷积。前三种算法用于理论上与我们之前的三种算法进行比较,第四种算法用于实践上与我们之前的算法进行比较。第一种算法以计算模式和文件间的欧式距离为基础,在时间O(n log｜｜P｜+ooc log k)内运行,第二种算法以计算模式和文件间的汉明距离为基础,在时间Olog ｜P｜ log σ + occ log k)内运行,第三种算法以素数编码为基础,在时间O(n log m + ooclog0)内运行,这里m是最长模式的长度。第四种算法是克利福德算法的单模式匹配算法的重复,克利福德算法是带通配符的单模式匹配中最高效的算法之一,在时间O(k n log m)内运行。第二,我们提出了三种带通配符的多模式匹配算法。第一种算法以欧几里得距离和散列函数为基础,包括三个主要步骤:预处理、检查每个模式步骤的第一块、以及当第一块匹配时检查模式的剩余部分。在预处理步骤中,每个模式被划分成适合的长度为l的块,需要假设最短模式的长度也足以创建一个块。如果模式的最后一个部分不足以创建一个完整的块,那么最后一个块与前面一个块合并。分别计算模式py的第一个块和该模式剩余块之间的平方差之修正和。首先,每个模式和文本中的每个符号都用独一无二的整数以及带0的通配符进行编码。然后,计算第一个块by,l和by,q块之间方差值的修正和Rp[by.l,by,q],如下所示:Rp[by.l,by.q]值用作散列值H[by,l,by.q],用于检查剩余块的匹配。为了检查每个模式的第一块的匹配情况,计算模式的每个第一个块by,l和每个可能的联配文本t之间的方差之修正和,如下所示:如果块在位置i处匹配文本,那么和在位置I处等于零。如果模式py的块by,l匹配文本,那么模式py被视作部分匹配,还需要检查它的剩余块。为了检查部分匹配模式py的剩余块的匹配情况,假设块by,q是部分匹配模式py的一个剩余块,第一个块by,1在位置i处匹配文本;然后,需要检查位置i+(q-1)/处的块by.q的匹配情况。如果H[by1,by,q]=H[by,1,ti+(q-1)t],那么块by.q在位置i+(q-1)l处匹配文本,不带通配符,这里H[by,1,by,q]是by,l和by,q之间的散列值,而H[by,1,ti+(q-1)t]是by,1和文本在位置i+(q-1)l处的散列值。如果在模式的剩余匹配块中或者在文本中有通配符,那么有值会由于零通配符值而导致丢失。丢失的值可以使用分量乘法轻松予以计算,因为通配符的位置可以在编码步骤中予以保存。如果Rt'(j)[by.1,by.q]和Rp(j)[by.q,ti+(q-1)t]分别是由于文本中的通配符和模式by,q的剩余块的零值所导致的丢失值之和,那么如果下式成立,块by,q在位置i+(q-1)l处匹配带有一个通配符的文本。如果模式py的第一个块和所有剩余块都匹配文本,那么模式py有一个匹配。算法的预处理时间是O(｜P｜-lk),可以在时间O(k n log l+ o +d)内高效找到模式匹配,这里n是文本t的长度,l是块的长度,k是模式的数量,o是使用散列值匹配的块的数量,而d是使用模式和文本中的散列值匹配的块中通配符的数量。我们的算法的主要优点是:(1)可以有效找到长模式的匹配;(2)如果字母集大小σ较长,该算法也很有效;(3)支持不中断模式更新。第二种算法以位并行为基础。除预处理步骤外,该算法还包括两个主要过程。第一个过程构建文本符号的位向量,称为"更新文本字符阵列tbv[i + ml]的位向量"。第二个过程计算汉明距离,称为"更新结果阵列R[i][y]的位向量"。为了保证移动过程中每次只处理一个字符,一个长度为w的移动窗口沿着文本移动。更新结果阵列R[i][y]的位向量在移动窗口的左端、文本的位置i处发生,而更新文本字符的位向量在移动窗口的右端、文本的位置i+ w处发生。在预处理步骤,构建模式字符Pbv[][]的位向量和模式字符(fp[][])的发生位置。这里,ind[][]是用于为发生模式的字符进行索引的一个阵列。在更新文本字符的位向量时,字母集的每个字符都有两个参数,即文本字符位向量tbv[]和字符lp[]的最后一个发生位置。字符的最后一个发生位置是一个整数,表明阵列tbv[]中文本字符位向量的最后一个更新位置。文本字符位向量更新在滑动窗口的右端、文本的位置i+ w处发生。当i = 0时,字符t[w]的位向量应该在位置w处更新,从而构建了第一个W文本字符的位向量。在移动窗口的每个移动过程中,移动窗口移动1,字符x进入移动窗口,对字符x tbv[t[i+ ml]]的位向量进行更新。可以按照如下方式完成字符更新过程。字符xtbv'[t[i+ml]]的第一个当前位向量根据当前位置和字符x(i+ ml-1p[t[i + ml]])的最后一个更新位置之间的差值移动到左侧。通过用无符号整数1的OR运算移动的当前位向量,增加窗口中字符x的位。然后,位向量及其发生位置分别存储在tbv[t[i+ ml]]和1p[t[i + ml]]中。在更新结果阵列位向量时,假设移动窗口按照1进行移动。在移动窗口的左侧,在位置i处有一个字符已经离开移动窗口。假设这个已经离开移动窗口的字符是字符x,它的文本位向量用于对所有模式更新阵列R[i][y]的位置i处的位向量,这些模式就包括字符x。这个过程如下所示。首先,字符.x的当前文本位向量根据当前位置和最后一个更新位置(i-lp[t[i]])之间的差值移动到左端。假设字符x在模式py中发生,字符x的第一个发生位置是文本的.fp[y][x]处。然后,字符.x的文本位向量移动fp[y][x],到达右端。接着,在文本位向量tbv[t[ii]和模式位向量pbt[y][x]之间完成aND(即"")位运算。把位向量结果通过在阵列R[i-fp[y]M][y]的位置(i-fp[y][x],j)处的位向量进行OR运算而加到结果阵列中。然后,如果位向量R[i-fp[y][x]][y]和模式py !pb[y][*]的通配符位向量的补码相同,那么模式py在位置i处匹配文本。该算法可以在O(n + d(n/σ)(m/w))时间内有效查找模式匹配,克服了发生高百分比通配符的问题。第三种算法以压缩串和位并行为基础。主要原理是把文本的每一个α=w/og2a符号压缩成一个单机字,用作沿着整个文本移动的移动窗口。在每个移动步骤中,移动窗口的压缩串与所储存模式的压缩串进行比较。除预处理步骤之外,该算法包括两个主要步骤:移动窗口更新过程和比较过程。假设机器字w的大小是标准尺寸(即32或64位)。然后,每个机器字可以包括至多α = W/log2 σ个字符,这里,σ是字母集大小。γ=log2σ是用于编码字母集的单个字符的位数。在预处理步骤中,文本和模式的每个符号都被编码成独一无二的整数,而通配符都被编码成0。所有模式字符都压缩成一个机器字。假设每个模式都可以编码成单个机器字(即mα),因此,每个比较过程花费的时间都只有O(1)。压缩过程通过移动以及OR位运算来执行。串结果存储成压缩串模式。我们以同样的方式压缩文本字符。首先,带有字符尺寸α = w/;log2σ的移动窗口沿着文本t移动。压缩前面α个字符,然后比较移动窗口的压缩串与模式的压缩串。比较过程可以按照如下方式完成。首先,计算模式py压缩串的补位,然后在模式py的压缩串和移动窗口压缩串之间的位置i处执行AND位运算,这里通配符的字位都是0。如果结果字位都是0,就意味着在文本位置i处有模式py匹配。当然,匹配可能是伪匹配。另一个过程用于复查,通配符的位都改成1,在模式压缩串补位和移动窗口压缩串之间执行OR运算。如果结果字位都是1,那么模式py有匹配。请注意,在AND位处理中,通配符的位都是0,而在OR位处理中,通配符的位都是1。当无法把模式压缩成单个机器字时(即mα)需要另一个过程来检查部分匹配模式的剩余部分的匹配。
[Abstract]:......
【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：TP391.1

【相似文献】