張小梅

（蘭州資源環(huán)境職業(yè)技術(shù)學(xué)院 信息管理系，甘肅 蘭州 730021）

陰性選擇算法是Forrest等人研究出來的應(yīng)用于計算機安全防護的檢測算法[1]，其用于故障檢測最大的優(yōu)勢是用有限數(shù)量的檢測器檢測無限種類的故障[2-5]。但這些算法都要檢查抗原中長度超過匹配閾值的所有子串是否在檢測器中出現(xiàn)，在都未出現(xiàn)的情況下，才能夠判斷抗原合法，由此導(dǎo)致檢測效率較低。國內(nèi)的一些否定選擇算法，如參考文獻[6-7]的研究也主要用于這一方面，缺乏對否定選擇算法檢測效率的研究。

本文深入研究了傳統(tǒng)否定算法的缺點及其產(chǎn)生的原因，提出了一種新的分段選擇檢測器生成算法并加以實現(xiàn)，克服了現(xiàn)有方法的不足。

1 典型的否定選擇算法研究

設(shè)l表示自體字符串的長度，m表示字符串中使用的符號數(shù)目，則對于兩個連續(xù)r個位匹配的隨機字符串，其發(fā)生匹配的概率為：

設(shè)Ns表示自體集的數(shù)目；NR0表示候選檢測器的數(shù)目；NR表示實際使用檢測器數(shù)目；Pf表示檢測失敗的概率，則：

在 式（5）中 ，當(dāng) r≤l≤2r 時，T（l）=ml-ml-r（l-r）l-r-1；當(dāng) l>2r時，T（l）=2T（l-1）-T（l-r-1），這是一個遞歸定義。

因此，對于給定的漏檢率，為了能夠覆蓋所能檢測到的“非我”空間，需要：

2 基于否定選擇的快速檢測器生成算法

當(dāng)否定選擇算法采用r連續(xù)位匹配規(guī)則時，可以考慮對線性時間算法分段實現(xiàn)的方法進行：先推導(dǎo)遞歸公式，然后利用有限的遞歸運算解決那些不被S中字符串匹配的循環(huán)計數(shù)問題，以此計算出候選檢測器C的規(guī)模，最后利用遞歸求解的序號，隨機生成檢測器。于是，檢測器集合生成算法描述如下：

步驟（1）：推導(dǎo)遞歸公式，計算候選檢測器C的規(guī)模

（1）規(guī)定 Ci[s]為模板 Ti，s的右實現(xiàn)中所有與 s未匹配的字符串總數(shù)。其中，字符串s的長度為r。根據(jù)i的值分情況處理：

①i=l-r+1

此種情況下，Ti，s由 l-r個未確定的位和連續(xù)的 r個確定的位組成，其中，l-r個未確定的位在左邊，r個確定的位緊跟在l-r個未確定位的后邊，于是，模板的右實現(xiàn)就是該模板本身。由此得到Cl-r+1[s]的值為：

此種情況下，找出i+1位置開始的未被匹配的右實現(xiàn)的數(shù)量，即可求出模板的未被匹配右實現(xiàn)數(shù)量。當(dāng)Ti，s與S中的位串相匹配時，Ci[s]=0；不匹配時，則在 Ti，s的 r連續(xù)位后附加1或0，于是，求模板的未被匹配的右實現(xiàn)數(shù)量，就變成了求s←.m的右實現(xiàn)數(shù)量。于是得到如下遞歸公式：

（2）對未匹配的空間，根據(jù) r位字符串 s進行分割，這一過程記作C1[.]。C1[s]代表每個分隔空間的大小。對從s開始的所有未被匹配的字符串，在字符串s后的相應(yīng)位上附加 1或 0，記作 C[s→.m]。 同樣地，C2[.]可看作是對未被匹配空間的進一步分割。以此類推，從C3[.]到Cl-r+1[.]進行更加詳細地分割。經(jīng)過Cl-r+1[.]分割后，每個分割便是一個長度為l的字符串。

（3）循環(huán)，重復(fù) l-r+1 次。

①計算2r個字符串s的右實現(xiàn)Ci[s]。

循環(huán)結(jié)束后，C1[.]的右實現(xiàn)就是一個所有位均被確定且長度為l的字符串。因此，由r位字符串s開始的未被S匹配的長度為l的字符串的總數(shù)是個C1[s]。于是得到未被匹配的字符串?dāng)?shù)目為：

