基于改进AP聚类算法的自学习应用层DDoS检测方法

刘自豪 张 斌 祝 宁 唐慧林

(信息工程大学 郑州 450001) (河南省信息安全重点实验室 郑州 450001) (liuzihao199307@126.com)

DDoS攻击作为一种有效的网络瘫痪与扰乱手段,其攻击范围不断扩大.随着针对网络层、传输层DDoS攻击检测防御技术的发展,如防火墙、入侵检测技术等,应用层DDoS攻击成为攻击者研究的热点.应用层DDoS攻击与服务器建立正常的连接,发送访问请求,在网络层与传输层表现正常,能够有效逃避网络层级的检测和过滤.如何有效检测应用层DDoS攻击是当前网络安全领域急需解决的关键问题.

应用层DDoS攻击与正常用户集中访问(flash crowd)现象较为相似,针对应用层DDoS检测的研究主要围绕如何区分上述2种现象开展.目前提出的检测方法分为3种:

1) 基于主机测试的检测方法.如将分析鼠标是否移动及请求是否符合正常行为模式程序传到客户端的图灵测试 [1] ,服务器触发所有客户端(攻击者和合法用户)提高访问速率的Speak-up [2] 等.该类方法容易部署,但会影响正常用户的体验,且生成请求、等待响应以及验证响应过程会消耗自身资源.

2) 基于行为特征描绘的检测方法.如采用隐马尔可夫模型描述服务器端观察到的用户访问行为 [3] 、用CUSUM算法检测Web群体外联行为参数的偏移 [4] 、利用大偏差统计模型分析用户访问行为实际点击概率分布与网站先验概率分布的偏差 [5] 以及将多层神经网络与遗传算法相结合对用户HTTP GET请求行为数量进行分析 [6] 等.该类方法检测率较高,但训练繁琐且无法及时更新样本空间中用户行为特征,攻击者容易掌握用户行为特征从而躲避检测.

3) 基于行为特征聚类的检测方法.如聚类Web日志中提取的用户行为属性的方法 [7-9] ,利用稀疏矩阵向量分解、节奏匹配以及 K -Means算法对用户请求频率序列构成的稀疏向量进行分类的方法 [10] .该类方法训练简单且检测率较高,但存在2个问题:①传统的 K -Means聚类算法由于聚类个数 K 需要手动设定,影响训练结果的客观性,且算法在处理大量训练数据集时训练时间较长,甚至会出现迭代无法中止的情况;②难以及时更新样本空间中用户行为类簇,同样存在躲避检测的风险.

为解决以上问题,本文基于行为特征聚类的思想,通过对近邻传播聚类(affinity propagation, AP) [11] 算法进行改进,并引入自学习功能,实现应用层DDoS攻击检测.主要贡献有3个方面:

1) 深入分析了flash crowd与应用层DDoS攻击访问行为的区别,在总结前人工作 [7-9,12] 的基础上,给出了活跃度、阅读速度、兴趣广泛度、热门网页偏好度、请求成功率、重复请求率、异常访问率7个用户行为特征属性用于描绘用户访问行为特征.

2) 在分析AP算法基础上,提出一种改进近邻传播聚类(improved affinity propagation, IAP)算法.IAP算法利用少量先验知识预先分类数据集,在此基础上通过类簇合并与清除过程,避免了聚类个数需要手动设置的问题,同时解决了传统AP聚类算法在样本数量过大时易出现存储空间不足或者聚类时间过长的问题以及特殊用户访问行为干扰检测结果的情况.

3) 用户行为类簇在检测过程中不断学习吸收正常用户行为特征,并引入Silhouette指标度量学习过程中类簇质量变化情况,及时对类簇进行重新聚类,不断丰富完善用户行为类簇,解决了用户行为类簇直接接收新用户行为造成的类簇结构越来越不集中、失真越来越大的问题.

本文首先介绍IAP聚类算法相关知识,包括AP算法研究现状及算法改进思想;其次提出基于IAP算法的用户行为聚类方法,包括Web日志预处理、用户行为属性提取及基于IAP算法的用户行为聚类流程;然后设计自学习应用层DDoS检测方法,包括用户检测方法、自学习方法及自学习应用层DDoS检测方法;最后进行实验与分析,验证IAP算法性能及自学习方法有效性.

1 IAP聚类算法

基于用户行为特征聚类进行应用层DDoS检测的方法分为2个阶段,即基于聚类算法的正常用户行为特征训练阶段和基于正常用户行为特征训练结果的检测阶段.1)训练阶段.基于日志统计信息计算用户行为特征属性,并通过聚类算法对正常用户历史行为特征属性进行聚类,获得多个正常用户行为特征属性类簇,即获得正常用户的访问习惯分布范围.2)检测阶段.将当前待测用户行为特征属性与正常用户行为特征属性类簇进行对比,判断待测用户的访问习惯是否在正常用户访问习惯分布范围内,从而判定待测用户是否为攻击者.因此,聚类算法是此类检测方法的核心.下面分析AP聚类算法相对于 K -Means算法的优势与AP聚类算法自身存在的不足,并介绍本文对AP聚类算法的改进方法.

