Computer Engineering and Applications 计算机工程与应用 2010，46（33） 101 面向 IDS 的可变长检测器生成算法研究 张玉花，张 星 ZHANG Yu-hua，ZHANG Xing 河南城建学院 计算机科学与工程系，河南 平顶山 467064 Department of Computer Science and Engineering，Henan University of Urban Construction，Pingdingshan，Henan 467064，China ZHANG Yu-hua，ZHANG Xing.Research on Intrusion Detection System oriented variable length detector algorithm.Com- puter Engineering and Applications，2010，46（33）：101-103. Abstract：Detector set affects efficiency and veracity of the Intrusion Detection System based on artificial immunity system. A variable length detector algorithm is presented aiming at the efficiency and false negative rate of intrusion detection sys- tem based on artificial immunity system.Compared with the other algorithms，it decreases the holes and redundancy detectors. The design thought，detail procedure and the realization in intrusion detection system are also proposed.An experimental ex- the same time，the algo- am and results are given to prove that rithm can also holds for other abnormal detector problems. Key words：intrusion detection system；artificial immunity system；variable length detector；detection rate this algorithm is effective in Intrusion Detection System.At 摘 要：在基于人工免疫的入侵检测系统（IDS）中，检测器集合直接影响检测结果的效率和准确度。针对目前基于人工免疫的 IDS 中检测效率和漏警率问题，提出了一种可变长检测器生成算法。该算法相对于已有的算法，降低了黑洞区域，减少了冗余检 测器，提高了检测器生成效率和检测效率。给出了算法的设计思想、具体步骤以及在入侵检测系统中的具体实现。对算法的分 析和实验表明，本算法用于入侵检测系统，提高了检测的准确率，降低了漏警率。同时，对各种异常检测向题具有一定的适用性。 关键词：入侵检测系统；人工免疫；可变长检测器；检测率 DOI：10.3778/j.issn.1002-8331.2010.33.028 文章编号：1002-8331（2010）33-0101-03 文献标识码：Ａ 中图分类号：TP393.08 1 引言 目前，入侵检测系统（Intrusion Detection System，IDS）正 在网络安全防护中发挥着重要作用，但同时也存在漏警率较 高、检测效率较低等问题，极大影响了检测结果的可信性。入侵 检测问题与生物免疫系统（Biological Immune System，BIS） 消灭外来病原体入侵问题具有惊人的相似性[1]。近年来，基于 人工免疫的入侵检测系统也多有研究。在基于人工免疫的入 侵检测方法研究中，检测器对应于抗体，网络行为对应为抗 原，检测器检测网络行为是否正常的过程被抽象为 BIS 中抗 体识别抗原的过程。由此可见，检测器集合影响着入侵检测 的结果。目前基于免疫的检测器生成算法主要有穷举生成算 法、线性检测器生成算法、贪心检测器生成算法，r 可变的检测 器生成算法等。这些算法均不同程度地存在检测器生成效率 低、检测器冗余、检测黑洞问题（检测黑洞问题是指依据检测 器生成方法在非我空间无法产生检测器的区域）。这些问题 应用于入侵检测系统，就造成了检测速度较慢、所需检测器数 目较大，检测具有较高漏警率等问题[2]。基于此，提出了一种 可变长检测器生成算法，通过检测器匹配长度的变化伸缩提 高了检测器的覆盖范围，消除了黑洞区域，同时减少冗余检测 器数量。算法应用于入侵检测系统，提高了入侵检测系统的 检测率，降低了漏警率，提高了检测性能。 2 算法相关定义和问题描述 2.1 相关的定义 为了更好地理解后边的算法，首先作如下定义： （1）模式串：长为 l 的编码串，l≥0。当 l=0 时，模式串=“”； 当 l>0 时，每一位有 k 种可能的编码。这里，k 表示字符集的大 小。k 个字符分别用{0，1，…，k－1}表示。 （2）“+”操作：“模式串 a+模式串 b”表示模式串 b 连接在 a 结尾，如“12”+“543”=“12543”。特别地，任意模式串 a+“”= “”+模式串 a=模式串 a 本身。 （3）子串：一个模式串中的部分连续的字符，称作这个模 式串的子串。即如果存在模式串 a，b，c 且 c=a+b，则 a，b 均是 模式串 c 的子串。 （4）求子串集合Φ（S）：设 S 是一个模式串集合，集合Φ（S） 表示 S 中所有模式串的所有子串的集合。 （5）待选检测器：是指任意可能的模式串。 （6）匹配规则：对于任意两个模式串 a 和 b，当且仅当 a 是 基金项目：河南省教育厅自然基金项目（No.0844204826）。 作者简介：张玉花（1968-），女，副教授，研究方向：网络安全、人工智能；张星（1981-），女，讲师，研究方向：网络安全、智能信息处理。 收稿日期：2009-04-01 修回日期：2009-05-20 

