AC算法BM算法

第36卷 第6期 2014-06(上) 【15】一种改进的单模式匹配算法Improved single pattern matching algorithm张玉新，李成海，白瑞阳ZHANG Yu-xin, LI Cheng-hai, BAI Rui-yang（空军工程大学 防空反导学院，西安 710051）摘 要：模式匹配算法在病毒特征码检测、入侵检测、生物信息等诸多领域有着广泛的应用，如何提高匹配的效率是制约模式匹配算法的决定因素，本文通过分析传统的模式匹配算法提出一种改进的单模式匹配算法，通过对比分析和验证，该算法提高了匹配效率。

关键词：模式匹配；BM算法；BMH算法中图分类号：TP393.08 文献标识码：A 文章编号：1009-0134(2014)06(上)-0015-03Doi：10.3969/j.issn.1009-0134.2014.06(上).04收稿日期：2014-03-08基金项目：国家自然科学（61272486）作者简介：张玉新（1990 -），男，甘肃民乐人，硕士研究生，研究方向为网络信息安全。

0 引言网络已成为人们生活、学习、生产等诸多领域不可缺少的一部分，但是由于诸多的因素造成了网络安全问题的频发，在网络高速化的时代，如何从大量数据中提取特定的信息，显得十分重要。

模式匹配就是给定字符串T 和S ，其中字符串T 称为正文，字符串S 称为模式，要求在正文T 中找到模式S 是否出现。

模式匹配可以分为单模式匹配和多模式匹配，其中单模匹配有著名的BF 算法、BM 算法、BMH 算法、KMP 算法，文献[1]提出的快速单模式匹配算法(FSBM)充分利用已匹配的后缀和字符串后一位字符的信息,已达到在每一次跳跃中跳跃尽量大的距离，文献[2]利用模式字符串中存在重复字符串来获得最大的移动距离。

多模匹配有AC 算法，AC-BM 算法，文献[3,4]也提出了相关的一些改进。

其中Snort2.9中应用的就是单模匹配和多模匹配算法。

AC经典多模式匹配算法多模式匹配AC算法（Aho and Corasick），BM、Wu-Manber算法，WM 由BM派生，不过AC与它们无染，是另外一种匹配思路。

1.Step1:将由patterns组成的集合（要同时匹配多个patterns嘛）构成一个有限状态自动机。

Step2:将要匹配的text作为自动机输入，输出含有哪些patterns及patterns在全文中位置。

自动机的执行动作由三个部分组成：（1）一个goto function（2）一个failure function（3）一个output function我们先通过一个具体实例来了解一下这三个部分，及该自动机的运作方式。

先有个大概印象，后面会具体讲解。

patterns集合{he,she,his,hers}，我们要在”ushers”中查找并匹配。

(1)goto functioni123456789f(i)000120303（发现没？貌似i和f(i)有相同前缀哦^_^）(2)failure functioni output(i)2{he}5{she,he}7{his}9{hers}(3)output function首先我们从状态0开始，接收匹配字符串的第一个字符u，在goto（简称goto function）中可以看到回到状态0，接着第二个字符s，发现转到状态3，在output中查找一下output(3)为空字符串，说明没有匹配到patterns。

继续匹配h，转到状态4，查找output发现仍然没有匹配，继续字符e，状态转到了5，查找output，发现output(5)匹配了两个字符串she和he，并输出在整个字符串中的位置。

然后接着匹配r，但发现g(5,r)=fail，这时候我们需要查找failure，发现f(5)=2，所以就转到状态2，并接着匹配r，状态转移到了8，接着匹配s，状态转移到了9，查看output，并输出output(9):hers，记录下匹配位置。

模式匹配算法在入侵检测中的应用作者：冉占军姚全珠王晓峰邹又姣来源：《现代电子技术》2009年第02期摘要：仅依靠传统的被动防御技术已经不能满足如今的网络安全需要，基于模式匹配的入侵检测系统正成为研究和应用的热点，模式匹配效率的高低决定了这类入侵检测系统的性能。

全面综述了应用于入侵检测系统的经典的模式匹配算法，包括单模式匹配算法中的KMP 算法、BM算法、RK算法和多模式匹配算法中的AC算法、AC－BM算法，并对各种算法的执行效率进行了总结。

通过分析算法的思想，提出了未来此类算法的研究方向。

