0 概述

边界网关协议(Border Gateway Protocol, BGP)^[1]作为互联网域间路由标准协议, 承担着建立、维持所有自治系统(Autonomous System, AS)之间网络可达性的功能, 对整个互联网的可靠稳定运行起到至关重要的作用。但错误配置、链路故障甚至病毒爆发等均容易导致BGP异常事件的发生, 使得数据流被重定向, 形成流量黑洞或在极短时间内产生大量的BGP更新报文, 破坏全球互联网的可达性和稳定性^[2-3]。近年来, BGP异常事件频繁发生。例如, 2012年8月, 加拿大运营商Dery Telecom(AS46618)由于错误配置将其全部路由表泄露给了提供商Bell Canada(AS577), 导致产生“BGP updates storm”, 破坏了全球互联网的稳定性和部分网络的可达性^[4]; 2017年4月, 瑞士运营商SwissIX(AS200759)因配置错误发起前缀劫持攻击, 影响了全球576个自治系统和3 431个前缀的可达性, 甚至包括Google、Amazon、Twitter、Apple等^[5]。针对BGP异常, 如果能够及时准确地检测出异常事件的发生, 通过采取有效的应对措施, 则将显著降低BGP异常事件对全球互联网可达性与稳定性的影响。

本文提出一种基于改进高斯核函数的BGP异常检测(Improved Gauss Kernel Function-based BGP Anomaly Detection, IGKAD)方法。IGKAD方法采用FMS(Fisher-Markov Selector)特征选择算法、基于Manhattan距离和特征权值的改进高斯核函数以及基于网格搜索和交叉验证的模型参数寻优方法, 实现BGP更新报文激增情况的异常检测。

1 相关工作

根据事件后果, BGP异常可分为数据流劫持异常和更新报文激增异常。数据流劫持异常会导致受害网络数据流的重定向, 形成流量黑洞, 破坏受害网络的可达性。更新报文激增异常会导致在极短时间内产生大量的BGP更新报文, 破坏全球互联网的稳定性。本文主要研究BGP更新报文激增异常的检测。目前BGP异常检测方法一般分为5类, 分别是基于统计模式识别的方法、基于历史BGP更新报文的方法、基于可达性验证的方法、基于时间序列分析的方法和基于机器学习的方法。基于统计模式识别的方法^[6]采用统计概率论进行模式识别, 根据模式之间的距离函数来判定异常, 能够同时检测数据流劫持异常和更新报文激增异常。但该方法正确估计高维数据分布困难、检测速度慢, 实际应用中需人工确定模型参数的阈值。基于历史BGP更新报文的方法^[7]和基于可达性验证的方法^[8]仅能检测数据流劫持异常, 前者利用历史数据对BGP异常路由进行检测, 后者根据目标前缀的可达性验证结果进行异常检测。基于时间序列分析的方法和基于机器学习的方法能够检测更新报文激增异常。基于时间序列分析的方法^[9]将BGP更新报文视为一个多维的时间序列, 通过选择合适的滑动时间窗口实现异常检测。但该方法难以确定时间窗口的大小, 时间窗口过小会导致模型可利用的信息量不够, 时间窗口过大又会导致模型对局部异常不敏感, 使得漏报率上升。近年来, 基于机器学习的方法在BGP异常检测领域得到一定应用。从机器学习角度来看, BGP异常检测问题可抽象为二分类问题^[10], 目的是将未知的BGP更新报文识别为正常报文或异常报文, 从而实现BGP异常检测。如文献[11]从公开路由数据集中提取出37个特征, 通过支持向量机算法和隐马尔科夫模型, 达到81.5%的分类准确率。文献[12]利用决策树和模糊粗糙集方法进行特征选择, 然后基于特征子集构造极限学习机模型, 达到80.08%的分类准确率。需要指出的是, 目前基于机器学习的BGP更新报文激增异常检测方法在分类准确率上有待进一步提高。

2 FMS特征选择算法

特征是机器学习的核心, 数据和特征决定了机器学习的上限, 会直接影响模型的分类性能。因此本文采用特征提取将原始BGP更新报文转换为一组具有明显统计意义的特征, 这些特征能够较好地描述原始BGP更新报文的内部结构。经由特征提取^[8]过程得到的37个特征具体定义如表 1所示。

