基于启发式算法的恶意代码检测系统研究与实现

单位代码： 10293 密 级：

硕 士 学 位 论 文

论文题目： 基于启发式算法的恶意代码检测系统

研究与实现

Y004091137 雷迟骏 王海艳 教授 王汝传 教授/博导 计算机软件与理论 软件技术及其在通信中的应用 工学硕士 二零一二年三月

学号

姓名

导 师

学 科 专 业 研 究 方 向 申请学

位类别 论文提

交日期

南京邮电大学学位论文原创性声明

本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得

的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包

含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它

教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的

任何贡献均已在论文中作了明确的说明并表示了谢意。

本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。

研究生签名：_____________ 日期：____________

南京邮电大学学位论文使用授权声明

本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印

件和电子文档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。

涉密学位论文在解密后适用本授权书。

研究生签名：____________ 导师签名：____________ 日期：_____________

南京邮电大学

硕士学位论文摘要

学科、专业：工科、计算机软件与理论

研究方向：基于网络的计算机软件应用技术

作者：二零零九级硕士研究生雷迟骏指导教师：王海艳教授王汝传教授/博导

题目：基于启发式算法的恶意代码检测系统研究与实现

英文题目：The Research and Realization of Unwanted Code monitoring system based on Heuristic algorithm

关键词：恶意代码，检测，启发式算法，模式匹配，虚拟技术

英文关键词：Pattern matching, Heuristic algorithm, Virtual machine technology, Cloud computing, Unwanted Code

论文选题来源：

1.国家863计划项目“新型对等计算安全软件平台的设计与实现”（编

号2006AA01Z439）

2.华为赛门铁克公司企业项目“ARES协议分析”（编号

YBSS2009401）

南京邮电大学硕士研究生学位论文中文摘要

中文摘要

随着计算机技术的发展，尤其是计算机网络的发展，恶意代码也在不断的发展中。当前的恶意代码的数量比起过去有着呈几何增长。传统的恶意代码基本都以病毒形式出现，而当前恶意代码形式多种多样,如蠕虫、病毒、木马、恶意插件等。从功能上分析，传统的恶意代码一般功能单一，大多以数据破坏为主，而当前的恶意代码还具有数据窃取、篡改等功能，并且运用了大量的反调试、反跟踪、反检测等技术来保护自身。由此可见，当前恶意代码对计算机发展的危害已经越来越显著，同时也是检测越来越困难。

在检测恶意代码方面，传统的杀毒软件仅仅采用的是二进制特征代码匹配技术来进行检测。由于该方法必须要得到恶意代码的二进制特征代码，一旦恶意代码通过加密等方式改变了其二进制特征代码，该方法将彻底失效。传统的杀毒软件面对当前的恶意代码已经显得力不从心。

本论文在阐述模式匹配算法、启发式扫描算法以及虚拟机技术等的基本理论及关键技术的基础上，研究了目前恶意代码检测引擎的模式匹配算法的不足，提出改进的方案。此外在基于启发式扫描算法和虚拟机技术的特征行为引擎研究下，本论文建立了一个结合二进制特征匹配、行为特征匹配以及云端检测的新型恶意代码检测方法的原型系统。

本文的研究成果能有效提高系统资源，并且充分利用网络资源，抵御恶意代码入侵,对维护互联网的健康环境，进而营造出一个和谐的网络社会有着积极意义。

关键词：模式匹配，启发式，虚拟机技术，云计算，恶意代码

-I-

南京邮电大学硕士研究生学位论文ABSTRACT

ABSTRACT

Nowadays, with the development of computer technology, especially computer networks, malicious code are constantly developing. The number of current malicious code has exponential growth than in the past. The traditional malicious code are basically in the form of the virus, but the current malicious code are all kinds of forms, such as worms, viruses, Trojan horses, malicious plug-ins. From the functional analysis, the traditional malicious code generally functioned specially on data breaches, but the current malicious code function on data theft, tampering and other functions, and also use of a large number of anti-debugging, anti-tracking , anti-detection techniques to the protect themselves. Evidently, the development of malicious code on computers has become increasingly significant harm and makes it more and more difficult to detecting them.

