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

谭建龙 沈星星 王映

摘要：数据流管理系统（data stream management system DSMS）是处理动态数据集合的一种数据管理技术，采用数据流模型对网络入侵检测系统(Network Intrusion Detection System-NIDS)进行设计，可以利用数据流中多持续查询优化的技术，提高网络入侵检测系统的性能。同时使用关系数据流模型可以让入侵检测系统结构更加清晰，扩展性更好。文章描述网络数据的关系结构化，入侵检测特征的关系查询表示以及过滤型多持续查询优化技术。这个系统可以认为是数据流管理系统的一个应用系统，体现了一些数据流管理的概念和核心技术，对设计和实现通用的数据流管理系统具有一定借鉴意义。本文将重点围绕数据流查询（continue query）的编译优化、数据流管理技术和网络安全应用的关系进行分析。

1.数据流管理系统的功能

数据流管理技术是处理相对固定不变的大量查询和源源不断的流动数据的技术。而网络信息安全是解决对网络信息的分发、通讯、管理的问题。由于网络信息是典型的源源不断的数据流，同时有很多网络信息安全应用系统是采用大量查询方式，对这些网络数据流进行处理。所以网络信息安全是数据流管理研究的一个很好的典型应用。这个安全应用必须不间断无延迟地处理在线、持续的高速网络数据流，且网络数据不可能全都保存在外部存储器中。我们的研究就是基于持续查询概念，采用数据流管理系统作为流数据处理平台，将其应用到网络安全监控系统中去。我们实现了一个基于数据流处理模型的网络安全事件监控系统IceNetwork。在这个系统中，数据流管理平台通过优化执行注册于系统中的大量持续查询，对连续网络流进行过滤等操作，完成各种安全事件的监测与报警，从而有效地支持了监控系统的实时性，准确性与灵活性要求。

本文以建立一个网络入侵检测技术系统为案例，采用基于数据流管理技术的思想，来开展数据流核心技术的研究。希望能把工程中的核心问题，转换为数据流管理研究领域的通用问题。

1.1.数据流管理系统的功能

数据流管理系统[1]是为流动数据管理建立的统一平台。在数据库管理中，数据是相对静态的，查询是动态的；而在数据流管理中，查询是相对静态的，数据是动态的。也就是说数据库技术主要研究对数据在外存（磁盘）上的存储索引和一次查询的执行技术，而数据流管理技术主要研究数据在内存中的存储索引和多个执行查询（continue query）[2]的执行技术。数据库管理的一个核心问题是为了高效的查询，如何建立数据对象的索引，而数据流管理技术的核心问题是如何管理这些检索条件和操纵程序，研究如何为实现高效的大量查询进行编译的技术。 

1.2.网络入侵检测系统

为了防范计算机被入侵，入侵检测系统应运而生。所谓入侵检测，就是通过从计算机网络或计算机系统中的若干关键点收集信息并对其进行分析，发现网络或系统中是否有违反安全策略的行为和遭到袭击的迹象，并对此做出适当反应的过程。根据入侵检测系统部署的位置以及网络数据的来源，入侵检测系统可以分为两类：主机入侵检测系统(HIDS)和网络入侵检测系统(NIDS)。其中HIDS部署于单个主机，收集所有进入本主机的数据，加以分析检测。而NIDS部署于一个子网的出入口，以进出子网的网络包做为分析数据源。

通常利用一个工作在混杂模式下的网卡来实时监视并分析通过网络的数据流。其分析模块通常使用模式匹配、统计分析等技术来识别攻击行为。一旦检测到了攻击行为，NIDS的响应模块就作出适当的响应，比如报警、切断相关用户的网络连接等。由于NIDS采用在关键节点集中监测的方式，能够监控整个子网，并且对于子网内单个主机来说是透明的，因此部署起来比HIDS方便得多。随着越来越多的单位和企业采用以太网的局域网组网方式，NIDS得到了广泛的应用。NIDS的主要检测手段是模式匹配，这里说的“模式”是指，网络数据包的头部信息或者载荷中的数据满足的特定条件，网络安全领域把能够判定一个入侵的一组特征条件叫做“特征(Signature)”。

