蟻群優化在Ｐ２Ｐ網絡防范ＤＤｏＳ攻擊中的應用研究
2009-01-01 00:00:00李俊青潘全科王文宏左鳳朝李元振謝圣獻
計算機應用研究 2009年1期
(1.聊城大學 計算機學院， 山東 聊城 252059；2.北京郵電大學 計算機科學與技術學院， 北京 100876)
摘 要：分析了非結構化P2P網絡DDoS攻擊的原理，借鑒蟻群算法的思想，為每個節點建立了一個資源相似度信息素表，利用這個信息素表，構建了一種防御DDoS攻擊的聯盟模型——AntDA (ant colony based defenseassociation)，并討論了應用AntDA模型進行防御的整個過程。在查詢周期模型平臺上實現了該模型，通過實驗分析，驗證了AntDA模型的有效性。
關鍵詞：蟻群算法；分布式拒絕服務攻擊；防御聯盟；對等網絡
中圖分類號：TP39308 文獻標志碼：A
文章編號：10013695(2009)01033903
Research on ant colony optimization in defending DDoS attacks of P2P network
LI Junqing1，PAN Quanke1，WANG Wenhong1，ZUO Fengchao1，LI Yuanzhen1，2，XIE Shengxian1
(1.School of Computer Science Technology， Liaocheng University， Liaocheng Shandong252059， China；2.School of Computer Science Technology， Beijing University of Posts Telecommunications， Beijing 100876， China)
Abstract:This paper discussed the DDoS attack process in P2P network.With introduction of ant colony idea，created a pheromone table for every peer in P2P network named resourcesimilarity pheromone table. Based on this pheromone table，created a new defending DDoS attacks model named AntDA，discussed three polices used in AntDA model.The new AntDA model is simulated on the QueryCycleSimulator platform， and its performance is excellent.
Key words:ant colony algorithm; distributed denial of service（DDoS）; defense collective; peertopeer
近年來，DDoS攻擊已經成為網絡攻擊中非常重要的一種形式。近來，聯眾公司就因DDoS攻擊而遭受了不小的損失。廣義上講，凡是妨礙服務器提供正常服務的攻擊方式均屬于DoS(拒絕服務)攻擊中的一種。DDoS是DoS攻擊發展中的一種新的形式，與DoS攻擊的主要區別是增加了攻擊者的數量，攻擊的力度更大。從攻擊技術角度，DDoS攻擊主要分成兩種，即直接攻擊和反射式攻擊。
在非結構化P2P網絡中，泛洪式路由轉發的特點導致這種網絡更容易遭受DDoS攻擊。文獻[1，2]對P2P網絡下DDoS攻擊的手段和形式進行了詳細的分析，指出攻擊的目標主要有兩種：a)攻擊P2P系統內部的節點；b)攻擊P2P系統外部的服務器。攻擊的手段主要有：index poisoning、routing table poisoning、pollution attacks、sybil attacks。
本文結合P2P網絡自身的特點，充分挖掘網絡邊緣資源的力量，充分考慮聯盟成員的資源相似度信息，提出一種在受害者周圍建立一種防御聯盟來共同抵御DDoS攻擊的方案。
1 蟻群算法簡介
蟻群算法(ant colony optimization，ACO)是一種用來在圖中尋找優化路徑的技術，由D. Marco于1992年在他的博士論文中引入，已經大量應用于各種優化問題的求解中[3]。蟻群算法是一種群智能問題求解方式，適用于求解簡單個體構成的復雜系統難題。本文以TSP為例說明蟻群算法的主要框架：
設有n個城市，蟻群中共有m只螞蟻，dij(i， j=1，2，…，n)表示城市i與j之間的距離，τij(t)表示t時刻城市i與j之間殘留的信息量，螞蟻k根據各個路徑上的信息量選擇下一個節點，用pkij(t)表示螞蟻k由城市i轉移到城市j的概率，則
pkij(t)=ταij(t)ηβij(t)/
r∈allowedkτir(t)ηβir(t)，j∈allowedk
0，otherwise （1）
其中：allowedk表示螞蟻k下一步可以選擇的城市的集合。各路徑信息素的更新操作如下：
τij(t+1)=ρ×τij(t)+Δτij，Δτij=mk=1Δτkij（2）
其中：Δτkij表示螞蟻k在本次移動中在城市i與j之間留下的信息量。其計算過程如下：
Δτkij=Q/Lk，if antk move from i to j
0，otherwise（3）
其中：Lk為螞蟻k在本次移動中所走路徑的長度；Q為常數，表示路徑上信息量對螞蟻選擇該路徑所起作用的大小，α=0時，算法就是傳統的貪心算法；ηij是能見度因數；β為啟發信息在選擇路徑中的所用，β=0時，算法成為正反饋啟發式算法。
2 防御聯盟構建
非結構化P2P網絡具有完全分布式特點，P2P網絡與復雜適應性系統（complex adaptive systems，CAS）有許多相同點：系統中存在很多個體，CAS中稱為agent，P2P中稱為peer，這些個體的行為是簡單的；多個簡單的個體構成的系統是動態的、復雜的、非中央化的；它們都是自組織的。非結構化P2P網絡中，每個peer只能得到局部鄰居節點信息，無法獲得整個網絡節點的信息。
本文采用蟻群算法計算資源相似度。系統中每個peer對應一個蟻巢nest，每個蟻巢由文件管理FM、通信管理CM和蟻群調度AS三個功能模塊構成。每個蟻巢擁有一個信息素(pheromone)表：r表示資源相關度信息素表，它是一個m×n矩陣。其中：m代表當前蟻巢的鄰居數目；n代表資源種類數目。同時，對系統資源進行分類：C={C0，C1，C2，…，Cn}共n類資源。
21 信息素表的構建與維護
每個蟻巢保存的信息素表反映了與其他蟻巢之間的信息相關性，信息素表的更新與維護工作是由在網絡中移動的螞蟻來完成的，主要有如下操作：
a）信息素表的初始化。pk節點剛加入系統時，對其他節點的資源是不可知的，借鑒文獻[4]的數據，對r信息素表的初始化為
γi， j=0.09(1≤i≤n，1≤j≤n) （4）
b）信息素表的更新。pk節點在請求資源時，首先生成一個搜索螞蟻searchant，其具有的屬性包括資源類別C、最大生存時間Tmax。Searchant每到一個中間節點pm，pm的AS模塊計算本地資源Cm與C的符合度，若distance(Cm，Ck)＜δ，則pm生成一個Resant，Resant沿原路返回并修改中間節點的r信息素表：
rm，c=rm，c+Δr
Δr=wd×|CRes|/|Cmax|+(1-wd)×Tmax/2×Td；0≤wd≤1(5)
CRes={ci|dis tan ce(ci，ck)＜δ}
其中：CRes表示滿足請求條件的資源；|Cmax|表示一次請求可以得到的最大回應數目，|CRes|/|Cmax|的值決定本次請求的資源匹配程度；TD表示滿足請求資源的節點的距離，TD的值越大，相應路徑上遺留的信息素強度越小；wd是在資源匹配度和距離兩個變量之間進行決策的參數。
c）信息素的揮發。信息素強度會隨時間的推移而揮發：
rm，c=(1-ρ)rm，c；ρ∈[0，1]（6）
22 防御聯盟形成
成為防御聯盟成員的條件是：要求即將加入防御聯盟的節點必須與本地節點在存儲資源方面具備一定的相似度。pk節點尋找防御聯盟成員的過程如下：
a)for every peer pjin p′k s neighbor list;
rj=sk=0rj，ck Ck=(c0，c1，…，cs) is the content of pk
b)ifrj>λ then addpj into defensecollective
23 防范流程
在遭受DDoS攻擊的早期，受害節點v會出現瞬時網絡流量增加或內存資源不足的情況。出現這種情況后，節點v馬上依次采取以下三種策略：
a)標記數據報。通知信任聯盟的所有成員標記所有目的地是v的數據報。根據文獻[10]的分析，IP首部中16位標志符在目前的網絡應用中很少使用，每個聯盟成員在這16位空間中填寫自己的一些信息，如peer的ID號，做好標記的數據報用于攻擊后的分析。這個過程是一個遞歸過程，節點v的聯盟成員會通知其聯盟成員在發往節點v的數據報中做標記，這些標記會構成一個攻擊路徑，為追蹤攻擊源提供幫助。
b)限制流量。如果網絡流量或資源不足的狀況短期內不能得到改善，v會認為DDoS攻擊已經開始，v馬上通知信任聯盟節點采取第二步策略，即限制目的地是v的數據報。在第二步策略中，充分考慮節點v的固定客戶群的利益，如果全部關閉所有發往v節點的數據流，勢必損害了這些客戶的利益，本文采用白名單的形式，在節點v通知聯盟成員限制流量的消息中包含其固定客戶群的名單，源地址屬于這個集合的數據報就放行；否則，以一定的概率q放行，不斷重復策略b)，直至網絡流量明顯減小或者q=0。
c)追蹤數據報。在網絡攻擊進行時或攻擊結束后，節點v可以向所有聯盟成員發送追蹤攻擊源的消息，成員接收到該消息后，以逆序的方式從做標記的數據報中獲取到最接近攻擊源的節點。
3 實驗分析
本文基于查詢周期仿真器[5]實現了基于蟻群算法的AntDA模型。
31 仿真環境
1）節點模型 系統中的節點分為四大類，即高可信節點(pretrusted peers)、好節點(good peers)、搭便車節點(freerider)和惡意節點(malicious peers)。其中，惡意節點又劃分為四種子模型，如表1所示。系統中各種節點分配情況如下：高可信節點5個，鄰居節點數目5個；好節點100個，鄰居節點數目3個，惡意節點12個，每種子模型各3個，鄰居節點數目5個。節點分類及其行為如表2所示。
表1 惡意節點子模型
惡意子模型共享資源行為推薦信任行為
A100%上傳惡意文件為上傳惡意文件的節點增加信任值
B100%上傳惡意文件為已知的惡意節點增加信任值
CP概率上傳惡意文件，1-p概率上傳好文件為已知的屬于同一個“合伙群”的惡意節點增加信任值
D100%上傳好文件為B類的節點增加信任值
表2 節點行為
節點類在線時間/%請求行為/%評價信任DDoS/%響應請求
好節點[0，100]隨機分布[0，50]隨機分布合理評價0提供真實的文件
搭便車節點[0，100]隨機分布[0，50]隨機分布不作評價0不提供任何文件
A類惡意節點100100負面評價[50，100]提供不真實的文件
B類惡意節點100100負面評價[50，100]提供不真實的文件
C類惡意節點100100夸大同類節點[50，100]以一定的概率對好節點提供可信文件
D類惡意節點100100夸大同類節點[50，100]信譽度高時以較低概率提供可信文件，信譽度低時又以較高比例提供可信文件
在每個查詢周期內，每類節點以不同的概率選擇在線、離線、發出請求和響應請求四種狀態中的一種。
2）資源分布模型 文獻[4]表明：節點總是只對部分資源類表現出興趣。每個文件由內容目錄c和在c中的流行度r決定，c和r均服從Zipf分布。
3）系統參數 實驗中用到的各種參數及其含義如表3所示。
表3 實驗參數
參數含義取值參數含義取值
ρ揮發率0.07m鄰居節點數目5
Tmaxn最大生存周期資源類數目2020wd資源匹配度與距離兩個變量之間進行決策的參數0.5
32 實驗結果分析
系統運行過程中，如果出現DDoS攻擊，受害者在攻擊流量超過一定限度時，會向鄰居節點發出建立防御聯盟的請求。以下是實驗分析結果。
1)無防御下性能分析 筆者分析了無防御情況下系統所有節點平均性能與受害節點性能的對比情況，定義平均性能(avgPerformance)如下：
avgPerformance=有效下載流量/當前周期系統總流量
在沒有任何防御措施情況下，所有攻擊流量均由受害節點處理，運行一定周期后，性能如圖1所示。從圖中曲線可以看到，隨著DDoS攻擊流量的加大，受害節點的性能急劇下降，在第110周期時，性能已經接近0；而系統其他節點的性能也會有所下降，原因是受害節點無法為其他節點提供正常服務。可以看出，隨著系統的運行，受害節點與其他節點之間的性能差距越來越大，最終導致受害節點因性能不足而被邊緣化，使得攻擊者攻擊成功。
2)AntDA模型性能分析 加入防御聯盟后，如圖2所示。在DDoS流量增加的初始階段，如第200周期左右，受害節點的性能有一個明顯下降的過程，此時，受害節點還沒有及時形成防御聯盟。在形成防御聯盟后，由于攻擊流量還處于相對可以承受的程度，受害節點會應用策略a)，圖中可以看出，受害節點的性能逐漸得到回升。隨著DDoS攻擊流量繼續加大，在第212周期時，受害節點性能達到最低，應用策略b)后，受害節點性能迅速回升。
對于其他節點，在應用策略b)之前，平均性能有一個平緩下降的過程，原因是受害節點無法提供正常服務；在應用策略b)后，由于這些節點中的一部分作為受害節點的聯盟成員，需要參與DDoS攻擊數據包的截獲工作，因而，平均性能下降幅度加大。然而不久，平均性能下降趨于平緩，原因是隨著受害節點性能的回升，它可以為其他節點提供正常服務了。從圖2可以看到，隨著系統的運行，受害節點與其他節點在性能上的差距逐漸縮小，系統逐漸趨于平衡。
4 結束語
本文結合P2P網絡的特點，提出一種基于防御聯盟的DDoS攻擊防范模型，模型充分考慮P2P網絡小世界特性以及節點理性等拓撲特征，采用蟻群智能算法選擇聯盟成員，有效避免了全局拓撲信息的計算。實驗證明，該方案可以在系統性能不受太大影響的情況下有效防范DDoS攻擊。下一步的工作是在參數選擇上增加靈活性，使系統能應對各種攻擊現象，增強系統的魯棒性。
參考文獻：
［1］LIANG J，NAOUMOV N，ROSS K W.The index poisoning attack in P2P file sharing systems[C]//Proc of the 25th IEEE International Conference on Computer Communications.Barcelona:[s.n.]，2006:112.
［2］MA Xinxin，ZHAO Yang，QING Zhiguang.Improving resilience against DDoS attack in unstructured P2P networks[J].Journal of Electronic Science and Technology of China， 2007，5(1): 1822，28.
［3］MARCO D.Ant colony optimization and swarm intelligence[M].Brussels:Springer，2006:100109.
［4］ELKE M，ARNO P，GERTI K.Using taxonomies for contentbased routing with ants [J].Journal of Computer Networks，2007，51(16): 45144528.
［5］田慧蓉，鄒仕洪，王文東，等.激勵一致的自適應P2P拓撲構造[J].軟件學報，2006，17(4):845853.
［6］KAMVAR S D， SCHLOSSER M T，GARCIA M H.The eigentrust algorithm for reputation management in P2P networks[C]//Proc of the 12th International Conference on World Wide Web. New York: ACM Press， 2003:640651.