与经典的 K -Means聚类算法相比,AP算法将所有数据点都作为候选的类中心点且聚类个数与输入偏好值(preference)及消息传播方式有关,避免了 K -Means算法初始点选择影响聚类结果与设置聚类个数 K 的问题.但AP聚类算法同样对样本数量的大小过于敏感,样本数量过大时易出现存储空间不足或者聚类时间过长的问题,当前解决方法主要分为2类:1)有监督的算法.主要包括分层组合的半监督近邻传播聚类算法 [13] 、基于同类约束的半监督近邻反射传播聚类算法 [14] 、基于概率框架融合AP聚类算法与EEM聚类算法的漂移动态 α -expansion聚类算法 [15] 等.该类算法利用先验知识(类标签、成对约束或先验概率)调整AP算法中相似度矩阵,在新得到的相似度矩阵基础上进行AP聚类,可以有效提高聚类性能.2)无监督的算法.包括基于基准数据的自适应AP算法 [16] 以及将Mergin思想融入到AP聚类算法过程的M-AP算法 [17] 等.该类算法通过降低输入数据规模,有效减少时间开销.

受上述2类算法启发,利用少量先验知识对样本数据进行预先分类,在此基础上引入类簇合并与清除机制,提出适用于用户行为聚类的IAP算法.下面分别介绍AP聚类算法以及IAP聚类算法思想.

1 . 1 AP聚类算法 [ 11 ]

AP聚类算法将每个数据点看成图的节点,图的有向边看成节点间消息的传递,目的是找到最优的类代表点集合,使得所有数据点到最近的类代表点的相似度之和最大.

数据点间相似度 s ( i , k )表示数据点 x i 作为 x k 中心点的合适程度,通常采用欧氏距离: 表示.其中 s ( k , k )为每个数据点 x k 的偏好值,表示数据点 x k 被选为中心点的可能性.AP算法初始假设所有数据点被选中为中心点的可能性相同,即设定所有 s ( k , k )为相同值 p .类簇个数受 p 的大小影响, p 取值越大得到的类簇数量越多.

节点间传播的消息参数为吸引度 r ( i , k )和归属度 a ( i , k ). r ( i , k )是从 x i 指向 x k ,它代表 x k 积累的证据,反映 x k 作为 x i 代表点的合适程度; a ( i , k )是从点 x k 指向 x i ,它代表点 x i 积累的证据,反映 x i 对选取 x k 作为代表点的认可程度. r ( i , k )与 a ( i , k )越大, x k 作为 x i 代表点的可能性越大.AP算法通过迭代不断交替更新每个点的吸引度和归属度,直至迭代次数超过最大值max its 或者聚类中心连续多次不发生改变.为了减轻震荡,在每次迭代中引入阻尼系数 λ r ( i , k )与 a ( i , k )交替更新过程为

r j ( i , k )= λ × r j -1 ( i , k )+(1- λ

(1)

i k 时,

a j ( i , k )= λ × a j -1 ( i , k )+(1- λ

(2)

i = k 时,

a j ( k , k )= λ × a j -1 ( i , k )+(1- λ

(3)

1 . 2 IAP算法基本思想

为提升AP聚类算法对相似度高、数量大训练样本集的适应性,首先利用少量先验知识对输入数据集预先分类并对每一类进行AP聚类,将整个AP聚类过程分成若干层聚类,使处理过程简单、易于实现;其次通过合并输出的类簇,消除相似数据点归于不同分类子集造成的误差;最后通过清除与正常用户行为偏差较大的特殊用户构成的类簇,消除特殊用户对检测精度的影响.

1) 数据集预分类.鉴于不同时段的用户访问特性不同,分别在不同时段抽取1个数据点构成抽样数据集.计算剩余数据集中每个样本与抽样集中每个样本的距离,与距离最近的样本点进行关联,得到分类集合.然后分别对分类集合内每个分类进行AP聚类,最终得到数据集的所有类簇.

2) 聚类结果合并.在分类关联过程中相似数据点被分至不同的分类中,会导致这些原本相似的数据点分布在2个不同的类簇中,降低聚类精准度.如图1所示,实心圆代表抽取的样本点,空心圆代表关联数据点,虚线代表分类边界,实线为类簇边界.

Fig.1 The distortion of classification
图1 分类造成的失真

对相似数据点所构成的类簇进行合并可有效解决这一问题.合并规则如下:

① 分别计算每个类簇内任意2个数据点 x i x j 间的欧氏距离 s ( x i , x j ),设类簇中成员数量为 N i ,类簇内所有数据之间的平均距离 s i

(4)

② 设数据集预分类后类簇的数量为 p ,数据集内所有数据点之间的平均距离 s

(5)

③ 对于任意2个不同类簇 C i C j ,计算分属不同类簇的任意2点距离,记其中最小值为 s min.如果 s min< s ,则类簇 C i C j 可以合并,记为 C i C j .对于多个类簇,合并准则为

C i C j C j C k C i C j C k .

(6)

3) 聚类结果清洗.训练数据集中部分特殊用户与大多用户行为差异较大,其构成的类簇会干扰检测结果.如图2所示, C 1 C 5 分别代表5个不同类簇,实心方形代表待测用户,实线代表类簇边界,虚线内部代表正常用户分布范围.其中 C 5 C 1 C 4 相距较远,即其与大多数用户行为差异较大,并不能代表普通用户的正常行为; C 5 的存在导致检测结果本该为异常的待测用户被判断为正常用户,降低了检测精度.

