一種分段檢測器集合生成算法的研究與實現

張小梅

（蘭州資源環境職業技術學院 信息管理系，甘肅 蘭州 730021）

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

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

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

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

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

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

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

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

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

步驟（1）：推導遞歸公式，計算候選檢測器C的規模

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

①i=l-r+1

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

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

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

（3）循環，重復 l-r+1 次。

①計算2r個字符串s的右實現Ci[s]。

循環結束后，C1[.]的右實現就是一個所有位均被確定且長度為l的字符串。因此，由r位字符串s開始的未被S匹配的長度為l的字符串的總數是個C1[s]。于是得到未被匹配的字符串數目為：

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

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

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

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

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

3 算法在實際工程中的應用

嘗試將本文的研究內容應于實際的工程。利用本文算法開發出一套故障診斷在線檢測監測系統。以YVP系列45 kW異步電機為實驗對象，對正常電機和三種故障電機（電機輸出軸失衡、電機軸承噪音大、電機轉子動偏心）進行訓練學習。

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

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

（3）將字符串各位上的數值范圍變換到區間0～1范圍內，并放大區間至 0～100；

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

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

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

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

表1 實驗檢測結果

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

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

[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.