To detect the malicious code, traditional anti-virus software only uses the method of binary characteristics of the code-matching techniques. Since the method must get the binary characteristics code of the malicious code, once the malicious code changes the characteristics code by encrypting its binary code, the method will completely fail. The traditional anti-virus software seems powerless to the current malicious code.

Based on the very explanation of basic theory and key technology, such as pattern matching algorithm, heuristic scanning algorithms and virtual machine technology, the paper has researched deeply on the shortages of pattern matching algorithm of the current malicious code detection engine, and put forward the improved method. In addition, based on the research of heuristic algorithms and the engine using virtual machine technology to match the behavior characteristics, the paper set up a prototype system which combined the binary feature matching, feature matching and the method of behavioral detection of cloud.

This research can improve the system resources and make full use of network resources to defend against malicious code intrusion, maintain a healthy environment of the Internet, thus and make positive sense to creating a harmonious network social.

Key words:Pattern matching, Heuristic, Virtual machine technology, Cloud computing,

-II-

南京邮电大学硕士研究生学位论文ABSTRACT Unwanted Code

-III-

南京邮电大学硕士研究生学位论文目录

目录

中文摘要............................................................................................................................................................... I ABSTRACT ......................................................................................................................................................... II 第一章引言 (1)

1.1 研究背景 (1)

1.2 课题来源及本人所做工作 (1)

1.3 论文结构 (2)

第二章模式匹配算法概述 (4)

2.1 模式匹配算法研究现状 (4)

2.2 模式匹配算法介绍 (4)

2.2.1 KMP (5)

2.2.2 Aho-Corasick算法 (8)

2.2.3 WM算法 (9)

2.3 多模式匹配算法改进 (11)

2.3.1 AC与WM算法比较 (11)

2.3.2 AM算法 (12)

2.4 本章小结 (14)

第三章虚拟机技术概述 (15)

3.1 虚拟机技术简介 (15)

3.2 x86 体系结构与PC 系统概要 (16)

3.2.1 x86 CPU 结构 (16)

3.2.2 x86 体系结构概览 (18)

3.2.3 PC 系统 (19)

3.3 BOCHS与QEMU技术分析 (20)

3.3.1静态翻译 (21)

3.3.2动态翻译 (23)

3.4 本章小结 (26)

第四章基于语义的启发式检测模型 (27)

4.1 引言 (27)

1

南京邮电大学硕士研究生学位论文目录

4.2 相关研究 (27)

4.2.1静态启发式扫描 (28)

4.2.2动态启发式扫描 (28)

4.3 基于语义的可信模型 (31)

4.3.1基本可信模型 (31)

4.3.2基于信息熵的判断模型 (32)

4.4 本章小结 (36)

第五章高性能云服务器设计 (37)

5.1 Windows Socket I/O模型 (37)

5.2 windows 完成端口模型 (38)

5.2.1完成端口简介 (38)

5.2.2 数据重组 (42)

5.3 本章小结 (43)

第六章原型系统实现与测试 (44)

6.1 基于云计算的恶意代码监测系统实现 (44)

6.1.1 体系结构 (44)

6.1.2系统工作流程 (44)

6.2 恶意代码监测系统测试 (48)

6.2.1 查杀率测试 (48)

6.2.2 误报率测试 (53)

6.3 本章小结 (56)

第七章总结与展望 (57)

7.1 总结 (57)

7.2 展望 (57)

致谢 (59)

攻读硕士学位期间的学术论文 (60)

攻读硕士学位期间参加的科研项目 (61)

缩略词 (62)

图表清单 (64)

参考文献 (66)

2

南京邮电大学硕士研究生学位论文第一章引言

第一章引言

1.1 研究背景

恶意代码是指没有作用却会带来危险的代码，一个最安全的定义是所有不必要的代码都看作是恶意的。近些年随着计算机技术的发展，尤其是计算机网络的发展，编程技术已经慢慢的普及化。编写病毒之类的恶意代码已经不再是计算机高手的专利，随之而来的是恶意代码的数量呈指数级增长，对社会的危害越来越大[1]。另一方面，恶意代码作者由于经济利益的驱使，在恶意代码编写的过程中利用了更多高深的技术来达到保护自身的作用，rootkit技术的迅速发展就是一个很好的证明[2]。

