（通信与信息系统专业论文）网络安全日志审计系统中实时审计技术的研究与实现.pdf

r e s e a r c ha n di m p l e ma n tt h et e c h n o l o g y o fr e a l t i m ea u d i ti nt h en e t w o r k s e c u r i t yl o ga u d i ts y s t e m a bs t r a c t r e a l - t i m ea u d i ti st h ec o r ec o m p o n e n t so ft h ea u d i ts y s t e m ，w h i c hd o p a t t e r nm a t c h i n gf o rt h el o gd a t at h a ta c c o r d i n gt ot h ep r e s e tr u l e so ft h e u s e r ，t h e nt od e t e c ta n df i n do u tt h es u b j e c to fa t t a c k ，g e n e r a t ea l a r m i n f o r m a t i o n r e f e r st ot h ek e yt e c h n o l o g i e so fp a t t e mm a t c h i n ga n dr u l e s s e a r c h i n gi nt h er e a l t i m ea u d i t ，t h ep a p e r sd i ds o m er e s e a r c h e sa n dp u t f o r w a r dt h ec o r r e s p o n d i n gi m p r o v e da l g o r i t h m f i r s t l y ，i ns o m ea s p e c t so fp a t t e r nm a t c h i n g ，t h ep a p e r sb a s e do nt h e c h a r a c t e r i s t i c so fn e t w o r ks e c u r i t yl o ga u d i ts y s t e m ，t or e s e a r c ha n d i m p r o v et h eb o y e r - m o o r ea l g o r i t h m a n dw u m a n b e ra l g o r i t h m ，a n d w h a t s m o r e ，c o r r e s p o n d i n g l yp r o p o s e ds i n g l e - p a t t e r nm a t c h i n g i m p r o v e da l g o r i t h m so fb m l aa n dm u l t i - p a t t e mm a t c h i n gi m p r o v e d a l g o r i t h m so fl s p w m a n df a s t e rm a t c h i n gs p e e dw h e na d d i t i o no f m i n i m a lo v e r h e a ds p a c e s e c o n d l y ，i nt h ea s p e c t so fr u l e ss e a r c h i n g ，i n i i 1 o r d e rt oi m p r o v et h es e a r c h i n ge f f i c i e n c y ，t h ep a p e r sb a s e do nt h em i n d o fc o n d i t i o n sh i e r a r c h i c a l ，p r o p o s e da na d a p t i v er u l eb a s e d e s i g n e d m e t h o d s ，w h i c hw h e ng e n e r a t e dt h er u l e st r e e s ，t h es y s t e mo v e r h e a dt i m e h a da l li n c r e a s eo f2 7 6 ，b u t3 8 2 o ft h es e a r c hs p e e dh a v er a i s e d w h e ny o us e a r c ht h er u l eb a s e f i n a l l y ，t h et h e s i su s et h ea b o v ea l g o r i t h m i nt h er e a l t i m ea u d i tm o d u l eo ft h ea u d i ts y s t e m ，a n dm a k eal o to f t e s t i n g ，t h er e s u l t ss h o wt h a tt h e s ea l g o r i t h m sc a ni m p r o v et h er e a l t i m e a u d i te f f i c i e n c yo ft h es y s t e mg r e a t l y k e y w o r d s ：l o ga u d i ts y s t e m ；r e a l t i m ea u d i t ；p a t t e r nm a t c h i n g ； l s p w m a l g o r i t h m ；b m l aa l g o r i t h m ；a d a p t i v er u l eb a s e i i i 啪43 舢2伽4 删3删z 删-v ，一l一；-i if； 目录 摘要i a b s t r a c t i i 目录i v l 引言1 1 1研究背景l 1 1 1网络安全现状1 1 1 2网络安全技术介绍2 1 2日志审计技术概述5 1 2 1日志审计系统的研究现状5 1 2 2日志审计技术简介7 1 2 3现有日志审计技术存在的问题8 1 3研究内容及意义9 1 4论文的组织结构1 0 2基于日志审计系统的模式匹配算法设计1 2 2 1模式匹配算法在实时审计中的应用1 2 2 1 1模式匹配算法的背景及原理1 2 2 1 2单模式匹配算法及其相关改进算法的研究现状1 3 2 1 3 多模式匹配算法及其相关改进算法的研究现状1 7 2 2基于b m 改进的单模式匹配算法2 1 2 2 1b m 算法及各改进算法的不足分析2 1 2 2 2b m l a 单模式匹配算法的设计2 2 2 2 3b m l a 单模式匹配算法的性能分析2 5 2 3基于w u m a n b e r 改进的多模式匹配算法2 5 2 3 1w m 算法及各改进算法的不足分析2 5 2 3 2l s p w m 多模式匹配算法的设计2 6 2 3 3l s p w m 多模式匹配算法的性能分析3 3 2 4本章小结3 3 3一种适用于日志审计系统的简单自适应规则库设计3 4 3 1现有规则库设计方法及不足之处3 4 3 2自适应规则库的设计方法3 5 3 2 1自适应规则库的设计3 5 3 2 2自适应规则库的构建3 6 3 2 3自适应规则库的排序算法3 7 3 3 自适应规则库设计方法的性能分析4 0 3 4本章小结4 0 i v 1一再jj!jlj r 一一一 l l 4日志审计系统的总体设计及实时审计模块的实现与分析4 1 4 1日志审计系统分析4 1 4 1 1日志审计系统的整体方案设计4 1 4 i 2实时审计模块的总体设计4 3 4 2实时审计模块的实现分析5 l 4 2 1实时审计引擎设计与审计流程5 2 4 2 2实时匹配规则库子模块的实现5 3 4 2 3b m l a 和l s p w m 模式匹配算法实现方案5 8 4 2 4自适应规则库的设计实现方案6 1 4 3本章小结6 2 5 测试分析6 3 5 1实验平台搭建6 3 5 2功能测试6 6 5 3性能测试6 9 5 4本章小结7 5 6全文总结及展望；7 6 6 1论文总结7 6 6 2下一步工作7 7 参考文献7 8 本文作者硕士期间参加的科研项月及发表的学术论文8 0 致谢8 1 独创性声明8 2 关于论文使用授权的说明8 2 v l 引言 当今世界网络应用越来越普及，在信息化社会中，网络已经深入到政治、经 济乃至人们的生活中。 但是伴随而来的网络安全问题也日益凸显，传统的网络安全技术已经越来越 不能满足网络安全的需要，我们更需要对入侵行为进行记录以便在任何时候再 现，甚至是提取出未曾发现的攻击模式。本章追本溯源，重点介绍了日志审计系 统研究现状，现存的日志审计技术存在的问题等。 1 1 研究背景 该节首先对网络安全现状和网络安全技术作简要介绍，接着介绍网络安全审 计技术，并引出本文所要研究的日志审计技术。 1 1 1 网络安全现状 信息化社会中，信息安全所面临的威胁己由来已久。随着因特网的迅猛发展， 更进一步暴露出了这种自由网络空间具有的无中心、无管理、不可控、不可信等 不安全的特征，且形成了对一切现存社会秩序的威胁。 根据国家计算机病毒应急处理中心的调查显示：2 0 0 8 年中国信息网络安全事 件发生比例为6 2 7 ，计算机病毒感染率高8 5 5 7 ，因病毒感染造成经济损失的 比率达到了6 3 5 7 。上述安全问题，已覆盖了各个重要敏感的安全领域，随着国 家信息化的进一步发展，还将更充分更深入地暴露出我国信息网络的安全隐患， 遭受更大的威胁和风险。 传统的信息安全技术，诸如身份认证技术、加解密技术、边界防护技术、访 问控制技术、检测监控技术等，尽管在一定程度上满足信息安全的需要，但是面 对网络中复杂的安全问题时，仍然无法解决问题。比如，目前公认的最为成熟的 防火墙技术，虽然可以在检测粗粒度数据包和内外部隔离上起着巨大作用，但是 其在对规则配置的复杂要求和应用支持速度方面存在缺陷。同样，当前的入侵检 -1ljl。1 】 r 。1 。一一一 l 测技术( i d e s ) 在面临黑客采取分布式攻击时也存在着较高的漏报率和误报率【l j 。 因此我们需要一个系统不仅能提供安全保护，诸如抵抗外来入侵，监控内网 泄密，而且还能克服静态安全防护体系的安全管理缺陷，整合信息源【2 】。在此， 网络安全日志审计系统很好地解决了这一问题，作为安全防护系统，它不仅能够 解决某些特殊入侵检测系统无法检测的入侵行为，并且能够对入侵行为进行记录 以便在任何时候再现，甚至是提取出未曾发现的攻击模式。作为系统管理平台， 它能够集中管理网络众多设备的日志信息，极大提高决策的效率。 而日志审计系统进行实时审计时涉及到大量日志文件，需要对其进行规则匹 配。随着网络应用的日益增长和大量应用层软件的开发，设计时必须设法提高攻 击的实时分析技术，必须提高对各种入侵模式字段的规则匹配速度，以适应网络 速度的提高和网络流量的增加。 1 1 2 网络安全技术介绍 网络的安全性主要包括网络服务的可用性，网络信息的保密性和网络信息的 完整性，下面简要介绍当前的网络安全技术： ( 1 ) 加密技术 加密技术主要分两种：对称密钥和公钥加密技术。其主要运用于两个方面： 一是加密信息，另一个是数字签名技术，用自己的私人钥匙将信息加密后发送。 接收方只有用发信者的公用钥匙，才能解开消息。这种“署名”方式一方面可以 证明这条信息确实是由发信者发出的，而且保证消息的完整性，另一方面也确保 发信者对消息的不可抵赖性3 1 。 ( 2 ) 身份验证技术 身份验证是一致性验证的一种。身份验证主要包括验证依据、验证系统和安 全要求。身份验证技术是在计算机中最早应用的安全技术，现在也仍在广泛应用， 它是互联网上信息安全的第一道屏障。 ( 3 ) 存取控制技术 存取控制技术主要规定主体对客体的操作权力。存取控制技术主要包括人员 限制、权限控制、数据标识、类型控制和风险分析。存取控制一般与身份验证技 术一起使用，赋予不同身份的用户以不同的操作权限，以实现不同安全级别的信 息分级管理。 ( 4 ) 数据完整性技术 数据完整性技术是证明收到的数据和原来数据完全一致的手段。检查手段是 最早采用数据完整性验证的方法，它虽只起到基本的验证作用，不能保证数据的 完整性，但由于实现简单，现在仍广泛应用于网络数据的传输。而数字签名等算 法也是常用的检查完整性的方法，但由于实现复杂，系统开销比较大，一般只用 于完整性要求较高的领域。 ( 5 ) 安全协议 安全协议的建立和完善是安全保密系统走上规范化、标准化道路的基本因 素。一个较为完善的内部网和安全保密系统，至少要实现加密机制、验证机制和 保护机制。 ( 6 ) 防火墙技术 防火墙的作用是阻挡外部不安全因素，从而影响内部网络，其目的就是防止 外部网络用户未经授权的访问。目前，主要采用的防火墙技术是包过滤、应用网 关、子网屏蔽等5 1 。 防火墙技术一般分为两类：1 ) 网络级防火墙主要功能是防止外来非法入侵。 其主要包括两方面，拒绝不符合规则的数据进入和检查访问用户的登录是否合 法。2 ) 应用级防火墙主要功能是从应用程序来进行接入控制。通常使用应用网 关活代理服务器来区分各种应用。例如，可以只允许f t p 应用的通过，而阻止访 问某网站的应用通过【4 】。 ( 7 ) 入侵检测技术 入侵检测技术( i d s ) 通过对收集到的信息进行分析，可以检测出对计算机 和网络资源的恶意使用的行为，并对其进行相应的处理。既包括系统外部的入侵， 又包括内部用户的非授权行为，是一种用于检测计算机网络中违反安全策略行为 的技术 5 】o 入侵检测系统有待解决的问题： 一入侵检测系统对加密的数据流及交换网络下的数据流不能进行检测，并 且其本身易受攻击。 检测速度过慢，难以跟上网络传输速度，导致误报率和漏报率。 入侵检测系统难以和网络安全进行信息交互，共同合作发现攻击并阻止 攻击【5 】o ( 8 ) 网络安全审计技术 网络安全审计技术是一种基于信息流的数据采集、分析、识别和资源审计封 锁，以便报警、处理的技术手段【l 】。通过实时审计网络数据，根据用户设定的安 全控制策略，对受控对象的活动进行审计。通过多级、分布式的网络审计、管理、 控制机制，以实现对内部网关资源的全局控制、把握和调度能力。为管理人员提 供了一种审计、检查当前系统运行状态的有效手段【7 1 。 网络安全审计技术主要包括主机审计技术、网络审计技术和日志审计技术。 1 ) 主机审计技术 主机审计技术是通过记录用户各种操作行为，或者捕获网络数据包分析用户 的网络行为，以查询用户可疑、异常的行为。按照行为类型划分，可分为：用户 登入退出系统的审计，用户查询、添加、删除、修改操作的审计，系统管理审 计，屏幕保护程序启动和退出的审计。该技术的目的是达到审计安全漏洞、审计 合法和非法或入侵操作、监控上网行为和内容以及向外拷贝文件行为、监控用户 非工作行为【6 1 。 2 ) 网络审计技术 网络审计技术是通过旁路和串接的方式实现对网络数据包的捕获，对协议数 据分析和还原，可达到审计服务器、用户电脑、数据库、应用系统的安全漏洞、 合法和非法或入侵操作、监控上网行为和内容、监控用户非工作行为等目的【8 1 。 3 ) 日志审计技术 日志审计技术通过s n m p 、s y s l o g 、o p s e c 或者其他的日志接口从各种网 络设备、服务器、用户电脑、数据库、应用系统和网络安全设备中收集日志，进 行实时分析、事后分析，对告警日志产生报警【l o 】。 综上所述，目前网络安全技术多种多样，方法也各有利弊，没有一种方法是 万能的。网络安全审计技术虽然只是处于探索阶段，其审计重点也在网络的访问 行为和网络中的各种数据。但是其作为一个新兴的概念和发展方向，已经表现出 强大的生命力。作为对防火墙系统和入侵检测系统的一个补充，它一般处在防火 墙和人侵检测系统之后，成为网络的第三道安全闸门。它能够检测出某些入侵检 测系统无法检测的行为；其次它可以对入侵的行为进行记录，并可以对其进行再 现以达到取证的目的；最后它可以提供一些未知的入侵和潜在的入侵行为等。日 志审计系统通过分析各设备、系统、应用、数据库产生的运行日志，能够及时发 现入侵检测系统检测到的各类安全隐患，并及时给予告警，从而避免安全事件的 发生。一般来说，网络安全审计系统能够发现的攻击种类大大高于入侵检测系统， 而且误报率也没有入侵检测系统那样的高【9 1 。 日志审计技术是网络安全审计技术最为常用的一种，也是最有效，发展最为 快速的一种，围绕着该概念产生了多种产品与解决方案。 1 2 日志审计技术概述 该节对日志审计技术进行概述，具体内容包括：日志审计系统的研究现状、 日志审计技术简介及现有日志审计技术存在的问题，并着重指出了论文的研究内 容及创新点。 1 2 1 日志审计系统的研究现状 目前日志审计技术尚处于探索阶段，国内外各种日志审计系统产品种类繁 多，除了个别企业拥有专利外，其余的产品都大同小异，虽然在功能上已基本满 足应用的要求，但在性能上将面对着网络日益增长庞大的日志数量的挑战。下面 先简要介绍目前市场上国内外的一些主流产品及其特点。 ( 1 ) 国内产品技术研究现状 x l o g 网络日志审计系统：该系统是由华为3 c o m 公司研发的低成本、可扩展 的网络日志信息审计与分析系统，能够与路由器、以太网交换机、b a s 设备等共 同组网，完成对n a t 、f l o w 、d i g 等多种网络日志的采集、统计与分析。可以 追溯网络使用行为，监视异常活动，为合理的网络规划提供重要参考。特点包括： 全面的日志采集、基于x m l 模板的数据分析引擎、灵活的统计分析、按需定制 的报表与审计、可扩展的体系结构【】。 l o g b a s e 日志管理综合审计系统：该系统是由思福迪公司研发的日志审计系 统，其可涵盖多种上网行为日志( h t t p f t p p 2 p i m ) ，数据库操作日志 ( o r a c l e s y s b a s e i n f o r m i x m y s q l ) ，全面收集系统各组成部分( 网络 5 设备、操作系统、应用系统、安全设备) 的运行日志。系统采用统一的日志格式， 并提供日志海量存储和高速检索功能，系统运用关键字实时跟踪分析技术，从事 件源、事件时间、事件目的对象、事件使用方法、事件频率各个角度，提供统计 分析报告，帮助用户在统一管理互联网访问、数据库操作的同时，及时发现安全 隐患【l l 】。 联想网御安全审计系统：该系统是由联想网御公司开发的日志审计分析平 台。其遵循c s c 关联安全标准，负责收集各类安全设备、网络设备和主机系统的 日志和事件信息，并进行统一的存储、备份、管理与统计分析，能够协助用户实 时监测网络中的恶意攻击，防范安全风险，实现用户的整体安全。特点：种类丰 富的事件审计、海量可信的日志管理、强大的日志在线分析、分布式安全审计管 理、产品部署灵活。 e t r u s t a u d i t 志审计系统：该系统是由冠群金辰公司研发的日志审计系统。 该系统通过跨平台的集中管理，先集中收集来自不同操作系统服务器、e t r u s t 安 全系统、以及第三方网络和安全设备的日志和事件信息，从海量数据库中精确识 别出关键的安全事件数据，有效地分析来自异构系统的安全事件数据。通过归类、 合并、关联、优化、直观呈现等方法，使管理员轻松识别网络环境中潜在的恶意 威胁活动。其产品特点有：接近实时的报警管理、跨平台事件管理、支持定制模 式识别、强大的过滤功能、开放且可扩展的设计、集中式的策略管理、中央审计 日志数据仓库、强大的报表功能、集成其它的e t r u s t 解决方案和u n i c e n t e r 等。 天碉网络安全审计系统：是由肩明星辰公司研发的对网络数据流进行采集、 分析和识别，实时监视网络系统的运行状态，记录网络事件，发现安全隐患，并 对网络活动的相关信息进行存储、分析和审计回放的审计系统软件。其特点是： 灵活的分布式管理、方便的定制审计内容、高度的自身安全保障、广泛的联动响 应支持、方便的统一管理平台。 t o p s e ca u d i t o r 安全审计综合分析系统：是由北京天融信科技有限公司开发 的产品。该系统对采集到的日志统一管理，对入侵行为进行检测，自动生成各种 综合报表和风险报告。该系统的特点：能够采集多种日志，包括入侵检测系统日 志、操作系统日志、防火墙系统日志、路由设备日志以及各种服务器的应用日志。 s e c f o x l a s 日志分析系统：是由网神公司研发的一个全面的、面向业务的、 6 集中的安全审计平台，能够收集来自i t 资源环境中各种设备和应用的安全日志， 并进行存储、监控、分析、报警、响应和报告。s e c f o x l a s 能够实时地对采集 到的不同类型的信息进行归一化和实时关联分析，通过统一的控制台界面进行实 时、可视化的呈现，协助安全管理人员迅速准确地识别安全事故，消除了管理员 在多个控制台之间来回切换的烦恼，同时提高工作效率。 ( 2 ) 国外产品技术研究现状 l o g l o g i c 日志管理平台：该系统是由美国日志管理公司研发的首个标准的 日志分析管理平台。其产品特点：基于硬件的一体化、独特的数据关联分析、基 于海量日志的各种分析报表、基于海量日志数据处理、独特的通过s y s l o g 的 警报机制、分布式的系统、内置防火墙和网络包分析工具、灵活定制日志的搜索 过滤条件、部署设备灵活f 4 3 】。 r s a e n v i s i o n 平台：是由r s a 公司研发能够提供唯一的信息安全及事件管理 解决方案，该平台横跨用户的整个信息基础设施，从交换机和路由器到安全设备， 主机资产，应用软件，服务器及存储层，提供所有安全威胁的1 0 0 可视化。其 通过l o g s m a r ti n t e m e tp r o t o c o ld a t a b a s e ( i p d b ) 技术，对来自网络各个部分的 所有必要数据进行实时集合和分析。特点：事件管理器、采取i p d b 及预设报表、 模板等技术h 3 1 。 综上所述，目前的日志审计产品各有其适用的领域和范围，都只是针对某一 领域的应用。 1 2 2 日志审计技术简介 本文主要研究的方向是日志审计技术，所以接下来着重介绍日志审计技术。 日志审计技术就是把日志作为研究对象，通过对各类日志进行实时分析和事后分 析，查找出各种恶意攻击、潜在的异常行为等。日志审计技术包括：数据采集、 数据处理、实时审计数据、数据存储、数据挖掘。 首先介绍日志审计的功能： ( 1 ) 对于正在遭遇的攻击，通过对日志进行实时审计，可以即时告知管理 员，阻止各种恶意攻击。 ( 2 ) 对日志进行事后挖掘分析，既可以查找到难以发现的入侵行为，并对 其进行补救措施，又可以判断对某个网站的访问是否合法等。 ( 3 ) 存储好原始的日志信息，为惩处恶意攻击者，提供重要的证据。 接着介绍日志审计技术的流程： ( 1 ) 数据采集：采用分布式架构，通过各个采集器实时采集日志数据。而 采集数据的实时性、安全性、完整性将是决定数据采集有效性的关键因素。 ( 2 ) 数据处理：将数据进行过滤和处理，过滤出所需数据，并对数据进行 分类。 ( 3 ) 实时审计数据：根据预先设定的规则对日志数据进行模式匹配，以发 现是否有告警日志，查找出所受到的攻击。模式匹配的速度与规则库搜索的速度 是两个影响实时审计效率的关键因素【4 3 】。 ( 4 ) 数据存储：将数据分门别类存储进数据库，便于管理员日后查看。数 据表设计的合理性是影响查找数据速度的一个关键因素。 ( 5 ) 数据挖掘：通过关联规则挖掘算法，对日志进行事后分析，找出隐藏 的异常行为【8 】。 1 2 3 现有日志审计技术存在的问题 虽然目前已经有大量的性能较好的日志审计系统，但是普遍存在着以下问 题： ( 1 ) 日益增大的日志信息量使得传输速度不能满足要求 因为日志审计系统主要处理的是系统各组成部分( 网络设备、操作系统、应 用系统、安全设备) 的运行日志，随着这些设备的功能不断增强，性能不断的提 高，所产生的日志信息也越来越多。拿一台普通的服务器主机来说，每天所产生 的日志就有几兆，上万条之多，更不用说处于核心地位的服务器了。 对于日志审计系统的采集中心传输日志数据的安全性、可靠性、实时性提出 了更高的要求。既要保证传输时不被别人篡改、截取、破坏，又要保证由于网络 拥挤等原因造成的传输延时，传输失败时能够重传，最后又要保证能够实时采集 日志数据。 但是随着日志信息量的不断增大，传输日志信息的速度已越来越不能满足要 求。 8 ( 2 ) 模式匹配性能差 当日志被采集后，需要根据事先设定的安全策略对日志进行实时审计，即判 断哪些日志是安全的，哪些日志是告警日志。对于告警日志，我们需要将它隔离， 并向管理员发出告警信息，以便管理员能够即时做出反应，阻止恶意攻击。因此， 对于安全策略的匹配，即模式匹配的速度显得尤为重要。 而如今，处理一台a p a c h e 服务器每天的网络访问日志，即h t t p 类日志，就 可能需要比较上万次，模式匹配的时间往往要占到整个系统运行时间的将近一 半。因此必须加快模式匹配的速度，提高对日志进行实时审计的效率。 ( 3 ) 规则库搜索速度慢 随着网络的安全性日益降低，各种恶意攻击层出不穷，管理员为了及时发现 攻击，所设置的安全策略也日益增多。于是规则数目迅速增加，规则库变得越来 越庞大，为了提高实时审计的效率，搜索规则库的速度也成为了仅次于模式匹配 速度的第二重要因素。而如今由于规则库设计的不合理，导致搜索规则库的速度 较慢，影响了实时审计的效率。 ( 4 ) 系统性能低 处理、存储日志信息要遵循一定的流程，但由于日志处理流程的设计不合理， 规则库的设计不合理，数据库表格的分类不明确，使得整个系统的性能降低。 1 3 研究内容及意义 本文主要对网络安全日志审计系统中的实时审计技术进行研究。其中研究的 主要内容包括模式匹配算法、规则库搜索等关键技术。 本文的主要工作如下： ( 1 ) 针对网络安全现状和存在的问题作了分析，采用良好的系统架构方法 对整个日志审计系统的整体架构进行研究与设计。 ( 2 ) 介绍了多种单模式匹配算法和多模式匹配算法，并对其进行比较，指 出其优缺点。 ( 3 ) 重点对审计中心的实时审计技术作了研究，改进了b o y e r - m o o r e 单模 式匹配算法和w u m a n b e r 多模式匹配算法，使之适合网络安全审计系统的运用， 并加快了实时审计的速度。 9 ( 4 ) 重点对实时审计的规则库设计进行研究，建立自适应性规则树，以加 快搜索规则库的速度。 本文的贡献如下： ( 1 ) 针对网络安全审计系统的特点，对原b o y e r - m o o r e 单模式匹配算法和 w u m a n b e r 多模式匹配算法进行改进，并提出了相应的单模式匹配改进算法 b m l a 和多模式匹配改进算法l s p w m ，在增加了极少的空间开销下，加快了匹 配速度。 ( 2 ) 针对网络安全审计系统的特点，基于条件分层的思想提出了一种自适 应的规则库设计方法，虽然在生成规则树时，系统开销时间增加了2 7 6 ，但是 在搜索规则库时速度提升了3 8 2 。 本文研究的意义如下： ( 1 ) 研究的意义：日志审计系统不仅能够解决某些特殊入侵检测系统无法 检测的入侵行为，并且能够对入侵行为进行记录以便在任何时候再现，通过实时 分析发现安全威胁。 ( 2 ) 设计的思路：采用良好的系统架构，严格按照软件工程的开发流程， 从需求分析到详细设计，再到测试和维护，极大地提高了整个系统的可靠性、安 全性、可扩展性、兼容性等性能。 ( 3 ) 关键技术方面：通过对模式匹配算法和规则库设计方法的改进，从而 提高了实时审计的效率。 ( 4 ) 对于本课题组的贡献：完成了实时审计模块的设计与实现，并将改进 的模式匹配算法和规则库设计方法应用于实时审计中。这些都对整个系统的改进 与研究奠定了基础。 1 4 论文的组织结构 本文分析了当前的日志审计系统的相关技术，对日志审计系统中实时审计的 关键技术进行研究，并将改进的模式匹配算法和构建自适应性规则库的思想应用 于实时审计模块中，提高了其运行的效率。 本文的正文部分共分为六章，内容安排如下： 第一章介绍了安全审计技术的背景。首先介绍当前的网络安全现状及网络安 1 0 全技术。接着介绍日志审计系统的发展及研究现状，现存的日志审计技术存在的 问题。最后提出本文的创新点及研究意义。 第二章介绍了实时审计模块中的一个关键技术：b m l a 单模式匹配算法和 l s p w m 多模式匹配算法，这两个改进算法的提出可以加快模式匹配速度，从而 提高整个实时审计模块运行的效率。 第三章研究了实时审计模块的另一个关键技术：实时审计模块中规则树的设 计，通过加入分层思想和自适应的思想，以加快搜索规则库的速度。 第四章主要介绍了安全审计系统的设计及相关的改进算法在实时审计中的 运用。首先介绍审计系统的整体方案设计，审计系统中实时审计模块的设计。接 着介绍了模式匹配改进算法和规则树在实时审计模块中的实现方案。 第五章是对整个实时审计模块进行了功能和性能方面的测试。 第六章是总结和展望，对全文作了总结，并提出了下一步研究工作的设想。 2 基于日志审计系统的模式匹配算法设计 日志审计系统通常由数据采集代理、数据采集中心、实时审计、日志存储、 事后审计、管理及查询这六大核心部件组成。其中实时审计的主要作用是根据管 理员设定的安全策略对各种设备的日志信息进行模式匹配，以发现存在的危险， 向管理员和用户发出告警信息。 要实现上述的实时审计效果，模式匹配是必不可少的技术手段。本章中，论 文在对现有的模式匹配算法分析的基础上，提出了改进的单模式匹配算法b m l a 和多模式匹配算法l s p w m 。算法通过加快模式匹配的速度，来提高系统的实时 审计效率。 2 1 模式匹配算法在实时审计中的应用 该节介绍了模式匹配算法的背景及原理，单模式匹配算法及其相关改进算法 的研究现状，多模式匹配算法及其相关改进算法的研究现状等内容。 2 1 1 模式匹配算法的背景及原理 模式匹配算法包括单模式匹配算法、多模式匹配算法，就是将收集到的信息 与事先定义好的安全策略进行对比，以发现违背安全策略的行为。其定义如下： 设定两个字符串t 和p ，其中字符串t 称为文本串，字符串p 称为模式串。也可 以将其形式化描述为：设有文本t = t i t 2 t 。( 长度为n ) ，模式p = p l p 2 p m ( 长 度为m ) ，并且m s ) ，p s + l n 】= p 【l n - s 1 ( i k i 将模式串末尾p 【m 】与t 陋】处对齐。 t u n e d b m 1 s ( t u n e db o y e r - m o o r ea l g o r i t h m ) 只使用了b a d c h a r 函数。在查 找阶段，算法只查找p 【m 】和文本是否匹配，若不匹配则模式串一直右移。 李必鹏提出：用一个6 ( x ) 函数判断文本某字符在模式串中出现的次数，如 果出现一次用f l a g 变量记录下第一个6 ( t i 】) = 1 的指针值。当匹配失败后，将文 本串的指针修改为m + f l a g 。如果f l a g 为0 表示匹配失败处之后的字符全都多次在 模式串中出现，下一次比较将由p 【m 】与t i + d 【t j 】重新匹配。 2 ) 对b m 好后缀规则的各改进算法 贺龙涛提出【2 8 】：将好后缀和坏字符规则合并为一个好后缀表。由于只使用 一个好后缀表，当匹配失败后可以比b m 少一次比较操作。李雪梅提出：改进的 算法除了利用已匹配字符和匹配失败字符信息外，还利用下一个字符的信息来计 算跳跃距离。 徐成提出【19 】：模式串与文本字符串进行匹配时采用从模式两端向中间位置 交替的匹配顺序，模式匹配先从模式最右端p 【m 】开始进行。若p 【m 】匹配不成功，则 通过s k i p i 函数计算模式向右移动的距离；若p 【m 】匹配成功，再比较p q 。若p 1 】匹配 成功，则按上述方法依次对p 【m 1 】、p 【2 】、p f 神】、p 【3 】进行匹配。 王大萌提出【2 0 】：按照模式串中的字母在自然英文中出现概率由低到高的顺 序进行匹配，在发生不匹配时，采用b a d c h a r 函数实现主串指针的向前跳跃，对 概率较低的字符进行优先匹配，这样可以尽可能的发现不匹配，减少比较次数， 从而尽可能早的利用b a d c h a r 函数来进行跳跃。 综上所述的各类改进算法，虽然在预处理阶段或是匹配阶段作出了改进，加 快了b m 算法的速度，提高了算法的性能，并且应用于s n o r t 等入侵检测系统中， 但是要适用于网络安全日志审计系统，还需要改进。 ( 3 ) b f ( b r u t ef o r c e ) 算法 b f 算法是模式匹配算法中最简单的算法，算法核心思想是：首先p 【l 】和t 【l 】 比较，若相等，则再比较p z l 和t 2 ，一直n p t m l 为止；若t q $ 8 p q 不等，则p 向右 移动一个字符的位置，再依次进行比较。如果t 时1 k + m 】= p 【l m 】，则匹配成功；否 则失败。 b f 算法的特点： 没有预处理阶段； 需要恒定不变的额外空间； 可以从任何位置开始进行比较； 该算法在最好情况下的时间复杂度为o ( n + m ) ，在最坏的情况下，要执 行( n m + 1 ) m 次字母的匹配，所以时间复杂度为o ( r i m ) 。 b f 算法的缺点是在主串中出现多个与模式串部分匹配的子串的情况下，主 串的指针需要经常回溯，显然算法的效率很低【2 l 】。 ( 4 ) k m p ( k n u t h m o r r i s p r a t t ) 算法【2 2 】 k m p 算法主要消除了主串指针的回溯，利用已经得到部分匹配结果将模式 串右滑尽可能远的一段距离再继续比较。 k m p 算法的特点： 匹配过程中主字符串指针不需要回溯； 查找时间计算复杂度为o ( n 协) ，计算n e x t ( j ) 的时间复杂度为o ( m ) ： 在查找阶段几乎执行2 n 1 倍的文本。 k m p 算法的优点是确保了线性，并且其扩展性适合求解更难的问题。由于 其主字符串不要回溯，在处理从外设输入大文件问题很有效，可以边读入边匹配。 2 1 3 多模式匹配算法及其相关改进算法的研究现状 多模式匹配算法一次可对文本串同时进行多个模式串匹配，也即根据建立在 一个有限的字符集上的模式串和文本串，找到文本串中与模式串完全相等的子串 的所有出现位置【2 3 】。目前主要的多模式匹配算法有a h o c o r a s i c k 2 4 1 、w u m a n b e r 2 5 】 等算法。 ( 1 ) a c ( a h o c o r a s i c k ) 算法 a c 算法是在预处理阶段利用模式集合建立转向函数g o t o 、失效函数f a i l u r e 和 输出函数o u t p u t ，并用它们构造一个树型有限自动机。其算法特点如下： 匹配过程也分为预处理阶段和查找阶段； 一预处理阶段的复杂性是o ( m ) ，查找的时间复杂度为o ( n ) ，a c 算法 总的时间复杂度是o ( m + n ) ，其中m 为所有模式串的长度总和。 a c 算法的缺点是对文本串进行搜索时没有跳跃，无法跳过没必要的比较， 因此在规则不是非常多的实际搜索过程中，a c 算法性能不佳。并且有限自动机 算法是以空间换时间，当模式集较大时可能产生空间膨胀问题。 ( 2 ) w m ( w u m a n b e r ) 算法 w u m a n b e r 快速字符串匹配算法采用了b m 算法进行跳跃的思想和h a s h 散列 的方法乜7 1 。 w u m a n b e r 算法首先对模式串集合进行预处理。预处理阶段将建立3 个表 格：s h i f t 表、h a s h 表、p r e f i x 表。 s h i f t 表中存储的是p a t t e r n 的安全移动距离，h a s h 表用来存储尾块字符散 列值相同的模式串，p r e f i x 表用来存储尾块字符散列值相同的模式串的首块字 符散列值。当s h i f t 表的值是0 的时候，h a s h 表和p i 汪f i x 表将被使用，以确定 可能被匹配的侯选p a t t e m ，并验证是否真正匹配。对文本与模式字符串进行匹配 的时候正是利用这三个表完成文本的扫描和匹配的判定。 下面首先来看预处理过程： 先计算所有p a t t e r n 中最短的长度，记为m ，并且只考虑每一个p a t t e m 的前m 个字符。在对匹配情况的考察中，我们一次考察的不是一个字符，而是由b 个字 符组成的一个字符串( 简称为块) ，根据块的匹配情况来决定p a r e m 的移动距离， b 的取值计算公式为：b = l o g c 2 m 。( m = k x m ，k 是模式的数目，c 表示文本集的 大小即c = i | 是字符集合) ，b 通常取2 或3 。 假设x 是我们现在正在处理的t e x t 中的某个块，通过h a s h 函数x 被散列成一个 整数值i ，这个索引值i 就是该块在s h i f t 表中的入口。s h i f t i q b 每一项的值决定 p a t t e r n 的安全移动距离。 】- 跗一b + k 蛾x ( 2 3 ) 沪i i i 】i n 川凰。】- 跗一十蛾x 2 3 以此将所有模式串中长度为b 的子串都映射至i j s h i f t 中，当比较文本串时， s h i f t i = 0 ，说明可能产生了匹配，此时查找h a s h 。h a s h i 是一个指针p ，指 向相同后缀的模式列表的起始地址。p 不停地累加，可以得到相同后缀的各个模 式串，直到p 等于h a s h i + io 同时p 指向了p r e f i x 表，它存放当前的模式串前 缀的长度为b7 字符的h a s h 值，它的存在可以有效减少