0 引言

分布式拒绝服务(Distributed Denial of Service，DDoS)攻击^[1]是一种分布的、协作的大规模拒绝服务(Denial of Service，DoS)攻击，它主要的攻击目标是大型的站点，比如商业公司、搜索引擎和政府部门的网站等。由于DDoS攻击较容易实施，且难于防范和追踪，已经成为了互联网中最严重的安全威胁之一。在DDoS攻击过程中，犯罪分子为了躲避打击，经常会伪造或通过代理改变数据包的源IP地址。为了对抗伪造源IP地址这种造成网络不可信的非法行为，IP追踪技术应运而生。

IP追踪技术已经有十多年的研究历史，主流的研究仍然集中在主动式追踪算法上。2000年，Savage等^[2]对包标记进行了深入的研究，提出了经典的概率包标记(Probabilistic Packet Marking，PPM)算法。为了检测和防御DDoS攻击，2001年，Song等^[3]在Savage的研究基础上，提出了两个改进方案：高级包标记策略(Advanced Marking Scheme，AMS)和带认证的包标记策略。

AMS算法使用哈希函数实现边地址的压缩，但由于哈希碰撞的存在，不同攻击路径上的路由器在路径重构中会被认为存在于同一条攻击路径上，这就导致AMS算法的误报率较高。将边地址压缩和数学编码思想相结合，可以有效减少重构路径所需的数据包数量，降低漏报率和误报率，提高追踪效率。

本文改进了原有的AMS算法，以边采样矩阵代替哈希函数，采用全新的边地址压缩策略，可以将整个标记算法都集成于路由器的硬件电路中，提高抗攻击能力；在受害者端，统计相同标记的重复数，并转化为边的权重值，最终得出可定性和定量分析的攻击路径图。

1 AMS算法

Song等提出的AMS算法分为AMSⅠ和AMSⅡ两种^[3]。AMSⅠ将32 b路由器i的地址R_i压缩成11 b的哈希值(另外采用5 b距离域)，两个相邻路由器的哈希异或值表示了边地址，放入边地址域，其中，地址压缩中使用两个相互独立的哈希函数h₁和h₂。路由器上的标记流程如下：当一个路由器i选择标记一个包时，它将h₁(R_i)写入边地址域，距离域置0；否则，如果发现距离域是0，即上游路由器已对这个包标记，则将数据包中的边地址和h₂(R_i)的异或值重新写入边地址域，距离域增加1。

受害者处的重构流程如下：假设受害者拥有路由器的拓扑图G_m，m为节点数，由G_m枚举相同距离值d=0, 1, 2, …的路由器地址组成的集合φ_d。由受害者处接收到的数据包得出对应相同距离值d的边地址组成的集合Ψ_d，并设攻击路径上对应于距离d的路由器地址组成的集合S_d。从离受害者最近的路由器开始进行宽度优先搜索：当d=0时，检查集合φ₀中所有的路由器地址R_i，若h₁(R_i)在集合Ψ₀中，R_i加入集合S₀。若已知集合S_d，求解S_d+1的过程如下：已知R_j在集合S_d中，集合Ψ_d+1中的边地址x，计算z=x⊕h₂(R_j)，检查φ_d+1中所有的路由器地址R_i，若h₁(R_i)=z，R_i加入集合S_d+1。

在AMSⅡ中，为了应对更大规模的DDoS攻击，由两组哈希函数代替AMSⅠ算法中的两个哈希函数，当有2^w个哈希函数时，不同路由器具有相同哈希值的概率为(1/2¹¹)^2w。同时，为了表明使用了哪个哈希函数，加入了w bit标志域，此时，边地址域减少为(11-w) b，距离域仍为5 b。

AMSⅡ算法中的标记过程与AMSⅠ算法类似，只是路由器在首次标记数据包时，需从一组哈希函数中随机选择出一个，并将所选哈希函数的编号记录至标志域，当下游路由器改写边地址域时，需使用另一组哈希函数中相同编号的一个。在受害者处的重构过程中，增加了一个阈值L。在标记信息中，假设距离为d、标志域为f的边地址为Ψ_df。如果路由器i有大于等于L个的哈希值与标记信息匹配，则路由器i被视为攻击路径上的节点。