Fig.2 The influence of special user
图2 特殊用户造成的影响

在将聚类结果用于检测之前,清洗这些特殊用户构成的类簇可以避免其对检测结果的干扰.清洗规则定义如下:

① 计算类簇 C i C j 的聚类中心 e i e j 距离 s ( e i , e j ),设聚类合并后类簇的数量为 q ,则所有聚类

中心距离平均值

(7)

② 计算 C i 的聚类中心与剩余类簇的聚类中心距离平均值

(8)

如果 则清除聚类 C i .

1 . 3 IAP算法复杂度分析

对于数据量为 n 的训练集,AP聚类计算复杂度主要与 n 个数据间的相似度矩阵相关,其计算复杂度为 O ( n 2 ).IAP算法将数据量为 n 的训练集分为 k 份较小规模子集依次聚类,设第 i 份子集中数据个数为 n i ,则其计算复杂度为 可知AP聚类计算复杂度可以转换为 故计算复杂度降低.

2 基于IAP算法的用户行为聚类方法

以原始Web日志为数据源,首先处理Web日志中记录的冗余请求信息;然后给出从Web日志中提取用户行为特征属性的方法;最后利用IAP算法快速准确聚类用户行为特征属性,生成用户行为类簇.下面分别介绍Web日志预处理、用户行为属性提取以及基于IAP算法的用户行为聚类流程.

2 . 1 Web日志预处理

原始Web日志中存在许多冗余信息,如当用户请求页面 ui-basic-elements.html时,Web日志记录的请求信息为 ui-basic-elements.html; assets plugins rap-heel js raphael.min.js assets js pages ui-elements.jpg.因此挖掘Web日志前,需要删除这些冗余信息,如JPEG,GIF等.应保留的请求有静态网页HTM,HTML,SHTML等,动态网页ASP,JSP,CGI,PHP等 [11] .

2 . 2 用户行为特征属性提取

文献[18]深入分析flash crowd与应用层DDoS的特点,总结flash crowd与应用层DDoS攻击访问行为具有如下区别:在发送请求速度方面,与正常用户相比,发生flash crowd时每个用户对应的请求数变小,而发生攻击时变大;在文件请求分布范围方面,发生flash crowd时被请求文件呈Zipf-like分布,而发生攻击时则集中在少数文件;在用户访问页面时间方面,正常用户阅读时间长,请求频率低,而攻击者阅读时间短,发生请求频率高.

为表征上述访问行为区别,挖掘Web日志记录信息,扩展文献[7-9,12]中提出的用户行为属性,构建用户行为特征向量.

假设在时间窗口 T 内,共 N 个用户访问了拥有 W 个网页的Web服务器.用户 i 的请求序列中,全部请求数为 Tol i ,不同请求数为 Dif i ,成功请求数为 Suc i ,总请求时间为 T i ,请求页面 w 的次数为 η w , i .

1) 活跃度.变量 α i 表示用户 i 活跃度,计算式为

(9)

其中, N 表示用户平均请求量.

2) 请求成功率.变量 β i 表示用户 i 请求成功率,反映用户访问有效页面的概率,计算式为

(10)

3) 重复请求率.变量 γ i 表示用户 i 重复请求率,反映用户对相同页面的偏好程度,计算式为

(11)

4) 阅读速度.变量 ε i 表示用户 i 的阅读速度,反映请求成功后用户的阅读时间长短,计算式为

(12)

5) 兴趣广泛度.变量 θ i 表示用户 i 兴趣广泛度,反映用户兴趣范围,计算式为

(13)

6) 热门网页偏好度.变量 λ i 表示用户 i 热门网页的偏好度,反映用户对请求次数最多网页的访问率,计算式为

(14)

其中, 表示用户 i 访问次数最多的网页.

7) 异常访问率.变量 μ i 表示用户 i 异常访问率,反映服务器繁忙时用户的请求速率,计算式为

(15)

其中, o i 为服务器繁忙时用户 i 的请求数.

根据上述定义的7个特征属性,构造用户 i 的访问行为特征向量:

V i =( α i , β i , γ i , ε i , θ i , λ i , μ i ).

N 个访问行为特征向量构成的访问行为特征矩阵 V =( V 1 , V 2 ,…, V N ) T ,表示Web日志中记录的 N 个用户的行为.

2 . 3 基于IAP算法的用户行为聚类流程

在用户行为属性及IAP算法思想的基础上,设计用户行为聚类流程,如图3所示.具体流程见算法1.

Fig.3 The flowchart of behavior model training
图3 行为模型训练流程

算法1 . 基于IAP算法的用户行为聚类方法.

输入:原始Web日志 L

输出:用户行为类簇集合 C .

步骤1. Web日志预处理.依据2.1节对原始Web日志 L 进行预处理.

步骤2. 用户特征属性提取.利用式(9)~(15)提取用户行为特征属性,获取用户行为特征集属性 X .