由于冗余特征的存在, 基于高维特征构造分类模型会增大计算开销, 并且噪声数据会降低模型分类准确率, 因此在数据预处理阶段经由特征提取^[13-14]过程得到相应特征集合的基础上, 需要进一步删除冗余和不相关特征, 寻找区分类别能力最优的特征子集, 达到降低特征矩阵的维数和计算复杂度, 同时提高模型分类准确率的目的。FMS特征选择算法^[15]能够根据Fisher线性分析和Markov随机场技术选择出能同时最大化类间距离和最小化类内距离的特征。采用FMS算法的特征选择过程与分类过程相互独立, 根据数据内在属性来衡量相关性, 并对每一个特征的权值大小进行排序, 权值越大表示该特征区分类别的能力越强。该方法效率较高, 不仅可以保证全局最优, 而且计算复杂度较低, 适合处理大规模数据。

将训练数据表示为$\left\{\left(\boldsymbol{x}_{k}, \boldsymbol{y}_{k}\right)\right\}_{k=1}^{n}, \boldsymbol{x}_{k} \in \boldsymbol{R}^{p} $表示p维特征向量, ${\mathit{\boldsymbol{y}}_k} \in \left\{ {{\omega _1}, {\omega _2}, \cdots , {\omega _g}} \right\} $表示类标签, $ \boldsymbol{C}_{i}(i=1, 2, \cdots, g)$表示第i个类, 每一个类C_i有n_i个样本。

定义1  类内散布矩阵、类间散布矩阵和总体散布矩阵分别记为S_w、S_b和S_t。

$ \begin{array}{*{20}{l}} {{\mathit{\boldsymbol{S}}_{\rm{w}}} = \frac{1}{n}\sum\limits_{j = 1}^g {\sum\limits_{i = 1}^{{n_j}} {\left( {\mathit{\boldsymbol{x}}_i^{(j)} - {\mathit{\boldsymbol{\mu }}_j}} \right)} } {{\left( {\mathit{\boldsymbol{x}}_i^{(j)} - {\mathit{\boldsymbol{\mu }}_j}} \right)}^{\rm{T}}}}\\ {{\mathit{\boldsymbol{S}}_{\rm{b}}} = \frac{1}{n}\sum\limits_{j = 1}^g {{n_j}} \left( {{\mu _j} - \mu } \right){{\left( {{\mu _j} - \mu } \right)}^{\rm{T}}}}\\ {{\mathit{\boldsymbol{S}}_{\rm{t}}} = \frac{1}{n}\sum\limits_{i = 1}^n {\left( {{\mathit{\boldsymbol{x}}_i} - \mu } \right)} {{\left( {{\mathit{\boldsymbol{x}}_i} - \mu } \right)}^{\rm{T}}} = {\mathit{\boldsymbol{S}}_{\rm{w}}} + {\mathit{\boldsymbol{S}}_{\rm{b}}}} \end{array} $

(1)

其中, x_i^(j)表示C_i类的第i个样本, $ {\mu _j} = \sum\limits_{i = 1}^{{n_j}} {\mathit{\boldsymbol{x}}_i^{(j)}} /{n_j}$表示C_i类的样本均值, $ \mu = \sum\limits_{i = 1}^n {{\mathit{\boldsymbol{x}}_i}} /n$表示总体均值。

定义2  从输入空间R^p到核空间R^D的非线性映射ϕ(·)定义如下:

$ \phi :{\mathit{\boldsymbol{R}}^p} \to {\mathit{\boldsymbol{R}}^D} $

(2)

定义3  核函数k(·, ·)满足:

$ < \phi \left( {{\mathit{\boldsymbol{x}}_1}} \right),\phi \left( {{\mathit{\boldsymbol{x}}_2}} \right) > = k\left( {{\mathit{\boldsymbol{x}}_1},{\mathit{\boldsymbol{x}}_2}} \right) $

(3)

其中, 运算 < ·, ·>代表核空间下的点积。

