層次化反匿名聯(lián)盟構建方法*

魯 寧,李 峰,王尚廣,史聞博,楊放春

1(東北大學 信息科學與工程學院,遼寧 沈陽 110819)

2(網(wǎng)絡與交換技術國家重點實驗室(北京郵電大學),北京 100876)

通訊作者:李峰,E-mail:lifeng@neuq.edu.cn

當前,互聯(lián)網(wǎng)轉(zhuǎn)發(fā)數(shù)據(jù)包的依據(jù)是目的IP 地址,通常不對源地址做真實性檢查,這就使得網(wǎng)絡中充斥了大量源地址虛假的匿名包,從而給網(wǎng)絡安全運營帶來了管理和計費問題.因此,如何在互聯(lián)網(wǎng)上建立面向源IP 地址的真實性驗證機制,解決其安全性弱、可信度低問題,進而為用戶提供高度可信的網(wǎng)絡服務,就顯得極其重要.

與互聯(lián)網(wǎng)本身的分層結(jié)構相對應,源地址驗證體系結(jié)構通常也劃分為3 個層次,自底向上分別為接入網(wǎng)絡地址驗證、域內(nèi)網(wǎng)絡地址驗證和域間網(wǎng)絡地址驗證,其中:前兩層都部署在自治域內(nèi),任務是阻止匿名包在域內(nèi)網(wǎng)絡傳播；第3 層通常部署在域邊界路由器,主要任務是通過識別和過濾域間匿名流來實現(xiàn)自治域粒度的網(wǎng)絡保護.由于自治域之間的關系要遠比域內(nèi)關系復雜,因此域間網(wǎng)絡地址驗證就成為整個驗證體系結(jié)構中最為關鍵的一個層次.按照是否需要對已有地址和路由協(xié)議進行擴展和改革,域間源地址驗證研究方法一般又可分為“革新型”和“改良型”兩大類.其中,前者集中于設計一種新的可綁定身份安全機制的地址系統(tǒng)和路由協(xié)議,以達到從根本上解決源地址偽造問題的目的[1-6]；而后者主要關注如何在保證現(xiàn)有地址體系和路由協(xié)議穩(wěn)定的前提下,通過增加檢測機制來彌補現(xiàn)有網(wǎng)絡體系結(jié)構的缺陷[7-9],因此更適合在現(xiàn)有網(wǎng)絡上部署.事實上,確實已有3種經(jīng)典的“改良型”域間源地址驗證方法被當前路由器市場所廣泛接受,它們分別是反向路徑轉(zhuǎn)發(fā)(unicast reverse path forwarding,簡稱uRPF)[7]、入邊界過濾(ingress filtering,簡稱I-filtering)[8]和出邊界過濾(egress filtering,簡稱E-filtering)[9].而本文主要關注其中過濾精度較高、操作開銷較小的E-filtering 方法.

雖然E-filtering 因性能優(yōu)勢而倍受主流網(wǎng)絡設備提供商的青睞,但是當前互聯(lián)網(wǎng)至今仍有38.5%的自治域未加入反匿名聯(lián)盟,這就說明它并未被網(wǎng)絡服務提供商(Internet service provider,簡稱ISP)所廣泛接受,其中的主要原因是它沒有遵循“誰部署、誰受益”的激勵原則,存在搭便車問題,阻礙了它的推廣應用.針對該問題,已有研究者提出了一種基于對等過濾的域間源地址驗證方法(mutual egress filtering,簡稱MEF),其主要任務就是構建一種面向Stub 域的反匿名聯(lián)盟,將未部署E-filtering 的Stub 域從受益者列表中嚴格剝離,只有聯(lián)盟成員才享有域間地址安全的權利[9].為了完成上述功能,該系統(tǒng)首先需要隨時發(fā)現(xiàn)聯(lián)盟成員狀態(tài)(加入和退出)的變化,并將相關信息廣播給其他成員,然后在聯(lián)盟成員的Stub 域邊界路由器的訪問控制列表(access control list,簡稱ACL)上配置面向?qū)Φ瘸蓡T的E-filtering 過濾規(guī)則.但是該方法存在可擴展性差、難以適應增量部署問題,原因如下:過于扁平化、單一化的聯(lián)盟體系結(jié)構,使得過濾器需求量和成員更新傳播范圍隨聯(lián)盟規(guī)模的擴張而急劇增大；過于隨機的非成員判定方式和低效的數(shù)據(jù)處理方式,使得過濾規(guī)則優(yōu)化的計算開銷和精度都有待改善.

針對上述挑戰(zhàn),本文提出一種層次化的基于對等過濾的反匿名聯(lián)盟構建方法(hierarchical anti-spoofing alliance construction approach based on egress filtering,簡稱EAGLE).與已有扁平化的反匿名聯(lián)盟構建方法相比,本方法著力解決了以下3 個問題:(1)立足于實際自治域網(wǎng)絡可分層的拓撲結(jié)構,通過對聯(lián)盟成員分級劃分,構建了新型的層次化的反匿名聯(lián)盟體系結(jié)構,摒棄了傳統(tǒng)方法中扁平的、單一的體系結(jié)構,避免成員之間建立不必要的全連接雙向過濾關系,實現(xiàn)了過濾規(guī)則的精簡,進而降低了過濾器需求量；(2)通過引入Transit 域?qū)Φ冗^濾模塊作為聯(lián)盟邊界,將每一層級聯(lián)盟和外界成員隔離,使得不同層級聯(lián)盟內(nèi)部網(wǎng)絡環(huán)境彼此互不可見,在確保域間高速通信的同時,排除了拓撲結(jié)構和成員變化帶來的影響,有效控制了過濾規(guī)則信息更新的范圍和頻度,進而降低了系統(tǒng)通信開銷；(3)聚焦因聯(lián)盟劃分不均造成高層成員的過濾器資源不足問題,通過定量分析網(wǎng)絡前綴與過濾規(guī)則之間的關系,結(jié)合聯(lián)盟成員動態(tài)變化的特征,設計一種高精度、可增量更新的過濾規(guī)則優(yōu)化算法,在加快求解速度的同時提高解的質(zhì)量.

為了驗證本文提出的EAGLE 方法,首先對其高效性進行了理論分析；然后,在基于真實互聯(lián)網(wǎng)拓撲的網(wǎng)絡仿真環(huán)境下中對其進行了實驗驗證,并與其他經(jīng)典方法進行了對比.結(jié)果表明:EAGLE 不僅延續(xù)了傳統(tǒng)方法的優(yōu)勢,而且通過改善過濾器開銷、通信開銷、計算開銷和優(yōu)化精度來提高可擴展性.

本文第1 節(jié)給出扁平化的基于對等過濾的反匿名聯(lián)盟構建方法形式化描述.第2 節(jié)介紹本文提出的EAGLE 方法,其中,第2.1 節(jié)介紹層次化反匿名聯(lián)盟的基本概念,第2.2 節(jié)給出聯(lián)盟的構建方法,包括系統(tǒng)結(jié)構模型、協(xié)同流程、安全策略、可靠性策略、過濾規(guī)則優(yōu)化策略等實現(xiàn)細節(jié).第3 節(jié)對EAGLE 的性能進行評估,其中,第3.1 節(jié)給出理論評估,第3.2 節(jié)則采用實驗仿真手段對分析結(jié)果進行補充.第4 節(jié)介紹相關工作.第5 節(jié)總結(jié)全文并指出下一步的工作重點.

1 回顧扁平化的基于對等過濾的反匿名聯(lián)盟構建方法

本節(jié)首先構建基于C2P 商業(yè)關系的層次網(wǎng)絡模型,說明上下層自治域的網(wǎng)絡前綴應該存在包含關系；然后回顧基于對等過濾的反匿名聯(lián)盟構建方法,證明它可以解決傳統(tǒng)方法部署激勵性缺乏的問題；最后,通過指出該方法存在可擴展性差等問題,表明本文研究動機.

1.1 基于C2P商業(yè)關系的層次網(wǎng)絡模型

一方面,研究者通過分析自治域(automous system,簡稱AS)路由策略,發(fā)現(xiàn)AS 路徑符合“無谷模型”的特征,即存在嚴格的層次結(jié)構,下層AS 只有通過上層或同層AS 才能將它的數(shù)據(jù)包路由轉(zhuǎn)發(fā)出去.本文將這種由上層向下層提供穿越服務并根據(jù)流量收費的商業(yè)關系稱為客戶-提供商關系(customer-to-provider,簡稱C2P),上層AS 稱為提供商,下層AS 就是它的客戶.另一方面,當前互聯(lián)網(wǎng)為了解決因路由規(guī)模過大而造成路由器的處理能力和內(nèi)存分配趨于飽和問題,廣泛采用了更具層次化的無類別域間路由(classless inter-domain routing,簡稱CIDR)技術來為AS 分配前綴地址塊,使得下層AS 的網(wǎng)絡前綴能夠直接取自它的上層,進而完成下層到上次的路由聚合,減少上層網(wǎng)絡中明細路由的數(shù)量.基于此,本文建立了一種基于C2P 商業(yè)關系的層次網(wǎng)絡模型.

如圖1 所示,該模型是典型的樹形結(jié)構,其中,Stub AS 是葉子節(jié)點,負責生成數(shù)據(jù)流,它只能充當Customer；而Transit AS 是非葉子節(jié)點,負責轉(zhuǎn)發(fā)數(shù)據(jù)流,既能充當Customer,又能充當Provider.此外,該模型具備以下特征:(1)只包含單宿主自治域；(2)客戶地址塊全部取自上層提供商；(3)不包含對等體-對等體(peering-to-peering,簡稱P2P)和同胞-同胞(sibling-to-sibling,簡稱S2S)關系,只突出C2P 商業(yè)關系.

Fig.1 Hierarchical network model based on C2P business relationship圖1 基于C2P 商業(yè)關系的層次網(wǎng)絡模型

提出上述假設的原因在于[10]:

(1)互聯(lián)網(wǎng)中雖然存在一個客戶連接多個提供商的多宿主現(xiàn)象,但是這會引入大量無法聚合的明細路由.因而,絕大多數(shù)客戶仍然在使用單宿主連接方式,只有當網(wǎng)絡規(guī)模超過早期容量規(guī)劃時或為了實現(xiàn)備用路由和可靠通信,才會購買不同提供商的地址塊.然而,即使在多宿主連接下,我們也可按照地址塊將客戶邏輯劃分為多個單宿主,而這種邏輯單宿主依然適合本文關注的出邊界過濾技術,邊界路由器就是先前客戶與提供商的連接接口；

(2)雖然存在因歷史遺留或臨時更換提供商而造成客戶的地址塊與提供商不相符的現(xiàn)象,但是這種連接方式非常少見,因為它相當于在提供商的地址空間鉆了個洞,使得它們不得不針對新引入地址塊設置明細路由.不過,即使客戶采用這種連接,也只是妨礙局部網(wǎng)絡的層次化,但并不影響系統(tǒng)的正常運行以及整個聯(lián)盟的層次化.基于此,該模型未包含這種非常規(guī)連接；

(3)P2P 和S2S 用于說明同層AS 及其客戶之間是否直接可達.就同層直連AS 產(chǎn)生的匿名流來說,采用入邊界過濾(ingress filtering,簡稱I-Filtering)來防御更加合適,因為這種場景既不會引發(fā)I-Filtering 的漏報率較高問題,也不會帶來較大的操作開銷.例如:假設ASA和ASB同層直連,那么在A和B的直連入接口上配置兩條規(guī)則:1)permitASBASA；2)deny any any.其中:規(guī)則1)允許所有源地址包含在ASB,且目的地址包含在ASA的IP 包進入自治域A；規(guī)則2)則指出,凡是不滿足前一規(guī)則的數(shù)據(jù)包都被過濾.由于本文偏向出邊界過濾,因此不包含P2P 和S2S.

定義1.基于C2P 的層次網(wǎng)絡模型定義為前綴樹G=(V,E,A),其中,節(jié)點集V={v|v是G中節(jié)點},邊集E={(u,v)|u,v∈V且u,v互為父子},前綴集A={a(v)|a(v)是節(jié)點v的前綴地址},?u,v∈V且a(u)?a(v),?u-v路徑.

定義2.給定層次網(wǎng)絡模型G=(V,E,A),如果?u∈V,?v∈V,s.t.a(v)?a(u),那么u為Stub 節(jié)點,記為ustub,所有Stub 節(jié)點構成Vstub集合,記為Vstub；反之,若存在v∈V,使得條件成立,u為Transit 節(jié)點,記為utrst,所有Transit 節(jié)點構成Vtransit集合,Vstub∪Vtransit=V.

