基于IR/S的软件定义网络流量异常检测算法

兰海燕　孙鹤玲　潘昱辰

摘   要：传统重标极差分析法（Rescaled Range Analysis，R/S）检測软件定义网络（SDN，Software Defined Network）流量是否存在异常时，某节点的网络流量序列存在恒定值小区间内子序列全为零值，造成标准差为零的运算错误，为了解决这个问题，文章提出了一种改进的重标极差法（Improvement Rescaled Range Analysis， IR/S）。算法利用微元法分析法，确定一组可用的参数，将参数引入计算数据流量序列Hurst指数，并将待计算的数据流量序列等分，同时规定序列长度为2的整数次幂，分别计算R/S值，通过拟合来判断是否存在异常流量情况。改进后的方法能够达到均分子序列的要求，无需计算序列的因数，使计算过程更加简化，避免了某些长度序列因数过少、素数长度导致的拟合点过少无法收敛的现象，减少了由计算结果精确度带来的误差。将算法在Mininet环境下进行虚拟SDN仿真测试，实验结果表明，文章中的方法能够较显著区分正常与异常流量，并且在探测异常时延迟较低。

关键词：Hurst指数;重标极差法;软件定义网络;拒绝服务攻击;分形学

中图分类号： TP393          文献标识码：A

Abstract： When traditional Rescaled Range Analysis （R/S） detects whether software defined network （SDN） traffic is abnormal， subsequences are all zero in the constant value interval existing in the network traffic series of several nodes， which causes some operation error with a standard deviation of zero. An Improved Rescaled Range Analysis （IR/S） method is proposed to solve this problem. The algorithm uses the micro-element analysis method to determine a set of available parameters which is introduced into the calculated data flow sequence Hurst exponent， and divides the data flow sequence to be calculated into equal parts. At the same time， the length of the sequence is specified as an integer power of 2， and calculate R / S values separately， to determine if there is an abnormal flow condition by fitting. The improved method can meet the requirements of homogeneous molecular sequences without calculating the sequence factors. The calculation process is more simplified， avoiding inability to converge due to too few factors of some length sequence or even too few fit points which is caused by prime length， and reducing the accuracy of the calculation results. A virtual SDN simulation test of the algorithm in Mininet environment is set up， and the experimental results show that the method can distinguish between normal and abnormal traffic significantly， and detect anomalies with a lower delay.

Key words： Hurst exponent; rescaled range analysis; software defined network; denial of service attack; fractal

1 引言

网络流量与时间序列具有分形学的自相似性，正常状态下网络产生的流量与异常状态下网络产生的流量自相似性不同，利用这一特点，可以通过直接分析网络所产生的流量序列分形特征进行相互对比，从而判断某一状态下的网络与正常状态的区别。由于研究序列的分形特征不太依赖对系统基础性的假设，故针对各种时间序列都具有较为广泛的适用性。这种方法无需依赖固有模式，更具备特异性，针对具体的网络结构将产生较好的判决效果。

自Harold Edwin Hurst研究分形序列的长期持续性提出了Hurst指数作为分形特征的一个指标以来，关于该指数的实际应用，已有各类学科的大量研究产生，如故障预测[1]、降雨侵蚀[2]、脑电特征识别[3]等。对于将Hurst指数应用于传统的网络结构，已有较多相关研究。例如，Leland等学者采用R/S分析法和聚集方差法分别计算序列的Hurst指数[4];Pharande等学者使用R/S分析法结合分数高斯噪声分析DoS（Denial of Service）攻击的自相似性[5];学者Lozhkovskyi A.G.利用R/S分析法计算部分R/S序列以研究分组交换网的流量自相似特征[6]。但是，针对SDN中发生的相关攻击事件却少有推广算法提出。目前，在SDN领域有关流量检测算法的研究，有基于信息熵的深度神经网络检测法[7]、主成分分析法[8]等，但少有学者利用分形学方法对SDN流量进行研究。

2 分形学与R/S分析法

根据分形学理论，存在分数维几何形并且这种几何大量存在于自然界。从自然山川的轮廓，到气候变化趋势，都是传统几何学无法精确表述的。分形学中一个重要的概念是自相似性，该概念指一个分形几何形是由众多更小的、与这个几何形差别不大的小几何形组成[9]。而理论上讲，这种迭代是趋向于无穷的，从而导致使用传统几何学几乎无法研究这类问题。如果利用分数维布朗运动作为研究对象，将会出现以某一尺度对该布朗运动曲线进行放缩时，曲线统计特性并不发生改变的特殊现象。该尺度放缩因数一般以指数形式2H出现，H即Hurst指数。H取值在0到1之间，可以表征序列的分形特征。经过研究，H与序列特征呈现的关系如表1所示。

