基于矩阵边采样的IP追踪

闫 巧，宁土文

1)深圳大学计算机与软件学院，深圳518060;2)深圳大学信息工程学院，深圳518060

拒绝服务攻击 (denial of service attack，DoS)和分布式拒绝服务攻击 (distributed denial of service attack，DDoS)消耗被攻击主机的网络资源，使得正常用户无法响应网络请求.由于攻击容易实施，但难以防范，更不容易查找攻击源，因此引起了研究者的广泛重视.IP追踪技术 (Internet protocol traceback)［1］借助路由器获得攻击路径，反向追踪到攻击源，是确定DoS和DDoS攻击源的有效方法.

根据IP追踪的主动被动性，现有的IP追踪技术可分为被动式IP追踪和主动式IP追踪两大类.被动式IP追踪，即检测到攻击后才开始引发追踪过程，这种追踪只能在攻击流保持活动时进行追踪，一旦攻击结束，就无法确定IP源，早期的方法包括输入调试［2］和控制洪泛［3］.主动式 IP追踪指当攻击发生时，可根据实时监测的结果重构攻击路径，这种追踪在攻击结束后仍能确定真实的IP源地址，主要方法包括:基于网际控制信息协议(Internet control message protocol，ICMP) 的 追踪［4］、数据包标记 (packet marking)追踪［5-10］和日记分析追踪［11-12］等.其中，数据包标记追踪是研究最多的IP追踪技术，它可分为概率包标记 (probabilistic packet marking，PPM)和确定性包标记(deterministic packet marking，DPM).PPM 方案［5］是一种针对DoS或DDoS的有效IP源追踪技术.它易于实现，仅使用IP包本身信息，不会产生额外流量，也不会被防火墙或安全策略堵塞，且不需来自互联网服务提供商 (Internet server provider，ISP)的相互合作，因此备受业界关注［6］.但PPM同时亦面临着存在最弱链、难收敛、重构算法复杂度过高和重构路径误报率过高等问题［5］.动态概率包标记 (dynamic probabilistic packet marking，DPPM)方案［7］采用自适应概率对数据包进行标记，使受害终端接收到攻击路径上的每个采样边的概率相等，从而不存在最弱链和难收敛问题，且重构路径时所需数据包数较少.然而，DPPM仍存在重构路径算法复杂度过高和重构路径误报率过多等问题［7］.

PPM算法的边采样是通过增加1个32 bit哈希然后分片，再由相邻路由器之间的异或来实现的.因此，PPM重构时可使用穷举法，再用哈希关系检测采样边［5］.当分片为8时，PPM重构算法复杂度为O(m8)，边采样的误报率PE=1－(1－1/232)m8.其中，m为攻击路径数.当m=20时，PE≈1.可见，PPM在攻击路径上使用相邻路由之间的异或来进行边采样，而PPM在重构时使用了穷举法，导致PPM重构攻击路径时复杂度和误报率过高.针对PPM的缺陷，本研究改进了边采样方法，用1个二维矩阵对相邻路由进行边采样，降低了重构算法的复杂度，通过引入8 bit的多路径检验，降低重构路径误报率.又因采用了自适应概率对数据包标记，使受害终端接收到的攻击路径上每个采样边的概率相等，减少了重构路径所需数据包.

1 基于矩阵边采样的IP追踪

DoS的攻击路径如图1［8］.由图1可见，整条攻击路径上有d个路由，由于IP包头中可标记的位数有限，不可能把d个路由的地址全部标记在1个数据包中，所以采用边采样，即将相邻路由之间的边信息标记进IP包头中，然后在收集到所有的边信息后重构整条攻击路径.

图1 DoS攻击路径示意图Fig.1 DoS attack path diagram

当引入1个二维矩阵进行边采样时

其中，ri和ri+1分别是DoS攻击路径上的第i个和第i+1个路由地址;ρi和ρi+1分别是ri和ri+1的线性累加;c00，c01，c10和 c11是随机数.

若A可逆，则可在重构时通过rT=A－1·ρ，且ρ=(ρd，ρd+1)T求得采样边(ri，ri+1)，即

其中，B为A的逆矩阵.

所以在标记数据包时，要把二维矩阵A和ρ=(ρi，ρi+1)T标记进去，而在每个数据包中只标记式(3)的［c00c01］和ρi，或式(4)的［c10c11］和ρi+1.

