基于GBF的追踪溯源系统设计*

黄 宸，陈周国，郝 尧，蒲 石

(保密通信重点实验室，四川 成都610041)

0 引言

随着互联网在人类政治、经济、文化、生活等各方面发挥越来越重要的作用，互联网的安全也越发引起人们的关注。面对日益严峻的网络安全形势，仅仅依靠传统的部署防火墙、IDS、IPS等被动防御方法已不足以确保组织、公司的网络安全。追踪溯源是一种主动防御方法，是在网络攻击发生时主动定位网络攻击者身份或位置及其攻击路径的过程。身份是指攻击者的姓名、账号等能够代表攻击者的信息，位置可以是攻击者的物理位置或网络地址，攻击路径是攻击数据流从攻击端到受害端所经过的网络路径。追踪溯源至少具有以下三点重要意义:①从源头上遏制攻击;②指导防御方采取有针对性防御措施;③为从司法上惩治网络罪犯提供有力证据。

学术界对网络追踪溯源已经有了较多的研究，主要包括:链路测试法、日志记录法、iTrace和数据包标记法。链路测试法［1］是在攻击发生时对各个路由器之间的链路进行测试以确定攻击流经过的路径。链路测试法缺陷是:只能在攻击发生时应用;只能进行自治域内的追踪;建立IPSec安全联盟需要消耗大量资源。SPIE(Source Path Isolation Engine)［2］是一种典型的日志记录追踪溯源方法，该方法提取数据包的IP头固定部分与数据的前8字节进行 Hash 运算，采用 Bloom Filter［3］存储结果。SPIE优化了日志存储所需的空间，但在当今的高速网络中，每秒所需的存储空间仍然达到了GB级别，所需的存储空间过大是日志记录法的最大缺陷。iTrace［4］是一种基于ICMP的溯源方法，路由器以一定的概率抽取所转发数据包的特征信息，与路由器自身的IP地址一起封装到ICMP数据包，之后发给目的端，当遭受攻击时，受害端收到足够多的数据包就可以重构攻击路径。iTrace溯源法需要收集大量数据包，重构攻击路径较慢，对受害端的资源消耗较大。数据包标记法对路由器所转发的数据包做标记，受害端收到数据包后可以根据标记信息重构攻击路径。典型的数据包标记法有:概率包标记法［5］、确定包标记法［6］和动态概率包标记法［7］。

1 GBF与包标记追踪溯源

最早的数据包标记追踪溯源直接在数据包中标记路由器的IP地址，由于每个IP地址占4字节，而数据包从攻击端到达受害端可能经过很多个路由器，需要的存储空间非常大，概率包标记法虽然减轻了路由器和网络的负载，减小了数据包的长度，但追踪溯源时需要收集大量数据包，重构路径速度慢且无法对单包进行溯源。为了解决以上问题，文中在包标记追踪溯源中引入一种高效的存储结构:Generalized Bloom Filter(简称GBF)。

Generalized Bloom Filter是 Rafael P.Laufer等人［8］提出的一种可以将大量数据存入较小存储空间并能快速查询的数据结构，GBF相对Bloom Filter的改进是GBF对存储空间的初始状态没有要求。对于集合S={s1，s2，…，sn}，GBF采用 k0个 g哈希函数和k1个h哈希函数，g函数将对应比特位置0，h函数将对应比特位置1，假如g函数和h函数计算出来的值相同，则置0。查询某个元素si是否属于S，需计算 g1(si)，g2(si)，…，gk0(si)并检查对应比特位是否为0，还需计算si的hash值h1(si)，h2(si)，…，hk1(si)并检查对应的位是否为1，如图1所示。

判断某个元素x是否属于集合S，GBF并不能保证100%的正确率。对于集合S中的某个元素x，当将x在存储空间的bit位分别置0和置1后，在x之后存储的元素有可能将x对应的bit位翻转，导致查询结果为x不属于S，造成漏报。对于某个不属于集合S的元素y，也可能在其他元素的影响下g1(y)，g2(y)，…，gk0(y)被置 0，h1(y)，h2(y)…hk1(y)被置1，造成y∈S的错报。在数据包标记追踪溯源中，错报意味着把本不属于攻击路径上的路由器判断为属于攻击路径，漏报意味着把本属于攻击路径上的路由器判断为不属于攻击路径。因此，需要研究GBF的错报率和漏报率，并尽量降低错报率和漏报率。根据文献［8］，GBF的最大错报率F在k=k0=k1时取得:F=(1/4)k。

图1 GBF存储过程Fig.1 GBF store procedure

