基于特征值的阴性选择算法和 M HC检测滤窗❋

徐 锐,马文丽,2,郑文岭,2

(1.上海大学 电子生物技术研究中心,上海 200072;2.广州南方医科大学基因工程研究所,广东广州 510515)

计算机病毒与生物病毒在其生活史方面的类似性,提示人们,二者之间在其原理方面亦应存在本质的共性,其在被清除或被控制方面亦应存在有共同之处[1].受此启发,人们开始将生物免疫系统检测原理引入到计算机防护中来.1994年,美国学者 Forrest和 Perelson等人提出了阴性选择算法,使用该算法生成异常模式检测器,从而提出了计算机免疫系统的概念[2].阴性选择算法作为计算机免疫系统中的核心算法之一,在识别“自我”与“非我”时不需要参考“非我”的信息,使其在安全检测中具有了特殊的优势,目前已经被应用于未知和时变环境下故障诊断、计算机安全监控等,具有十分广阔的发展前景[3-8].

然而阴性选择算法其步骤虽然简单高效,但在经典的阴性选择算法中,“黑洞”的存在是任何采用部分匹配方式的阴性选择算法不可回避的问题[9],这一盲点导致无论我们如何改进算法的效率与准确性,耗费多少时间生成检测器集合,总会存在部分“非我”空间无法完全覆盖,这在安全检测过程中作为漏洞,其缺陷对整个安全系统可以说是致命的.本文通过对阴性选择算法进行深入研究,结合了生物免疫系统中 M HC分子表征个体特异性的原理,提出了特征值匹配新原则,构建“自我”特征值集合,并通过加载 M HC独立检测滤窗,从根本上解决了“黑洞”通过安全检测问题.

1 特征值在阴性选择算法中应用

主要组织相容性复合体,即 M HC分子最初是在研究排斥反应的过程中发现的.MHC分子作为代表个体特异性的主要组织抗原,正是它的存在,使得免疫系统不仅可以区分明显属于不同类的“自我”和“非我”,还可以利用存储在 MHC中的“自我”特征值,来有效地区分与“自我”属于同类或者特征十分相似的一些“非我”,从而指导免疫细胞的识别.而这一原理正是本文提出特征值的依据.

网络数据流检测可以用知识表达和抽象的方式分析,通过基因表现型方式[10]分离网络通信数据的多个特征区间,如果可以结合本文提出的基于特征值的阴性选择算法,则两者均具有针对特征值的分离比对,将具有很好的算法耦合和实用价值.这也是本文提出特征值的重要意义之一.

经典阴性选择算法采用二进制字符串进行待讨论问题集合的描述,并使用 r连续位匹配规则作为核心的匹配法则,针对于该算法已经提出一些改进方法用于提高检测准确性和减少“黑洞”的产生数量.所以本文首先从不失一般性的经典阴性选择算法给出一些基本定义和标识,并给出一些新的定义,用于更好地描述算法和进行深入的分析.

1.1 阴性选择的基本定义

1.1.1 模 式

模式分为“自我”模式和“非我”模式,或者称为安全模式和非法模式,在算法中定义整个模式集合为M,采用长度为 L的二进制字符串 mi表现任意一个存在模式,其中 S为“自我”模式集合,NS为“非我”模式集合.检测器集合作为一个特殊的子集合是基于 S通过阴性选择得到的,定义为 D.则有 D⊆NS,以及 S∩ N S=H.

区别于其他,本文还将定义一个新的模式集合 F,它是 NS的一个子集,定义为可以通过检测器但非“黑洞”模式的“非我”模式,称之为“友元”模式集合.

1.1.2 匹 配

本文依旧采用传统的 r连续位匹配规则,即任意两存在模式 m1和 m2,当且仅当它们在 r或多于 r个连续位置上有相同字符时(同为 1或者同为 0),称为它们在 r连续位匹配规则下匹配,记为 M(m1,m2).

1.1.3 黑 洞

定义“黑洞”集合为 H,如果有一个存在模式 hi∈ H为“黑洞”,则必存在 dj∈ D和 mk∈ S使得 M(hi,dj)且 M(mk,dj).根据下面将介绍的阴性选择算法流程,可以得知黑洞是无法被检测器根据匹配原则检测到的.

