免疫入侵检测多目标优化克隆选择算法研究

张凤斌，范学林，席 亮

(哈尔滨理工大学计算机科学与技术学院，黑龙江 哈尔滨 150080)

1 引言

在有线和无线网络中，免疫入侵检测系统凭借其自适应性和稳定的检测率得到广泛应用，其中检测器的迭代进化过程极为关键。克隆选择算法是训练成熟检测器的一种有效方法，其原理是类比父代和子代的累计亲和力选取优势样本[1]，但这会致使迭代后的成熟检测器高度重叠，影响进化效率。其主因在于，大量受交叉变异操作的检测器能检测出当代种群无法检测的抗原，却因为没有达到设定的累计匹配亲和力阈值，在迭代中被丢弃。显然，提高种群个体的累计亲和力平均值会提升种群检测范围，但该策略缺乏对检测器个体与所有抗原检测结果的统计和记录，使得大量筛选的优势个体存在检测半径相互包含冗余的问题，不利于训练的高效性。

随着对入侵检测理论的不断研究，机器学习和统计学习相关模型在该领域得到了良好的应用，Altwaijry[2]在一般的网络嗅探器基础上，引入了多个异常检测的贝叶斯分类器，用于计算TCP连接正常与攻击的概率，该算法判断同类型攻击较为精确，对多种类型的攻击则需多种分类器协作识别。Tian等人[3]通过统计操作系统中每个进程的系统调用次数和执行的概率构建了一种用于在线检测的马尔科夫入侵检测模型。在大数据量检测时，该模型具有较高的速度，然而对一些与正常行为相似度极高的行为易引发误报。文献[4]提出了拥有双分界面的一种新型支持向量机算法，在训练耗时方面只有标准支持向量机的四分之一，但需要对训练样本进行降噪处理。Elhag等人[5]将一类二值技术用于模糊遗传系统，通过得分矩阵实现FRBCSs检测器对抗原的识别，但检测结果一定程度上依赖规则集的设定。

上述检测方法经实验证实都具有较好的检测率，然而监测模型对抗原的判别严重依赖原始训练集的训练结果，面对检测数据中自体与非自体标准的不断更迭，和已出现误报的攻击行为，系统的自适应能力很差，造成系统检测率的鲁棒性较低，自我更新与纠错能力较弱。

免疫入侵检测模型属集合范畴，集合中个体具有较高的独立性，可及时根据网络中的自体与非自体规则对模型中的检测器和自体集进行更新。当前网络中的非自体被检测器判定是自体时，删除该检测器以及系统中与该非自体在空间上高重叠的自体样本；如识别当前网络中的自体为非自体时，移除该检测器，并把该自体纳入自体集中。定时在自体集中耐受生成新的成熟检测器，置换超过生命周期的成熟检测器和耐受失败的记忆检测器，使得系统具有良好的动态自适应性。然而进化过程中的检测器高重叠现象却因累计亲和力函数值策略不能得到很好的解决。本文将检测器的克隆进化过程抽象为求解多目标优化问题，优化了检测器种群迭代效率，提升了系统的检测率，当规则集发生变化时具有良好的动态自适应性。

2 相关工作

基于遗传理论的迭代算法具有良好的全局性和收敛性,Barani等人[6]通过融合小生境技术的蜂群算法训练经自体耐受的成熟检测器，使用蒙特卡罗积分法预测非自体被检测器覆盖的总量，根据该值确定检测器迭代次数。该免疫入侵检测模型很好地平衡了检测率和误报率之间的关系，但缺乏鲁棒性。多目标优化遗传算法大量应用于高维多目标函数极值最优解的搜索[7,8]。文献[9]提出将非线性数据线性化，并对数据进行特征选择，以构建多目标优化模型，实现对数据的线性分析，高速判断网络行为。Yu等人[10]提出了结合多目标优化理论的遗传算法，实现了对抗原的特征提取，在保持一定检测率的前提下，具有较高的检测效率。