反持续性序列具有均值回复性，即一个上升值更可能出现在一个下降值之后，反之亦然。H越趋近于0，均值回复性越强[10]。而一个持续性序列意味着下一个值的变化方向更趋向于和上一个值的变化方向，H越趋近于1，持续性越强。

对于网络流量序列、气温序列、金融市场序列等，都可以利用Hurst指数定量描述序列的特征，目前主流的计算方法是R/S分析法[11]。要估计Hurst指数，首先必须估计重标极差对观察时间跨度的依赖性。将长度为N的时间序列划分为多个较短的时间序列长度，之后对于n的每个值，计算重标极差的平均值。H定义为时间序列的时间跨度函数，这是根据重标极差的渐进性变化特点决定的。具体为：

其中，是前n个值与均值作差的累积取值范围，是标准差，是期望，n是观察的时间跨度（时间序列内数据点的数量），C是一个常量。

给定一个长为n的序列，重标极差计算方法为[12]：

（6）计算重标极差序列

通过按照幂次规律拟合数据来估算Hurst指数，可以通过将作为的函数进行双对数坐标线性拟合，拟合直线斜率即为Hurst指数值。

利用该算法，计算如图1所示的控制器流量序列的Hurst指数。该序列以100ms为采样间隔，采集了128个样本点，样本点的值为控制器正常工作时的数据包数量。在使用Python的numpy库进行线性拟合时会提示的信息为：LinAlgError： SVD did not converge in Linear Least Squares。

产生该计算故障的原因在于该序列有较多长期连续0值，使用Python计算R/S序列时，由于在计算恒值序列，得到的极差和标准差均为0，做除法后得到nan值即无意义值，影响了线性拟合的收敛。故为了消除这种影响，需要对传统算法进行改进以适应输入序列的特性。

3 IR/S分析法

3.1算法设计

在实际情况下，网络中一段时间内流经的包数量必为一个非负实数，而且可能会出现某些节点，尤其是SDN控制器，在一定时间内没有数据包通过，使得在子序列长度较短时子序列全为0值。考虑到后续对于求解R/S时在数学上要求在分母上的标准差非零，以及使用对数拟合时自变量R（n）/S（n）需大于0的数学要求，本文提出并采用的计算方法为：

3.2 对新参数的探究

鉴于计算一个序列的Hurst指数过程需要将序列等分，分别计算R/S值并最终进行拟合。在此改进算法中，规定了待计算序列长度为2的整数次幂，这样能够达到均分子序列的要求，计算过程更加简化，无需计算序列的因数，也能避免某些长度序列因数过少甚至是素数长度导致的拟合点过少无法收敛。且该做法能够使线性拟合时的取整数，减少由计算结果精确度带来的误差。

在本节步骤（4）中计算标准差时添加微小量 的目的是避免标准差为0带来的分母为0，由于网络流量会有较长时间持续为一恒定值0，故某个子区间Ia标准差为0的情况时有发生。但是增加标准差会导致Hurst指数值略微偏大，可令尽可能小以减少影响。

对产生这一趋势的原因进行分析，不妨假设一个序列的序列是一个均值序列，即：

此时，构造函数

考察该函数的变化趋势，增加带来的的变化与S有关，故对S求偏导

由偏导数可知，S增加会使增加，这里，故存在且，即会随着S的增加而减小，其斜率随着S增大而减小。由反比例函数性质可得，由增加带来的增量随着S的减小而增加，由此更小的S，在更大的下，的减小量更多。序列越短，序列波动的程度与长序列相比更轻微，S会随着序列长度缩短而减少。于是，较短序列长度下的会在的作用下减少更多，逆时针偏移，斜率增大，H增大，且增加会导致H进一步增加。

根据使用长度为4096的随机序列、长度为4096的单调递增序列、长度为4096的正弦序列进行、、、实验得出结果可得到验证，计算结果如表2所示。如图2所示，对和序列Hurst指数值变化趋势的探究中，横坐标取以10为底的对数，可以看出更大的会使Hurst指数较原值增加更多，当越趋近于0时，值的变化越小。

