《否定选择算法》PPT课件.ppt

否定选择算法,否定选择算法,1.1 算法功能 1994年，Forrest，Perelson等人提出的否定选择算法成功的模拟了免疫系统识别自我和非 我的免疫耐受过程。这种识别能力源于T细胞(免疫细胞的一种)表面的受体可检测到外来抗原。 在T细胞的产生过程中，通过伪随机遗传重组过程来形成，然后这些细胞通过一个检测过程即 否定选择过程，在胸腺的T细胞(未成熟的T细胞)，对自身蛋白有反应的被破坏，只有那些不与 自身蛋白结合的T细胞可以离开胸腺(成熟的T细胞)此后，这些成熟的细胞就在体内血液中循 环，完成免疫功能，保护身体不受外来抗原损害。 目前，免疫细胞的自体耐受主要由否定选择算法来实现。在入侵检测领域里，使用否定选 择算法生成检测器。 1.2 算法描述 否定选择算法 (如图3.1所示)可概括如下: (1)定义自体为一个长度为L的字符串的集合，S表示“自体”一个受保护或者监督的集体。例 如，S可以是一个文件片段或者是某个系统与过程的活动模式; (2)产生检测器集合R，每一个R中检测器与任何S中的字符串都不匹配; (3)通过不断地将R中的检测器与S比较来监控S的改变。采用部分匹配规则，两个字符串当且仅 当至少在r个连续 位上一样时才发生匹配，是一个被选定的合适的参数，监督S变化。检测 器与S连续匹配，如果任何检测器都匹配，则一定有变化发生。,否定选择算法,2.1 r一连续位匹配规则 r-连续位的匹配规则是指任意两个字符串，如果两个字符串中至少有连续r个对应位上的符号相同，就说这两个字符串匹配。即有任意两个字符串x和y，如果x和y至少有r个连续对应位上的符号相同，则有x和y连续r位匹配。 例如:字符表A，B，C，D，E，x和y为定义于其上的任意2个字符串 X CBACDEAB Y BDADCDEA 其中，有3个连续位上的符号相同(见下划线部分)。当r3时，为x和y匹配。 这种匹配规则可应用于任意符号表上定义的字符串,最通用的符号表为0，l。 在一连续位的匹配规则，用PM为任意两个等长随机字符串的匹配的概率，设如下参数: m:表示符号表所含的符号数目 l:表示字符串所含符号的数目，即字符串的长度 r:表示匹配中所要求的连续匹配位数，即匹配长度 符号表中的m个符号是各不相同的、是互补的。对于字符串每一个位置上的符号，从符号表中选取符号与之匹配即相同的概率是1/m，而与之不匹配(即互补)的概率是(1一1/m)。当两个长度为Z的字符串进行比较时，如果至少有r连续对应位上的符号相同，则这两个串匹配。如果两个字符串匹配，并且这种匹配是:从l长度字符串的最左端开始，有连续r个对应位取值相同，则匹配的概率为:,如果两个字符串匹配，并且匹配的起始位置是从l长度字符串左边的第2位到第(l一r+1)位，那么在每次匹配成功的起始位置之前，总有不匹配发生时，其每次匹配成功的概率为: (m一1)/mXm一 应当注意:该匹配概率是近似值。因为它仅包括了那些在每次匹配成功的起始位置之前，没有匹配发生的情况。而忽视了那些在每次匹配成功的起始位置之前，有匹配发生的情 况。当使r足够大(即m一rl)时，可以减小精度误差。因为当l不变时，随r的增大，两个字符串多处发生匹配的可能性将减小。于是，两个字符串匹配的总概率 可见， PM随m，r和l变化而变化。,2.2 检测能力,2.3 否定选择算法存在的问题,使用否定选择算法产生的检测器覆盖异己空间越大说明检测器的检测能力也就 越强。理想情况下，检测器的容量越大，则覆盖异己空间也就越广。但实际情况 是，自体集合是一个相对较为有限的空间，而非自体集合多数情况下近似于一个 无穷的空间，要完全覆盖异己空间就需要极其大量的检测器。而从实际应用的情 况来看，有限的系统资源无法满足完全产生这些有效检测器的要求。故产生能覆 盖整个非自体空间的检测器是不现实的。同时，根据3.2.4结论2也为该观点提供 了理论基础:有限的检测器可以保护大量的自体数据集。 现在的问题是如何在检测器容量确定的情况下，尽可能多的覆盖异己空间。 Forrest提出的否定选择算法中，使用r一连续位匹配规则产生的检测器会存在 黑洞，使得覆盖异己空间变小。 Forrest否定选择算法中全长串的:一连续位匹配规则会存在两类漏洞:交叉漏洞 和限长漏洞。 (1)限长漏洞 限长漏洞是漏洞串h至少有一个r位窗口不在S，其它窗口能够和S匹配。 例如:S=110010，l=3，r=2，则h=101就是一个限长漏洞。因为检测h的检测串必须 以10开头或者以01结尾，但是任何这样的检测串都会与自体匹配而不能生成。 (2)交叉漏洞 交叉漏洞是一个串h不在自我集S中，h中的所有窗口与S相邻窗口交叉。,2.3 否定选择算法存在的问题,下面用有向非循环图DAG来描述这个漏洞。设s=0002，1011，l=4，r二2，则相应的DAG图(如图3.2所示),从左端结点出发，能够产生串0001，0011，1001，1011，1000，其中0011，1001是交叉漏洞。,3.黑洞问题讨论,3.1 黑洞产生的原因 尽管希望构造一个完整的有效检测器集合，但是总会有一些Nonself字符串无法被检测到，这些Nonself串就称为“黑洞”。图3.3给出了黑洞的直观形象表达，在形态空间中，self集与Nonself集的界面往往是不规则的，而匹配闽值是固定的，因此有一些Nonself不能被任何检测器检测。,黑洞存在于任何匹配规则中，事实上，在生物免疫系统中，也存在黑洞问题，而且病原体总在向黑洞中进化，使其更难被检测到。,3.2减少黑洞数目,对于给定字符串长度L和匹配闭值r下带有固定匹配率的r连续位匹配算法不可避免地会 出现这样的检测黑洞。对于固定不变的Self集合，不同“形状”的检测器可以覆盖不同的 Nonself集，产生不同的检测黑洞，如果能将不同“形状”的检测器共同作用，那么必然可以 减少黑洞的存在。如图3.4所示,3.3漏洞的判定算法,在描述算法之前首先给出以下几个定义。 定义3.1字符串的r模板:在长度为L的字符串中，只对r个连续位置进行定义，其它l-r个位置的字符可以任意取值，这样的字符串称为字符串r模板。 定义3.2第i头模板:是指从字符串的第i个位置开始有确定的定义，则该模板是第i模板。 定义3.3第j尾模板:是指从字符串的第j+l个位置开始没有确定的定义，则该模板是第j尾模板。 例如，*011*就是一个长度为8的字符串的3模板，同时也是一个第2头模板和第4尾模板。 定义3.4字符串的模板匹配:如果一个模板c，其连续:个位置与字符串e的对应位置的字符相同，则称c，和e匹配。例如，*011*和1011010。 判定c是否为漏洞及生成有效检测器的算法: (1)寻找c的字符串r模板，并设其为第i头模板，记为:Ci，使其与C匹配，但不与集合A的任 何元素匹配，同时根据r和i找到cj。如果存在这样的模板则执行第2步;否则认为是漏洞，,如图3.5所示,3.3 漏洞的判定算法,3.3漏洞的判定算法,举例说明: 设模式的长度L=10，有“自体”模式串集合为A=11111100，10001111l，1100110100，0010010011。设“非自体”模式串e=0010110100，匹配长度r=3。 利用上述算法判定字符串c是否是漏洞，如图3.7。首先，构造一个字符串r模板Ci=*101*，然后如图进行搜索，则可以看到*10101010就是一个有效的检测器，因此可以说字符串c不是漏洞。,4.基于改进否定选择算法的异常检测模型,4.1.2模型框架 该模型分为检测器生成和检测器识别两个模块。如图4.1所示。检测器生成模块采用否定选择算法来生成，但将算法中采用的rcb匹配规则用r-字符块匹配规则替换。首先，选择匹配阂值R，设置T检测器容量，利用改进的否定选择算法生成T检测器;其次，选择匹配闭值R1，使得R1R，设置B检测器容量，利用改进的否定选择算法生成B检测器。 检测器识别模块采用B、T双检测器协同识别，匹配规则仍为r一字符块匹配规则。如图,4.3 B/丁检测器协同识别 4.3.1生物免疫中B、丁细胞的作用及其协同关系 生物免疫系统是一个主要由淋巴细胞构成的系统。淋巴细胞有两种，一种是B细胞，它是体液免疫，分泌抗体，抗体能够识别并结合抗原，最终清除抗原。另一种是T细胞，它是细胞免疫。其作用主要是给B细胞提供一个信号，确认B细胞识别的nonself. B、T细胞通过细胞的接收器和抗原的抗原决定基绑定来识别抗原。接收器是由基因片断随机组合生成，接收器和抗原决定基越相似，它们之间的亲合度越高，越容易绑定。识别抗原的任务主要是由B细胞完成的，当它绑定到未接触过的抗原时，会产生一个初次反应，分泌抗体，消灭抗原。同时“学习”并记忆这种特殊的抗原结构，当它再次接触同种抗原时，会快速发生再次反应，表现出很快的响应速度。其中，B细胞的“学习”、记忆能力是通过一个亲和性成熟的过程。在初次反应后，和抗原具有高亲和性的B细胞大量克隆(复制)自身，在克隆过程中以较高的概率进行变异，因变异率较高，所以经克隆、变异过程后产生的新的B细胞，可能其亲合度还不及父细胞，所以必须再经过亲合度判断，亲合度最高的B细胞留下，去替换亲合度低的B细胞。 T细胞是在胸腺中分化发育的，而胸腺中存在体内大部分的self蛋白，当新生成的T细胞可以和Self蛋白绑定时，就在成熟培养的过程中死亡。所以，最后存活下来的T细胞是能识别nonself，而不能识别Self。T细胞的作用就是给B细胞提供一个信号，确认B细胞识别的是nonself，表现出和两种细胞的协同关系，由此可以降低B细胞的误识别率。,4.3.2 B、T检测器原理 该文借鉴B、T细胞协作识别抗原的免疫机理，生成B、T双检测器进行协同识别异常行为。 首先，匹配阂值设置为r，使用改进的否定选择算法生成T检测器。 其次，选择另一匹配闭值r1，令r1r，仍然使用改进的否定选择算法生成B检测器。 最后，生成B、T双检测器进行协同识别。将B检测器作为T检测器的前置过滤检测器，用于进一步减轻T检测器的检测负担，提高检测速度和准确率。 4.3.3 检测器生成 检测器的生成算法(如图4.5)如下: (l)字符串随机发生器随机生成L位的二进制字符串，这时生成的字符串是未成熟的，还不能作为检测器使用，这些随机生成的字符串只是作为检测器的候选字串; (2)二进制字符串与Self集中的每一个字符串作，一字符块匹配运算，如果该二进制字符串与Self集中任一个字符串匹配运算为真，则忽略字符串(所谓的杀死)，转入步骤1，如果该二进制字符串与Self中的每一个字符串都不匹配，那么将该字符串加入到检测器集中去，成为成熟的检测器; (3)判断检测器集中的检测器的数目是否达到一定的量，如果达到，构造完毕，否则转入步骤1。,检测器的生成算法如图4.5如下:,4.3.4 检测器识别 当B、T检测器生成后，就可用它们协同起来识别抗原。正如在机体免疫中用B细胞识别抗原一样，用B检测器集来识别抗原，因为B检测器所覆盖的抗原空间更大。将外来抗原用和检测器一样的编码方式表示，同样运用r一字符块匹配规则，将它们和每一个B检测器相比较，当某个B检测器与之匹配，此检测器被激活，由B检测器的生成过程可知，B检测器可能和sel晒配，所以，为了降低伪肯定率(将seir当作nonsel哟几率)，需要T检测器的协同刺激。此时，将那些由B检测器识别到的抗原再和T检测器相比较，如果能和T检测器相匹配，说明该抗原是nonself，报警。反之，如果不能匹配，则报警等待系统相应。另一方面，B检测器作为T检测器的前置过滤检测器，提高了使用T检测器单一检测器的检测速度。如图4.6所示。,5.仿真实验,在前面章节理论分析的基础上，首先对黑洞问题进行了仿真实验来说明黑洞的存在 及黑洞存在的数量和自体集S本身的相似度、匹配阂值:的大小有关。然后对模型采用 改进否定选择算法生成B、T检测器协同识别检测的检测率进行仿真实验，并通过对 实验结果的分析，来进一步研究基于否定选择算法的入侵检测系统模型，从而验证该 模型的检测准确性，实现较高的检测率和低的误报率。 5.1黑洞仿真实验 (l)采用r连续位匹配算法，在r，L固定情况下。 假设在否定选择算法中采用r连续位匹配算法，字符串长度为L，匹配阂值r固定， 并设为L=10，r=5。自我集s1=0110100110;1000010000;1010101010;1111011100 通过仿真实验，计算出黑洞的数量为4个。如图5.1所示。图中横坐标为自我串的高五 位10进制数值，纵坐标为自我串的低5位10进制数值。图中横坐标和纵坐标交差点上 的黑点代表检测器覆盖异己空间点。图中空白点为self和漏洞点。,5.1Self集相似度小情况下黑洞数量图,当自我集s2=0110100110;1011011000;0010010100;0100110011，通过仿真实验，计算出黑洞数量为2个。如图5.2所示。图中横坐标为自我串的高5位10进制数值，纵坐标为自我串的低5位10进制数值。图中横坐标和纵坐标交差点上的黑点代表检测器覆盖异己空间点。图中空白点为self和漏洞点。,图5.2Self集较相似情况下黑洞数量图,比较图5.1和图5.2可知，Self集本身越相似，黑洞数量越少。 (2)假设在否定选择算法中采用:连续位匹配算法，字符串长度为L，self集固定， 设为s=0110100110;1011011000;0010010100;0100110011，L=10。匹配闽值r可变。 当r=7时，如图5.2所示。 当r=5时，如图5.3所示。,图5.3 当r=时的黑洞数量图 比较图5.2和图5.3可知，匹配闭值:越大，黑洞数量越少。,5.2改进算法仿真实验,要验证模型的检测准确性，主要着重验证该模型采用的改进否定选择算法生成的B、T双检测 器的检测率要比原算法生成的检测器的检测率在一定程度上有所提高。 由于入侵检测是一个很复杂的问题，不仅涉及大量使用的通信协议，而且还涉及到许多操作 系统，网络服务、软件漏洞等。另外，网络中入侵或攻击方式多种多样，因此，我们不可能采用 众多的入侵或攻击分别对模型的功能进行实验验证，所以本次实验我们准备构造一个