定义4   K和K⁽ⁱ⁾分别为n阶和n_i阶方阵, 且满足:

$ \begin{array}{*{20}{l}} {{{\left\{ \mathit{\boldsymbol{K}} \right\}}_{kl}} = k\left( {{\mathit{\boldsymbol{x}}_k},{\mathit{\boldsymbol{x}}_l}} \right)}\\ {{{\left\{ {{\mathit{\boldsymbol{K}}^{\left( i \right)}}} \right\}}_{uv}} = k\left( {\mathit{\boldsymbol{x}}_u^{(i)},\mathit{\boldsymbol{x}}_v^{(i)}} \right)} \end{array} $

(4)

其中, k, l∈{1, 2, …, n}, u, v∈{1, 2, …, n_i}, i=1, 2, …, g。

定义5   S_w、S_b和S_t在核空间下分别记为${\mathit{\boldsymbol{\widetilde S}}_{\rm{w}}} $、${\mathit{\boldsymbol{\widetilde S}}_{\rm{b}}} $和${\mathit{\boldsymbol{\widetilde S}}_{\rm{t}}} $, 对应的迹分别为:

$ \begin{array}{l} {\rm{Tr}} \left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{w}}}} \right) = \frac{1}{n} {\rm{Tr}} (\mathit{\boldsymbol{K}}) - \frac{1}{n}\sum\limits_{i = 1}^g {\frac{1}{{{n_i}}}} {\rm{Sum}} \left( {{\mathit{\boldsymbol{K}}^{(i)}}} \right)\\ {\rm{Tr}} \left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{b}}}} \right) = \frac{1}{n}\sum\limits_{i = 1}^g {\frac{1}{{{n_i}}}} {\rm{Sum}} \left( {{\mathit{\boldsymbol{K}}^{(i)}}} \right) - \frac{1}{{{n^2}}} {\rm{Sum}} (\mathit{\boldsymbol{K}})\\ {\rm{Tr}} \left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{t}}}} \right) = \frac{1}{n} {\rm{Tr}} (\mathit{\boldsymbol{K}}) - \frac{1}{{{n^2}}} {\rm{Sum}} (\mathit{\boldsymbol{K}}) \end{array} $

(5)

其中, Sum(·)表示计算矩阵所有元素的总和。

定义6  定义特征选择向量为:

$ \boldsymbol{\alpha}=\left[\alpha_{1}, \alpha_{2}, \cdots, \alpha_{p}\right]^{\mathrm{T}} \in\{0,1\}^{p} $

(6)

其中, α_k=1表明第k个特征被选中, α_k=0表明第k个特征没有被选中。

特征向量x选定的特征由x(α)=x⊙α给出, ⊙表示Hadamard积。因此, 可将最大化类分离的特征选择准则转化为一个无约束最优化问题。

$ \mathop {{\rm{argmax}}}\limits_{\mathit{\boldsymbol{\alpha }} \in {{\left\{ {0,1} \right\}}^p}} {\rm{Tr}}\left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{b}}}} \right)(\mathit{\boldsymbol{\alpha }}) - \gamma {\rm{Tr}}\left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{t}}}} \right)(\mathit{\boldsymbol{\alpha }}) $

(7)

其中, γ是自由参数, 分析表明γ≤0能得到一个更好的分类效果, 在γ的合理波动范围内, 分类器的实验效果对γ不敏感^[15]。为能处理线性不可分离和冗余特征带来的高噪声数据集, 加入l₀范数, 即特征选择准则优化为:

$ \mathop {{\rm{argmax}}}\limits_{\mathit{\boldsymbol{\alpha }} \in {{\left\{ {0,1} \right\}}^p}} \left\{ {{\rm{Tr}} \left( {{{\mathit{\boldsymbol{\tilde S}}}_{\rm{b}}}} \right)(\mathit{\boldsymbol{\alpha }}) - \gamma {\rm{Tr}} \left( {{{\mathit{\boldsymbol{\tilde S}}}_t}} \right)(\mathit{\boldsymbol{\alpha }}) - \beta {{\left\| \mathit{\boldsymbol{\alpha }} \right\|}_0}} \right\} $