为降低重构算法复杂度，使A矩阵固定，那么在重构时就不用计算A的逆矩阵.A固定后，就可用A的行标和列标来索引A中的每1个cij(i，j∈{0，1}).由于A的列标与攻击路径上的距离信息相关，因此只需用1 bit来索引A的行标.

为降低重构算法复杂度，并减少标记的总位数，需选择一个合适的矩阵A.下面讨论A的制约条件.首先，A必须是可逆矩阵，如此才能使式(1)通过 rT=A－1·ρ，ρ=(ρi，ρi+1)T求得采样边(ri，ri+1).而标记进每1个数据包中的是式(3)中的［c00c01］和ρd或式(4)的［c01c11］和ρd+1.而在固定矩阵A后标记进每个数据包的是A的行标和列标.行标和列标都只有两种情况，且列标可用距离信息表示，因此只需1 bit表示行标.然而，ρi(或ρi+1)也要被标记进数据包中，ρi=c00ri+c01ri+1和ρi+1=c10ri+c11ri+1.其中，［c00c01］和［c01c11］为A的行向量.若ρi(或ρi+1)的数值很大，则所需标记位就很多，因此要使ρi(或ρi+1)尽量的小.根据以上原则，本研究选择A为二维单位矩阵，这是因为:首先，二维单位矩阵是可逆矩阵，且其可逆矩阵也为二维单位矩阵;其次，由ρi=c00ri+c01ri+1和ρi+1=c10ri+c11ri+1.其中，［c00c01］和［c10c11］为A的行向量.由此可知，在没有信息压缩的情况下，A为单位矩阵，那么［c00c01］(或［c10c11］)就只有1个元素是1，此时ρi=c00ri+c01ri+1(或ρi+1=c10ri+c11ri+1)的值最小，这是因为ρi(或ρi+1)是要标记进数据包中的.所以ρi(或ρi+1)值越小，占用的标记位就越少.

引入8 bit的攻击路径检验，以区分DDoS多攻击源下产生的多条攻击路径中的边采样.由此可知，当攻击路径数为m时，其重构路径的边采样的误报率PE=m/(28).然后，参考DPPM的自适应概率标记方法［7］，采用自适应概率对采样边进行标记，可降低重构路径所需数据包数.

如图1，假设DoS攻击路径上有d个路由，每个边采样的标记概率为p(i)(i∈{1，2，…，d})，由PPM算法可知，在受害终端检测到的相邻路由采样边标记信息的概率为 pL(i)，其中i∈ {1，2，…，d}，则有

若是PPM算法，则相邻路由边采样的标记概率相同，即 p(i)=p(i∈ {1，2，…，d})［5］.此时，在终端检测到的各采样边的概率为

由 pL(i)(i∈{1，2，…，d})可知，pL(1)的概率最小，是最弱链.要避免出现最弱链，须使pL(1)=pL(2)=… =pL(d)=1/d，由式(5)解得pL(i)(i∈ {1，2，…，d})为 p(i)=1/i，i∈ {1，2，…，d}).将其代入式(5)，得

对侨民的赞美和爱戴在节庆时刻得到集中展示，也是对他们贡献的回报形式。在节庆中，侨民收获的无形权力体现为人气和声誉——作为“皇后”“公主”的人气和作为海外侨民作出贡献的声誉，来自四面八方的艳羡和敬重在节庆时刻达到极致。侨民的皇后加冕已经形成一种乡村礼仪规范，维系着侨民与本地留守人员之间的关系。参与其中的侨民和本地留守人员默认维护着这一套乡村礼仪规范，成为节庆大群体的成员。不认同该“规则”的人也有权选择不参与这一套礼仪规范。

因此第一个路由的标记概率为1，第二个路由的标记概率为1/2，第d个路由的标记概率为1/d.IP包中的生存时间 (time to live，TTL)值每经过一个路由就减1，因此，设初始化TTL=32，则可用1/(32－TTL)代表每一个路由器上的标记概率.从而使每个路由标记的数据包到达受害终端的概率相等.因此，本研究提出基于矩阵边采样的IP追踪 (IP traceback with matrix edge sampling)方案，即MES方案.

1.1 基于矩阵边采样的IP追踪方案的标记

由上述基于矩阵边采样的IP追踪思想可知，边标记的过程如式 (1)，将A固定为二维单位矩阵后，只需标记其行标和列标 (与距离信息相关).然后，将每个路由地址分成4片，每片8 bit，引入1个8 bit的攻击路径检验用以区分DDoS多攻击源下产生的多条攻击路径中的边采样.为使重构时需要的数据包数更小，本研究采用自适应概率标记数据包.