步骤3. 抽取样本子集.分别在特征属性集 X m 个不同时段抽取1个数据点构成抽样集 Y ,对于剩余特征属性集 X - Y 中每个样本 r i ,计算 r i 与抽样集 Y 中每个样本的距离,关联至与之距离最近的点 y i 形成分类 T i .得到 m 个分类构成的集合 T ={ T 1 , T 2 ,…, T m }.

步骤4. 聚类样本子集.分别对集合 T 内每个分类 T i 进行AP聚类,分类 T i 经聚类后生成的类簇集合 其中 k i T i 生成的类簇数量,进而得到特征集 X 的所有类簇集合 C ={ C 1 , C 2 ,…, C m }.

步骤5. 合并类簇.依据式(4)~(6)对 C 中类簇进行合并,更新特征集 X 所有类簇集合 C .

步骤6. 清洗类簇.依据式(7)~(8)对更新后的类簇集合 C 中异常数据点进行清洗.

3 自学习应用层DDoS检测方法

自学习应用层DDoS检测方法由用户检测与类簇自学习2部分组成.

3 . 1 用户检测方法

在用户行为类簇基础上,确定待测用户所属类簇,依据待测用户与所属类簇中心距离是否在检测阈值范围内来判断待测用户为攻击者还是正常用户.具体如下:

1) 对待测用户Web日志进行预处理,并依据式(9)~(15)提取待测用户 x t 的行为特征向量.

2) 计算待检测用户 x t 与每个类簇 C i 的聚类中心 e i 的欧氏距离 s ( x t , e i ),选择距离最近的类簇为待测用户最合适类簇 C fit .

3) 类簇 C fit 的检测阈值 δ fit 计算式为

δ fit = E [ Σ fit ]+ φ σ [ Σ fit ],

(16)

其中, Σ fit 表示类簇 C fit 中每个成员与聚类中心的距离构成距离集合; E [ Σ fit ]与 σ [ Σ fit ]分别为集合 Σ fit 的均值及标准差; φ 是偏差变量.根据检测偏差研究 [9] ,偏差范围应该偏离均值2~3个标准绝对误差,即2<| φ |<3.

4) 计算待测用户的偏移距离 s ( x t , e fit ),即待测用户 x t 与所属类簇聚类中心 e fit 之间的距离,如果 s ( x t , e fit )> δ fit ,判定待检测用户 x t 为攻击者,反之为正常用户.

3 . 2 类簇自学习方法

当用户 x t 的检测结果为攻击者时,采取异常处理策略;当检测结果为正常用户时,类簇 C fit 接收用户 x t .然而随着类簇中新用户数量增多,会出现簇分布结构越来越不集中,失真不断增大,聚类结果的精确性不断降低的情况.如图4所示,空心圆代表类簇原始数据,实心圆代表新归入的数据,在吸收新用户过程中,原始相对集中的类簇逐渐分散为3个不同类簇.

Fig.4 The change of distribution after accepting user
图4 用户归入前后类簇分布

在类簇 C fit 不断吸收新数据时,本文引入Silhouette指标(见式(17))度量类簇内部成员间的紧密性与可分性,从而确定何时对 C fit 重新进行聚类,将 C fit 重新划分为多个紧密的类簇.具体解决方法如下:

1) 设类簇 C fit 未接收新数据时用户数量为 f ,以每个用户为中心建立 f 个独立空间 Sp ,将待测用户 x t 关联至距离最近的用户所在空间.

2) 计算独立空间内所有用户的Silhouette指标,空间 Sp i 中用户 x u 的Silhouette指标 S il ( x u )计算为

(17)

其中, a ( x u )为空间 Sp i 中用户 x u Sp i 内所有其他样本的平均距离,表示空间内部成员间不相似度; b ( x u )=min{ s ( x u , Sp j )}, s ( x u , Sp j )为空间 Sp i 中用户 x u 到另一个空间 Sp j 的所有用户的平均距离,表示空间 Sp i 与空间 Sp j 的不相似度.

类簇 C fit 内所有用户的 S il 值均值 S av 反映了类簇内部所有空间相互可分性,即

(18)

其中,| C fit |表示类簇 C fit 中独立空间个数,| Sp i |表示独立空间 Sp i 中成员个数.

3) 当 S av <0.2时,表示该类簇缺乏实质聚类结构 [19] ,利用IAP算法重新聚类 C fit ,从而更新类簇.

3 . 3 自学习应用层DDoS检测方法

在用户检测及自学习方法的基础上,设计自学习应用层DDoS检测方法,如图5所示:

Fig.5 The flowchart of adaptive detection
图5 自学习检测流程

具体流程见算法2:

算法2 . 自学习检测算法.

输入:待测用户 x t 的Web请求日志 L ′、用户行为类簇集合 C ;

输出:异常用户集合 A 以及更新后的用户行为类簇集合 C .

步骤1. 待测用户特征属性提取.对待测用户 x t 的Web请求日志 L ′进行预处理,并利用式(9)~(15)提取用户行为属性特征,获取待测用户行为特征集 X ′.

步骤2. 寻找待测用户最合适类簇.计算待测用户 x t 与所有聚类中心距离,选择距离最近的类簇为待测用户最合适类簇 C fit .

步骤3. 计算偏移距离与检测阈值.计算待测用户的偏移距离 s ( x t , e fit )并利用式(16)计算类簇 C fit 的检测阈值 δ fit .