步驟（2）：生成未被匹配的檢測器集合

（1）給每個未被匹配的字符串分配1…sum序號。

（2）根據(jù)分配的序號，查找生成相應(yīng)的字符串。生成相應(yīng)的未被S匹配的字符串的步驟如下：

以此類推，形成了一個完整的字符串s1。

該算法需要一個（l-r）×2r維的數(shù)組，用來存放兩個字符串可能r連續(xù)位匹配的所有情形。因此，它的空間復(fù)雜度為：O（2r（l-r）2），時間復(fù) 雜度為：O（2r（l-r））+O（Ns（l-r））+O（NRl）。

3 算法在實際工程中的應(yīng)用

嘗試將本文的研究內(nèi)容應(yīng)于實際的工程。利用本文算法開發(fā)出一套故障診斷在線檢測監(jiān)測系統(tǒng)。以YVP系列45 kW異步電機為實驗對象，對正常電機和三種故障電機（電機輸出軸失衡、電機軸承噪音大、電機轉(zhuǎn)子動偏心）進行訓(xùn)練學(xué)習(xí)。

（1）采集各種工況下的電機振動信號，消噪并進行特征提??；

（2）將反映信號特征矢量數(shù)據(jù)歸一化處理，組成字符串，長度為 6；

（3）將字符串各位上的數(shù)值范圍變換到區(qū)間0～1范圍內(nèi)，并放大區(qū)間至 0～100；

（4）將區(qū)間 0～100劃分為 60個小區(qū)間，并按從小到大的順序依次編號為 0，1，2…59；

（5）將相應(yīng)的數(shù)據(jù)進行二進制編碼，結(jié)合自體集生成方法，對應(yīng)的子空間分別由 3 600，4 800，6 000，10 000個自體數(shù)據(jù)串組成。于是，整個自體空間的自體數(shù)據(jù)串為24 400個。

采用3個連續(xù)位匹配方法，假定檢測器未檢測到異常的概率為5%，即檢測的準(zhǔn)確率為95%，那么，由式（4）可知，只要生成73 096個抗體字符串即可達到要求。

通過對表1所列的差速器樣本的檢測，得到實驗檢測數(shù)據(jù)。

表1 實驗檢測結(jié)果

該算法的檢測準(zhǔn)確率高于90%，雖然未達到預(yù)先設(shè)定的95%的檢測率（這是由于“孔洞”[2]問題導(dǎo)致的），但是已經(jīng)滿足了故障在線檢測問題的需求。而且，該算法在生成檢測器集合時，所花費的時間為2分42秒，而傳統(tǒng)否定算法則需要5分33秒，可見，改進后的算法的時間性能提高顯著。

論文將檢測器集合的生成分段進行，并對算法的性能進行了驗證。實驗結(jié)果表明，本文的檢測器生成算法的匹配速度更快，且能夠有效地提高檢測效率，減小漏報率與誤報率，具有實際的工程應(yīng)用價值，為進一步研究入侵檢測系統(tǒng)提供了新的算法依據(jù)。

[1]ROEKE A J， DEMARA R F.Confidant： Collaborative ObjeetNotifieation Framework forInsiderDefense using AutonomousNetwork Transactions.AutonomousAgentsand Multi-Agent System[J].2006（1）.

[2]FORREST S， PERELSON A， A LLEN L， et al.Selfnonself discrim ination in a computer[C].In Proceedings IEEE Symposium on Research in Security and Privacy，Los A lan itos，CA，1994，IEEE Computer Society Press.

[3]FORREST S，HOFMEYR S A.Engineeringanimmune system[J].Graft，2001（4）：5-9.

[4]BALTHROP J， FORREST S， GLICKMAN M R.Revisting L ISYS：parameters and normal behavior[C].In Procceding of the 2002 Congress on Evolutionary Computation CEC 2002.

[5]FAMER J D， PACKARD N H， PERELSON A S.The immune system， adaptation， and machine learning[J].Physical D，1996.

[6]ZHANG H， WU L F， ZHANG Y S， et al.An algorithm of r-adjustable negative selection algorithm and its simulation analysis[J]. Chinese Journal of Computers， 2005， 28（10）：1614-1619（in Chinese with English abstract）

[7]SMITH R， FORREST S.Searching for diverse， cooperative populations with genetic algorithm[J].Evolutionary Computation，1993.