本文根据抗原与抗体一对多的映射关系，提出了用于迭代训练检测器的多目标优化克隆选择算法MCSA (Multi-objective optimization-Clonal Selection Algorithm)。将种群的克隆进化过程转化为特殊的多目标优化模型。MCSA算法中，经克隆、交叉、变异、耐受后的种群中的每个成员将和所有抗原进行匹配，并以向量的方式记录检测器和所有抗原的检测结果。通过计算向量间的支配关系来得到非支配向量，非支配向量对应的成熟检测器将进入子代的记忆检测器集合。同时，受支配检测器经变异、耐受后，部分进入子代。最后，在子代中加入耐受成功的新的成熟检测器，以固定一定的种群规模。实验表明，迭代次数相同的情况下，相比传统克隆选择算法，MCSA使得种群拥有更大的检测范围和更低的误报率，加快了检测器的进化效率，提高了系统的检测率。

2.1 多目标优化理论基本概念

在实数集R中,n维决策向量X=(x1,x2,…,xn)T⊂Rn，m维目标向量Y={y1,y2,…,ym}⊂Rn。多目标函数如下：

Max(Y)=G(X)=(f1(X),f2(X),…fm(X))T,

(1)

G(X)为从目标到决策向量的转换函数。

定义1可行解：∀X∧∈X，且满足上述约束条件，则X∧为可行解。

定义2可行解集合：所有可行解的集合记做可行解集，用XP表示。

定义3pareto支配：{∀x,y∈Xp|fk(x)≥fk(y),k=1,2,…,m}∧{∃l∈{1,2,…,m}|fl(x)>fl(y)}，则x对于多个目标而言支配y，记做xy。

定义4pareto最优解:{∀X,X*∈XP|∃XX*}，则X*为pareto最优解，也被称作非支配解。

定义5pareto最优解集:S*={X*|∀X,X*∈XP;∃XX*}。

2.2 构建检测器抗原多目标优化模型

检测器和抗原通过实值编码,由l个特征表示。其中检测器X=〈x1,x2,x3,…,xl〉,抗原Y=〈y1,y2,y3,…,yl〉。把特征转化至[0,1]空间，则任意特征f∈[a,b]，f=(f-a)/(b-a)。耐受过程，候选检测器与自体抗原的欧氏距离大于匹配阈值Dd时，成功耐受，否则删除该检测器；检测阶段，如公式(1)所示，fk(X,Y)=1，则X判断Y为攻击行为。图1为m个非自体抗原与n个检测器的检测结果。将检测器X1、X2和所有非自体抗原的检测结果分别映射成向量α、β，当X1、α、X2、β满足定义3的条件时，即X1X2。那么，所有满足定义4条件的检测器，就形成了非支配的成熟检测器集合，该集合的检测范围可覆盖这n个检测器的检测范围。

Figure 1 Relationship of detector antigen matching

图1 检测器抗原匹配关系

2.3 MCSA中的交叉变异策略

相同特征之间的互换交叉以及单点特征的高频变异，使得种群在进化过程中的多样性不断提高。然而，在多目标问题中引用传统变异的方式，会引发解空间的最优解过于稠密，不利于种群多样性。为解决这一问题，文献[11]对变异算子加入了特殊的越界处理方法，用于最优解的迭代，相比在多目标问题中得到广泛应用的多项式变异[12]收敛性更优。因此，本文利用柯西变异结合越界处理策略对检测器进行变异。Ti为检测器Xi中的某一特征，公式(2)为柯西分布，公式(3)为参数σ的柯西变异过程。φ(0,σ)为以0为对称轴，参数为σ的柯西分布的随机数。公式(4)为越界处理过程，其中χ为离散型随机变量：

fc(x,σ)=σ/[π(σ2+x2)],-∞

(2)

di≤Ti≤hi,σ=1