如图2，用1 bit的firstc表示A的行标，用5 bit的distance表示距离信息，同时距离信息与A的列标相关，用log24=2 bit的offset表示分片信息，用8 bit的 sumedge表示采样边累加，用8 bit的path表示路径检验，所需标记位共24 bit.因此，可采用IP包头中的16 bit的IP标识域［5］和8 bit的服务类型 (type of service，TOS)域［9-10］进行标记，恰好24 bit.图3是标记算法伪代码.

图2 位预算与标记Fig.2 Bit budget and marking

标记算法在每个路由器中都是一样的.首先，将路由器地址R分成4片，每片8 bit保存在whichs［i］(i∈{1，2，3})中.然后，保存1 个8 bit的路径检验 XORpath=whichs［0］= ⊕whichs［2］ ⊕whichs［3］，并保存1个二维单位矩阵MAT.对每个经过路由器的数据进行包标记.首先算出标记概率p为从 ［0 1］中取1个随机数x，若x＜p，则对数据包进行标记.其中，b是从{0，1，2，3}中随机选取的1个整数，而a是从{0，1}中随机取1个整数.然后，令w.sumedge=whichs［b］* MAT［a］［0］，w.distance=0，w.offset=b，w.firstc=a，w.path=XORpath;否则，即x≥p，那么先检查w.distance是否为0，若是，则令 w.sumedge=whichs［w.offset］ * MAT［w.firstc］ ［1］ +w.sumedge，w.path=w.path⊕XORpath.w.distance都要增1.

1.2 基于矩阵边采样的IP追踪方案的重构

由上述基于矩阵边采样的IP追踪思想可知，MES边采样标记对应式(1)，而重构对应式(2)，其中A是关键.又因矩阵A为二维单位矩阵，所以其逆矩阵B也为二维单位矩阵.因此，只需要将不同路径和不同距离的边信息收集齐后，即可按照式(2)进行边重构.边重构完成后就进行多路径重构.

图3 MES标记算法伪代码Fig.3 Marking algorithm of MES schema

重构算法在受害终端进行，首先需将数据包的标记信息保存下来，然后将相邻路由的线性累加变换成为分片，再将分片转换成为边信息，最后将边信息组合成为攻击路径.

2 性能分析

2.1 重构路径所需要的数据包数

重构路径所需数据包数目是评价概率包标记算法的重要性能指标之一，反映了概率包标记算法的效率.

假设一条攻击路径长度为d，由传统PPM知，受害者重构一条长度为d的攻击路径所需要的数据包数量N的期望值［5］为

传统PPM的边分片数为8，所以其重构路径所需数据包数约为

基于矩阵边采样的IP追踪，即MES方案 (IP traceback with matrix edge sampling，MES)，采用自适应概率标记数据包.路由器标记数据包的概率为1/dA，这里dA是路由器距离攻击者的跳数，可确保每个路由器标记过的数据包到达受害者的概率都为1/d，这里d为攻击路径长度波.如DPPM的重构路径所需数据包数［7］为

其中，k为分片数;d为攻击路径长度.由于基于矩阵边采样的IP追踪采用的是用1个二维单位矩阵对相邻路由边进行采样，而该二维矩阵的两个行向量是独立标记进数据包中的，因此需采集到两个不同的数据包，才能对采样边进行重构.假设平均采集X次才能采集到两个不同的数据包，且采集到的各个数据包的概率都为0.5，则

即平均要采集3次才能采集到两个概率相等的数据包.所以，该重构路径所需数据包量为

由MES方案可知，k=4，即

NS2(Network Simulator version 2)环境［13］下仿真结果如图4.由图4可见，仿真结果与理论分析一致.

图4 重构路径所需数据包数Fig.4 The number of packets required during reconstruction

2.2 重构路径算法复杂度

假设攻击路径上有d个路由，m条独立的攻击路径，由PPM和DPPM的重构算法可知，重构攻击路径需进行8md次异或和dm8次哈希运算，即算法复杂度为O(8md+m8d).由于d＜32，所以PPM和DPPM的重构路径算法复杂度为O(m8)［5-7］.

