面向信息安全的高速数据流管理系统的设计与实现

1、第25卷第12期2008年12月计算机应用与软件Computer Applications and SoftwareV01.25No.12Dec.2008面向信息安全的高速数据流管理系统的设计与实现李冬1薛一波21(苏州经贸职业技术学院汀苏苏州2100092(清华大学信息技术研究院网络安全实验室北京100084摘要随着信息安全领域研究和应用的深入,网络行为和流量分析等应用对网络流的处理提出了更高的要求。从数据流管理系统的角度重新诠释了网络流分析,设计并实现了一个能够匹配千兆网络的高速数据流管理系统IS.DSMS(Data Stream ManagementSystem for Informat

2、ion Security。系统利用了采样技术、概要技术、滑动窗口等技术对常用的五类聚合查询进行了优化。实验证明,系统具备千兆网络条件下实际使用的性能,可作为网络数据流实时查询和统计分析引擎,为入侵检测、网络监控等系统提供高速有效的支持。关键词数据流管理系统聚合查询THE DESIGN AND IMPLEMENTATIoN oF INFoRMATIoN SECURITY-oR砸NTEDHIGH DATA STREAM MANAGEMENT SYSTEMLi Don91Xue Yib027(Swhou Institute ofCommerce and Trade,Suzhou210009,Jian

3、gsu,China2tNetwork.Security Lab,FlT,Tsinghua University。8ebi鸭100084,ChinaAbstract Network applications such as network behaviour and traffic analysis,etc.,have raised higher demands for handling the network stream along with the deepened research and application in information security fields.Stream

4、 analysis was re-characterized in terms of datastream management system,and the Data Stream Management System for Information Security(ISDSMSwhich could fit thegigabyte network was designed and implemented.The technologies of sample,synopsis and sliding windows were adopted to optimize five common a

5、ggregated queries in the system.The test experiments have proved that it has practical performance in gigabyte network condition and can be used as the realtime en西ne to query and make statistic of the network data flow.Meanwhile,it may provide a high and effective support to network invasion and ne

6、twork monitoring.Keywords Date stream management Aggregate query0引言互联网技术二十年来发展十分迅速,已经融入到人们的日常生活当中。随着基于网络的各类应用的发展和广泛应用,越设备和终端设备获得处理。其中典型的应用包括金融数据处理、股市交易数据处理、传感器网络数据处理、系统日志处理等。针对上述流数据,应用系统的要求往往是以查询为中心,即针对特定的查询计划,要求系统能够做到对流数据连续不问断地查询处理,甚至要求实时的连续查询。为了更好地解决这类数据的查询问题,数据流管理系统DSMS(Data Streams Management Sy

7、stem应运而生。这类系统提供给用户新的查询检索方式,并提供灵活的配置,既可以管理常规的关系型数据,又可以处理持续的数据流。数据流查询系统在很多方面已经发挥了越来越重要的作用。在信息安全应用中,数据流查询系统也得到了一定的应用。但网络宽带的快速发展给内部机制原本就复杂的数据流查询系统带来了性能上的挑战。本文的主要研究内容是设计并实现一个能够适用于千,I;网络环境的高速数据流查询系统IsDSMS。ISDSMS提供了对网络流数据类型高效、灵活的流查询统计分析功能,可以作为数据流实时查询和处理的引擎,为入侵检测和网络监控提供有效的支持;对于提高网络行为分析水平和事件监控效率具有重大意义。本文致力于将

8、数据流管理系统应用于网络安全系统中,国内外在这方面的研究刚刚起步。最早将数据流管理系统应用于网络安全系统中的应用是斯坦福大学的Shivnath Babu,2005年他的博士论文中,利用数据流管理系统中的查询计划替代入侵检测系统中的特征,从而将数据流管理系统作为引擎实现了一个入侵检测系统。1996年Bell实验室的Mark Sullivan提出的Tribeca流数据管理系统H应用在了网络监控方面,为面向数收稿开期:20080303。李冬,副教授,主研领域:计算机网络技术,分布式控制等。第12期李冬等:面向信息安全的高速数据流管理系统的设计与实现269据流的应用设计了查询语言和有限的查询操作。在此

9、之后,中科院计算所的谭建龙提出了类似Shivnath Babu想法“,并实现了相关系统。总的来说,将数据流管理系统应用于网络安全的尝试刚刚开始,目前国内外都处于试验阶段,还没有形成统一的认识。在数据流管理系统方面,国外许多大学和研究机构开展了大量的研究工作。国内对数据流管理的研究起步比较晚,且大部分是研究数据流挖掘,只有少数研究数据流管理系统。国外比较著名的流数据管理系统相关的研究工作包括:1992年的Tapestry系统"o,该系统首次提出连续查询的概念。系统设计的初衷是用于电子邮件和电子公告牌系统信息的过滤。Oregon Graduate Institute和Wisconsin大

10、学共同开发的NiagaraCQ系统”J支持连续查询,能支持监视整个广域网络上持久稳定的数据集。布朗大学的Aurora系统一1,它以一个触发器网络作为核心,主要用来处理流式监控。UC-Berkeley的TelegraphCQ系统【81列主要应用在传感器网络上,它由前端、共享存储区和后端共同组成,实际的查询处理在TelegraphCQ的后端进行。对数据流管理系统的研究从特定应用开始,逐渐过渡到通用方向,即设计能够适用于任何方向的通用数据流管理系统。这类系统主要的代表是斯坦福大学的STREAM。斯坦福大学的STREAM系统¨山。是一个基于关系的通用数据流管理原型系统。该系统设计了一种通用的

11、流查询语言CQL(Continuous Query Language,它以SQL语言为基础,增加了对流的操作和窗口控制,是SQL的超集。系统接受用户注册的查询并将其编译成为查询计划,保持运行直到查询失效。STREAM主要解决在内存有限的情况下,如何扩展查询语言、高效的执行查询以及如何进行近似查询等问题,具有良好的连续查询能力。本文设计的Is.DSMS系统,借鉴了STREAM的原型系统和文献14,15的思想。并对一些关键技术进行了相应的改进,目的是使系统的整体性能适用于干兆网络环境中。2IS-DSMS设计2.1设计目的IS.DSMS设计的目的是为千兆网络提供一个实用的数据流管理系统引擎。该系统主

12、要分成三个部分:流数据XML输入接口、数据流查询核心和查询注册客户端。流数据输入接口是一个可配置的对外接口,采用XML语法设计,可以与其他的网络安全系统中关键层次对接,实现嵌入其他系统的目的;数据流查询核心是数据流管理系统的核心部分,主要负责对流数据进行处理,它的结构决定了整个系统的性能;查询注册客户端是IsDSMS的管理界面,它为用户提供了管理整个系统的接口,并获得查询和处理结果的输出。其系统结构如图1所示。|r=j圈一一H圆|斟ll l l i图下豳l图1IS.DSMS系统结构圈在ISDSMS流数据输入接口中,用户可以定制XML语法将IS.DSMS融入到应用系统中。例如在人侵检测系统中,X

13、ML定义的接口可以使ISDSMS接入包分类模块之后、或者流重组模块之后,甚至特征匹配模块之后。而原系统需要的改造是将数据打包成XML格式,形成ISDSMS能够接受的元组形式。用户的另外一部分工作是在ISDSMS的查询注册客户端中完成的。这部分工作主要包括数据流选择、查询注册、查询控制和分析输出结果等。此外,系统运行的一些参数需要通过该客户端中注册。ISDSMS的数据流查询核心在接到客户端注册的查询及分析开始命令之后,开始监视从流数据输入接口中流入的XML形式的元组。对到来的元组,该部分进行处理,并将结果输出到客户端。ISDSMS流查询子系统还可以生成概要。2.2流查询处理机制IS-DSMS是基

14、于STREAM系统实现的,为此,其查询注册通过关系型描述查询语言CQL1实现。IS.DSMS的数据流查询核心中的PRE(PaRser Element模块对用户注册的CQL语句查询进行解析,经过一系列的中间语言转换。输出可实际运行的查询计划,该查询计划中包含各种优化策略,可以指导执行模块优化的执行查询操作。PRE模块的工作流程如图2所示。查询经过四个阶段变成可知道执行模块执行的计划,分别是:语法解析部分、语义解析部分、逻辑计划生成和物理计划生成。语法解析部分的主要工作是将输入的查询CQL语句转换成语法树,利用语法树为语义分析作准备。语义解析部分主要是将语法树转换成内部查询表示。内部查询表示是一种

15、粗粒度的查询表示。逻辑计划生成部分主要将查询转换成内部可执行的计划。在这一层次,逻辑计划的基本操作类似关系运算符,是CQL相关的,它与执行查询时的实际操作无关,仅仅是用来作性能提升和变换的一个中间环节表示,是一种功能上的体现。通过这个层次的解析,查询计划变成了逻辑上可执行的操作a图2PRE模块工作流程物理计划的基础是基本的物理操作,即可执行的数据结构,它分别对应IS-DSMS中执行模块的各个功能。该计划统筹各功能,形成一个统一的整体,实现查询功能。这个过程类似于软件的编译器,优化步骤贯穿始终。在逻辑计划层,多查询之间的冗余操作可以被优化去掉。在物理层次,可共用的执行模块也被共用。经过上述过程,

16、查询计划可以被隐式的合并优化,存储空间可以共享。可执行的物理查询计划生成后,查询需要的各类实际资源的数量和顺序都被确定,如存储空间数量、队列数量、队列摆放、算术和逻辑操作数量和位置等。IS.DSMS数据流查询核心中的执行模块负责按照查询计划,依次实现各个实际功能单元。在模块中存在一个全局的调度器,它使用Round Robin策略来调度这些单元,每个单元被分配特定的时间片实现并发执行。经过分析,我们认为,提高数据流查询系统查询性能的关键是提高其中的积累基本操作的实现。主要是五类聚合查询COUNT、270计算机应用与软件2008益SUM、MAX、MIN和AVG。我们可以对其中的数据结构进行简化并增

17、加并行处理的能力,同时采用采样等技术使五类聚合查询的执行速度得到明显的提升。IS-DSMS的这类优化对于该系统在信息安全中的应用极具意义。概要技术主要对整个网络数据流的内容做精简版本的保存,既可以形成历史数据便于后期的统计和分析,也可以作为近似查询的一个方法,在对精确性要求不高时可以直接在概要上执行查询。IS.DSMS中的概要是用户可控的。流查询子系统中的概要模块负责解析用户注册的生成概要的请求,并采用合适的算法来实现。目前IS.DSMS支持的计算数据流概要的算法包括采样、直方图和小波。其中采样技术采用精简采样算法和计数采样算法两种算法,它们都很适合于解决频度查询问题(即top.k问题。直方图

18、采用的等深直方图算法。小波采用的是最简单的一维Haar小波算法。在IS-DSMS中具体使用哪种概要技术,可以通过概要模块选取,也可以由用户在注册概要时指定。2.3高速流查询技术在使用窗口之前,首先要确定窗口边界即确定窗口的大小。根据窗口边界的确定方式,我们把窗口分为快照窗口、路标窗口和滑动窗口三种。快照窗口(Snapshot两个边界都是固定的,这样窗口大小就是固定的,常见于对确定的某个时间段内的数据进行查询;路标窗口(1andmark的开始边界是固定的,结束边界向前移动,随着数据的不断到达,窗口不断变大,常见于对某个时间点之后的所有数据进行查询;滑动窗口(Sliding Win.dowt9j的

19、开始和结束边界同时动态向前移动,窗口大小固定。滑动窗口技术大小固定的特性符合内存有限的要求,强调最新数据的特性符合大多数应用的要求,因而成为目前使用最普遍的窗口技术。ISDSMS对于这三种窗口机制均有很好的支持,用户可以根据自己的资源状况手动配置窗口的大小,默认大小是10万个元组。当突发流量超过系统的处理能力,如果不采取相应的措施,会导致整个系统的吞吐量和响应时间极度恶化。负载脱落(Load Shedding通过丢弃一定数量的数据,在牺牲部分准确性和完整性的条件下,保证系统的性能。我们设计了一个随机采样的算子来具体实现基于语义的负载脱落¨o】。目前我们采用的采样算法是基于Hoeffd

20、ing不等式的概率采样算法。该算法描述如下:对于查询Q。,累计的平均值和标准方差是胁和吼,窗口大小是.。给定阈值占。;和超过它的变化量占,计算采样概率P。使用公式(1。ISDSMS中的负载脱落在突发流量超过某个配置文件中指定阈值的时候自动启用。1届了赢了_2i刁面109了【1经过我们的分析发现,系统结果的输出对整个系统性能的影响十分严重。这是由于数据流管理系统内部的数据也是以流的方式传输体现。任何一个环节性能的下降会导致整体性能的变化。由于IS-DSMS将输出反馈到客户端,而客户端通过文件记录方式记录结果,导致性能下降。很显然,对于10万元组/秒的数据流,后果就是系统会把每秒上万条查询记录写入

21、本地文件。事实上,并不是所有查询都要求结果以数据流的形式输出。这种情形下过于密集的数据输出只会增加系统的负荷,降低系统性能。因此,在执行这些操作的时候,我们可以适当地减少写文件的次数,这样既不影响查询结果的精确性,又可以提高系统的性能。ISDSMS所采用自可输出控制方式默认是在执行五类聚合查询时,每输出一万条记录写入文件一条,并保证第一条和最后一条一定会被输出。此外,用户可以根据自己的需求配置写入的密集程度,还可以利用元组里的时间戳信息来控制记录的输出。3实验和性能测试由于五类聚合查询在各种系统中广泛使用,且ISDSMS极大地优化了聚合查询的执行,我们设计如下测试方案来检验Is. DSMS处理

22、五类聚合查询的性能。图3测试环境我们使用K次最多的方法(实验中K=10,对主要由五类聚合查询组成的共计六组查询进行了测试。其中Testl和Test2主要是对单个统计值维护的测试,Test3和Test4主要是对统计值表达式的测试,Test5和Test6主要是对多统计查询的性能测试,包含了数十个查询。为了保证公平,在测试中IS.DSMS关闭了负载脱落和生成摘要的功能。ISDSMS和STREAM的对比实验结果如图4所示,速率单位为万条元组/秒。图41SDSMS和STREAM性能对比测试4结论本文从数据流管理系统的角度重新诠释了网络流分析,设计并实现了一个能够匹配千兆网络的高速数据流管理系统(IS。D

23、SMS。该系统利用了采样技术、概要技术、滑动窗口等技术对网络应用中常用的五类聚合查询进行了优化。实验证明,该系统具备千兆网络条件下实际使用的性能,处理聚合查询的性能可以达到STREAM系统的10一20倍。可作为网络数据流实时查询和统计分析引擎,为入侵检测、网络监控等信息安全方面的应用提供高速、有效的支持。 (下转第277页第12期杜青:基于混沌的双像素灰度差分脆弱数字水印算法277图4是输入错误密钥key后得到的篡改检测结果,由图4可以看出,输入错误密钥后不能对嵌入认证水印后的图像进行检测,说明算法具有一定的安全性。图4输入错误密钥后的检测结果本文提出了一种基于混沌的双像素灰度差分脆弱数字水印

24、算法,该算法能对图像的真实性进行检测,具有较好的不可见性以及篡改检测和篡改定位能力。参考文献1吴金海,林福宗.基于数字水印的图像认证技术J.计算机学报,2004(9:11531160.2朱从旭,陈志刚.一种灵敏的文本图像认证混沌脆弱水印技术J.小型微型计算机系统,2006(1:151154.3李长河,张永强,王君.一种新颖的图像自适应信息隐藏算法J.计算机应用,2005(5:1138一1140.4Xue Xiaohui,Wu Xiaolin.Directly operable image representation ofmuhisealeprimalsketchJ.IEEE Transati

25、ons on Multimedia,2005,7(5:805816.(上接第270页参考文献1Shivnath Babu.Adaptive Query Processing in Data Stream Management2谭建龙,沈星星,王映.基于关系数据流模型的网络入侵检测系统.信息技术快报.2005.3Terry D,Goldberg D.Nichols D,et a1.Continuous queries over append4Sullivan M.Tribeca:A stream database nlanager for network traffic analy-sis.In

26、 Proc.of the1_9916Intl.Cont".on Very Large Data Bases.1996:594.5Chen J,DeWitt D J,Tian F,et a1.NiagraCQ:A scalable continuousquery system for internet databases.In Proc.of the6Arasu A,Babcock B,Babu s,et a1.STREAM:The Stanford Stream Da-7Abadi D,Carney D,Cetintemel U,et a1.Aurora:A Data Stream

27、Management System(demo description.In Proceedings of the2003ACM SIGMOD Conference on Management of Data,San Diego,CA,2003. 8Chandrasekaran S,Cooper O。Deshpande A,et a1.TelegraphCQ:Con9】Amsu A,Babu S,Widom J.The CQL Continuous Query Language:Semantic Foundations and Query Execution,Stanford Universit

28、y,2003. 1OArasu A.Manku G.Approximate Counts and Quantiles over Sliding Windows.The Proc.of PODS2004,June2004.11Babcock B,Datar M.Load Shedding Techniques for Data Stream Systerns.Management and Processing of Data Streams,San Diego,Califor-nia,USA,2003,6.Babu S.Widom J.StreaMon:A Adaptive Engine for

29、 Stream Query Processing,Paris,France,SIGMOD2004:1318.Sailesh Krishnamurthy,Sirish Chandrasekaran,Owen Cooper,et a1.7FelegraphCQ:An Architectural Status ReportJ.In Proceedings of IEEE Conference on Data Engineering,2003,26(1:1118.Arasu A,Babcock B。Babu S。et a1.Characterizing Memory Require-ments for

30、 Queries over Continuous Data StreamsJ.ACM Transactions on Database Systems,2004,29(I:162194.(上接第274页ACM Workshop on Multimedia and Security2002,Juan-lesPins。France,December6.10Kharrazi M,Senear H T,Memon N.Benchmarking Steganographic andSteganalyticTechniques.to appear in E.Delp et a1.(eds.:Proc.SP

31、IEElectronic IlllagiIlg,Security,Steganogsaphy,and Watermarking of Multimedia Contents VII,2005.11Farid H.Siwei L Detecting Hidden Messages Using HighdrOrder Sta-Science,SpringerVedag New York,2002.2578:340354.12Tzschoppe R,Bauml R,Huber J,Kaup A.Stegsnographic System Basedon Hi【sherOrder Statistics

32、.in E.Delp et a1.(eds.:Proc.SPIE Electmnic lm画ng,Security,Steganography,and Watermarking of Muhimedia Contents V,2003,5020:156一166.13Harmsen J J,Pearlman W A.Steganalysis of Additive Noise ModelablelnformationHiding.in E.Delp at a1.(eds.:Proc.SPIE Electronic lma舀ng,Security,Steganography,and Watermarking of Multimedia Contents V,2003:131142.14Celik M,Sharma G,Tekalp A.Universal Image Stegunalysis UsingRateDi