《-第8章 恶意代码检测用匹配算法》由会员分享，可在线阅读，更多相关《-第8章 恶意代码检测用匹配算法（34页珍藏版）》请在金锄头文库上搜索。
1、本章学习目标 理解单模式匹配算法 掌握多模式匹配算法 理解HASH算法 本章内容 模式匹配算法概述 经典单模式匹配算法 多模式匹配算法 HASH算法 章节实验 1 模式匹配算法概念 查找的速度是评价一个查毒引擎的关键因素之一。 算法种类： 单模式匹配算法：KMPQSBM等 多模式匹配算法：DFSA基于二叉树的算法 问题描述 设待处理（动态）文本为 单模式匹配是从文本中查找一个模式串 多模式匹配就是通过一次查找从文本中发现多个P1,P2,.,Pq n tttT 21 = n21 xxxPi= 2 经典单模式匹配算法 查找过程的两个部分： 匹配过程（字符比较） 后移过程 加速单模式匹配算法的关键：
2、 (1) 尽量加快“匹配过程”的完成速度 (2) 使“后移过程”的步骤尽量大 经典算法 BF KMP BM QS 最简单的查找算法BF算法 Brute-Force算法匹配过程 KMP算法 KMP算法在预处理阶段的时间复杂度为 ，查找过程实际平均复 杂度为，最坏情况下的时间复杂度为 )(mO )(mnO+ )2( nO BM算法 bad-character位移，字符a在P中出现 bad-character位移，字符a在P中不出现 计算公式 Pa 1 10|min bm_bca = = 否则 中出现在模式如果且 m ajmPmjj good-suffix位移，只有u的前缀v在P中重现 good-s
3、uffix位移，u的一次重现且其前一个字符与b不同 首先定义两个条件： cond1(j,s): 对每个k, jkm, s k 或者Pk-s=Pk cond2(j,s):如果 s state2 模式集合he，she，his，hers she si sreh h,s 0 98 76 5 4 3 21 (2) 失效函数f 当发生字符失配时，失效函数指明下一个应处理的状态。规定： 所有第一层状态的失效函数； 对于非第一层的状态s，若其父状态为r（存在某个字符a, g(r,a)=s），其失效函数为，状态 为追溯状态s的祖先 状态所得到的最近一个使存在的状态。 s123456789 f(s)0001203
4、03 0)(=sf ),()( * asfgsf= * s ),( * asfg (3) 输出函数output Output(s) = 根节点到叶子节点路径上字符组成的字符串 当f(s)=s时， output(s) U= output(s) s2579 output(s)heshe, hehishers 2. DFSA算法的查找过程 （1） 从有限自动机的0状态出发，逐个取出P中模式Pk中的字符c，并按转向函 数g(s, c)或失效函数f(s)进入下一状态。 （2） 当输出函数output(s)不为空时，输出output(s)。 用有限自动机扫描文本串“ushers”的过程： 开始为0状态，因
5、g(0,u)=0，g(0,s)=3，g(3,h)=4，g(4,e)=5，而output(5)=he，she， 故输出he，she； 因f(5)=g(f(4),e)=2，g(2,r)=8，g(8,s)=9，output(9)=hers，故输出hers。 即文本串“ushers”中含有he，she，hers这三个模式串。 she si sreh h,s 0 98 76 5 4 3 21 基于有序二叉树的 多模式匹配算法（SMA） DFSA的缺点： 在树的构造过程中，不能预先知道每个节点有几个子节点 传统算法的转向、失败和输出表也需要大量的空间 传统算法在构造过程中，没有对模式串进行排序 SMA的优
6、点 提高构造速度 提高查找速度 便于动态增删模式串 不用额外的转向、失败和输出表 SMA的构造 算法算法 有序二叉树的构造有序二叉树的构造 输入：输入：模式串集合 输出：输出：有序二叉树、输出节点和父状态节点指针 Begin for each pattern do p=root; i=0; while( (p=goto(p, patterni)!=NULL ) i+; 在p处插入相应的patterni:strlen(pattern); End. 算法算法 goto(p, char) 输入：输入：节点p, 字符char 输出：输出：相应的子状态 Begin if ( (charp.Rchar)
7、if (patterni=p.Rchar) return p.Rchild; else return NULL; 算法算法 失败指针的确定失败指针的确定 输入：输入：有序二叉树，根节点是root; 输出：输出：标注了失败指针的右序二叉树 Build_Fail_Func(Structure Node s) Begin 按上述原则标注节点s的失败指针； Build_Fail_Func(s. Lchild); Build_Fail_Func(s. Rchild); End SMA的查找 算法算法 模式匹配算法模式匹配算法 输入：输入：文本串string= a1a2 an. 根为root的有序二叉树。
8、 输出：输出：各个模式以及它们在文本string中出现的位置 p root; for i 1 until n while ( (p=goto(p, ai ) = NULL ) do p p.failstate; if (p.output) print i; print p; if(p.failstate.output) print p.failstate SMA实例 根据模式集合he, hers, his, hour, she, our 构造的有序 二叉树 0 2 13 10 1 3 14 11 7 5 4 15 12 8 6 9 h e r s u o s i o u r r e h s 查
9、找文本串“ushers”的过程如下： 从根root开始，goto(root, u)=0. goto(0, s)=13. goto(13, h)=14. goto(14, e)=15. 此时输出节点15，也就是输出she，同时输出节点 2，也就是输出he. 接下来，状态节点15的失败指针指向状态节点2. goto(2, r)=3. goto(3, s)=4. 此时输出状态节点4, 也就是输出hers. 此时查找过程 结束。 4 HASH算法 能够以线性速度匹配在源文件中一次性定位多个模式串的另一个 有效数据结构是HASH算法。当模式串的数量达到一定数量的时 候，即使数量再增长，总体需要的时间也不
10、会明显增加。 假设词典是由如下几个单词组成：an，and， another，bus，but， buzzy，school，shot，zig，zigzag。 最终要在一个文本串定位这几个单词，假设文本串为“We go to school by bus.” 词典结构 a b c d s z 0 12 -1 -1 23 33 an;and;another bus;but;buzzy school;shotzig;zigzag 查找过程 算法：查找过程 输入：文本串，及相应的词典 算法开始： For（文本串中的每个字符char） 获取char对应的地址address; If (address = -1)
11、 break; 在address地址处读取相应的词序列； 逐个匹配相应的词，如果匹配成功则有一个成功的定位。 算法结束。 HASH算法改进 1. 索引不能以一个字符建立。如果由一个字符建立，仅 仅能把词典进行26分。最多能128分。如果按两位byte建 立索引，可以把词典256分。如果按四位byte建立索引， 可以把词典65536(=256*256)分。 2不能仅仅建立一级索引。如果模式量大的时候，可以 建立多级索引。其实，建立多级索引的目的也是把词典 分成更多份。 3每个小类中也不能随意存放。经过索引把模式串集合 分为了很多份。在每份中，也要对相应的词进行字典序 排序。其目的也就是能够按二分
12、法在小类中进行快速匹 配。 5 章节实验 【实验目的】 掌握计算机病毒扫描算法 【实验平台】 Windows系列操作系统 Visual Studio 6.0应用程序 【实验步骤】 源码位置：解压缩目录AttachmentCh08Scan Algorithm。 如果要使用该算法，读者需要一定的VC+编程基础，具 体使用过程如下： (1) 在工程中，引入文件BinTree.h和BinTree.cpp (2) 声明变量：CBinTree* tree (3) 把病毒特征代码库中的所有特征码插入tree树中 for ( 病毒特征代码库 ) tree-InsertString ( 特征码, 病毒标示 ); (4) 构造tree树 tree-Build_Parent_State(tree-mRoot); tree-Build_Fail_Func(tree-mRoot); tree-Build_State_No(tree-mRoot); (5) 查毒过程 打开待查毒文件，把文件内容读入缓存memory中； int iRet = tree-Search( memory ); (6) 判断是否染毒 如果iRet0，则说明文件含有病毒。