传统的恶意代码检测系统主要采用的是二进制特征代码匹配技术，首先病毒分析专家通过分析确定一些已知恶意代码的二进制特征代码，保存到数据库即病毒库中，在检测中利用模式匹配算法对带检测的代码与病毒库中的特征代码进行匹配，匹配成功确定其为恶意代码，否则视为安全代码。

但当前随着恶意代码的数量的增多，病毒库越来越庞大，利用传统的模式匹配算法说耗费的时间不断的增大，已经不能满足实际应用。另外随着恶意代码编写技术的发展，当前的恶意代码大多采用加密等技术对自身进行保护，这样就更近一步降低了传统检测方法的准确性。为了解决这一问题，最有有效的应为归纳总结出一类恶意代码的行为特征，将传统的二进制特征匹配提升到行为特征匹配，才能利用尽可能少的特征检测出尽可能多的恶意代码。除此之外，充分的利用网络的资源共享优势，利用云计算技术进行辅助检测，从而有效的降低了误报率。

1.2 课题来源及本人所做工作

本文所涉及的课题得到国家863计划项目（编号2006AA01Z439）和华为赛门铁克公司委托开发项目的资助。

本人所做的工作可陈述如下：

1

南京邮电大学硕士研究生学位论文第一章引言

(1)探讨目前诸多模式匹配算法，并通过比较，突出恶意代码检测系统的特点，分析了目前诸多算法的不足，提出了改进算法。

(2)分析了虚拟机技术，全面的分析了目前几种流行的虚拟机技术，经过比对得出了更适合于恶意代码检测引擎的。

(3)学习启发式算法，探讨了启发式技术在恶意代码中的实际运用，给出了原型系统的总体设计框架。

(4)探讨云计算技术，提出了结合本地防御，网络资源共享的整体系统架构。

(5)设计原型系统，并在现有条件下对系统进行测试。

1.3 论文结构

论文共分为七章，其组织结构如下：

第一章引言。首先介绍了恶意代码检测技术的历史背景和发展现状，并根据目前恶意代码发展的趋势特点指出了它的广阔应用前景，以及主要的研究机构等。最后指出本课题的来源、本人所做工作以及论文采取的结构。

第二章模式匹配算法概述。本章介绍了包括单模式匹配算法KMP和多模式匹配。然后结合当前恶意代码检测系统的特点，分析了AC与WM两种多模式匹配的不足。之后提出了改进算法AW算法，并通过实验得出数据进行对比，证明AW算法可以支持当前环境下恶意代码特征码检测引擎。

第三章虚拟机技术概述。本章全面介绍了虚拟机技术。根据系统架构的不同，对当前虚拟机产品进行了分类。详细研究了目前流行的x86 PC系统的体系结构，进而研究了虚拟机工作的原理。随后对基于指令模拟的两款虚拟机产品BOCHS和QEMU进行了对比分析，分析了静态翻译和动态翻译的差异。着重研究了动态翻译，为整个恶意代码监测系统中系统仿真打下基础。

第四章基于语义的启发式检测模型。本章全面介绍了基于语义的启发式恶意代码检测技术。首先阐述了根据当前恶意代码发展的趋势，利用行为特征分析取代传统二进制特征码定位的优势。介绍了静态启发式扫描和动态启发式扫描两种扫描方式。此外，提出了基于语义的可信模型和信息熵判断模型。

第五章高性能云服务器设计。本章全面介绍了高性能服务器的构建，为监测系统的云服务平台提供支持。着重研究了windows平台下网络应用程序的六种socket I/O模型。此后，详细研究了windows完成端口网络模型，分析了其整个工作流程。

2

南京邮电大学硕士研究生学位论文第一章引言第六章原型系统实现与测试。本章主要完成对检测原型系统的设计实现和测试。在

根据前面研究的模式匹配、虚拟机技术、启发式检测技术和高性能服务器技术的基础上，