102 2010，46（33） Computer Engineering and Applications 计算机工程与应用 b 的子串时，称 b 被 a 匹配。 定义当前搜索的层次为 i，从 i=L 层开始从左到右搜索，对 （7）Str（node）：节点 node 所表示的模式串。这里，节点 于每个节点： node 是一个模式串。 2.2 问题描述 根据以上定义，构造出如下的问题模型：字符集的大小为 k，自我个体长度为 l，自我集合为 S，有限全空间 I 表示在此字 符集上全部长度不大于 l 的字符串。要求找到检测器集合 D，D 是 I的子集，且 D尽可能消除黑洞区域。即算法应该具有只够高 的覆盖率 Pc 和较低的漏报率 Pf（Pf=1－Pc），并尽可能高效。 3 可变长检测器生成算法 算法具体步骤如下： （1）将全空间看作一棵根为空串，深度为 l+1 的 k 满叉树， 如图 1 所示。其中深度为 1 时表示空串，深度为 2 时表示长度 为 1 的串的集合。以此类推，当深度为 l 时，表示长度为 l－1 的串集合。每一个节点包含一个字符，但每个节点均代表一 个模式串，这个模式串等于在其父亲节点表示的模式串后面 连接其自身字符而构成的模式串。如第 3 层第 2 个节点包含 的字符为 1，其父亲节点的模式串为 0，则该节点所代表的模 式串为“0”+“1”＝“01”。又如，对于该节点的 k 个孩子来说， 它们所代表的模式串分别为“01”+“0”，“01”+“1”，…，“01”+ “k－1”（这里，k－1 表示 1 个字符）。 0 0 1 … K-1 0 Root= 空集 1 … K-1 … … K-1 K-1 0 1 2 L 图 1 全空间树 （2）从根节点开始，从上到下，从左至右，对于每一个预检 测器 d（即节点所代表的模式串），做如下操作：如果 d 是某自 我个体的子串，则丢弃；如果 d 不是任何自我个体的子串，则 将 d 加入检测器集合 D，并对全空间搜索树进行剪枝。由于 d 所在节点的子孙节点均可被 d 匹配，无须再进行搜索，则删除 其所有子树节点。 （3）由于搜索过程是从根节点开始，从上到下，从左至右， 因此检测器的长度应该是递增的。按检测器长度从小到大的 顺序，对于每一个预检测器 d，如果它被已有检测器匹配，则直 接丢弃 d 并删除其所有子树节点。这里主要是借助变长模式 串匹配的特点，通过找到模式串覆盖范围的真包含关系，减少 了模式串的个数。 （4）直到满足算法终止条件。终止条件可以是找到足够 数量的检测器，或满足一定的覆盖率，或搜索完毕。 （5）利用检测器监视受保护的串。若待检测的串被某个 检测器匹配，则表示发生了异常变化。 此算法是通过宽度优先遍历来生成预检测器，通过剪枝 来减少搜索空间。实际上，可以采用利用折半遍历的思想来 加速算法。具体步骤如下： （1）如果该节点是检测器，则其父亲节点可能是检测器， 对 i=Int（i/2）（向上取整）层祖先节点进行搜索。如果其祖先 节点是检测器，则丢弃当前预检测器，并将其祖先节点设为当 前预检测器，令 i=Int（i/4）继续进行搜索。如果其祖先节点不 是检测器，令 i=i/2+i/4 继续进行搜索，如此类推即可。最后， 将找到的检测器加入检测器集并执行剪枝操作，即将找到的 检测器的所有子树节点删除。 （2）若该节点不是检测器，则其父亲节点必然不是检测器 而无须进行搜索，对同一层的其余节点进行搜索。 （3）如果找到的检测器数量已足够，或 i=L 层已无可选节 点，则算法终止。 4 算法分析 为了对算法性能进行分析，对算法的黑洞数、检测率及 检测器个数进行了对比。比较对象主要是穷举生成算法检 测器（穷举检测器生成算法与线性检测器生成算法和贪心 检测器生成算法的黑洞个体和数量完全一致）、r 可变检测 器生成算法[3]。 设固定 L=16，自我大小固定为 2 048。检测率（覆盖率）定 义为“可检测到的集合大小占非我集合的比例”。当检测器数 量相同时，各算法的检测率如表 1 所示，可以看出通过调整检 测器的长度，覆盖率明显高于穷举检测器生成算法和 r 可变检 测器生成算法。同时，当检测器数目相同时，各算法检测率如 表 2 所示，可见本文算法明显较优。特别是在自我集较大时， 由于“黑洞”问题，穷举检测器生成算法和 r 可变检测器生成算 法能够生成的检测器数目逐步减少，其覆盖率急剧下降。因 此，本文算法生成的检测器在数目和质量上较优。 表 1 各算法检测率（覆盖率）对比表 （%） 检测器 数量 100 1 000 4 000 8 000 穷举检测器生 r 可变检测器生 成算法 成算法 1.8 6.7 23.8 43.3 2.6 17.8 42.6 68.5 本文 算法 16.6 56.8 89.5 98.4 表 2 各算法检测率（覆盖率）对比表 （%） 自体 大小 2 048 4 096 8 192 16 384 穷举检测器生 r 可变检测器生 成算法 成算法 30.5 78.6 76.4 40.7 71.6 84.5 77.8 41.2 本文 算法 97.8 98.4 98.2 98.5 5 算法在入侵检测系统中的具体应用研究 5.1 生物免疫系统与入侵检测系统对应模型 网络对应生物体，网络中的主机对应生物免疫系统中的 淋巴结，免疫系统中的抗原被映射成 AIDS 中的网络行为。根 据免疫学原理，抗原又被分为自体抗原和非自体抗原，因此自 体抗原被映射成正常网络行为，非自体抗原被映射成非法网 络行为。生物免疫系统中抗体（包括成熟抗体和记忆抗体）识 