1.2 阴性选择算法

阴性选择算法的核心是生成检测器集的过程,它的步骤为：对于确定的一个“自我”模式集合,从整个模式集合中随机挑选存在模式,如果该模式与任何一个“自我”模式集合中的模式都不匹配,则它成为一个成熟的检测器,否则被淘汰.

检测器集制备完毕后,开始进行“非我”模式检测.如果外来的存在模式与检测器集中任意检测器匹配,则该模式被诊断为异常模式清除.阴性选择算法的流程图如图 1所示.

1.3 特征值

对于使用 r连续位匹配规则的阴性选择算法,本文通过引入特征值的概念来对它加以改进.这里定义特征值为,对于长度为 L的模式集合,“自我”集中任意模式 mi∈ S,它的特征值为Substring(mi,k,r),1≤k≤L-r+ 1,即对于一个二进制字符串表征的模式,可以得到它(L-r+ 1)个长度为 r的字符串作为特征值,且每个特征值都是该模式字符串的子串,同时每个特征值都对应一个截取子串的起始位 k,所以每个完整特征值信息包含一个子串和一个起始位,记为 e(s,k).

根据如上定义,可以得到一个关于特征值的推论：如果一个模式集合 M1中任意模式,在 M2中总能找到模式与其相匹配,则 M1的特征值集合 E1是 M2特征值集合 E2的一个子集.即 ∀mi∈ M1总 ∃mj∈M2使得 M(mi,mj)则可得

1.4 改进的阴性选择算法

本文采用特征值匹配进行阴性算法的改进,即任意两存在模式 m1和 m2,当且仅当它们各自所有的特征值中有一组相等时(包括子串相同和起始位相同),称为它们在 r连续位匹配规则下匹配,记为M(m1,m2).

基于该匹配原则和公式(1)可知,如果任意一存在模式 mi不与任何“自我”模式匹配,则有 Ei⊈ES.本文提出的新阴性选择算法流程,如图 2所示.

其中,“自我”模式集合的特征值库 E由分别提取每个“自我”模式得到的特征值组成,即在每个起始位 k,共提取 count(S)个子串 s,由于这 count(S)个子串 s可能存在重复情况,所以实际得到的特征值 e(s,k)的数量小于等于(L-r+1)*count(S)个,将随机挑选的存在模式提取的(L-r+1)个特征值与上述特征值库进行匹配测试,从而实现检测器筛选.

使用r邻域匹配函数判定模式间匹配程度的情况下,任意两个存在模式匹配概率为P=(2-r)*[(L-r)/2+1],则不与任何“自我”集中模式匹配的随机挑选存在模式产生的概率为(1-P)count(s),可见在传统的阴性选择算法中检测器的生成概率将随“自我”集中模式数量的增加而成指数增长.而对特征值改进的阴性选择算法,分析可得任意随机挑选的存在模式与“自我”集特征库在某一起始位特征值匹配概率

式中：x为在同一起始位“自我”集中重复的特征值数量,且有 0≤x≤count(s)-1.

则任意随机挑选的存在模式特征值与“自我”集中特征库所有特征值不匹配概率为(1-P)(L-r+1).可见在改进的阴性选择算法中检测器的生成概率与“自我”集中模式数量不再成指数增长关系,同时如果选取特征值相近的一组“自我”模式,将提高 x的值,从而进一步增大检测器的生成概率.

使用提取特征值方法改进阴性选择算法,符合安全检测中对模式进行特征比较的实际情况,有效地改进了算法流程的执行效率,同时使得下面生成 M HC检测滤窗,消除黑洞入侵成为了可能.

2 M HC独立检测滤窗