定義3.匿名流定義為三元組F=(s,i,d),其中,s表示發(fā)送匿名流的自治域,i表示匿名流所攜帶源地址的域前綴,d表示被匿名流攻擊的自治域.一般情況下,在正常網(wǎng)絡環(huán)境中,給定數(shù)據(jù)流F,都有a(F.s)=F.i.然而在匿名網(wǎng)絡環(huán)境下,?匿名流F=(s,i,d),s.t.F.i≠a(F.s)和F.i∈Ωstub,其中,Ωstub表示網(wǎng)絡中Stub 域網(wǎng)絡前綴的全集.針對不同的網(wǎng)絡協(xié)議漏洞,攻擊者通過偽造源地址能夠發(fā)起多種匿名攻擊.根據(jù)源地址與攻擊目標的聯(lián)系,匿名攻擊可劃分為直接攻擊和間接攻擊:前者是由攻擊者直接向受害主機發(fā)起匿名流,其中,匿名流的目的地址就是指向攻擊目標,而源地址可設置為任何虛假IP,常見類型有SYN 風暴攻擊；后者利用網(wǎng)絡協(xié)議中請求和回復包數(shù)量不對稱的特點,先由攻擊者向中轉(zhuǎn)服務器發(fā)起少量匿名請求,使它誤以為該請求由受害主機發(fā)起,進而向受害主機發(fā)送大量回復信息,造成其癱瘓,常見類型有DNS 放大攻擊.基于上述分析,給定匿名流F=(s,i,d),如果F屬于前者,那么d是指匿名流所攜帶目的地址的域前綴；如果F屬于后者,那么d是指匿名流所攜帶源地址的域前綴.為了同時防御二者,反匿名聯(lián)盟成員之間既不應該彼此發(fā)送匿名流,也不應該發(fā)送源地址涉及彼此網(wǎng)絡前綴的匿名流,也就是說,凡是目的地址或源地址隸屬于成員網(wǎng)絡前綴的匿名流都應該被過濾.

1.2 扁平化的反匿名聯(lián)盟構建方法FAGLE

當前,互聯(lián)網(wǎng)協(xié)議通常不對源地址做真實性檢查,因此,攻擊者能夠?qū)⑵渌灾斡騃P 地址寫入數(shù)據(jù)包的源地址字段,誤導受害者.本文將這種源地址虛假的數(shù)據(jù)流稱為匿名流,如定義3 所描述.出邊界過濾(egress filtering,簡稱E-filtering)技術的主要任務就是過濾匿名流和凈化域間網(wǎng)絡,其基本原理正是利用第1.1 節(jié)提到的數(shù)據(jù)流源地址與自治域網(wǎng)絡前綴的隸屬關系來判定數(shù)據(jù)流的合法性,具體過程是在邊界路由器的訪問控制列表(access control list,簡稱ACL)上配置特定的包過濾規(guī)則,對每個流出數(shù)據(jù)包進行驗證:如果發(fā)現(xiàn)其源地址不屬于本網(wǎng)絡范圍,則丟棄；反之,正常轉(zhuǎn)發(fā).本文將這種配置ACL 過濾規(guī)則的邊界路由器稱為邊界過濾路由器(border filtering router,簡稱BFR).以圖1 為例,假設Stub 域AS2的網(wǎng)絡前綴是198.1.2.0/24,那么對于所有從AS2流出的數(shù)據(jù)包來說,其源地址必須隸屬于該前綴,否則就過濾它.基于此,AS2的邊界路由器需要配置以下兩條規(guī)則:(1)permitAS2any；(2)deny any any.其中:規(guī)則(1)允許所有源地址包含在網(wǎng)絡前綴AS2的數(shù)據(jù)包正常轉(zhuǎn)發(fā)；規(guī)則(2)指出凡是不滿足規(guī)則(1)的數(shù)據(jù)包都被過濾,無論其源地址和目的地址是多少.本文將部署E-Filtering 的Stub域記為EStub,將具備匿名包過濾能力的網(wǎng)絡稱為反匿名網(wǎng)絡(anti-spoofing network,簡稱ASN).雖然E-Filtering因輕量、高效等優(yōu)點在提出伊始就被標準化,然而近年的網(wǎng)絡測量驚人地發(fā)現(xiàn),該方法的部署率連續(xù)多年都維持在一個極低的水平.造成這種后果主要原因是,它缺乏部署激勵性.在本文中,部署激勵(incentive for deployment,簡稱Inc)就是指網(wǎng)絡服務提供商對一個反匿名方法的部署意愿程度,它通常表現(xiàn)在部署收益和非部署收益兩方面:前者主要針對已部署反匿名機制的自治域,其部署收益越大,說明該方法的部署激勵越大,反之越?。缓笳咧饕槍ι形床渴鸱茨涿麢C制的自治域,若它們總能不勞而獲,那么收益越大,方法部署激勵就越小,反之越大.基于此,本文借鑒文獻[11]定義部署激勵的思想,首先采用對偶方式來定義部署收益f1和非部署收益f2,然后通過逐一累加反匿名網(wǎng)絡中所有自治域的收益就可評估出方法的部署激勵,如定義4 所述.

定義4.部署激勵可被定義為一個累加函數(shù).

給定反匿名網(wǎng)絡ASN=(G,RA-stub):

為了強化E-Filtering 的激勵功能,Liu 等人借鑒社會學的互動關系理論,定義了一種基于對等過濾的反匿名聯(lián)盟[9],其中,對等過濾(mutual egress filtering,簡稱MEF)是指StubASi能夠阻止流向StubASj匿名流的充分條件是ASj也阻止流向ASi的匿名流,而反匿名聯(lián)盟(anti-spoofing alliance,簡稱AA)就是由具備對等過濾關系AS 組成的集合.雖然反匿名網(wǎng)絡上可能存在多個AA,甚至其成員彼此交叉,但通過定義4 不難推斷出:為了最大化激勵效果,所有成員域都應該加入同一個AA.因此,不失一般性,本文假設整個網(wǎng)絡只有一個AA.部署MEF 方法的Stub 域稱為MStub.在已有的方法中,反匿名聯(lián)盟的所有成員都是MStub,而且它們必須保持完全雙向過濾關系,根據(jù)定義5,它被稱為扁平化的反匿名聯(lián)盟(flat AA,簡稱FAA).

定義5.扁平化的反匿名聯(lián)盟定義為FAA={uMStub∈RA-stub|具備對等過濾關系的MStub 節(jié)點}.?數(shù)據(jù)流F=(s,i,d),已知F.s∈FAA,F滿足以下條件:(1)如果F.d∈FAA,那么F.i=a(uMStub)；(2)如果F.d?FAA,那么或,其中,.

如圖2 所示:在FAA 中,每個MStub 的邊界路由器都需配置4 組ACL 規(guī)則.

Fig.2 An example of FAA圖2 扁平化的反匿名聯(lián)盟舉例

以AS1為例,它的邊界過濾路由器配置規(guī)則如下:(1)permitAS1any；(2)denyAS2&AS4&AS5&AS8&AS10any；(3)deny anyAS1&AS2&AS4&AS5&AS8&AS10；(4)permit any any.其中,

· 規(guī)則(1)允許通過源地址包含在AS1網(wǎng)絡前綴的數(shù)據(jù)包；

· 在前面規(guī)則不滿足的條件下,規(guī)則(2)指出:無論目的地址是多少,所有源地址包含于成員域網(wǎng)絡前綴的數(shù)據(jù)包都將被過濾；

· 在前面規(guī)則都不滿足的條件下,規(guī)則(3)指出:無論源地址是多少,所有目的地址包含于成員域網(wǎng)絡前綴的數(shù)據(jù)包也都將被過濾；

· 規(guī)則(4)則指出,凡是不滿足規(guī)則(1)～規(guī)則(3)的數(shù)據(jù)包都將允許通過.

在基于MEF 的反匿名網(wǎng)絡ASN=(G,RA-stub)中,RA-stub等于反匿名聯(lián)盟AA.?匿名流F=(s,i,d),如果d∈RA-stub,那么F.i=a(F.s)；如果d∈Rc-stub,那么F.i≠a(F.s).與E-Filtering 相比,MEF 能防止非部署者不勞而獲,而僅讓部署者受益,有效地解決了搭便車問題,使得非部署收益f2恒等于0.

1.3 研究動機

在扁平化的反匿名聯(lián)盟中,

· 一方面,為確保對等過濾機制能夠有效運轉(zhuǎn),MStub 域的邊界路由器必須維護面向全部成員的過濾規(guī)則,這就產(chǎn)生以下問題:

(1)過濾器需求量過大.所謂過濾器是指訪問控制列表ACL 的表項,每個表項對應一條ACL 規(guī)則.過濾器不足就意味著ACL 過濾規(guī)則數(shù)量超過了其表項,例如:當聯(lián)盟成員域數(shù)量為N時,每個域的邊界過濾路由器都需要配置o(2N)量級的ACL 過濾規(guī)則.雖然當前路由器大都已提供ACL 過濾平臺,但是它們?nèi)加砂嘿F的三態(tài)內(nèi)容尋址存儲器(ternary content addressable memory,簡稱TCAM)來實現(xiàn),為此,路由器設備商只能通過限制每臺路由器的過濾器數(shù)量來降低成本[12,13].以常見的中端路由器Cisco Catalyst4500 為例,它的ACL 平臺最多只有64 000 個過濾器,而且同時還被384 個接口共享；

(2)較大的通信開銷.例如:當聯(lián)盟成員域數(shù)量為N時,每當新成員加入或舊成員退出的時候,規(guī)則更新消息都將輻射到整個聯(lián)盟范圍,其代價達到o(N)；

· 另一方面,當出現(xiàn)過濾規(guī)則數(shù)量超過過濾器需求的時候,MSM 模塊會執(zhí)行過濾規(guī)則優(yōu)化算法.然而已有算法的效率較低,原因如下:非成員列表作為優(yōu)化算法的重要輸入?yún)?shù),卻采用隨機性較大的排他法來判定,這會影響優(yōu)化解的質(zhì)量,使得過濾器利用率較差；面對不斷變更的聯(lián)盟成員,每次都只能將新舊數(shù)據(jù)重復處理,這會增加計算開銷,影響系統(tǒng)響應時間.

簡言之,以上問題終究會制約反匿名聯(lián)盟的可擴展性.為此,本文希望在繼承原有方法優(yōu)勢的前提下,構建一種層次化的體系結(jié)構,取代扁平化聯(lián)盟的雙向過濾關系,以達到降低通信開銷和過濾器需求量的目的；設計一種可增量更新、高精度的過濾規(guī)則優(yōu)化算法:一方面,利用已測量的拓撲數(shù)據(jù)來判定非成員域；另一方面,通過參考歷史計算結(jié)果來處理新增數(shù)據(jù),并將它們?nèi)诤弦郧蟮米顑?yōu)解.

2 一種層次化的基于對等過濾的反匿名聯(lián)盟構建方法

針對上述問題,本文提出了一種可自下而上分層、基于對等過濾的反匿名聯(lián)盟構建方法(hierarchical antispoofing alliance construction approach based on egress filtering,簡稱EAGLE).本節(jié)將詳細闡述本方法的設計思想和具體實現(xiàn)機制.

2.1 層次化反匿名聯(lián)盟的基本概念