设计了高性能、稳定、可靠的基于云计算技术的恶意代码检测系统。之后对系统的查杀率

和误报率的两方面问题进行了测试，并与国内外的一些著名杀毒软件测试的结果进行了对

比，基本达到预期效果。

第七章总结和展望。对本课题实现的恶意代码检测系统作出总结，分析了其实现方

法及应用前景。并针对当前系统中尚存在有待改善的地方，以及对如何开展进一步的工作

做出展望。

3

南京邮电大学硕士研究生学位论文第二章模式匹配算法概述

第二章模式匹配算法概述

模式是指按照某种结构组织起来的多个元素的集合[3]。模式匹配是指将两个模式作为输入，计算模式元素之间语义上的对应关系的过程。模式匹配作为计算机科学中的一个重要研究领略，被广泛应用于搜索引擎、海量数据处理、网络入侵检测等领域[3]。尤其是目前的杀毒软件的检测引擎重要是基于模式匹配[4]。

2.1 模式匹配算法研究现状

首先出现的模式匹配算法为BF算法，这是一种单模式匹配算法，由于采用的只是简单的逐个字符比较，因而效率很低。1977年Boyer和Moore提出的单模式BM算法，由于BM算法主要是针对当字符串比模式的长度大的情况，造成了在移动对于小的字符串情况下不是特别有效。此后Horspool根据BM算法的思想提出通过最右边的字符的移动来计算BM算法的移动距离，即BMH算法。在诸多单模式匹配算法中，最为著名的要属Knuth，MorriS和Pratt提出了KMP算法。该算法和前面算法不同，KMP算法在比较时，如果某次匹配不成功，模式串可能右移多个字符，而且右移后，可以不必从模式起点处进行匹配[5]。

随着计算机的发展，简单的但模式匹配算法已经不能满足实际需求。随着模式数量的增加，采用单模式匹配需要对每个模式进行重复匹配，检测算法的时间复杂度将呈指数级增长。为了提高检测效率，需要一种高效算法能够完成一次对多个模式进行匹配操作，即对N个模式进行匹配时，只需要进行扫描一次数据流操作即多模式匹配算法。1975 年，Aho 和Corasick 提出了著名的基于有限状态自动机的AC 算法，这种算法最早应用于图书馆的书目查询中，它采用一种有限自动机把所有的模式串构成一个集合，可以一次查找多个模式。但由于AC算法空间复杂度过大，在模式集合过大时，实际效果并不理想。上世纪九十年代吴升（台湾）和他的导师Udi Manber提出了Wu-Manber算法。

2.2 模式匹配算法介绍

模式匹配算法从待匹配集合的数量上分类，可分为单模式匹配算法和多模式匹配算法。单模式匹配算法以KMP为代表[6]，多模式匹配算法从设计思路上分类大致有AC算法和

4

南京邮电大学硕士研究生学位论文 第二章 模式匹配算法概述 5 WM 算法，其他诸多算法大多是基于这两种的改进。

2.2.1 KMP

设有两个串S 和P ，其中S 为主串，P 为子串，又称为模式。在简单模式匹配中，一旦出现了匹配失败的情况，算法将回溯到模式的原点进行重新匹配，而KMP 引入了失败函数，避免了匹配过程中的回溯，从而有效的提高了匹配效率。如图2-1所示，在S[i]≠P[j]即到达匹配失败时。在简单模式匹配算法中，主串 S 要回到原来的i+1的位置（称为回溯），模式串P 要回到第一个字符的位置，然后继续匹配如图2-2所示。每次到达匹配失败点时，串S 和串P 的指针i ，j 都要回溯，因而效率不高。而在KMP 算法中在第一趟到达匹配失败点，即S[4]≠P[4]时，匹配失败点前的4个字符是两两相等的。由于S[1]=P[1](=?b ?)，而P[0]≠P[1]，因此P[0]≠S[1]，这样i 回溯到1和j 回溯到0的第二趟匹配是毫无意义的；同理，第3趟也是没有意义的。而第4趟匹配，i 可以不回溯,j 只要回溯到1，如图2-3所示。

S:a c

a b c a a b c

a

P:a b c a a b

