High-Speed Inter-domain Fault Localization

> C. Basescu, Y. -H. Lin, H. Zhang and A. Perrig, “High-Speed Inter-Domain Fault Localization,” 2016 IEEE Symposium on Security and Privacy (SP), 2016, pp. 859-877, doi: 10.1109/SP.2016.56.

文章发在SP上, 但读的时候很不好受, 很难受, 因为里面的英语表达写法很不习惯, 而且读的时候还总给人一种水时长的感觉, 挑与我相关的重点读了一下, 感觉还不错.

工作背景

AS未按要求转发数据包, 而是对包延迟发送, 丢弃和修改, 本文工作就是这样的恶意AS进行检测与定位.

工作概述

Faultpints使用 确定性采样来抓捕恶意AS.每个AS都要和源建立一个秘密数据包抽样密钥\(D_{AS_i, S}\), 且规定相应的确认包种类,如DACK. 如图1中所示, 源与目的通信, AS3是恶意的. 当AS抽样包时会存储一个数据包的fingerprint到 Bloom filter中, 这个fingerprint会捕获包的presence 和包的内容. 当包被丢弃那么D则不会发确认包,所以S会为这个数据包发探针, 所有的AS都会响应这个探针, 而源会从探针数据包中获得抽样包的信息. 源会检查响应包的密钥并对某些AS进行怀疑, 并为每个AS进行怀疑打分, 错误行为的AS的怀疑打分最终会高于其他AS.

TODO 其他章节

都略去, 写得实在冗余而且难懂

Fault Localization Mechanism

依据: 当端到端的数据包崩坏率超过一个给定的域值时则说明存在攻击者. 源根据正确的探针响应和缺失的验证探针响应定位攻击者. 源为每个AS维护两个值: 崩坏打分和误操作概率.

崩坏打分:AS错误响应探针的次数

误操作概率:基于不正确响应探针而计算的概率

Corruption score computation

源对比接收到的probe与本地存储bloom filter中的值,若相等则说明\(AS_i\)是诚实的. 若不等, 分两种情况: 若期望接收探针但实际没接收到,则源会去定位哪个数据包丢失了,如图8.源收集所有的正确响应, 并定位到最后一个正确响应的数据包的AS以及第一个响应丢失的AS. 因为响应包是在这两个AS间丢失的, 因此源增加这这条路径上这两个AS间所有AS的崩坏打分.若不期望接收但接收到了响应, 在错误行为概率中讨论.

Misbehavior probability computation

式(17)定义了良性AS和恶意AS的概率转移矩阵. \(P_D\)为恶意AS破坏一个响应包的概率. 良性AS破坏一个数据包与自然包率相同, 为\(\rho\). 利用该矩阵,一个正确数据包经过良性AS后保持正确的概率为\(1-\rho\), 经过一个恶意AS后保持正确的概率为\(1-P_D\). 因此当一条长度为r的链路有t个恶意AS时, 响应数据包保持正确的概率如式(18).

\(P_Q\)为恶意AS在交付链路上的概率, 当有f个恶意AS时,响应包被破坏的概率如式(19)

错误行为概率如式(20). k为中间AS节点个数. \(t_i\)为ASi的返回路径上的AS数, \(r_{j,i}\)为1若ASj在返回路径上. 对于每一个AS, 式(20)都是常量. 因此要算的是\(P(dmg_1, …, dmg_k | AS_i mal)\). mal表示malicious, n为源期待接收的响应包数.为定位恶意链路, 源最终需要计算所有的 \(P_{i+1}|P_{i}\) 并将最高Pi的ASi->AS_i+1链路识别为恶意链路.