2 基于多维伪随机序列的边采样矩阵 2.1 地址的压缩编码

为了降低重构算法的复杂度和路径误报率，有学者使用边采样矩阵代替哈希函数，对边地址进行随机采样，例如随机化链接方法^[4]、随机线性网络编码^[5-6]和单位矩阵边采样^[7]等。

设M×N维边采样矩阵A，IPv4地址M取32，IPv6地址M取64，当N < M时，路由器地址x的压缩采样过程可描述为：

$$\begin{array}{l} \mathit{\boldsymbol{y}} = \left[ {{y_N}{y_{N - 1}} \cdots {y_2}{y_1}} \right]{\bf{ = }}\left[ {{x_M}{x_{M - 1}} \cdots {x_2}{x_1}} \right] \cdot \\ \;\;\;\;\;\left[ {\begin{array}{*{20}{c}} {{a_{1,1}}}& \cdots &{{a_{1N}}}\\ \vdots & \ddots & \vdots \\ {{a_{M1}}}& \cdots &{{a_{MN}}} \end{array}} \right] = \mathit{\boldsymbol{x}} \cdot \mathit{\boldsymbol{A}} \end{array}$$

(1)

其中:a_{i, j}∈{0, 1}，“·”号表示式中的加法均指模2加法。

可以证明，如果边采样矩阵A是一个随机矩阵，则它能以很高的概率满足不相关的特性^[8-9]，能有效避免边地址的碰撞。但在实际应用中，这些随机矩阵存在存储元素容量巨大、计算复杂度高的缺点，需要设计出基于确定性构造的边采样矩阵。本文采用基于多维伪随机序列的二进制矩阵的构造方法，实现边采样矩阵的设计。

2.2 边采样矩阵的设计

在码分多址通信系统中，m序列是由带线性反馈的移存器产生的周期最长的序列。基于m序列优选对，Gold于1967年提出一种具有三值相关性的编码组，称为Gold码^[10]。Gold码组可以由二个优选的m序列“模二加”得到，具备良好的不相干特性，其硬件构造简单，产生的序列数多，这些特性很适用于边采样矩阵^[11]。

设α是GF(2ⁿ)的一个本原元，α^u1, α^u2(0 < u_i < 2ⁿ-1, i=1, 2)分别是GF(2)上2个n次本原多项式f_u1(x), f_u2(x)的首根，G(f_u1)和G(f_u2)为对应的周期为2ⁿ-1的m序列集合。将一对优选对(u₁, u₂)的m序列进行“模二加”后输出，得到Gold序列集G(f_u1, f_u2)=G(f_u1)⊕G(f_u2)(文中“⊕”均为“模二加”)，其互相关系数仅能取-1、-1-2^[0.5n+1]和-1+2^[0.5n+1]这三个值，其中，[]表示取整^[12]。

基于m序列优选对，边采样矩阵A的构造步骤^[13]如下：

1)给定M和N，计算n=[1b (N+1)]；如果mod(n, 4)=0，n=n+1；查找周期为N′=2ⁿ-1的m序列优选对集合Λ。

2)从集合Λ中选择一组优选对(u₁, u₂)，计算本原多项式f_u1(x)和f_u2(x)。

3)与f_u1(x)和f_u2(x)对应的两个最长线性反馈移位寄存器分别输出两个优选的m序列，取出两个m序列中连续2ⁿ-1项，构成码组g₁和码组g₂。

4)初始化i=1，j=1，t=0，定义作用在g₁上的一位左移变换L：L(g₁)=(g₁₁, g₁₂, …, g_1(n-1), g₁₀)，c_t=g₁。

5)如果t≥M-1，转至8)；

6)如果j≤2ⁿ-1，t=t+1，c_t=g₁⊕g₂，g₂=L(g₂), j=j+1，转至6)。

7)如果i≤2ⁿ-1，g₁=L(g₁)，t=t+1，c_t=g₁，i=i+1, j=1，转至6)。

8)码组集{c₀, c₁, …, c_M-1}构成二进制矩阵A′的M个行向量。

9)取矩阵A′的前N个列向量构成M×N维边采样矩阵A。

