摘  要： 分析了目前入侵检测系统运行机制和不足，提出了一种基于粗糙集的遗传算法，通过粗糙集属性精简遗传算法种群，并在变异操作中将优异个体朝重要属性加速变异，降低算法时空复杂度。通过实验验证，该算法收敛速度快，检测率高，能很好地应用于目前入侵检测系统之中。
关键词： 入侵检测；粗糙集；遗传算法；属性

    随着信息技术和网络的发展及应用，安全问题日益突出。入侵检测系统作为继防火墙后第二道安全防线，已成为保障网络安全的重要核心技术[1]。传统基于聚类的检测方法对数据输入顺序敏感，需要事先指定聚类数目等，造成聚类结果不理想，难以形成入侵特征，并且收敛速度慢，检测率不高。本文提出一种基于粗糙集的遗传算法并应用于入侵检测系统之中，通过粗糙集属性精简运算，降低算法时空复杂度。
1 入侵检测系统及其分类
1.1 入侵检测系统
    入侵检测系统是一种主动防御体系，它从计算机系统或网络环境中采集分析数据，通过检测引擎判断可疑攻击和异常事件，在计算机网络和系统受到危害之前拦截特征行为攻击[2]。系统遭受入侵后，IDS能将收集到的入侵行为和相关信息纳入知识库，通过主动学习方式避免重复或类似攻击，有效弥补防火墙被动防御的不足。
1.2 入侵检测分类
    入侵检测系统根据检测技术可以为分特征检测和异常检两类。特征检测是通过监视特定活动并与预先所设置的模式进行匹配来检测入侵[2]。这种利用特征库检测已知入侵行为的方法检测率高，速度快，并且对检测结果有明确的处理参照，但是不能检测未知攻击，很难将具体入侵手段抽象成知识特征。异常检测是基于系统或用户的正常行为模式检测入侵。该方法首先建立用户正常行为模式，当系统运行时将实时行为与正常行为模式进行匹配，一旦发生显著偏离即认为是入侵[2]。异常检测方式与系统环境无关，通用性较好，可以检测未知攻击和潜在威胁，但需要对每个户行为作全面描述，兼之个体行为的不确定性和独特性导致算法复杂，检测速度缓慢，漏报、误报率较高。
2 粗糙集理论
    粗糙集理论是处理不精确、不确定和不完整数据的数学理论，能够对不一致、不完整、不完善信息提炼内在特征，揭示隐含规律。
    粗糙集理论可以对决策表的属性进行约简，以便提高分类性能，获取潜在规则。对于任意决策表，不是每个属性对分类决策表的分类能力都有效，因此，在决策表分类能力不变的情况下，删掉冗余的条件或者决策属性，可以得到相对简单、易理解、易操作的决策表[3]。通过粗糙集理论对决策表属性进行约简，有利于过滤典型分类属性，形成新的决策表。通过约简决策表中的无关属性可以有效降低计算的时空复杂度，加速算法收敛。粗糙集理论如下。

3 遗传算法
    遗传算法GA（Genetic Algorithms）源于达尔文的进化论和孟德尔、摩根的遗传学理论，由美国John Holland教授于20世纪60年代末提出，模拟生物遗传机制“适者生存、优胜劣汰”。遗传算法操作对象是一群二进制串，称为染色体或种群，每个染色体都对应于问题的一个解。从初始种群出发，采用基于适应度比例的选择策略在当前种群中选择个体，通过交叉选择和变异操作产生新一代适应度更高的染色体，重复上述繁衍进化过程直到收敛到一个最合适的染色体上，从而找出问题的最优解。遗传算法拥有卓越的智能学习效率和自适应性，近年来应用于故障诊断、行为仿真和入侵检测等领域。
    决定遗传算法性能的3个参数分别为群体大小pop、交叉概率pc和变异概率pm。群体大小pop太小时难以找出最优解，太大则增加收敛时间；交叉概率pc太小时难以向前搜索，太大则容易破坏高适应值的结构；变异概率pm太小难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。
4 一种基于粗糙集遗传算法
    粗糙集理论和遗传算法各有优势。粗糙集适用于主动学习模式，通过约简高维数据属性维数降低算法时空复杂度。而遗传算法处理数据量不大时具有良好的收敛性和鲁棒性，但在处理海量数据时，特别是当处理高维数据时，参数难以界定，易出现染色体的变异交叉操作使得算法经高次迭代繁衍仍无法收敛的问题。
    本文将粗糙集约简原理与遗传算法进行整合，通过自适应学习方式为入侵检测系统提供行为特征。基本思想是通过粗糙集约简策略先过滤数据流量的无关属性，然后对处理后数据采用结合邻域思想进行分类，为遗传算法初始化种群，并保证筛选样本的稳定性和典型性，避免遗传算法处理数据量过大难以收敛的问题，最后由遗传算法迭代完成入侵行为特征的提炼和描述。
