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

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

o
RAT TIST = o i= 1 (1 p− ∏ ) = (1 p− ) .综上所述,已知 p=(1−e nk/m k
) ,其中,n 为插入布鲁姆过滤器的成员前缀数量,k 为哈
希函数数量,m 为存储容量.鉴于 k,m 通常是定值,可推出 RAT TIST 与 n 成反比.在联盟构建初期,成员前缀数量较
少,RAT TIST 较高;随着联盟规模增大,RAT TIST 会增大.
3.1.2 链路指纹建立
a. 指纹存储开销(SFE)
为了建立链路指纹,溯源路由器单位时间内所记录的链路指纹信息数量,可记为 SFE.HIT 通过隔跳记录 IP
包来建立链路指纹.假设单位时间内到达溯源路由器 R i 的 IP 包为 n,那么 SFE HIT ≈n/2.SEE 通过记录 Stub 域内溯
源路径片段来建立链路指纹.假设单位时间内经过 R i 的溯源路径为 s,那么 SFE SEE ≈s.鉴于作者在之前研究中已
统计出 s≤256,而每个路径片段又与最大长度为 256 的子表外联,因此 STE SEE ≤0.2MB [12] .与 SEE 相似,TIST 也
是采用基于溯源路径的记录方式来建立链路指纹.不过,为了实现联盟内溯源,TIST 只需要溯源路由器记录指
向联盟成员的链路指纹.考虑到 Stub 域通常只设置一个流向外域的边界路由器,而且 TIST 在建立域内溯源网络
时使用前缀聚合,因此 SFE TIST ≤SFE SEE .综上所述,在发生高速匿名攻击时,可推出 SFE TIST ≤SFE SEE <<SFE HIT .
b. 指纹处理开销(PFE)
溯源路由器在执行链路指纹建立函数时所花费的时间,可记为 PFE.它除了影响溯源路由器的分组转发速
率,还会影响网络时延.HIT 使用布鲁姆过滤器来存储 IP 包特征,当 IP 包到达后,溯源路由器 R i 依据包头标记信
息来决定是执行哈希计算还是包标记:前者属于轻量操作,在多核条件下花费时间为 o(1);相对于前者,后者更耗
时,记为 o(s),也就是说,PFE HIT ≤o(s).SEE 使用表结构来记录链路指纹信息,当 IP 包到达后,R i 首先以包头标记信
息作为匹配条件来查询溯源转发表,然后执行包标记,若使用软件来实现表结构,那么表查询开销为 o(m/2),其
中,m 为表项数量;若使用硬件来实现表结构,那么表查询开销为 o(1).基于此,PFE SEE ≤o(m/2)+o(s).TIST 采用与
SEE 相似的存储结构,所不同的是,TIST 只需对溯源分组执行表查询和包标记.任给到达包,假设它成为溯源分
组概率为 p≤1,PFE TIST =p×PFE SEE .综上所述,因联盟构建初期成员数量较少,故 PFE HIT ≤PFE TIST <<PFE SEE ;随着
成员增多,PFE TIST 会逐渐增大,直到所有域加入联盟,PFE TIST ≈PFE SEE .
3.1.3 攻击路径回溯
a. 路径回溯开销(CPC)
TIST 为重构一条攻击路径所耗费的时间,可记为 CPC.它取决于链路指纹提取时间 TTX 和溯源路由器访问
数量 n,可记为 PC=n×TTX.就 HIT 来说,为了完成溯源任务,它需要沿着路由路径反向逐跳访问路由器.假设路由
路径平均长度为 n,那么 CPC HIT =n×TTX HIT .已知域间路径 n 1 和域内路径 n 2 共同组成了路由路径,即 n=n 1 +n 2 .鉴
于 SEE 采用与 TIST 相似的跨域溯源架构,CPC TIST =CPC SEE .就 TIST 来说,它只需访问一次联盟注册服务器就能
确定攻击域,然后回溯攻击域内路径就可识别出入口路由器.基于此,CPC TIST =n 2 ×TTX TIST .链路指纹提取时间
TTX 是指溯源路由器 R i 在收到溯源请求后,执行链路指纹提取函数所花费的时间.HIT 通过查询布鲁姆过滤器
来判定 R i 是否位于攻击路径之上.在多核条件下,TTX HIT =o(1);SEE 通过查询溯源转发表来确定上一跳,若该表
是基于软件的,那么 TTX SEE =o(m/2),其中,m 为表项数量;若是基于硬件的,那么 TTX SEE =o(1).只要能严格禁止非成
员域发起溯源请求,那么 TIST 的链路指纹提取函数与 SEE 完全相同,TTX TIST =o(m/2)或 o(1).因此,TTX HIT ≤
TTX TIST =TTX SEE .不过,鉴于溯源任务发起不频繁,TTX 不会对路由器性能产生较大影响.也就是说,虽然 TTE HIT ≤
TTE TIST ,但是考虑到溯源请求发送操作要远比链路指纹查询操作耗时,n 成为决定 PC 的因素.综上所述,当域内
路径长度远小于路由路径时,即 n 2 <<n,CPC TIST =CPC SEE ≤CPC HIT ;当 n 2 =n,CPC HIT ≤CPC SEE =CPC TIST .
b. 路径回溯精度(TA)
路径回溯精度是指溯源系统准确、完整回溯一条攻击路径的概率.一般来说,溯源误报率和漏报率都会影
响溯源精度,前者使得系统重构出错误的攻击路径,后者使得系统重构出不完整的攻击路径.就 HIT 方法来说,
它采用布鲁姆过滤器来记录压缩后的链路指纹,通常不会产生漏报率,但会生成误报率.给定攻击路径 x 0 P R x k =
x 0 x 1 …x k ,任给节点 x i ∈P R ,假设它的误报率为 p i =(1−e nk/m k HIT = k i= 0 (1 p− ∏ i ) ,其中,n 为到达
) ,HIT 的溯源精度为 TA
x i 的 IP 包数量,k 为哈希函数数量,m 为 x i 中布鲁姆过滤器的存储容量.就 SEE 方法来说,它不需要使用压缩链路