随着科技与信息化的飞速发展，日常的学习、工作、生活中都离不开网络，网络安全问题日益严峻，计算机病毒、黑客攻击等事件频出，网络安全已经上升到国家安全层面. 为了做好网络安全防护、防范网络安全风险，网络异常流量检测是一种行之有效的技术手段，也是当前学术界和网络安全界的研究热点.

自20世纪80年代开始，国内外研究人员针对异常检测已经作了大量研究. 目前，对于异常普遍采用的是Hawkins等^[1]给出的定义：异常是指在数据集合中与其他数据有较大偏差的那些数据，这些偏差让人们怀疑是由不同机制产生的，而非随机偏差. 针对时间序列数据的异常检测方面，主要可以分为数据点异常和数据序列异常. 对于数据点异常，目前主要的检测方法有：基于统计的异常数据点检测算法^[2]、基于距离的异常数据点检测算法^[3]、基于密度的异常数据点检测算法^[4]、基于聚类分析的异常数据点检测算法^[5]、基于机器学习的异常数据点检测算法^[6]等. 本文研究的网络异常流量是针对某段时间内的异常，即序列异常. 近年来，针对序列异常，国内外研究人员作了大量的研究. Keogh等^[7]提出序列的异常是那些与其他序列最不一样的序列集合，根据这项定义，给出基于距离的暴力异常发现算法（brute force discord discovery，BFDD）. 对于网络流量数据这类高维度、大体量的数据，BFDD算法因时间复杂度较高（O（n²）），在实际的异常检测过程中开销过大，因此Keogh等^[7]基于启发式异常发现算法，提出HOT SAX时间序列异常检测算法，提高了异常检测效率. Fu等^[8]提出基于哈尔小波变换的时间序列异常检测算法. Khanh等^[9]利用iSAX^[10]表示算法的优势，结合iSAX与WAT算法，提出WATiSAX异常检测算法. 孙梅玉^[11]提出将基于距离和基于密度结合到一起的GMBR-DD异常检测算法. 余宇峰等^[12]借鉴基于窗口方法中子序列分割的思想，提出基于滑动窗口预测的时间序列异常检测算法. 周大镯等^[13]利用序列重要点进行分割，提出基于k近邻的局部异常检测算法. 张力生等^[14]提出通过将时间序列按照重要点分割来检测异常子序列的算法.

本文主要针对网络异常流量序列的检测方法进行研究. 将网络流量数据转换成具有趋势特征的符号表示形式，大大降低了数据维度，利用提出的距离算法，根据基于密度的异常检测方法检测网络异常流量. 通过实验验证了提出的网络异常流量检测算法的有效性和高效性.

网络流量数据是随着时间迁移而不断变化的，为了使数据表示简单、明晰，基于时间序列模式，对网络流量数据模型和流量子序列模型给出定义.

定义1　网络流量数据模型 对于一个长度为n的网络流量数据记录，n随时间的变化不断增大，可以将网络流量数据集记为

(1) ${\rm{NF}} = \{ {f_1},{f_2}, \cdots ,{f_i}, \cdots, {f_j}, \cdots, {f_n}\} .$

定义2　网络流量子序列模型 网络流量子序列SNF是长度为l（ $l \leqslant n$）且从时刻a（ $1 \leqslant a \leqslant $ $ n - l + 1$）开始连续采样l次取得的数据序列，可以记为

(2) ${\rm{SNF}} = \{ {f_a},{f_{a + 1}}, \cdots ,{f_{n - l + 1}}\} .$

可以将其简记为 ${\rm{SNF}}[a:l]$.

定义3　子序列SNF的k近邻距离　对于给定的正整数 $k \geqslant 1$，S为所有子序列集合. 子序列SNF的k近邻距离 $k {\text{-}} {\rm{distance}}\;({\rm{SNF}})$可以由SNF到任意子序列 $o \in S$的距离 ${\rm{dist}}\;({\rm{SNF}},o)$来确定，须满足：

1）至少有k个子序列， $o' \in S\backslash \{ {\rm{SNF}}\} $，使得 ${\rm{dist}}\;({\rm{SNF}},o') \leqslant {\rm{dist}}\;({\rm{SNF}},o)$.

