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

鲁宁 等:联盟模式下高效单包溯源方法研究 3897

⎛ − ⎞ nk k
− ⎜
P = ⎜ 1e m ⎟ ⎟ (8)
⎝ ⎠
其中,n 为插入布鲁姆过滤器的元素个数,k 为哈希函数个数,m 为该布鲁姆过滤器存储容量.很明显,P 的大小取
决于 k,n 和 m.
• 首先分析 k.本文依据路由器的计算性能和最大并行度来设置 k 的数量;
• 然后分析 n.因误报率会随着 n 的增长而迅速变大,故本文只考虑最坏情况,即插满布鲁姆过滤器.
I
假设某布鲁姆过滤器的掩码长度为 I≤32,那么它插入元素的最大数量为 2 ,所需匹配的最大 IP 地址数量为
2 32−I+1 .已知布鲁姆过滤器 i 插满时误报率为 P i ,任给一个 IP 包,只有 32 个布鲁姆过滤器的查询结果全部准确,
最终结果才会正确,PCBF 的精确度 E total 为
E total = 32 1 (1 p− ∏ i ) (9)
i=
基于此,本节主要研究如何最小化布鲁姆过滤器集的误报总数,也就是:
max(1−p 1 )×(1−p 2 )×…×(1−p 32 ) (10)
根据定理 1 可知:只有满足 P 1 =P 2 =…=P 32 ,误报总数才会最小.若想达到取等号的条件,各布鲁姆过滤器的存
i−1
储容量需满足 m i =2 ×m 32 .进一步考虑到 m 1 +m 2 +…+m 32 =M,根据等比数列求和,可得:
m = 2 31 i− × M ,m = M (11)
i
32
2 − 1 32 2 − 1
32
这也就是说,只要满足公式(11),即按照公式(11)为布鲁姆过滤器分配存储容量,就可获得最小误报期望.
在联盟构建初期,各个布鲁姆过滤器不可能全部插满元素,因此本文提出两种分配策略:动态分配和静态分
配.前者以 m 32 存储空间为初始分配值,每插入一个元素就增长一个存储空间,因此其空间利用率较高,但误报率
较大;后者直接以计算得出的比例依次为不同布鲁姆过滤器分配存储空间,特点是误报率低,空间利用率也低.
定理 1. 当 P 1 =P 2 =…=P 32 时,公式(10)就会成立.
1/n
证明:已知 1≥P i ≥0,根据算术几何均值不等式:[(a 1 +a 2 +...+a t )/n]≥(a 1 ×a 2 ×...×a t ) ,当且仅当 a 1 =a 2 =...=a t 等
号成立.基于此,当(1−P 1 )=(1−P 2 )=…=(1−P 32 )时,公式(10)成立. □
3 性能评价

为了验证提出的 TIST 方法,本文进行了理论分析和仿真实验,其中,第 3.1 节将使用理论分析来证明方法的
可部署性,第 3.2 节则通过基于真实网络拓扑的实验仿真来补充分析结果,第 3.3 节重点讨论大规模部署时方法
的优势以及可能存在的问题.
3.1 理论评估
[8]
本节将使用数学方法来比较分析 TIST 与经典单包溯源方法(包括 HIT ,SEE [12] 等)的性能指标.重点是那
些第 2.2 节提出的非功能、可测试指标(例如高效性、高精度),至于功能性指标(例如松耦合、动态扩展),我们
在方法论述过程中就已说明.根据第 2.1 节所述,TIST 方法被划分为控制层和数据层:前者承担溯源联盟构建,
而后者承担链路指纹建立和攻击路径回溯.在构建溯源联盟过程中,联盟注册服务器和各成员域的控制器既需
要彼此之间频繁通信,又需要各自记录成员信息.
基于此,我们重点评估控制层的通信开销(communication overhead for tracing-alliance establishment,简称
CTE)和存储开销(storage overhead for tracing-alliance establishment,简称 STE).此外,TIST 部署激励性(incentive
for deployment,简称 IDP)的提高,是因构建溯源联盟而造成的,因此,相关评估也在这一部分.
在链路指纹建立过程中,溯源路由器既需要提取指纹,也需要记录它们,故我们主要评估它的存储开销
(storage overhead for fingerprint establishment,简称 SFE)和处 理开销 (processing overhead for fingerprint
establishment,简称 PFE).
在攻击路径回溯过程中,各成员域控制器需要提取和匹配若干溯源路由器上的指纹,而匹配又存在误报率