Snort[3]是一个成熟的、被广泛使用的、开放源代码网络入侵检测系统，它的有效性已经得到时间的验证。它具有一个可配置的特征库(因为它的每一个特征对应于一条规则，我们也把它的特征库称为规则库)，最新版本的Snort规则库包含了约2300条常见网络入侵的检测规则。图1为Snort2.0中检测引擎的工作流程图。

图1  snort2.0 包数据和特征(处理图)

典型情况是包通过且仅通过多特征过滤引擎一次，所以设计高效的多特征过滤引擎是入侵检测系统的核心问题之一。对于一个在监控整个子网的入侵检测系统来说，网络数据捕获，TCP组包、应用协议分析、特征设计方、多特征过滤引擎是决定效率的主要方面，也是研究的重点内容。

2.关系数据数据流模型的网络入侵检测系统

一个采用数据流管理系统作为处理引擎的NIDS的结构如图2所示。

其中捕包前端负责将以太网数据帧捕获，并转换为预定义的结构化数据，提交给入侵检测引擎。入侵检测引擎的核心是DSMS引擎，其中预先注册了大量以数据流查询语言表示的入侵检测条件。当格式化的描述网络数据包的关系元组到达时，计算注册查询。检测结果被传给检测结果处理模块，以对入侵进行报警等后续处理。

2.1.网络入侵检测系统和数据流管理技术的关系

如果我们把网络入侵检测系统看作数据流管理系统的一个应用，数据流管理系统为入侵检测系统提供一个基础的平台，那么数据流管理平台就需要为入侵检测系统提供一些核心技术的支持。

下表说明网络入侵检测系统和数据流管理技术的关系。从对照比中我们可以看出入侵检测系统需要使用到大量的数据流管理的核心技术。把数据流管理研究的技术应用到入侵检测系统中，将为入侵检测系统提供良好的性能和扩展性。

2.2.网络数据关系化

我们利用改进的轻量级捕包程序winpcap进行捕包，对于每一个IP包，首先对载荷部分进行统一的关键词扫描。如果没有命中的关键词则将其抛弃；否则，将其拼到相应的TCP流，提取包内各个字段信息，分别生成两个流：TCPLink 与Packet。

TCPLink包括一个连接的四元组信息，表示了一个包所属的TCP连接，两个流格式如下：

其中，TCPLink是主流，每一个元组对应一个连接；Packet是辅流，记录主流中每个元组对应的每一个包的各个字段的具体值。主流与辅流之间是一对多的关系。通过对网络包的预处理，形成两条流，完成了网络数据的关系化，从而可以在其上进行关系操作。

2.3.入侵检测特征的关系查询表示

数据流管理系统只接受SQL语句表示的查询，因此我们必须将Snort的特征转换为SQL表示，这需要解析Snort规则。我们实现了一个规则转换程序RulesParser，读入标准snort规则，生成数据流管理系统NIDS的SQL查询。

一条典型的Snort规则如下：

alert tcp any any -> any 6666:7000 (msg:"EXPLOIT CHAT IRC Ettercap parse overflow attempt"; 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,www.bugtraq.org/dev/GOBBLES-12.txt; classtype:misc-attack; sid:1382; rev:9;)

这条规则表达的含义是：一个TCP数据报，无论来自哪个IP地址的哪个端口，只要是6666:7000 端口，并且含有二进制串” PRIVMSG”，“nickserv”，“IDENTIFY ”等则触发报警，报警信息为” EXPLOIT CHAT IRC Ettercap parse overflow attempt”。 

转换成关系数据上的查询

SELECT * FROM packet WHERE packet.ip_proto=6 AND (packet.DestinationPort>=6666 AND packet.DestinationPort<=7000) AND (packet.flowflag&18)=18 AND packet.ruleid=110 AND substr(content,”PRIVMSG”) AND    substr(content,” nickserv”) AND substr(content,” IDENTIFY”) AND bytetest(content,100)

3.过滤型多持续查询优化

网络入侵检测系统所注册的持续查询基本上均为过滤型查询（Filter），即对由网络包生成的关系表中某些字段的选择操作。这些字段类型包括字符型、整型等。我们分别针对不同字段类型设计过滤型多持续查询优化算法。

3.1.字符字段的多串匹配优化