张玉花，张 星：面向 IDS 的可变长检测器生成算法研究 2010，46（33） 103 别抗原的过程就是识别判断抗原是自体/非自体的过程。入 侵检测系统中，检测器（正常行为轮廓）对应于抗体，网络行为 对应为抗原，检测器检测网络行为是否正常的过程就被抽象 为 BIS 中抗体识别抗原的过程。 5.2 自体与非自体形式化描述 定义论域 D ={01}l，抗原集合 Ag Ì D，自体集合 Self Ì Ag， 非 自 体 集 合 Nonself Ì Ag 。 有 Self  Nonself = Ag ，Self  Nonself = ϕ 。其中 Ag 表示对网络上传输的 IP 包进行特征提取 得到的长度为 l 的二进制字符串，包括 IP 地址、端口号、协议类 型等网络事务特征。Self 集为正常网络服务事务，Nonself 集 为非法活动或网络攻击。 5.3 抗原与抗体 抗体抗原的匹配采用r匹配算法，如公式（1）所示。其中1表 示匹配，0 表示不匹配，l 为字符串长。当抗体 Ab 和抗原 Ag 之 间连续匹配的位数大于等于r值时，则认为 Ab 与 Ag 二者匹配。 = y iff$ij(x j j - i ³ r0 < i < j £ lijr Î N) ...x x i = y = y f (xy) = ì 1 ï í ï 0otherwise î 5.4 仿真实验及结果分析 match i i + 1 i+1  j （1） 实验在网络实验室完成。使用随机生成的自我集合，设定 自我集大小为 2 048，检测器集大小为 4 000。实验结果采用 TP 值（检测率）对算法进行评估。模拟对网络进 flood、land、tear- drop 等 20 多种攻击，采取每 100 个数据包中夹杂 20 个非自体。 实验表明：系统的检测率在 98％以上。为了便于比较，采用了 3 个开放源代码的 IDS 系统：Snort、Bro、Dragon IDS，共选用 5 天时间测试，各检测器的检测率如表 3。 通过对比以上实验数据可以发现，本文方法的检测率与 其他 IDS 系统相比均有所改善。究其原因为本算法采用变长 检测器长度，通过检测器匹配长度的变化来伸缩检测器的覆 盖范围，消除黑洞区域和黑洞点，从而降低了漏警率（1－检测 率），提高了报警的可信性。另外，本算法所需检测器数目较 表 3 各检测器检测率对比表 （%） 时间 1 2 3 4 5 Snort 95.38 95.74 95.30 95.72 94.81 Bro 96.18 96.63 96.48 96.31 95.46 Dragon 本文方法 96.41 96.28 97.12 97.09 96.86 97.38 98.12 98.24 98.68 97.86 少，有利于实时检测。 6 结束语 分析了入侵检测系统的报警可信性问题，提出了可变长 检测器生成算法。该算法通过检测器长度的变化，提高了检 测器的检测率，降低了黑洞区域，空间覆盖率明显提高，实现 了以较小的检测器集合，检测到较大范围的“非己”行为。应 用于入侵检测系统，提高入侵检测的检测率，降低了漏警率， 实验结果表明了算法是有效的。该算法不仅适用于基于人工 免疫的入侵检测、病毒识别等网络安全相关领域，同时对其他 的异常检测、变化检测问题，具有一定的借鉴意义。 参考文献： [1] 李 涛.基 于 免 疫 的 网 络 监 控 模 型 [J].计 算 机 学 报 ，2006，29（9）： 1515-1522. [2] 符海东，李雪.一种基于危险理论的双信号免疫入侵检测模型[J]. 计算机工程与应用，2008，44（14）：113-117. [3] 张衡，吴礼发，张毓森，等.一种 r可变阴性选择算法及其仿真分析[J]. 计算机学报，2005，28（10）：1614-1619. [4] 鲁云平，宋军，姚雪梅.基于免疫的网络入侵检测算法改进[J].计算 机科学，2008，35（9）：115-118. [5] 何申，罗文坚，王煦法.一种检测器长度可变的非选择算法[J].软件 学报，2007，18（6）：1361-1369. [6] 闫巧，江勇，吴建平.基于免疫机理的网络入侵检测系统的抗体生 成与检测组件[J].计算机学报，2005，29（9）：1515-1522. （上接 90 页） 方法也可拓展到双环网络的其他领域，最优双环网络的路由 算法、容错控制等均可在直角坐标系下得到很好的研究，是今 后新的研究方向。 [4] Dharmasena H P，Yan Xin.An optimal fault-tolerant routing al- gorithm for weighted bidirectional double-loop networks[J].IEEE Trans on Parallel and Ditributed Systems，2005，16（9）：841-952. [5] 刘焕平，杨义先，胡铭曾.最优双环网的构造[J].系统工程理论与实 参考文献： [1] Bermond J C，Comellast F，Hsu D F.Distributed loop computer networks：A survey[J].Parallel and Ditributed Computing，1995， 24（2）：2-9. [2] Mukhopadhyaya K，Sinha B P.Fault-tolerant routing in distribut- ed loop networks[J].IEEE Trans on Computing，1995，44（12）： 1452-1456. 践，2001，21（12）：72-75. [6] 周建钦，汪文娟.最优双环网的构造[J].计算机工程与应用，2008， 44（35）：62-65. [7] 方木云，汤红霞.非单位步长双环网络平均直径的研究[J].华中科 技大学学报，2009，37（6）：12-15. [8] 陈宝兴.基于 Cayley图的互连网络的研究[D].厦门：厦门大学，2004. [9] 方木云，赵保华.一种新的无向双环网络 G（N；±1，±s）直径求解方 法[J].通信学报，2007，28（2）：124-129. [3] Hwang F K.A complementary survey on double-loop networks[J]. [10] 李颖，陈业斌.基于树的无向双环网络 G（N；±r，±s）寻径策略[J]. Theoretical Computer Science，2001，263（4）：211-229. 华中科技大学学报，2009，37（6）：8-11.