基于偏二叉树SVM多分类算法的应用层DDoS检测方法
张斌1,2, 刘自豪1,2, 董书琴1,2, 李立勋1,2
1 信息工程大学，河南 郑州 450001
2 河南省信息安全重点实验室，河南 郑州 450001
关键词:
应用层DDoS攻击
;
HTTPGET统计模型
;
流量特征参数
;
SVM多分类器
中图分类号：TP393
文献标识码：A
doi:10.11959/j.issn.2096-109x.2018020
1 引言
分布式拒绝服务（DDoS,distributed denial of service）攻击通过控制僵尸主机发送大量数据分组，耗尽被攻击目标网络或系统资源，影响其正常工作，已成为网络安全的主要威胁之一。
当前，针对网络层、传输层DDoS攻击的检测防御技术不断完善，应用层DDoS（App-DDoS， application layer DDoS）攻击成为研究的热点。App-DDoS 攻击与服务器建立正常的连接，发送访问请求，在网络层与传输层表现正常，数据分组中TCP 3次握手及请求内容均不存在异常，与正常用户集中访问（flash crowd）造成的表象极为相似，能够有效地逃避网络层级的检测和过滤。如何实现App-DDoS的早期检测及过滤是当前研究的重点与难点。
App-DDoS 攻击检测的研究主要从日志与流量2个角度展开。其中，由于日志在攻击作用于服务器之后才会产生，基于日志挖掘的检测方法偏向于对攻击的事后挖掘，而基于流量统计分析的检测方法实时性强，更适用于App-DDoS攻击早期检测和过滤。当前基于流量统计分析的检测方法主要分为以下两类。1) 流量相关性建模的方法，如通过Jeffery距离、Sibson距离、Hellinger距离3种抽象距离来度量网络流之间相似性的方法；分别利用Total varition度量与Bhattacharyya度量评估流分布的差异度与相似度的方法；通过流量相关系数度量网络流量间差异的方法等。此类方法侧重于通过实时流量数据间相似性与差异性进行区分，忽略对历史数据的充分挖掘利用，难以进行模型的学习更新。2) 基于机器学习的方法，如将多层神经网络与遗传算法相结合，对用户HTTP GET请求的熵与熵的方差进行训练建模的方法；利用AAR模型将每个源IP地址平均HTTP GET请求数熵的时间序列映射为多维向量序列，并使用支持向量机算法分类器进行分类训练建模的方法；通过Navie Bayes、多层神经网络、SVM、决策树等机器学习算法设计一种智能IDS 系统进行检测的方法。此类方法依据机器学习算法不断挖掘训练历史流量数据，并基于训练模型进行异常检测，但主要选取持续型App-DDoS攻击流与Flash Crowd流的特征作为输入进行分类器的训练，将检测看作二分类问题，而在训练过程中忽略了上升型与脉冲型App-DDoS攻击流特征。当充分考虑正常流、Flash Crowd 流及持续型、上升型与脉冲型App-DDoS 攻击流的特征时，训练与检测过程将从二分类问题转变为多分类问题。
目前，构造多类分类器的方法主要有两类。一类是直接法，直接在目标函数上进行修改，将多个分类器的参数求解合并到一个最优化问题中，通过求解该最优化问题一次性实现多类分类。这种方法结构简单，但计算复杂度较高，不适用于实时性要求高的检测领域。另一类是间接法，通过组合多个二分类器实现多分类器的构造，主要分为一对一SVM多分类方法]、一对多SVM多分类方法及决策二叉树SVM多分类方法等。对于P分类问题，一对一分类方法中二分类器个数为
，过大的二分类器数量导致分类判决速度慢，且采用“投票法”进行决策影响了分类时的精度；一对多分类方法中二分类器个数为P，但全部的样本数据都要参与 P 个二分类器的训练，使单个分类器的训练时间较长、训练效率低；决策二叉树多分类方法中二分类器个数为P−1，随着二叉树层次的增加，训练的规模不断下降，训练的时间不断减少，且分类判决时不一定需要从根节点开始对所有分类器进行计算，从而减少了分类判决所需的时间，但是其分类效果受选取的二叉树结构影响较大。通过上述分析比较，拥有更好训练效率与相对简便判决过程的决策二叉树多分类方法更适用于实时性要求高的App-DDoS 攻击检测方法，但是如何选取适合App-DDoS 攻击检测领域的二叉树结构是所需解决的主要问题。
综上，为解决非突发性正常流量、Flash Crowd及上升型、脉冲型与持续型App-DDoS攻击的多分类问题，本文围绕五者在流量规模、流量趋势及源IP分布方面的差异，考虑检测的区分流程提出一种基于偏二叉树 SVM 多分类算法的App-DDoS攻击检测方法，主要贡献如下。
1) 设计一种HTTP GET统计模型，通过Hash函数及开放定址防碰撞方法建立多个时间周期内源IP地址在统计模型中的索引，实现多周期内不同源IP地址HTTP GET数的快速统计功能。
2) 深入分析非突发性正常流量、Flash Crowd与App-DDoS攻击流量在数据规模、流量趋势及源IP地址分布的区别，给出时间窗内HTTP GET总数、HTTP GET方差、源IP地址熵及时间窗间HTTP GET自相关系数4个流量特征参数用于描绘用户流量特征差异。
3) 按区分突发流与非突发流、在突发流中区分Flash Crowd与App-DDoS攻击流及在App-DDoS攻击流中区分具体类型的顺序建立偏二叉树 SVM训练模型，并进一步提出基于偏二叉树SVM多分类算法的App-DDoS攻击检测方法，相比传统的二分类App-DDoS攻击检测方法，通过划分检测类型、逐层训练检测模型提升检测性能。
下面分别介绍统计空间模型、流量特征参数及基于偏二叉树 SVM 多分类算法的 App-DDoS检测方法。
2 统计空间模型
HTTP GET是用户访问Web服务器的主要标识，准确高效收集HTTP GET标识数据是进行流量特征参数计算的重要前提，本节设计一种HTTP GET统计空间模型，定义如下。
定义1 （HTTP GET统计空间模型）假设测量周期内最大源IP地址数为n，以一定的周期连续地测量任意一对源—目的节点之间的 HTTP GET数，所有测量值组成一个
的HTTP GET统计空间S，称为该目的节点的HTTP GET统计空间，其中，T表示测量的周期数，流量空间的横轴值x与纵轴值y分别为源节点IP地址前16 bit与后16 bit经Hash函数及开放定址防碰撞方法映射的值，流量空间的竖轴坐标值z为采样周期数，流量空间的任一元素s(i,j,k)表示第k个周期内横轴值i与纵轴值 j所对应源节点上的HTTP GET数测度大小。
其中，源—目的节点对由所有访问者与受保护的服务器组成；
为不小于
的最小整数；Hash函数如式(1)所示，由于
值不小于n，因此Hash函数的模值取
，并通过开放定址防碰撞的方法表示所有n个源IP地址，该统计空间模型如图1所示。
3 流量特征参数
非突发性正常流不影响服务器正常工作，而Flash Crowd流及App-DDoS攻击流会导致服务器瘫痪。且Flash Crowd流由用户自发访问产生， App-DDoS 攻击流由黑客通过对僵尸主机发送指令产生。通过分析以上2种情况可知，非突发性正常流、Flash Crowd流及App-DDoS攻击流主要在数据规模、流量趋势及源IP地址分布上具有显著差异，具体区别如下。
1) 规模差异。App-DDoS 攻击流与 Flash Crowd 流导致服务器瘫痪的原因为大规模流量，而非突发性正常流量通常维持在较低的规模，这不会影响服务器正常工作。
2) 趋势差异。App-DDoS攻击流是黑客通过发送指令造成的，每个用户流量HTTP GET请求数差异小且攻击分为上升型、持续型及脉冲型，而Flash Crowd流是用户独立访问造成的，每个用户流量HTTP GET请求数差异大且在服务器瘫痪时请求数逐渐降低。
3) 源IP地址分布差异。App-DDoS攻击流与Flash Crowd流不仅在HTTP GET请求数上存在差异，每个周期内源 IP 地址数量也不同。产生Flash Crowd的用户可能来自整个网络，源IP地址分布非常分散，而在一次App-DDoS攻击中，源 IP 地址分布受到攻击者数量或僵尸网络规模的限制会相对集中。
为详细刻画上述3个方面差异，从同一周期内数据变化角度提出HTTP GET总数、HTTP GET方差及源IP地址熵等特征参数，从不同周期间的数据变化角度提出HTTP GET自相关系数特征参数。对于三维流量空间流量
特征参数定义如下。
1) 使用第k个周期内HTTP GET总数
Tol
k
表征非突发性正常流与 Flash Crowd 及 App-DDoS攻击的规模，即
2) 使用第k个周期内每个源IP的HTTP GET方差Vk与T个不同周期间的HTTP GET总数自相关系数A(τ)分别表征 Flash Crowd 与 3 种类型App-DDoS攻击的趋势，即
其中，当s
ijk
≠0时，b
ijk
=s
ijk
，即测量值为 0 时无实际含义；s
k
为第k个周期内所有数据，E(⋅)为期望；
为流量空间S标准差，可表征周期内数值波动的大小；τ为延迟，k+τ表示周期k之后的第τ个周期；根据自相关系数的定义，自相关系数的取值范围为[−1,1]，可表征不同周期间相关性程度，取值的绝对值越大相关性越高。
3) 使用第 k 个周期内源 IP 地址熵E
k
表征Flash Crowd与3种类型App-DDoS攻击的源IP地址分布，即
其中，
，且
。根据熵的定义，
E
k
取值越小表明分布越有序，反之，取值越大表明分布越杂乱无章。
4 多分类检测方法
在上述HTTP GET统计空间与表征流量差异的特征参数基础上，本节提出一种基于偏二叉树SVM多分类算法的App-DDoS检测方法，解决非突发正常流、Flash Crowd 流及 3 种类型App-DDoS 攻击流的多分类问题。相比传统二分类的App-DDoS检测方法，通过丰富的训练数据与细化检测粒度提升检测性能。下面分别介绍基于偏二叉树的 SVM 多分类算法以及基于该算法的App-DDoS检测方法。
4.1 基于偏二叉树的SVM多分类算法
上文已分析指出拥有更好训练效率与相对简便判决过程的决策二叉树多分类方法更适用于实时性要求高的App-DDoS攻击检测方法。此类方法是以二叉树的形式组合多个二分类器构造实现多分类器，因此需要解决二分类器选取与二叉树结构选取2个问题。
针对二分类器选取问题，选取 SVM 算法作为二分类器，该算法建立在 VC（VapnikChervonenkis）理论和结构风险最小化原则（SRM,structural risk minimization）基础上，通过构造一个最优分类超平面，实现未知样本类别的判断，表现出了良好的泛化性能，适合解决小样本和非线性问题，同时解决了维数灾难、过学习和局部极小等常见问题，是当前机器学习的重要方法。
对于二分类问题，给定训练样本(u
i
,v
i
)，
，u
i
∈R
d
，v
i
∈{−1,1}（l为训练样本数量；R为实数域；d为样本特征维数；v
i
为样本标签，1与−1分别代表不同类型样本）， SVM 算法的最优超平面构造可转化为一个二次规划问题。
其中，α
i
为Lagrange乘子，K(u
i
u
j
)为核函数， b为常数。
针对二叉树结构选取问题，考虑本文的分类流程为先区分出非突发流与突发流，再在突发流中区分Flash Crowd流与App-DDoS攻击流，最后依据 App-DDoS 攻击流类型依次区分持续型App-DDoS攻击、脉冲型App-DDoS攻击及上升型App-DDoS攻击，此流程近似于偏二叉树结构，因此选取基于偏二叉树 SVM 多分类算法（PBT-SVM,partial binary tree based SVM algorithm）进行样本训练，训练流程如图2所示，具体步骤如下。
步骤 1 计算训练数据集N,F,A1,A2,A3的HTTP GET总数(N,F,A1,A2,A3)Tol作为输入，通过 SVM 算法训练超平面 H1 区分 N 与F,A1,A2,A3，其中，N,F,A1,A2,A3分别代表非突发性正常流、Flash Crowd、持续型App-DDoS攻击、脉冲型App-DDoS攻击及上升型App-DDoS攻击的相应数据。
步骤 2 计算训练数据集 F,A1,A2,A3的HTTP GET 方差、自相关系数及源 IP 地址熵(F,A1,A2,A3)V,A,E作为输入，通过SVM算法训练超平面H2区分F与A1,A2,A3。
步骤 3 选取步骤 2 中A1,A2,A3的 HTTP GET方差、自相关系数(A1,A2,A3)V,A作为输入，通过SVM算法训练超平面H3区分A1与A2,A3。
步骤4 选取步骤2中A2,A3的HTTP GET方差、自相关系数(A1,A2,A3)V,A作为输入，通过SVM算法训练超平面H4区分A2与A3。
4.2 基于PBT-SVM算法的App-DDoS检测方法
基于PBT-SVM算法的App-DDoS检测方法通过HTTP GET统计空间收集数据，依据所计算的流量特征参数从训练的偏二叉树 SVM 模型根节点开始遍历进行流量分类，对检测结果进行学习更新，并将更新后结果用于下一次检测，检测方法如图3所示，具体步骤如下。
图3 基于PBT-SVM算法的App-DDoS攻击检测方法
步骤 1 流量空间更新。在统计新时间窗口内数据之前，先将当前流量空间内第2～T个窗口内数据依次前移覆盖前1窗口内容。然后，依据式(1)计算当前时间窗口内源 IP 对应坐标并统计该IP对应HTTP GET总数，覆盖第T个窗口内容。
步骤2 流量区分。采用遍历二叉树的思想，依据训练流程进行检测指标计算与流量类型判断，在当前节点无子节点时中止判决。检测结果为正常流量时允许直接访问；检测结果为 Flash Crowd 流时设置限制访问及排队机制；检测结果为某一具体类型App-DDoS攻击时，依据攻击类型选取不同的防护策略。
步骤3 区分结果的反馈学习。 将当前周期的检测结果反馈给训练模块进一步训练，并在更新后结果的基础上重复步骤1与步骤2进行下一次检测。
5 实验分析
本文选取FIFA World Cup中1998年5月10日8～9时的数据作为非突发性正常用户训练数据NTD，9～10 时的数据作为流量体积相似的非突发性正常用户检测数据NDD
1
，14～15 时的数据作为流量体积不同的非突发性正常用户检测数据NDD
2
；同时，选取1998年7月12日（决赛） 8～9时的数据作为Flash Crowd训练数据FTD， 9～10时的数据作为流量体积相似的Flash Crowd检测数据FDD
1
，14～15时的数据作为流量体积不同的Flash Crowd检测数据FDD
2
；通过大流量发生器 Sprient TestCenter C100 模拟大规模App-DDoS 攻击数据，上升型、脉冲型及持续型的训练与检测数据集分别记为ATD
1
～ATD
3
与ADD
1
～ADD
3
，其中，C100 模拟的实验数据中Client（客户）参数设置主要包括：1) 负载中发送数据的计量单位，攻击阶段数设置及每阶段的峰值、上升时间、稳定时间；2) Actions中访问页面内容；Subnets中子网网段，即模拟的客户端数。
5.1 特征参数验证
为了验证所提指标的合理性，下面分别给出数据集的4个特征。
首先，以1 min为时间窗口给出正常用户与Flash Crowd的HTTP GET总数统计结果，分别如图4、图5所示。
图5 Flash Crowd训练及检测数据集统计结果
实验结果表明，Flash Crowd 的 HTTP GET数总量分布在4 100～6 000与8 100～9 900这2个范围内，非突发性正常用户总量分布在210～1 160之间，相比而言，非突发性正常用户数据集HTTP GET总数远小于Flash Crowd数据集。故HTTP GET总数可表征两者的流量规模差异。
同时，通过 C100 模拟攻击流量时具体参数如表1所示。其中Trans/s表示链接/秒，Random表示对目标Web服务器随机访问，参数依据如下。
1) 攻击时间与等数据集时间相同，且攻击分为6个阶段，每一阶段时间为统计模型最大周期容量，即攻击时间为60 min，HTTP GET统计空间模型中。
2) 表1中只给出一个阶段的参数设置，剩余阶段的参数设置与给出的参数相同，且为了保证检测的多样性，设置不同的训练集与检测集参数。
3) 脉冲型攻击在表1中只显示了5 min时间，实际为5 min脉冲峰值时间与5 min脉冲谷值15 Trans/s访问量时间（与非突发正常流总数相似），同理，脉冲型攻击实际为6 min脉冲峰值时间与4 min脉冲谷值15 Trans/s访问量时间。
4) 峰值量保持与Flash Crowd平均量近似，训练集设置为120 Trans/s，检测集设置为150 Trans/s。
其次，由于方差是在区分 Flash Crowd 与App-DDoS 攻击时使用，下面给出 3 个 Flash Crowd数据集与3个攻击训练数据集数据的方差统计结果，分别如图6、图7所示。
实验结果表明，Flash Crowd 方差分布在47～281之间，上升型App-DDoS攻击训练数据集方差分布在10～38之间，持续型脉冲App-DDoS攻击训练数据集方差分布在23～38之间，而脉冲型App-DDoS攻击训练数据集在峰值时方差分布在23～38之间，谷值时方差为0，相比而言攻击数据集方差及其波动范围均较小。故HTTP GET方差可表征两者在流量波动上的差异。
然后，给出3个Flash Crowd数据集、3个攻击训练数据集熵值统计结果，分别如图8、图9所示。
实验结果表明，Flash Crowd 熵值分布在7.68～9.21之间，上升型App-DDoS攻击训练数据集熵值分布在 0.30～0.81 之间，持续型脉冲App-DDoS 攻击训练数据集熵值分布在 0.6～0.91之间，而脉冲型App-DDoS攻击训练数据集在峰值时熵值分布在0.61～0.90之间，谷值时熵值分布在0.20～0.48之间，相比而言攻击数据集熵值及其波动范围均较小。故源IP地址熵可表征两者在源IP地址分布的差异。
最后，设置延迟τ=2，给出3个Flash Crowd数据集、3 个攻击训练数据集自相关系数，分别如图10、图11所示。
图10 Flash Crowd数据集自相关系数统计结果
实验结果表明，Flash Crowd自相关系数分布在−0.79～0.38之间，上升型App-DDoS攻击训练数据集自相关系数分布在−0.19～0.48 之间，而脉冲型App-DDoS攻击训练数据集自相关系数分布在−0.1～0.48之间，由于实验攻击具有周期性，导致上述两类攻击自相关系数近似于具有周期性且在每个周期变化临界点数值会骤然变化，同时持续型攻击流量自相关系数在0.96～1之间小范围波动。故自相关系数可表征两者在流量趋势的差异。
5.2 检测性能验证
为了验证所提方法检测性能，将其与传统的基于 SVM 二分类算法及基于 Navie Bayes二分类算法的检测方法进行检测率（TPR，true positive rate）、误检率（FPR,false positive rate）比较。其中，在本文给出的流量特征参数基础上，所提方法分别按图2与图3流程进行训练与检测，且训练过程中核函数采用线性核函数，基于 SVM 二分类算法的检测方法中训练数据集分为正常数据集（包括NTD与FTD）与攻击数据集（包括ATD1～ATD3）且训练过程中核函数同样采用线性核函数，基于 Navie Bayes 二分类算法的检测方法中训练数据集与基于 SVM 二分类算法的检测方法相同，实验结果如表2和表3所示。检测率与误检率计算式如下。
其中，negative对象包括正常流量与Flash Crowd流量、positive对象包括3种类型攻击流量。
实验结果表明，在本文给出的流量特征参数基础上，利用 PBT-SVM 算法对不同检测数据集进行测试时，与SVM及Navie Bayes算法相比，都能完全检测出非突发正常流与持续型App-DDoS攻击，但是检测Flash Crowd时误检率分别平均降低了 3.3%与 4.17%，检测上升型App-DDoS 攻击时检测率分别提升了 11.67%与13.34%，检测脉冲型App-DDoS攻击时检测率分别提升了6.66%与11.66%。同时，通过检测流程，本文所提方法可以区分出具体的App-DDoS攻击类型，而基于 SVM 二分类算法及基于 Navie Bayes 二分类算法的检测方法只能判断出攻击是否发生而无法具体区分攻击类型。
综上，本文给出的特征参数可分别表征流量规模、流量趋势、流量波动及源IP地址分布差异，且所提检测多分类方法与传统二分类方法相比拥有更好的检测性能，能有效区分出具体攻击类型。
6 结束语
本文针对现有基于流量特征的App-DDoS检测方法在训练过程中忽略脉冲型与上升型App-DDoS 攻击问题，提出一种检测多类型应用层DDoS攻击的方法。首先，通过建立源IP地址Hash 索引的方法，设计了多周期内不同源 IP 地址HTTP GET快速统计模型；其次，基于同周期内与不同周期间的HTTP GET数与源IP地址信息，给出了刻画数据规模、流量趋势及源IP地址分布差异的特征参数；然后，提出基于偏二叉树SVM多分类算法的App-DDoS检测方法，通过划分检测类型、逐层训练检测模型，快速区分出非突发正常流、突发正常流及多类型App-DDoS流；最后，通过实验证明了所提特征参数的有效性及检测方法的准确性。下一步将对骨干网进行大规模流量下的实时性验证。
张斌（1969-），男，河南郑州人，信息工程大学教授、博士生导师，主要研究方向为网络空间安全。
刘自豪（1993-），男，湖北十堰人，信息工程大学硕士生，主要研究方向为应用层DDoS攻击检测与评估。
董书琴（1990-），男，河北邢台人，信息工程大学博士生，主要研究方向为网络空间态势感知。
李立勋（1994-），男，四川都江堰人，信息工程大学硕士生，主要研究方向为动态目标防御。
《网络与信息安全学报》是由工业和信息化部主管，人民邮电出版社有限公司主办的信息安全领域的学术刊物，现为中国网络空间安全协会会刊，中国科技核心期刊、CCF推荐中文科技期刊。办刊宗旨：汇聚安全创新思想，传播学术研究成果，提升科学研发实力，服务国家信息安全。
中国网络空间安全协会会刊
中国科技核心期刊
CCF推荐中文科技期刊
