一種自適應優化算法在信息安全中的應用

摘 要:隨著科技進步和計算機網絡技術的飛速發展，網絡“黑客”的攻擊手段越來越先進，信息安全問題也越來越突出。為了有效保護信息傳輸的安全，提出一種基于自適應優化算法的信息安全檢測技術，將具有自適應功能的優化算法應用于信息檢測中，通過動態調整交叉概率和變異概率，利用多次迭代得出最優解，實現最優檢測，最終達到提高檢測的準確率和減少誤報率的目的。

關鍵詞:自適應;優化算法;信息安全;變異算法

中圖分類號:TN918.91 文獻標識碼:A

文章編號:1004-373X(2010)03-044-03

Application of Self-adaptive Optimal Arithmetic in Information Security

YAO Changhong

(China Airborne Missile Academy，Luoyang，471009，China)

Abstract:Hackers master more and more cutting-edge attack means，therefore the issue of information security is becoming outstanding along with technological progress and rapid growth of computer Internet technology.For the sake of protecting the security of information transmission，the information security technique based on self-adaptive optimal arithmetic，which applies self-adaptive optimal arithmetic to information test is introduced.Through dynamically adjusting chiasm probability and aberrance probability，it realizes optimal test through making use of repetitious subrogation.Then the technique can increase veracity and reduce misinformation.

Keywords:self-adaptive;optimal arithmetic;information security;aberrance algorithm

0 引 言

計算機網絡不斷被非法入侵，重要情報資料被竊取，甚至造成網絡系統的癱瘓，給各個國家及眾多公司造成巨大的經濟損失，嚴重地危害到國家和地區的安全。對信息安全進行保護己經成為刻不容緩的重要課題。

當前計算機網絡正在各個領域迅速普及，整個社會對網絡的依賴程度越來越大，網絡已經成為社會和經濟發展的強大動力，其地位越來越重要。眾多的企業、組織、政府部門與機構都在組建和發展自己的網絡，并連接到Internet上，以充分共享、利用網絡的信息和資源。但伴隨著網絡的發展，也產生了各種各樣的問題，其中以安全問題尤為突出。網絡攻擊與入侵行為，對國家安全、經濟、社會生活造成了極大的威脅。目前，有超過120個國家己經或正在開發網絡攻擊技術，有些恐怖分子和極端分子甚至可以獲得對國防信息系統的控制，嚴重削弱一個國家對軍事力量的部署和維持能力 [1，2]。

通常的信息安全檢測系統存在漏報率和誤報率高，實時性差，訓練數據代價高，自適應性差，可擴展性和可移植性差等問題。優化算法可以用來產生檢測系統的規則，用來區分正常的連接和異常的連接。然而簡單的優化算法搜索能力不強，收斂速度較慢，而且算法的穩定性不高，不能保證收斂于全局最優解。針對以上問題，本文設計了一種基于自適應優化算法的信息安全檢測技術。

1 自適應優化算法

1994年Srinivas等人提出了一種根據適應度動態調整交叉概率pc和變異概率pm的自適應優化算法。在Srinivas等人提出的自適應優化算法中，交叉概率pc和變異概率pm按如下公式進行自適應調整[3-5]。

pc=k1(fmax-f′)fmax-favg，f′≥favg

k2，f′

(1)

pm=k3(fmax-f)fmax-f，f≥favg

k4，f

(2)

式中:fmax為種群中最大的適應度值;

favg為每代種群的平均適應度值;

f′為要交叉的兩個個體中較大的適應度值;

f為要變異個體的適應度值;

k1，k2，k3，k4為取(0，1)區間的值。

其中，交叉概率pc和變異概率pm隨適應度值的變化，如圖1所示。

圖1 自適應優化算法的交叉概率和變異概率

由式(1)和式(2)可知，當種群各個體適應度趨于一致或趨于局部最優時，使交叉概率pc和變異概率pm增加，當種群適應度比較分散時，使交叉概率pc和變異概率pm減小。同時，對于適應度值高于種群平均適應度值的個體，取較低的交叉概率pc和變異概率pm，使該解得以保護進入下一代;對于低于種群平均適應度值的個體，取較高的交叉概率pc和變異概率pm，使該解被淘汰。