為了保證部署激勵性,本方法依然采用對等過濾思想來建立反匿名聯(lián)盟.隨著越來越多的Stub 域加入聯(lián)盟,反匿名網(wǎng)絡的局部區(qū)域可能出現(xiàn)以下情形:與提供商Transitutrst直接關聯(lián)的所有客戶Stub 都成為MStub,例如,圖3 中TransitAS3的兩個客戶Stub 域AS1和AS2都是MStub.本文將它們前綴的并集AS3∪AS2∪AS1稱為內(nèi)部前綴(inner prefix,簡稱INp).除此之外,聯(lián)盟其他成員前綴的并集統(tǒng)稱為外部前綴(out prefix,簡稱OUTp).就AS1～AS3發(fā)送的匿名流來說,根據(jù)源地址src 和目的地址dst 的可能組合方式,它們分為以下4 種:src∈INp∧dst∈INp,src∈INp∧dst∈OUTp,src∈OUTp∧dst∈INp,src∈OUTp∧dst∈OUTp.前3 種都涉及區(qū)域內(nèi)成員前綴,稱為區(qū)域內(nèi)匿名流(inner anonymous flow,簡稱INf),第4 種只涉及區(qū)域外成員,稱為區(qū)域外匿名流(out anonymous flow,簡稱OUTf).鑒于AS1～AS3是客戶-提供商關系,通過路由策略可推斷出OUTf必然經(jīng)由提供商AS3轉(zhuǎn)發(fā).利用這個特點,我們可以實現(xiàn)層次化的對等過濾,基本原理就是由AS1和AS2來共同過濾INf,而由AS3來過濾OUTf.相應的ACL 規(guī)則配置方法如下:首先,鑒于AS1和AS2的任務相同且關系對等,它們的規(guī)則配置方法也相同.因此,本文只介紹AS1的規(guī)則配置情況.在AS1的邊界過濾路由器上,共需配置4 組規(guī)則:(1)permitAS1any；(2)denyAS2&AS3any；(3)deny anyAS2&AS3；(4)permit any any.其中,第1 組用于判斷數(shù)據(jù)包是否真實,第2 組和第3 組將侵犯同層MStub 域的匿名包全部過濾掉,第4 組用于剪除搭便車的非MStub 域.如果上述場景發(fā)生在第1.1 節(jié)建立的層次網(wǎng)絡中,利用提供商包含客戶前綴的特點,第2 組、第3 組規(guī)則可簡化為圖3 所示:(2)denyAS3any；(3)deny anyAS3.然后,AS3的配置規(guī)則為:(1)permitAS1&AS2&AS3any；(2)denyAS4&AS5&AS6&AS7any；(3)deny anyAS4&AS5&AS6&AS7；(4)permit any any.利用層次網(wǎng)絡的前綴包含關系,第1 組～第3 組規(guī)則則可簡化為圖3所示:(1)permitAS3any；(2)denyAS7any；(3)deny anyAS7.到此為止,完成了由{AS1,AS2,AS3}組成的局部區(qū)域的層次化過濾.從聯(lián)盟其他成員來看,該區(qū)域可被看為一個規(guī)模較大、以INp為前綴的可信邏輯Stub(trusted logical mef-stub,簡稱TMStub),圖3 將它稱為sub-TMStub1.隨著聯(lián)盟規(guī)模的進一步擴大,就有可能生成更高層級的TMStub.例如,隨著sub-TMStub1={AS1,AS2,AS3}和sub-TMStub2={AS4,AS5,AS6}的加入,即可生成TMStub3={sub-TMStub1,sub-TMStub2,AS7}.基于此,本文將TMStub 表示為一個嵌套二元組(uTrst,ISMStub),如定義6 所示,其中,uTrst表示邊界Transit 域,ISMStub表示內(nèi)部其他成員集合.通過層次網(wǎng)絡的前綴包含關系,可推斷出TMStub 的前綴就是utrst的前綴.綜上所述,TMStub 所配置過濾規(guī)則的特點可歸納如下:雖然邊界規(guī)則較為復雜(最高層邊界需要與其他成員實現(xiàn)完全雙向過濾),但是內(nèi)部規(guī)則較為簡單(只需4 條)和穩(wěn)定(既不因外部成員的變化而頻繁更新,又不因聯(lián)盟規(guī)則的增大而加大過濾器需求量).

本文將這種層次化的反匿名聯(lián)盟(hierarchical anti-spoofing alliance,簡稱HAA)表示為{MStub1,…,MStubn,TMStub1,…,TMStubm},其中,MStubi是MStub 類型的成員域,TMStubi是TMStub 類型的成員域,如定義7 所示.與扁平化聯(lián)盟中單一雙向過濾不同,HAA 的過濾場景需要被擴展成3 類.

(1)最高層級聯(lián)盟成員之間過濾——在反匿名聯(lián)盟中,最高層級成員之間互為過濾端,把侵犯彼此的匿名流全部過濾.在這類場景中,每個成員的ACL 規(guī)則都要滿足雙向過濾,并且要實現(xiàn)物理MStub 之間、TMStub 之間以及物理MStub 與TMStub 之間的匿名包過濾,例如圖3 中HAA={TMStub3,Stub8,Stub10},它們之間需要配置雙向過濾規(guī)則,因此該層次的規(guī)則配置最為復雜,開銷也最大；

(2)TMStub 內(nèi)部過濾——TMStub 的內(nèi)部成員域(其成員類型可能是MStub 或sub-TMStub)作為單向過濾端,把侵犯其他內(nèi)部域的所有匿名流全部過濾.在這類場景中,內(nèi)部成員域只需配置面向TMStub 網(wǎng)絡前綴的 ACL 規(guī)則,例如圖 3 中TMStub3={uTrst,ISMStub},其中,uTrst=AS7,ISMStub={sub-TMStub1,sub-TMStub2}.uTrst是邊界Transit 域,鑒于TMStub3已屬于最高層級成員,因此uTrst需配置雙向過濾規(guī)則；而sub-TMStub1和sub-TMStub2作為內(nèi)部成員,分別配置面向AS7的過濾規(guī)則即可.該場景的規(guī)則配置最簡單,開銷也較??；

(3)反匿名聯(lián)盟與非成員之間過濾——聯(lián)盟成員不過濾任意流向非成員域的匿名包.在這類場景中,每個成員既不應該單獨配置面向非成員域的ACL 規(guī)則,也不應該配置可能涵蓋非成員域地址塊的ACL規(guī)則.例如圖3 中Stub9是非聯(lián)盟成員,成員域不會配置任何涉及Stub9網(wǎng)絡前綴的ACL 規(guī)則,允許匿名流進入該域.

綜上所述,雖然定理1 已經(jīng)證明FAA 和HAA 在過濾效果和激勵效果方面理論上相同,但是后者通過引入TMStub,使得Mstub 之間不必保持完全雙向過濾關系,降低了聯(lián)盟建立開銷:(1)成員更新不會輻射到全聯(lián)盟的Mstub 域,只在最高層級聯(lián)盟成員之間傳播,無需通知TMStub 內(nèi)部成員,減少了通信開銷；(2)過濾規(guī)則配置數(shù)量與Mstub 數(shù)量無關,只與最高層級聯(lián)盟成員數(shù)量有關,縮減了過濾器需求量.很明顯,在聯(lián)盟規(guī)模一定的條件下,TMStub 成員數(shù)量越多,最高層級聯(lián)盟成員數(shù)量就會越少,它的性能優(yōu)勢就越明顯.但是,受限于自身策略、網(wǎng)絡結(jié)構和經(jīng)濟、政治、軍事利益等因素,某些Transit 域可能無法或不愿意開啟過濾功能,從而影響聯(lián)盟中TMStub成員數(shù)量.本文將開啟過濾功能的Transit 域,記為Mtransit.不過,即使只有少量TMStub 成員,與FAA 相比,HAA在開銷方面也具明顯優(yōu)勢.這就意味著:我們可以在維持HAA 優(yōu)勢的同時,采用松耦合的方式來生成TMStub,并不要求所有滿足定義6 的局部網(wǎng)絡都建立TMStub,從而能夠更靈活的構建反匿名聯(lián)盟.

Fig.3 An example of HAA圖3 層次化的反匿名聯(lián)盟舉例

定義6.邏輯可信Stub 域定義為二元組TMStub={uTrst,ISMstub},其中,uTrst表示TMStub 的邊界Transit域,ISMstub表示TMStub 的內(nèi)部Mstub 域集合,.?數(shù)據(jù)流F=(s,I,d),已知a(F.s)?a(TMStub),F滿足以下條件:(1)若a(F.d)?a(TMStub),則F.i=a(F.s)；(2)若F.d?a(TMStub),則F.i=a(F.s)或F.i∈a(TMStub)-.

性質(zhì)1.給定TMStub,?數(shù)據(jù)流F=(s,I,d),a(F.s)?a(TMStub)且a(F.d)?a(TMStub),如果F.i?a(TMStub),就有F.i=a(F.s).

證明:運用定義6 即可證明.

定義7.層次化的反匿名聯(lián)盟定義為HAA={MStub1,…,MStubn,TMStub1,…,TMStubm},其中,MStub 是物理MStub 域,TMStub 是最高層的邏輯可信Stub 域.給定u∈HAA,?匿名流F=(s,i,d),已知F.s=u,F需滿足以下條件:

(1)若?v∈HAA,s.t.a(F.d)?a(F.v),那么F.i=a(u)；

(2)若?v∈HAA都不存在a(F.d)?a(F.v),那么.

離心泵在運行過程中因發(fā)生汽蝕直接影響到泵的性能，使泵的效率下降，揚程降低，嚴重時還會產(chǎn)生噪聲和振動，腐蝕破壞葉輪等過流部件[1]。因此，對離心泵的汽蝕性能進行深入的研究，是很有必要且具有重要意義。

定理1.層次化的反匿名聯(lián)盟HAA 與扁平化的反匿名聯(lián)盟FAA 在過濾效果和激勵效果方面理論上相同.

證明:首先,把FAA 的MStub 成員按照HAA 中TMStub 的組成結(jié)構劃分為若干組.以圖3 的HAA={TMStub3,AS8,AS10}為例,已知T1={AS1,AS2,AS4,AS5}隸屬于TMStub3,因此,圖2 中FAA 可劃分為兩組,即FAA=T1∪T2,其中,T2={AS8,AS10}.然后,為了證明FAA 和HAA 的過濾效果相同,將FAA 的匿名包過濾場景分為三類:組內(nèi)成員互相發(fā)送匿名包、組內(nèi)向組間發(fā)送匿名包、組間向組內(nèi)發(fā)送匿名包,從而只需證明3 個場景分別相同即可.

· 場景1:?匿名流F=(s,i,d),如果F.s∈T1且F.d∈T1,根據(jù)定義5 可知F.i=a(F.s).已知?u∈T1都有a(u)?a(TMStub3),根據(jù)定義6 可知F.i=a(F.s).這就意味著FAA 和HAA 在場景1 下過濾效果相同；

· 場景2:?匿名流F=(s,i,d),如果F.s∈T1且F.d∈T2,根據(jù)定義5 可知F.i=a(F.s).已知F.d∈HAA且a(F.d)?a(TMStub3),根據(jù)定義7,可知F.i?a(TMStub3).進一步通過性質(zhì)1 可得F.i=a(F.s).因此,FAA 和HAA 在場景2 下過濾效果相同；

· 場景3:?匿名流F=(s,i,d),如果F.s∈T2且F.d∈T1,根據(jù)定義5 可知F.i=a(F.s).已知F.d∈HAA且a(F.d)?a(TMStub3),根據(jù)定義7,可知F.i=a(F.s).FAA 和HAA 在場景3 下過濾效果也相同.

最后,為了證明FAA 和HAA 的激勵效果相同,只需說明它們都不存在搭便車自治域.也就是說:?匿名流F=(s,i,d),如果F.d?AA,那么不存在F.s∈AA,s.t.F.i=a(F.s).為此,將FAA 的匿名包過濾場景分為兩類:組內(nèi)成員向非聯(lián)盟成員發(fā)送匿名流和組外成員向非聯(lián)盟成員發(fā)送匿名流.

場景1:?匿名流F=(s,i,d),如果F.d?FAA且F.s∈T1,根據(jù)定義5,可知.如果?u∈TMStub3,s.t.a(F.s)?a(u),且?v∈TMStub3,st.a3,s.t.a(F.d)?a(v),根據(jù)定義7,可知.因此,FAA 和HAA在場景1 下不存在搭便車自治域；

場景2 與場景1 相同,也不存在搭便車自治域.

2.2 層次化反匿名聯(lián)盟的構建方法

傳統(tǒng)的E-Filtering 通常是被各個自治域獨立部署,然而層次化反匿名聯(lián)盟HAA 卻要求部署E-Filtering 的自治域之間既能夠及時發(fā)現(xiàn)彼此,也能夠互相交換網(wǎng)絡前綴,因此它的構建必然依賴于一種分布式協(xié)同控制系統(tǒng).鑒于HAA 立足于實際網(wǎng)絡體系結(jié)構,與網(wǎng)絡控制系統(tǒng)相似,該協(xié)同控制系統(tǒng)應具備開放性、簡單性、可擴展性、可靠性等特征.圍繞實現(xiàn)這些特征,接下來我們主要闡述HAA 分布式協(xié)同控制系統(tǒng)的結(jié)構模型、協(xié)同流程、安全策略、可靠性策略、過濾規(guī)則優(yōu)化等.

2.2.1 系統(tǒng)結(jié)構模型