关键词：入侵检测；KMP算法；BM算法；RK算法；AC算法；AC－BM算法中图分类号：TP301文献标识码：B文章编号：1004 373X(2009)02 063 05Application of Pattern Matching Algorithm in Intrusion Detection TechniqueRAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in thispaper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC －BM algorithm0 引言随着网络技术的发展，各种基于网络的应用层出不穷。

AC算法BM算法AC算法（Aho-Corasick Algorithm）AC算法是一种字符串算法，通常用于在一段文本中查询多个模式串的出现情况。

它是由Alfred V. Aho和Margaret J. Corasick于1975年提出的，并以他们的名字命名。

AC算法的原理是构建一个有限状态机（FSM），该状态机能够同时处理多个模式串的匹配。

该算法具有高效的时间和空间复杂度，并且能够在一次扫描内找到所有模式串的匹配位置。

下面将介绍AC算法的详细步骤：1. 构建Trie树（前缀树）：根据给定的模式串集合，构建一个Trie树。

Trie树是一种特殊的字典树，它能够实现快速的字符串匹配。

Trie树的根节点为一个空节点，每个节点都有多个子节点，每个子节点都代表一个字符。

从根节点到叶子节点的路径上的所有字符组成一个模式串。

2. 构建失败指针（Fail Pointer）：在Trie树中，每个节点的失败指针指向它的最长后缀节点，该后缀节点也是Trie树的节点。

如果一个节点的当前字符在其最长后缀节点的子节点中不存在，则将失败指针指向最长后缀节点的失败指针指向的节点。

如果没有最长后缀节点，则将失败指针指向根节点。

3. 在文本中匹配模式串：从文本的第一个字符开始，按照Trie树的路径进行匹配。

如果在一些节点匹配失败，则通过失败指针转移到下一个节点进行匹配，直到匹配成功或到达文本的末尾。

当匹配成功时，可以通过沿着失败指针回溯，找到其他可能的匹配位置。

4.输出匹配结果：对于每个文本字符，记录匹配的模式串。

使用一个结果链表，其中每个节点包括一个指向匹配的模式串的指针和该模式串在文本中的位置。

AC算法的时间复杂度为O(n+m)，其中n是文本的长度，m是模式串的总长度。

空间复杂度为O(m)，即模式串的长度。

BM算法（Boyer-Moore Algorithm）BM算法是一种字符串和匹配算法，通过对模式串的后缀进行预处理，实现在文本中的快速。

基于AC_QS多模式匹配算法的优化研究作者：董志鑫方滨兴来源：《智能计算机与应用》2017年第05期摘要：随着互联网的日益强大，互联网上数据急剧增多，如何在海量的数据中快速准确地找到所需信息，就显得尤为重要，这就需要多模式串匹配算法。

多模式串匹配算法在越来越多的领域里都有应用，比如：信息安全领域中，入侵检测系统、防火墙等，在医学领域、数据挖掘、信息检索等等领域中均有广泛的应用。

AC算法在多模式串匹配算法中是一个能达到线性时间的算法，其算法效率较高，AC_QS算法是在AC算法基础上增加坏字符规则，进一步增加了AC算法的匹配效率，但其空间复杂度较高。

本文在AC_QS算法的基础上，对算法预处理和匹配过程中继续优化，并对字典树存储时进行了优化，使算法在空间和时间复杂度上得到进一步优化，提高了算法性能。

实验结果也验证了该算法的高效性。

关键词：多模式；模式匹配； AC算法； QS算法中图分类号： TP301文献标志码： A文章编号： 2095-2163（2017）05-0100-04Abstract： With the Internet becoming more and more powerful and the data increasing dramatically on the internet， it is very important to find the needed information quickly and accurately in the mass of data， so it is determined to require multipatterns string matching algorithm. Multi-patterns string matching algorithm has been used in more and more fields such as information security， intrusion detection system and firewall， data mining and medicine， and also has a wide range of applications in the field of information retrieval and so on. AC algorithm in multipatterns string matching algorithm is a linear time algorithm， which can achieve high efficiency. AC_QS algorithm is to increase the bad character in the AC algorithm and then improve the matching efficiency of AC algorithm， but its space complexity is high. In this paper， based on the AC_QS algorithm， the algorithm will continue to optimize the preprocessing and matching process， and in the dictionary tree storage are optimized. After that， the algorithm in space/time complexity is further optimized， therefore the algorithm performance is improved. The experimental results also verify the efficiency of the algorithm.Keywords： multiple patterns； pattern matching； AC algorithm； QS algorithm0引言模式串匹配算法，适用于从某个序列中，找到具有某种属性的模式段或者位置等信息。