步骤4. 检测待测用户.如果 s ( x t , e fit )> δ fit ,则判定用户为攻击者,转入步骤6;反之则为正常用户,转入步骤5.

步骤5. 更新类簇.将正常用户归入类簇 C fit 中,利用式(18)计算 S av ,反映类簇 C fit 的聚类质量.如果 S av ≥0.2,将数据点直接归入类簇 C fit ;反之利用IAP聚类算法对类簇 C fit 中所有样本进行聚类.使用更新后的用户行为类簇集合 C 替代更新前的类簇集合,重新执行步骤2~4.

步骤6. 统计攻击者数量.记类簇更新前后攻击者数量分别为 ATK 1 ATK 2 .如果 ATK 1 ATK 2 ,转入步骤5,对类簇继续进行更新;反之转入步骤7.

步骤7. 结束.停止更新类簇并输出最终待测用户检测结果.

4 实验与分析

实验主要验证3个方面:

1) 利用IAP算法、AP算法及App-DDoS检测领域常用的 K -Means多重主成分分析(KMPCA)算法 [8-9] 对相同数据集进行聚类,对比时间开销,验证IAP算法效率;

2) 基于IAP聚类算法、AP聚类算法以及KMPCA算法聚类结果进行检测,对比误检率、检测率及ROC曲线,验证IAP聚类结果准确性;

3) 在IAP聚类结果基础上,分别采用无学习的方法(none-learning method, NLM)、直接归入学习的方法(direct-learning method, DLM)、本文所提自学习的方法(adaptive-learning method, ALM)更新正常用户行为特征属性类簇,并利用更新后的结果重新进行检测,对比误检率、检测率以及ROC曲线,验证自学习方法的有效性.

本文实验环境如下:Windows 7 x64操作系统,CPU Intel core i5-4590 3.30 GHz,8 GB RAM,1 TB硬盘存储空间.实验数据集分为正常用户训练数据集、攻击用户测试数据集、正常用户测试数据集以及正常用户学习数据集.选取真实Web日志Clerknet-HTTP数据集 [20] 中8月29日全天数据作为正常用户训练数据集(normal_training),9月3日全天数据作为正常用户学习数据集(normal_learning).考虑不同时段正常用户行为不同,选取9月1日2:00—6:00,8:00—12:00,14:00—18:00,20:00—24:00,4组不同时间段的数据作为正常用户测试数据集,分别记为正常用户测试_1数据集(normal_testing1)、正常用户测试_2数据集(normal_testing2)、正常用户测试_3数据集(normal_testing3)、正常用户测试_4数据集(normal_testing4).依据文献[21]中生成应用层DDoS攻击Web日志的方法,本文模拟随机页面(random page, RP)、单一页面(single page, SP)、重放序列(repeat sequence, RS)三种不同类型App-DDoS攻击数据,每种类型都包含每秒400次请求、每秒600次请求、每秒800次请求以及每秒1 000次请求的4种不同攻击速率.

4 . 1 数据预处理

根据Web日志处理方法,清除正常用户数据集中冗余内容,各正常用户数据集处理前后的总请求数变化如表1所示:

Table 1 The Total Request Before and After Processing
表1 数据集预处理前后总请求数对比

DatasetBefore ProcessingAfter Processingnormal_traning26873353267normal_learning16288727428normal_testing1214103632normal_testing2461958492normal_testing36885513363normal_testing4328015141

4 . 2 IAP算法运行效率验证

为验证IAP算法运行效率,分别从正常用户训练集抽取10,20,40,60,80,100,200个样本,对比IAP聚类时间、AP聚类算法与KMPCA算法的聚类时间.其中,KMPCA算法中 K =5,迭代最大次数为1 000次;AP算法中偏好值取中值,阻尼系数设置为0.9,最大迭代次数为1 000次;IAP算法偏好值取中值,阻尼系数设置为0.9,最大迭代次数为1 000次.对比结果如表2所示:

Table 2 The Time of Clustering for normal_training
表2 正常用户训练数据集聚类时间

Number ofSamplesTime of Clustering∕sKMPCAAPIAP10370.129304.88762.18320370.129304.88743.74640370.129304.88742.11460370.129304.88741.94580370.129304.88739.668100370.129304.88740.591200370.129304.88741.974

实验结果表明:在聚类正常用户训练数据集时,KMPCA算法与AP算法都在迭代次数达到1 000次时强制中止,对训练样本的聚类时间分别为370.129 s与304.887 s.由于2种算法均未涉及样本子集抽取问题,因此,训练样本的聚类时间不随着样本抽取数量的不同而发生变化.而IAP算法依据抽样数量的不同,聚类时间分布在39~63 s.当设置迭代最大次数为1 000、抽样数为10时,IAP算法运行效率与AP算法相比提高了约4倍,与KMPCA算法相比提高了约5倍;当抽样数为20~200,运行效率比AP算法提高了约6倍,比KMPCA算法提高了约8倍,运行效率上有明显优势.

4 . 3 IAP算法准确性验证

将IAP算法(抽样80)、AP算法与KMPCA算法聚类结果用于检测,设置偏差变量 φ =-3(由于欧氏距离为负数),分别从正常用户的误检率、攻击用户的检测率及ROC曲线进行对比,验证IAP算法准确性.