一般來說,按照分布式協(xié)同系統(tǒng)中各部分的位置、角色以及它們之間的關系,其結(jié)構模型可分為兩類:對等結(jié)構和客戶/服務器結(jié)構.若使用前者來構建HAA,為了完成TMStub 成員判別和對等過濾,每個成員域必須通過建立一對多的通信關系來收集其他成員信息,進而獲取聯(lián)盟成員列表.除此之外,鑒于聯(lián)盟與成員之間寬松的綁定關系,每個成員域還需具備鄰接成員資格檢測功能,以便隨時感知新成員的加入和舊成員的退出,進而更新成員列表并將其通知至整個聯(lián)盟,保證元數(shù)據(jù)的一致性.簡言之,這既會加大設計的復雜性,又會產(chǎn)生巨大的通信開銷,進而影響系統(tǒng)的可擴展性.然而,若采用后者來構建HAA,聯(lián)盟成員列表的維護工作(包括成員的動態(tài)加入或退出)將全部由服務器來完成,而成員域作為客戶端,只需提交加入或退出請求即可,成員域之間無需建立任何關系,這既能簡化成員注冊/退出流程,實現(xiàn)系統(tǒng)高效擴展,又能省去鄰接成員資格檢測,降低系統(tǒng)通信開銷.不過,客戶/服務器結(jié)構將所有操作都集中于服務器端,從而使它極易成為整個系統(tǒng)的瓶頸.為了解決該問題,一種直觀的方法是利用TMStub 分層嵌套結(jié)構的特點,將中心服務器的部分管理功能逐層下放到MTransit 域中,由它們負責TMStub 成員的維護以及其內(nèi)部ACL 規(guī)則參數(shù)的傳遞,而服務器只承擔最高層級成員的管理工作.在這種可分層的客戶/服務器結(jié)構模型中,下層自治域若提出注冊/退出請求,正常情況下需要先與上層MTransit域建立通信連接,逐層向上轉(zhuǎn)發(fā)請求信息,以便各層MTransit 域隨時判斷下層成員是否已滿足TMStub 生成條件,直至中心服務器.此外,為了降低系統(tǒng)運行條件,使它更符合真實的網(wǎng)絡環(huán)境,我們不能要求每個Transit 域都成為MTransit.在這種特殊情況下,因上層不存在MTransit,下層自治域只能將注冊/退出請求直接發(fā)送給中心服務器.基于此,上層MTransit 的不確定性導致下層自治域必須具備關于它的檢測功能,然后依據(jù)檢測結(jié)果來選定請求消息的發(fā)送對象,進而再次引發(fā)因系統(tǒng)設計難度大和通信開銷高的問題.因此,利用該模型來構建HAA 并不合適.另一種方法是采用多副本存儲技術,由多個配置完全一致、功能地位對等、所處地區(qū)不同的副本服務器共同組成中心服務器,而由地位完全相等的MTransit 和MStub 成員域組成客戶端.由于該方法的上下層級的成員域之間無需執(zhí)行主從式通信,因此不會引發(fā)可擴展性差的問題.綜上所述,本文最終選定基于多副本均衡負載的客戶/服務器系統(tǒng)結(jié)構模型來構建HAA.

如圖4 所示,HAA 構建系統(tǒng)需要由聯(lián)盟成員管理模塊(alliance management module,簡稱AMM)、Transit 對等過濾模塊(mef-transit module,簡稱MTM)、MStub 對等過濾模塊(mef-stub module,簡稱MSM)、ACL 規(guī)則配置模塊(ACL rule configuration module,簡稱RCM)協(xié)同工作來完成聯(lián)盟成員列表的管理、ACL 規(guī)則的生成和匿名包的過濾.為了降低部署成本,本文借鑒了第1.2 節(jié)提到的文獻[9]中有關控制層面的部署方式,將上述模塊依次部署于聯(lián)盟注冊服務器(alliance registration,簡稱AR)、網(wǎng)絡管理服務器(network management,簡稱NM)、邊界過濾路由器,其中,AR 是由Internet 號碼分配局(Internet assigned number authority,簡稱IANA)或地區(qū)注冊處(regional Internet registries,簡稱RIRs)負責維護的新增互聯(lián)網(wǎng)實體設備,而NM 是由網(wǎng)絡服務提供商負責維護的已存在的網(wǎng)絡實體設備.所不同的是:在EAGLE 中,上述模塊分別被賦予新的職能.MSM 作為核心功能模塊,主要任務有:(1)向AMM 提交成員注冊/退出請求,其內(nèi)容須包含成員的AS 編號和AS 網(wǎng)絡前綴等；(2)接收AMM向它傳遞的ACL 規(guī)則參數(shù),以此為依據(jù),結(jié)合RCM 提供的過濾器數(shù)量,生成ACL 規(guī)則；(3)向同層RCM 發(fā)起ACL 規(guī)則配置請求.MTM 作為新添加模塊,絕大部分任務都與MSM 重合,唯一的區(qū)別是:MTM 向AMM 提交的請求信息中,除了本自治域的AS 編號和AS 網(wǎng)絡前綴,還應包含它所覆蓋下層所有自治域的AS 編號和AS 前綴.RCM 作為過濾執(zhí)行模塊,一邊向同層MTM 或MSM 上傳邊界過濾路由器所擁有的過濾器數(shù)量,一邊接收和配置由它們下發(fā)的過濾規(guī)則.與基于路由的反匿名方法不同[14],本文的過濾規(guī)則表是基于ACL 平臺的,而不是路由轉(zhuǎn)發(fā)表,因此它的下發(fā)過程不依賴于BGP 擴展協(xié)議,而是SSH,TELNET 等遠程通信協(xié)議.鑒于聯(lián)盟成員的動態(tài)性,本文的過濾規(guī)則表無法一次性完全生成,只能增量裝載.為了降低開銷、提升效率,本文建議通過組合當前路由器操作系統(tǒng)(例如Cisco IOS v8.3)已支持的增刪改操作來完成表增量,而不是先刪除后重建.AMM 作為信息匯聚模塊,主要任務有:

(1)利用已有的拓撲測量方法和自治域商業(yè)關系推測方法來獲取AS 級網(wǎng)絡結(jié)構數(shù)據(jù),進而建立第1.1 節(jié)提到的層次網(wǎng)絡結(jié)構模型.在該模型中,Transit 節(jié)點配置兩個屬性:過濾狀態(tài)位和TMStub 狀態(tài)位,前者記為FS,用于聲明相關自治域是否已注冊為成員域；后者記為TS,用于聲明相關Transit 域管轄區(qū)域能否構成TMStub.而Stub 節(jié)點只配置過濾狀態(tài)位FS；

(2)接收和保存MTransit 和MStub 成員域的注冊請求信息,修訂其在層次網(wǎng)絡結(jié)構模型中節(jié)點狀態(tài)信息；

(3)遍歷拓撲結(jié)構模型,依據(jù)定義6 來判別部分注冊成員是否能生成TMStub,在修改節(jié)點狀態(tài)位的同時更新聯(lián)盟成員列表(alliance member list,簡稱M-List),以此為基礎,結(jié)合第2.1 節(jié)的過濾場景,給每個成員下發(fā)相應的ACL 規(guī)則參數(shù).

Fig.4 System structure overview for HAA (HAA from Fig.3)圖4 HAA 構建系統(tǒng)的結(jié)構模型(聯(lián)盟結(jié)構源于圖3)

2.2.2 協(xié)同流程

在層次化反匿名聯(lián)盟中,數(shù)據(jù)包的過濾動作受聯(lián)盟成員列表的控制,而成員列表又因MTransit 和MStub 域的加入或退出發(fā)生變化,原因是它們可能引發(fā)TMStub 的生滅,進而造成列表成員的聚合和裂變.因此,MTransit和MStub 域的加入或退出是觸發(fā)系統(tǒng)運行的主要事件.本文以圖4 為例來分別闡述當上述事件發(fā)生后,各模塊之間是如何協(xié)同、完成列表更新的.假設StubAS2,AS4,AS5,AS7都已注冊為成員域,AMM 的網(wǎng)絡拓撲結(jié)構模型如圖1 所示,成員列表M-List={AS2,AS4,AS5,AS7}.

(1)非成員域若想加入聯(lián)盟,先得向AMM 提出注冊申請.

AMM 在收到申請后,首先在拓撲結(jié)構模型中查找注冊域?qū)?jié)點,修改其過濾狀態(tài)位,并將其孩子節(jié)點與申請消息中下層自治域逐一匹配,糾正拓撲模型的節(jié)點漏報；然后判定TMStub 域的生成,依據(jù)判定結(jié)果,修改相關邊界域的TMStub 狀態(tài)位,同時更新成員列表,最后向聯(lián)盟成員(包括ASi)下發(fā)新的ACL 規(guī)則參數(shù)；成員域收到參數(shù)后,依據(jù)過濾器數(shù)據(jù),優(yōu)化過濾規(guī)則,并將其下發(fā)到RCM；RCM 通過配置規(guī)則,完成匿名包過濾.整個過程需AMM 完成定位、判定、更新這3 個任務,接下來主要說明它們的實現(xiàn)方式.

a.鑒于拓撲結(jié)構模型存在逐層匯聚的特點,本文將它定義為一種可用于快速檢索的多叉樹結(jié)構——前綴樹(retrieval tree,簡稱Trie),通過它的查找方法即能快速定位自治域；

b.不同類型申請域的判定方法也不同.若Transit 域ASi申請加入,首先查驗以ASi為首的局部網(wǎng)絡是否生成TMStub,然后采用向上就近查驗原則,逐層判定高層級的TMStub.例如:若AS3希望成為MTransit,因為在其管轄的局部網(wǎng)絡中AS1尚未注冊,所以不滿足TMStub 生成條件,判定結(jié)果為MTransit.AS6在AS3加盟后也提出注冊請求,因其管轄的AS4和AS5都已加入聯(lián)盟,生成sub-TMStub2.然后查驗以AS6為首、覆蓋sub-TMStub2的局部網(wǎng)絡,條件不再匹配,最終判定結(jié)果為TMStub.若Stub 域ASj申請加入,直接采用向上就近查驗原則即可.例如:繼AS3和AS6后,AS8提出申請,因以AS11為首、覆蓋AS8的局部網(wǎng)絡存在非成員域,TMStub 判定結(jié)果為MStub.此后,AS1選擇加入,生成sub-TMStub1,然后查證以AS7為首、覆蓋sub-TMStub1的局部網(wǎng)絡,生成TMStub3,最終判定結(jié)果為TMStub；

c.依據(jù)TMStub 判定結(jié)果,選擇成員列表更新方法.若結(jié)果為Transit 域,無需更新.例如,加入AS3既沒有生成新TMStub,也不影響對等過濾,因此M-List={AS2,AS4,AS5,AS7}.若結(jié)果為TMStub 域,需要將成員列表的部分成員聚合為該自治域.例如:加入AS6生成sub-TMStub2,先將該TMStub 添加到成員列表,后將它覆蓋的成員前綴AS4和AS5刪除,M-List={AS2,AS7,sub-TMStub2}.若結(jié)果為Stub 域,直接將它添加到成員列表.例如,加入AS8雖然沒有生成新TMStub,但是為了不影響對等過濾效果,M-List更新為{AS2,AS7,AS8,sub-TMStub2}.

(2)成員域若想退出聯(lián)盟,先得向AMM 提出退出請求.

AMM 在收到請求后,首先在拓撲結(jié)構模型中修改相關節(jié)點的過濾狀態(tài)位,然后將該節(jié)點及其祖先節(jié)點的TMStub 狀態(tài)位都改為False,最后更新成員列表,向聯(lián)盟成員下發(fā)規(guī)則參數(shù)；成員域和RCM 的處理過程與步驟(1)相同.值得說明的是,列表更新方法取決于退出成員類型及其前綴與成員列表的關系.若MTransitASi選擇退出且它的前綴等于或包含于最高層級的TMStub 成員,首先分裂與ASi相關的所有TMStub,然后將剩余TMStub和MStub 添加到成員列表,例如:當M-List={sub-TMStub3,AS8}運行一段時間后,MTransitAS3因經(jīng)濟或政治原因選擇退出,希望重新變?yōu)門ransit 域,與AS3相關的TMStub 域(包括sub-TMStub1和sub-TMStub3)全部發(fā)生裂變,最終剩余MStubAS1,AS2和sub-TMStub2,從而將M-List更新為{AS1,AS2,sub-TMStub2,AS8}；若ASi的前綴與任何成員不發(fā)生關系,無需更新,例如:繼AS3后,AS7也選擇退出,它就與M-List成員無交集；若MStubASj選擇退出且它的前綴等于最高層級成員,就直接將它從列表中刪除,例如:AS8退出不會引發(fā)TMStub 分類,只需更新M-List={AS1,AS2,sub-TMStub2}；若ASj前綴包含于某TMStub 成員,其處理過程與MTransit 退出相同,例如:AS4退出造成sub-TMStub2的裂變,使M-List更新為{AS1,AS2,AS5}.

2.2.3 安全和可靠性策略

就安全性而言,HAA 構建系統(tǒng)的開放性允許任何陌生自治域都能向AMM 提出成員注冊、退出請求,這為匿名、中間人等惡意攻擊的發(fā)起提供了可能,究其原因在于:(1)AMM 無法通過成員域的網(wǎng)絡前綴來識別其身份；(2)成員域MTM/MSM 無法確認AMM 發(fā)送的消息中ACL 規(guī)則參數(shù)是否被篡改.基于此,系統(tǒng)模塊之間的通信只有嵌入身份認證和消息驗證才能預防上述攻擊.為此,本文以節(jié)約部署成本、保證執(zhí)行效率為出發(fā)點,先使用資源公共密鑰基礎架構(resource public key infrastructure,簡稱RPKI)來保障MTM/MSM→AMM 的通信安全,后使用RSA 數(shù)字簽名來完成AMM→MTM/MSM 的安全通信,最終實現(xiàn)它們之間安全的雙向通信.

鑒于核心管理模塊AMM 的負載較重,本文采用多副本存儲技術來構建AMM,這雖然提升了HAA 系統(tǒng)的可靠性和可用性,但是也帶來管理難題,包括如何放置副本、如何均衡副本負載、如何保持副本之間的成員數(shù)據(jù)一致性、如何處理副本故障等.本文以高效、實用為出發(fā)點,分別選用如下技術來解決上述問題.