GBF的最大错报率仅随所选取的hash函数的数目的增加而递减，与存储空间的大小m和元素数目n无关。假设k=k0=k1=4，最大错报率F为0.39%。由于越早存入GBF的元素越有可能被后续存入的元素覆盖，GBF的漏报率随元素序号递减。又由于每个hash函数进行计算后都要对bit位进行置0或置1，每次设置元素都有可能被覆盖，因此采用的hash函数数目k越大，GBF的漏报率越高。

GBF的错报率随hash函数数目k增大而减小，而漏报率随k增大而增大(在m/n不变时)，并且k的数目越多，需要做的计算越多，因此需要对k做一个折中的选择。GBF的漏报率随m/n增大而减小(在k不变时)，但在数据包标记追踪溯源的应用中，需要考虑数据包太大对网络的影响。

2 追踪溯源系统设计

2.1 GBF 参数选择

为了应用GBF，先要定义hash函数，选定hash函数的数目，此外，还应当在数据包中给出GBF的存储位置。选择hash函数数目为k=k0=k1=2，定义hash函数为:

x为数值形式的 IP地址，z为大素数4294967291，m为 GBF存储空间大小。通过变换hash函数的id号得到不同的hash函数(0≤id＜k0+k1)，当0≤id＜k0时为置0的hash函数，k0≤id＜k0+k1时为置1的hash函数，定义:

c［id］=2 ×id+1，d［id］=2 × id+2文中选取GBF存储空间大小m为38B(304b)，在hash函数数目为k=k0=k1=2时，根据第三部分对GBF的介绍，最大错报率为6.3%，当攻击路径上有10个路由器时，追踪到最接近攻击端(序号为1)路由器时漏报率达到20%左右(计算方法可参考文献［8］)，若要降低漏报率需增大m/n值。

图2是带GBF的数据包格式，在IP Header之后加入了40字节的IP Option，其中第一字节是flag标志，第二字节是IP Option的大小(size)，在本溯源系统中为0x28(即40字节)，剩下的38字节是GBF。

图2 带GBF的数据包格式Fig.2 Packet format with GBF

2.2 系统设计

Internet是由多个自治系统(Autonomous System)组成，通常一个自治系统代表了一个组织，组织对本自治系统具有完全的管理权。在自治系统内部的追踪溯源称为域内追踪，而在多个自治网络之间的追踪称为跨域追踪。自治系统中一般都部署有自治网络管理机(简称管理机)，由专门的网络管理员操作。为了能追踪到攻击的源头，追踪溯源系统应当同时支持域内追踪和跨域追踪。

基于GBF的追踪溯源系统包含四个组件:路由器标记组件RM(Router Mark)、受害端溯源组件VT(Victim Traceback)、路由器溯源组件RT(Router Traceback)和管理机溯源组件MT(Manager Traceback)。

系统各组件之间的关系如图3所示，n代表数据包经过的路由器数目，m代表数据包经过的自治域数目。RM是部署到路由器上的组件，当数据包经过路由器时，RM将路由器自身的IP地址标记到数据包的GBF中，GBF存储在IP选项中，由于大部分数据包都不使用IP选项，因此不会影响正常数据流解析。

图3 追踪溯源系统Fig.3 Traceback system

VT是部署在受害端的组件。VT是追踪溯源的发起者，当IDS(入侵检测系统)检测到攻击发生时，VT构造ICMP溯源数据包并发送给RT或MT，由RT、MT进行之后的追踪溯源。ICMP溯源数据包中含有从攻击数据包中提取的GBF和开辟的IP地址存储空间。VT同时也是追踪溯源结果的解析者，各级RT、MT会将攻击路径上的路由器IP地址写入ICMP溯源数据包的IP_DATA区域并由最接近攻击机的RT或MT将ICMP溯源数据包发回给VT，VT读取IP_DATA区域就能得到攻击路径。ICMP溯源数据包的格式如图4所示。

图4 ICMP溯源数据包格式Fig.4 ICMP Traceback packet format

RT是部署在路由器上的组件，以图5为例说明RT溯源的过程。攻击数据包经过R4－R3－R2－R1到达受害端;受害端向R1发起溯源请求;R1通过查询GBF判断R2在攻击路径上并将ICMP溯源数据包发给R2;R2收到ICMP溯源请求包之后，检查发现R3的IP地址属于GBF而R5的IP地址不属于GBF，于是R2将ICMP数据包发给R3;R3通过同样的判断过程将ICMP溯源数据包发给R4;R4将ICMP溯源数据包发回给受害端;在整个回溯过程中，各个路由器将自己的IP地址写入了ICMP溯源数据包的IP_DATA区域，因此，受害端可以得到攻击路径V－R1－R2－R3－R4。

图5 RT溯源过程Fig.5 RT Traceback procedure