由以上构造方法可知，矩阵A中任意一列均为对应优选对(u₁, u₂)的Gold序列的连续2ⁿ-1项。

图 1显示了构造边采样矩阵A的硬件框图。根据本原多项式f_u1(x)和f_u2(x)设定两个n级线性反馈移存器中反馈线的连接状态，初始化寄存器状态，避免出现全“0”状态。时钟信号Clock1为全局时钟，周期为T₁；时钟信号Clock2为Clock1的分频时钟，周期T₂=(2ⁿ-1)T₁。2选1数据选择器(MUX)的功能是：当Select=0时，D=S₁；当Select=1时，D=S₂。初始化Select=1，经过2ⁿ-1个全局时钟周期，一个周期的m序列保存至缓冲存储器中。然后令Select=0，2ⁿ-1个全局时钟后产生Gold序列的一个周期码组，作为二进制矩阵A′的行向量；经过(2ⁿ-1)MT₂后，产生二进制矩阵A′。最后，A′的前N个列向量构成边采样矩阵A。

3 基于多维伪随机序列的AMS算法 3.1 边地址压缩码

将原有的AMS算法和本文的边地址压缩编码方法相结合，在AMSⅠ中需要1对边采样矩阵，而在AMSⅡ中需要2^w对边采样矩阵。如图 2所示，以AMSⅡ为例，在受害者端，已知32 b上游路由器地址x_i和下游路由器x_i-1，令w=3，基于8对边采样矩阵，在重构开始之前，计算出上游压缩码组{y_i1, y_i2, y_i3, y_i4, y_i5, y_i6, y_i7, y_i8}和对应的下游压缩码组{y′_(i-1)1, y′_(i-1)2, y′_(i-1)3, y′_(i-1)4, y′_(i-1)5, y′_(i-1)6, y′_(i-1)7, y′_(i-1)8}，“模二加”得到边地址压缩码{z_i1, z_i2, z_i3, z_i4, z_i5, z_i6, z_i7, z_i8}，再结合网络的拓扑图，作为重构算法的条件输入。

3.2 边的权重

攻击路径上距离受害者i的路由器R_i的地址为x_i，在PPM算法中，p表示路由器上的标记概率，设α_i(p)表示路由器R_i的标记信息能够被受害者收集的概率，可以推出：α₁(p)≥α₂(p)≥α₃(p)≥…。也就是说，距离受害者越远的路由器标记信息越难收集。在接收端，大多数重构算法未统计标记信息的重复数，不能在最终的攻击路径图上反映出参数α_i(p)。这一失误至少会导致两种不良后果：一个被篡改的标记信息就会导致生成了错误的攻击路径；不利于定性分析攻击路径重构失败的原因。所以，为了统计标记信息能够被受害者收集的概率，本文引入了边的权重。

设对应于一条边e_i(i-1)的边地址压缩码为z_it，在受害者处，这个值z_it在k_it个数据包的标记字段出现。则在AMSⅠ中，边的权重wg为1/k_i1；在AMSⅡ中，边的权重wg为$1/\sum\limits_{t = 1}^{2w} {{k_{it}}} $。而该条边e_i(i-1)在攻击路径上的可信度为：

${T_{i\left( {i - 1} \right)}} = \left( {1 - wg} \right) \times 100\% $

(2)

则一条攻击路径的可信度T等于该条路径上所有边可信度的乘积：

$T = \prod\limits_i {{T_{i\left( {i - 1} \right)}}} $

(3)

把标记信息出现的频繁度作为拓扑图中边的权重，在路径重构过程中考虑该因素的影响:一方面，可以弱化单个被篡改的数据包对整体路径重构的影响；另一方面，在AMSⅡ中，可以在原有定量的阈值判决基础上，进一步考虑利用可信度进行定性分析。

3.3 路径重构

基于以上分析，改进的AMSⅠ中的路径重构过程如下：

1)建立以受害者Victim为根的路由器拓扑图G，以4元组(start, end, distance, code)表示G中的边e，其中code是边地址的压缩编码。设攻击图P=(V, E)，任一边{m, n}对应的权重为w(m, n)。

