基于数据挖掘和特征选择的入侵检测模型

1、28卷 第 8期 2011年 8月微 电 子 学 与 计 算 机MICROELECTRONICS &COM PU TERV ol. 28 N o. 8A ug ust 2011收稿日期 :2011-05-15; 修回日期 :2011-06-23基于数据挖掘和特征选择的入侵检测模型康世瑜(广西工业职业技术学院 , 广西 南宁 530003摘 要 :提出了一种基于 SV M 特征选择和 C4. 5数据挖掘算法的高效入侵检 测模型 . 通过使用该模 型对经过特 征 提取后的攻击数据的训练学习 , 可以有效地识别 各种入侵 , 并提高 检测速度 . 在经典 的 K DD 1999入 侵检测数据 集 上

2、的测试说明 :该数据挖掘模型能够高效地对攻 击模式进行 训练学 习 , 能 够采用 选择的 特征正确 有效地 检测网 络 攻击 .关键词 :入侵检测 ; 特征选择 ; C4. 5算法 ; 支持向量机中图分类号 :T P309 文献标识码 :A 文章编号 :1000-7180(2011 08-0074-03A Network Intrusion Detection Model Based on Data Ming and Feature Selection SchemesKA NG Shi yu(G uang xi Vo cational &T echnical Institute of Ind

3、ustr y, Nanning 530003, ChinaAbstract:T his paper pr oposes a kind of intrusion detectio n model based on C4. 5data mining alg or ithm and SV M (cor relation based feature selectio n based feature selection mechanism, w hich can effectively detect sever al types o f attacks using the pr ocess o f fe

4、ature selectio n and att ack feature tr aining. T he ex per iment s on classic K DD 1999in tr usion dataset demo nst rate our mo del is accur ate and effective.Key words:int rusion detectio n; feature selectio n; C4. 5alg or ithm; SV M (Support Vecto r M achines1 引言入侵检测系统是当前网络安全领域的 研究热 点 , 在保障网络安全方面

5、起着重要的作用 1 2. 由于传统的入侵检测技术存在着规则库难于管 理、 统计模型难以建立 , 以及较高的误报率和漏报率 等诸多问题 , 制约了入侵检测系统在实际应用中的 效果 . 并且 , 我们通过研究发现 , 提取和处理的特征 数目过多是导致当前网络入侵检测系统速度下降的 主要原因之一 . 特征和检测算法之间并不存在线性 关系 , 当特征数量超过一定限度时 , 会导致检测算法 性能变坏 . 实际上 , 有些特征没有包含或者包含极少 的系统状态信息 , 它们对检测结果几乎没有影响 . 所 以使用特征选择去除冗余特征 , 保留能够反映系统 状态的重要特征是提高检测速度的一个有效方法 .在这种背

6、景 下 , 首先 提出 并实 现了 一 个基 于C4. 5数据挖掘算法的网络入侵检测系统 . 并且 , 采 用基于 SVM (Suppo rt Vector M achines, 支持向量 机 的特征选择技术对它所使用的特征进行选择和 约简 , 以提高整个系统的性能 .2 C4. 5数据挖掘算法Quinlan 提出的 C4. 5算法 3是当 前的最著名 的分类算法之一 , 该算法可以分为两个阶段 :树的生 成和树的剪枝 . 自顶向下的决策树的生成算法的关 键性决策是对节点特征值的选择 , 选择不同的属性 值会划分出不同的样本子集 , 从而影响决策树生长 的快慢以及决策树结构的好坏 , 导致找到

7、的规则信 息的优劣差异 . C4. 5算法的属性选择的基础是基于 使生成的决策树中节点所含的信息熵最小 , 所谓熵 在系统学上是表示事物的无序度 . 不难理解熵越小 则样本集合的无序性越小 , 也就是说样本集合内的第 8期 康世瑜 :基于数据挖掘和特征选择的入侵检测 模型属性越有顺序有规律 , 这也正是分类所追求的目标 .集合 S 的熵的计算公式如下 :Info (S =- k j =1j |S |*log 2j |S |(1式中 , fr eq (C j , S 表示集合 S 中属于类 C j (k 个可能类中的一个 的样本的数量 . |S |表示集合 S 中样本数量 . 上面的公式仅仅给出

8、了一个子集的熵的计算 , 如果按照某个属性进行分区后就涉及到若干个子集 , 需要对这些子集进行熵的加权和的计算 , 公式如下 :Info f (T = n i=1i |T |*Info (T i (2 式中 , T 指按属性 f 进行分区后的集合 , T i 指分区后 集合中的某一个集合 . |T i |表示在集合 T i 中样本 数量 , |T |表示集合 T 中样本数量 . 为了更加明显 地比较不同集合的熵的大小 , 需要计算分区前的集 合的熵和分区后的熵的差 (这个差被称做增益 , 增 益大的就是决策树要选取的节点 . 公式如下 :Gain (f =Info (S -Info f (T

9、(3 在第二阶段 , 算法通过计算信息增益率 , 对建立 的树进行剪枝 . 信息增益率的计算公式如下 , 其中 , v 是该节点分枝数 , S i 是第 i 个节点下的记录个数 . 就建模的计算复杂度而言 , C4. 5算法也包含了建树 与剪 枝 两 部 分 , 其 时 间 复 杂 度 为 O(mn log n + O(n(log n 2 , n 是训练样本 集中的样本数量 , m 是 特征数量 .Ratio (A =I (S 1, S 2, , S v (4 3 基于 SV M 的特征选择模型支持向量机是由 Vapnik 博士提出的基于统计 学习理论的一种新的模式识别技术 4. 支持向量机

10、用于特征选择主要基于如下思想 5:把已知 1组 N 个 d 维的独立同分布的训练样本 X =(x i , y i |x i R d , y i -1, 1, i =1, 2, , N 通过非线性变 换 h( 映射到一个高维特征空间 f . 在此高维特征 空间中 , 构造最优性决策函数 y (x =sgn ( h(x +b. 是分类超平面的系数向量 , b 是分类阈值 , 应 用 lagrange 乘子法 , 可以表示为= Ni=1i y i h(x i (5 式中 , i 是 lagrange 乘子 . 如果 y (x 是正值 , 则 X 属 于正值的类 ; 如果 y (x 是负值 , 则 X

11、 属于负值的类 . y (, 那么第 i 个特征对正值类的贡献大 ; 如果 是一个很 大的负值 , 则第 i 个特征对负值类的贡献大 ; 如果 的值在零值左右偏移 , 则第 i 个特征没有很好的分 类能力 . 一个对于特征的排序可以通过支持向量机 的函数完成 .4 基于数据挖掘和特征选择的高效入侵检 测模型依据本文第 2节所述的 C4. 5数据挖掘算法模 型的特点 , 我们使用 SVM 特征选择方法 , 构建了一 个高效的网络入侵检测系统 , 如图 1所示 . 该系统的 工作过程如下 :图 1 基于特征选择的高效入侵检测模型(1 报文捕获引擎捕获所有流经系统监测网段 的网络数据流 ;(2 特征

12、选取模块对捕获到的网络数据流进行 分析处理 , 提取出可以完备而准确代表该数据流的 特征向量 , 并采用本文所述的 SVM 选择方法对特 征空间进行 选择 和约简 , 并 将该特 征向 量提 交给 C4. 5数据挖掘算法分类引擎以作为 C4. 5数据挖掘 算法分类引擎的输入向量 ;(3 C4. 5数据挖掘算法分类引擎对这一特征向 量进行分析和处理 , 从而判别出是否为入侵行为 . 如 果 C4. 5数据挖掘算法分类引擎经过分析处理以后认 为是一种攻击行为 , 则向用户发出警告信息 ; 如果报 警信息对于攻击样本库的完善和更新有较大价值 , 比 如发现了未知类型攻击行为 , 可以在用户参与下将该

13、 次攻击事件加入到训练数据里 , 以备 C4. 5数据挖掘 算法分类引擎的再学习 , 这体现了 C4. 5数据挖掘算 法所具备的不断学习以识别更多类型攻击行为的能 力 , 也是 C4. 5数据挖掘算法入侵检测系统相比于一 般的基于规则入侵检测系统的突出优势和亮点 , 对入 侵检测系统的实际应用具有很大的价值 .特别需要注意的是 :C4. 5数据挖掘算法分类引 75微电子学与计算机 2011年的时间间隔根据攻击数据库的信息进行再训练 , 以 适应不断变化 的攻击 方式 , 能 够较好 地保 证检 测 效率 .5 实验结果及分析为了验证我们提出的入侵监测系统的性能和效 率 , 我们采用较为通用的

14、KDD 1999数据集 6来进 行测试 . 在实验前 , 我们对该数据集进行了预处理 . 首先 , 我们对其进行了随机采样 , 得到了 120387条 实验数据 , 这数据当中包含了四类攻击类型以及正 常数据 (Norm al 类型 ; 其次 , 我们 采用 SV M 的特 征选择方法选择了 KDD 数据集中的 6个主要特征 (sr c_by tes 、 dst _host_rerr or _rate 、 dst_byte 、 dst _ ho st_srv_rerr or_rate、 ho t 、 num _compromised 作为 C4. 5数据挖掘算法模型的输入 , 并且将采用得来的

15、 数据的其他属性进行了去除处理 .在实验中 , 我们采用了十折交叉验证 (ten fo ld cro ss validation 的方法 , 测得该 C4. 5数据 挖掘算 法模型检测攻击的正确识别率 (True Positiv e , 误 报率 (False Positiv e 以及漏报率 (False Negative , 并取其十次的平均值进行评价 .在经典的 WEKA 机器学 习框架下 7, 我们 利 用预处理后得到的训练样本对 C4. 5数据挖掘算法 分类器进行了训练 . 然后使用训练得到的模型进行 攻击识别 , 得到如表 1所示的实验结果 .表 1 检测率实验结果 %类型 正确率

16、误报率 漏报率 No rmal 95. 753. 251Pr obe 99. 800. 20DoS 10000U 2R 95. 893. 750. 36 R 2L 90. 785. 433. 79从表 1的测试结果可以看出 , 对于训练过的攻 击类型 , C4. 5数据挖掘算法具有很高的识别率 , 而 误报率和漏报率都很低 . 并且 , 由于 KDD 1999数据 集中包含的 DoS 和 Pro be 攻击的种类以及 数据量 都相对比较大 , 因而检测正确率较高 , 因此 C4. 5数 据挖掘算法模型对于训练数据量充足的入侵检测下 的应用应该是非常适合的 .从表 2中与传统入侵检测技术的比较结

17、果可以 看出 , 相对于传统的入侵检测技术而言 , C4. 5数据 挖掘算法以决策树的形式实现对攻击模式的记忆 , 能更好地满足入侵检测系统的实时性要求 ; 在检测 , , 法的检测效果优于传统的入侵检测系统 , 具有很低 的漏报率和误报率 ; 对于未知类型的攻击行为 , C4. 5数据挖掘算法具备一定的检测能力 , 在一定程度 上克服了基于规则入侵检测系统只能检测已知攻击 行为的缺陷 .表 2 对比实验结果 %IDS 类型 检测率 误报率 神经网络 95. 731SV M 98. 280C4. 597. 390C4. 5+特征选择 99. 180. 56 结束语本文研究的基于数据挖掘和特征选

18、取的入侵检 测模型还有待于在今后相关研究工作中进行优化和 性能提升 , 目前在实践过程中 , 还是存在着部分漏报 和误报问题 , 我们将在下一阶段的工作中针对 C4. 5算法和 SVM 算法进行进一步地针对性完善和优化 .参考文献 :1Byko va M , Ostermann S, T jaden B. Detecting netw o rk int rusions via a statistica l analy sis o f netw or k packet char acter istics C /Pr oc. of the 33rd Southeastern Sy mp. on System T heor y. A thens, O H. IEEE, 2001. 2陈丽丽 , 李 卫 , 管 晓宏 , 等 . 一种 基于 网络的 入侵 检测 系 统的研究与实现 J. 微电 子 学与 计算 机 , 2004, 21(6 : 63-65.3Quinlan J R. C4. 5:P rog rams for machine lea rningM . San F rancisco :M o rg an K aufmann Publishers, 1993. 4V apnik V