K-近邻算法在入侵检测系统中的应用研究

张昊

（沈阳理工大学信息科学与工程学院，辽宁 沈阳 100159）

0 引言

计算机网络已经深入到工业、商业和人类生活的各个领域，随着世界向云计算，移动应用和无线网络发展，网络安全比以往任何时候都更加重要。网络中的攻击行为种类繁多，网络攻击事件也屡屡发生。计算机安全协会的一份调查报告发现，45.6%的受访者表示他们在过去一年中至少遭受过一次有针对性的攻击，数据泄露通常也会导致公司损失数十亿美元资产[1]。因此，构建可靠的网络对IT管理员来说是一项非常重要的任务。同时，信息技术的快速发展也为建立可靠网络带来了若干挑战，建立一个易于实现的网络安全体系已经成为一项非常艰巨的任务。针对上述问题，入侵检测系统（IDS）应运而生，它是指被设计用来发掘那些对网络安全可能产生威胁的行为的软件或硬件系统，入侵检测系统不仅易于实现并且切实可靠，是构建网络安全体系的重要措施。入侵检测系统的主要任务是通过检测网络系统或主机设备上的恶意攻击来保护计算机系统或计算机网络，监视计算机系统或网络中发生的事件并挖掘他们入侵的迹象[2]。IDS能够对网络安全事件进行发现、记载并产生安全报告，一般放在内联交换机的生成端口或集线器上，用来取代交换机。

1 常见的入侵检测系统

常见的入侵检测系统主要有：基于主机的IDS（HIDS）、基于网络的IDS（NIDS）以及基于签名的IDS，其具体介绍如下：

基于主机的IDS是一种通常在计算机、节点或设备中运行的IDS，现如今已经开发了许多可用于监视网络的HIDS变种。它的主要功能是内部监控，首先，它监视和分析计算机、节点或设备的内部[3]。然后，HIDS确定系统是否已被入侵并警告管理员。例如，它可以检测到一个流氓程序，以可疑的方式访问系统资源，或者发现程序以有害的方式修改注册表。

基于网络的IDS与HIDS的不同之处在于它通常沿着LAN线放置。它试图通过分析遍历到多个主机的线路的流量来发现对LAN的未授权和恶意访问。目前已经有许多用于检测恶意流量的算法，它们通常读取入站和出站数据包并搜索任何可疑模式[4]。NIDS生成的任何警报都允许它通知管理员或采取主动操作，例如阻止源IP地址。NIDS最常见的位置是使用网络分路器直接连接到交换机跨接端口，并且在内部连接[5]。

在基于签名的IDS中，IDS查找数据包并将其与预定义的规则或模式（称为数据库中定义的签名）进行比较[6]。该技术的主要优点是简单有效地处理审计数据。基于签名的方法的优点是具有低得多的误报率。但是基于签名的检测这种方法对未知攻击是无效，随着每小时新攻击和恶意活动的更新速度的加快，基于签名的IDS仅能检测到与其签名数据库和规则集的贴近度一样的攻击方式。

2 KNN算法在入侵检测中的适用性

面对肆意发生的网络攻击，入侵检测系统需要通过对网络攻击行为有更高检测率的检测算法来维护网络安全。在本节首先介绍朴素贝叶斯、C4.5决策树和KNN算法的原理，然后比较分析KNN算法相比于朴素贝叶斯和C4.5决策树算法在入侵检测系统中有更好的适用性。

2.1 朴素贝叶斯

根据贝叶斯定理有，给定样本特征B,样本属于类别A的概率为：

朴素贝叶斯是基于贝叶斯定理和特征条件独立假设的分类方法，则有：

在上式中，分母对于所有类别来说都相等，因此只需将分子最大化，所以有：

对于一个新的测试样本X,对各个类别计算P( X | yi) P( yi)概率，如果某个类标yi使该概率最大化，则该测试样本的类标则为yi[7]。

2.2 C4.5决策树算法

C4.5决策树是一种用于分类和回归的有监督学习方法，C4.5决策树的本质是构建一个树，其中每个分支显示多个可能性之间的概率，每个叶子用来显示决策[8]。C4.5决策树算法收集信息并将其用于决策，在C4.5决策树中，每个类别根据不同的属性划分数据，目标是以最少的决策数量实现完美的分类。