· 為了降低通信時延、縮短響應時間,引入數(shù)據(jù)分區(qū)技術,將AMM 按照RIRs 的組織方式劃分為5 份,每個注冊地區(qū)至少放置一個AMM 副本,除了少量的跨分區(qū)通信外,大部分的分區(qū)都可獨自地處理服務請求；

· 若所屬注冊地區(qū)存在多個副本,客戶端通過循環(huán)域名服務技術(round-robin DNS,簡稱RR)來選定與它通信的副本服務器,從而保證各副本之間的負載平衡；

· 通過對AMM 業(yè)務特點進行分析,選定通信開銷較小的最終一致性模型來完成副本數(shù)據(jù)之間的同步,通過犧牲一致性來換取高可靠性和可用性；

· 采用自適應檢查點機制和Merkle 哈希樹來解決臨時故障和永久性故障.

2.2.4 過濾規(guī)則優(yōu)化

在HAA 構建初期,聯(lián)盟中MStub 成員類型較多而TMStub 成員類型較少,進而造成絕大部分成員位于聯(lián)盟最高層.根據(jù)過濾場景1 可知,最高層成員之間需要維持雙向過濾關系,因此這會產(chǎn)生過多過濾規(guī)則,從而使邊界過濾路由器的過濾器資源發(fā)生短缺.為此,MTM 和MSM 模塊如何在不損害激勵機制的前提下優(yōu)化過濾規(guī)則、降低過濾規(guī)則對過濾器的需求,成為決定HAA 激勵性能的關鍵問題.

2.2.4.1 過濾規(guī)則優(yōu)化問題形式化描述

如圖3 所示,按照功能不同,位于聯(lián)盟最高層成員的BFR 所配置的過濾規(guī)則可劃分為4 組,其中:第1 組和第4 組分別只含一條規(guī)則,而第2 組和第3 組所含規(guī)則較復雜.因此,BFR 通常能夠容納第1 組、第4 組規(guī)則,卻無法容納其余兩組.基于此,本文主要集中于優(yōu)化第2 組、第3 組規(guī)則.鑒于這兩組規(guī)則都具備一維特性(其規(guī)則參數(shù)僅局限于源地址或目的地址且二者只能取其一),過濾規(guī)則優(yōu)化可歸為同一前綴壓縮問題(same prefixes compression,簡稱SPC).給定一組去本地化且彼此不重疊的成員列表M-List、一組彼此不重疊的非成員列表W-List、過濾器投入量Rmax以及一組歸一化的地址權重集W.為了覆蓋所有M-List成員,同時最小化搭便車率(free riding ratio,簡稱FRR),SPC 可被形式化為如下方程:

其中,公式(1)表明優(yōu)化目標,g是FRR的決定因子；公式(2)表明過濾器投入數(shù)量不高于Rmax；公式(3)表明每個成員前綴有且只能被過濾一次,否則會浪費過濾器；公式(4)表明決策變量的取值范圍.

定義8.成員列表,其中,表示HAA 中最高層成員ASi的網(wǎng)絡前綴(若是TMStub,則ASi就是TMStub 邊界域).M-List的成員具備兩個性質(zhì).

其中,Ωp表示IP 前綴全集.

定義9.亞屬于∈sub:ip∈subList,當且僅當,其中,List表示M-List或W-List,ip表示IP地址.

定義10.非成員列表,其中,表示未加入聯(lián)盟的StubASi網(wǎng)絡前綴.W-List具備以下性質(zhì):

定義11.決策變量xp∈{0,1},當p∈L時,xp=1；當P?L時,xp=0.其中,L表示規(guī)則優(yōu)化算法輸出的網(wǎng)絡前綴集.Rmax是指過濾器最大投入數(shù),也就是說|L|≤Rmax.

定義12.地址權重wip∈[0,1],表示免費保護地址ip可能帶來多大程度的不良影響.若ip∈subM-List,wip=0；若ip∈subW-List,wip＞0.

定義13.地址權重集,為了描述簡單,對權重進行歸一化處理,使得.給定W,?網(wǎng)絡前綴P∈L,它的權重.

定義14.搭便車率是指得到免費保護的網(wǎng)絡前綴的總權重.

2.2.4.2 過濾規(guī)則優(yōu)化算法

文獻[13]指出,SPC 問題可歸為多維背包問題(multidimensional knapsack problem,簡稱dKP).眾所周知,dKP屬于NP-hard 范疇,若使用常規(guī)解法,例如分支界限法和割平面法,雖然能夠求得精確解,但是運行時間隨著反匿名聯(lián)盟規(guī)模的增大會呈指數(shù)增長,從而使得各成員域的MTM 或MSM 模塊無法快速求得最優(yōu)解.其次,聯(lián)盟規(guī)模的逐漸擴張要求過濾規(guī)則優(yōu)化算法必須具備增量更新的特點,否則,若新舊過濾規(guī)則合并后再優(yōu)化,那么這一方面會因數(shù)據(jù)集過大而消耗太多的時間和存儲空間,另一方面則會因全局優(yōu)化使得原有過濾規(guī)則也需重新配置,產(chǎn)生額外處理開銷.Soldo[13]曾經(jīng)提出一種基于最長公共前綴樹(longest common prefix tree,簡稱LCP)、可增量更新的動態(tài)規(guī)劃算法,用來解決IP 地址優(yōu)化問題.經(jīng)過碎片化處理,雖然能夠?qū)⒈疚乃P注的前綴優(yōu)化也轉(zhuǎn)化為上述的IP 地址優(yōu)化,但是這會造成IP 數(shù)量激增,進而帶來龐大的計算開銷.為此,Liu[9]提出了基于擴展LCP 樹(extended LCP,簡稱ELCP)的動態(tài)規(guī)劃算法,它在保證解質(zhì)量的同時提高了求解速度.然而該算法存在兩點不足.

(1)采用排他法來建立非成員列表W-List,即?ip,ip∈M-List?ip?W-List.由于W-List是構建ELCP 樹的重要數(shù)據(jù)源,這既會生成大量碎片IP,進而造成ELCP 樹的規(guī)模過大,產(chǎn)生較大內(nèi)存開銷,又會因多余的W-List成員而影響ELCP 樹非葉子節(jié)點中誤報率屬性的計算結(jié)果,進而降低了算法優(yōu)化精度.原因如下:假設兩個自治域執(zhí)行聚合操作,判斷其結(jié)果是否引入誤報的依據(jù)應該在于它有沒有夾雜其他真實自治域的網(wǎng)絡前綴,而與這兩個自治域的網(wǎng)絡前綴是否連續(xù)沒有直接關系.也就是說:即使它們不連續(xù),只要聚合結(jié)果不包含真實自治域,它也就不會引發(fā)誤報.然而在上述方法中,鑒于W-List包含大量非真實自治域IP,這會造成ELCP 樹包含許多無用白色葉子節(jié)點,進而影響非葉子節(jié)點中誤報率屬性的計算,最終誤導算法的優(yōu)化方向,降低它的求解精度；

(2)不再支持增量更新,降低了算法重新求解的效率.

針對上述兩個問題,本文提出了一種可增量的高效過濾規(guī)則優(yōu)化算法.

從聚合角度來看,SPC 問題就是在指定數(shù)量的條件下搜索一組誤報率最小的M-List成員聚合前綴.基于此,可增量的過濾規(guī)則優(yōu)化過程可劃分為3 步:第1 步,以最小化聚合誤報為目標,推測M-List成員最優(yōu)聚合次序,提取它們的聚合前綴,組成最優(yōu)前綴集I-Set；第2 步,從I-Set 中挑選數(shù)量不超過|Rmax|個、彼此不相交、累積聚合誤報最小的前綴,組成最終結(jié)果F-Set；第3 步是在成員加入或退出的時候,及時更新I-Set,以便重新計算F-Set.每一步的實現(xiàn)方式如下所述.

根據(jù)定義15 可知:聚合操作屬于二元運算,且滿足交換律和結(jié)合律,因此任何加括號的方法都會得到相同的計算結(jié)果.例如,則共有3 種加括號方式:,它們的計算結(jié)果完全相等.然而不同的加括號方法通常會產(chǎn)生不同的累積聚合誤報,例如:根據(jù)定義 16,,而且.此時,如果,那么不難推斷.因此,如何優(yōu)化聚合次序(即加括號),使M-List成員聚合操作產(chǎn)生最小的累積誤報率,成為首先需要解決的關鍵問題.

在提出解決方案之前,本文對聚合優(yōu)化問題做了如下分析.

· 首先,給定一個規(guī)模為n的M-List,令P(n)表示可供選擇的括號化方案的數(shù)量,不難推出,這意味著括號化方案數(shù)量與n呈指數(shù)關系,因而窮舉法的效率會非常差；

· 其次,根據(jù)定理2,聚合優(yōu)化問題具備最優(yōu)子結(jié)構和重疊子問題等基本要素,因此我們可以利用基于自底向上的動態(tài)規(guī)劃方法來對它求解,即,通過子問題的最優(yōu)解來逐層向上遞歸構造出原問題最優(yōu)解.整個過程可看做是在構建一顆二叉樹:首先,從M-List中挑選聚合誤報最小的兩個成員作為參數(shù)；然后建立一顆以參數(shù)為葉子、聚合前綴為根的二叉子樹；最后,將該子樹插入M-List,同時刪除M-List中與子樹相關的成員.逐層向上重復上述動作,最終生成一顆前綴聚合二叉樹,樹中所有非葉子節(jié)點就可組成最優(yōu)聚合前綴集I-Set.

基于上述分析,因為二叉線索樹能夠標識出哪些節(jié)點對應最優(yōu)聚合前綴,所以通過遍歷就能獲取最優(yōu)聚合前綴集I-Set.此外,由于M-List和W-List成員因聯(lián)盟規(guī)模變化而不斷更新(加入或退出),因此樹的建立過程除了在BT 中標識最優(yōu)聚合前綴和計算聚合誤報兩個階段,還應包括更新階段.更新操作由成員變化類型而決定.例如:當M-List加入新成員m時,如果m之前屬于W-list,說明樹中已包含m；如果m不屬于W-List,先遍歷已存在節(jié)點,不做任何操作,后插入新節(jié)點.當W-List加入新成員n時,操作過程與第二階段相同.退出M-List相當于是向W-List添加新成員,因此該操作與上一過程相同.

定理2.聚合優(yōu)化問題能夠采用動態(tài)規(guī)劃方法來求解.

證明:眾所周知,只有具備最優(yōu)子結(jié)構和子問題重疊特征的最優(yōu)化問題才適合使用動態(tài)規(guī)劃方法來求解.基于此,我們首先發(fā)掘聚合優(yōu)化問題的最優(yōu)子結(jié)構,該證明過程通常遵循如下模式.

a.如果對M-List所有成員執(zhí)行聚合操作,那么必先將M-List劃分為兩個子集sub1和sub2,聚合誤報ρ(M-List)=ρ(sub1)+ρ(sub2)+ΔM-List,其中,Δ表示包含于M-List的聚合前綴、與sub1和sub2無交集的聚合誤報；

b.假設sub1和sub2是M-List的最優(yōu)分割子集,那么對子集sub1進行聚合優(yōu)化,直接采用獨立求解該子集時所得的最優(yōu)方案即可.這樣做的原因可采用“剪切-粘貼”技術證明:如果不采用獨立求解sub1所得的最優(yōu)分割方案來對它進行聚合操作,那么可以將此最優(yōu)方案帶入M-List的最優(yōu)方案中,代替原來對子集sub1進行分割的方案,顯然,這樣得到的方案比M-List原來最優(yōu)方案的誤報更低,這與之前假設相矛盾.對子集sub2來說,可得到相似的結(jié)論:在原問題M-List的最優(yōu)分割方案中,對子集sub2進行分割的方法,就是它自身的最優(yōu)分割方案.然后,證明聚合優(yōu)化問題的的遞歸算法會反復地求解相同的子問題,而不是一直生成新的子問題,這也就證明它具備子問題重疊性質(zhì).

假設m[An]表示在聚合基數(shù)為n的前綴集An時所生成的最小誤報,根據(jù)最優(yōu)子結(jié)構可知m[An]=m[Ai]+m[An-i]+.考慮到子集Ai與An-i彼此關系對等,An的分割方案有種.由于最優(yōu)分割方案必在其中,我們只需檢查所有可能情況,找到最優(yōu)者即可.因此,An最優(yōu)分割方案的遞歸求解公式變?yōu)?/p>

通過觀察該函數(shù)的遞歸調(diào)用樹不難發(fā)現(xiàn):在求解高層的子問題時,底層子問題的解會被反復調(diào)用,這也就滿足了子問題重疊的特征.

