（通信与信息系统专业论文）基于sopc的入侵检测系统的设计与实现.pdf

摘要 摘要 随着计算机入侵事件的频频发生，计算机网络安全问题也越来越引起人们的 重视。入侵检测系统正是在这样的背景下应运而生。入侵检测系统能够主动查找 和评估风险，是防火墙的重要补充。目前的入侵检测系统一般是基于软件或基于 网络处理器的方式实现，然而随着网络速度的不断提升，对入侵检测系统的处理 速度提出了更高的要求。入侵检测系统需要将收集到数据与特征库进行匹配，这 就造成了处理速度瓶颈的存在。因此，如果采用硬件的方式对特征匹配进行加速 处理，将会大大的提高入侵检测系统的性能。 正是在这样的背景下，提出了一种嵌入式入侵检测系统的s o p c ( s y s t e mo n p r o 乒觚l n l a b l ec h i p ) 实现架构，包含基于n i o s l i 处理器的软件模块和硬件加速模 块。其中，软件模块采用协议分析技术检测网络层、传输层的疑似威胁信息；硬 加速模块包含包头匹配、正则表达式匹配等两个子模块匹配s n o r t 规则库。包头 匹配模块采用t r 幽i tm a p 算法实现；正则表达式匹配模块采用n f a ( n o n e d e t e r m i n i s t i cf i n i t ea u t o m a t a ) 状态机实现。该架构在a l t e r ac y c l o n e l i f g p a 上实现，并在a l t e r ad e l l 开发板上进行了验证，实验结果表明系统能够正 确检测网络流量中的威胁信息，硬件加速器的吞吐率可达1 6 g b p s 。同时，充分 考虑了设计的可升级性，开发了用软件能够读取规则集并自动生成h d l 代码。 本文首先阐述了入侵检测系统的发展背景、趋势及基本理论。其次重点介绍 了用于包头匹配的t r e e i tm a p 算法以及用于正则表达式匹配的由正则表达式构 造n f a 状态机的算法；随后提出了基于s o p c 的入侵检测系统的总体设计方案； 然后分别从硬件实现部分以及软件设计部分对系统的构建进行阐述；最后，对系 统在f p g a 上的测试做了分析，并给出测试结果。 关键词：入侵检测，正则表达式匹配，n f a ，t r e e - b i tm a p ，s o p c a b s t r a c t a b s t r a c t a st h ei n t r u s i o ne v e n t so nt h ei n t e r n e ta l w a y sh a p p e n s ，c o m p u t e rn e t w o r k s s e c u r i t yi sm o r ea n dm o r ec o n c e r e db yp e o p l e i n t r u s i o nd e t e c t i o n ss y s t e m ( i d s ) i s b o m e du n d e rt h i sb a c k g r o u n d i d sc o u l di n i t i a t i v e l yf i n da n da s s e s st h r e a t st h a te x i s ti n t h es y s t e m , w h i c hi sa ni m p r o t a n tc o m p l e m e n t a r i t yf o rf i r e w a l l t h ei d su s i n ga t p r e s e n ti su s u a l l yb a s e do ns o f t w a r eo rn e t w o r kp r o c e s s o r s ( n p ) ，w h i c hc o u l dn o t s t a t i s f yt h ei n c r e a s i n gs p e e do ft h ec o m p u t e rn e t w o r k s i d sn e e d st oc o l l e c td a t aa n d t h e nm a t c hi t 、析t l lt h ef e a t u r ed a t a b a s e t h em a t c h i n gp r o c e s si st h eb o t t l e n e c ko ft h e w h o l ei d ss y s t e m sp r o c e s s i n gs p e e d t h e r e f o r , i ft h ef e a t r u em a t c h i n gp r o c e s si s a c c e l a r a t e db yh a r d w a r e ，t h e nt h ep e r f o r m a n c eo ft h ei d s s y s t e mw o u l db eg r e a t l y i m p r o v e d , e s p e c i a l l yt h ep r o c e s s i n gs p e e d a ns o p c ( s y s t e mo np r o g r a m m a b l ec h i p ) b a s e da r c h i t e c t u r eo ft h ei d ss y s t e m i sp r o p o s e d ，w h i c hc o n t a i n sa ns o f t w a r em o d u l er u n n i n go nt h en i o s i ip r o c e s s o ra n da n h a r d w a r ea c c e l a t r a t o r t h es o f t w a r em o d u l eu s e sp r o t o c o la n a l y s i st e h n o l o g yt od e t e c t m a l i c o u si n f o r m a t i o nc o n t a i n i n gi nt h en e t w o r kl a y e ro rt h et r a n s p o r t a t i o nl a y e r , t h e h a r d w a r ea c c e l a r a t i o nm o d u l ei sc o m p o s e do ft w os u b s i d i a r ym o d u l e ：t h eh e a dm a t c h m o d u l ea n dt h er e g u l e re x p r e s s i o nm a t c hm o d u l e t h eh e a dm a t c hm o d u l eu s e st r e e - b i t m a pa l g o r i t h m s a n dt h e r e g u l a re x p r e s s i o n m a t c hm o d u l eu s e sn f a s ( n o n e d e t e r m i n i s t i cf i n i t ea u t o m a t a ) t h ep r o p o s e da r c h i t e c t u r ei sr e a l i z e do na l t e r a c y c l o n e l if p g aa n di st e s t e do na l t e r ad e l ld e v e l o p m e n tb o a r d t h et e s tr e s u l ts h o w s t h a tt h ed e s i n g e ds y s t e mc o u l dc o r r e c t l yd e t e c ta l lm a l i c o u si n f o r m a t i o nh i d i n gi nt h e n e t w o r kd a t af l o w t h eh a r d w a r ea c c e l a r a t o r st h r o u g h p u ts p e e di s1 6 g b p s f i r s t l yt h ed e v e l o p m e n tb a c k g r o u do ft h ei d ss y s t e m ，t h eb a s i ct h c o r y so fi d s a n dt h ed e v e l o p i n gt r e n di sb r i e f l yi n t r o d u c e d ；s e c o n d l yt h et r e e - b i tm a pa l g o r i t h m s a n dt h en f as a t e - m a c h i n ea r ei n t r o d u c e d ；t h i r d l yt h eh a r d w a r ei m p l e m e n t a t i o no ft h e a e c e l a r a t o ra n dt h es o f t w a r ei m p l e m e n t a t i o ni si n t r o d u c e d ；f i n a l l y , t h es y s t e m st e s t r e s u l ta n da n a l y s i si sp r o p o s e d k e y w o r d s ：i d s ，r e g u l a re x p r e s s i o nm a t c h , n f a , t r e e - b i tm a p ，s o p c 图目录 图2 1 图2 2 图2 3 图2 _ 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 一1 0 图2 1 l 图2 1 2 图2 1 3 图2 1 4 图2 1 5 图2 1 6 图2 一1 7 图2 1 8 图2 1 9 图2 2 0 图2 2 l 图2 - 2 2 图2 2 3 图2 2 4 图3 。1 图3 2 图3 3 图3 - 4 图4 1 图4 2 图4 3 图4 4 图4 5 图目录 入侵检测系统原理6 包头分类算法分类8 采用t r e e - b i tm a p 算法构建的多比特决策树1 0 正则表达式、d f a 、n f a 之间的转换关系1 3 d f a 状态机例子13 n f a 状态机例子1 4 单个字符n f a 14 并置运算15 选择运算15 重复零次、一次或多次运算16 重复至少一次运算16 存在或不存在运算17 ( ( a i b ) 木) ( c d ) 语法树结构18 正则表达式生成n f a 状态机算法例子19 ( a b ) + c 木对应的n f a 状态机2 0 ( a b ) + c 木对应的电路结构2 0 基本n f a 状态机的存储数据结构一2 2 弹出a b c 后生成的n f a 状态机2 3 弹出后的n f a 状态机2 4 弹出木后的n f a 状态机2 4 弹出后的n f a 状态机2 5 弹出d e 后的n f a 状态机2 5 弹出i 后的n f a 状态机：2 6 弹出后的n f a 状态机2 6 系统功能2 9 入侵检测处理流程3 0 系统总体框图3 2 n i o s 处理器架构3 3 硬件加速器架构3 4 包头匹配模块架构3 5 匹配比特数示意图3 6 包头匹配电路的系统框图3 6 控制器的状态机3 7 v i 图目录 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 _ 1 1 图4 1 2 图4 1 3 图4 1 4 图4 - 1 5 图4 1 6 图4 1 7 图4 1 8 图4 1 9 图4 2 0 图4 2 1 图4 2 2 图4 2 3 图4 2 4 图4 2 5 图4 2 6 图5 1 图5 2 图5 3 图6 1 图6 2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 图6 9 图6 1 0 n o ne n dn o d e 存储结构3 7 e n dn o d e 存储结构。3 8 b i tv e c t o r 计算电路3 8 包头匹配模块仿真结果3 9 正则表达式匹配模块3 9 a s c i i 预解码器4 0 采用a s c i i 预解码后( a b ) + c 对应的电路。4 0 精确匹配电路结构4 1 前缀共享电路结构4 2 正则表达式匹配模块自动化生成流程4 3 正则表达式匹配模块仿真结果4 4 硬件加速器总线接口4 5 来自总线的读写信号同步4 5 慢时钟域到快时钟域同步时序4 6 硬件加速器组件接口信号_ 4 8 s o p c 系统模块结构4 9 系统综合结果4 9 设置m o d e l s i m 路径5 0 在n i o si d e 中选择m o d e l s i m 仿真选项5 l 使用m o d e l s i m 仿真5 1 s o p c 系统仿真结果：5 2 软件模块框架5 3 串口通信软件处理流程_ 6 2 串口通信软件界面6 2 d e l l 开发板6 4 科来数据包生成器6 5 配置应层数据存放地址寄存器a d d r3 2 b 6 6 配置应用层数据长度寄存器l e n3 2 b 6 7 配置目的地址寄存器s i p3 2 b 6 7 配置源口地址寄存器d i p3 2 b 6 7 配置源目端口号寄存器s pd p3 2 b 6 7 加速器匹配结束后产生中断信号6 7 检测利用协议漏洞进行的攻击6 8 检测利用i p 载荷进行入侵的行为。6 8 v 表目录 表目录 表2 1口地址前缀表达与规则号对应表9 表2 2正则表达式中的常用字符1 2 表2 3d f a 与n f a 存储要求以及处理复杂度比较17 表2 - 4符号优先级l8 表2 5需要处理的正则表达式运算符2 1 表4 1 c o n s t r a i n t r e p e t i t i o n 类型4 1 表4 2前缀共享例子4 3 表4 3硬件加速器寄存器组4 7 表5 1口分片重组表5 5 v i i i 缩略词表 英文缩写英文全称 d s s o p c p s n f a d f a p c r e t c p u d p 口 n p 缩略词表 i n t r u s i o nd e t c t i o ns y s t e m s y s t e mo np r o g r a m m a b l ec h i p i n t r u s i o np r o t e c t i o ns y s t e m n o n e - d e t e r m i n i s t i cf i n i t ea u t o m a t a d e t e r m i n i s t i cf i n i t ea u t o m a t a p e r lc o m p a t i b l er e g u l a r e x p r e s s i o n t r a n s p o r t a t i o nc o n t r o lp r o t c i c o l u s e rd a t a g r a mp r o t o c o l i n t e r n e tp r o t o c o l n e t w o r kp r o c e s s o r i x 中文释义 入侵检测系统 片上可编程系统 入侵防护系统 无穷自动机 有穷自动机 p e r l 兼容的正规表达式 传输控制协议 用户数据包协议 网际互联协议 网络处理器 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：趑塞，象 日期：矽届年月乡日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盔墨益岳导师签名：么垄公丛塾丛匕 日期：如o 年6 月；e l 第一章绪论 第一章绪论弟一早珀下匕 本章简要介绍了入侵检测系统的研究意义、实用价值及其发展历史与趋势， 简要回顾了特征匹配的硬件加速研究现状，最后简述了本论文的研究内容与章节 安排。 1 1 入侵检测技术背景 随着计算机用户的增长，以及网络流量的急速增长，计算机病毒及恶意代码 成了计算机用户最头疼的问题。2 0 0 7 年，中国互联网信息中心在其发表的中国互 联网发展状况统计报告中指出：中国网民人数已达1 3 7 0 0 万人，其中有9 1 的网 民( 约1 2 5 5 0 万人) 都曾遭受过计算机病毒的侵袭。在网络入侵事件频发的今天， 网络安全成了人们越来越关注的问题。 目前网络安全技术以被动防御为主，通常采用的技术有：防火墙技术、密码 技术、访问控制技术等。被动防御系统通常不会主动去发现入侵。因此，需要一 种能够主动探测入侵，并采取相应措施的系统来保障计算机网络的安全。入侵检 测技术就是这样一种安全防护系统。入侵检测系统通常在网络中的关键点收集数 据，然后对数据进行分析( 一般是与特征库进行匹配) ，若检测到入侵行为发生， 则采取相应的措施【。目前的入侵检测系统仍然属于被动防御的系统，但是相比 传统的防火墙等技术而言，入侵检测系统加入了能够主动探测入侵的特性，因此 其在保护计算机安全方面的能力比传统的防火墙等技术更强。入侵检测系统通常 会对于检测到的入侵行为采取以下措施【2 】： 1 监控并分析网络流量 ，2 找到网络中的脆弱部分 3 对敏感数据进行测试 电子科技大学硕士学位论文 1 2 入侵检测系统发展历史及趋势 2 0 世纪8 0 年代，d e n n i n g 在其一篇论文中提出了i d s 模型，最初该模型被 当作是计算机安全的一种补充手段【3 】：j a m s ea d e r s o n 在1 9 8 0 年提出了入侵检测 概念；m m 在1 9 8 6 年用c o b o l 开发了d i s c o v e r y 系统，该系统成为了第一个基于 主机的入侵检测系统；d o r t h y 与d e n n i n g 在1 9 8 7 年提出了入侵检测系统的模型； t e r e s al u n t 等研究人员在1 9 8 8 年提出了入侵检测专家系统；在本世纪9 0 年代研 究人员对入侵检测系统做了深入的研究，各种新的技术被不断提出：h e r b e l e i n 于 1 9 9 0 年提出网络安全监视器，m a r k c r o s b i e 使用自治代理技术提高了i d s 的性能。 目前，入侵检测系统作为成熟的产品已经广泛被人们接受，但是由于网络技 术的不断进步，对入侵检测系统也提出了更高的要求。 在防御入侵行为方面，由于入侵检测系统仍然属于被动防御系统，当系统检 测到入侵行为后，不会主动采取措施，如：断网、关闭连接等。因此入侵检测系 统未来的发展趋势是具有检测及防御功能。目前出现了入侵检测系统与防火墙联 动的安全防护系统【4 】。但是由于是联动，阻断时间上会出现滞后，往往攻击已经 发生了才出现阻断，这种阻断已经失去了意义。因此，i p s 系统应运而生，i p s 集 检测及防御于一身，是未来入侵检测系统发展的新方向1 5 】。 二十一世纪是计算机技术、网络技术飞速发展的时代，用户网络设备正朝着 高速化方向发展，千兆网络已经出现，并催生了各种千兆网络设备，如千兆网络 交换机、千兆网络服务器等。因此，对入侵检测系统提出了更高的要求系统 的处理速度要达到千兆以上。而传统的基于主机的入侵检测系统，如s n o r t 等均采 用软件的方式采集网络数据、进行协议分析与特征匹配，因此不能满足千兆网络 的要求。目前市场上已经出现了千兆级入侵检测产品，如华为赛门特克的n i p l 0 0 0 以及启明星辰天阗s 1 1 0 0 等，处理速度均达到了千兆级别。i d s 的核心技术是特 征匹配，这是系统处理速度的瓶颈所在【6 】。目前市场上的千兆级产品，从本质上 讲仍然是采用软件的方式实现特征匹配采用高性能的网络处理芯片( n e t w o r k p r o c e s s o r ) 及高性能协处理器实现指令级并行、线程级并行以及处理器级并行。 由于硬件在速度方面的绝对优势，基于硬件加速方式实现特征匹配的入侵检 测系统正成为当前学术界以及业界的研究热点。 2 第一章绪论 1 3 特征匹配的硬件加速研究状况 目前，基于硬件加速的入侵检测系统主要将特征匹配交由硬件加速器处理， 而其他与协议处理相关的部分仍然交给网络处理器进行处理。特征匹配分为包头 匹配与内容匹配，其中包头匹配技术源于用在路由器上的包分类技术；而内容匹 配主要采用正则表达式匹配实现。 包头匹配技术源于包分类技术，包分类技术是用于路由器上路由选择的关键 技术。t e r n a r yc o n t e n ta d d r e s s a b l em e m o r y ( t c a m ) 被广泛用于包分类应用。 t c a m 除了能够存储0 、l 二进制数据外，还能够存储“d o n tc a r e 状态。输入 数据与每个t c a m 项目进行比对，比对是并行完成的。为了改进t c a m 的匹配 效率，l i u 提出了改进型t c a m 技术以便于进行范围匹配【8 】。l a k s h m a n 提出了 b i tv e t o r 算法【9 】，b v 算法更易于采用硬件实现，它将口包头多个域( 源口地址、 目的口地址、源端口号、目的端口号以及协议类型) 的匹配分解成多个独立的匹 配问题。b v 算法的思想是：找到能够匹配域的所有规则，并将匹配结果用一个 比特向量表示。每条规则在向量中用一个比特表示。如果包头的某个域匹配某条 规则相应的域，则将该规则对应的比特位置l ，否则置0 。1 9 9 9 年，w i l l i a m n e a t h e r t o n 第一次提出了t r e e - b i tm a p 算法，该算法相比于其他包分类算法，更 适合于硬件电路实现，同时资源消耗更低。在前人的研究基础上，h a o y us o n g 提 出了b v - t c a m 架构【l 们，并第一次将t r e e - b i tm a p 算法应用于入侵检测的包头匹 配部分，并在x i l i n xf p g a 上进行了实现。 正则表达式由于其强大的描述能力，被越来越广泛的应用于规则集的描述。 正则表达匹配主要采用自动机的方式实现，j o l u le h o p c r o f t 在自动机理论中阐述 了如何由正则表达式生成n f a 状态机【1 1 1 。1 9 8 2 年，f l o y d 提出了n f a 的硬件实 现【1 2 】。s i d h u 与p r a s a n n a 提出了n f a 自动机的f p g a 硬件实现架构【13 1 。y a m a g a k i n 等提出了多字节n f a 状态机的实现算法【l 舢，提高了吞吐率。在以上研究的基础 上，j a nk o r e n e k 第一次提出了基于硬件加速器方式实现特征匹配的入侵检测过滤 器【1 5 1 。 随着千兆级网络的到来，对入侵检测系统的处理能力提出了更高的要求，因 此，对特征匹配进行硬件加速是入侵检测系统发展的必然趋势。如何提高硬件加 速器的吞吐率、可升级性以及降低硬件资源消耗仍然是今后的研究热点。 3 电子科技大学硕士学位论文 1 4s o p c 技术 s o p c 即s y s t e m o n a - p r o g r a m m a b l e - c h i p 的简称，该技术能够将整个电子系 统放到一块f p g a 上。s o p c 技术有两个特点：i s o p c 开发的系统是一个片上系 统( s o c ) 。2 s o p c 系统是可编程的。s o p c 技术打破了传统的以分离的集成电 路为基础的电子系统开发模式，同时s o p c 系统比传统的s o c 系统具有更好的可 升级性。s o p c 系统不仅能在开发的早期进行调试，更能够在现场对系统的主要 逻辑功能进行更正。 因此，本设计采用s o p c 技术实现。采用s o p c 技术能够方便的将硬件加速 器、r a m 控制器、u s b 等各种接口集成到系统中，使得系统具有很强的灵活性； 此外a l t c r a 提供了良好的软件开发环境：n i o si d e ，该环境支持系统在线调试、 f l a s h 烧写、b o o t l o a d e r 自动生成等。 1 5 论文内容及章节安排 网络流量的急速提升，对特征匹配进行硬件加速进行研究具有重要的科研及 实用意义。采用硬件加速方式实现特征匹配充分利用了硬件处理的并行性，使系 统具有更高的吞吐率，完全能够满足千兆网络的需求。本文在已有的研究基础上， 提出了基于s o p c 的入侵检测系统架构，特征匹配部分完全由硬件实现。该系统 在a l t c r ad e i i 开发板上进行了实现。本文的主要内容包括以下几个方面： 1 概述入侵检测系统、t r e e - b i tm a p 包头匹配算法以及正则表达式匹配算法。 2 提出特征匹配的硬件加速器架构。开发软件工具自动读取规则集，并生 成n f a 状态机，最后用n f a 状态机生成h d l 代码。 3 提出基于s o p c 的入侵检测系统架构：采用硬件加速的方式对提取自 s n o r t 规则集的2 0 0 条正则表达式进行匹配；采用嵌入式软件的方式进行 协议分析；设计上位机程序对报警信息进行实时显示与记录。 4 使用m o d e l s i m 对s o p c 系统进行仿真与测试；在a l t e r ad e l l 开发板 上对入侵检测系统进行测试。 论文的章节安排如下： 4 第一章绪论 第一章简述了入侵检测系统的发展背景、发展趋势，并对特征匹配的硬件加 速研究现状作了简要回顾，最后阐述了本文的主要研究内容及论文章节安排。 第二章对入侵检测系统的基本概念作了阐述，并对本设计中用到的包头匹配 t r e e - b i tm a p 算法以及n f a 自动机做了简要介绍。最后给出了由正则表达式自动 生成硬件电路的算法。 第三章对系统总体设计方案进行了描述，并给出了入侵检测系统的处理流程， 最后对各个模块做了简要介绍。 第四章重点描述了硬件加速器的架构、包头匹配模块设计及实现以及正则表 达式匹配模块的设计及实现，并给出了两个模块的仿真结果。最后将硬件加速器 集成到s o p c 系统。 第五章重点介绍了软件部分设计，包括嵌入式软件模块的设计以及上位机通 信软件模块的设计。 第六章给出了系统的测试结果，并对测试进行了分析。 第七章对全文进行了总结，并提出了下一步的研究改进方向。 5 电子科技大学硕士学位论文 第二章入侵检测系统概述及相关算法研究 本章主要简述了入侵检测系统的基本原理及入侵检测系统的分类。对t r e e - b i t m a p 包头匹配算法以及采用自动机实现正则表达式匹配的相关算法进行了简述。 最后，提出了由正则表达式生成h d l 代码的算法。 2 1 入侵检测系统概述 2 1 1 入侵检测系统原理 入侵检测是一个监控电脑或网络上所发生事件的过程。通过对这些捕捉到的 事件进行分析处理，能够发现到潜在的威胁。这些威胁包括：恶意软件、非法访 问越权访问等。入侵检测系统是一个能够将入侵检测过程自动化的系统。一个入 侵检测系统主要有3 个处理步骤【1 6 】：数据收集、数据分析和响应处理。 数据包 图2 1入侵检测系统原理 1 数据收集 由传感器从计算机或网络中收集主机日志、网络数据包、防火墙日志等系统 关心的数据。 2 数据分析 数据分析步骤首先对数据进行格式化处理，然后对收集到的数据进行分析( 包 括协议分析、查询知识库等) ，若发现异常行为，则产生报警信息。 3 响应处理 6 第二章入侵检测系统概述及相关算法研究 当入侵发生后，响应步骤负责采对报警信息进行处理，包括记录入侵日志、 通知管理员或者通知防火墙等。 一 2 1 2 入侵检测系统类型 根据各个步骤的实现方法不同，入侵检测系统可以分成很多种类。通常可以 根据入侵检测系统采用的技术、入侵检测的数据来源以及入侵检测系统的体系结 构来进行分类【朋。 2 1 2 1 按检测技术分类 入侵检测系统通常采用的检测技术分为：误用检测、协议分析以及异常入侵 检测三类。 误用检测又称为基于特征的入侵检n t l 8 】。系统的目的是检测入侵者的活动是 否与已知的特征相匹配。误用检测技术可以对已有的入侵方法进行有效检测，但 是无法检测新的入侵方法。 异常检测技术首先对主体的正常活动进行统计【1 9 1 ，并建立“正常活动档案。 若当前主体的活动与“正常活动档案不一致时，则视该活动为疑似入侵行为。 异常检测的难点在于如何对“正常活动 进行统计以及如何设计统计算法。 协议分析技术充分利用网络协议的规整性，能够快速检测某种特征攻击是否 存在【2 0 】。协议分析技术是特征匹配技术之外的一种新的入侵检测技术。 2 1 2 2 按数据来源分类 根据入侵检测系统数据来源的不同，可以将入侵检测系统分为：基于主机的 入侵检测系统和基于网络的入侵检测系统【2 1 1 。 基于主机的入侵检测系统通常安装在主机上，负责对主机的网络连接以及系 统日志进行分析与检查，当发现存在疑似攻击行为时，向管理员发出警报。 基于网络的入侵检测系统通常安装在需要防护的网络中，负责对网络中的数 据包进行分析与检查。放置于网络中的入侵检测引擎可以监视整个网络，发生入 侵行为时，负责采取相应的措施如：向管理员发出警报或直接切断网络连接等。 目前大部分商业化入侵检测产品都是基于网络的入侵检测系统。 7 电子科技大学硕士学位论文 2 1 2 3 按体系结构分类 入侵检测系统体系结构主要有两种体系结构：集中式入侵检测系统、分布式 入侵检测系统。 集中式入侵检测系统将位于不同主机上的嗅探器收集到的数据发送到一个中 央服务器进行集中分析处理。当主机数量增多时，中央处服务器的数据量会猛增， 而一旦中央服务器瘫痪，则整个系统就会崩溃。 分布式入侵检测系统将入侵检测任务分配给多个基于主机的入侵检测系统。 每个基于主机的入侵检测系统具有独立性，独立地监控当地主机的活动。与集中 式入侵检测系统相比，分布式入侵检测系统具有更高的安全性及可伸缩性。但是 其维护成本却相应提高了。 2 2 包头匹配算法 包头匹配算法的主要目的是将网络协议五元组( 源口地址、目的口地址、 源端口地址、目的端口地址以及协议类型) 与规则集中对应的域进行匹配。包头 匹配算法源于包分类算法，在介绍包头匹配算法之前有必要对包分类算法做简要 介绍。华盛顿大学工程及应用科学学院的t a y l o r , d a v i de 教授第一次较为全面地 对各种包分类算法做了统计【勿。包分类技术总体上而言分为四类，如图2 2 所示。 图2 2 包头分类算法分类 e x h a u s i t i v es e a r c h ：一次性搜索规则集中的所有域，典型代表技术：t c a m 。 d e c i s i o nt r e e ：根据规则集中的规则建立一棵决策树，用数据报中包头的相 应域来遍历这棵树。典型代表技术：g r i d o f - t r i e s 。 8 第二章入侵检测系统概述及相关算法研究 d e c o m p o s i t i o n ：将一次搜索多个域分解成二次性搜索单个独立的域。最后将 每个独立域的搜索结果组合从而得到搜索结构。典型代表技术：p a r a l l e lb v 。 t u p l es p a c e ：根据规则集中的指定比特位数划分规则集，采用简单的精确搜 索方法搜索划分后的规则子集。 2 2 1t r e e b i tm a p 算法概述 在众多的包分类算法中，t r e 冶- b i tm a p 算法是最适合硬件实现的算法。t r e e - b i t m a p 算法属于d e c i s i o nt r e e 算法中的一种。1 9 9 9 年，w i l l i a mn e a t h c r t o n 第一次 提出了t r e e - b i tm a p 算法，并使用该算法设计了硬件电路。2 0 0 5 年，h a o y us o n g 采用t r e e - b i tm a p 算法实现了应用于入侵检测系统的包头匹配，并在f g p a 上进 了实现。t r e e - b i tm a p 算法是一种多比特二叉决策树算法，是众多包分类算法中搜 索速度较快、资源消耗较少的好算法。 t r e e - b i t m a p 算法在多比特决策树的基础上，采用两个向量： i n t e r n a l _ t r e eb i tm a p 、e x t e r n a l t r e e - b i t - m a p 对每个大结点进行描述。所有的大结 点均按照从上到下，从左到右的顺序在存储器中依次存储。 表2 1 i p 地址前缀表达与规则号对应表 源口地址规则i d 号 1 ，5 0 0 0 0 010 0 0 0 0 0 0 0 0 02 ，3 0 0 0 0 1 宰牛乞宰宰_ 料 2 0 0 0 1 一一宰l 料 2 0 0 1 宰_ 幸宰枣木_ 料奉乞料 2 0 1 一一宰乞料 2 1 宰一料 乞料木l 2 0 0 0 0 _ 0 0 0 0 _ 0 0 0 0 一1 0104 如表2 。1 所示，源口地址采用前缀表达的方式进行描述，规则号i d 表示源d 地址所匹配的规则编号。用表3 一l 按照t r e e - b i tm a p 算法构造一棵多比特决策树， 该树的步长r 为4 ( 即每次输入4 个比特) ，并按照t r e e - b i tm a p 算法计算出各个比 特向量。最终的多比特决策树如图2 3 所示，图中黑色实心结点表示存在最长匹 配的点。二叉树左分支代表输入o ，右分支代表输入1 。 9 电子科技大学硕士学位论文 第一级 n o d e 3 第二级 图2 3采用t r e e - b i tm a p 算法构建的多比特决策树 图中结点之间若存在连接关系则用实线表示，不存在的连接关系用虚线表示。 图中共有7 个大结点，从上到下，从左到右依次编号为1 7 。每个大结点在存储 器中被表示为：i n t e r n a lt r e e - b i tm a p 、e x t e r n a lt r e e - b i tm a p 以及c h i l da d d r e s s 。采用 从上到下，从左到右的方式对小结点进行编号。若该点为匹配点，则该结点编号 所对应的位在i n t e r n a lt r e e - b i tm a p 中置1 。 i n t e r n a lt r e e b i t m a p 每个比特位所对应的最长匹配为： 木，0 幸，1 幸，0 0 ，0 1 ，1 0 ，1 1 * , 0 0 0 , 0 0 1 掌，0 1 0 , 0 1 1 木，1 0 0 , 1 0 1 木，1 1 0 宰，1 1 1 幸) 。如图2 - 3 中 的第一级中的大结点i n t e r n a lt r e e - b i tm a p 为：1 0 1 0 1 0 0 0 1 0 0 0 0 0 。在该大结点中第 l 、3 、5 、9 小结点为匹配点。所以对应的i n t e r n a lt r e e - b i tm a p 在第1 、3 、5 、9 位为1 。按照从左到右的方式对大结点所有可能存在的到子结点的边进行编号。 如图2 3 所示第一级大结点的e x t e r n a lt r e e - b i t m a p 为：1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 。第1 、 2 比特为1 表明该大结点存在两个子结点，并且子结点编号为l 、2 。图2 3 中的 1 0 第二章入侵检测系统概述及相关算法研究 箭头代表父结点指向子结点的指针。每个父结点只包含一个指向第一个子结点的 指针。其他子结点的地址可以根据e x t e r n a lt r e e - b i tm a p 计算出来。 子结点地址计算方法为：用输入比特遍历e x t e r n a lt r e eb i tm a p ，计算出在该 比特位置以前的1 的个数i ，假设每个大结点的存储大小为s ，并设当前结点的地 址为y ，则子结点的地址为：y + ( i 幸s ) 。 此外，如图2 3 所示，在树的第四级的所有结点均含有3 0 个小结点，并且只 含有长度为3 0 比特的i n t e r n a lt r e e - b i tm a p 。因为最后一级没有子结点需要访问， 因此不需要存储e x t e r n a lt r e e - b i tm a p 。同时将i n t e r n a lt r e e - b i tm a p 扩展1 6 个比特， 可以将最后一级多余的1 6 个小结点包含到一个大结点中来，从而减少大结点个 数，进而减少存储空间。 与包分类问题不同的是，包头匹配需要知道哪些规则被匹配，因此需要在搜 寻到匹配点后得到匹配结果信息。如图2 3 所示各个匹配点所对应的方框中的5 比特向量表示该匹配点所对应的匹配结果。如第一级大结点中编号为3 的小结点 所对应的匹配结果为：0 1 0 0 0 ，表示第二条规则被匹配( 小结点3 所对应的前缀表 达为：l 宰木木宰枣木幸| c 木雄枣枣木宰宰) 。 2 3 正则表达式匹配算法 正则表达式由于其强大的描述能力，越来越多的用于入侵检测系统规则集的 描述。j o h ne