Page 216 - 《软件学报》2020年第12期

3882 Journal of Software 软件学报 Vol.31, No.12, December 2020

立、路径重构、回溯精度来提高可部署性.
本文第 1 节对单包溯源问题进行形式化描述,进而指出本文的研究动机.第 2 节介绍本文提出的 TIST 方法,
其中,第 2.1 节介绍整体架构,第 2.2 节、第 2.3 节分别介绍溯源联盟网络下的链路指纹建立和溯源分组识别策
略.第 3 节对 TIST 的性能进行评估,其中,第 3.1 节给出理论评估,第 3.2 节则采用实验仿真手段对分析结果进行
补充,第 3.3 节讨论大规模部署问题.第 4 节介绍相关工作.第 5 节总结全文,并指出下一步的工作重点.

1 问题描述和研究动机

本节首先对单包溯源问题进行形式化描述,推断出单包溯源方法应满足的性能指标,以此为参照,指出已有
方法存在可部署性不足的问题,通过分析该问题产生的根本原因,进而阐明本文研究动机.

1.1 问题描述
本文将源地址伪造的 IP 分组称为匿名分组,其中,发送和接收匿名分组的主机分别称为攻击者 A 和受害者 V;
将组成节点(路由器)由相同网络服务提供商(Internet service provider,简称 ISP)管理、连接边由相同 IGP(interior
gateway protocol)生成的网络称为自治域网络(autonomous system,简称 AS),如定义 1 所述;将自治域网络分为
Stub 和 Transit 两类,其中,Stub 域只负责转发源于自身的 IP 分组,而 Transit 域则负责为其邻居 Stub 域提供转发
服务;将组成节点由多个自治域提供、连接边由 BGP(border gateway protocol)和 IGP 共同生成的网络称为底层
路由网络,如定义 2 所述;将 IGP 生成的链路称为域内链路,将 BGP 生成的链路称为域间链路,如定义 3 所述;将
IP 包在底层路由网络的转发路径称为路由路径,如定义 4 所述;将用于链路指纹建立、完成溯源功能升级的路
由器称为溯源路由器;将包含溯源路由器的自治域称为溯源自治域;将组成节点为溯源路由器、连接边为底层
路由路径压缩生成的覆盖网络称为溯源网络,如定义 5 所述;将溯源网络上从 V 到 A 的路径称为攻击路径,如定
义 6 所述.
定义 1. 自治域网络可表示为一个无向图 G AS =(N AS ,E AS ,T AS ),其中:N AS ={n 1 ,…,n k }是普通路由器集合;E AS 是
由 IGP 生成、连接两个普通路由器的链路集合;T AS 是自治域类型变量,0 为 Stub,1 为 Transit.假设顶点 n i 与 n k
相邻,链路(n i ,n k )记为 n i n k .
定义 2. 底层路由网络可表示为一个无向图 G R =(N R ,E R ,M R ),其中,N R 是普通路由器集合,E R 是由 IGP 或 BGP
生成、连接两个路由器的链路集合,M R 是自治域集合.
定义 3. 给定虚拟链路 y i y i+1 ,如果 y i ∈N ASi 且 y i+1 ∉N ASi ,则 y i y i+1 被称为域间链路;如果 y i ,y i+1 ∈N ASi ,则 y i y i+1 被
称为域内链路.
定义 4. 路由路径可表示为一个非空图 P R =(V R ,L R ),其中:V R ={x 0 ,x 1 ,…,x k },V R ⊆N R ;L R ={x 0 x 1 ,x 1 x 2 ,…,x k−1 x k },
L R ⊆N R .为了方便,可用顶点自然顺序排列表示路径,记为 x 0 P R x k =x 0 x 1 …x k ,并称 P R 是一条从 x 0 到 x k 的路由路径.
性质 1. 给定 G R =(N R ,E R ),∀x i ,x j ∈N R ,根据路由拓扑的连通性,可推出至少存在一条路由路径 x i P R x j .
定义 5. 溯源网络是由底层路由网络进行点压缩操作而获得的,也可表示为一个无向图 G T =(N T ,E T ,M T ),其
中,N T ⊆N R 是溯源路由器集合,E T 是连接两个溯源路由器的虚拟链路集合,M T ⊆M R 是溯源自治域集合.虚拟链路
的生成方法如下:∀v i ,v j ∈N T ,必然存在路由路径 v i P R v j =v i x i+1 …x j−1 x j ,若 v i P R v j ∩N T =∅,则删除路径顶点 x i+1 …x j−1 ,将
v i ,v j 用边连接起来,生成虚拟链路 v i v j .
性质 2. 如果 N T =N R ,则 E T =E R ,G T =G R ,M T =M R .
s
s
定义 6. 攻击路径 P 是指匿名包 z 在溯源网络上的转发路径,表示为 P =(V A ,L A ),其中:V A ={y 0 ,y 1 ,…,y k },
A A
V A ⊆N T ;L A ={y 0 y 1 ,y 1 y 2 …,y k−1 y k },L A ⊆E T .顶点 y 0 和 y k 分别称为攻击入口和出口.
所谓单包溯源问题就是在溯源网络上寻找一种能为每个转发分组建立链路指纹的方法,使得网络服务提
供商只利用单个样本分组就能够完成指纹匹配和提取,重构出整条攻击路径.很明显,除了溯源网络构建,解决
单包溯源问题的另一个难点就在于链路指纹建立.至于指纹提取,它只是指纹建立的逆过程.给定虚拟链路
v i v i+1 ∈E T ,IP 分组是从 v i 转发到 v i+1 ,v i+1 的链路指纹建立过程可形式化为一种单射函数 S = f ()v , 而指纹提取
1 + i v i