字符串匹配是包的规则检测中最耗时的一个操作，很大程度上决定了检测引擎的性能。snort2.0中采用改进的Wu-Manber[4]和Aho－Corasick[4]多串匹配算法，比以前的算法性能有了大幅提高。在我们的系统中，采用了一种新的高效多串匹配算法SBOM[6]，试验表明，这种算法同样能取得较高的性能。

3.2.整数字段的模式匹配优化    

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，如果第一条规则不满足必然不满足第二条规则，因此不用再进行第二次比较。可见顺次执行各条规则的判断导致产生多余的比较。

所以，针对上述两个弊端，我们提出新的数值型模式匹配算法，充分利用大量注册查询能够事先知道的优势，将其进行预编译，形成有效的内部数据结构（一个DFA，或者说是一棵匹配树），使得匹配时间不由规则数目线性决定，并减少不必要的比较，从而缓解规则数目大，网络流速高，导致检测引擎效率降低的困难。

3.2.1.问题形式化

给定一个关系，关系是一个属性的（attribute）集合：a1, a2…an.每一个这个关系上的元组都由各个属性域上的值组成。每一个属性有它特定的值域范围aj ∈Dj.每一个规则是一系列谓词的合取范式，每一个谓词对应于一个属性的判断。

  ∀i ∈{1,2 ⋅⋅⋅m} : Ri  =      其中，Pij有如下形式  Pij :Dj →Boolean

如果某个规则中对于某个属性域没有，则认为这条规则对于这个属性域的取值是此属性域上的所有值。

首先任意确定一个属性顺序a1,a2…an，则每一个元组就成为此顺序的属性值域上的序列，且序列的长度是n。每条规则都可以转化成一个顺次对每个属性值判断的谓词的合取范式，可以看成一个非确定有限自动机（NFSA）。我们对每一条规则都进行形式化规范，这样使其精确地由n个条件序列组成。其中的第i个条件就是作用于第i个属性域上的谓词。如果对第i个属性域没有，则认为它可以取所在值域上的所有值，在自动机中以TRUE代替。从而，每条规则都转化为一条匹配路径，如图4。同样的处理办法，对于每一条规则都进行规范化，都成为n个比较步骤。将所有的规则首尾并列连接起来，就形成一个对应于所有规则的非确定自动机。如果将其转化为一个确定性自动机，则对于每一个元组，走一遍自动机，顺次对每一个属性域上的值进行比较，走完n步之后，可以找出这条属性满足的所有规则。这种算法的关键是将这个NSFA转化为DSFA。传统的字符串匹配中的自动机转化方法不能直接应用到此情况中。首先，每个属性的值域是不确定的，而且可能不是有限域，如值域为整个整数域。而字符串匹配中自动机的值域就是26个字母，是确定的有限的。另外，不同属性的值域可能不同，不像字符串自动机中，每一步匹配的值域都是字母集合域。所以，针对规则匹配的自动机转化，需要解决的问题是对于每个不同的属性，如何确定每个属性域上的值域，以及如何将原始值转化为新的属性域上的新值。当前我们仅考虑所有字段都是整数域的情况（对于非整数域数值，我们经过预转换将其映射到整数域）。对于整数域上所有值不可穷尽枚举的问题，我们通过生成新字母表的方法解决。下面讲述具体算法。

         P1        P2                TRUE             Pn

                        图3匹配路径

3.2.2.算法概述

⏹生成新值域

对应于某一个属性，通过下面所述的转换方式，根据所有规则在此属性上的取值，为此属性域构造新的值域。这个值域是一个整数集合，它的势是有限的。这样我们就为每一个属性分别构造了类似于字符集合的有限的属性域，从而可以运用自动机思想来进行匹配。

设有m条规则，对应于某个属性i的值域构造方法如下：