网络入侵检测系统中的模式匹配算法设计优化陈卓民【摘要】为了使网络入侵检测系统能够在高速网络环境中有效工作,就实现了网络入侵检测系统中模式匹配算法的优化设计.首先对网络入侵检测系统和算法进行全面的分析,介绍了网络入侵检测核心技术,也就是入侵检测算法,并且对传统入侵检测算法中的缺点进行了分析,提出了基于特征匹配的模式匹配算法优化,从而有效提高模式匹配算法效率,从而进一步提高系统的检测能力.通过结果表示,优化之后的模式匹配算法能够有效提高网络入侵检测系统检测的性能.【期刊名称】《电子设计工程》【年(卷),期】2018(026)015【总页数】5页(P154-157,162)【关键词】网络入侵检测;模式匹配算法;算法设计;优化【作者】陈卓民【作者单位】陕西警官职业学院教务处陕西西安710021【正文语种】中文【中图分类】TN99在现代互联网不断发展的过程中，网络规模在不断的扩大，网络应用也越来越朝着全球化的方向发展。

在此背景下，网络入侵攻击事件的发生机率也在不断的增加。

传统防火墙技术已经无法有效保证网络安全，网络入侵检测系统属于积极主动安全防护技术，其目前已经成为网络安全领域中的研究热点内容[1]。

网络入侵检测系统一般使用被动监听方式实现，通过关键网段实现网络传输数据包的获取，并且通过多种检测分析方式对数据包进行分析，从而寻找入侵的证据。

网络入侵检测系统能够基于不对网络性能造成影响然后实现网络检测，从而寻找网络攻击事件[2]。

现代网络入侵检测系统检测分析的方法主要包括两种，分别为异常检测和基于特征检测。

因为异常检测需要学习时间，并且具有较高的检测误报率，无法满足大流量网络实时检测需求。

所以，目前都使用基于模式匹配特征检测。

现代网络流量在不断的提高，并且入侵特征库在逐渐更新，对于基于特征匹配网络入侵实时检测性能提出了一定的挑战[3]。

基于此，文中对网络入侵检测系统模式匹配算法的设计进行全面的分析。

1 网络入侵检测系统和算法1.1 网络入侵检测系统网络入侵检测系统属于标识并且隔离入侵安全的技术，其也是防火墙以外的第二道防线，图1为网络入侵检测系统的结构。

基于AC自动机的多模式匹配算法FACA陈新驰;韩建民;贾泂【摘要】Aho-Corasick automata algorithm has to backtrack for multiple times to shift to the effective subsequence state when it fails in one pattern matching. In order to solve this problem, this paper proposes a fast multiple patterns matching algorithm based on Aho-Corasick automata. The improved algorithm builds the subsequence pointers for each state. On failing matching, it can shift to the effective subsequence state through the subsequence pointers efficiently, which can reduce backtracking times in Aho-Corasick automata. Furthermore, the proposed algorithm achieves information such as matching length, matching times etc for each state during building automata by dynamic programming methods. Based on this information, the algorithm can calculate the repeated times of pattern strings, earliest position of pattern strings. Experimental results show that the algorithm has advantages of matching accuracy, efficiency, and supporting on-line operation.%Aho-Corasick自动机算法在模式匹配失配时,需要多次回溯才转移到有效的后继状态.为此,提出一种快速多模式匹配算法.该算法为每个状态建立失配时的后继指针,在模式匹配失配时,可以通过失配后继指针快速找到有效后继状态,从而避免Aho-Corasick自动机失配时的过多回溯,提高匹配效率.算法在自动机建立时采用动态规划的方法,为每个状态建立匹配长度和匹配量等信息,在模式匹配过程中,基于这些信息统计模式串在主串中的重复次数、最早出现模式串位置等信息.实验结果表明,该算法匹配精确、效率高,且支持在线操作.【期刊名称】《计算机工程》【年(卷),期】2012(038)011【总页数】4页(P173-176)【关键词】模式匹配;自动机;动态规划;Trie树【作者】陈新驰;韩建民;贾泂【作者单位】浙江师范大学计算机系,浙江金华321004;浙江师范大学计算机系,浙江金华321004;浙江师范大学计算机系,浙江金华321004【正文语种】中文【中图分类】TP3121 概述模式匹配算法是信息领域中的重要内容，广泛应用于文本搜索、网络入侵检测系统、病毒检测、信息检索、计算生物学等领域。