由基于矩阵边采样的IP追踪重构算法可知，因新方案分片数为4，而重构出相邻路由边采样的运算如式 (2)为4次乘法，若DDoS攻击路径上有d个路由，m条独立的攻击路径，则其需进行4×4×d×m次乘法.其中，d是小于32的常数.因此，重构算法复杂度为O(m).由此可知，基于矩阵边采样的IP追踪的重构算法复杂度比PPM和DPPM都要低很多.

2.3 重构路径误报率

由传统的PPM算法可知，PPM重构是逐边往回追踪，其每个边采样的误报率［5］为

其中，m为攻击路径数.基于矩阵边采样的IP追踪，即MES方案，引入了8 bit的多路径检验，若有m条攻击路径，则其边采样误报率PE(MES)=m/28.PPM、DPPM和MES的重构路径边采样的误报率统计如图5.由图5可见，当攻击路径m=20时，PE(PPM)≈1，而PE(MES)=20/28=0.078 125，这表明MES方案比PPM方案保持了更低的误报率.

图5 重构路径误报率Fig.5 False alarm rate during reconstruction

结 语

本研究提出一种边采样概率包标记方案，即MES方案.通过引入二维单位矩阵对相邻路由节点进行边采样，降低了重构路径的算法复杂度，引入8 bit的多攻击路径检验，降低了重构路径的误报率，采用自适应概率对数据包进行标记，从而降低重构路径所需要的数据包数.理论分析和NS2仿真结果表明，MES方案在防御DDoS攻击中的表现比其他概率包标记方案更佳.

/References:

［1］ Belenky A，Ansari N.On IP traceback［J］.IEEE Communications Magazine，2003，41(7):142-153.

［2］ Stone R.Center track:an IP overlay network for tracking Dos floods［C］//Proceedings of 2000 USENIX Security Symposium.Denver(USA)，2000:199-212.

［3］ Burch H，Cheswick B.Tracing anonymous packets to their approximate source［C］//Proceedings of 2000 USENIX LISA Conference.Seattle(USA)，2000:319-327.

［4］ Sung M，Xu J，Li J，et al.Large-scale IP traceback in high-speed internet:practical techniques and informationtheoretic foundation ［J］.IEEE/ACM Transactions on Networking，2008，16(6):1253-1266.

［5］ Savage S，Wetherall D，Karlin A，et al.Network support for IP traceback ［J］.IEEE/ACM Transactions on Networking，2001，9(3):226-237.

［6］ YAN Qiao，XIA Shu-tao，WU Jian-ping.Improved compressed edge fragment sampling algorithm ［J］.Journal of Xidian University:Nature Science，2006，33(5):824-828.(in Chinese)闫 巧，夏树涛，吴建平.改进的压缩边分段采样算法［J］.西安电子科技大学学报:自然科学版，2006，33(5):824-828.

［7］ LIU Jenshiuh，LEE Zhi-Jian，CHUNG Yeh-Ching.Dynamic probabilistic packet marking for efficient IP traceback ［J］.The International Journal of Computer and Telecommunications Networking，2007，51(3):866-882.

［8］ LU Jun-jie，LIU Li.New fragment marking algorithm for IP traceback ［J］.Computer Engineering and Applications，2010，46(13):4-7.(in Chinese)吕俊杰，刘 丽.一种新的IP追踪的分片标记方法［J］.计算机工程与应用，2010，46(1):4-7.

［9］ Dean D，Franklin M，Stubblefield A.An algebraic approach to IP traceback［J］.ACM Transactions on Information and System Security，2002，5(2):119-137.

［10］ Pegah Sattari，Minas Gjoka，Athina Markopoulou.A Network coding approach to IP traceback［C］//IEEE International Symposium on Network Coding(NetCod).Toronto:［s.l.］，2010:1-6.

［11］ Snoeren A C，Partridge C，Luis A，et al.Hash-based IP traceback［C］//Proceedings of the ACM SIGCOMM 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication.New York:ACM，2001:3-14.

［12］ Snoeren A C，Partridge C，Luis A，et al.Single-packet IP traceback［J］.IEEE/ACM Transactions on Networking，2002，10(6):721-734.

［13］ YAN Qiao，Ning Tu-wen.Implementation of simulation platform for probabilistic packet marking based on NS2［J］.Computer Engineering，2011，37(S395):135-138.(in Chinese)闫 巧，宁土文.基于NS2的概率包标记仿真平台的实现 ［J］.计算机工程，2011，37(S395):135-138.