多年来阴性选择算法都一直被尝试改进,以提高有效检测器的生成概率和尽量减少黑洞数量,但正如前文提及,采用部分匹配方式的阴性选择算法将不可避免地产生黑洞,黑洞的存在是采用部分匹配规则的阴性选择算法不可避免的结果,是系统误报率的底线[11].可以说黑洞已经成为约束该算法的核心问题.黑洞的存在取决于模式集的结构和模式匹配所采用的匹配规则[10].减少黑洞数量时传统的做法就是增加检测器的数量或者改进匹配方法,从而尽可能地扩大检测范围.但这样做存在两个问题,首先是无论采用何种方式改进算法扩大检测器检测范围,诸如实数向量改进[12-13],变 r值迭代[12,14],模糊匹配[15]等都不可避免地付出了昂贵的时间和影响系统性能的代价.Hofmeyr[16]在其论文中提出了采用多重表示(Multiple Representation)的方式来减少黑洞数量,因为 M HC分子同样呈现多态性,所以被认为是模拟生物免疫系统的 MHC机制,但笔者认为这一方法的本质同样是通过扩大检测范围来缩小黑洞面积,而且经验证该方法对系统性能的影响同样较大.

2.1 黑洞特点分析

大部分的研究仅从阴性选择算法本身出发,重点放在了改进检测器的生成流程上,本文则从黑洞本身的角度出发,对它的特点进行分析.

任意两个二进制字符串如果在 r连续位匹配,则当这两个字符串按位取异或时,结果必有长度为 r且各位均为 0的子串存在.即

根据 1.2节阴性选择算法的实现流程,可以得到推论 1,即

1)对于所有的 ndj∈ ND,总有 mi∈ S使存在 Include(mi⊕ndj,1)≥r,其中：nd为任意非检测器模式,ND为非检测器模式集合.

根据 1.1.3节黑洞的定义,以及与“自我”模式和黑洞匹配的检测器(实际不存在)必然在非检测器模式集合中,可以得到推论 2,即

2)对于所有的 hk∈ H,总有 ndj∈ ND,使存在

根据 1.3节公式(1)和本节推论 1,可知对于任意 ndj∈ ND,nhj的特征值集 Endj⊆ES,则有 END⊆ES,其中 END为 ND的特征值集,ES为 S的特征值集.根据 1.3节公式(1)和本节推论 2,可知对于任意 hk∈ H,hk的特征值集 Eh⊆END,其中 Eh为 hk的特征值集.所以可以得到最后结论：

对于任意 hk∈ H,hk的特征值集 Eh⊆ES.

3)这一结论为判别一个“非我”模式是否为不属于“自我”集且检测器又无法检测到的黑洞提供了一个有效可行的办法.

2.2 MHC检测滤窗

2.2.1 M HC限制性

免疫 T细胞是在胸腺内分化成熟的,包括阳性选择、阴性选择两个过程[10].阴性选择使机体获得自身免疫耐受,阳性选择决定了成熟 T细胞的 M HC限制性.T细胞通过识别 M HC分子提供的抗原缩氨酸来达到识别功能.成熟的 T细胞具有两种基本特性：① T细胞识别抗原是 M HC限制性的,即每一个体的 T细胞只能识别与其自身 MHC分子结合的异种抗原分子.② T细胞对自己抗原是自身免疫耐受的,即每一个体的T细胞不能单独识别自己 MHC分子或是与之结合的自己抗原分子.包括阳性选择、阴性选择两个过程的细胞成熟机制对阴性选择算法的改进有很好的借鉴作用.

MHC分子的独特限制性往往从其带来的抗体多样性来研究,检测器附加一个限制条件或者是附带可变 r值也都可认为是这个方向的尝试.但本文希望引入 M HC的特征限制本质,而不是只从机理入手进行模仿.

2.2.2 检测滤窗

根据前文的分析和推论,可以在检测器防护层面之内再加一个由“自我”特征值集表达生成的独立检测滤窗,这一检测滤窗除保留检测器高效、快速、分布式处理的优点外,还可以采用将通过检测器检测的外来模式的特征值进行抽取,然后与自我特征值集进行比对的模式,来有效地判断通过检测器的外来模式是可接纳的安全模式还是黑洞模式.

具体步骤为：首先对任意外来通过检测器检查的“非我”模式 mj∈N S,提取(L-r+1)个长度为 r的特征值,每个特征值仅需与所有 mi∈ S中相应起始位的特征值进行比较,其最大比较次数为

如果该“非我”模式每个起始位的特征值都可以在 mi∈ S中相应的起始位找到相等的值,则判别该“非我”模式属于黑洞集合,mj∈ H,即该模式是一个与“自我”集合特征相似相近的非法入侵模式.

