第 14 期 .33 No.14 卷 第 33 Vol ·安全技术· 计 算 机 工 程 Computer Engineering 2007 年 7 月 July 2007 文章编号：1000—3428(2007)14—0154—03 文献标识码：A 中图分类号：TP309.1 K-means 聚类算法在入侵检测中的应用 李 洋 (长沙理工大学计算机与通信工程学院，长沙 410076) 摘 要：提出了一种基于聚类分析方法构建入侵检测库的模型，实现了按 K-平均值方法建立入侵检测库并据此划分安全等级的思想。该检 测系统的建立不依赖于经验数据，能自动依据原有数据对入侵行为进行重新划分。仿真实验表明，该方法具有较强的实用性和自适应功能。 关键词：网络安全；入侵检测；数据挖掘；聚类分析；K-平均值 Application of K-means Clustering Algorithm in Intrusion Detection (Institute of Computer & Communication Engineering, Changsha University of Science & Technology, Changsha 410076) LI Yang 【Abstract】This paper introduces an intrusion detection model based on clustering analysis and realizes an algorithm of K-means which can set up a database of intrusion detection and classify safe levels. Experiential data are not required to set up this detection system, which is capable of re-classifying intrusion behaviors in terms of related data automatically. Simulation experiments show that the technique possesses strong applicability and self-adaptability. 【Key words】network security; intrusion detection; data mining; clustering analysis; K-means 随着网络的迅速发展和广泛使用，人们得益于网络的同 时，网上的数据也频繁地受到黑客的攻击和篡改，网络安全 变得越来越重要。目前常用的安全技术如信息加密、防火墙 等可以作为保护网络的第 1 道防线，但仅有上述技术是不够 的，比如目前广泛使用的防火墙技术不能阻止内部攻击，不 能提供实时检测等，人们由此提出了网络安全的第 2 道防线 ——入侵检测技术。入侵检测用于识别非授权使用计算机系 统的个体(如黑客)和虽有合法授权但滥用其权限的用户(如内 部攻击)。现有的入侵检测系统大都采用专家系统或基于统计 的方法，这需要较多的经验，而数据挖掘(data mining)方法的 优势在于它能从大量数据中提取人们感兴趣的、事先未知的 知识和规律，而不依赖经验[1]。本文运用数据挖掘中的聚类 分析方法，建立入侵检测模型数据库。它的优点是能高度自 动化地分析原有数据，作出归纳性推理，从中挖掘出潜在的 模式，预测出客户的行为，更重要的是它能够优化或完全抛 弃既有的模型，对入侵行为重新划分并用显示或隐式的方法 进行描述。仿真实验表明该方法具有较强的实用性和自适应 功能。本文的聚类分析方法是基于距离的K-平均值(K-means) 方法，利用此技术实现网络安全目前在国内外都是一种新的 尝试。 1 入侵检测系统 入侵检测是对入侵行为的发觉。入侵检测系统将收集到 的信息加以分析，判断网络中是否有违反安全策略的行为和 遭到攻击的迹象，若找到入侵痕迹，认为与正常行为相符合 的行为是正常行为，与攻击行为相符合的是入侵行为，二者 都不符合的，则认为是异常数据，将其加入到数据仓库中作 进一步分析。 入侵检测系统的基本框架如图 1 所示[2]。 —154— 引擎 格式数据 原 始 数 据 检测器 型 模 数据 仓库 格式数据 模型 自适应检测 模型产生 图 1 入侵检测框架 图 1 中引擎观察原始数据并计算用于模型评估的特征； 检测器获取引擎的数据并利用检测模型评估它是否是一个攻 击；数据仓库被用作数据和模型的中心存储地；自适应检测 模型实时产生，送至检测器实时检测入侵行为。在整个检测 系统中，自适应检测模型的产生无疑对入侵行为的辨识起着 决定作用。如何快速准确地产生检测模型库显得至关重要。 2 建立检测模型库[3] 入侵检测模型能否高效、准确地辨析海量的用户行为数 据，并尽可能降低误判率、漏判率是判断一个入侵检测系统 成功与否的标志。数据挖掘技术是一种决策支持过程，它主 要基于人工智能(AI)、机器学习统计等技术，能从大量数据 中提取或挖掘知识。其中的聚类分析方法具有可伸缩性、高 维性、能处理不同类型属性、可按各种约束聚类等优点，尤 其适用大型数据库的模式分类[4]。 2.1 聚类分析 聚类按照“最大化类内相似性，最小化类间相似性”的 原则，将数据对象分组为多个类或簇(cluster)，同一个簇中的 对象具有较高相似度，而不同簇间的对象差别较大，对象间 作者简介：李 洋(1974－)，男，硕士研究生，主研方向：数据挖掘， 智能控制，Petri 网理论及应用 收稿日期：2006-08-27 E-mail：liyangpeace@sina.com 

