否定选择算法.ppt

《否定选择算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、否定选择算法否定选择算法1.1算法功能1994年，Forrest，Perelson等人提出的否定选择算法成功的模拟了免疫系统识别自我和非我的免疫耐受过程。这种识别能力源于T细胞(免疫细胞的一种)表面的受体可检测到外来抗原。在T细胞的产生过程中，通过伪随机遗传重组过程来形成，然后这些细胞通过一个检测过程即否定选择过程，在胸腺的T细胞(未成熟的T细胞)，对自身蛋白有反应的被破坏，只有那些不与自身蛋白结合的T细胞可以离开胸腺(成熟的T细胞)此后，这些成熟的细胞就在体内血液中循环，完成免疫功能，保护身体不受外来抗原损害

2、。目前，免疫细胞的自体耐受主要由否定选择算法来实现。在入侵检测领域里，使用否定选择算法生成检测器。1.2算法描述否定选择算法(如图3.1所示)可概括如下:(1)定义自体为一个长度为L的字符串的集合，S表示“自体”—一个受保护或者监督的集体。例如，S可以是一个文件片段或者是某个系统与过程的活动模式;(2)产生检测器集合R，每一个R中检测器与任何S中的字符串都不匹配;(3)通过不断地将R中的检测器与S比较来监控S的改变。采用部分匹配规则，两个字符串当且仅当至少在r个连续位上一样时才发生匹配，是一个被选定的合适的参数

3、，监督S变化。检测器与S连续匹配，如果任何检测器都匹配，则一定有变化发生。否定选择算法2.1r一连续位匹配规则r-连续位的匹配规则是指任意两个字符串，如果两个字符串中至少有连续r个对应位上的符号相同，就说这两个字符串匹配。即有任意两个字符串x和y，如果x和y至少有r个连续对应位上的符号相同，则有x和y连续r位匹配。例如:字符表{A，B，C，D，E}，x和y为定义于其上的任意2个字符串XCBACDEABYBDADCDEA其中，有3个连续位上的符号相同(见下划线部分)。当r≦3时，为x和y匹配。这种匹配规则可应用于

4、任意符号表上定义的字符串,最通用的符号表为{0，l}。在一连续位的匹配规则，用PM为任意两个等长随机字符串的匹配的概率，设如下参数:m:表示符号表所含的符号数目l:表示字符串所含符号的数目，即字符串的长度r:表示匹配中所要求的连续匹配位数，即匹配长度符号表中的m个符号是各不相同的、是互补的。对于字符串每一个位置上的符号，从符号表中选取符号与之匹配即相同的概率是1/m，而与之不匹配(即互补)的概率是(1一1/m)。当两个长度为Z的字符串进行比较时，如果至少有r连续对应位上的符号相同，则这两个串匹配。如果两个字符串

5、匹配，并且这种匹配是:从l长度字符串的最左端开始，有连续r个对应位取值相同，则匹配的概率为:如果两个字符串匹配，并且匹配的起始位置是从l长度字符串左边的第2位到第(l一r+1)位，那么在每次匹配成功的起始位置之前，总有不匹配发生时，其每次匹配成功的概率为:(m一1)/mXm一应当注意:该匹配概率是近似值。因为它仅包括了那些在每次匹配成功的起始位置之前，没有匹配发生的情况。而忽视了那些在每次匹配成功的起始位置之前，有匹配发生的情况。当使r足够大(即m一r<

6、个字符串多处发生匹配的可能性将减小。于是，两个字符串匹配的总概率可见，PM随m，r和l变化而变化。2.2检测能力2.3否定选择算法存在的问题使用否定选择算法产生的检测器覆盖异己空间越大说明检测器的检测能力也就越强。理想情况下，检测器的容量越大，则覆盖异己空间也就越广。但实际情况是，自体集合是一个相对较为有限的空间，而非自体集合多数情况下近似于一个无穷的空间，要完全覆盖异己空间就需要极其大量的检测器。而从实际应用的情况来看，有限的系统资源无法满足完全产生这些有效检测器的要求。故产生能覆盖整个非自体空间的检测器是不

7、现实的。同时，根据3.2.4结论2也为该观点提供了理论基础:有限的检测器可以保护大量的自体数据集。现在的问题是如何在检测器容量确定的情况下，尽可能多的覆盖异己空间。Forrest提出的否定选择算法中，使用r一连续位匹配规则产生的检测器会存在黑洞，使得覆盖异己空间变小。Forrest否定选择算法中全长串的:一连续位匹配规则会存在两类漏洞:交叉漏洞和限长漏洞。(1)限长漏洞限长漏洞是漏洞串h至少有一个r位窗口不在S，其它窗口能够和S匹配。例如:S={110010}，l=3，r=2，则h=101就是一个限长漏洞。因为

8、检测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，1