否定选择算法.ppt

文档介绍：否定选择算法
本讲稿第一页，共三十六页
否定选择算法
算法功能
1994年，Forrest，Perelson等人提出的否定选择算法成功的模拟了免疫系统识别自我和非
我的免疫耐受过程。这种识别能力源于T细胞(免 限长漏洞是漏洞串h至少有一个r位窗口不在S，其它窗口能够和S匹配。
例如:S={110010}，l=3，r=2，则h=101就是一个限长漏洞。因为检测h的检测串必须
以10开头或者以01结尾，但是任何这样的检测串都会与自体匹配而不能生成。
(2)交叉漏洞
交叉漏洞是一个串h不在自我集S中，h中的所有窗口与S相邻窗口交叉。
本讲稿第八页，共三十六页
否定选择算法存在的问题
下面用有向非循环图DAG来描述这个漏洞。设s={0002，1011}，l=4，r二2，则相应的DAG图()
从左端结点出发，能够产生串{0001，0011，1001，1011，1000}，其中{0011，1001}是交叉漏洞。
本讲稿第九页，共三十六页

黑洞产生的原因
尽管希望构造一个完整的有效检测器集合，但是总会有一些Nonself字符串无法被检测到，这些Nonself串就称为“黑洞”。，在形态空间中，self集与Nonself集的界面往往是不规则的，而匹配闽值是固定的，因此有一些Nonself不能被任何检测器检测。
黑洞存在于任何匹配规则中，事实上，在生物免疫系统中，也存在黑洞问题，而且病原体总在向黑洞中进化，使其更难被检测到。
本讲稿第十页，共三十六页

对于给定字符串长度L和匹配闭值r下带有固定匹配率的r连续位匹配算法不可避免地会
出现这样的检测黑洞。对于固定不变的Self集合，不同“形状”的检测器可以覆盖不同的
Nonself集，产生不同的检测黑洞，如果能将不同“形状”的检测器共同作用，那么必然可以
减少黑洞的存在。
本讲稿第十一页，共三十六页

在描述算法之前首先给出以下几个定义。
:在长度为L的字符串中，只对r个连续位置进行定义，其它l-r个位置的字符可以任意取值，这样的字符串称为字符串r模板。
:是指从字符串的第i个位置开始有确定的定义，则该模板是第i模板。
:是指从字符串的第j+l个位置开始没有确定的定义，则该模板是第j尾模板。
例如，*011***就是一个长度为8的字符串的3模板，同时也是一个第2头模板和第4尾模板。
:如果一个模板c，，其连续:个位置与字符串e的对应位置的字符相同，则称c，和e匹配。例如，*011***和1011010。
判定c是否为漏洞及生成有效检测器的算法:
(1)寻找c的字符串r模板，并设其为第i头模板，记为:Ci，使其与C匹配，但不与集合A的任
何元素匹配，同时根据r和i找到cj。如果存在这样的模板则执行第2步;否则认为是漏洞，
本讲稿第十二页，共三十六页

本讲稿第十三页，共三十六页
漏洞的判定算法
本讲稿第十四页，共三十六页

本讲稿第十五页，共三十六页
举例说明:
设模式的长度L=10，有“自体”模式串集合为A={11111100，10001111l，1100110100，0010010011。设“非自体”模式串e=0010110100，匹配长度r=3。
利用上述算法判定字符串c是否是漏洞，。首先，构造一个字符串r模板Ci=**101*****，然后如图进行搜索，则可以看到**10101010就是一个有效的检测器，因此可以说字符串c不是漏洞。
本讲稿第十六页，共三十六页

本讲稿第十七页，共三十六页

该模型分为检测器生成和检测器识别两个模块。。检测器生成模块采用否定选择算法来生成，但将算法中采用的rcb匹配规则用r-字符块匹配规则替换。首先，选择匹配阂值R，设置T检测器容量，利用改进的否定选择算法生成T检测器;其次，选择匹配闭值R1，使得R1<R，设置B检测器容量，利用改进的否定选择算法生成B检测器。
检测器识别模块采用B、T双检测器协同识别，匹配规则仍为r一字符块匹配规则。如图
本讲稿第十八页，共三十六页
本讲稿第十九页，共三十六页
本讲稿第二十页，共三十六页
本讲稿第二十一页，共三十六页
本讲稿第二十二页，共三十六页