(8)

其中, 正则因子β表示全局阈值。

考虑如下线性核函数:

$ \begin{array}{l} {k_1}\left( {{\mathit{\boldsymbol{x}}_1},{\mathit{\boldsymbol{x}}_2}} \right)(\mathit{\boldsymbol{\alpha }}) = 1 + < {\mathit{\boldsymbol{x}}_1} \odot \mathit{\boldsymbol{\alpha }},{\mathit{\boldsymbol{x}}_2} \odot \mathit{\boldsymbol{\alpha }} > = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 + \sum\limits_{i = 1}^p {{\mathit{\boldsymbol{x}}_{1i}}} {\mathit{\boldsymbol{x}}_{2i}}{\mathit{\boldsymbol{\alpha }}_i} \end{array} $

(9)

将式(9)代入到式(8)得到:

$ \mathop {{\rm{argmax}}}\limits_{\mathit{\boldsymbol{\alpha }} \in \left\{ {0,1} \right\}p} \sum\limits_{j = 1}^p {\left( {{\theta _j} - \beta } \right){\alpha _j}} $

(10)

θ_j定义如式(11)所示。

$ {\theta _j} = \frac{1}{n}\sum\limits_{i = 1}^g {\frac{1}{{{n_i}}}\sum\limits_{u,v = 1}^{{n_i}} {\mathit{\boldsymbol{x}}_{uj}^{(i)}\mathit{\boldsymbol{x}}_{vj}^{(i)}} } - \frac{\gamma }{n}\sum\limits_{i = 1}^n {\mathit{\boldsymbol{x}}_{ij}^2} + \frac{{\gamma - 1}}{{{n^2}}}\sum\limits_{u,v = 1}^n {{\mathit{\boldsymbol{x}}_{uj}}} {\mathit{\boldsymbol{x}}_{vj}} $

(11)

其中, θ_j用来衡量特征在类分离判别中的重要程度, 即特征权值。θ_j值越大, 表明第j个特征越重要。

对于给定的β和γ, 结合式(10), FMS特征选择算法得到一个最优的特征选择向量α^*∈{0, 1}^p, 满足:

$ {\theta _j} > \beta \Leftrightarrow \alpha _j^* = 1 $

(12)

若α_j^*=1, 则表明第j个特征被选中; 若α_j^*=0, 则表明第j个特征未被选中。

FMS特征选择算法的伪代码如算法1所示, 该算法的计算复杂度为O(n²p)。

算法1   FMS特征选择算法

输入  特征矩阵$ \mathit{\boldsymbol{X}} = \left[ {{\mathit{\boldsymbol{x}}_1}, {\mathit{\boldsymbol{x}}_2}, \cdots , {\mathit{\boldsymbol{x}}_n}} \right] \in {\mathbb{R}^{p \times n}}$, 类标签向量$\boldsymbol{Y}=\left[\boldsymbol{y}_{1}, \boldsymbol{y}_{2}, \cdots, \boldsymbol{y}_{n}\right], \boldsymbol{y}_{k} \in\left\{\boldsymbol{w}_{1}, \boldsymbol{w}_{2}, \cdots, \boldsymbol{w}_{g}\right\}, k=1, 2, \cdots, n $, 参数γ、β

输出  特征选择向量$ \boldsymbol{\alpha}^{*}=\left[\alpha_{1}^{*}, \alpha_{2}^{*}, \cdots, \alpha_{p}^{*}\right]^{\mathrm{T}} \in\{0, 1\}^{p}$

1.begin

2.for j=1→p do

3.由式(11)计算θ_j

4.if θ_j>β then

5.α_j^*=1

6.else

7.α_j^*=0

8.end if

9.return α_j^*, θ_j

10.end for

11.end

3 基于改进高斯核函数的SVM模型 3.1 SVM模型与高斯核函数

SVM^[16]是在统计学习理论的VC维理论和结构风险最小化原理基础上发展起来的一种机器学习方法。SVM在很大程度上克服了“维数灾难”“过学习”等问题, 在解决非线性及高维模式识别问题中表现出特有优势, 已成为机器学习的主流技术之一。