图2-1 到达匹配失败点 S:a c b a b c a a b c a

P:a b c a a b

图2-2 简单匹配算法的下一次匹配

南京邮电大学硕士研究生学位论文 第二章 模式匹配算法概述

6 S:a c

a b c

a a

b c

a P:a

b

c a a b

图2-3 KMP 算法的下一次匹配

又上可见，问题的核心在于j 回到什么位置。因而KMP 算法的关键是求出模式串P 的所有字符的最大k 值，k 是匹配失败是j 需要向前回溯的最少位置。一旦在该字符上出现了匹配失败时，下一趟匹配可以直接从S[i]和和P[k]开始。设主串S=“011...n s s s -”，模式串P=“01...n p p p ”，并设在i s ≠j p 处匹配失败。分析P 串，如果发现011...k p p p -= 11...j k j k j p p p --+-，我们称在串011...j p p p -中，串011...k p p p -为前缀子串，串11...j k j k j p p p --+-为后缀子串。由于匹配在i s ≠j p 处失败，所有必有11...j k j k j p p p --+-=21...i k i i s s s ---和011...k p p p -=21...i k i i s s s ---。所以下一趟匹配可以直接从i s 和k p 开始，即将模式串中k 位置的字符与主串中i 位置的字符对齐后开始下一趟匹配。其中匹配算法中的重要代码为

失败函数代码

由上述代码可知，假设模式串的长度为m，则失败函数的时间复杂度为O(m)。如果将失败函数的计算时间包括在KMP算法的匹配过程中，则KMP算法中，当主串的长度为n 时，算法的时间复杂度为O(m+n)。

7

南京邮电大学硕士研究生学位论文 第二章 模式匹配算法概述

8

2.2.2 Aho-Corasick 算法

Aho-Corasick 自动机算法（简称AC 自动机）于1975年产生于贝尔实验室，是用来处理模式集合大于1的多模式匹配算法。该算法和巧妙的运用了有限状态机机制，将字符匹配转化成了状态转移[7]。

该算法的基本思想为：

AC 算法大致思想为，根据待匹配的多模式串建立一个有限状态机，即一个树形数据结构，将主串作为输入，放置到状态机中进行状态转换，当到达某些特定的状态时，模式匹配成功[8]。

在预处理阶段，算法建立了三个函数，跳转函数goto ，失败函数failure 和输出函数output ，由此构造了一个有限自动机。

在搜索查找阶段，则通过这三个函数的交叉使用扫描主串S ，定位出模式串i

P 在主串

S 出现位置。

此算法有两个极其显著的特点，一个是扫描主模式串S 时完全不需要回溯，另一个是不需要对模式集中的模式进行逐个匹配，时间复杂度为O(n)。

算法步骤如下：

(1) 根据模式串i P 建立有限状态机。

设多模式集合i P ={“she ”, “he ”, “his ”, “hers ”}，如图2-4为对应的有限状态机。

图2-4 AC 匹配算法状态转换

在该阶段，AC 算法建立了三个函数，失败函 failure 、跳转函数 goto 和输出函数output 。

图2-4 有限状态机图

南京邮电大学硕士研究生学位论文第二章模式匹配算法概述跳转函数goto，用来确定有限状态机中个个状态的跳转关系。goto(Previous, x)=next,

状态Previous 在输入一个字符x 后转换为状态next。如果在模式串中不存在这样的转换，

这说明当前匹配失败，则next=fail。如图2-4，当状态机当前处于状态0，输入字符为h时，

则进入状态1，输入字符为s时，则进入状态3.

失败函数failure，用来判断状态转换的成功与否。在构造转向函数时，用fail 表示不

存在的转换，一旦出现fail而整个匹配并没有完全结束时，根据失败函数状态机会跳转到

相应的状态，从而使匹配继续。如图2-4，当状态机当前处于状态6时，说明当前的匹配

过程已经成功的匹配出了串“hi”，而下一个输入值不为‘s?则说明整个匹配失败，此时状态

机回到初始状态状态0。

(2)输入主串S进行匹配

设主串S=“ushers”，状态机初始状态为0，当输入值为‘u?时，匹配失败，状态机回到