2）至多有k−1个子序列， $o' \in S\backslash \{ {\rm{SNF}}\} $，使得 ${\rm{dist}}\;({\rm{SNF}},o') < {\rm{dist}}\;({\rm{SNF}},o)$.

${\rm{dist}}\;({\rm{SNF}},o)$为子序列SNF的k近邻距离，记为 $k {\text{-}} {\rm{distance}}\;({\rm{SNF}})$.

定义4　子序列SNF的k近邻可达距离　对于给定正整数 $k \geqslant 1$，子序列SNF到任意子序列 $o \in S$的可达距离定义为 ${\rm{reach}} {\text{-}} {\rm{distance}}\;({\rm{SNF}},o)$，即为子序列o的k近邻距离 $k {\text{-}} {\rm{distance}}(o)$和子序列SNF与o之间的距离 ${\rm{dist}}\;({\rm{SNF}},o)$的最大值，可以记为reach- $ {\rm{distance}}\;({\rm{SNF}},o) = {\rm{max}}\;\{ k {\text{-}} {\rm{distance}}\;(o) $, dist (SNF, o)}.

定义5　子序列SNF的k局部可达密度　对于子序列 $o \in S$，将 ${\rm{dist}}\;({\rm{SNF}},o) \leqslant k {\text{-}} {\rm{distance}}\;({\rm{SNF}})$的子序列定义为SNF的邻居，记 ${N_k}({\rm{SNF}})$为子序列SNF邻居的个数. 子序列SNF的k局部可达密度可由下式计算得出：

(3) ${{\rm{lrd}}_k}({\rm{SNF}}) = { {\left( {\frac{{\sum\limits_{o \in {N_k}({\rm{SNF}})} {{\rm{reach}} {\text{-}} {\rm{distanc}}{{\rm{e}}_k}({\rm{SNF}},o)} }}{{{N_k}({\rm{SNF}})}}} \right)}}^{-1}.$

定义6　子序列SNF的局部异常因子　记为子序列SNF的邻居的平均局部可达密度与子序列SNF的局部可达密度的比值：

(4) ${{\rm{lof}}_k}({\rm{SNF}}) = \frac{{\sum\limits_{o \in {N_k}({\rm{SNF}})} {{{{\rm{lrd}}_k}(o)}/{{{\rm{lrd}}_k}({\rm{SNF}})}} }}{{{N_k}({\rm{SNF}})}}.$

定义7　子序列SNF的平均局部异常因子　记子序列SNF的局部异常因子 ${{\rm{lof}}_k}\;({\rm{SNF}})$，其中近邻指数 $k = \{ {k_1},{k_2}, \cdots ,{k_t}\} $，则子序列SNF的平均局部异常因子 ${\zeta _{{\rm{SNF}}}}$可由下式计算得出：

(5) ${\zeta _{{\rm{SNF}}}} = {{\sum\limits_{i = 1}^t {{{\rm{lof}}_{{k_t}}}({\rm{SNF}})} } / t}.$

局部异常因子（local outlier factor，LOF）^[15]反映子序列SNF的异常程度，即LOF越大，说明位于子序列SNF周围的子序列数量越少，即具有较低的局部可达密度，表明该子序列SNF很有可能是异常的.

根据网络流量模型的定义可知，为了能够支持流数据的异常检测，支持通过滑动窗口（sliding window）模型来检测当前窗口的网络流量数据. 滑动窗口^[16]模型是时间序列流数据挖掘与分析的重要工具之一，在时间序列的降维简化表示方法^[17-19]中经常用到. 考虑到网络流量的数据规模，一般需要先对数据进行降维表示，然后基于降维表示后的结果进行异常检测分析. 关于降维表示，国内外研究人员已经作了大量研究^[18-21]. 其中聚合符号表示（symbolic aggregate approximation，SAX）方法是利用符号对序列数据进行降维简化表示，并提供了相应的距离计算方法. 通过SAX方法降维表示后，能够大幅降低数据维度，降低异常检测的复杂度. 该方法只依靠分段的均值来进行符号转化，不可避免地丢失了原有序列的数据特征. 随着分段的长度增加，丢失的数据特征越多. 对于网络流量这类时间序列数据，数据的趋势特征是非常重要的一种属性.

