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

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

其中,x prefix 是决策变量,x prefix =1 说明网络前缀 prefix 被选中,x prefix =0 说明未被选中;公式(1)表明优化目标;公式(2)
是资源受限条件;公式(3)是每个成员的地址前缀有且只能被覆盖 1 次.清华大学的毕军和加利福尼亚大学的
F.Soldo 研究团队将上述问题已经归为多维背包问题 [14,15] (属于 NP-hard 范畴),并且提出了相关解决算法.但是
它们存在时间开销大、求解精度低等缺陷,因此,我们在文献[13]中进一步提出了可增量、高精度的过滤规则优
化算法 EAGLE.限于篇幅,本文就不再对算法具体设计细节展开叙述.
密钥作为成员域的身份标识,一旦被非成员域劫持,就会引发溯源误报.只有不断更新密钥,才会保证安全
性.然而,随着溯源联盟规模逐渐增大,密钥更新范围也越来越广,这必然产生巨大通信开销.基于此,如何设计一
种低开销的密钥更新策略,就成为提高系统可扩展性的关键问题.考虑到各成员域边界路由器的性能容量和负
载不同,它们可承受的密钥更新周期也应不同.若由联盟注册服务器集中生成和分发密钥,为了降低服务器的管
理复杂度,更新周期就只能固定,这不符合上述要求.为此,本文提出一种面向成员域的动态更新策略.具体原理
是:各成员域的控制服务器独立生成基于时间分片的密钥链{K 0 ,K 1 ,K 2 ,…,K m },K i =H(K i−1 ),0<i<m−1,K 0 =x,其中,
ρ
*
H:{0,1} →{0,1} .
H 是单向散列函数;ρ是定值,表示输出结果的长度;*表示任意长度;x∈{0,1}是随机输入参数.每个时间片内
都会生成密钥链中一个密钥,并将它下发到所有边界路由器.各成员域依据路由器的性能容量制定时间片长度.
在时间片结束后,延迟时间Δ将该密钥发布到联盟注册服务器,其中,Δ至少要大于密钥发布请求在互联网上的往
返时间.也可以推迟若干个时间片,等溯源任务开启后,由注册服务器主动请求成员域发布密钥.在攻击域识别
过程中,注册服务器只需下载成员域最近公开的密钥,进行匹配即可.值得注意的是:为了降低各成员域生成同
一密钥的可能性,可依次推算密钥链,再进行匹配.
b. 域间链路指纹建立函数
在融合对等过滤和密钥认证的域间溯源过程中,攻击域边界路由器和受害域边界路由器实现不同链路指
纹建立函数,分别表示为 h 1 和 h 2 ,其中:h 1 为攻击域生成密钥,并为受害域分配出标签和标记指纹;h 2 只为攻击域
记录链路指纹.给定攻击域为 AS i ,受害域为 AS j ,h 1 和 h 2 分别定义为
h 1 (AS i ):={GenerateKey(AS i .SK);
If (Tracing-packet){InsertKey(SK);}}
h 2 (AS j ):={
If (Tracing-packet){InsertFingItem(AS i .SK);}}
其中,GenerateKey 表示生成密钥操作,InsertKey 表示密钥标记操作,InsertFingItem 表示指纹记录操作.
2.3 基于布鲁姆过滤器的溯源分组识别策略

溯源路由器除了完成固有的路由转发功能,还需要识别流向成员域的 IP 分组.考虑到溯源路由器的高负载
以及有限的存储、计算资源,TIST 的溯源分组识别应满足如下条件.
1) 快速.时间复杂度要尽可能低,避免它对路由器的转发时延产生较大影响;
2) 轻量.空间复杂度要尽可能低,防止它对路由器的吞吐量产生较大影响.
为此,本文提出一种基于布鲁姆过滤器的溯源分组识别策略.
TIST 为了建立链路指纹,需要入口路由器从 IP 分组中识别溯源分组,然后为它们建立链路指纹.一种直接
的溯源分组识别策略是:利用已有的 IP 包分类算法对到达分组目的地址进行最长前缀匹配,例如基于 TCAM 的
分类算法、基于二叉搜索树的分类算法等,匹配成功,则说明该 IP 包会流向成员域,也就可判定它为溯源分组;
反之,则不是.然而,这些算法要么需要较高构建成本,要么需要较大内存和计算开销,因此并不适合 TIST.例如,在
IPv4 网络中,二叉线索树高度可达 32 层,这就意味着最坏情况下需要访存 32 次.上述策略之所以低效,是因为它
们采用先分类、后识别方式.若能不经分类就完成分组识别,那么处理开销自然会降低.受此启发,本文引入布鲁
姆过滤器来完成识别任务,其基本思想是:利用布鲁姆过滤器空间利用率高、计算时间短等特点,将所有联盟成
员的网络前缀全部压缩于该数据结构中.对于每一个 IP 到达分组,使用相同的压缩算法来计算其目的地址所对
应每一种网络前缀的特征值.若该值已存于布鲁姆过滤器,就证明它是溯源分组;反之,则不是.例如,给定 k 个独