是所有对象的数目；k是簇的数目；t是迭代次数(一般k和 t 均小于n)。鉴于待划分的数据库通常比较大，这种性能还是 比较优良的。 K-means 算法流程如下。 算法 K-means 基于簇中对象平均值 输入 簇的数目 K 和 N 个对象的数据库 输出 K 个簇，满足均方误差函数值最小 步骤： (1)任意选择 K 个对象作为初始簇中心(也是初始平均值)； (2)对 K 个对象数据度量值进行标准化处理； (3)Repeat； (4)计算分配后每个簇中对象的平均值(第一次按初始平均值)； (5)根据簇中对象平均值，重新将每个对象赋给最类似的簇； (6)Until 对象的重新分配不再变化。 3 实例仿真 限于篇幅，本文利用上述K-means算法只对一个小型用 户行为数据库进行实例分类[1]，表 1(除Class栏)列出了 20 条 网络级连接记录的特征数据[5]。须指出的是，入侵检测很大 程度上依赖于收集信息的可靠性和正确性，选择哪些数据表 现用户行为是首要问题。黑客们经常在系统和网络日志文件 中留下踪迹，充分利用这些信息是检测入侵的必要条件。所 选择的特征数据应能充分反映用户行为特征全貌，数据量应 尽量小，提取难度不可太大，还要考虑学习过程的时间、用 户行为的时效性等。此例中，特征参数的含义如表 2 所示[6]。 表 1 网络连接记录及分类 Count Serror Same_srv Diff_srv Srv_count Srv_serror Srv_diff_host Class 的相异度根据对象的属性值计算。聚类分析属观察式学习， 不依赖预先定义的类和训练实例，由此形成的每个簇，可从 中 导 出 相 应 规 则 。 聚 类 分 析 算 法 包 括 划 分 法 (patitioning method)、层次法(hierarchical method)、密度法(density method) 等，其中划分法最常用。 2.2 聚类划分法 给定一个有 N 个对象或元组的数据库，用聚类划分法构 建数据的 K 个划分，每个划分表示一个聚簇，并且 K≤N， 即将数据划分为 K 个组时，必须满足如下要求：(1)每个组至 少包含一个对象；(2)每个对象必须属于且只属于一个组。划 分法首先创建一个初始划分，然后采用一种迭代的重新定位 技术，通过对象在划分间的移动改进划分效果。一个好划分 的一般准则是：同一类中的对象间尽可能“接近”或相关， 不同类中的对象间尽可能“远离”或不同。当然，还有许多 其它评判划分质量的准则。 为了达到全局最优，基于划分的聚类要求穷举所有可能 的划分。在聚类划分中，基于距离的分类采用度量方式，例 如 K-means、K-medoids 等。当前比较流行的启发式方法首推 K-means 算法，本文采用此算法对已知用户行为数据库进行 聚类划分，检测入侵行为。 2.3 K-means 算法 K-means 算法以 K 为参数，把 N 个对象分为 K 个簇，以 使簇内具有较高的相似度，而簇间的相似度较低。相似度的 计算根据一个簇中的平均值(视为簇重心)进行。K-means 算法 的处理过程为：(1)随机选择 K 个对象，每个对象初始代表一 个簇的平均值或中心。对剩余的每个对象，根据其与各个簇 中心的距离，将它赋给最近的簇。(2)重新计算每个簇的平均 值。这个过程不断重复，直至准则函数收敛到期望值。由于 实际应用中对象数据选用的度量单位将直接影响聚类分析结 果，不同度量单位可能产生迥异的聚类结构，因此为避免对 度量单位选择的依赖，实际中应先对数据进行标准化处理。 标准化的步骤如下： 给定一个变量 f 的度量值， (1)计算平均绝对误差(mean absolute deviation)sf s ... m − y ) f 1 ( y ,..., 1 = p fy y 2 f p f f f f f 1 y − m + + m − y f p ... + + + 是变量f的p个度量值；m y 其中， 1 ( m p (2)计算标准化的度量值(X-Score) x ，i=1,2,…,p )f 。 m = + y = y f 1 f f p 2 f f f i i − s f f是f的平均值，即 用于判断的准则函数通常采用均方误差和，其定义如 式(1)所示： E = ∑ ∑= k i 1 mp − i 2 (1) 参数 Cp ∈ i 表 2 特征参数 含义 d i j ( , ) = 2 x i 1 − x j 2 + x i 2 − x j 2 2 ... + + x i p − x j p 2 其中，E是数据库中所有对象的均方误差总和；p表示给 定的数据对象；mi是簇ci中数据对象的加权平均值(p和mi都是 多维的)；簇ci的数目取决待划分类数。每个对象与簇中心的 距 离 采 用 欧 几 里 德 距 离 ， 其 定 义 如 式 (2) 所 示 ， 其 中 是 2 个P维的数据对象。该 i = 算法试图找出使均方误差函数值最小的K个划分，令生成的 结果尽量紧凑、独立。下面给出了K-means算法的流程，从中 ，其中，n 可以得到，算法的复杂度为 ，远小于 x x , i i 1 2 (nktO 2nO ,..., ,..., 和 x i = x x x ( ) ( ) ) j ) ( , j 2 j 1 p j p Count (2) 在 一 个时 间 窗 口 内 目 标 主机 是 与 当 前 连接 相同的连接次数(以下属性针对相同主机的 连接) 出现 SYN 错误的连接百分比 目标端口(service)相同的连接所占的百分比 目标端口(service)不同的连接所占的百分比 目标端口(service)与当前连接相同的连接次 数(以下属性针对相同服务的连接) 出现 SYN 错误的连接百分比 Serror Same_srv Diff_srv Srv_count Srv_serror rv_diff_host 目标主机不同的连接所占的百分比 Class 分类结果 参数 序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 1 15 6 8 7 1 1 1 2 1 6 7 1 1 1 2 1 7 6 0.1 0.0 0.88 0.75 0.95 0.82 0.0 0.0 0.2 0.1 0.0 0.8 0.85 0.0 0.2 0.2 0.0 0.0 0.9 0.8 1.0 1.0 0.88 0.3 0.25 0.18 0.55 1.0 1.0 0.9 0.75 0.1 0.05 0.85 0.65 0.5 0.6 0.67 0.33 0.0 0.0 0.0 0.12 1.0 0.75 0.9 0.67 0.0 0.0 0.1 0.0 0.9 0.85 0.0 0.3 0.5 0.4 0.33 0.67 1.0 5.0 4.0 25.0 6.0 7.0 6.0 2.0 2.0 3.0 5.0 6.0 6.0 6.0 5.0 4.0 4.0 5.0 6.0 7.0 6.0 0.0 0.0 0.5 0.0 0.6 0.0 0.0 0.0 0.0 0.0 0.0 0.2 0.1 0.0 0.0 0.0 0.0 0.0 0.6 0.0 0.6 0.5 0.0 0.0 0.3 0.0 0.0 0.0 0.33 0.55 0.5 0.2 0.0 0.45 0.65 0.0 0.1 0.2 0.2 0.0 正常 正常 攻击 异常 异常 异常 正常 正常 正常 正常 正常 异常 异常 正常 正常 正常 正常 正常 异常 异常 类型 Uint Uint Uint Uint Uint Uint Uint Char —155— 

此算法用 C++编程实现，实验数据均取自 PIII566 微机。 按上述流程及所选择的特征数据，程序经过 8 次迭代即识别 出攻击、异常和安全 3 种类型的记录(也可根据需要设定其它 分类数)，均方误差和为 57.004 327。将该算法用于不同大小 数据集，实验表明，迭代次数总是一个小于数据集的整数， 并与之保持近似线性关系，这无疑对满足适时应用需要有实 际作用。此例中，聚类分析后识别出的结果如表 2 的 Class 栏所示。从中可以看出，运行 K-means 聚类后，记录 3 是唯 一具有攻击倾向的记录；而记录 4~6、12、13、19、20 是具 有异常行为模式的 7 条记录，需要进一步观察；剩下的记录 1、2、7~11、14~18 则是安全的。K-means 算法按特征参数的 性质，把该网络级行为数据集归为 3 类。 图 2 是运行算法前后，聚类结果的对照。从图 2(b)中可 以看出，具有异常或攻击行为模式的记录，同正常行为记录 有效隔离开来。对 K-means 聚类结果进行分析后，总结出如 表 3 所示的 3 类规则及其含义，这些规则中的正常与攻击行 为模式可作为入侵检测模式保留在数据仓库中，用以预测和 判断用户行为合法性的依据。 18 18 16 16 14 14 12 12 10 10 22 20 18 16 14 12 10 8 6 4 2 0 22 22 20 20 8 8 6 6 4 4 2 2 0 0 2222 20 20 18 18 16 16 14 14 12 12 10 10 8 8 6 6 4 4 2 2 0 0 0.2 0 .3 0 .4 0.5 0.6 0.2 0.6 0.2 0.6 0.5 0.5 0.3 0.3 0.4 0.4 (a) 0.2 0.2 0 .3 0 .4 0.5 0.6 0.3 0.4 0.5 0.6 (b) 图 2 聚类结果的对照 表 3 聚类检测规则 含义 在一个时间窗口内，目标主机与当前连接相同的次数大于等于 15；同一主机的连接中出现 SYN 错误的百分比大于等于 88%， 且目标端口与当前连接相同次数大于等于 25 在一个时间窗口内，目标主机与当前连接相同次数大于等于 6； 同一主机连接中出现 SYN 错误的百分比大于 75%，且目标端口 与当前连接相同次数大于等于 6 如果不满足上述条件 规则 攻击 异常 正常 —156— 对 其 中 的 异 常 行 为 记 录 作 进 一 步 分 析 ， 可 再 次 运 用 K-means 算法进行二次识别，程序只经过 4 次迭代，划归出 2 类，分别是记录 4、6、12、13、20 和记录 5、19，均方误 差和为 18.055 98。图 3 是再次应用聚类算法识别异常行为记 录后，分类出的结果。对分类的记录数据进行合理性分析， 可以得出记录 4、6、12、13、20 的用户行为不具备攻击特性， 可提高其安全等级；而记录 5、19 相同服务的连接中出现 SYN 错误达 60%，同一主机连接中出现 SYN 错误超过 90%，应 予以重点监控。 22 20 18 16 14 12 10 8 6 4 2 0 22 20 18 16 14 12 10 8 6 4 2 0 0.2 0.2 0 .3 0.4 0.5 0.6 0.6 0.4 0.5 0.3 图 3 二次分类结果 4 结语 本文运用聚类分析中的 K-means 算法分析用户行为数据 库，从中筛选出不安全的用户，也可以凭借该算法分列安全 等级，构建入侵检测库。 与传统方法相比，基于聚类的 K-means 算法在检测的精 确度上可能略有不足，但其应用便捷，对训练数据集的要求 低，特别是它可以优化或完全抛弃既有模型，对用户行为重 新划分，从中不断挖掘新的潜在模式，使该方法在入侵检测 领域有广泛的应用前景。 该算法适用于对入侵检测库构建时的初选，为降低误判 率和漏判率，还可对初选后的结果再次分类或配合其它算法 进行合法性分析，提高辨析精度。但是 K-means 方法不适合 发现非凸面形状的簇，或大小差别很大的簇，而且它对“噪 声”和孤立点数据较敏感，少量该类数据可能对平均值产生 较大影响，因此，如何“降噪”和“脱敏”是下一步工作需 要继续研究的问题。 参考文献 1 Lee W, Stolfo S J, Mok K W. Mining Audit Data to Build Intrusion Detection Models[EB/OL]. 2001. http://www.yahoo.com. 2 胡建斌. 入侵检测技术[DB/OL]. 北京大学网络与信息安全研究 室, 2004. 3 Han J, Kamber M. 数据挖掘概念与技术[M]. 范 明, 孟小峰, 译. 北京: 机械工业出版社, 2001. 4 宁玉杰, 郭晓淳. 基于数据挖掘技术的网络入侵检测系统[J]. 计 算机测量与控制, 2002, 10(3). 5 戴英侠, 连一峰, 王 航, 等. 系统安全与入侵检测[M]. 北京: 清 华大学出版社, 2002. 6 罗守山. 入侵检测[M]. 北京: 邮电大学出版社, 2004.