在本节步骤（3）中添加的微小量保证序列不为0，从而使对数坐标有意义。取值与有关，两者数值大小将影响Hurst指数的偏移量。使用在不同数量级区間内取值的和计算一个随机序列的Hurst指数并绘制出热图，结果如图3所示。可以初步观察到，变大将影响Hurst指数增大，增大将影响Hurst指数减小。

首先对的影响进行分析，继续考察函数的特性，求对R的偏微分得：

由反比例函数性质可知，R增加会引起减小，由于，存在且，故随着R增加而增加，且增加速率随着R变大而减小，会随着增大而减小，且越小的R产生的变化越大。当序列越短时，序列上下极值的差异性会越小，R会随着序列长度缩短而减少。于是，较小序列长度下的会在的作用下，增加的幅度更大，从而导致拟合直线顺时针偏移，斜率减小，H减小，更大的会导致H减小幅度更大。

由全微分可以得出，当，此时等号代表数量级的相等，这时最小且;当时，，此时最小且，即在这两种情况下的改变量最小。

从图3中可以看到一条贯穿左上角与右下角的等值点组成的线，在右下角的点为与均取0值，在这条线上的点，颜色基本一致，对应着相同数量级下的与所对应的Hurst指数值。当与取10-5或更小的值时，即使二者数量级略有差异，对Hurst指数的取值影响以及影响变化的速度有显著减小，但当与取10-2时，即使两个参数数量级相同，也对Hurst指数有较大的影响，基本符合上述分析结果。结合实际网络流量可能的特征，在实际计算时10-5应保持在较小且相同的数量级下。经过对单调递增序列和正弦序列进行计算也得到类似的结果。

综上对取值数量级范围的讨论，本文在较小的数量级取值范围下取，作为后续计算基础。

4 异常流量检测

4.1 获取待检测数据

本文以Mininet为仿真环境建立一个虚拟SDN拓扑网络，以Ryu作为SDN控制器，设置网络连接带宽均为10Mbps。网络拓扑结构如图4所示。

进入节点h1的终端，调用SYN泛洪（SYN flood）攻击脚本向h2发起攻击，作为DoS的测试模块。利用Wireshark工具获取控制器c0、攻击节点h1、目标节点h2的流量信息，采样间隔为100ms，分别获取网络正常运行时的信息和发动攻击时的流量信息。

4.2 檢测流量状态

对于本文所用网络，在正常状态下捕获的c0、h1、h2节点流量Hurst指数情况如表3所示。

当SYN泛洪测试开启后，再捕获各节点流量并计算Hurst指数，结果如表4所示。

对正常状态下的网络和存在异常流量的网络各节点分别进行20次流量捕获与计算，做出各节点流量序列Hurst指数的箱型图，如图5所示。

由上述实验数据可以明显区分出网络正常状态与SYN泛洪状态。相比于正常状态的网络流量，控制器c0的Hurst指数明显升高，而两个终端节点的Hurst指数下降，但变化幅度小于控制器。故针对本文所用的网络拓扑结构，判定网络内部SYN泛洪发生与否的指标应设为控制器c0的Hurst指数。一旦c0节点的Hurst指数升高至0.7以上，则应该考虑网络内部可能发生了SYN泛洪攻击。

如果进一步分析这种变化的原因，主要是由于SDN的特性所决定。SYN泛洪需要向被害主机发送大量以伪造IP为源地址的SYN消息，而网络中突然出现大量新IP，导致交换机不断匹配、更新流表[13]，从而向控制器下发大量PACKET_IN请求，控制器忙于处理PACKET_IN和PACKET_OUT，导致单位时间内流量包急剧升高。

4.3 检测异常时刻

获得一个网络的异常情况Hurst指数后，就可以利用其进行检测异常发生时刻。在探测异常变化时，针对流量时间序列，用一定宽度的窗，以序列起始部分加上窗宽度的位置作为起始位置，依次向后截取序列并分析Hurst指数。对本文所用网络，检测内部SYN泛洪事件发生时刻，使用宽度为102400ms（1024个采样点）的窗对序列进行截取，计算控制器c0的Hurst指数变化情况并试图得到异常流量开始的时刻。