定義15.聚合∞:Pi,j=Pi∞Pj,當且僅當(Pi?Pi,j)∧(Pj?Pi,j),且?P′∈Ωp,s.t.,(Pi?P′)∧(Pj?P′),都有(Pi,j?P′).

定義16.聚合誤報ρ(Pi,Pj),當且僅當,其中Pi,j=Pi∞Pj,也可記為ρ(Pi,j).

性質(zhì)2.給定M-List={P1,P2,…,Pn},如果LCP(Pi,Pj)≥LCP(Pi,Pk),其中,Pi,Pj,Pk∈M-List,LCP表示最長公共前綴,那么ρ(Pi,Pj)≤ρ(Pi,Pk).

證明:鑒于最長公共前綴具備網(wǎng)絡前綴的性質(zhì),已知LCP(Pi,Pj)≥LCP(Pi,Pk),可推出Pi,j?Pi,k,其中,Pi,j=Pi∞Pj,Pi,k=Pi∞Pk,根據(jù)定義16,就可得到ρ(Pi,Pj)≤ρ(Pi,Pk).

定義17.網(wǎng)絡前綴序列空間被定義為一種三元組H=(I,S,P),其中,

· 前綴變量集I:I={P1,P2,…,Pm}為所涉及網(wǎng)絡前綴的定義范圍；

· 操作P:關于S中的前綴變量的操作集.

由于變量集實際上是由二進制字符串構成,因此,傳統(tǒng)的絕大部分字符串操作對它仍然是適用的,例如屬于(∈)、包含(?)、交(∩).然而,對于網(wǎng)絡前綴集格來說,僅有這些操作是不夠的,還需要擴展它的操作能力.首先,遵循全序關系的自反性、反對稱性和傳遞性原則,給定pi,pj∈I,網(wǎng)絡前綴之間可能存在的“=”、“＞”和“＜”關系重新定義如下:(1)若pi=pj,那么?m∈[1,32],；(2)若pi＞pj,那么?m∈[1,32],使得且?k＜m,；(3)若pi＜pj,那么?m∈[1,32],使得且?k＜m,.

以圖5 為例,已知M-List={AS1,AS4,AS8,AS9},W-List={AS2,AS5,AS10}和全部源自圖1.樹的構建分為兩個階段:M-List成員插入和W-List成員插入.每個節(jié)點都有兩個屬性:最優(yōu)聚合前綴和誤報量.前一階段負責在尚未插入W-List的二叉樹中標識最優(yōu)聚合前綴,即將葉子和度為2 的節(jié)點的最優(yōu)聚合前綴設置為True,如圖5(1)所示；后一階段負責在原有樹的基礎上標識誤報量,如圖5(2)所示.

Fig.5 An example of BT圖5 二叉字典樹(BT)舉例

定義18.二叉線索樹(binary trie tree,簡稱BT)定義為BT(H.I),其中,H.I=M-List∪W-List表示無序的前綴變量集.BT 具備以下幾個特征.

1)每條從節(jié)點到根的路徑都對應一個網(wǎng)絡前綴的網(wǎng)絡號；

2)非葉子節(jié)點的左孩子取值為0,右孩子取值為1,這能使得樹節(jié)點滿足序列空間所定義的前綴比較方法從左到右依次增大；

3)以最優(yōu)聚合前綴為判別依據(jù),將樹節(jié)點分為白、黑兩種:若某節(jié)點與最優(yōu)聚合前綴(包括M-List成員前綴和它們之間的最長公共前綴)對應,那么該葉子為黑色；否則,為白色；

4)每個節(jié)點前綴所累計的聚合誤報用矩形框來標識到它的附近.

(2)給定二叉線索樹BT,從中搜索|Rmax|個、彼此不相交且標識最優(yōu)聚合前綴的樹節(jié)點.

通過分析不難發(fā)現(xiàn):不同的節(jié)點組合會累積不同的聚合誤報.以圖5 為例,假設|Rmax|=3,滿足上述條件的樹節(jié)點組合有兩種:A={AS1,AS4,p2}和B={AS10,AS8,p3},其中,,也就是說A比B更高效.基于此,如何獲取累積聚合誤報最小的節(jié)點組合就成為第2 個需要解決的問題.

最優(yōu)前綴選擇問題可描述如下:給定|Rmax|個過濾器序列,通過遍歷二叉線索樹中擁有最優(yōu)聚合前綴的節(jié)點來求取一種分配方案,使得累積聚合誤報最小.首先,令Lp(k)表示當使用k個過濾器來覆蓋最優(yōu)聚合前綴p時可供選擇的分配方案.當k=1 時,只有一種分配方案；當p=leaf時,也只有一種分配方案；當k≥2 時,分配方案可描述為兩個子方案相乘的形式,而兩個子方案的劃分點在第k個過濾器和第k+1 個過濾器之間,k為1,2,…,|Rmax|-1中的任意一個值.基于此,可以得到如下遞歸公式:

其中,sl和sr分別表示在p的左子樹和右子樹中離p最近的最優(yōu)聚合前綴節(jié)點,而Lsl(k)和Lsr(n-k)則表示關于sl和sr的分配方案.該公式與矩陣鏈相乘問題的遞歸公式相似,它的序列增長速度接近Ω(2n),也就是說分配方案數(shù)量與n呈指數(shù)關系.因此,通過暴力搜索所有分配方案來尋求最優(yōu)組合并不高效.然后,最優(yōu)前綴選擇問題也能夠使用基于自底向上的動態(tài)規(guī)劃方法來對它求解,其證明過程與定理2 相似.

(3)假設二叉線索樹BT 已成功建立,每當有新成員加入或舊成員退出時,BT 都需要被更新.

例如:自治域s準備加入聯(lián)盟,如果s包含于已選定的過濾器,那么只需將它插入到BT 即可；反之,除了插入操作,它還需要重新計算最優(yōu)前綴.不過,它的計算開銷與第(2)步相比減少了很多,原因如下:本次只需計算s的上游節(jié)點,其他結(jié)果可直接從之前的結(jié)果中提取.當s選擇退出聯(lián)盟時,首先從BT 中刪除一個成員s,然后重新計算位于s上游的最優(yōu)前綴.簡言之,利用第(2)步已保存的所有中間結(jié)果,更新算法只需重新計算與新增節(jié)點相關的最優(yōu)解.

3 性能評價

為了驗證提出的EAGLE 方法,本文進行了理論分析和仿真實驗,其中,第3.1 節(jié)將使用理論分析來證明方法的高效性,第3.2 節(jié)則通過基于真實網(wǎng)絡拓撲的實驗仿真來補充分析結(jié)果.

3.1 理論分析

通過與經(jīng)典的反匿名聯(lián)盟構建方法(包括E-Filtering,FAGLE 等)進行比較,本節(jié)將使用數(shù)學方法來分析EAGLE 方法的性能,涉及的指標包括部署激勵(deployment incentive,簡稱Inc)、過濾器需求(filter demanded,簡稱FD)、通信開銷(system communication overhead,簡稱SC)、存儲開銷(system storage overhead,簡稱SS)、規(guī)則優(yōu)化誤報(false positive of filter optimization,簡稱FP)、規(guī)則優(yōu)化的時間復雜度(time overhead for filter optimization,簡稱TF)和規(guī)則優(yōu)化的空間復雜度(space overhead for filter optimization,簡稱SF).

3.1.1 部署激勵

部署激勵指網(wǎng)絡服務提供商ISP 對反匿名方法的部署意愿程度.鑒于ISP 部署新技術的動力是追求潛在的經(jīng)濟利益,Inc 的大小取決于部署收益和非部署收益兩方面:前者是當一個自治域部署了反匿名方法后,其受到的偽造攻擊中匿名報文減少比率的期望增量；后者是就一個尚未部署反匿名方法的自治域而言,其獲得匿名報文的減少比率.很明顯,Inc 與部署收益成正比,而與非部署收益成反比.基于此,本文采用對偶方式來定義部署收益f1＞0 和非部署收益f2＜0,而將Inc 定義為二者之和f1+f2,見定義5.在基于E-Filtering 的反匿名網(wǎng)絡中,各自治域除了部署收益,還存在非部署收益,因此IncE-Filtering＜f1；在基于對等過濾的反匿名網(wǎng)絡中,各自治域只具備部署收益而沒有非部署收益,因此IncMEF=f1.此外,根據(jù)定理2 可知,FAGLE 和EAGLE 的過濾效果在理想情況下是相同的,進而推出IncFAGLE=IncEAGLE.然而在過濾器短缺和規(guī)則優(yōu)化精度等因素影響下,上述兩個方法都會產(chǎn)生聚合誤報ρFAGLE和ρEAGLE,從而使得部分自治域再次獲得非部署收益.在M-List和Fmax給定的條件下,一方面,鑒于聚合操作是在過濾器需求量FD 超過過濾器供應量的時候發(fā)生的,FD 越缺乏,聚合執(zhí)行越頻繁,誤報量也越大,可得ρ與FD 成正比關系；另一方面,鑒于聚合結(jié)果會受規(guī)則優(yōu)化算法求解質(zhì)量的影響,優(yōu)化解的誤報越高,聚合誤報也越高,可得ρ與規(guī)則優(yōu)化誤報FP 也成正比關系.基于此,本文將ρ定義為一種以FD 和FP 為變量的單調(diào)遞增函數(shù).

根據(jù)第 3.1.2 節(jié)和第 3.1.5 節(jié)可知,FDFAGLE≥FDEAGLE和FPFAGLE≥FPEAGLE,因此,ρFAGLE(FDFAGLE)≥ρEAGLE(FDEAGLE),進而得到IncE-Filtering＜＜IncFAGLE≤IncEAGLE.

3.1.2 過濾器需求

過濾器需求是指在不執(zhí)行規(guī)則優(yōu)化的前提下,每個AS的邊界過濾路由器平均配置過濾規(guī)則的數(shù)量,它會間接影響構建系統(tǒng)的部署激勵性.給定一個反匿名網(wǎng)絡ASN=(G,RA-stub),不失一般性,假設每個AS只有一個網(wǎng)絡前綴,通過第1.3 節(jié)和第1.4 節(jié)所述,不難推出:E-Filtering 的過濾器開銷FDE-Filtering=2；FAGLE 的過濾器開銷FDFAGLE=2|RA-stub|+1；在EAGLE 中,最高層成員分為TMStub 和MStub 兩類,其中,TMStub 內(nèi)部成員(包括MStub和MTransit)的過濾器開銷FDEAGLE-Intra=4,最高層成員的過濾器開銷FDEAGLE-Inter=2×最高層成員數(shù)量+1.在|RA-stub|為常數(shù)的情況下,如果RA-stub的成員壓縮比r=最高層成員數(shù)量/所有MStub 成員數(shù)量|RA-stub|,那么EAGLE的過濾器需求FDEAGLE可定義為一元整數(shù)分段函數(shù),如下所示:

很明顯,r越大,FDEAGLE越大,當r=1 時,FDEAGLE=FDM；r越小,FDEAGLE越小.需要說明的是,當r=1/|RA-stub|時,相當于最高層只有一個成員,FDEAGLE等于2.因此,FDEAGLE＜＜FDM.這就意味著:即使只有極少量MStub 聚集成為TMStub,與FAGLE 相比,EAGLE 在過濾器需求方面也會有明顯優(yōu)勢.綜上所述,FDE-Filtering≤FDEAGLE≤FDFAGLE.

3.1.3 通信開銷

通信開銷是指因構建反匿名網(wǎng)絡而產(chǎn)生的數(shù)據(jù)通信量,它能反映構建系統(tǒng)對網(wǎng)絡帶寬的影響.在基于E-Filtering 的反匿名網(wǎng)絡中,每個EStub 獨立過濾匿名流,因此通信開銷SCE-Filtering=0.然而,在基于對等過濾的反匿名網(wǎng)絡中,因為MStub 之間需要通過交換彼此前綴來實現(xiàn)對等過濾,所以FAGLE 或EAGLE 會因成員加入和退出而產(chǎn)生通信開銷(主要是AMM 模塊與MStub 和MTransit 的交互次數(shù)).鑒于成員更新不會頻繁發(fā)生,無論是FAGLE 還是EAGLE 構建系統(tǒng),其通信開銷都不會很大.即使這樣,若能進一步降低通信開銷,也會非常有意義.給定一個反匿名網(wǎng)絡ASN=(G,RA-stub),鑒于FAGLE 扁平化的體系結(jié)構,每次加入或退出產(chǎn)生的通信開銷都為|RA-stub|-1,因此,它的通信開銷SCFAGLE=n×(|RA-stub|-1),其中,n表示成員更新發(fā)生次數(shù).鑒于EAGLE 層次化的體系結(jié)構,每次成員加入或退出都有兩種情況發(fā)生.