(3)

(4)

3 算法与分析

3.1 MCSA迭代训练算法

输入：检测器种群规模N,父代种群Pt,子代种群Qt,训练数据集Strain(Snoself,Sself)，迭代次数t，迭代最大次数tmax。成熟检测器集Dma，候选检测器Dim，记忆检测器集Dmc，变异概率Pv，交叉概率Pc，检测器和所有非自体匹配后的记录向量Vectorset，受支配检测器集，数组p[],q[]。

输出:训练t代的检测种群Pt。

begin

Pt=∅，Qt=∅，t=1,Ddominated=∅;//初始化数据

produceDimtoleranceSself→Dma(|Dma|==N);/*耐受生成成熟检测器集合直至规模达到N*/

While(t≤tmax)

Pt=Dma;

if(|Pt|

do

Produce newDim;

newDimtoleranceSself→newDma;/*耐受生成成熟检测器*/

Pt=Pt+newDma;

While(|Pt|<=N) /*加入新耐受成功的成熟检测器直至达到种群规模*/

p[]=∅,q[]=∅;

p[]=Pt;//将Pt放入数组p[]中

q[]=Pt;//将Pt放入数组q[]中

for (i=1;i≤N;i++)

p[i].(Vectorset)=p[i] matchSnoself;/*存储匹配结果到对应检测器的Vectorset*/

for (i=1;i≤N;i++)

if(p[i]==∅)

continue;

for(j=1;j≤N;j++)

if(j==i||q[j]=∅)

continue;

if(p[i].(Vectorset)q[j].(Vectorset))/*判别检测器之间的支配关系*/

Ddominated=Ddominated∪q[j];

q[j]=∅;//将q[]中受支配检测器置空

p[j]=∅;//将p[]中受支配检测器置空

else if(!(p[i].(Vectorset)q[j].(Vectorset)))

continue;

if(t≠tmax)

Dmc=Pt-Ddominated;

Ddominated=clone(Ddominated);

newDdominated=variaion and cross (Ddominated);

[(newDdominated] toleranceSself→Dma;/*将交叉变异后的受支配检测器重新耐受*/

Dma=Dmc+Dma/*新耐受成功的检测器和记忆检测器一起作为下一代的成熟检测器*/

remove(Dma);//删除重复的检测器

t=t+1;

end;

3.2 算法分析

由MCSA算法的迭代流程可知，抗体的交叉变异操作，会使得抗体在受支配和非支配之间相互转化，为证明迭代进化具有收敛性，抽象克隆进化过程为马尔科夫状态模型，得出迭代稳定的种群存在非支配抗体的概率。以A(k)={A1(k),A2(k),…,An(k)}表示总量为n的第k代抗体集合A。φ(A)表示A中非支配抗体的总量，l为抗体的特征总量，δ()算子用来计算支配和非支配抗体在相同特征上取值不同的特征数量，D表示A(k)中的非支配抗体集。

证明A(k)不存在最优非支配抗体的概率:

根据贝叶斯公式有如下关系：

由克隆选择的性质知P{φ(A(k+1))=0|φ(A(k))≠0}=0。

所以P{φ(A(k+1))=0|φ(A(k))=0}≤1-ε<1。

经上述分析，MCSA算法迭代至收敛时，种群中存在非支配抗体的概率为1。

□

4 实验分析

4.1 数据处理及参数设置

Figure 2 Influence of matching threshold on the algorithm图2 匹配阈值对算法的影响

4.2 算法迭代效率分析

通过对比500个成熟检测器的迭代耗时、检测率、误报率这三个指标，考量了CSA和MCSA两种算法的特性，结果如表1所示。

鉴于较低的匹配阈值会使耐受生成的成熟检测器和自体在高维空间过重叠，较高的匹配阈值会使得迭代效果不明显，因此设定实验的匹配阈值为0.5。检测器种群经CSA算法克隆进化至150～190代时，DR稳定在30.1%左右，FR保持在0.60%左右，而经MCSA算法克隆进化至90～190代时，检测率保持在32.78%左右，误报率维持在0.50%左右。在一定的检测器基数和匹配阈值的前提下，由于MCSA算法存在计算非支配向量这一过程，使得其每20次的迭代耗时相比CSA较高，但却削减了迭代至稳定的总时间，提升了进化效率。

4.3 检测器匹配阈值分析

图2为不同阈值下，500个成熟检测器的检测率及误报率的变化过程。Dd以 0.5为起点，0.1为步长。根据表1的实验结果，分别设定MCSA和CSA的迭代次数为90和150。通过表1和图2可以发现，偏低的匹配阈值导致了检测器种群较低的检测范围，限制了克隆选择提高种群检测器率的作用，但也使得种群误报率较低。另一方面，数据采集的不确定性造成了训练集和测试集中的自体差异性较高，当匹配阈值设定较大时，由训练集自体耐受生成的检测种群易引发较高的误报率。所以，匹配阈值的确定对平衡系统检测率和误报率的关系极为重要。为计算合适的匹配阈值，转化不同阈值下的检测结果为约登指数，约登指数表示为检测率与误报率的差，约登指数与分类效果成正比。根据图2可知，经MCSA训练的检测器种群，系统约登指数的最大值为97.35%，DR为98.85%，FR为1.50%，Dd=2.5；经CSA训练的检测器种群其最大约登指数为93.71%,DR为97.21%，FR为3.50%，Dd=2.8。自体集的自适应更新策略和检测器的克隆进化过程以及较低的匹配阈值，使得检测系统的FR在Dd< 2.0以前，未因匹配阈值的递增发生较大变化，稳定一个较低的值。系统的FR在Dd≥2.0以后均有较为明显的变化，相比之下，AMINM的误报率略低。同等的匹配阈值条件，AMINM相比AINM始终具有较高的DR。当Dd为1.8时，两系统的FR相差0.06%，DR却相差0.146；在Dd为3时，DR仅差0.2%，FR却相差4.6%。其原因在于，CSA算法中,成熟检测器匹配抗原的累计亲和力值可以反映该抗体识别攻击的数量，但不能完全反映该个体相对所有抗原的检测能力。同理，根据激活阈值β筛选的记忆检测器种群也存在这一问题，导致该种群在高维空间依旧高重叠，不能有效保存迭代过程的优化成果，影响克隆选择的效率，导致AINM相对于AMINM在DR方面提升较为缓慢。检测过程，在一定检测器数量和固定的匹配阈值的环境下，相比CSA算法，MCSA算法使得记忆检测器得到了精简且检测面范围更大，由系统中已识别出的自体耐受的成熟检测器将更多，这对稳定误报率在一个较低的水平意义重大。

Figure 3 Effect of detector number on algorithm图3 抗体规模对算法的影响

4.4 检测器数量分析

为验证检测器数量对系统检测率的影响，分别选取AINM和AMINM的最佳匹配阈值和迭代次数进行了对比实验，结果如图3所示。系统的DR伴随检测器数量的增长逐步提高，并最终达到一个稳定的水平,DF并没有因为系统检测器基数的变化受到太大的影响，这也说明了匹配阈值对于控制误报率的重要作用。而在一定匹配阈值的情况下，过度增加系统检测器的基数，并不能对检测率和误报率带来绝对意义上的优化效果，反而还会降低克隆进化的效率。所以，适当的检测器数量无论对系统的检测效率还是迭代效率甚至是检测精度都具有重要意义。

5 结束语

传统克隆选择算法通过累计亲和力函数值选取优势个体，这一策略导致了检测器的高重叠。为解决这一问题，本文将克隆选择算法抽象为检测器与抗原的多目标优化问题，提出了MCSA算法。MCSA以向量的形式记录检测结果，根据该向量矩阵映射出Pareto非支配向量，以此得到当代种群中的非支配检测器，最终实现筛选优势个体。通过实验，实现了在不同阈值、不同种群数量的环境下，AMINM和AINM检测性能的对比。虽然在检测率和误报率这一指标上，MCSA的训练效果要优于CSA算法，但是MCSA每代的训练耗时依旧高于CSA。减小非支配检测器求解的时间复杂度，加大实验数据的规模，是未来需要进一步改善的工作。

[1] Yin Chun-yong,Ma Lu-yu,Feng Lu.Towards accurate intrusion detection based on improved clonal selection algorithm[J].Multimedia Tools & Applications,2015:1-14.

[2] Altwaijry H.Bayesian based intrusion detection system[J].Journal of King Saud University-Science,2012,24(1):1-6.

[3] Tian P R, Duan M, Sun C, et al.Intrusion detection based on system calls and homogeneous Markov chains[J].Journal of Systems Engineering and Electronics,2008,19(3):598-605.

[4] He Jun,Zheng Shi-hui.Intrusion detection model with twin support vector machines[J].Journal of Shanghai Jiaotong University (Science),2014,19(4): 448-454.

[5] Elhag S,Fernández A,Bawakid A,et al.On the combination of genetic fuzzy systems and pairwise learning for improving detection rates on intrusion detection systems[J].Expert Systems with Applications,2015,42(1):193-202.

[6] Barani F,Abadi M.BeeID: Intrusion detection in aodv-based manets using artificial bee colony and negative selection algorithms[J].The ISC International Journal of Information Security,2012,4(1):25-39.

[7] Liu Min, Zeng Wen-hua.Memory enhanced dynamic multi-objective evolutionary algorithm based on decomposition[J].Journal of Software,2013,24(7):1571-1588.(in Chinese)

[8] Wang Bo,Nie Xiao-wei.Multi-criteria mathematical programming based on network instrusion detection[J].Computer Research and Development,2015,52 (10): 2239-2246.(in Chinese)

[9] Badran K,Rockett P.Multi-class pattern classification using single,multi-dimensional feature-space feature extraction evolved by multi-objective genetic programming and its application to network intrusion detection[J].Genetic Programming and Evolvable Machines,2012,13(1): 33-63.

[10] Yu Yan, Huang Hao. An ensemble approach to intrusion detection based on improved multi-objective genetic algorithm [J].Journal of Software,2007,18(6):1369-1378.

[11] Wen Shi-hua,Zheng Jin-hua,Li Mi-qing.Comparison and research of mutation operator in multi-objective evolutionary algorithm [J].Computer Engineering and Applications,2009,45 (2): 74-78.(in Chinese)

[12] Deb K,Goyal M.A combined genetic adaptive search (GeneAS) for engineering design[J].Computer Science and Informatics,1996,26(4): 30-45.

[13] Yu Yan, Huang Hao.Feature selection using multi-objective genetic algorithms for intrusion detection [J].Computer Science,2007,34 (3): 197-200.(in Chinese)

[14] Li Tao. An immune based model for network monitoring[J].Chinese Journal of Computers,2006,29(9): 1515-1522.(in Chinese)

附中文参考文献：

[7] 刘敏,曾文华.记忆增强的动态多目标分解进化算法[J].软件学报,2013,24(7):1571-1588.

[8] 汪波,聂晓伟.基于多目标数学规划的网络入侵检测方法[J].计算机研究与发展,2015,52(10):2239-2246.

[11] 文诗华,郑金华,李密青.多目标进化算法中变异算子的比较与研究[J].计算机工程与应用，2009,45(2):74-78.

[13] 俞研,黄皓.面向入侵检测的基于多目标遗传算法的特征选择[J].计算机科学,2007,34(3): 197-200.

[14] 李涛.基于免疫的网络监控模型[J].计算机学报，2006,29(9):1515-1522.