笔者在前期的工作中，提出2种以数据趋势特征为分割依据的降维表示方法，分别是基于特征分割的符号聚合近似方法^[18]（feature-based dividing symbolic aggregate approximation，FD-SAX）和基于特征的时间序列在线分割算法^[19]（feature-based online segmentation algorithm，FOS）. 本文利用FD-SAX的表示思想，结合符号表示与FOS算法的分割结果，将网络流量数据转换成包含7项特征值的若干子序列集合，开展异常子序列的检测.

提出基于特征符号表示的网络异常流量检测算法（network traffic anomaly detection based on feature-based symbolic representation，NAAD-FD）.

网络流量随着在时间维度上的不断变化，形态上会呈现不同的变化趋势，这种趋势能够反映一定时间段内网络流量的走向. 根据趋势的变化可以来提取趋势转折点^[20]（turning point，TP），依此作为分割网络流量数据为子序列的依据.

定义8　网络流量趋势转折点 对于一个网络流量数据NF，若数据点 ${f_i}$满足以下任一项不等式，则数据点 ${f_i}$记为网络流量趋势转折点（network trend turning point，NTTP）.

(6) ${\rm{NTTP}} = \left\{ \begin{array}{l} {f_{i - 1}} > {f_i} < {f_{i + 1}} , \\ {f_{i - 1}} > {f_i} = {f_{i + 1}}, \\ {f_{i - 1}} = {f_i} < {f_{i + 1}} , \\ {f_{i - 1}} < {f_i} > {f_{i + 1}}, \\ {f_{i - 1}} < {f_i} = {f_{i + 1}}, \\ {f_{i - 1}} = {f_i} > {f_{i + 1}} . \end{array} \right.$

NTTP虽然能够反映网络流量的数值变化，但是每个NTTP对网络流量局部走势的影响程度是不同的. 为了描述NTTP对网络流量局部走势的影响程度，定义9给出NTTP权重的定义.

定义9　NTTP权重 对于一个网络流量数据NF，其中包含的c个网络流量趋势转折点为 $\{{{\rm{NTTP}}_1},{{\rm{NTTP}}_2}, \cdots ,{{\rm{NTTP}}_c}\} $，记 $\mu $为当前网络流量序列的均值，则NTTP权重记为

(7) ${{\rm{TPW}}_i} = \left| {{{\rm{NTTP}}_i} - \mu } \right|;\;\;\;\;1 \leqslant i \leqslant c.$

在获取网络流量数据中NTTP以及TPW后，可以利用FOS^[19]算法对原始网络流量数据进行分段，表示为

(8) $\overline {{\rm{NF}}} = \{ (\overline {{s_1}} ,{w_1}),(\overline {{s_2}} ,{w_2}), \cdots ,(\overline {{s_N}} ,{w_N})\} .$

式中： $\overline {{s_i}} $和 ${w_i}$分别为第i个子序列的均值和长度，N为分段子序列的数量.

对 $\overline {{\rm{NF}}} $进行离散化处理，对照查找表，将子序列均值 $\overline {{s_i}} $转化为符号表示，记 ${\tilde s_i}$为每个子序列的符号，如下：

(9) $\tilde {\rm{NF}} = \{ ({\tilde s_1},{w_1}),({\tilde s_2},{w_2}), \cdots ,({\tilde s_N},{w_N})\} .$

为了进一步描述每个子序列的特征，将子序列SNF的最大值 ${\max_i}$、最小值 ${\min_i}$、均值 ${{\rm{ave}}_i}$、起始值 ${{\rm{sv}}_i}$和结束值 ${{\rm{ev}}_i}$增加到子序列的特征集合中. 综上所述，网络流量子序列 SNF[a:l]的特征集合表示为

(10) ${\tilde {{\rm{SNF}}_i}} = ({\tilde s_i},{w_i},{{\rm{max}}_i},{{\rm{min}}_i},{{\rm{ave}}_i},{{\rm{sv}}_i},{{\rm{ev}}_i}).$

为了利用定义3~6计算网络流量的异常程度，给出子序列特征集合表示的距离计算公式.

定义10　子序列特征集合表示距离　设定 ${{\rm{S}}\tilde {{\rm{NF}}_x}} $和 ${\rm{S}}\tilde {{\rm{NF}}_y}$为子序列 ${{\rm{SNF}}_x}$和 ${{\rm{SNF}}_y}$的特征集合表示结果，则两者之间的距离定义为

(11) $\begin{split} {\rm{dist}}&\;(\tilde {{\rm{SNF}}_x},{\tilde{\rm{SNF}}_y}) = \left[{(d\;({{\tilde s}_x},{{\tilde s}_y}))^2} + {({w_x} - {w_y})^2} +\right. \\& {({\max}_x - {\max}_y)^2} + {({\min}_x - {\min}_y)^2} + \\& \left.{({{\rm{ave}}_x} - {{\rm{ave}}_y})^2} + {({\rm{td}}({\rm{S}}{\tilde {\rm{N}}}{{\rm{F}}_x},{\rm{S}}{\tilde {\rm{N}}}{{\rm{F}}_y}))^2}\right]^{1/2}. \end{split}$

式中： $d\;({\tilde s_x},{\tilde s_y})$为符号距离， ${\rm{td}}\;({\tilde {{\rm{SNF}}_x}} ,{\tilde {{\rm{SNF}}_y}} )$为两者的趋势距离^[21].

提出的NAAD-FD网络流量异常检测算法结合时间序列的降维简化表示和相似性比较方法，基于密度的局部异常因子思想，将表示后的流量子序列作为研究对象，改进局部异常因子的计算方法，得出流量子序列的异常程度，得到异常子序列.

LOF是Breunig等^[15]提出的可以用于高维数据集异常检测的算法. LOF算法的核心思想在于计算一个异常得分来反映数据的异常程度，这个异常得分取决于一个数据对象相对于周围相邻数据对象的孤立程度，即一个数据对象跟周围邻近的数据对象的相对密度. LOF越大，说明所处位置的密度越小于周围数据对象所处位置的密度，越有可能是异常数据对象. 本文的研究对象是网络流量数据，该类数据具有明显的时序特征，且是连续数据. NAAD-FD算法首先将网络流量数据序列转化为子序列特征集合表示模式，即将研究对象从连续的序列数据转化为离散的 ${\tilde {\rm{SNF}}} $对象，通过提出的子序列特征集合表示距离计算方法计算对象间的相似性，得到每个 ${\tilde{\rm{SNF}}} $对象的平均局部异常因子，得出异常的 ${\tilde{\rm{SNF}}} $对象和异常子序列. 如图1所示为提出的NAAD-FD算法的检测原理模型. 将每个 ${\tilde{\rm{SNF}}} $对象表示成一个圆圈，其中圆圈的半径用序列长度w表示. 利用提出的 ${\rm{dist}}\;({{\tilde{\rm{SNF}}}_x} ,{\tilde {{\rm{SNF}}_y}} )$距离计算方法计算每个对象的平均局部异常因子，如图1所示，右下角的3个 ${{\rm{S}}\tilde {\rm{N}}{\rm{F}}} $对象具有相近的平均局部异常因子，左上角实心对象 ${\tilde {{\rm{SNF}}_x}} $距离其他对象较远，平均局部异常因子较大，可以判断为异常对象，则 ${\tilde {{\rm{SNF}}_x}} $对象所代表的某段序列数据可以判定为异常序列.

网络异常流量检测算法NAAD-FD从整体上可以分为3个阶段，伪代码如算法1所示.

1）数据准备. 随着网络流量进入缓冲区cs，当缓冲区cs满时，可以对当前缓冲区进行异常流量检测. 在算法1第3行找到网络流量转折点^[18]，根据网络流量转折点和字母表大小，将缓冲区cs内的网络流量数据转换成子序列特征集合表示模式（第4行）.

2）异常检测处理. 在完成降维表示后，根据定义10可知，初始化表示子序列的距离矩阵（第5行）. 根据距离矩阵可知，结合定义3~6，可以计算每个子序列在近邻指数k下的异常因子；将近邻区间内的异常因子求均值^[4]，得到每条子序列的最终异常因子. 若异常因子明显大于1，则将该子序列加入异常子序列集合中（第6~9行）.

3）网络流数据持续检测. 在完成当前缓冲区的异常检测后，清空缓冲区cs. 若还有待处理的网络流量数据，则算法返回第1行继续执行；否则，输出异常子序列结果.

算法1　NAAD-FD

输入　网络流量模型NF，字母表大小a，缓冲区大小cs，单点最大误差百分比Percent，近邻指数 $k \in [\min k,$ $ \max k]$.

输出　网络异常流量子序列集合NAList.

1. 网络流量数据进入缓冲区cs.

2. If 缓冲区cs已满：

3. NTTPList = calculateNTTPsInCs（cs）；

4. EFOSSAXList = efossaxRepresent（cs，a，NTTPList，Percent）；

5. distMatrix[][] = initDistanceMatrix（EFOSSAXList）

6. 计算不同k指数下， $\tilde {\rm{SNF}} $的局部异常因子

7. 计算每个 $\tilde {\rm{SNF}} $的平均异常指数ζ

8. If ζ 明显大于1:

9. 　NAList.add（SNF）

10. 清空缓冲区cs

11. If 尚有网络流量数据待处理：

12. 　go to Line 1

13. Else

14. 　return NAList

提出的NAAD-FD网络异常流量检测算法使用符号化降维表示的技术，在符号化降维表示中，字母表a 的选择将影响数据序列在振幅域的划分程度. 设计实验来对比字母表参数a对NAAD-FD算法结果的影响，以分析NAAD-FD算法对字母表参数a的敏感性. 利用仿真方法^[22]生成时序数据，设定字母表a从3递增至6，递增步长为1. 为了排除算法其他参数对实验结果的影响，其他参数均固定. 实验参数的设定如表1所示.

为了研究字母表a对实验结果的影响规律，列出平均局部异常因子ζ最大的前5个子序列，其中子序列序号为降维简化表示后 ${\tilde {\rm{SNF}}} $的索引位置. 实验结果如表2所示.

从表2的实验结果可以看出，在相同的参数条件下，NAAD-FD取不同的字母表大小得到了相同的异常序列，且ζ变化波动不大，表明该算法对字母表大小的选取具有普遍有效性和健壮性. 在后续的实验中，统一将字母表大小设置为a=3.

为了使得算法得出的异常结果更具有鲁棒性，设计实验用于比较不同近邻指数k的选取对异常检测稳定性的影响. 该实验的思路是选取不同的（min k，max k），在其他参数相同的条件下，得出对应的异常序列编号集合. 将集合中的异常序列出现频次进行统计，得出在不同（min k，max k）参数条件下的异常序列得分，分数计算如下：

(12) ${{\rm{KrangeScore}}_i} = \prod\limits_{{\rm{SNF}} = 1}^{{\rm{ANCount}}} {\left( {\frac{{{\rm{Occurrence\;of }}\;{\rm{SNF}}}}{\rm{KrCount}}} \right)}. $

按照异常因子从大到小排列，选取前ANCount条异常序列用于计算KrangeScore，即是每种（min k，max k）的总得分. KrCount表示（min k，max k）对的种类. 如图2所示为实验结果.

图2中，利用面积展示不同近邻指数范围选取的得分情况，面积大的表示得分较高. 从图2可以看出，当近邻指数定义在[5, 30]时，得到的结果普遍较稳定.

使用NAAD-FD算法对仿真数据进行异常检测，实验相关的参数设置如表3所示. 表中，NSD为标准化仿真数据.

仿真数据的异常序列和通过NAAD-FD检测出的异常序列如图3所示. 如图3（a）所示为仿真数据原始序列和模拟异常序列，模拟异常序列为[60:160]. 通过NAAD-FD异常检测算法检测出来的异常序列为[50:85]、[87:160]，检测出了仿真数据中的绝大部分的异常，仅有个别数据点不在模拟异常序列中. NAAD-FD算法的检测结果如图3（b）所示. 可以看出，NAAD-FD异常序列检测算法在仿真数据的异常检测中能够检测出目标异常序列.

通过仿真数据的异常检测实验结果发现，对于网络流量此类具有显著时间序列特征的数据，通过之前的研究结果表明，NAAD-FD异常检测算法的降维表示结果保留了原始数据序列的形态特征，这是时间序列类数据的重要表征参数. 结合NAAD-FD提出的距离计算方法，能够区分各分段子序列的差异程度，可以有效检测出异常目标.

为了验证NAAD-FD算法在真实网络流量数据下的有效性，选取山东大学2018年10月至2019年6月的每日网络入流量数据作为实验数据，共计250项数据记录. 流量数据如图4所示. 图中，NT为网络流量. 可以看出，网络流量在2019年1月20日至2019年3月1日左右出现大幅度下降后又大幅度上升的异常趋势.

在实验结果的基础上，将NAAD-FD算法应用到真实数据上进行检测实验. 对原始数据进行标准化. 经过异常检测计算发现，网络异常流量子序列为：[96:117]、[118:130]、[131:136]（数字为日期索引值，2018-10-13索引值为1），检测结果在实际异常区间范围内，与实际异常情况基本一致，如图5（a）中虚线标注的区域所示. 图5中，NNT为标准化后的网络流量.

为了验证NAAD-FD算法在真实数据下的有效性和正确性，使用BFDD和HOT SAX算法对该数据序列进行异常检测. 由于2种算法需要提前设定异常序列的长度，按照实际情况，将异常序列长度设置为40，实验结果如图5（b）、（c）所示. 可以发现，利用BFDD和HOT SAX算法检测出了流量大幅下降的趋势异常，异常区域与NAAD-FD结果基本一致，但没有发现大幅上升的趋势异常. 通过观察原始网络流量数据可以发现，NAAD-FD的检测结果与实际情况是相符的，NAAD-FD算法将降维表示及相似性度量均将数据的趋势特征考虑在内，能够更好地发现数据序列中的趋势变化，同时将趋势特征体现在异常指数中，因而在异常检测过程中能够有更好的检测结果.

通过该实验可以验证，利用提出的NAAD-FD网络流量异常检测算法能够有效检测出真实环境下的网络流量异常情况.

提出的NAAD-FD算法时间复杂度可以从以下4个方面进行分析. 1）对原始数据进行降维表示的时间复杂度为O（TP×M×N）. 其中，TP表示序列中平均分段转折点数量，其值远小于序列长度，M为分段子序列数量，N为序列长度. 2）子序列特征集合表示距离计算时间复杂度为O（M²）. 3）计算子序列局部可达密度的时间复杂度为O（M×min k×max k），其中min k和max k为算法初始设置的常数. 4）计算子序列异常因子的时间复杂度为O（M×min k×max k）.

综合以上分析，NAAD-FD算法的时间复杂度不超过O（TP×M×N）. 其中TP和M远低于序列长度，有效提升了NAAD-FD算法的异常检测效率，在进行大数据量的网络流量数据计算时，能够节省大量的处理时间. 为了对比NAAD-FD算法的实际运行效率，相关方法在不同数据长度下的平均运行时间（average running time，ART）如图6所示. 从图6可知，随着数据序列的递增，BFDD算法因其算法复杂度是O（n²），平均运行时间增长较快，HOT SAX算法采用了启发式的异常检测策略，算法的执行效率较高，平均运行时间增长较缓. 对比可知，NAAD-FD算法的平均运行时间最短，运行效率比HOT SAX提升约40%.

在当前日益严峻的网络安全形势下，为了准确检测网络中的流量异常情况，本文提出基于特征符号表示的网络异常流量检测算法NAAD-FD. 该算法通过标准化、符号化降维表示、计算异常因子3个步骤，实现了网络异常流量序列的检测. 本文通过对算法参数、仿真数据和真实网络流量数据进行实验分析可知，NAAD-FD算法不需要提前设定异常序列长度，且在降维表示时保留了原始数据的趋势特征，能够产生更好的检测结果，验证了NAAD-FD算法的有效性和稳定性. 针对算法的异常检测效率，通过实验比较不同算法的平均运行时间分析可知，NAAD-FD算法的执行效率较高；从时间复杂度方面分析可知，NAAD-FD算法的时间复杂度不超过O（TP×M×N），由于TP和M远低于原始数据长度，有效提升了NAAD-FD算法的异常检测效率.