一种自适应优化算法在信息安全中的应用
摘 要:随着科技进步和计算机网络技术的飞速发展,网络“黑客”的攻击手段越来越先进,信息安全问题也越来越突出。为了有效保护信息传输的安全,提出一种基于自适应优化算法的信息安全检测技术,将具有自适应功能的优化算法应用于信息检测中,通过动态调整交叉概率和变异概率,利用多次迭代得出最优解,实现最优检测,最终达到提高检测的准确率和减少误报率的目的。
关键词:自适应;优化算法;信息安全;变异算法
中图分类号: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等人提出了一种根据适应度动态调整交叉概率pc和变异概率pm的自适应优化算法。在Srinivas等人提出的自适应优化算法中,交叉概率pc和变异概率pm按如下公式进行自适应调整[3-5]。
pc=k1(fmax-f′)fmax-favg,f′≥favg
k2,f′
pm=k3(fmax-f)fmax-f,f≥favg
k4,f
式中:fmax为种群中最大的适应度值;
favg为每代种群的平均适应度值;
f′为要交叉的两个个体中较大的适应度值;
f为要变异个体的适应度值;
k1,k2,k3,k4为取(0,1)区间的值。
其中,交叉概率pc和变异概率pm随适应度值的变化,如图1所示。
图1 自适应优化算法的交叉概率和变异概率
由式(1)和式(2)可知,当种群各个体适应度趋于一致或趋于局部最优时,使交叉概率pc和变异概率pm增加,当种群适应度比较分散时,使交叉概率pc和变异概率pm减小。同时,对于适应度值高于种群平均适应度值的个体,取较低的交叉概率pc和变异概率pm,使该解得以保护进入下一代;对于低于种群平均适应度值的个体,取较高的交叉概率pc和变异概率pm,使该解被淘汰。
根据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 交叉算子的选取
采用两点交叉算子,设Xt1=(x11,x12,…,x1k,…,x1n),Xt2=(x21,x22,…,x2k,…,x2n)的两个解群,在第i点至第j点实施两点交叉,产生Xt+11=(x11,…,x1i-1,x′i,…,x′j,x1j+1,…,x1n),Xt+12=(x21,…,x2i-1,x″i,…,x″j,x2j+1,…,x2n)。其中,向量Xt+11中元素x′k及向量Xt+12中元素x″k(i≤k≤j)通过x′k=αx1k+(1-α)x2k,x″k=αx2k+(1-α)x1k的组合产生,其中α∈(0,1),x1k,x2k分别为Xt1和Xt2的元素。
两点交叉算子能够以较高的概率产生出具有较大多样性的解,即能够以较高的概率产生出适应度更高的新解。
2.3.2 变异算子的选取
采用非均匀变异操作,在进行由X=(x1,x2,…,xk,…,xt)向X′=(x1,x2,…,
x′k,…,xt)的非均匀变异操作时,若变异点xk处的基因值取值范围为[Ukmin,Ukmax],则新的基因值xk可由式(3)确定:
x′k
=xk+Δ(t,Ukmin-vk),if random(0,1)=0
xk-Δ(t,vk-Ukmin),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 交叉概率和变异概率
在自适应优化算法中,交叉概率pc和变异概率pm按如下公式进行自适应调整。
pc=pc1-(pc1-pc2)(f′-favg)fmax-favg,
f′≥favg
pc1,f′
f≥favg
pc1,f
式中:fmax为种群中最大的适应度值;
favg为每代种群的平均适应度值;
f′为要交叉的两个个体中较大的适应度值;
f为要变异个体的适应度值;
pc1=0.9,pc2=0.6,pm1=0.1,pm2=0.001。
该算法的交叉概率pc和变异概率pm随适应度值的变化,如图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
(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]拉斯•克兰德.挑战黑客——网络安全的最终解决方案[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.
