DBSCAN算法在DDoS上的应用及改进_互联网+_

朱静轩+孟彦+魏鸿坤

[摘要]本文介绍了智能物联网时代下DDoS的现状，DBSCAN算法为DDoS智能识别提供了方法，可以自动聚类出僵尸网络的IP，适应性很好，但是由于其领域半径使用余弦值，导致复杂度高，计算时间长。SimHash算法可以很好的解决计算邻域半径的复杂度高的问题，有效地改进了DBSCAN算法。

[关键词]DBSACN SimHash DDoS 聚类领域半径

中图分类号：TP68 文献标识码：A 文章编号：1009-914X（2017）01-0223-02

一、背景

随着互联网的发展，智能时代的到来，人工智能相关技术不断发展，各大商业巨头加大对人工智能的投入，智能家居，智慧城市相关设备不断完善，智能物联网终端设备种类数量大大增加，但由于智能设备的快速扩张，各家对安全的重视程度参差不齐，导致安全问题频发。2016年9月，著名僵尸网络Miral利用物联网设备，如道路摄像头对Krebs？on？security发起了DDoS攻击，而后作者在GitHub上开源了相关代码，10月21日，Dyn公司的DNS服务遭受到来自Miral更大的DDoS攻击，此外家用路由器摄像头等，经调查显示大多数都是使用的弱密码，如123456等，安全性急需加强。由此可见，智能物联网终端设备本身是脆弱的，用户对这方面的认知还处于空白期，一方面要加强对用户的宣传，另一方面云上服务需要加强对来自终端设备请求的检测，检测其发出的请求是否符合要求。智能物联网设备数量巨大，请求格式各异，对云上服务的处理要求很高，需要在及时处理掉众多请求，完成安全检测。

值得高兴的是，随着机器学习、深度学习的发展，以及在实践中的运用，DBSCAN算法在快速聚类和快速分类上具有巨大优势，提供了理论基础和方法。

二、DBSCAN算法

1、DBSCAN（Density-Based？Spatial？Clustering？of？Applications？with？Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。DBSCAN算法的显著特点是聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。

2、DBSCAN算法的几个基本概念

定义2.1（密度）空间中任意一点的密度是以该点为圆心、以Eps为半径的圆区域内包

含的点数目。

定义2.2（邻域：Neighborhood）空间中任意一点的邻域是以该点为圆心、以Eps为半

径的圆区域内包含的点集合，记作NEps（p）={q∈Dβdist（p，q）≤Eps}。这里D为数据库。

定义2.3（核心点：CorePoints）空间中某一点的密度，如果大于某一给定阈值MinPts，

则称该为核心点。

定义2.4（边界点：BorderPoints）空间中某一点的密度，如果小于某一给定阈值MinPts，

则称该为边界点。

定义2.5（直接密度可达到）点p从点q直接密度可达，若它们满足：

1）p处于q的邻域中，即p∈NEps（q）；

2）q是核心点，即βNEps（q）β≥MinPts。

定义2.6（密度可达到）点p从点q密度可达，若（p1，p2，...，pn），其中p1=p，pn=q，

且有pi从pi+1直接密度可达。

定义2.7（密度连接）点p和点q是密度连接的，若vo，使p和q都从o密度可达。

定义2.8（类：Cluster）数据库D的非空集合C是一个类，当且仅当C满足以下条件：

1）对于Pp，q，若p∈C，且从p密度可达q，则q∈C；

2）对于Pp，q，有p∈C和q∈C，则p和q是密度连接的。

定义2.9（噪声：Noise）数据库D中不属于任何类的点为噪声。

3、DBSCAN算法的基本思路

考察数据库D中的某一点o，若o是核心点，则通过区域查询得到该点的邻域，邻域中的点和o同属于一个类，这些点将作为下一轮的考察对象（即种子点），并通过不断地对种子点进行区域查询来扩展它们所在的类，直至找到一个完整的类。然后，依此程序寻找其它的类。最后剩下的不属于任何类的点即为噪声。

DBSCAN算法的思想是：对于某一聚类中的每个对象，在给定半径（文中用Eps表示）的邻域内数据对象个数必须大于某个给定值，也就是说，邻域密度必须超过某一阈值（文中用MinPts表示）。DBSCAN算法的聚类过程基于如下事实，即一个聚类可以由其中的任何核心对象唯一确定。可表述为：

（1）给定任一满足核心对象条件的数据对象p，数据库D中所有从p密度可达到的数据对象o所组成的集合{oβo>Dp}构成了一个完整的聚类C，且p∈C；

（2）给定一个聚类C和它的任一核心对象p，C等价于集合{oβo>Dp}。

三、SimHash算法