一、概述AC算法是一个经典的多模式匹配算法，可以保证对于给定的长度为n的文本，和模式集合P{p1,p2,...pm}，在O(n)时间复杂度内，找到文本中的所有目标模式，而与模式集合的规模m无关。

要理解AC算法，仍然需要对KMP算法的透彻理解。

KMP中我们用两个指针i和j分别表示，A[i-j+ 1..i]（目标串）与B[1..j]（模式串）完全相等。

也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符，当A[i+1]≠B[j+1]，KMP 的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配，而next函数恰恰记录了这个j应该调整到的位置。

同样AC自动机的失败指针具有同样的功能，也就是说当我们的模式串在Tire上进行匹配时，如果与当前节点的关键字不能继续匹配的时候，就应该去当前节点的失败指针所指向的节点继续进行匹配。

算法就是这样应用有限自动机巧妙地将字符比较转化为了状态转移。

此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关，但所需时间和文本长度以及所有关键字的总长度成正比。

AC算法有三个主要步骤，一个是字典树tire的构造（即构造转向函数），一个是搜索路径的确定（即构造失败函数），还有就是模式匹配过程。

二、AC算法思想算法的基本思想是这样的：●在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。

●在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。

下图是多模式{he， she， his ，hers}构成的一个确定性有限状态机，做几点说明：图 2.11、该状态机优先按照实线标注的状态转换路径进行转换，当所有实线标注的状态转换路径条件不能满足时，按照虚线的状态转换路径进行状态转换。

现代网络搜索引擎一般使用基于字符串匹配的搜索方式，使用的软件核心之一是字符串模式匹配算法。

网络特别是Internet 的信息量极大，在相同的信息采集方式下网络搜索的时间主要取决于所使用的串匹配算法的效率。

改善串匹配算法的特性或者时间复杂度，将有效提高网络搜索引擎的性能。

所以算法的提出和后续改进的算法称为研究的重点。