MT是部署在自治系统管理机上的组件，MT完全掌握本自治系统的网络拓扑，可以在MT上重构该自治系统下的攻击路径。以图6为例说明MT溯源的过程。从A(攻击者)发出的数据包经过R9－R8－R7－R3－R1到达V(受害者);V构造ICMP溯源数据包并发给AS1的管理机M1开始溯源;M1首先进行域内追踪，即对AS1内的所有路由器R1、R2…R7逐一判断是否属于GBF，得到域内追踪的结果R1－R3－R7，并将结果写入ICMP溯源数据包IP_DATA区域，M1接着寻找上级AS，即判断邻接AS的边界路由器R8、R14是否属于GBF，判断结果为R8属于GBF，于是M1将ICMP溯源数据包发给M2;M2做与M1同样的工作，得到AS2域内的追踪结果R8－R9，并将结果写入IP_DATA区域，由于没有上级AS，M2将结果发回V;V重构攻击路径为V－R1－R3－R7－R8－R9，追踪溯源结束。

图6 MT溯源过程Fig.6 MT Traceback procedure

3 实验验证与分析

使用 VMware8.0软件模拟了两个自治系统AS1和AS2，共9个 host－only网络，12个 Linux主机，通过配置路由表和开启IP转发使其中的六个主机以路由器模式运行。AS1由攻击机A、正常主机N1、管理机 M1和三个路由器(R1、R2、R3)组成，AS2由受害主机V、正常主机N2、管理机M2和三个路由器(R4、R5、R6)组成。各设备的网络配置情况如图7所示，省略号“...”代表“192.168”，如“...1.2”即“192.168.1.2”。

图7 实验环境Fig.7 Experimental environment

在各个路由器上运行标记组件RM和溯源组件RT，在管理机M1、M2上运行MT，在攻击主机A上运行攻击程序，向受害主机V发送伪造了源IP地址的UDP攻击数据包。在受害主机V上运行VT，对UDP数据包进行追踪溯源。

VT收到的UDP攻击数据包如图8所示，图中深色部分(IP Options的40字节)是GBF空间，其中0x99是标志，0x28是空间大小，之后38字节是标记后的数据空间，未标记时都为0x00。

图8 数据包标记Fig.8 Packet Mark

VT收到的ICMP溯源结果数据包如图9所示，图中深色部分(ICMP的Data区域)是溯源结果，第一字节0x02代表这是溯源结果数据包，C0A80705即V 自己的 IP 地址(192.168.7.5)，C0A80703 是R6 的 IP 地址(192.168.7.3)，以此类推，可以得到攻击路径V－R6－R4－R2－R1。

图9 溯源结果Fig.9 Traceback Result

4 结语

文中设计的数据包标记追踪溯源系统利用GBF来存储标记信息，具有如下优点:只占用固定大小的空间，数据包不会随着经过路由器数目的增多而增大，减轻了溯源对网络的压力;可以对单独的数据包进行溯源，无需收集大量的数据包;既可以即时溯源也可以事后溯源;在后续的研究中，将进一步优化错报率和漏报率，减小GBF存储空间，研究系统在实际网络环境中的应用问题。

［1］CHANG H Y，NARAYAN R，WU S F.Deciduous:Decentralized Source Identification for Network－based Intrusions［C］//Proceedings of the Sixth IFIP.Boston:IEEE International Symposium on Integrated Network Management，1999:701 －714.

［2］ALEX C，CRAIG P，LUIS A，et al.Hash － Based IP Traceback［D］.Britain:Cambridge，2001:401 －407.

［3］BLOOM B H.Space/Time Trade－Offsin Hash Codingwith Allowable Errors［J］.Communications of the ACM，1970，13(07):422 －426.

［4］BELLOVIN S，LEECH M，TAYLOR T.ICMP Traceback Message［S］.Internet Draft，California:IETF，2003:112－125.

［5］胡长俊.概率包标记技术综述［J］.通信技术，2009，42(02):267－268.HU Chang－ jun.Overview on Probabilistic Packet Marking Technology［J］.Communications Technology，2009，42(02):267－269.

［6］BELENKY A，ANSARI N.IP Traceback with Deterministic Packet Marking［J］.IEEE Communications Letters，2003，7(04):162－164.

［7］刘红，陈秀真，严庆蕾.基于动态概率的多条标记IP追踪方法［J］.信息安全与通信保密，2013(03):66－69.LIU Hong，CHEN Xiu － zhen，YAN Qing － lei.A Multi－Packet Marking Method for IP TracebackBased on DPPM［J］.Information Security and Communications Privacy，2013(03):66－69.

［8］RAFAEL P L，PEDRO B V，OTTO C D.Generalized Bloom Filters［EB/OL］.(2005－05－24)［2014 －01－25］.https://www.gta.ufrj.br/ftp/gta/TechReports/LVD05d.pdf.