基于关系数据流模型的网络入侵检测系统

-.z基于关系数据流模型的网络入侵检测系统摘要：数据流管理系统〔datastreammanagementsystemDSMS〕是处理动态数据集合的一种数据管理技术，采用数据流模型对网络入侵检测系统(NetworkIntrusionDetectionSystem-NIDS)进展设计，可以利用数据流中多持续查询优化的技术，提高网络入侵检测系统的性能。同时使用关系数据流模型可以让入侵检测系统构造更加清晰，扩展性更好。文章描述网络数据的关系构造化，入侵检测特征的关系查询表示以及过滤型多持续查询优化技术。这个系统可以认为是数据流管理系统的一个应用系统，表达了一些数据流管理的概念和核心技术，对设计和实现通用的数据流管理系统具有一定借鉴意义。本文将重点围绕数据流查询〔continuequery〕的编译优化、数据流管理技术和网络平安应用的关系进展分析。数据流管理系统的功能数据流管理技术是处理相对固定不变的大量查询和源源不断的流动数据的技术。而网络信息平安是解决对网络信息的分发、通讯、管理的问题。由于网络信息是典型的源源不断的数据流，同时有很多网络信息平安应用系统是采用大量查询方式，对这些网络数据流进展处理。所以网络信息平安是数据流管理研究的一个很好的典型应用。这个平安应用必须不连续无延迟地处理在线、持续的高速网络数据流，且网络数据不可能全都保存在外部存储器中。我们的研究就是基于持续查询概念，采用数据流管理系统作为流数据处理平台，将其应用到网络平安监控系统中去。我们实现了一个基于数据流处理模型的网络平安事件监控系统IceNetwork。在这个系统中，数据流管理平台通过优化执行注册于系统中的大量持续查询，对连续网络流进展过滤等操作，完成各种平安事件的监测与报警，从而有效地支持了监控系统的实时性，准确性与灵活性要求。本文以建立一个网络入侵检测技术系统为案例，采用基于数据流管理技术的思想，来开展数据流核心技术的研究。希望能把工程中的核心问题，转换为数据流管理研究领域的通用问题。数据流管理系统的功能数据流管理系统[1]是为流动数据管理建立的统一平台。在数据库管理中，数据是相对静态的，查询是动态的；而在数据流管理中，查询是相对静态的，数据是动态的。也就是说数据库技术主要研究对数据在外存〔磁盘〕上的存储索引和一次查询的执行技术，而数据流管理技术主要研究数据在内存中的存储索引和多个执行查询〔continuequery〕[2]的执行技术。数据库管理的一个核心问题是为了高效的查询，如何建立数据对象的索引，而数据流管理技术的核心问题是如何管理这些检索条件和操纵程序，研究如何为实现高效的大量查询进展编译的技术。网络入侵检测系统为了防*计算机被入侵，入侵检测系统应运而生。所谓入侵检测，就是通过从计算机网络或计算机系统中的假设干关键点收集信息并对其进展分析，发现网络或系统中是否有违反平安策略的行为和遭到袭击的迹象，并对此做出适当反响的过程。根据入侵检测系统部署的位置以及网络数据的来源，入侵检测系统可以分为两类：主机入侵检测系统(HIDSHostIntrusionDetectionSystemHostIntrusionDetectionSystem通常利用一个工作在混杂模式下的网卡来实时监视并分析通过网络的数据流。其分析模块通常使用模式匹配、统计分析等技术来识别攻击行为。一旦检测到了攻击行为，NIDS的响应模块就作出适当的响应，比方报警、切断相关用户的网络连接等。由于NIDS采用在关键节点集中监测的方式，能够监控整个子网，并且对于子网内单个主机来说是透明的，因此部署起来比HIDS方便得多。随着越来越多的单位和企业采用以太网的局域网组网方式，NIDS得到了广泛的应用。NIDS的主要检测手段是模式匹配，这里说的“模式〞是指，网络数据包的头部信息或者载荷中的数据满足的特定条件，网络平安领域把能够判定一个入侵的一组特征条件叫做“特征(Signature)〞。Snort[3]是一个成熟的、被广泛使用的、开放源代码网络入侵检测系统，它的有效性已经得到时间的验证。它具有一个可配置的特征库(因为它的每一个特征对应于一条规则，我们也把它的特征库称为规则库)，最新版本的Snort规则库包含了约2300条常见网络入侵的检测规则。图1为Snort2.0中检测引擎的工作流程图。图1snort2.0包数据和特征(处理图)典型情况是包通过且仅通过多特征过滤引擎一次，所以设计高效的多特征过滤引擎是入侵检测系统的核心问题之一。对于一个在监控整个子网的入侵检测系统来说，网络数据捕获，TCP组包、应用协议分析、特征设计方、多特征过滤引擎是决定效率的主要方面，也是研究的重点内容。关系数据数据流模型的网络入侵检测系统一个采用数据流管理系统作为处理引擎的NIDS的构造如图2所示。查询提交查询提交捕包前端网络数据入侵检测引擎DSMS引擎检测结果处理模块检测条件图2基于DSMS的NIDS构造图其中捕包前端负责将以太网数据帧捕获，并转换为预定义的构造化数据，提交给入侵检测引擎。入侵检测引擎的核心是DSMS引擎，其中预先注册了大量以数据流查询语言表示的入侵检测条件。当格式化的描述网络数据包的关系元组到达时，计算注册查询。检测结果被传给检测结果处理模块，以对入侵进展报警等后续处理。网络入侵检测系统和数据流管理技术的关系如果我们把网络入侵检测系统看作数据流管理系统的一个应用，数据流管理系统为入侵检测系统提供一个根底的平台，则数据流管理平台就需要为入侵检测系统提供一些核心技术的支持。下表说明网络入侵检测系统和数据流管理技术的关系。从对照比中我们可以看出入侵检测系统需要使用到大量的数据流管理的核心技术。把数据流管理研究的技术应用到入侵检测系统中，将为入侵检测系统提供良好的性能和扩展性。网络入侵检测系统数据流管理系统联系应用系统根底平台网络入侵检测系统是基于数据流管理系统的应用系统。网络数据捕获：将网络的数据保存到内存中。难点主要是如何在内存中存储大量的数据，同时及时将处理后的数据丢弃。内存数据存储：解决海量关系数据的存储问题。主要是处理数据滑动出处理窗口后，如何高效地丢弃掉。由于数据流管理系统只能处理关系化的数据，所以如何把网络数据包变化为关系数据，将是这局部需要完成的工作。TCP组包：将网络上的单个IP包，拼装为一个完整的TCP流。主要解决IP后序包先到，和存在碎片包的问题。要保证应用层可以看到连续的网络数据流。内存数据索引：解决在内存数据中，如何通过键(key)找到数据记录的问题和如何对数据建立键索引(inde*)的问题核心问题是如何通过IP包的地址信息找到以前的数据包。也就是对已经存在的数据包按IP地址对建立好索引，将来新数据包到来的时候，通过这个索引找到对应的TCP流。应用协议分析：协议分析包括协议解码、协议状态识别、协议内容分析等工作多流连接：如果多个数据流存在一定的关系，需要将这多个数据流窗口内的表进展多表连接计算，形成一个表关系后再进展持续查询的过滤。核心问题是协议分析可能需要关注其他流的信息，例如ftp命令流的结果，可能对当前文件传输流的分析是有用的。所以需要连接这两个流，才能进展判断和计算。特征设计方案：特征设计的时候需要考虑特征对入侵描述的简洁性和高效实现扩展的可能性。使用关系查询语句来定义查询的条件和过滤的操作。每个网络入侵检测产品使用单独的入侵特征，不利用入侵检测系统之间的信息交流。多特征过滤引擎：多特征过滤引擎一般包括协议域搜索、一般内容搜索、**异常检测。单流多持续查询执行引擎：对关系数据流中的字段属性，一般分为字符串字段、整数字段、实数字段、时间日期等字段。针对不同的字段类型，可以设计不同的多持续查询优化策略。同时各个字段间的判断次序也是一个需要考虑的问题。入侵检测系统中，IP地址可以看作整数字段；包内容可以看做字符串字段；IP头的字段一般是整数字段。所以入侵检测系统中需要设计的是整数字段和字符串字段的单流多持续查询优化。从上表可以看出，基于关系数据流模型的入侵检测系统，需要解决网络数据关系化存储〔网络数据捕获〕、整数字段索引〔TCP组包〕、特征设计方案、整数字段持续查询编译、字符串字段持续查询编译〔多特征过滤引擎〕等问题。还应包括多流连接查询、字段判断次序、实数字段的持续查询编译等问题。网络数据关系化我们利用改进的轻量级捕包程序winpcap进展捕包，对于每一个IP包，首先对载荷局部进展统一的关键词扫描。如果没有命中的关键词则将其抛弃；否则，将其拼到相应的TCP流，提取包内各个字段信息，分别生成两个流：TCPLink与Packet。TCPLink包括一个连接的四元组信息，表示了一个包所属的TCP连接，两个流格式如下：TCPLinkTCPLinkIDPRIMARYKEYSourceIPDestIP,SourcePortDestPort…..PacketIDPRIMARYKEYTcpIDForeignKEYFragOffset;//IP头信息TTL,Buffvarchar(64,000)….其中，TCPLink是主流，每一个元组对应一个连接；Packet是辅流，记录主流中每个元组对应的每一个包的各个字段的具体值。主流与辅流之间是一对多的关系。通过对网络包的预处理，形成两条流，完成了网络数据的关系化，从而可以在其上进展关系操作。入侵检测特征的关系查询表示数据流管理系统只承受SQL语句表示的查询，因此我们必须将Snort的特征转换为SQL表示，这需要解析Snort规则。我们实现了一个规则转换程序RulesParser，读入标准snort规则，生成数据流管理系统NIDS的SQL查询。一条典型的Snort规则如下：alerttcpanyany->any6666:7000(msg:"E*PLOITCHATIRCEttercapparseoverflowattempt";flow:to_server,established;content:"PRIVMSG";nocase;content:"nickserv";nocase;content:"IDENTIFY";nocase;isdataat:100,relative;pcre:"/^PRIVMSG\s+nickserv\s+IDENTIFY\s[^\n]{100}/smi";reference:url,./dev/GOBBLES-12.t*t;classtype:misc-attack;sid:1382;rev:9;)这条规则表达的含义是：一个TCP数据报，无论来自哪个IP地址的哪个端口，只要是6666:7000端口，并且含有二进制串〞PRIVMSG〞，“nickserv〞，“IDENTIFY〞等则触发报警，报警信息为〞E*PLOITCHATIRCEttercapparseoverflowattempt〞。转换成关系数据上的查询SELECT*FROMpacketWHEREpacket.ip_proto=6AND(packet.DestinationPort>=6666ANDpacket.DestinationPort<=7000)AND(packet.flowflag&18)=18ANDpacket.ruleid=110ANDsubstr(content,〞PRIVMSG〞)AND substr(content,〞nickserv〞)ANDsubstr(content,〞IDENTIFY〞)ANDbytetest(content,100)过滤型多持续查询优化网络入侵检测系统所注册的持续查询根本上均为过滤型查询〔Filter〕，即对由网络包生成的关系表中*些字段的选择操作。这些字段类型包括字符型、整型等。我们分别针对不同字段类型设计过滤型多持续查询优化算法。字符字段的多串匹配优化字符串匹配是包的规则检测中最耗时的一个操作，很大程度上决定了检测引擎的性能。snort2.0中采用改进的Wu-Manber[4]和Aho－Corasick[4]多串匹配算法，比以前的算法性能有了大幅提高。在我们的系统中，采用了一种新的高效多串匹配算法SBOM[6]，试验说明，这种算法同样能取得较高的性能。整数字段的模式匹配优化 Snort规则中，除了content选项是对网络包载荷局部进展关键词模式匹配，还有相当数量的**协议字段的数值匹配。如源、目的端口、ttl值等。一种直观而简单的处理方式是对每一个到来的数据包，先顺次执行一条规则中各个字段的数值比较，再顺次执行多条规则。这种处理方式有几个弊端：时间复杂度是O(n)，n为总规则数目，即比较次数与规则条数成正比。处理时间随着规则数目的增加而线性增长。当前的snort包含2300多条规则，其中不含content字段的包异常检测有相当数量。日益增多的网络攻击使得规则数目仍在增长。如此大量的规则数导致的匹配引擎性能下降已经是一个不得不考虑的问题。针对各个属性域上的判断，规则与规则之间存在冗余。考虑下面两条规则片断：Rule1:SourcePort=200;DestPort=23;ttl=3;…Rule2:80<=SourcePort<6000;DestPort!=8080;ttl=5;…Rule3:SourcePort=80;DestPort=23;ttl=3;…假设*个包的SourcePort字段为60，如果第一条规则不满足必然不满足第二条规则，因此不用再进展第二次比较。可见顺次执行各条规则的判断导致产生多余的比较。所以，针对上述两个弊端，我们提出新的数值型模式匹配算法，充分利用大量注册查询能够事先知道的优势，将其进展预编译，形成有效的内部数据构造〔一个DFADeterministicfiniteautomaton，或者说是一棵匹配树〕，使得匹配时间不由规则数目线性决定，并减少不必要的比较，从而缓解规则数目大，网络流速高，导致检测引擎效率降低的困难。Deterministicfiniteautomaton问题形式化给定一个关系，关系是一个属性的〔attribute〕集合：a1,a2…an.每一个这个关系上的元组都由各个属性域上的值组成。每一个属性有它特定的值域*围aj∈Dj.每一个规则是一系列谓词的合取*式，每一个谓词对应于一个属性的判断。i{1,2m}:Ri=其中，Pij有如下形式Pij:DjBoolean如果*个规则中对于*个属性域没有限制，则认为这条规则对于这个属性域的取值限制是此属性域上的所有值。首先任意确定一个属性顺序a1,a2…an，则每一个元组就成为此顺序的属性值域上的序列，且序列的长度是n。每条规则都可以转化成一个顺次对每个属性值判断的谓词的合取*式，可以看成一个非确定有限自动机〔NFSA〕。我们对每一条规则都进展形式化规*，这样使其准确地由n个条件序列组成。其中的第i个条件就是作用于第i个属性域上的谓词。如果对第i个属性域没有限制，则认为它可以取所在值域上的所有值，在自动机中以TRUE代替。从而，每条规则都转化为一条匹配路径，如图4。同样的处理方法，对于每一条规则都进展规*化，都成为n个比较步骤。将所有的规则首尾并列连接起来，就形成一个对应于所有规则的非确定自动机。如果将其转化为一个确定性自动机，则对于每一个元组，走一遍自动机，顺次对每一个属性域上的值进展比较，走完n步之后，可以找出这条属性满足的所有规则。这种算法的关键是将这个NSFA转化为DSFA。传统的字符串匹配中的自动机转化方法不能直接应用到此情况中。首先，每个属性的值域是不确定的，而且可能不是有限域，如值域为整个整数域。而字符串匹配中自动机的值域就是26个字母，是确定的有限的。另外，不同属性的值域可能不同，不像字符串自动机中，每一步匹配的值域都是字母集合域。所以，针对规则匹配的自动机转化，需要解决的问题是对于每个不同的属性，如何确定每个属性域上的值域，以及如何将原始值转化为新的属性域上的新值。当前我们仅考虑所有字段都是整数域的情况〔对于非整数域数值，我们经过预转换将其映射到整数域〕。对于整数域上所有值不可穷尽枚举的问题，我们通过生成新字母表的方法解决。下面讲述具体算法。P1P2TRUEPn 图3匹配路径算法概述生成新值域对应于*一个属性，通过下面所述的转换方式，根据所有规则在此属性上的取值，为此属性域构造新的值域。这个值域是一个整数集合，它的势是有限的。这样我们就为每一个属性分别构造了类似于字符集合的有限的属性域，从而可以运用自动机思想来进展匹配。设有m条规则，对应于*个属性i的值域构造方法如下：对于整数域上的每一个取值*围，都可以统一用左关右开的值域来表示。设置最大值Ma*Num与最小值MinNum，这个值取得足够大〔小〕从而所有元组的真实取值都不会超过这个*围。如对于端口号，设置MinNum=0,Ma*Num=65535。则对于a1=m，可以表示为a1∈[m,m+1〕；对于a1<m,可以表示为a1∈[MinNum,m〕；对于a1>m，可以表示为a1∈[m+1,Ma*Num〕；对于n<a1<m，可以表示为a1∈[n+1,m〕；类似的，可以这种统一的方式表示出a1在整数域上的所有*围。读入所有规则中相应属性上的所有取值。设有m+1个不同的取值，这样，整个整数轴在最大值与最小值*围内分成m段。如图4所示。如果为每一个划分出的值分别赋予新的字母，则产生了一个有有限个数的值域。每一个取值必然落在数轴上的*一段内，从而属于*一个字母。对于每一个数，我们都可以通过二分查找，在Ο(log(m))的时间内得出这个数在新值域下的取值。将每一条规则在新值域下进展转换，则所有规则就转换为新值域下的表示了。考虑到规则中有Any的情况，也就是对此属性域上的值不作限制，则将其表示为新值域上所有值的集合。MMinnumn1n3n2Ma*numabcd图4分段整数轴，构造新的值域生成自动机假定有n个属性域，共有m条规则。则自动机树是一个n层的树，每一层代表对一个属性值的判断。树的每一个节点是一个向量。向量的每一个元组是一个构造，包含指向下一个树节点〔ne*tnode〕的指针以及当前树节点所匹配的规则集合〔ruleset〕。非叶子节点的Ruleset均为空，因为此时没有匹配成功的规则。如果*个节点的ne*tnode域为空指针，则表示由当前规则集在这一层所表示的属性上的相应值有匹配状态，指针指向下一个状态节点。而如果*个节点的ne*tnode域为空指针，说明匹配树到此状态为止已经停顿，没有进一步的状态。向量的大小对应于此节点包含的规则集在所属属性域上划分出的新值域的个数。向量的下标值对应于新值域上的相应取值。向量在每一个下标下的值是一个指向节点的指针，表示当前状态节点在对应取值下的状态转换。 图5规则树构造图上图为由Rule1,Rule2,Rule3生成的匹配树自动机。匹配树自动机从左至右共三层，每层对应一个属性字段的匹配，在这里为SourcePort、DestPort、ttl。每个节点对应一个临时规则集，表示匹配到这个节点时剩余可能最终匹配成功的所有规则。根节点对应的规则集为原始规则集，包括全部规则数。每个节点根据对应的临时规则集在相应属性上的划分，生成当前节点的新值域。接着根据当前规则集的各条规则分别生成各个新值域上的后继状态节点。叶子节点的规则集指针指向全部属性匹配完毕后最终匹配的规则集合。如上所示，全部规则经过预处理，整体编译成一棵自动机匹配树的内部表示形式，从而支持高效的多查询执行。运行自动机对于每一个到来的元组，判断哪些规则满足的过程就是将元组的各个属性上的值在生成于内存中的自动机上跑一遍的过程。由根节点开场，按自动机属性顺序进展每一层的匹配。如果在中间的*一层，下一节点指针为空，说明没有匹配规则。如果匹配到最后一层，则相应规则集代表此元组所触发的所有规则集。复杂度分析时间复杂度：设|Q|=m,表示规则个数；|T|=n，表示规则的属性共有n个。{Qj(Ti)=true}Qj(Ti)表示对第j条规则的第i个属性域字段进展匹配的布尔函数。则一条查询规则j的执行，表现为对待匹配数据的相应字段i执行匹配布尔函数{Qj(Ti)=true}，并将所有结果相与，取合取值。普通查询算法中最差算法复杂度O〔规则个数m字段个数n〕。平均最优判断复杂度O〔规则个数mp〕P为一个小于1的概率，由规则的分布与待匹配元组的分布决定。多持续查询优化算法中速度和配置检测规则个数m无关。对于匹配成功的元组，匹配时间是确定的，为∑log〔pi)。pi为属性i的新值域上的势。匹配过程中，需要将原始值转化为新值域上的值，通过二分查找，可以在log〔pi)的时间内完成。对于匹配不成功的元组，匹配过程会在自动机的*一层打住，则可定义平均匹配复杂度为O(t)=O(∑(j×(1－∏kt))其中，kt为自动机中第t层的过滤度，即均匀分布的元组值，经过第t层的过滤后，剩下的元组数目占总数目的百分比。空间复杂度对于普通查询算法，所有查询只需在内存中存储一次，而顺次执行导致比较次数有冗余。优化查询算法存在规则的重复存储，而比较次数却大大减少，相当于是用空间换时间。优化算法在自动机转化过程中，存在状态数目指数增长的问题。为了防止空间复杂度过大，我们可以采取将规则分组，分别生成多棵匹配树，从而使每棵树的大小可控；还可以让一样状态共用指针，而不是以在内存中再存储一个拷贝的方式，来解决空间复杂度过大的问题。优化算法的改进一旦规则集给定，属性顺序给定，生成的匹配自动机就是确定的。到来的元组跑一遍自动机，或者在中间的*层打住，表示没有任何规则匹配，或者在最末一层停顿，相应的规则集表示匹配规则。元组所匹配的步数代表了自动机的效率。匹配步数由到来的元组的分布情况以及匹配自动机的形状共同决定。假设到来的元组是均匀分布的，不考虑由元组分布造成的对匹配效率的影响，则匹配自动机的形状就是决定效率的因素了。我们希望找到效率最高，即平均匹配步数最少的自动机生成方法。已有研究显示，到达全局最优是NPhard〔多项式时间难解〕的问题[7]。我们只能通过一些启发式方法，进展局部优化，改进效率。我们从以下两个方面考虑：属性选择度为了到来元组在匹配过程中能尽早打住，从而减少平均总比较次数，应该将过滤度〔Ki〕高的属性排在自动机的前部。过滤度的度量没有一个确定的算法，我们提出以下几种可行的度量方法。值域*围百分比。Ki＝1－〔∑dij/di〕/m，dij表示第j条规则中属性i在新值域上的定义*围，m表示规则总数目。di表示属性i的新值域*围。1－〔∑dij/di〕/m的值越大，表示经过过滤后可能被排除的*围越大，即过滤度越高。这里通过值域*围反映过滤度大小。信息熵。我们借鉴优化决策树生成理论，引入机器学习中的聚类〔clustering〕算法。算法从一个分类的有不同属性的数据集合中生成决策树。生成过程利用信息增益〔informationgain〕的概念。数据的*个属性的信息增益是将一个数据集划分后熵〔混乱，无序〕的减少量。划分后数据集的熵的度量是将每一个划分集大小相对于原始数据集大小的比例作为权重累加。一个规则集合S的熵E通过如下公式计算Es=∑-1/nlog2(1/n)=log2(n)则一个规则集S在属性A上的信息增益通过如下公式计算G(s,f)=Es-∑|Sv|/|S|*Esv=log2(|S|)-∑|Sv|/|S|*log2(|Sv|)Sv代表对于规则集S,在属性A上划分之后生成的各个规则集合。|Sv|，|S|代表集合的数目。我们对原始规则集以及划分后生成的多个规则集，计算各个属性上的信息增益,选择大的作为先匹配的属性。这里通过信息增益来反映过滤度，实际上是认为，划分后分布越均匀的属性有更大的区分度。经历判断在实际的网络平安监控系统中，利用经历来判定区分度与优先顺序是可行的。在包过滤步骤中，源、目的端口有较强的区分度，对这个属性的过滤能较均匀地将规则集分类，应该放在前面匹配。而ttl值这个属性的区分度相对较弱，应该放在靠后的位置。我们可以根据经历将各个属性区分度排序，从而确定一个较优的匹配顺序。规则集分类将规则集预分类，一样类型的规则作为一个初始规则集。如TCP规则集，UDPUserDatagramProtocol〔用户数据报协议〕UserDatagramProtocol〔用户数据报协议〕InternetControlMessageProtocol〔Internet控制信息协议〕性能测试为检验IceNetwork处理引擎的功能与性能，我们设计如下测试方案测试环境：千兆交换机器千兆交换机器网络发包机：AMDOpterontm1421。60Ghz64bit入侵检测效劳器*eon〔tm)2*CPU2.0GHz3.87G内存图6测试网络构造图测试说明：入侵检测系统包括Snort和IceNetwork;发包机器，可以按照指定的速度发送全部是攻击数据的网络数据包。发送包间隔中插入特定Sleep(0)进展时间延时。攻击包的构造是通过依照Snort规则构造的。测试丢包率结果如下：在纯攻击包流量压力较小时，两者均有较好的处理效率。当流量压力加大时，Snort丢包率明显增大，而IceNetwork显示出较好的检测引擎执行效率与抗压能力。实验说明，这种基于数据流管理平台进展网络平安事件监控的设计思路是正确可行的。