基于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.