初始状态0。输入值为‘s?时，状态机跳转到状态3。输入值为‘h?时，状态机跳转到状态

4。输入值为‘e?时，状态机跳转到状态5，匹配成功输出“she”。

由上可见，AC算法避免了多模式匹配过程中，模式串集合需要多次和模式主串匹配

的情况，有效的降低了匹配所耗费的时间，模式主串S的长度为n时，算法的时间复杂度

为O(n)。

2.2.3 WM算法

WM算法在多模式匹配中，引入了坏字符跳转的概念，从而实现了模式匹配中的大幅度跳转。该思想源自于BM单模式匹配算法，但是在单模式应用场景，很少有哪个模式串会包含所有可能的输入字符，而在多模式匹配场景，如果模式集合的规模较大的话，很可能会覆盖很大一部分输入字符，导致坏字符跳转没有用武之地。所以WM算法中使用的坏字符跳转，不是指一个字符，而是一个字符块，或者几个连续的字符。通过字符块的引入，扩大了字符范围，使得实现坏字符跳转的可能性大大增加。WM算法与AC算法一样分为预处理阶段和搜索阶段[9]。

预处理阶段需预先对模式串集合进行处理，并构造三个表：SHIFT 表、HASH表、

PREFIX 表。WM 算法中SHIFT 表主要是用来确定匹配串滑动窗口可以跳跃多少个字符

位置。WM 算法将文本串以B 个字符长度分块，称该B 个字符为1 个块字符，B 为块字

符的长度，B 通常取2 或3。当匹配串滑动窗口的末字符块与模式串集合中的任何一个模

式串的末字符块不匹配时，文本滑动窗口可以安全地移动m-B+1 个字符位置（其中B 是

9

南京邮电大学硕士研究生学位论文第二章模式匹配算法概述字符块的长度，m是模式串集合中长度最小的模式串的长度）。HASH 表是建立在模式串的前缀基础上(前缀就是滑动窗口中对应字符串的首字符块)，HASH 函数把每个模式串的长度相等的前缀映射成一个合适的值，同时有较好的冲突处理方法。HASH表用来确定某个模式串是否是一个待匹配的模式串。

算法搜索过程的步骤如下[10]：

(1)计算所有待匹配模式串的长度，得到其中的最小值，记为m,这里将m 称为匹配窗口的大小；

(2)根据所有待匹配模式串的m 个字符，计算其尾块字符T[m-B+1,…, m]的散列值h；

(3)检查SHIFT[h]的值,如果SHIFT[h]>0，将窗口向右移动SHIFT[h]大小位置，返回第(2)步，否则，进入第(4)步；

(4)计算所有待匹配模式串对应窗口“前缀”的散列值，记为text_prefix；

(5)对符合HASH[h] ≤P

PREFIX[p]=text_prefix.如果相等，对文本和模式串进行完全匹配；

搜索过程的主要代码如下：

当字符表的长度为L，模式串长度总和为M，主串长度为B，窗口大小为m，WM 算法在预处理阶段的时间复杂度为O(L+M)，匹配阶段的时间复杂度为O(B*n/m)。

10

南京邮电大学硕士研究生学位论文第二章模式匹配算法概述2.3 多模式匹配算法改进

2.3.1 AC与WM算法比较

由2-2节介绍可见，AC算法的核心在于利用有限状态机将模式集P连成整体，然后将主串S放入状态机进行匹配，由于不需要对模式集合的模式进行逐个匹配因而大幅缩短匹配时间。WM算法的核心在于，利用字符块增大匹配失败概率，来避免逐个模式匹配带来的大量无效匹配[11]。

根据以上研究，通过具体实验对AC和WM算法进行对比分析。利用一个随机生成的200M的文件充当主串S，随机生成若干模式组成模式集P，作为测试数据集。分别采用AC 和WM算法作为模式匹配检测引擎，测试这两种情况下每个数据报的平均模式匹配时间与模式数目的变化关系。实验环境：CPU 1.66 GHz*2，内存1 GB，操作系统windows xp。表2-1比较了两种算法的平均匹配时间随着模式数目增加的变化情况