如表5所示，是实际攻击开始时刻与预测时刻对照表，如图6所示是一个控制器在SYN泛洪攻击发生时的Hurst指数变化情况。根据对照表可以看出该方法在判断攻击发生时刻上具有较低的延迟，一般在几秒内。根据变化情况图可以看出该方法较为稳定，异常发生时的Hurst指数与正常相比会出现大幅度变化。对异常发生时刻检测效果较好。

5 结束语

SDN环境下的网络流量检测问题，与传统网络不同的是，SDN环境下不仅需要检测终端情况，还应检测SDN控制器的状况。通过分形学中的Hurst指数，正常状态与异常状态的网络流量序列能够用量化的数字进行区分，这种方法不需要借助其他因素，可以从流量序列本身得到，特异性和可推广性都较强。本文从传统R/S分析法出发，通过引入新参数并从数学角度利用微元法分析了参数对算法造成的影响，通过实验测试具体参数的影响，确定了一组可用的参数，使该算法成功克服了网络流量序列可能存在的长期连续恒定0值带来的极差、标准差为0所造成计算出错的问题。对一段连续的序列，可以探测序列中发生的异常，这为网络状态实时检测提供了切入点。通过实验，展示了SDN环境下利用该算法分析异常的思路，最终计算得到该网络在正常状态下和异常状态下的Hurst指数分别为0.55和0.85左右，对攻击时刻判定的延迟在2s左右，证明了该算法检测异常的可行性和准确性。

参考文献

[1] 于群， 屈玉清， 石良. 基于相对值法和Hurst指数的电网停电事故自相关性分析[J]. 电力系统自动化， 2018， 42（01）： 55-60+124.

[2] 钱峰， 董林垚， 黄介生， 等. 基于Hurst指数与相关系数的降雨侵蚀力变异识别与分级方法[J]. 农业工程学报， 2018， 34（14）： 140-148.

[3] 李昕， 蔡二娟， 田彦秀， 等. 一种改进脑电特征提取算法及其在情感识别中的应用[J]. 生物医学工程学杂志， 2017， 34（04）： 510-517+528.

[4] Leland W E， Taqqu M S， Willinger W， et al. On the self-simmilar nature of ethernet traffic（extended version[J]. IEEE/ACM Transactions on Networking， 1994， 2（1）： 1-15.

[5] Pharande S， Pawar P， Wani P W， et al. Application of Hurst Parameter and Fuzzy Logic for Denial of Service Attack Detection[M]. IEEE International Advance Computing Conference， ed; 2015， 834-838.

[6] Lozhkovskyi A G. Simplified Calculation of the Hurst Coefficient by the R/S-Analysis Method[C]. Lviv， UKRAINE： IEEE， 2017： 254-257.

[7] 张龙， 王劲松. SDN中基于信息熵与DNN的DDoS攻击检测模型[J]. 计算机研究与发展， 2019， 05： 909-918.

[8] 左青云， 陈鸣， 王秀磊， 等. 一种基于SDN的在线流量異常检测方法[J]. 西安电子科技大学学报， 2015， 42（01）： 155-160.

[9] Peitgen H O， Jurgens H， Saupe D. Chaos and Fractals[M]. 2004.

[10] Rejichi I Z， Aloui C. Hurst exponent behavior and assessment of the MENA stock markets efficiency[J]. Research in International Business & Finance， 2012， 26（3）： 353-370.

[11] Zhang H Y， Kang M C， Li J Q， et al. R/S analysis of reaction time in Neuron Type Test for human activity in civil aviation[J]. Physica A Statistical Mechanics & Its Applications， 2017， 469： 859-870.

[12] Qian B， Al. E. HURST EXPONENT AND FINANCIAL MARKET PREDICTABILITY[Z]. 2007.

[13] Foundation O N. openflow-switch-v1.5.1[Z]. 2015.

作者简介：

兰海燕（1983-），女，汉族，黑龙江绥化人，哈尔滨工程大学，博士，哈尔滨工程大学，讲师;主要研究方向和关注领域：信息安全、移动边缘计算。

孙鹤玲（1996-），女，汉族，黑龙江大庆人，哈尔滨工程大学，硕士;主要研究方向和关注领域：信息安全、移动边缘计算。

潘昱辰（1997-），男，汉族，河南新乡人，哈尔滨工程大学，硕士;主要研究方向和关注领域：人工智能、信息安全。

（本文为“2020年429首都网络安全日”活动征文）