2)分析收集到的数据包，将具有相同distance值i的标记信息c_ij放入集合C_i={c_i1, c_i2, …, c_ij, …}，并统计各个标记信息在数据包中的出现次数k_ij放入集合K_i={k_i1, k_i2, …, k_ij, …}。

3)当i=e.distance，如果c_ij=e.code，则标记信息合法，将边插入到图P中，e.start → V，e.end → V，{e.start, e.end} → E，w(e.start, e.end)=1/k_ij。

在改进的AMSⅡ中，对相同距离域、不同标志域的数据包，步骤2)和3)重复2^w次，最终的边的权重等于$1/\sum\limits_{t = 1}^{2w} {{k_{it}}} $。

3.4 算法流程

根据以上三节所述的改进方法，图 3给出了基于多维伪随机序列的AMS算法流程。首先，在路由器上，由一组硬件电路生成了边采样矩阵集合，并完成路由器地址的压缩编码。其次，按照AMS算法中的标记方法对路由器转发的数据包进行标记。然后，受害者从收集到的数据包中提取出这些标记信息，并利用路由器的拓扑图计算边地址压缩码。最后，将标记信息和压缩码输入路径重构算法，输出攻击图。

4 实验设计与性能分析 4.1 评价指标的对比

为了验证基于多维伪随机序列的AMS算法性能，本文以学术界广泛使用的NS2为网络模拟的实验工具。首先，为了便于计算各算法的收敛包数，通过编写OTcl脚本，生成了一条总长度为31的路径，受害者节点标号为0，并分别在节点1、2、…、31处发起攻击，攻击流量为100包/s。受害者处的31个文本文件对应了在不同的距离值下收集到的数据包标记域，文件中的一行记录对应一个数据包的标记域。在各个距离值下：以10行的增量将文件的标记域输入重构算法，如果重构结果正确，则认为成功一次；重复进行1 000次实验得到重构成功率P_suc；因为重构算法输入的包数是逐步递增的，可以认为最早满足置信度要求(P_suc≥1-1/c)的数据包数是收敛包数的实验值。实验中的参数设置为：置信度95%，即c=20；标记概率p=0.04；阈值L=4。分别计算了使用经典PPM算法^[2]、原始AMS算法^[3]和本文算法时收敛包数的理论值和实验值。

由图 4可知：无论是从理论值还是从实验值来看，收敛包数最少的均是AMSⅠ，其次是AMSⅡ，经典PPM算法的收敛性能最差。其次，基于多维伪随机序列的AMS算法，在收敛包数上与原始AMS算法一致，保持了较好的性能。

在重构过程中，可能出现误报的情况为：相同距离域的异或值通过哈希检验，被判为节点路由器，事实上并非是攻击路径上对应的路由器。所以，本文根据相同距离域的所有碎片组合对应的异或值，判断是否发生了碰撞，将碰撞次数累加，最终得出误报数。

分析图 5可知，AMSⅠ在2 000个攻击者时的误报数达到了528个，AMSⅡ随着判决阈值的增大误报数在减少；大致上看来，本文AMS算法和原始AMS算法性能较接近，很多数据点的结果还要优于后者。

4.2 算法输出的攻击图

接着，本文使用文献[14]和文献[15]中的网络拓扑模型，编写OTcl脚本进行DDoS实验仿真。如图 6所示，该网络包括：3个攻击节点0、1和2，30个中间路由器和1个受害者节点3，攻击流量为100包/s。

将受害者处收集到的标记信息分别输入对应的攻击路径重构模块，得出攻击路径上的各条边和边的权重，最终输出攻击图。因为在原始AMSⅠ和AMSⅡ中，没有边的权重的计算过程，所以，本文对它们所得攻击图的边赋权值1。

为了模拟路由器被攻陷的情况，分别在原始AMSⅠ和本文AMSⅠ收集到的标记文本中加入了伪造的标记记录：边{4, 5}和{5, 9}各2个，伪造路径(0 → 4 → 5 → 9 → 13 → 19 → 25 → 31 → 3)。