模式匹配主要有BF 算法，KMP 算法，BM 算法及其改进算法，尤其是BM 算法，在实际应用中非常著名，在此我们将对这几种算法做简单分析，分析前，我们做如下假定：文本：]1..0[-n text n 为文本长度模式：]1..0[-m pat m 为模式长度2.1 BF 算法BF （Brute Force ）算法又称为蛮力匹配算法[2]，这是一种效率很低的算法，其算法主要思想是模式的第一个字符与文本的第一个字符进行比较，如果相同，就继续比较后面的字符，否则，文本的起始位置加1，即模式右移一个位置，再进行比较，如果模式与文本中一段连续字符串都相同，则匹配成功，返回当时文本的起始比较位置，否则匹配不成功，实现过程：在串text 和串pat 中比较的起始下标i 和j ；循环直到text 中所剩字符小于pat 的长度或pat 的所有字符均比较完（如果text[i]=pat[j]，则继续比较text 和pat 的下一个字符；否则将i 和j 回溯，准备下趟比较）；如果pat 中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。

BF 算法如下：Algorithm BFk=0;j=0;while ((j<=m)&&(k<=n-m)){ if (pat[j]==text[k]){ k++;j++;}Else{k=k-j+1;j=0;}}if (j= =m) Match found at text[k-m]else No match found例子1：文本：astringsearchingexamplelienvolingrelatively模式串：relative1. astringsearchingexamplelienvolingrelativelyrelative2. astringsearchingexamplelienvolingrelativelyrelative3. astringsearchingexamplelienvolingrelativelyrelative4. astringsearchingexamplelienvolingrelativelyrelative：32. astringsearchingexamplelienvolingrelativelyrelative该算法简单，但是效率较低。

网络安全审计系统设计方案深圳市中科新业信息科技发展有限公司错误!图片串中含有不匹配的引号。

目录1、网络安全审计系统设计方案 (3)1。

1、项目背景 (3)1.2、总体项目概述 (3)2、企业网络架构及安全审计总体需求分析 (4)3、企业网络安全审计系统整体解决方案 (6)3.1、企业网络哨兵网络安全审计系统部署方案 (6)3。

2、网络哨兵网络安全审计工作原理说明 (7)4、网络哨兵网络安全审计系统技术优势 (11)4.1、高速的数据捕获技术 (11)4。

2、数据高速分析匹配技术 (11)4。

3、审计协议丰富、内容审计功能强大 (12)4.4、内置强大过滤库 (12)4.5、管理策略可精细定制 (13)4.6、审计对象管理灵活 (15)4。

7、部署方式多样 (15)4.8、自身安全性高 (16)4.9、能对上网用户进行认证管理 (16)4。

10、辅助功能齐全 (19)4.11、违规通知 (19)4。

12、方便用户使用的个性化设置 (19)4。

13、分权管理 (20)4。

14、强大的报表系统 (21)5、网络哨兵部署后实现的价值 (23)1、网络安全审计系统设计方案1.1、项目背景企业网络内部作为一个开放的局域网络接入系统，应用状况日趋复杂。

一方面各员工上网工作的条件得到改善,但另一方面也给信息中心的管理层面貌带来更高的网络使用危险性、复杂性和混乱，在帮助企业走向成功的同时，也成倍的加大了遭遇到各种风险的可能性:在IDC对全世界网络使用的调查结果中发现，员工30％至40％的上网活动与工作无关.超过85%的网络安全威胁来自于内部；有16%来自内部未授权的存取；有14％来自专利信息被窃取；有12％来自内部人员的财务欺骗；而只有5％是来自黑客的攻击.有 69％的组织机构承认他们的信息安全被破坏通常是来自于员工恶意的行为与非恶意的失误;数据泄漏的原因有39％来自于非恶意员工的失误。

在欧美发达国家: 80％的企业对员工的互联网活动进行审计，而且这一举措得到了法律条文上的支持. 在中国：据IDC统计数据显示，中国员工比其它地区的员工每周多花7.6小时的时间来使用QQ、玩游戏、新闻网页浏览等。

双向AC算法及其在入侵检测系统中作者：潘华伟来源：《电子技术与软件工程》2017年第06期经过众多伟大科学家不断地研究，我国在算法领域有了进一步的发展，当前相关的科学家已经在经典的多模式字符串匹配算法-AC算法的基础上提出了双向AC算法。

这种双向算法的提出能够在预处理阶段建立正向和反向两种状态的自动机，这种自动机在扫描的过程中使用正向有限自动机从中间向右进行，而反向有限自动机从中间向左进行。

这种算法与之前相比具有更高的效率，因此得到了更广泛的使用。

【关键词】AC算法串匹配算法入侵检测系统一般情况下，网络入侵检测系统的模式匹配算法的主要功能就是判断攻击模式串是否在截获的网络数据包有效负载中出现。

一般情况下，我们将模式匹配算法分为两种，一种是单模式匹配，还有一种是多模式匹配。

单模式算法中最经典的是跳跃式配算法，其在匹配的过程中能够自动的跳过不许匹配的字符。

而多模式算法中最经典的是AC算法，这种算法在执行过程中不会受到模式长度以及文本特征的影响，因此使用的比较广泛。

1 双向AC算法的工作流程双向AC算法在运行的过程中，首先进行的工作就是对模式串进行预处理，并且在处理的过程中生成正向、反向两种树状有限状态自动机，其在匹配的过程中由正向、反向自动机分别从中间向左右两侧扫描，从而将所有的模式串匹配出来。

1.1 模式串集合的预处理过程进行模式串集合的预处理工作时，相关工作人员的主要工作就是将模式串集合转换成正向和反向有限自动机。

在这个阶段，工作人员需要注意的是将正向有限自动机与AC算法结合，从左向右进行扫描。

另外，在预处理的过程中，首先进行的就是对Goto函数，与此同时注意生成一部分Output函数，工作的时候从0开始，对字符的顺序及重复性进行考虑，同时增加一些新的状态及路径，直到将所有的模式串都处理完。

另外，在处理模式串的过程中，还应该将其状态进行记录，使整个算法能够有条不紊的进行。

1.2 AC算法的文本匹配过程AC算法在进行的过程中，文本串及模式串集合一般情况下是已经给定的，因此工作人员在匹配的过程中就应该将文本串的中心点作为基础，而匹配过程中的重复区域使用最长模式串充当，并且将正向和反向匹配的起点确定下来，将正向处理过程与反向处理过程进行对比，使AC算法的文本匹配过程能够顺利的进行。

关于KMP算法和BM算法的理解自己之前没有接触到模式匹配的问题。

对于所谓的字符串匹配也只是简单的蛮力匹配。

上周刚看了《多模式匹配算法及破件实现》这篇文章。

文章中主要讲的是多模式匹配算法: AC算法和WM算法以及这两个算法的改进。

AC算法是基于KMP算法的，WM算法是基于BM算法的。

只有充分理解了单模式匹配的KMP算法和BM算法才能理解多模式匹配算法, 最后才能对模式匹配有一个深入的理解。

卜面主要说卜•自己对KMP算法和BM算法的理解。

KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。

所谓前缀匹配是指: 模式串和母串的比较从左到右，模式串的移动也是从左到右：所谓后缀匹配是指：模式串和母串的的比较从右到左，模式串的移动从左到右。

看得岀来前缀I兀配和后缀匹配的区别就仅仅在于比较的顺序不同。

KMP算法KMP算法，是由Knuth, Morris, Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，足一个非常优秀的模式匹配算法。

KMP算法对于朴素匹配算法的改进是引入了一个跳转表next[]。

但next[]刚接触时比较难于理解。

next跳转表，在进行模式匹配，实现模式串向后移动的过程中，发挥了更要作用。

这个表看似神奇，实际从原理上讲并不复杂，对于模式串而言，其前缀字符串，有町能也是模式串中的非前缀子串，这个问题我称之为前缀包含问题。

以模式串abcabcacab为例，其前缀abca,止好也是模式串的一个子串abc(abca)cab,所以当目标串与模式串执行匹配的过程中，如果直到第8个字符才匹配失败，同时也意味着目标串当前字符Z前的4个字符, 与模式串的前4个字符是相同的，所以当模式串向后移动的时候，可以直接将模式串的第5 个字符与当前字符对齐，执行比较，这样就实现了模式串一次性向前跳跃多个字符。

这里只是一个模式串移动的思想。

如何以较小的代价计算KMP算法中所用到的跳转表next,是算法的核心问题。

2.4 开源杀毒软件ClamWin及其引擎ClamAV学习总结2.4.1 ClamWin及其引擎ClamAV介绍2.4.2 ClamAV引擎中的主要扫描功能函数•cli_scanpe：先是进行PE合法性校验，若遇到入口在不在节内，或小于各个节所在的大小，及一系列非法PE格式文件情况，就都报“Broken.Executable“，然后检测退出。

而后进行壳情况的检测，后面有这块的具体分析说明，在调用相应壳版本验证后，调用脱壳函数，而后进行特征匹配。

•cli_scanmschm：该函数用来对微软的CHM格式文件进行解码处理。

•cli_scanscrenc：针对微软的Script Encoder脚本加密的解密处理流程，解码后按目录文件方式扫描。

•cli_scan_mydoom_log：该函数用来处理Worm.Mydoom.M.log ，走入该检测流程分支依赖格式识别，返回CL_TYPE_UNKNOWN_DATA 类型，显然这样的处理方式并不合理。

•Scanmanager所有检测入口函数•cl_loaddbdir加载本地所有格式病毒库到内存•cl_build构建扫描引擎•cl_scandesc扫描分析•cli_loaddb加载*.db,*.db2,*.db3,*. Mdb等格式的病毒库•cli_parse_add添加病毒库特征到结构•cli_ac_addsig添加特征到AC算法结构•cli_bm_addpatt添加特征到BM算法结构2.4.3 ClamAV引擎宏观结构说明从v0.15 – v.093，ClamAV引擎的整体上一直都保持统一的风格，不断增加的仅是内部功能更加细致的分类，与一些重要数据结构的增加和修改或相应算法的修正。

当然就引擎调用来看ClamAV较为简单，这方面没有什么变化，引擎所处的环境也始终是以文件或目录为单位输入的情况，不涉及网络部分。

对ClamAV引擎归纳来说有2个特点：一、通过配置信息指明检测目标；二、靠流程来驱动检测。