根據Srinivas等提出的自適應優化算法，交叉概率和變異概率隨著個體的適應度在種群平均適應度和最大適應度之間進行線性調整。當適應度越接近最大適應度時，交叉概率和變異概率越小;當適應度值接近或等于最大適應度值的個體時，交叉概率和變異概率接近或等于零[6]。

2 設計與實現

2.1 基本思想

按照一定的規則生成初始解群，然后從這些代表問題的可能潛在解的初始解群出發，運用改進的交叉概率和變異概率，挑選適應度強的個體進行交叉和變異，以期發現適應度更佳的個體，如此一代代的演化，得到一個最優個體，將其經過解碼，該最優個體的編碼則對應問題的最優解或近似最優解[7-10]。

算法的偽代碼如下:

(1) 隨機初試化初試種群，n=1，Gen=0，s=0，N為種群大小;

(2) if(Gen=max)

{退出;}

else

{

if(n

{

復制s到種群中;

計算適應度;

淘汰適應度低的個體;

}

else

{

應用優化算法中的交叉獲得新染色體加入該種群;

應用優化算法中的變異獲得新染色體加入該種群;

}

Gen=Gen+1;

}

2.2 編碼

采用實數編碼的形式。實數編碼(浮點數編碼)不需要對待優化參數進行編碼及譯碼操作，它采用直接把待優化參數連成一個實數向量的方式。實數編碼的精度高，適合于復雜大空間的搜索。

2.3 選擇算子

采用輪盤選擇法，其方法是計算種群中所有染色體適應度值的總和[S]，然后在[0，S]的搜索空間中隨機產生一個R，選擇一個適應度值大于R并最靠近R的染色體。

2.3.1 交叉算子的選取

采用兩點交叉算子，設Xt1=(x11，x12，…，x1k，…，x1n)，Xt2=(x21，x22，…，x2k，…，x2n)的兩個解群，在第i點至第j點實施兩點交叉，產生Xt+11=(x11，…，x1i-1，x′i，…，x′j，x1j+1，…，x1n)，Xt+12=(x21，…，x2i-1，x″i，…，x″j，x2j+1，…，x2n)。其中，向量Xt+11中元素x′k及向量Xt+12中元素x″k(i≤k≤j)通過x′k=αx1k+(1-α)x2k，x″k=αx2k+(1-α)x1k的組合產生，其中α∈(0，1)，x1k，x2k分別為Xt1和Xt2的元素。

兩點交叉算子能夠以較高的概率產生出具有較大多樣性的解，即能夠以較高的概率產生出適應度更高的新解。

2.3.2 變異算子的選取

采用非均勻變異操作，在進行由X=(x1，x2，…，xk，…，xt)向X′=(x1，x2，…，

x′k，…，xt)的非均勻變異操作時，若變異點xk處的基因值取值范圍為[Ukmin，Ukmax]，則新的基因值xk可由式(3)確定:

x′k

=xk+Δ(t，Ukmin-vk)，if random(0，1)=0

xk-Δ(t，vk-Ukmin)，if random(0，1)=1

(3)

其中:Δ(t，y)是在[0，y]范圍內符合非均勻分布的隨機數，其表達式為:

Δ(t，y)=y[1-r(1-t/T)b]

(4)

式中:t為種群進化代數;

r為[0，1]間符合均勻分布的隨機數;

T為最大進化代數;

b為系統參數(一般取值為2)。

2.4 交叉概率和變異概率

在自適應優化算法中，交叉概率pc和變異概率pm按如下公式進行自適應調整。

pc=pc1-(pc1-pc2)(f′-favg)fmax-favg，

f′≥favg

pc1，f′

pm=pm1-(pm1-pm2)(fmax-f)fmax-favg，

f≥favg

pc1，f

(6)

式中:fmax為種群中最大的適應度值;

favg為每代種群的平均適應度值;

f′為要交叉的兩個個體中較大的適應度值;

f為要變異個體的適應度值;

pc1=0.9，pc2=0.6，pm1=0.1，pm2=0.001。

該算法的交叉概率pc和變異概率pm隨適應度值的變化，如圖2所示。

圖2 自適應的交叉概率與變異概率

自適應優化算法在標準優化算法的基礎上運用了最優保存策略、自適應理論，只改變交叉算子和變異算子，未改變標準優化算法中有限狀態的齊次馬爾可夫鏈;在經過固定代數的優化操作后，且保留了最優個體，且保證是以概率1收斂的，即改進的自適應優化算法可以以概率1收斂到全局最優。

3 實驗與分析

實驗環境:一臺PC機，操作系統為Windows XP，開發工具為Microsoft Visual Studio.Net 2003，開發語言為C++和J#。其中，C++用于網絡特征提取的計算;J#用于入侵檢測系統的實現。

3.1 實驗流程

(1) 隨機產生初始解群，n=1，初始化Gen=0，s=0。其中，Gen表示優化算法迭代次數;變量s表示保存的全局最優個體;

(2) 判斷Gen是否達到確定的最大進化迭代數max，若相等跳到(10)，否則進行下一步;

(3) 復制變量s到種群;

(4) 計算解群的適應度值;

(5) 淘汰適應度低的個體;

(6) 判斷n與N(本次實驗使用的解群值)的關系，若n

(7) 根據適應度值選擇兩個染色體，按照預先定義好的交叉策略產生新的下一代;

(8) 根據適應度值選擇一個染色體，按照預先定義好的變異策略產生新的下一代;

(9) Gen=Gen+1;

(10) 結束。

3.2 實驗結果及分析

在解群大小為100，進化代數為500，得到數據如表1所示。

由普通算法和自適應優化算法的實驗結果對照可以看出:在二者解群大小、迭代次數相同的情況下，后者的DR和FPR有一定程度的提高。隨著解群數和迭代

次數的增大，普通遺傳算法和自適應優化算法的檢測準確率都有所提高，同時檢測誤報率有一定程度的減小。

表1 進化500代得到的結果

攻擊類型

普通算法 /%自適應優化算法 /%

檢測率誤報率檢測率誤報率

DoS98.950.0499.120.03

Probe98.790.4298.960.38

R2L98.7611.1298.838.91

U2R98.930.1499.020.11

4 結 語

采用實數編碼的形式，直接把帶優化參數連成一個實數向量，實現復雜大空間的搜索。通過動態調整交叉概率和變異概率，利用多次迭代得出最優解，實現最優檢測，最終達到提高檢測的準確率，減少誤報率的目的。該算法將具有自適應功能的優化算法應用到信息安全檢測技術中，保證存在收斂于全局的最優解，實現了優化算法與信息安全檢測技術的有機結合，提高了信息安全檢測的準確率，適用于入侵攻擊型檢測與防范。

參考文獻

[1]拉斯#8226;克蘭德.挑戰黑客——網絡安全的最終解決方案[M].陳永劍，譯.北京:電子工業出版社，2000.

[2]胡道元，閔京.網絡安全[M].北京:清華大學出版社，2004.

[3]Dipankar Dasgupta，Fabio A Genzalez.An Intelligeni Deeison Support System for Intrusion Detection and Response[A].MMM-ACNS[C].2001:1-24.

[4]Taeshik Shon，Jungtaek Seo.An Intrusion Detection Model[Z].NetSTAT，2003.

[5]Dong Seong Kim.Fusions of GA and SVM for Anomaly Detection in Intrusion Detection System[M].Amsterdam:IOS Press，2004.

[6]Ludov M E.A Genetic Algorithm as an Altemative Tool for Security Audio Trails Analysis[A].GASSATA[C].1996.

[7]任子武，傘冶.自適應遺傳算法的改進及在系統辨識中應用研究[J].系統仿真學報，2006，18(1):41-46.

[8]Jai Balasubramaniyan，Jose Omar Garcia-Fernandez，David Isacoff，et al.An Architecture for Intrusion Detection using Autonomous Agents[J].Purdue University:Department of Computer Sciences，1998.

[9]Asaka M，Okazawa S，Taguchi A，et al.A Method of Tracing Intruders by Use of Mobile Agents[A].INET′99[C].1999.

[10]Debar H，Dacier M，Wespi A.A Revised Taxonomy for Intrusion-Detection System[A].Annals of Telecommunications[C].2000.