对于输入空间中线性不可分的情形(如图 1所示), SVM的基本思想是利用满足Mercer条件的核函数将输入空间映射到一个高维特征空间, 在高维特征空间中找到一个划分超平面, 使得样本能够线性可分。表 2列出了4类常用的核函数。Mercer条件使得相应的优化问题转化为凸问题, 因此没有局部最小。模式识别理论已经证明:如果输入空间是有限维, 即特征维数有限, 那么一定存在一个高维特征空间使得样本可分。

在表 2中, x_i、x_j表示输入向量, γ表示斜率, d表示多项式度数, r表示常数项。高斯核函数可将样本非线性地映射到更高维空间, 因此与线性核不同, 可以处理类标签和特征之间的关系是非线性的情况。文献[17]指出线性核是高斯核的一种特殊情况, 因为带惩罚参数的线性核与带参数的高斯核具有相同的性能。多项式核比高斯核具有更多的超参数, 而参数数量影响模型复杂程度, 且考虑到多项式核的表达式, 可能会导致数值计算困难。例如, 当度数d很大且$\left( {\gamma \mathit{\boldsymbol{x}}_i^{\rm{T}}{\mathit{\boldsymbol{x}}_j} + r} \right) < 1 $时, 值趋于0;当度数d很大且$ \left(\gamma \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+r\right)>1$时, 值趋于无穷大。此外, 文献[18]研究表明, Sigmoid核在特定参数下性能与高斯核几乎相同, 而且由Sigmoid核计算得到的核矩阵不一定是正定矩阵, 由它构造的SVM模型在准确性上通常也不如高斯核。因此, 本文选择基于高斯核函数的SVM模型。

3.2 基于Manhattan距离与特征权值的高斯核函数

传统高斯核函数采用Euclidean距离度量两个向量之间的距离, 但是Euclidean距离在一定程度上会增强误差较大的元素在距离计算中的作用, 影响SVM的分类准确率。基于此, 本文采用Manhattan距离作为高斯核函数中衡量两个向量之间的距离测度方法。Manhattan距离中各元素的误差对整体距离的影响相同, 使得数值更具可比性, 并且运算量较低。

如果在距离计算中能够体现出各特征对分类的贡献程度, 则将会使分类方法更贴合BGP的数据特点, 进一步提高分类准确率。据此, 引入特征权值来度量特征对分类的贡献程度, 提出基于Manhattan距离与特征权值的改进高斯核函数, 记为k′(x, y), 如式(13)所示。

$ k'(\mathit{\boldsymbol{x}},\mathit{\boldsymbol{y}}) = \exp ( - \gamma \delta (\mathit{\boldsymbol{x}},\mathit{\boldsymbol{y}})) $

(13)

其中, δ(x, y)表示两向量间的Manhattan距离, 如式(14)所示。

$ \delta (\mathit{\boldsymbol{x}},\mathit{\boldsymbol{y}}) = \sum\limits_{i = 1}^n {{\theta _i}} \left| {{\mathit{\boldsymbol{x}}_i} - {\mathit{\boldsymbol{y}}_i}} \right| $

(14)

根据平移不变核的定义^[19], 可以证明改进高斯核函数k′(x, y)的有效性。平移不变核是一类重要的核函数, 如高斯核函数。

定义7  平移不变核形如$k(\mathit{\boldsymbol{x}}, {\rm{ }}\mathit{\boldsymbol{y}}) = f(\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{y}}) $, 其中f:X→R是有界可积连续函数, 则$k(\mathit{\boldsymbol{x}}, {\rm{ }}\mathit{\boldsymbol{y}}) $是核函数的充分必要条件为f(0)>0, 且其Fourier变换满足:

$ f(\omega ) = \int_{ - \infty }^{ + \infty } f (\mathit{\boldsymbol{x}}){{\rm{e}}^{ - i < \mathit{\boldsymbol{\omega }},\mathit{\boldsymbol{x}} > }}{\rm{d}}\mathit{\boldsymbol{x}} \ge 0 $

(15)

命题   $k'(\mathit{\boldsymbol{x}}, {\rm{ }}\mathit{\boldsymbol{y}}) $是有效的核函数。