首先使用3种算法的聚类结果对各个时段的正常用户数据集进行误检率测试.对normal_testing1~4进行误检率测试结果如表3所示:

Table 3 False Positive Rate of KMPCA AP and LAP
表3 KMPCA AP LAP算法误检率对比 %

DatasetKMPCAAPIAPnormal_testing110.702.791.63normal_testing223.4517.9616.24normal_testing320.2919.0918.74normal_testing411.629.195.59Average16.5212.2610.55

实验结果表明:分别利用IAP算法、AP算法以及KMPCA算法聚类结果对不同时段正常用户进行检测时,IAP算法与AP算法相比,误检率降低了约17%;与KMPCA算法相比,降低了约36%.同时由于访问量越大的用户行为越接近攻击者行为,IAP算法对访问量相对较小的2:00—6:00及20:00—24:00正常用户的误检率小于访问量相对较大的8:00—12:00及14:00—18:00用户的误检率.

其次使用3种算法的聚类结果对不同攻击类型、不同攻击速率攻击用户数据集进行检测率测试,实验结果如表4所示.

实验结果可见,利用IAP算法聚类结果对不同类型、不同速率攻击用户进行检测,与AP算法相比,两者检测率基本相同;与KMPCA算法相比,检测率提高了约10%.攻击速率越高,利用IAP算法聚类结果的检测率越高,且对于单一页面攻击检测率达到90%以上,对于随机页面攻击检测率达到80%及以上,而由于重复序列攻击重放正常用户访问序列,检测率相对较低.

Table 4 Detection Rate of Different Kinds and Speed App - DDoS Attacks
表4 不同类型不同速率应用层DDoS攻击检测率 %

Attack Type400 request∕s600 request∕s800 request∕s1000 request∕sKMPCAAPIAPKMPCAAPIAPKMPCAAPIAPKMPCAAPIAPSP86.7391.7892.6787.5992.5793.4588.1594.3994.8989.2096.2397.15RP78.4980.5081.4379.7881.7281.8180.5487.1485.2682.0289.2688.44RS48.5761.2859.7249.8362.7862.8350.1863.5965.1550.3569.5870.53Average71.2677.8577.9472.4079.0279.3672.9581.7181.7773.8685.0285.37

为了更加全面地评价检测性能,采用ROC曲线分析检测算法的动态检测性能,ROC曲线描述了检测算法在不同检测阈值条件下检测率与误检率之间的折中关系,实验结果如图6所示:

Fig.6 The ROC curve of KMPCA,AP and IAP
图6 KMPCA,AP,IAP算法ROC曲线对比

综上,依赖IAP算法进行检测时,与AP算法及KMPCA算法相比,改善了检测性能,且运行效率大幅提高.

4 . 4 自学习方法有效性验证

在IAP聚类结果基础上,将分别利用ALM,NLM,DLM学习之后的聚类结果用于检测,分别从正常用户的误检率、攻击用户的检测率及ROC曲线3个方面进行对比,从而验证ALM的有效性.

首先在IAP聚类结果基础上,分别使用ALM以及DLM对normal_learning中数据进行学习;然后对各个时段的正常用户数据集进行误检率测试.normal_testing1~4误检率如表5所示:

Table 5 False Positive Rate of NLM DLM and ALM
表5 经NLM DLM ALM学习后的误检率 %

DatasetNLMDLMALMnormal_testing11.631.810.92normal_testing216.2415.439.53normal_testing318.7416.6112.89normal_testing45.596.394.18Average10.5510.066.88

实验结果表明:NLM无任何学习过程,检测结果不变;经ALM学习之后,各个时段用户的误检率都有所降低,学习使平均误检率降低了约34%;而经过DLM学习之后,与学习之前相比,2:00—6:00及20:00—24:00误检率升高,8:00—12:00及14:00—18:00误检率降低,整体误检率略有下降,学习效果差于ALM.

其次在ALM和DLM学习后的聚类结果基础上,对不同攻击类型、不同攻击速率攻击用户数据集进行检测率测试,实验结果如表6所示:

Table 6 Detection Rate of NLM DLM and ALM
表6 经NLM DLM ALM学习后不同类型不同速率应用层DDoS攻击检测率 %

Attack Type400 request∕s600 request∕s800 request∕s1000 request∕sNLMDLMALMNLMDLMALMNLMDLMALMNLMDLMALMSP92.6793.5295.8893.4593.2895.2394.8995.2896.1797.1596.4897.89RP81.4380.2892.9281.8183.9691.8785.2683.8588.1588.4487.2689.88RS59.7262.3772.3362.8363.5769.5665.1565.3870.4670.5372.1875.43Average77.9478.7287.0479.3680.2785.1581.7781.5084.9285.3785.3187.73

实验结果表明:经ALM学习之后,与学习之前相比,对不同速率、不同类型的攻击检测率都有所提升,同时随着攻击速率升高提升效果递减,对4种速率攻击平均检测率的提升比例依次为11.6%,7.3%,3.9%,2.9%;而经过DLM学习之后,与学习之前相比,对每秒400次请求与每秒600次请求的攻击平均检测率提升率分别为1.0%与1.1%,而对每秒800次请求与每秒1 000次请求的攻击平均检测率略有降低,学习效果差于ALM.

