基于概念格的入侵检测系统0921.doc

基于概念格的入侵检测谷雨谷雨, 女, 1974年生, 讲师, 博士研究生, 研究方向为数据挖掘与网络安全. Email: ,张天军2,范菁2,何磊2（1. 西安交通大学电子与信息工程学院, 西安 710049; 2. 云南民族大学网络中心, 昆明650031）摘 要 概念格是近年来获得飞速发展的数据分析的有力工具. 在本文中, 作者将概念格应用于入侵检测系统中, 构造了一个基于规则分类判决的入侵检测模型; 提出了决策规则格和决策规则格约简的概念, 获得了入侵检测的分类规则集. 实验表明此方法能较好地缩减规则集中规则的数目, 且有较高的分类正确率.关键词 入侵检测；概念格；决策规则格；约简中图法分类号 TP309Intrusion Detection Basing on ConceptLatticeGu yu1, Zhang Tianjun2, Fan Jing2, He Lei2(1. Electron and Information Engineering Institute of Xian Jiaotong University, Xian 710049;2. Network and Information Center of Yunnan Nationalities University, Kunming 650031)Abstract Concept Lattice is a kind of powerful data analytic tool, which is developing quickly in recent years. In this thesis, author applies Concept Lattice to Intrusion Detection System, and constructs an intrusion detection model basing on classifying ruling. The concept of decision-making rule lattice and decision-making rule lattice reduction are brought forward; an intrusion detection classifying rule assembly is acquired. Conclusion from experiment, the method could curtail the number of the rules in the rule assembly, and could get more exact classifying ratio.Key words Intrusion Detection; Concept Lattice; Decision-making rule lattice; Reduction1 引言随着网络技术和网络规模的不断发展, 其应用领域正在不断拓展, 电子商务、公用网站、金融电子化等新兴事物的出现极大地改变了人们传统的生活和学习方式, 互联网络已经成为当今信息社会不可或缺的一部份. 但是随着社会网络化程度的增加, 安全性隐患日益明显地开始暴露出来. 入侵检测（Intrusion Detection, 简称ID）是对（网络）系统的运行状态进行监视, 发现各种攻击企图、攻击行为或者攻击结果, 以保证系统资源的机密性、完整性与可用性. 入侵检测系统（Intrusion Detection System, 简称IDS）能有效地检测各种形式的入侵行为并及时响应, 是构筑网络系统安全防御体系的一个重要组成部分. 一般地, 入侵检测的方法可分为异常检测方法和滥用检测方法两种. 异常检测（Anomaly Detection）的思想是：入侵行为通常和正常行为存在严重的差异, 通过检查这些差异可以检测出入侵. 异常检测针对某个特定的对象, 学习其行为特征, 产生这个对象的行为概貌, 并通过其后的监视对比学习到的行为概貌来检测出该对象的异常行为, 产生警告并做出相应的反应. 随着计算机网络技术的发展, 新型的攻击方法层出不穷, 由于异常检测系统具有检测未知入侵场景的能力, 可以发现一些未知的入侵行为, 近年来倍受瞩目. 滥用检测（Misuse Detection）主要是通过某种模式或信号预先定义入侵行为, 然后监视系统的运行, 并从中找出符合预先定义规则的入侵行为. 其优点是检测的准确度高, 缺点是只能对一些已知的入侵行为进行标识. 从本质上讲, 入侵检测实际上是一个分类问题, 就是要通过检测把正常数据和异常数据分开. 为此作者构造了一个基于规则分类判决的入侵检测模型, 如图1所示. 模型采用TCPDUMP收集网络数据包, 首先进行过滤和格式转换, 将网络数据包恢复成含有相关网络信息连接记录；随后, 进行数据预处理, 如对连续属性的离散化处理；对处理后的数据进行学习, 提取相应特征, 构造规则集. 规则分类系统分为训练阶段和工作阶段. 训练阶段主要完成分类模型的归纳学习工作；工作阶段则用学习得到的分类模型对网络事件进行分析、检测, 也可以同时反馈给特征选取和计算部分, 以便对分类模型做在线学习. 工作阶段ASCII二进制TCPDUMP过滤及格式转换预处理规则集特征选择及构造测试分类结果分类模型训练阶段图1 基于规则分类判决的入侵检测模型分类学习的方法有很多种, 如基于决策树的方法、基于神经网络的方法、基于数据聚类的方法等等. 这些方法均各有其优缺点. 如C4.5算法评价决策树的最主要依据是决策树的错误率, 而对树的深度、节点个数等不进行考虑, 所以直接从由C4.5算法构造的决策树提取的规则集不是最简的；基于神经网络的方法可以通过训练来固定神经网络结构, 然后对入侵进行预测1, 但神经网络的连接权系数难以确定, 且若不能自动调整神经网络的结构则无法对新入侵进行判断；基于数据聚类的方法中向量间的相似度也是难以定义的. 为了简化分类规则集, 提高入侵检测系统的检索速度, 使实时检测成为可能, 作者采用了概念格理论来获取决策规则. 概念格是近年来获得飞速发展的数据分析的有力工具, 目前已被应用于机器学习等方面, 如Neuss和Kent使用概念格进行Internet上文档元信息的自动分类和分析2.从数据集中生成概念格的过程实质上是一种概念聚类过程. 在本文中, 作者将概念格应用于入侵检测系统分类规则集的构造, 实验表明它能较好地缩减规则集中规则的数目, 且有较高的分类正确率. 2 基于概念格的决策规则集2.1 概念格基本思想概念是人类进行知识表达的一种手段, 数据库知识发现的过程就是将数据库中蕴含的知识形式化成有用概念的过程. 概念格, 也称为Galois格, 由Wille R于1982年首先提出3. 概念格的每个节点是一个形式概念, 由两部分组成: 外延, 即概念所覆盖的实例, 和内涵, 即该概念覆盖实例的共同特征. 对于同一批数据, 所生成的格是唯一的, 即不受数据或属性排列次序的影响, 这是概念格的优点之一. 定义1 一个形式背景（formal context）是一个三元组T=(O, D, R), 其中O是事例集合, D是描述符（属性）集合, R是O和D之间的一个二元关系, 即. g R m表示与之间存在关系R. 定义2 在形式背景中, 对于对象集和特征集可以定义下面的两个函数f和g：通常称函数f和g为D的幂集P(D)和O的幂集P(O)之间的Galois连接. 定义从形式背景中得到的每一个满足及的二元组为一个形式概念（formal concept）. 其中O1称为概念的外延（extent）, D1称为概念的内涵（intent）. 定义3 在概念节点之间能够建立起一种偏序关系. 对于给定C1=( O1, A1) 和 C2=( O2, A2), 则C1 C2 A1 A2 O1 O2, 领先次序意味着C1是C2的父节点或称泛化. 若概念C1=( O1, A1) 和C2=( O2, A2) 满足O2 O1, 且不存在概念C3 =(O3,A3) 使得O2 O3 O 1则称C1是C2的直接超概念, C2是C1的直接子概念, 记为(O1, A1)(O2, A2). 2.2 决策规则格为了在概念格上构造入侵检测分类规则集, 我们对概念格的结构进行了扩展, 提出决策规则格的概念. 定义4 决策规则的支持度：对于训练集中给定的对象集合O1, count(O1, i )被定义为O1中具有决策i 的对象的数目. 如果, 则决策j被称为O1的支持决策, 记为sup_dcs(O1). r(d) 为决策种类的个数. 定义5 决策j在O1的置信度定义为：表示O1的支持决策的信度. 定义6 决策规则格：决策规则格的节点是用表示的形式. 其中C1是条件属性的集合, 称为O1的内涵, 即O1对各条件属性的特定取值；| O1|是O1的基数；sup_dcs(O1) 表示O1的支持决策；是相应支持决策的信度. 在决策规则格中, 每一个节点均由不同条件下对应的决策及该决策的信度来表示, 这样可以直接从决策规则格上获取相应的入侵检测分类规则. 然而, 由于决策规则格的外延是内涵可以确定的最大的对象集合, 因此获得的分类规则并非最简的. 为从决策规则格中提取简化规则, 作者提出了决策规则格约简的概念：定义7 对于一个决策规则格中的节点H(O1, C1, sup_dcs(O1), 1.0), 如果属性集且C2满足以下两个条件：（1）g (C2) = g (C1)= O1,（2）从C2中去掉任何一个属性都将使（1）不成立. 则称C2为C1关于sup_dcs(O1)的约简. 定义7表明, 如果条件集C2比C1更简化, 则可以用C2取代C1. 为此, 可以设计出相应的决策规则格构造算法及入侵检测分类规则集的生成算法. 实验表明算法有效地削减了分类规则集中规则的数目.3 实验实验所采用的训练数据及测试数据选自KDD CUP 99中标注了正常行为与异常行为的数据集 4 . 两个数据集相互独立, 各种攻击类型在两个数据集中具有不同的分布. 其中, 训练数据集中包含123845条记录, 共有正常数据和27种攻击类型数据；测试数据集中包含31019条记录, 有正常数据和31种攻击类型数据, 其中有8种攻击是训练数据集中所没有的. 作者采用了规则总数, 规则前件的平均长度, 不可识别样本率, 分类正确率等几个指标对分类效果进行评价. 其中, 实验结果如下:未做规则简化基于本文方法获得的规则集规则总数74191643规则前件的平均长度92.36不可识别样本率73.5145.61分类正确率97.8389.27%实验结果表明, 当决策表中的冗余信息没有充分去掉时, 规则集中规则数目过多, 新样本匹配时间长, 且对新样本的预测能力低下, 不可识别样本多. 相比之下, 经过对属性值进一步约简后, 规则集中的规则数目明显减少了, 不可识别率也降低了. 在实验中, 系统的不可识别率仍然很高, 这是由于测试数据集是从样本集中随机选取的, 其中大量新样本 (新攻击类型) 没有在训练数据集中出现, 这些样本不一定能识别, 或识别不正确. 这一问题可以在在线学习中将新知识加入到分类规则集中来解决. 4 小结概念格的每个节点是一个形式概念, 它所对应的偏序关系简洁地体现了概念之间的泛化和特化关系, 是进行数据分析的有力工具. 在本文中, 作者将概念格应用于入侵检测系统中, 构造了一个基于规则分类判决的入侵检测模型; 提出了决策规则格和决策规则格约简的概念, 获得了入侵检测的分类规则集. 实验表明此方法能较好地缩减分类规则集中规则的数目, 且有较高的分类正确率.参考文献1. Fox K L, Henning R, Reed J, etc. A neural network approach towards intrusion detection. In Proceedings of the 13th National Computer Security Conference, Washington, D.C., October 1990: 125-1342. Neuss C, Kent R E. Conceptual Analysis of Resource Meta-Information EB/OL.