“自我”集合特征值库的完备性以及根据推论得出的特征值完全包含性,即 Eh⊆ES可以得知,采用检测滤窗这一方法可以从根本上杜绝黑洞检测的盲区,从而极大提高检测防护的准确性和安全性.同时因为检测滤窗是安放在检测器防护层之内,所以绝大部分不属于黑洞的“非我”模式仍由传统的检测器进行检测从而进行判断是否为非法入侵模式,其工作效率并未有任何降低,而且对检测器生成算法的任何改进也不会与检测窗产生相互影响,故该检测窗有着独立检测能力.通过检测器防护层的待检测模式可以选择是否再进行滤窗过滤,而最大为N的比较次数也并未占用过多的系统资源.可以说独立检测滤窗是一种可选择的更高级别的安全检测手段,为杜绝非法模式采用黑洞模式绕过检测器进行攻击提供了有力武器.

独立检测滤窗的运作方式与 MHC分子的限制方式均采用了特征值比对的方式,事实上在自然免疫系统中免疫系统也同样是采用 M HC进行模式匹配来解决阴性选择所造成的黑洞问题,所以不妨引入这一概念,将这一滤窗称称为 M HC独立检测滤窗.

3 仿真程序设计与分析

本文采用 .net2005开发平台,使用 C# 语言编制仿真测试程序.程序流程图如图 3所示.

在程序流程图 3的基础上编制仿真程序进行测试.首先选择小规模的模式集合进行测试,而不是直接进行常规测试,以便简单而直观地观察使用MHC检测滤窗的效果.这里选择长度 L为 6的二进制字符串作为模式集合,随机选取 3个模式作为本体的“自我”集合,匹配阈值为 3;然后对程序进行小的修改,设置生成检测器数量参数为足够大,这样得到的检测器集合为整个模式集合中所有可作为检测器的模式;最后用模式集合中除去“自我”模式以外的其它模式作为外来模式进行攻击,使用检测器进行检测,并对比使用和不使用 M HC检测滤窗的差异.结果如图 4所示.

从程序运行的测试结果可以看出,仿真软件随机生成“自我”集合为 {010000,110101,011100},共产生检测器 21个,使用除“自我”集合外全体模式进行攻击,共检测到“非我”模式 56个(其中 21个为检测器模式本身),而有 5个模式是检测器无法检测到的,也就是黑洞集合 {010100,010101,011101,110000,110100},这 5个模式经验证均符合黑洞的定义,而“自我”模式与“非我”模式以及黑洞模式的加和也等于全体模式的总量,M HC独立检测滤窗的有效性得到验证.

再采用规模更大的模式集合进行仿真测试.选择长度 L为 16的二进制字符串作为模式集合,随机选取 100个模式作为本体的“自我”集合,匹配阈值为 8,生成检测器数量为 500,同样产生检测器集之后用所有的除“自我”集合外全体模式进行攻击,测试结果如图 5所示.

从测试结果可以看出,在 100个“自我”模式并使用 500个检测器检测的情况下,共发现“非我”模式58051个,存在黑洞模式 475个,“友元”模式 6910个,总量同样符合 65536个模式空间.在其它 L取值下同样进行全模式攻击测试或随机模式攻击测试,均得到预期结果,如表 1所示.

因为采用的是随机生成“自我”模式,可以看到黑洞的数量并不随“自我”模式呈线性或者指数增加,而是与特征值库的大小有直接关系.同时在选取一定数量随机模式攻击时,因为包含少量随机生成的“自我”模式,所以“友元”模式和异常模式以及黑洞模式的总和并不一定等于攻击模式的数量.

图4 仿真测试结果(L= 6)Fig.4 Simulation result(L= 6)

图5 仿真测试结果(L=16)Fig.5 Simulation result(L=16)

表1 仿真结果Tab.1 Simulation results

以上测试结果说明,使用 M HC独立检测滤窗成功地发现了所有检测器未能阻击的黑洞模式,真正确保了外来模式检测的准确性和安全性.

4 结 论