对于整数域上的每一个取值范围，都可以统一用左关右开的值域来表示。设置最大值MaxNum与最小值MinNum，这个值取得足够大（小）从而所有元组的真实取值都不会超过这个范围。如对于端口号，设置MinNum=0,MaxNum=65535。则对于a1=m，可以表示为a1∈[m,m+1）；对于a1m，可以表示为a1∈[m+1,MaxNum）； 对于n图4  分段整数轴，构造新的值域

⏹生成自动机

假定有n个属性域，共有m条规则。则自动机树是一个n层的树，每一层代表对一个属性值的判断。树的每一个节点是一个向量。向量的每一个元组是一个结构，包含指向下一个树节点（nextnode）的指针以及当前树节点所匹配的规则集合（ruleset）。非叶子节点的Ruleset均为空，因为此时没有匹配成功的规则。如果某个节点的nextnode域为空指针，则表示由当前规则集在这一层所表示的属性上的相应值有匹配状态，指针指向下一个状态节点。而如果某个节点的nextnode域为空指针，说明匹配树到此状态为止已经停止，没有进一步的状态。向量的大小对应于此节点包含的规则集在所属属性域上划分出的新值域的个数。向量的下标值对应于新值域上的相应取值。向量在每一个下标下的值是一个指向节点的指针，表示当前状态节点在对应取值下的状态转换。

                            图5 规则树结构图

上图为由Rule1,Rule2,Rule3生成的匹配树自动机。

匹配树自动机从左至右共三层，每层对应一个属性字段的匹配，在这里为SourcePort、DestPort、ttl。每个节点对应一个临时规则集，表示匹配到这个节点时剩余可能最终匹配成功的所有规则。根节点对应的规则集为原始规则集，包括全部规则数。每个节点根据对应的临时规则集在相应属性上的划分，生成当前节点的新值域。接着根据当前规则集的各条规则分别生成各个新值域上的后继状态节点。叶子节点的规则集指针指向全部属性匹配结束后最终匹配的规则集合。如上所示，全部规则经过预处理，整体编译成一棵自动机匹配树的内部表示形式，从而支持高效的多查询执行。

⏹运行自动机

对于每一个到来的元组，判断哪些规则满足的过程就是将元组的各个属性上的值在生成于内存中的自动机上跑一遍的过程。由根节点开始，按自动机属性顺序进行每一层的匹配。如果在中间的某一层，下一节点指针为空，说明没有匹配规则。如果匹配到最后一层，则相应规则集代表此元组所触发的所有规则集。

3.2.3.复杂度分析

⏹时间复杂度：

设|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层的过滤后，剩下的元组数目占总数目的百分比。

⏹空间复杂度

对于普通查询算法，所有查询只需在内存中存储一次，而顺次执行导致比较次数有冗余。优化查询算法存在规则的重复存储，而比较次数却大大减少，相当于是用空间换时间。优化算法在自动机转化过程中，存在状态数目指数增长的问题。为了防止空间复杂度过大，我们可以采取将规则分组，分别生成多棵匹配树，从而使每棵树的大小可控；还可以让相同状态共用指针，而不是以在内存中再存储一个拷贝的方式，来解决空间复杂度过大的问题。

3.2.4.优化算法的改进

一旦规则集给定，属性顺序给定，生成的匹配自动机就是确定的。到来的元组跑一遍自动机，或者在中间的某层打住，表示没有任何规则匹配，或者在最末一层停止，相应的规则集表示匹配规则。元组所匹配的步数代表了自动机的效率。匹配步数由到来的元组的分布情况以及匹配自动机的形状共同决定。假设到来的元组是均匀分布的，不考虑由元组分布造成的对匹配效率的影响，则匹配自动机的形状就是决定效率的因素了。我们希望找到效率最高，即平均匹配步数最少的自动机生成方法。已有研究显示，达到全局最优是NP hard（多项式时间难解）的问题[7]。我们只能通过一些启发式方法，进行局部优化，改进效率。我们从以下两个方面考虑：

⏹属性选择度

为了到来元组在匹配过程中能尽早打住，从而减少平均总比较次数，应该将过滤度（Ki）高的属性排在自动机的前部。过滤度的度量没有一个确定的算法，我们提出以下几种可行的度量方法。

a.值域范围百分比。

Ki＝1－（∑dij / di）/m，dij表示第j条规则中属性i在新值域上的定义范围， m表示规则总数目。di表示属性i的新值域范围。1－（∑dij / di）/m的值越大，表示经过过滤后可能被排除的范围越大，即过滤度越高。这里通过值域范围反映过滤度大小。

b.信息熵。

我们借鉴优化决策树生成理论，引入机器学习中的聚类（clustering）算法。算法从一个分类的有不同属性的数据集合中生成决策树。生成过程利用信息增益（information gain）的概念。数据的某个属性的信息增益是将一个数据集划分后熵（混乱，无序）的减少量。划分后数据集的熵的度量是将每一个划分集大小相对于原始数据集大小的比例作为权重累加。一个规则集合S的熵E通过如下公式计算

      Es=∑-1/n log2(1/n)=log2(n)

则一个规则集S在属性A上的信息增益通过如下公式计算

      G(s,f)=Es-∑|Sv|/|S|*Esv= log2(|S|)-∑|Sv|/|S|* log2 (|Sv|)

Sv代表对于规则集S,在属性A上划分之后生成的各个规则集合。|Sv|，|S|代表集合的数目。

我们对原始规则集以及划分后生成的多个规则集，计算各个属性上的信息增益,选择大的作为先匹配的属性。这里通过信息增益来反映过滤度，实际上是认为，划分后分布越均匀的属性有更大的区分度。

c.经验判断

在实际的网络安全监控系统中，利用经验来判定区分度与优先顺序是可行的。在包过滤步骤中，源、目的端口有较强的区分度，对这个属性的过滤能较均匀地将规则集分类，应该放在前面匹配。而ttl值这个属性的区分度相对较弱，应该放在靠后的位置。我们可以根据经验将各个属性区分度排序，从而确定一个较优的匹配顺序。

⏹规则集分类

将规则集预分类，相同类型的规则作为一个初始规则集。如TCP规则集，UDP规则集，ICMP规则集等。这样有两个好处。一是每一个自动机匹配树的规则集不会太大，状态数目可控，并且多棵树可以并行运行。二是相同类型的规则有类似的属性字段，有些字段是某种规则集特有的，如ICMP的itype字段，在TCP规则集中就不需要考虑。所以针对每一种类型的规则集生成相应的自动机，能够减少自动机匹配树的层数，从而提高匹配效率。

4.性能测试

为检验IceNetwork处理引擎的功能与性能，我们设计如下测试方案

测试环境：

测试说明：入侵检测系统包括Snort 和IceNetwork;发包机器，可以按照指定的速度发送全部是攻击数据的网络数据包。发送包间隔中插入特定Sleep(0)进行时间延时。攻击包的构造是通过依照Snort规则构造的。 测试丢包率结果如下：在纯攻击包流量压力较小时，两者均有较好的处理效率。当流量压力加大时，Snort丢包率明显增大，而IceNetwork显示出较好的检测引擎执行效率与抗压能力。实验表明，这种基于数据流管理平台进行网络安全事件监控的设计思路是正确可行的。系统能够完成设计功能，并获得了较好的性能。

5.结论和展望

本文将数据流模型引入系统设计，提出了一种新型的网络入侵检测系统的实现方式。其中网络数据及检测规则的关系化表示，使入侵检测系统结构更加清晰，扩展性更好。多持续查询优化技术提高了检测引擎的性能。接下来，我们将进一步研究面向通用的数据流管理系统的单流多持续查询优化算法，以及多流连接算法。

参考文献

[1.]B. Babcock, S. Babu, M.Datar. Models and Issues in Data Stream Systems. SIGMOD POS, 2002:1-16

[2.]A. Arasu, S. Babu, J. Widom. An Abstract Semantics and Concrete Language for Continuous Queries over Streams and Relations. http://dbpubs.stanford.edu:8090/pub/2002-57

[3.]Snort 2.0 http://www.snort.org.

[4.]Marc Norton.Optimizing Pattern Matching for Intrusion Detection.http:// www.snort.org

[5.]Christophe Diot,  Brian Neil Levine,  Bryan Lyles,  Hassan Kassem, Doug Balensiefen, Deployment Issues for the IP Multicast Service and Architecture. IEEE Network magazine special issue on Multicasting, 14(1):78--88, January/February 2000

[6.]Gonzalo Navarro and Mathieu Raffinot , Flexible Pattern Matching in Strings：Practical on-line search algorithms for texts and biological sequences, Cambridge University Press, 2002,ISBN 0-521-81307-7

[7.]B. Bollig and I. Wegener. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. on Comp., 45(9):993-- 1002, 1996.

作者简介：

谭建龙：中国科学院计算技术研究所软件研究室助理研究员，博士。2003年在中国科学院计算技术研究所获博士学位。主要研究领域包括数据流管理系统、网络信息安全、算法设计等。

沈星星：中国科学院计算技术研究所 硕士研究生

王映：中国科学院计算技术研究所 博士研究生