(1)如果生成新的TMStub 或分裂已有的TMStub,那么AMM 不僅需要通知最高層成員,還有TMStub 的內(nèi)部成員.假設當前RA-stub的成員壓縮比為r∈[0,1],且相關TMStub 由m1個成員組成(包括Mstub,Mtransit 和sub-TMStub),前者的最大通信開銷都為(r×|RA-stub|-1),后者的最大通信開銷為m1.基于此,它的最大通信開銷為SCEAGLE=n×[(r×|RA-stub|-1)+m1].在聯(lián)盟構建初期,有時會生成規(guī)模較大的TMStub,特別是該TMStub 所含成員數(shù)量超過構建聯(lián)盟MStub 數(shù)量,即m1＞|RA-stub|,此時,SCEAGLE略大于SCFAGLE；

(2)如果沒有生成新的TMStub 或分裂已有的TMStub,那么僅需通知最高層,此時,SCE-Filtering＜＜SCEAGLE=n×[(r×|RA-stub|-1)]＜＜SCFAGLE.

證畢.

3.1.4 存儲開銷

存儲開銷是指因記錄聯(lián)盟成員信息而帶來的內(nèi)存開銷,它能反映構建系統(tǒng)的可擴展性.在基于E-Filtering的反匿名網(wǎng)絡中,成員之間互相獨立,無需記錄信息,因此SSE-Filtering=0.在基于對等過濾的反匿名網(wǎng)絡中,構建系統(tǒng)需要收集和管理成員信息,因此FAGLE 或EAGLE 都會產(chǎn)生存儲開銷.

· 前者的構建系統(tǒng)包括3 個模塊,分別為RCM,MSM 和AMM.其中,RCM 只記錄ACL 規(guī)則參數(shù),存儲開銷可忽略不計,SSF-R=0；MSM 需要記錄所有成員的前綴,每個前綴占5B,那么SSF-M=5|RA-stub|B；AMM 除了成員前綴,還記錄AS號與前綴的映射表,假設每個AS號占4B 且每個AS只有一個網(wǎng)絡前綴,那么SSF-A=(5|RA-stub|+9|RA-stub|)B；

· 后者的構建系統(tǒng)除了上述3 個模塊,還增加了MTM 模塊.只有RCM 的開銷沒有變化:SSE-R=0,其余模塊都有不同.

? 就MSM 來說,如果它位于聯(lián)盟最高層且成員壓縮比為r,那么SSE-MSM=(5r×|RA-stub|)B；反之,位于TMStub 內(nèi)部的MSM 只需記錄其上層提供商的前綴,因此SSE-MSM=5B；

? MTM 除了上述開銷,還需記錄下層客戶前綴.假設每個提供商的平均客戶數(shù)量為m,那么SSE-MTM=(5r×|RA-stub|+5m)B 或者SSE-MTM=(5+5m)B；

? AMM 需要建立面向全網(wǎng)的層次結(jié)構模型(如圖1 所示),模型中,樹節(jié)點的數(shù)據(jù)結(jié)構描述為{過濾狀態(tài)位,TMStub 狀態(tài)位,網(wǎng)絡前綴,AS號,孩子(客戶)指針},共占(11+4m)B.假設全網(wǎng)的自治域數(shù)量為z,那么SSE-A=z×(11+4m)B.通過統(tǒng)計可知z約為45k[31],進而可推出SSE-A是在可接受范圍內(nèi).

綜上所述,EAGLE 的MSM 和MTM 存儲開銷要小于FAGLE,而AMM 存儲開銷要大于FAGLE.不過,當所有AS都加入聯(lián)盟時,它們的AMM 開銷相差并不大.

3.1.5 規(guī)則優(yōu)化誤報

規(guī)則優(yōu)化誤報是指因運行過濾規(guī)則優(yōu)化算法而帶來的誤報,這會間接影響構建系統(tǒng)的部署激勵性.基于EFiltering 的反匿名網(wǎng)絡對匿名包進行無差別過濾,不存在過濾器短缺問題,不需要規(guī)則優(yōu)化,因此FPE-Filtering=0；基于對等過濾的反匿名網(wǎng)絡對匿名包進行選擇性過濾,過濾器需求量較大,需要規(guī)則優(yōu)化.在M-List和Fmax給定的條件下,影響規(guī)則優(yōu)化誤報的主要因素包括地址權重的準確度σ和優(yōu)化解的質(zhì)量.鑒于EAGLE 和FAGLE方法都能求得最優(yōu)解,誤報率的計算公式可簡化為FP=f(σ),σ越準確,FP越小；反之,則越大.根據(jù)定義12 可知,地址權重源于W-List,這也就是說,它的準確度σ取決于W-List是否客觀.已知EAGLE 中的W-List成員是真實自治域,而FAGLE 采用排他法來推測W-List成員,后者增加了隨意性,不難推出σEAGLE≥σFAGLE,因此FPEAGLE≤FPFAGLE.

3.1.6 規(guī)則優(yōu)化的時間復雜度

規(guī)則優(yōu)化的時間復雜度是指因運行規(guī)則優(yōu)化算法而產(chǎn)生的的時間開銷,這會間接影響構建系統(tǒng)的響應時間.基于E-Filtering 的反匿名網(wǎng)絡不存在過濾器缺乏問題,因此TFE-Filtering=0.給定M-List,W-List和Fmax,FAGLE的規(guī)則優(yōu)化算法主要包括建立樹(build tree,簡稱BT)、裁剪樹(prune tree,簡稱PT)和壓縮樹(compress tree,簡稱CT),其中,BT 需要進行(|M-List|+|W-List|)次節(jié)點插入操作,而每次插入最多執(zhí)行H次比較,H表示樹的高度,最大值為32,時間開銷為o(32×(|M-List|+|W-List|))；PT 需要對樹至少執(zhí)行5 次遍歷,已知樹節(jié)點數(shù)量最多為((|M-List|+|W-List|)×(|M-List|+|W-List|-1)/2),它的開銷為o(5×(|M-List|+|W-List|)×(|M-List|+|W-List|-1)/2)；CT 需要為每個樹節(jié)點計算過濾器分配方案,最大開銷為o(|M-List|×).基于此,=o(BT)+o(CT)+o(PT).需要注意的是:因為FAGLE 的規(guī)則優(yōu)化算法不支持增量更新,所以每當有成員加入或退出,必須重新運行一次算法,也就是說假設先后有s個成員需更新,那么時間開銷為TFFAGLE=s×.EAGLE 的規(guī)則優(yōu)化算法主要包括建立樹BT、前綴選擇(prefix selection,簡稱PS)和成員更新(member update,簡稱MU),其中:BT 需要進行(|M-List|+|W-List|)次節(jié)點插入操作,而每次插入最多執(zhí)行32 次比較,因此它的開銷為o(32×(|M-List|+|W-List|))；PS需計算每個最優(yōu)聚合前綴節(jié)點的過濾器分配方案,它的開銷為o(N×Fmax×(Fmax-1)),N表示樹中最優(yōu)聚合前綴節(jié)點數(shù)量,在最壞的情況下(即文獻[9]提高的非平衡樹,它的每個葉子節(jié)點幾乎都對應一個最優(yōu)聚合前綴),N=|M-List|-1；MU只需重新計算更新節(jié)點上游的過濾器分配方案,而且可重用已有分支的分配方案,因此它的開銷為o(H×Fmax×(Fmax-1)),最壞情況下,H=Fmax-1.基于此,假設先后有s個更新成員,EAGLE 的時間開銷為TFEAGLE=o(BT)+o(PS)+s×o(MU).通過比較不難發(fā)現(xiàn),TFE-Filtering＜TFEAGLE＜＜TFFAGLE,聯(lián)盟成員更新越頻繁,這種優(yōu)勢越明顯.

3.1.7 規(guī)則優(yōu)化的空間復雜度

規(guī)則優(yōu)化的空間復雜度是指因運行規(guī)則優(yōu)化算法而產(chǎn)生的內(nèi)存開銷,這會間接影響構建系統(tǒng)的可擴展性.基于E-Filtering 的反匿名網(wǎng)絡不存在過濾器缺乏問題,因此SFE-Filtering=0.FAGLE 的規(guī)則優(yōu)化算法會先后引入3種數(shù)據(jù)結(jié)構:ELCP 樹T、誤報率數(shù)組Z和過濾器分配數(shù)組R,其中:T的最大節(jié)點數(shù)量為(|M-List|+|W-List|)×(|M-List|+|W-List|-1)/2,內(nèi)存開銷約為o(1/2×(|M-List|+|W-List|)2)；Z和R的最大長度為H×|M-List|,H表示樹的最大高度,它們的內(nèi)存開銷為o(32×|M-List|).EAGLE 的規(guī)則優(yōu)化算法先后引入3 種結(jié)構:ELCP 樹T、誤報率數(shù)組Z和過濾器分配數(shù)組R,其中:T的最大節(jié)點數(shù)量為(|M-List|+|W-List|)×(|M-List|+|W-List|-1)/2,它的內(nèi)存開銷約為o(1/2×(|M-List|+|W-List|)2)；Z和R的最大長度為H×|M-List|,H表示樹的最大高度,內(nèi)存開銷為o(32×|M-List|).基于此,SFFAGLE=o(1/2×(|M-List|+|W-List|)2+64×|M-List|).與FAGLE 相似,EAGLE 的規(guī)則優(yōu)化算法也引入3 種結(jié)構,其中:BT 樹的最大節(jié)點數(shù)量為32×|M-List|,最優(yōu)解集Sec和誤報率集f的最大長度也為H×|M-List|,內(nèi)存開銷為o(32×|M-List|).基于此,SFEAGLE=o(96×|M-List|).通過比較不難發(fā)現(xiàn),SFE-Filtering＜＜SFEAGLE≤SFFAGLE.不過,FAGLE 中的T和Z都是中間數(shù)據(jù),一旦運行結(jié)束,就會釋放空間；而EAGLE 為了實現(xiàn)增量更新,上述結(jié)構都不會被中途釋放.簡言之,就是用空間換取時間.

3.2 仿真實驗

鑒于第3.1 節(jié)的理論分析都是基于層次結(jié)構的網(wǎng)絡拓撲,本節(jié)的仿真實驗將在結(jié)構特征更加多樣的真實網(wǎng)絡拓撲上運行,以便對上述分析結(jié)果進行補充.考慮到真實環(huán)境的復雜性和實現(xiàn)的困難性,出于簡化實驗的目的,與文獻[9]相同,本文也是通過搭建面向BGP 的網(wǎng)絡仿真平臺來模擬域間網(wǎng)絡的IP 包活動情況.平臺搭建過程分兩步.

(1)對美國UCLA 大學收集到的自治域級拓撲數(shù)據(jù)集進行清理以及二次開發(fā),獲取可支持C-BGP 的網(wǎng)絡拓撲[15]；

(2)以真實拓撲作為輸入?yún)?shù),通過搭建面向網(wǎng)絡模擬器C-BGP 的開發(fā)環(huán)境來構建自治域級網(wǎng)絡[16].

該仿真平臺運行在一臺PC 虛擬機上(Intel 4core 2.2GHz processor,16GB of RAM,Parallels Desktop 12,Ubuntu 16.04).除了仿真任務,還需要提取網(wǎng)絡特征、收集過濾器需求量以及優(yōu)化過濾規(guī)則,上述計算任務都在另一臺PC 機(Windows XP SP3,Intel 2core 2.40GHz processor,2.0GB of RAM,VS 2008)上運行.

與FAGLE 相比,EAGLE 的先進性在于提高了聯(lián)盟成員的部署激勵性,而這又取決于反匿名聯(lián)盟的層次化程度.基于此,本節(jié)實驗都將圍繞能夠反映聯(lián)盟層次化的網(wǎng)絡拓撲特征和影響部署激勵性的因素(包括過濾器需求量、規(guī)則優(yōu)化準確度)而展開.首先,從真實網(wǎng)絡中提取與層次化相關的網(wǎng)絡拓撲特征；然后,比較過濾器需求量的分布情況；最后,比較因規(guī)則優(yōu)化而產(chǎn)生誤報率的分布情況.

此外,E-Filtering 部署激勵性差是因非部署收益,而與網(wǎng)絡拓撲無關,因此它不必參與實驗比較.

3.2.1 網(wǎng)絡結(jié)構特征

根據(jù)第2.1 節(jié)的描述可知,反匿名聯(lián)盟的層次化程度源于網(wǎng)絡結(jié)構的層次化,而后者又取決于以下拓撲因素:AS之間是否存在大量C2P 關系；AS的前綴數(shù)量；上下層AS前綴之間的包含情況；AS的路由備份情況；上下層AS的累積高度.基于此,本節(jié)將運行以下5 組實驗來反映真實網(wǎng)絡的層次化程度.

(1)第1 組實驗分別統(tǒng)計真實網(wǎng)絡中Stub 域、Transit 域、C2P、P2P 占AS總量或AS商業(yè)關系的比重,結(jié)果見表1.在真實網(wǎng)絡中,一方面C2P 關系所占比例明顯要高于P2P 關系,這為聯(lián)盟層次化奠定了基礎；另一方面,Stub 域所占比例要遠高于Transit 域,這又為大規(guī)模邏輯域的建立提供了可能；