4.1 算法思想和流程
    粗糙集的属性约简原理适合于处理精确数据，进行数据知识分类与获取，同时对决策分析进行辅助。经过粗糙集属性约简后的系统，属性的减少降低了计算的复杂性，但仍能够保持相同的决策要求和效果。遗传算法对数据特征进行选择和优化建立在选择合适的适应度函数以及合理进行选择、交叉和变异的基础上。
    另外在遗传算法中，交叉变异算子作用是将群体中优良个体遗传到下一代，加速算法的收敛速度，并增加和维持群体多样性，以免陷入局部最优解的问题。但是传统算法中，交叉变异算子以一个极小概率随机改变染色体某些字位，随意性和任意性影响算法的收敛速度。本文再次利用粗糙集约简属性，将优异个体朝重要属性

    新算法通过粗糙集理论约简属性，一方面为遗传算法提供初始化种群，减少训练时间；另一方面可避免随机变异造成的缓慢收敛，减少算法时空复杂度，随着样本的增多，新算法在训练时间上更具优势。在检测精度和检测率方面，新算法有效去除无用样本和冗余属性，检测更为方便快捷，检测精度和检测率都有不错表现。
5.3 个体适应度和迭代次数测试
    新算法个体适应度明显优于其余两种算法。新算法利用粗糙集约简属性，将优异个体朝重要属性加速变异，并将其基因繁衍给下一代个体，使得个体适应度更高，新算法在第640次迭代已趋于收敛，如图3所示。而其余两种算法由于变异的随机性和任意性，适应度不高，分别在经760次和740次迭代才趋于收敛。

    本文在研究粗糙集和遗传算法的理论基础上，提出一种基于粗糙集的遗传算法，通过粗糙集属性精简遗传算法种群，并在变异操作中将优异个体朝重要属性加速变异，降低算法时空复杂度。通过算法对比和实验分析，本文提出的新算法在提高网络入侵检测速度和准确率方面是有效的、可靠的和可行的，为网络安全信息建设提供强有力的保障。
参考文献
[1] HOFMEYR S A， FORREST S. Architecture for an artificial immune system[J]. Evolutionary Computation Journal， 2000，8（4）：443-473.
[2] TSUI J B. Fundamentals of global positioning system receivers：a software approach[M]. New York： Wiley， 2000.
[3] HOFMEYR S， FORREST S. Architecture for an artificial immune system[J]. Evolutionary Computation， 2000，8（4）：443-473.
[4] TARAKANOV A， DASGUPTA D. A formal model of an artificial immune system[J]. BioSystems， 2000，55（55）：151-158.
[5] BEHDINAN N A K， FAWAZ Z. Applicability and viability of a GA based finite element analysis architecture for structural design optimization[J]. Computers and Structures， 2003，81（22-23）：2259-2271 .
[6] MIDDLEMISS M， DICK G. Feature selection of intrusion detection data using a hybrid genetic algorithm/KNN approach[C]. Design and Application of Hybrid Intelligent Systems， IOS Press Amsterdam，2003：519-527.
[7] KWON Y， KWON S， JIN S， et al. Convergence enhanced genetic algorithm with successive zooming method for solving continuousoptimization problems[J]. Computers and Structures， 2003， 81 （17） ：1715-1725 .  
[8] HUSSEIN O，SAADAWI T. Ant routing algorithm for mobile ad-hoc networks（ARAMA）[C]. Proceedings of the 2003 IEEE International Conference on Performance， Computing，and Communications， 2003：281-290.
[9] ONDREJ HRSTKA， ANNA KUCEROVA. Improvements of real coded genetic algorithms based on differential operators preventing premature convergence[J]. Advances in Engineering Software， 2004（35）：237-246.
[10] KABREDE H， HENTSCHKE R. Improved genetic algorithm for global optimization and its application to sodium chloride clusters[J]. Journal of Physical Chemistry B， 2002， 106 （39） ：10089-10095 .
[11] HEISSENB U M， BRAUN T. Ants based routing in large scale mobile ad-hoc networks[C]. Proceedings of the 13th ITG/GI-Fachta-gung Kommunikation Inverteilten System（KiVS2003）， 2003：181-190 .
[12] TIMMIS J， NEAL M， HUNT J. An artificial immune system for data analysis[J]. BioSystems， 2000，55，（55）：143-150.