为进一步评价ALM学习性能,绘制不同方法的ROC曲线,结果如图7所示:

Fig.7 The ROC curve of NLM,DLM and ALM
图7 经NLM,DLM,ALM学习后ROC曲线对比

综上,将经ALM学习之后的聚类结果应用于自学习检测时,与NLM方法、DLM方法相比,检测率及误检率都得到改善.本文提出的ALM学习方法具有良好的学习能力,能够使类簇有效学习新用户行为属性,不断完善样本空间,提高检测性能.

5

本文针对现有基于用户行为聚类的应用层DDoS检测方法中对样本空间大小敏感、特殊行为类簇干扰检测、正常行为类簇易被攻击者探测等问题,提出一种基于改进AP聚类算法的自学习应用层DDoS检测方法.首先给出了Web日志预处理与用户行为属性提取方法;其次设计IAP算法并利用此算法聚类用户行为属性;然后提出检测方法与类簇自学习思想,在检测过程中不断完善类簇;最后通过实验证明了IAP算法的高效性、准确性以及自学习检测算法的有效性.未来我们将依据网络流量数据在中间层(路由器、交换机等)进行应用层DDoS检测,提升检测的实时性以及预测性.

参考文献

[1]Park K S, Pai V S, Lee K W. Securing Web service by automatic robot detection[C] Proc of the 2006 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2006: 255-260

[2]Walfish M, Vutukuru M. DDoS defense by offense[C] Proc of ACM SIGCOMM Conf on Applications. New York: ACM, 2006: 303-314

[3]Xie Yi, Yu Shunzheng. A large-scale hidden semi-Markov model for anomaly detection on user browsing behaviors[J]. IEEE ACM Trans on Networking, 2009, 17(1): 54-65

[4]Wang Fengyu, Cao Shoufeng, Xiao Jun. Method of detecting application-layer DDoS based on the out-linking behavior of Web community[J]. Journal of Software, 2013, 24(6): 1263-1273 (in Chinese)(王风宇, 曹守峰, 肖军. 一种基于Web群体外联行为的应用层DDoS检测方法[J]. 软件学报, 2013, 24(6): 1263-1273)

[5]Wang Jin, Yang Xiaolong, Long Keping. Http-Flood DDoS detection scheme based on large deviation and performance analysis[J]. Journal of Software, 2012, 23(5): 1272-1280 (in Chinese)(王进, 阳小龙, 隆克平. 基于大偏差统计模型的Http-Flood DDoS检测机制及性能分析[J]. 软件学报, 2012, 23(5): 1272-1280)

[6]Singh K J, Thongam K, De T. Entropy-based application layer DDoS attack detection using artificial neural networks[J]. Entropy, 2016, 18(10), 350-367

[7]She Chuyu, Wen Wushao, Zheng Kesong, et al. Application-layer DDoS detection by K -Means algorithm[C] Proc of the 4th Int Conf on EEECS. Paris: ATLANTIS, 2016: 75-78

[8]Sangjae L, Gisung K, Sehum K. Sequence-order-independent network profiling for detecting application layer DDoS attacks[J]. Eurasip Journal on Wireless Communication & Networking, 2011, 50(1): 1-9

[9]Yang Hongyu, Chang Yuan. App-DDoS detection method based on K -means multiple principal component analysis[J]. Journal on Communications, 2014, 35(5): 16-24 (in Chinese)(杨宏宇, 常媛. 基于 K 均值多重主成分分析的App-DDoS检测方法[J]. 通信学报, 2014, 35(5): 16-24)

[10]Qin Liao, Li Hong, Kang Songlin, et al. Application layer DDoS attack detection using cluster with label based on sparse vector decomposition and rhythm matching[J]. Security and Communication Networks, 2015, 8(17): 3111-3120

[11]Frey B J, Duech D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976

[12]Qin Liao, Li Hong. Feature extraction and construction of application layer DDoS attack based on user behavior[C] Proc of the 33rd Control Conf. Piscataway, NJ: IEEE, 2014: 5492-5497

[13]Zhang Zhen, Wang Binqiang, Yi Peng. Semi-supervised affinity propagation clustering algorithm based on stratified combination[J]. Journal of Electronics & Information Technology, 2013, 35(3): 645-651 (in Chinese)(张震, 汪斌强, 伊鹏. 一种分层组合的半监督近邻传播聚类算法[J]. 电子与信息学报, 2013, 35(3): 645-651)

[14]Xu Mingliang, Wang Shitong, Hang Wenlong. A semi-supervised affinity propagation clustering method with homogeneity constraint[J]. Acta Automatica Sinica, 2016, 42(2): 255-269 (in Chinese)(徐明亮, 王士同, 杭文龙. 一种基于同类约束的半监督近邻反射传播聚类方法[J]. 自动化学报, 2016, 42(2): 255-269)

[15]Bi Anqi, Dong Aimei, Wang Shitong. A dynamic data stream clustering algorithm based on probability and exemplar[J]. Journal of Computer Research and Development, 2016, 53(5): 1029-1042 (in Chinese)(毕安琪, 董爱美, 王士同. 基于概率和代表点的数据流动态聚类算法[J]. 计算机研究与发展, 2016, 53(5): 1029-1042)