Table 1 Basic parameters of topological structure (%)表1 拓撲基本參數(shù) (%)

(2)第2 組實驗用來計算真實網(wǎng)絡中擁有不同前綴數(shù)量的AS占總數(shù)量的比例,進而統(tǒng)計它的補充累積分布函數(shù),結(jié)果如圖6 所示.雖然網(wǎng)絡中存在少量前綴數(shù)量較大的AS,但是絕大部分AS的前綴數(shù)量都只有1 或2 個,這與第3.1 節(jié)的假設基本相同；

(3)第3 組實驗用來計算上下層前綴存在不同包含關系的C2P 數(shù)量占總數(shù)量的比例,進而統(tǒng)計它的補充累積分布函數(shù),結(jié)果如圖7 所示.在真實網(wǎng)絡中,上下層前綴之間存在包含關系的C2P 數(shù)量只占了10%左右,其中只有不足一半C2P 的前綴包含比例超過50%,這與第3.1 節(jié)的假設(供應商前綴包含客戶前綴)略不相同.原因可能是:雖然設備商已提供CIDR 技術,但是由于AS管理協(xié)商困難或歷史等原因,該技術并沒有被廣泛推廣.但即使這樣,依據(jù)EAGLE 的松耦合性,相比于FAGLE,它依然會帶來少量收益.更何況在某些屬權較為統(tǒng)一且CIDR 技術使用率較高的專用網(wǎng)絡(例如教育網(wǎng))上,C2P 關系的前綴包含比例必然會大幅度提升.這也就意味著,本文方法更適合教育網(wǎng)等專屬網(wǎng)絡；

Fig.6 Number of prefixes on different AS圖6 不同自治域的前綴數(shù)量變化情況

Fig.7 Prefix coverage ratio in different C2P圖7 不同C2P 關系的前綴包含比情況

(4)第4 組實驗通過統(tǒng)計擁有多個提供商的客戶數(shù)量占總數(shù)量的比例以及相關補充累積分布函數(shù)來說明單宿主或多宿主連接概率,結(jié)果如圖8 所示.無論客戶是Stub 域或Transit 域,單宿主連接概率都會接近50%及以上,這也就證明第3.1 節(jié)的假設基本合理.至于剩余的那些采用多宿主連接的客戶,無論它們是因為網(wǎng)絡前綴太多或路由備份,都可以在不影響EAGLE 性能的前提下,通過邏輯劃分單宿主的方式來滿足第3.1 節(jié)的假設條件.

(5)第5 組實驗通過統(tǒng)計邏輯域中Stub 域數(shù)量占總數(shù)量的比例來說明不同高度邏輯域的生成概率,結(jié)果如圖9 所示.在真實網(wǎng)絡中,一方面,高度大于6 的邏輯域所占Stub 域的比例不到5%,而且大多是因為少量非常規(guī)的首尾相接的C2P 關系而造成的；另一方面,接近95%的Stub 域位于高度不足5 的邏輯域中,其中,3 層邏輯域就占了一半以上.基于此,本文在第3.2.2 節(jié)選擇3 層邏輯域作為實驗拓撲.

Fig.8 Number of providers on different multi-homed ASs圖8 不同多宿主Stub AS 的提供商數(shù)量變化情況

Fig.9 Number of stub ASs on different levels圖9 不同層次中Stub AS 數(shù)量變化情況

3.2.2 部署激勵性

根據(jù)第3.1 節(jié)可知,過濾器需求量和規(guī)則優(yōu)化誤報會間接影響反匿名聯(lián)盟構建方法的部署激勵性.為此,本實驗主要關注在相同規(guī)模的反匿名聯(lián)盟條件下EAGLE 和FAGLE 方法中過濾器需求量和規(guī)則優(yōu)化誤報的變化情況.為了簡化實驗步驟、突出比較結(jié)果,依據(jù)第3.2.1 節(jié)已推測出的網(wǎng)絡結(jié)構特征,本實驗選則所有3 層邏輯域作為實驗拓撲,而且將所有多宿主AS簡化為單宿主AS.基于此,本節(jié)運行的兩組實驗如下.

(1)第1 組實驗通過搜集不同聯(lián)盟成員的過濾器需求量來統(tǒng)計它的補充累積分布函數(shù),結(jié)果如圖10 所示.鑒于EAGLE 方法的最高層成員過濾器需求量FDInter與TMStub 內(nèi)部成員過濾器需求量FDIntra不同,需要分層搜集；而FAGLE 只包含一種過濾場景,無需分層.首先,在EAGLE 中,聯(lián)盟成員的過濾器需求量從底層到高層逐層增加,且增幅較大.主要原因是為了完成對等過濾,除了本層前綴,上層的過濾規(guī)則還必須包含下層前綴.然后,從總體上看,與FAGLE 相比,EAGLE 的過濾器需求量要降低很多；而且隨著層數(shù)增多,優(yōu)勢會更明顯.然而,實驗結(jié)果與第3.1.2 節(jié)理論分析結(jié)果略有不同,原因在于真實網(wǎng)絡中上層前綴并不能完全覆蓋下層前綴,進而無法簡化過濾規(guī)則.最后,EAGLE 中最高層的過濾器需求量與FALGE 的幾乎相同,因為它們的過濾原理完全相同；

Fig.10 Number of required filters on different members圖10 不同聯(lián)盟成員的過濾器需求量變化情況

(2)根據(jù)第3.1.5 節(jié)可知:鑒于規(guī)則優(yōu)化誤報取決于地址權重準確度,第2 組實驗通過搜集所有BT 樹節(jié)點權重的絕對誤差來統(tǒng)計它的補充累積分布函數(shù),結(jié)果如圖11 所示.已知EAGLE 地址權重的計算方法是客觀的,而FAGLE 帶有不確定性,為了評估后者與前者的差距,本文提出了地址權重絕對誤差.為了突顯實驗的客觀性,一方面假設所有StubAS全部成為聯(lián)盟成員,因此；另一方面,假設所有TransitAS都不是聯(lián)盟成員,因為權重計算方法與聯(lián)盟層次化無關.首先,從總體上看,EAGLE 與FAGLE 的地址權重之間確實存在絕對誤差,根附近節(jié)點的權重誤差甚至達到0.5 以上；然后,雖然絕大部分位于葉子和底部節(jié)點的地址權重誤差都非常小,接近于0,但是仍存在少量誤差較大的節(jié)點,這些節(jié)點最終會影響規(guī)則優(yōu)化算法；最后,部分節(jié)點的地址權重誤差可達到0,主要原因是下層自治域前綴之間不存在間隙,這意味著只有規(guī)劃非常合理,FAGLE 與EAGLE 的規(guī)則優(yōu)化誤報才可消除.

Fig.11 Rate of false positive on different tree nodes圖11 不同樹節(jié)點的過濾誤報率變化情況

4 相關工作介紹

按照動作發(fā)生的先后順序,反匿名技術可分為源地址驗證和IP 溯源兩大類:前者實現(xiàn)事前預防,后者實現(xiàn)事后追責[17,18].二者在功能上互為補充,缺一不可,本文主則要關注前者.學術界已經(jīng)提出大量的源地址驗證方法,經(jīng)典的有DPF[1],IDPF[2],SAVE[3],SPM[4],Hidasav[5]和Passport[6]等.DPF 方法利用核心網(wǎng)絡大都依據(jù)最短路由轉(zhuǎn)發(fā)IP 包的特點,將凡是不應出現(xiàn)在當前路由上的IP 包當作匿名包,并過濾.然而為實現(xiàn)該功能,部分邊界路由器必須掌握全網(wǎng)路由,這并不現(xiàn)實.為此,Hai 等人提出了IDPF 方法,通過配置BGP 路由策略,將原方法的強假設——最短路由弱化為可行性路由,增強了可部署性.然而,這又造成較高的過濾漏報率.SAVE 方法提出了一種新的通信協(xié)議,通過在網(wǎng)絡路由節(jié)點上建立源地址和入接口的映射關系,徹底實現(xiàn)了基于路由的匿名包過濾.不過,該協(xié)議沒有考慮路由系統(tǒng)的層次結(jié)構,源地址或路由變化引發(fā)的消息更新范圍達到整個網(wǎng)絡,這既會產(chǎn)生較大通信開銷,又會影響過濾的準確性.SPM 是一種基于加密認證的源地址驗證方案,每對通信自治域都需共享一個密鑰,其中源自治域負責寫入,而目的自治域負責檢查.然而,該方法過于扁平化和單一化的體系結(jié)構會造成較大的存儲和通信開銷.為此,吳建平等人提出一種層次化的域間真實源地址驗證方法,簡稱Hidasav,通過合理規(guī)劃聯(lián)盟層次和聚類整合,即使部署在大規(guī)模網(wǎng)絡上,仍能保證驗證的簡單、輕權、有效.Passport 是一種基于對等密鑰MAC 的端到端匿名包過濾方法,通過計算上游AS號對應的MAC 值并將它標記到轉(zhuǎn)發(fā)包中,使得下游Transit 域能夠?qū)υ摪M行驗證和過濾.通過分析上述方法不難發(fā)現(xiàn):它們都是對現(xiàn)有通信協(xié)議進行革新,進而要求徹底升級當前路由器.然而,本文關注的出邊界過濾方法E-Filtering 既不需要升級路由器,又不需執(zhí)行額外操作,因此擁有更小的部署和計算開銷.

盡管E-Filtering 具備上述優(yōu)點并已在路由器廣泛實現(xiàn),但是它的部署率依然較低,其中一個重要原因就是它缺乏部署激勵性.為此,劉冰洋等人近年來提出一種基于對等過濾的反匿名聯(lián)盟構建方法,與已有方案相比,它在可行性和效率方面具有明顯優(yōu)勢[9].而本文就是在此工作的基礎上做了以下努力:通過改善它的過濾器開銷、通信開銷、計算開銷和過濾規(guī)則優(yōu)化精度,進一步提高方法的可擴展性,適應可增量部署.

5 結(jié)論與未來工作展望

出邊界過濾是當前網(wǎng)絡流行的一種基于過濾器的反匿名技術,但是因為搭便車問題,缺乏部署激勵性,致使它一直無法大范圍推廣.基于對等過濾的域間源地址驗證方法就是針對上述問題而提出的,該方法借鑒社會學的互動關系理論,通過建立反匿名聯(lián)盟,使得未部署運營商從受益者列表中嚴格剝離.然而,過于扁平化、單一化的聯(lián)盟體系結(jié)構以及過于隨機的非成員判定方式和低效的成員數(shù)據(jù)處理方式,使得它在面對大規(guī)模網(wǎng)絡時存在可擴展性問題.為此,本文提出一種層次化的反匿名聯(lián)盟構建方法,通過減小過濾器、通信、計算開銷以及提高過濾規(guī)則優(yōu)化精度來增強可擴展性,實現(xiàn)增量部署.與已有方法相比,本文方法具備以下特征:1)構建了新型的層次化的反匿名聯(lián)盟體系結(jié)構,避免成員之間建立不必要的全連接雙向過濾關系,降低過濾器需求量；2)引入Transit 域?qū)Φ冗^濾模塊作為聯(lián)盟邊界,將每一層級聯(lián)盟和外界成員隔離,減少因成員更新而帶來的通信開銷；3)設計高精度、可增量更新的過濾規(guī)則優(yōu)化算法,在加快求解速度的同時提高解的質(zhì)量.

未來的研究工作主要包括:

1)與公用網(wǎng)絡(例如互聯(lián)網(wǎng))相比,本文的工作更適合于專用網(wǎng)絡(例如中國教育網(wǎng)),主要原因如下:一方面,公用網(wǎng)絡作為一個松散的商業(yè)聯(lián)盟,很難集中管理所有自治域,更別說讓它們服從于一個全局管理服務器AMM；另一方面,由于歷史遺留或部署激勵不足,公用網(wǎng)絡的上下層自治域網(wǎng)絡前綴并非完全具備層次結(jié)構,雖然本文方法在非層次網(wǎng)絡模型下也能正常工作,但是其優(yōu)勢會有所下降.基于此,我們希望在今后,以當前本文研究為基礎放寬前綴層次化的假設條件,盡可能設計一種去中心化的體系結(jié)構.其目標是在不久的將來為互聯(lián)網(wǎng)環(huán)境中的部署和商業(yè)應用提供參考和借鑒,以便為網(wǎng)絡用戶提供可靠的反匿名機制；

2)雖然本文通過解決搭便車問題增強了傳統(tǒng)E-Filtering 的部署激勵性,但是在反匿名聯(lián)盟構建初期,因為聯(lián)盟成員較少,根據(jù)定義4 可知,新部署者只能獲得較少的收益,這會再次影響構建方法的部署激勵性.因此,如何利用早期少量成員所帶來的市場壓力刺激更多的新成員加入[19],使聯(lián)盟構建方法從始至終都能保持較高的部署激勵性是非常必要的.