证明  因为$ f(\mathit{\boldsymbol{x}}) = \exp ( - \gamma \delta (\mathit{\boldsymbol{x}}))$, 所以$ f(\mathit{\boldsymbol{x}})$是有界可积连续函数, 且f(0)=1。又因为$ f(\mathit{\boldsymbol{x}})$ ${{\rm{e}}^{ - {\rm{i}} < \omega , \mathit{\boldsymbol{x}} > }} = {{\rm{e}}^{ - \gamma \delta (\mathit{\boldsymbol{x}}) - {\rm{i}} < \omega , \mathit{\boldsymbol{x}} > }} \ge 0 $, 所以f(ω)≥0恒成立。综上, $ k'(\mathit{\boldsymbol{x}}, {\rm{ }}\mathit{\boldsymbol{y}})$是有效的核函数, 命题证毕。

3.3 基于网格搜索与交叉验证的参数寻优方法

SVM模型的性能依赖一对重要的参数(C, gamma), 其中C为惩罚因子, 表示对误差的容忍度。C越大, 表明模型越不能容忍出现误差, 越容易导致模型过拟合; 相反地, C越小, 越容易导致模型欠拟合。C过大或过小, 均会降低模型的泛化能力, 因此参数C的适当取值对模型分类准确率和泛化能力的提升具有重要意义。gamma是多项式核、高斯核以及Sigmoid核中的一个参数, 它决定了数据映射到新的特征空间后的分布。gamma值越大, 则支持向量越少, gamma值越小, 则支持向量越多, 支持向量的个数会影响模型训练与预测的速度。

考虑到训练数据集两类样本的不平衡性(如表 3所示), 以总体分类准确率为评价目标的传统分类算法会过多关注多数类样本, 从而使得少数类样本的分类性能下降。为此, 在(C, gamma)的寻优过程中, 需要充分考虑少数类样本数据, 使两类样本在训练过程中具有相同的“话语权”。本文按照两类样本数目大小比值的反比分别为两类样本赋予权值, 这样可以有效解决数据不均衡问题。

核参数的选取是一个难点, 目前还没有国际公认的普适性方法, 实际应用中只能依靠实验比较或经验所得, 因此本文在不平衡数据集约束下结合网格搜索与交叉验证进行参数寻优(如图 2所示), 将(C, gamma)的搜索范围按照取值划分成网格, 网格中的每个点代表一种参数组合方案。网格搜索范围满足式(16), 步长为1, 即C∈{2^－5, 2^－4, …, 2⁵}且gamma∈{2^－4, 2^－3, …, 2⁰}。