[16]Jiang Jie, Wang Zhuofang, Chen Tieming. Adaptive AP clustering algorithm and its application on intrusion detection[J]. Journal on Commonications, 2015, 36(11): 118-126 (in Chinese)(江颉, 王卓芳, 陈铁明. 自适应AP聚类算法及其在入侵检测中的应用[J]. 通信学报, 2015, 36(11): 118-126)

[17]Gan Yuesong, Chen Xiuhong, Chen Xiaohui. Improved AP algotithm: M-AP clustering algorithm[J]. Computer Science, 2015, 42(1): 232-235 (in Chinese)(甘月松, 陈秀宏, 陈晓晖. 一种AP算法的改进: M-AP聚类算法[J]. 计算机科学, 2015, 42(1): 232-235)

[18]Zhang Yongzheng, Xiao Jun, Yun Xiaochun. DDoS attacks detection and control mechanisms[J]. Journal of Software, 2012, 23(8): 2058-2072(in Chinese)(张永铮, 肖军, 云晓春. DDoS攻击检测和控制方法[J]. 软件学报, 2012, 23(8): 2058-2072)

[19]Velamuru P K, Renaut R A, Guo H B. Robust clustering of positron emission tomography data[C OL] Proc of Joint Conf of CSNA. 2005 [2017-03-07]. https: math.la.asu.edu ~rosie mypapers CSNApaper.pdf

[20]Arlitt M, Williamson C. Web server workload characterization: The search for invariants[DB OL]. New York: ACM, 1996[2017-03-07]. http: ita.ee.lbl.gov html contrib ClarkNet-HTTP.html

[21]Xiao Jun, Yun Xiaochun, Zhang Yongzheng. Defend against application-layer distributed denial-of-service attacks based on session suspicion probability model[J]. Chinese Journal of Computers, 2010, 33(9): 1713-1723 (in Chinese)(肖军, 云晓春, 张永铮. 基于会话异常度模型的应用层分布式拒绝服务攻击过滤[J]. 计算机学报, 2010, 33(9): 1713-1723)

Liu Zihao , born in 1993. Master candidate. His main research interest is information system security.

Zhang Bin , born in 1969. Professor and PhD supervisor. His main research interest is cyberspace security.

Zhu Ning , born in 1981. PhD and lecturer. His main research interest is cyberspace security.

Tang Huilin , born in 1981. PhD candidate and lecturer. His main research interest is cyber security situation awareness.

Adaptive App - DDoS Detection Method Based on Improved AP Algorithm

Liu Zihao, Zhang Bin, Zhu Ning, and Tang Huilin

( Information Engineering University , Zhengzhou 450001) ( Henan Key Laboratory of Information Security , Zhengzhou 450001)

Abstract As it is complicated for training samples and difficult for updating models in behavior-based application layer DDoS detection methods, an adaptive App-DDoS detection method based on improved affinity propagation (IAP) algorithm is proposed. Firstly, to optimize the affinity propagation algorithm, we previously divide the dataset into several parts utilizing the limited priori knowledge, and merge the similar clusters for enhancing the ability of processing large amount of data. Besides, the abnormal clusters cleaning mechanism is introduced so as to avoid their interference for the detection results. Secondly, some user behavior attributes are given to represent behavior features, and the improved AP algorithm is applied to efficiently clustering the proposed attributes, as a result, improving the detection rate for abnormal users. Then by evaluating the quality of clusters with Silhouette index in real-time, a self-updating learning mechanism is put forward to support the resistance of analyzing the distribution of normal users’ attributions, which further reduces the false positive rate and increases the detection rate. The experimental results on real dataset, ClerkNet-Http, show that the proposed method is more effective and more accurate compared with the conventional AP algorithm and KMPCA algorithm, as well as can update clusters by itself in the process of detection.

Key words application layer DDoS; detection method; behavior feature; improved affinity propagation (IAP) algorithm; self-updating

针对基于用户行为的应用层DDoS检测算法中样本训练过程繁琐以及模型更新困难2个难点,提出一种基于改进AP聚类算法的自学习应用层DDoS检测方法.首先对近邻传播聚类算法改进优化:在利用少量先验知识对数据集进行预分类的基础上,结合同类簇合并机制解决样本大小敏感问题,同时引入异类簇清除机制排除特殊类簇对检测结果所造成的干扰;其次给出用户行为属性表征用户行为特征,利用IAP聚类算法实现用户行为有效聚类,提高检测精度;然后引入Silhouette指标实时监控类簇质量,设计类簇自学习更新机制,进一步降低误检率、提高检测率,并支持检测类簇的动态抗解析.实验结果表明:与传统AP聚类、KMPCA算法相比,所提方法具有较高的运行效率和较好的检测性能,并具有一定的自主优化能力.

关键词 应用层DDoS;检测方法;行为特征;改进AP聚类算法;自学习

中图法分类号 TP309

收稿日期 2017-03-07;

修回日期: 2017-08-07

基金项目 国家“八六三”高技术研究发展计划基金项目(2012AA7117058);河南省基础与前沿技术研究计划项目(142300413201)

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2012AA7117058) and the Basic and Advanced Technology Research Project of Henan Province (142300413201).