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

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

3) 一旦发起溯源任务,部署域在无法收到任何收益的条件下免费为所有域(包括非部署域)提供服务.
对于以盈利为目的的 ISP 来说,既然溯源升级只能无偿帮助他人,自身却无法获得任何收益,就缺乏部署意
愿.部署激励通常表现在部署收益和非部署收益两方面:前者针对部署域,其部署收益越大,部署激励也越大;后
者针对非部署域,若它们总能不劳而获,那么收益越大,部署激励就越小.
基于此,如定义 8 所述,本文通过逐一累加所有自治域的收益来估算单包溯源方法的部署激励.
以图 1 为例,已知 IS trc ={AS 1 ,AS 6 ,AS 2 ,AS 5 },IS com ={AS 3 ,AS 4 },且只有 stub 域之间会发送数据流.因 Transit 只是
经过域,很少直接被攻击,故 g 1 (AS 1 )+g 1 (AS 2 )+g 1 (AS 4 )+g 1 (AS 5 )=2×2×1/2+2×0×1/2=2;因搭便车问题使得所有域都
能被溯源,故 g 2 (AS 3 )+g 2 (AS 4 )=−2×2×1/2=−2.因此,IDP=0.根据性质 3,因搭便车和 Transit 部署域过多而造成已有
方法的部署激励值较低.
定义 8. 部署激励(incentive for deployment,简称 IDP)定义为一种累加函数,可表示为
IDP = g (G AS ∑ trc ) + ∑ g (G com ) .
G trc ∈ IS trc 1 G com ∈ IS com 2 AS
AS
AS
其中,IS trc =M T 表示部署溯源机制的自治域集合,IS com =M R −M T 表示未部署溯源机制自治域集合, gG trc ) 表示自
(
1 AS
(
治域 G trc 的非部署收益, gG com ) 表示自治域 G com 的非部署收益. g (G trc ) = (| IS stub | / | IS |) F× trc / F total ,其中,
AS 2 AS AS 1 AS trc trc 1 1
IS stub 表示由 Stub 部署域组成的 IS trc 子集, F trc 表示向 G trc 发送匿名流但能被追溯自治域数量. gG com ) =
(
trc 1 AS 2 AS
− (| IS stub | / | IS |) F× com / F total ,其中, F com 表示向 G com 发送匿名流但能够被追溯自治域数量.
trc trc 2 2 2 AS
性质 3. 在已有单包溯源方法中,搭便车和 Transit 部署域数量太多,都会影响它的部署激励性.
证明:根据定义 8 可知:非部署收益越小,部署激励越大;而部署收益越大,部署激励越大.在已有的单包溯源
方法中:非部署收益源于搭便车问题,它会产生大量不劳而获的非部署域;部署收益取决于部署域的数量,在匿
名流总量不变的前提下,部署域越多,部署收益越小.已知部署域包括 Transit 域和 Stub 域.与后者不同,前者很少
遭到直接匿名攻击,所以它的部署收益很低.因此,只要降低 Transit 部署域数量,就能提高方法的部署激励. □
针对上述问题,本文希望通过构建一种以 Stub 域为成员单位的溯源联盟,来强化单包溯源方法的可部署性.
一方面降低溯源网络的成员复杂度,仅由 Stub 域来灵活组建,这不仅有效弱化了部署域之间的溯源耦合性,实现
增量部署;另一方面,只为成员域建立链路指纹,既有效减少了溯源路由器的成本开销,又将非成员域从受益者
列表中严格剥离,缓解了部署激励问题.

2 联盟模式下高效单包溯源方法

本文提出了一种联盟模式下的高效单包溯源方法(an efficient single-packet traceback based on alliance
theory,简称 TIST),本节将详细阐述本方法的设计思想和具体实现细节.为此,本节组织结构如下:第 2.1 节主要介
绍 TIST 的整体架构,之后各节分别阐述它的具体设计细节,其中,第 2.2 节阐述联盟网络下链路指纹建立策略,
第 2.3 节阐述联盟网络下溯源分组识别策略.
2.1 整体架构

TIST 的核心思想是:由部署溯源机制的 Stub 域作为成员单位自愿构建一个溯源联盟,每个成员域只需承担
律己的基础责任,即,联盟内每一对互为通信端的成员 Stub 域 AS x 和 AS y 都需为彼此提供溯源服务.当 AS x 作为
源自治域时,即 IP 分组源自 AS x 发往 AS y ,AS x 内部的溯源路由器需要为该分组建立链路指纹,进而承担由 AS y 发
起的路径回溯任务,使它能够通过捕获异常样本分组直接完成源自治域的识别和攻击路径的回溯;同样原理,当
AS y 作为源域、AS x 作为目的域时,则由 AS y 建立链路指纹建立和承担回溯任务.定义 9 对溯源联盟(tracing
alliance,简称 TA)进行了形式化描述,很明显,这种联盟系统符合俱乐部经济学模型.将溯源功能作为俱乐部物
品,仅为俱乐部会员之间相互提供,而俱乐部以外的成员则不享有俱乐部的溯源服务.根据性质 4,它不仅能够有
效地剪除搭便车非成员域,提高部署激励,而且能够减少成员域建立的链路指纹数量,降低处理开销.更进一步,
考虑到互联网中可能同时存在多个溯源联盟,甚至它们的成员彼此交叉,当所有成员域加入同一个溯源联盟,
TIST 将获得最大的激励效果.为此,本文不失一般性地假设整个网络只有一个溯源联盟.按照功能,TIST 可划分