$ \left\{ \begin{array}{l} {\rm{lb}}\;C \in \left[ { - 5,5} \right],且取值为整数\\ {\rm{lb}}\left( {gamma} \right) \in \left[ { - 4,0} \right],且取值为整数 \end{array} \right. $

(16)

每一个网格点按如下流程进行交叉验证:将总的训练集平均分成N个子集, 其中N-1个作为训练集, 余下1个作为测试集。每次用测试集去测试训练后的模型会得到一个分类准确率, 当N个子集均做过测试集后, 取N折交叉验证分类准确率的平均值。这样遍历网格内所有点, 取分类准确率平均值最大的点即为对应的性能最优的(C, gamma), 流程如图 3所示。需要指出的是, 本文采用5折交叉验证, 且由于(C, gamma)在搜索过程中均选取搜索范围有限且离散的值, 因此(C, gamma)可能仅为局部最优解。

4 特征效率函数

基于FMS特征选择算法可以得到各特征的权值, 将各个特征按权值降序排列, 根据排序结果将特征依次加入模型训练集中。实验发现, 因为前期加入训练集中特征的权值较大, 模型的分类准确率会逐渐提高, 但随着后期权值较低特征的加入, 且数据集中噪声和冗余数据的存在, 此时模型分类准确率的增长速度会放缓甚至使准确率下降。但与此同时, SVM模型的训练时间一直会随着特征数量的增加而增加。因此, 持续增加特征用于模型训练并不合适。基于此, 本文提出特征效率函数的概念, 以度量模型分类准确率和模型训练时间之间的关系。根据特征效率函数最大值构建特征子集, 此时的特征子集为最优特征子集, 能够使模型性能(即模型的分类准确率和训练时间)达到综合最优。

定义8  函数$f(n)(n \in \mathbb{Z}) $是模型分类准确率关于特征数量n的函数。

定义9  函数$ g(n)(n \in \mathbb{Z})$是模型训练时间关于特征数量n的函数。

由上述定义可知, 函数f(n)和g(n)分别描述了模型训练集包含一定数量的特征时, 模型的分类准确率与模型训练时间的大小。为评价模型的最优综合性能, 定义特征效率函数。

定义10   h(n)是关于特征数量n的特征效率函数, 其表达式为:

$ h(n) = \frac{{f(n)}}{{g(n)}},n \in \mathbb{Z} $

(17)

其中, h(n)描述了单位时间内分类准确率的大小, 若单位时间内分类准确率越大, 即h(n)越大, 则模型综合性能越优。

定义11  将h(n)取得最大值的点n₀作为模型的最优点。

最优点描述了当n=n₀时, 模型在单位时间内取得的最大分类准确率, 此时模型综合性能达到最优。根据特征权值排序, 基于TOP n₀构建的特征子集, 能使模型性能达到综合最优。

5 实验结果与分析 5.1 实验数据集与数据标准化 5.1.1 实验数据集

实验选取AS513(RIPE RIS、rcc04、CIXP、Geneva)提供的Slammer^[20]、Nimda^[21]以及Code Red I^[22]爆发时的BGP更新报文作为BGP异常数据集, 其中, Slammer和Nimda为训练集, Code Red I为测试集。利用libBGPdump工具^[23]将路由数据从MRT格式^[24]转换为ASCII格式, 而后基于C#编写的工具解析ASCII文件并提取特征统计信息。5天内每间隔1 min抽样统计1次特征值, 从而获得每个异常事件的7 200个样本, 经过数据标准化及特征选择后可被用作分类模型的输入。每个事件前后2天的样本被认为是正常数据集, 第3天的样本是每个异常活动的高峰期。

5.1.2 数据标准化

为消除量纲和数值大小的影响, 需要进行数据标准化处理, 从而使得不同特征能够进行比较和加权。本文采用Z-score标准化方法, 如式(18)所示。

$ \mathit{\boldsymbol{x'}} = \frac{{\mathit{\boldsymbol{x}} - \mu }}{\sigma } $

(18)

其中, μ表示总体均值, σ代表总体标准差。

本文考虑到BGP数据集来自于抽样统计, 使用样本均值代替总体均值, 用样本标准差代替总体标准差, 处理方法如式(19)所示。

$ \mathit{\boldsymbol{x'}} = \frac{{\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{\bar x}}}}{S} $

(19)

其中, ${\mathit{\boldsymbol{\bar x}}} $代表样本均值, S代表样本标准差。

5.2 评估指标

由于训练数据集是不平衡数据集, 仅由分类准确率这一指标来衡量模型的分类效果并不合适, 因此为全面准确地评价模型性能, 本文综合分类准确率和F1-Score两个评价指标来全面衡量模型性能。

5.2.1 准确率

基于分类混淆矩阵(如表 4所示)计算分类准确率。对于二分类问题, 将模型预测的类别与样本真实类别进行组合, 分为TP、FN、FP、TN4种情形, 其中:TP表示样本是正例并且预测结果也是正例; FN表示样本是正例, 却错误预测为负例; FP表示样本是负例, 预测结果为正例; TN表示样本是负例, 预测结果也是负例。

将分类准确率(Accuracy)定义为:

$ Accuracy = \frac{{TP + TN}}{{TP + FN + FT + TN}} $

(20)

5.2.2 F1-Score

F-Score是精确率(Precision)和召回率(Recall)的加权平均调和值, 精确率反映了测试集样本被模型预测的正例样本中真实正例样本所占的比例, 召回率反映了测试集样本中被模型正确预测的正例样本占总的正例样本的比例, 精确率与召回率在多数情况下两者相互制约。精确率、召回率和F-Score分别定义如下:

$ \mathit{Precison} = \frac{{TP}}{{TP + FP}} $

(21)

$ \mathit{Recall} = \frac{{TP}}{{TP + FN}} $

(22)

$ F - Score = \left( {1 + {\beta ^2}} \right)\frac{{\mathit{Precision} \times \mathit{Recall}}}{{{\beta ^2}\left( {\mathit{Precison} + \mathit{Recall}} \right)}} $

(23)

其中, β>0衡量了精确率和召回率的重视程度, β < 1时对精确率有更大影响, β>1时对召回率有更大影响。本文令β=1, 表示对精确率和召回率同等重视, 此时的F-Score又称为F1-Score, 计算公式为:

$ F1 - {\rm{Score}} = 2 \times \frac{{\mathit{Precision \times Recall}}}{{\mathit{Precison + Recall}}} $

(24)

5.3 实验结果

实验采用SVM模式识别与回归软件包libsvm-3.22^[25], 具有C、Java、Matlab、Python等多种语言版本, 代码开源, 易于扩展。本文选择在Intel^© Core^TM i7-6500U CPU @ 2.50 GHz四核处理器、4.00 GB内存、运行64位Windows 10系统的PC机上进行实验。

5.3.1 特征选择算法实验结果

基于已构造的实验训练集, 采用FMS特征选择算法计算各特征的重要性指数(即特征权值)。计算结果如图 4所示。TOP10特征及其权值如表 5所示。

5.3.2 改进高斯核函数实验结果

本文对改进高斯核函数和传统高斯核函数的分类准确率进行对比实验。如图 5所示, 当训练集为TOP10特征时, 改进高斯核函数的分类准确率达到91.65%, 优于传统高斯核函数, 达到较好的分类效果。可以看出, 随着后续低权值特征的加入, 分类准确率有下降趋势, 而模型训练时间却不断增长, 如图 6所示。训练时间为模型10次运行的CPU平均耗时。

5.3.3 特征效率函数实验结果

实验验证特征效率函数的有效性并确定最优特征子集, 实验结果如图 7所示。可以看出, 当特征数量为8时, 特征效率函数取得最大值。由定义11可知, 最优点为8。当特征子集包含TOP8特征时, 模型性能达到综合最优, 此时的分类准确率为90.37%。

5.3.4 与现有研究的比较结果

在训练集和测试集相同的情况下, 基于分类准确率和F1-Score两项评价指标, 本文对比了极限学习机(ELM)^[12]、决策树(DT)^[12]、长短时记忆网络(LSTM)^[14]、朴素贝叶斯(NB)^[26-27]、支持向量机(SVM)^[27]和本文提出的IGKAD方法, 结果如表 6所示, 其中“—”表示没有该评价指标的实验结果。可见, 在分类准确率上, 本文IGKAD方法为91.65%, 仅次于文献[27]中基于NB方法2的97.5%;在F1-Score上, 本文方法为94.27%, 优于其他方法。

5.3.5 综合实验结果

根据特征选择情况并通过选取不同的核函数, 可构造出12个SVM模型, 并对这12个SVM模型进行实验测试。实验结果表明(如表 7所示):1)采用FMS特征选择算法训练的模型要优于未进行特征选择的模型, 证明了FMS特征选择算法在提高分类准确率的同时减少了模型训练时间; 2)改进高斯核函数优于线性核函数、多项式核函数及Sigmoid核函数; 3)采用FMS特征选择算法和改进高斯核函数的模型SVM₅(即IGKAD方法)取得了最优的分类准确率(91.65%)和F1-Score(94.27%)。

6 结束语

针对BGP更新报文激增情况的异常检测问题, 本文提出一种基于改进高斯核函数的BGP异常检测方法。实验结果表明, 当训练数据集包含TOP10特征时, 该方法的分类准确率为91.65%, F1-Score为94.27%, 分类性能优于基于机器学习的BGP更新报文激增异常检测方法。下一步将结合时间序列属性, 分析历史BGP报文对BGP异常检测的影响, 进一步提高异常检测准确率。