当主串长度为B，窗口大小为m时，由于|B|>m, WM算法的时间复杂度O(|B|*n/m)大于

11

南京邮电大学硕士研究生学位论文 第二章 模式匹配算法概述 12 AC 算法的时间复杂度。如表2-1，在模式数量小于100时，AC 算法的效率明显优于WM 算法。但当模式数量大于100时，由于建立有限状态机所需的内存不断增大，AC 匹配过程的状态跳转带来系统内存频繁切换造成在实际匹配过程中，效率反而比WM 算法低。但模式数量达到2000时，由于系统内存的限制，已经无法成功建立有限状态机，而造成AC 算法就此失效[12]。同样，当模式数量到达50000时，WM 算法也因系统内存限制问题失效。

2.3.2 AM 算法

有2.3.1节可知，AC 算法在理论上优于WM 算法，但AC 算法对系统硬件配置有较高要求。因而造成随着模式数量的增加，AC 算法在实际匹配中效率低于WM 算法，甚至在模式过多的情况下AC 算法会失效。而在当前杀毒软件与恶意代码的对抗中，病毒库（即模式集合P ）不断的增大，数量甚至超过几十万，达到百万级别。显而易见，AC 算法和WM 算法都已经没有办法满足当前恶意代码检测引擎的要求。

根据AC 算法和WM 算法的优缺点，我们结合两者对多模式匹配算法进行了改进，提出了AW 算法。

引入WM 算法字符块概念，来产生大量失败匹配，从而避免无效匹配。同时引入AC 算法中状态机原理，避免对模式集合P 中的模式逐个匹配现象。

假设模式集P={01...n p p p }，函数f(i P )为i P 模式的串长度，b =min(f(i P ))，(i=0，1，…，n)，我们以长度b 对模式集中所有模式进行分割，其中长度不足b 的分割块用十六进制0x00填充。例如，P={“qwqew ”, “wi ”, “ncxk ”}，b = 2，其中0P 被分割为{…q ?, …w ?}、{…q ?, …e ?}和{…w ?, 0x00}，1P 被分割为{…w ?, …i ?}，2P 被分割为{…n ?, …c ?}和{…x ?, …k ?}。同时，我们引入WM 算法的HASH 函数，对所有分割出来的块进行HASH 运算得到集合Q ，其中HASH 算法使用最为简单的异或运算。原因有二，计算机对异或运算处理最快，异或运算能保证使用0x00填充的块与原串等效。根据Q 集建立有限状态机，对主串S 中的字符串进行逐个HASH 运算得到输入值，放入状态机进行匹配。

假设主串为S=“qwiqewdskjskdsjkds ”， P={“qwqew ”, “wi ”, “ncxk ”}，我们根据P 建立得到集合Q ，如表2-1所示：

根据Q 建立有限状态机如图2-5所示：

南京邮电大学硕士研究生学位论文第二章模式匹配算法概述

图2-5 AW匹配算法状态转换

在AC算法中，模式集合P中一个Bit位将会被转换成一个状态，假设模式集合P中模式的模式总长度为n，则空间复杂度为O(n2)。在实验对比中，当模式个数为1000，平均模式长度为8时，算法消耗的系统内存达到700M。当模式个数为2000时，预计消耗系统内存为2400M，而实验机器的最大内存为1G，小于2400M，所以算法初始有限状态机失败，匹配无法进行。AW算法采用HASH技术，将AC算法中的几个状态合并成一个状态，从而大大减小算法实际消耗系统的内存量。

根据以上研究，通过具体实验对AC、WM和AW算法进行对比分析。利用一个随机生成的200M的文件充当主串S，随机生成若干模式组成模式集P，作为测试数据集。分别采用AC、WM和AW算法作为模式匹配检测引擎，测试这三种情况下每个数据报的平均模式匹配时间与模式数目的变化关系。实验环境：CPU 1.66 GHz*2，内存1 GB，操作系统windows xp。表2-2比较了三种算法的平均匹配时间随着模式数目增加的变化情况

表2- 2 AC、WM和AW算法效率对比

13

本文来源：https://www.bwwdw.com/article/o4ce.html