2.3 K-近邻算法（KNN）

K近邻算法(k-nearest neighbor, KNN)是一种基于实例的学习方法，也可以称为懒惰学习，它是用于分类或回归的非参数方法[9]。KNN的分类原理为对于训练集中待分类的对象，每个对象的分类由最近的K个数据投票确定，即对象被分配给最近的K个对象中最多的类，并由训练集中K个最近邻居的多数标签表示。每个对象的特征由位置矢量描述，并且特征之间的距离由欧几里德或曼哈顿距离测量。

2.4 比较分析

从上述对算法原理的分析我们可以得出，朴素贝叶斯算法对输入数据的要求较为严格，若某个属性值在训练集中没有与某个类同时出现过，则直接基于条件概率与先验概率的计算公式进行计算，将出现不论其它属性如何，该类的判别概率都为0的问题，导致分类质量大大降低，这在我们入侵检测系统中将会产生严重的漏判问题，导致大部分网络攻击行为无法检测出来，给计算机网络安全带来严重问题。而C4.5决策树算法相比于朴素贝叶斯来说，虽然在输入数据要求上并不严格，可以处理具有不相关特征的数据，但同时由于其分类原理是选择最佳特征进行分类，很容易造成过度匹配的问题，在入侵检测系统中往往会产生对某种攻击行为检测率较高，而对其他攻击行为检测率很低的问题，对于入侵检测系统来说，这都不是我们希望看到的。

入侵检测系统需要的是算法易于实现，对数据结构并不敏感，且检测精度较高的检测技术。KNN算法是基于不同数据特征值之间的距离进行分类的，采用计算不同数据之间的欧几里德或曼哈顿距离来判别待测数据的类别，通过这种精确的数学计算，在入侵检测系统中，会对网络攻击行为产生较好的检测效果。

3 实验结果分析

为了分析上述入侵检测技术的性能，本节采用应用广泛的朴素贝叶斯、KNN和C4.5决策树算法在KDD Cup99 数据集[10]上进行仿真实验。并给出评价指标准确率和召回率。准确率指正确检测到入侵记录数与记录总数的比例，召回率指正确检测到入侵记录数与入侵记录总数的比例。

表1给出了朴素贝叶斯、K-NN和C4.5决策树检测算法对攻击行为检测的准确率和召回率。

表1 不同算法对攻击行为的检测效果Tab.1 Detection effect of different algorithms on attack behavior

图1给出了朴素贝叶斯、KNN和C4.5决策树检测算法对攻击行为检测准确率和召回率的柱状图。

图1 不同算法对攻击行为的检测效果Fig.1 Detection effect of different algorithms on attack behavior

由上述实验结果可以看到，朴素贝叶斯和C4.5决策树检测算法对网络攻击行为检测都有一定的效果，但KNN算法的检测效果最好，朴素贝叶斯检测算法的准确率和召回率明显低于K-NN和C4.5决策树检测算法，检测效果较差。而KNN和C4.5决策树检测算法虽然在准确率上相差不多，但KNN的召回率要明显高于C4.5决策树检测算法，说明KNN相比C4.5决策树检测算法对网络中的攻击行为有更好的检测效果。由此可见，KNN算法相比于朴素贝叶斯和C4.5决策树检测算法在入侵检测系统中有更好的检测效果，非常适合应用到入侵检测系统当中。

4 结论

本文介绍了IDS在网络安全的重要性，以及不同类型的入侵检测系统、方法和技术。每种技术和IDS都有其优越性和局限性，因此在选择最佳方法时应注意。本文通过算法原理和在KDD Cup99数据集上的实验分析发现，朴素贝叶斯、K-NN和C4.5决策树检测算法都可以用于入侵检测系统中对网络攻击行为的检测，但K-NN算法在入侵检测系统中有更好的检测效果，非常适合应用于入侵检测系统对网络攻击行为的检测。在今后会将研究重点放在常见的入侵检测模型上，同时也会对KNN算法的计算复杂度进行进一步的研究。