图 7显示了由原始AMSⅠ得出的包括4条攻击路径攻击图：攻击路径0(0 → 4 → 9 → 13 → 19 → 25 → 31 → 3)，攻击路径1(1 → 6 → 11 → 13 → 19 → 25 → 31 → 3)，攻击路径2(2 → 9 → 13 → 19 → 25 → 31 → 3)，伪造路径(0 → 4 → 5 → 9 → 13 → 19 → 25 → 31 → 3)。可见，原始AMSⅠ无法判断伪造的标记信息，会将伪造路径误认为攻击路径输出。

对本文AMSⅠ得出的攻击图(图 8)进行定性和定量分析可知：1)各条边的权重对应了这条边被误判的概率，越小则说明误判可能性越小，则这条边的可信度越高；2)判断节点0、1和2为3个末端节点，对应3个攻击点；3)3条攻击路径存在多条重合边，而多个攻击流合并时，权重会减小，如边{9, 13}的权重小于边{11, 13}的权重；4)边{13, 19}、边{19, 25}、边{25, 31}和边{31, 3}的权重大小类似，反映了各个路由器标记数据包的可能性是相互独立的，满足理论分析的前提条件；5)根据式(3)计算攻击路径0的可信度为98.4%，攻击路径1的可信度为98.08%，攻击路径2的可信度为98.77%。6)虚线表示攻击者伪造的边{4, 5}和{5, 6}，权重均为0.5，计算该条路径的可信度为24.7%，由于可信度较低，判为伪造路径。

图 9显示了由原始AMSⅡ得出的包括4条攻击路径的攻击图：攻击路径0，攻击路径1，攻击路径2，误报路径(23 → 29 → 31 → 3)。可见，原始AMSⅡ无法判断哈希碰撞造成的误报，会将误报路径误认为攻击路径输出。

图 10显示了由本文AMSⅡ得出的攻击图。对该攻击图进行定性和定量分析可以得出和图 8类似的结论，唯一不同的是这里也发生了一次误报：重构过程中将边{30, 31}误认为是攻击路径上的边。从对节点31所连接的三条边的可信度分析可知：边{25, 31}、边{30, 31}和边{31, 3}对应的权重分别为0.001 3、0.001 3和0.001 2，三个数值基本一致，并不存在两个攻击流合并导致的边{31, 3}权重相应减小的情况，所以，可以判断边{30, 31}是误报。

5 结语

基于多维伪随机序列的AMS算法保持了原始算法的优点，收敛包数少，计算代价和误报率低，总结以上实验结果，该算法的高效性体现如下：

1)保密性能高。

经典PPM算法和原始AMS算法存在一个安全隐患：如果攻击者通过病毒、木马注入等方式控制了一个路由器，就可以篡改经过的标记数据包，甚至可以破解路由器中的标记概率分布，迫使受害者即使分析标记信息的重复个数，也无法找出被控制的路由器。针对这个问题，本文AMS算法采用了全新的边地址的压缩编码策略，一个边采样矩阵既是压缩编码的关键，又等同于一种鉴别码。一方面，攻击者无法破解出全硬件实现的边采样矩阵；另一方面，受害者能够根据边采样矩阵对标记包进行鉴别运算。

2)计算速度快。

一般来说，软件实现的算法速度较慢，不能满足数据实时处理的要求，为了达到高速处理的性能要求，采用硬件实现边采样矩阵的构造具有重要的现实意义。另外，随着工艺技术的发展和市场需要，超大规模、高速、低功耗的新型现场可编程门阵列(Field-Programmable Gate Array，FPGA)器件不断推陈出新，可使用FPGA实现边地址的压缩编码。

3)快速判断伪造路径。

当有路由器被攻击者所控制，使得受害者端收集到的数据包中存在伪造的边地址信息时，算法如何对抗这种干扰呢？在以往的算法中，基本上没有任何的抵抗能力，很容易构造出错误的攻击路径。本文AMS算法考虑到了这个问题，统计了标记信息的重复次数，并将其转化为边的权重值，从而计算出每条攻击路径的可信度，有利于快速发现伪造路径。

4)有效降低误判的发生。

边的权重的引入，使本文可以对重构结果进行定性和定量分析，在面对无法避免的误报情况时，通过对比分析连接在同一节点上的不同边的可信度，能有效降低误判的发生。