本文提出了特征值的概念,通过对存在模式提取特征值,组建特征值集,使用特征值比对来替代原有的匹配规则,从而实现了对阴性选择算法的有效改进,提高了检测器生成的概率.然后在借鉴 MHC分子限制理论的基础上引入了检测滤窗,使用“自我”特征值集生成的检测滤窗对通过检测器检测的外来模式进行二次过滤,彻底杜绝黑洞模式的侵入.仿真结果表明,使用 M HC独立检测滤窗可以成功检测到所有安全通过检测器集的黑洞模式,真正意义上消除黑洞这一危险检测漏洞,而其检测时间和对系统资源的占用并未因此显著增加.

[1]郑文岭,马文丽.生物病毒与计算机病毒 [J].科技导报,1995(2)：1-6.Zheng Wenling,Ma Wenli.Biological virus and computer virus[J].Science& Technology Review,1995(2)：1-6.(in Chinese)

[2]Forrest S,Perei Son A S,Allen L,et al.Selfnonself discrimination in a comput er[C].Proceedings of the 1994 IEEE Symposium on Security and Privacy.Los Alamitos,CA,1994.

[3]Esponda F,Forrest S,Helman P.A formal framework for positive and negative detection scheme[J].IEEE Transaction on Systems,Man,and Cybernetics,2003,34(1)：357-373.

[4]Singh S.Anomaly detection using negative selection based on the r-contiguous matching rule[C].Timmis J,Bentley P J.Proc.of the1st Int′l Conf.on Artificial Immune Systems(ICARIS).Canterbury： University of Kent at Canterbury,2002：99-106.

[5]Aickelin U,Greensmith J,Twycross J.Immune system approaches to intrusion detection-a review[C].Proc.of the 3rd International Conference on Artificial Immune Systems.Catania Italy,2004：316-329.

[6]Gonzalez I,Dasgupta D.Anomaly detection using real-valued negative selection[J].Genetic Programming and Evaluable Machines,2003,4(4)：383-403.

[7]Gonzalez F,Dasgupta D,Gomez J.The effect of binary matching rules in negative selection[C].Proceedings of the Genetic and Evolutionary Computation Conference(GECCO),Chicago,IL：Springer-Verlag Press,2003：196-206.

[8]张海英,管洪娜,潘永湘.一种改进的阴性选择算法 [J].西安理工大学学报,2005,21(3)：306-309.ZhangHaiying,Guan Hongna,Pan Yongxiang.An improved instrusion detection negative selection immune algorithm[J].Journal of Xi′an University of Technology,2005,21(3)： 306-309.(in Chinese)

[9]Forrest S.Design principles for the immune system and other distributed autonomous systems[C].Immunology as Information Processing.U SA：Oxford University Press,2000.

[10]Jong K D.Using genetic algorithms for concept learning[J].Machine Learning,1993,13(3)：61-188.

[11]Dhaeseleer P.An immunological approach to changed detection：theoretical results[C].Proceedings of the 9th IEEE Computer Security Foundations Workshop,IEEE Computer Society Press,1996：66-71.

[12]Ji Z,Dasgupta.Real-valued negative selection algorithm with variable-sized detectors[J].Lecture notes in Computer Science,2004,3102：287-298.

[13]Ji Z,Dasgupata D.Augmented negative selection algorithm with variable-coverage detectors[C].Proc.of the 2004 Congress on Evolutionary Computation.IEEE Press,2004：1081-1088.

[14]张衡,吴礼发,张毓森,等.一种 r可变阴性选择算法及其仿真分析 [J].计算机学报 ,2005,28(10)：1614-1618.Zhang Heng,Wu Lifa,Zhang Yusen,et al.An algorithm of r-adjustable negative selection algorithm and its simulation analysis[J].Chinese Journal of Computers,2005,28(10)：1614-1618.(in Chinese)

[15]王辉,王科俊,于立君,等.一种基于模糊思想的变阈值免疫阴性选择算法[J].哈尔滨工程大学学报,2007,11(28)：1222-1227.Wang Hui,Wang Kejun,Yu Lijun,et al.An immune negative selection algorithm with an adjustable threshold based on fuzzy logic[J].Journal of Harbin Engineering University,2007,11(28)：1222-1227.(in Chinese)

[16]Hofmeyr S A.An immunological model of distributed detection and its application to computer security[C].University of New M exico,Albuquerque,NM,1999.