1、SimHash算法是Google公司進行海量网页去重的高效算法，它通过将原始的文本映射为64位的二进制数字串，然后通过比较二进制数字串的差异进而来表示原始文本内容的差异。Simhash算法将一个文档集合转换成一个64位的特征值，该特征值保留了原文档的绝大部分信息，可通过比较特征值来比较两个文档集合之间的差异，例如比较两个文档集合是否是重复的，通过比较两个文档集合的特征值之间的海明距离是否小于N（通常N取值为3），如果小于N的话，则可认为两个文档是重复的。简化了两个文档之间的运算流程步骤，大大加快了信息处理的效率

2、simhash值计算过程

（1）输入一个N维的文本特征向量V，每个特征具有一定权重

（2）初始化一个C维的向量Q为0，C位的二进制签名S为0

（3）对于向量V的每一个特征，使用传统Hash算法计算出一个C位的散列值H。对1<=i<=C，如果H的第i位为1，则Q的第i个元素加上该特征的权重；否则，Q的第i个元素减去该特征的权重。

（4）如果Q的第i个元素大于0，则S的第i位为1，否则为0

（5）返回这个C位的二进制签名S

3、海明距离

二进制串A 和二进制串B 的海明距离就是 A xor B 后二进制中1的个数。

四、DBSCAN在DDoS数据包聚类上的应用

众多物联网设备发出的DDoS攻击，在整个请求数据包集合上呈现出相似度高，攻击请求数据包附近的密度大的特点，使用DBSCAN算法来识别聚类DDoS攻击类别是非常合适的。

针对DDoS攻击高流量多终端的特点，选出源IP地址，源PORT，目的IP地址，目的PORT，协议类型、采样时间、数据大小和数据包内容信息8个字段作为DBSCAN算法的输入参数维度，使用两个数据包之间的余弦值作为DBSCAN算法中的邻域距离，将领域半径定为大于等于0.9，邻域阈值为100，计算出个数最多的一类，此类呈现的特点是数量大，相似度高，可作为DDoS來源类别。

则算法过程见下

（1）收集数据包，并将数据包中的源IP地址，源PORT，目的IP地址，目的PORT，协议类型、采样时间、数据大小和数据包内容信息规格化之后存储到原始表

（2）计算原始表两两数据包的领域半径（余弦值），如大于0.9，则将数据包存储到聚类表中

（3）扫描邻域半径表，得到个数最多个聚类，将聚类中的源IP、源PORT输出

五、SimHash对DBSCAN在DDoS数据包上的改进

使用DBSCAN算法来聚类DDoS攻击数据包，常常需要数小时乃至几天，原因就在于，在大数据量的情况下，计算领域半径的复杂度过高，导致计算时间长。幸好，SimHash算法提供了一个解决计算领域半径的方法。使用SimHash算法来改进计算流程，主要是使用海明距离作为DBSCAN算法的领域度量，使用SimHash值来代替原始数据来计算领域半径。由于海明距离得到的相似度是整数范围，所以将DBSCAN算法中的领域阈值定为3，这样就可以将聚类问题转换成求单个数据包的相似包有哪些，即是求与数据包X海明距离小于3的数据包集合。在这个问题上，数据包的聚类就减少了许多运算，十几分钟便得到结果。

则算法过程见下

（1）收集数据包，并将数据包中的源IP地址，源PORT，目的IP地址，目的PORT，协议类型、采样时间、数据大小和数据包内容信息、SimHash值规格化之后存储到原始表

（2）计算原始表两两数据包的领域半径（海明距离），如小于3，则将数据包存储到聚类表中

（3）扫描邻域半径表，得到个数最多个聚类，将聚类中的源IP、源PORT输出

六、结论

本文介绍了DBSCAN算法以及DBSCAN算法在计算领域半径复杂度高的缺陷，针对这个问题，本文使用SimHash算法来改进这一问题，使用海明距离替代余弦值距离，大大提高了计算领域半径的效率，降低了复杂度。在后续的研究中，会继续改进DBSCAN算法的计算效率，在DDoS攻击数据包上有更好的聚类效果

参考文献

[1] 钟锐.一种基于聚类与关联规则算法的DDoS攻击检测模型.赣南师范学院学报.2009年第六期

[2] 张楠，李洪敏，卢敏，柯明敏.网络异常流量检测方法.兵工自动化.2016-09-35（9）

[3] 徐洋，孙建忠，张焕国，谢晓尧.云环境下Web服务应用层DDoS攻击检测系统.计算机应用研究.2016年9月第33卷第9期

[4] 张明明，李玉峰，张鹏，孙淼.大流量下一种基于活跃熵的DDoS攻击检测方法.计算机应用研究.2016年7月第33卷第7期

[5] 王希斌，廉龙颖，高辉，郎春玲.网络安全实验中DDoS攻击实验的实现.实验科学与技术.2016年2月第14卷第1期