方 堃武小年,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

改進的一致性哈希算法及應用

方 堃1武小年1,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

針對分布式入侵檢測中的數(shù)據(jù)分割問題，給出一種改進的一致性哈希算法。該算法針對采集的數(shù)據(jù)包，通過TCP流重組建立TCP數(shù)據(jù)鏈，保證數(shù)據(jù)流的完整性；再通過結點的分組對一致性哈希算法進行改進，并實現(xiàn)組間和組內的數(shù)據(jù)分配，減少虛擬結點數(shù)量；對結點的負載均衡檢測和調整策略，改善了系統(tǒng)的負載均衡性。仿真測試結果表明該算法具有較好的負載均衡性。

分布式入侵檢測；TCP流重組；一致性哈希算法；負載均衡

1 引言

隨著網(wǎng)絡帶寬的不斷增大，網(wǎng)絡速度的不斷提高，傳統(tǒng)的基于單主機的入侵檢測系統(tǒng)已經(jīng)很難滿足大規(guī)模網(wǎng)絡高效檢測的需求。分布式入侵檢測系統(tǒng)是解決高速網(wǎng)絡環(huán)境下入侵檢測效率低下問題的解決方案之一?，F(xiàn)今，提升分布式入侵檢測系統(tǒng)的性能面對許多難題。首先，數(shù)據(jù)的完整性對入侵檢測系統(tǒng)檢測準確率的提升至關重要，因此如何保持數(shù)據(jù)的完整性是對分布式系統(tǒng)中數(shù)據(jù)分割算法提出的重大挑戰(zhàn)；其次，分布式系統(tǒng)中可能會產(chǎn)生添加或刪除結點的情況，此時若采用傳統(tǒng)求模運算的哈希函數(shù)，則必須重新分配數(shù)據(jù)，然而在入侵檢測中有時需要與歷史信息結合來準確判斷出攻擊行為，此時將產(chǎn)生大量的數(shù)據(jù)遷移，降低整個系統(tǒng)性能；最后，均衡的保持每個結點的負載，使各個結點發(fā)揮出最大性能，也是提升分布式入侵檢測系統(tǒng)的關鍵。因此，實現(xiàn)分布式入侵檢測的關鍵在于數(shù)據(jù)分割算法。

一個良好的面向分布式入侵檢測的數(shù)據(jù)分割算法應當滿足以下三個特征：（1）有效性，即每個數(shù)據(jù)分片應能準確檢測出攻擊行為；（2）均衡性，即每一個分片應使各分布式結點負載均衡；（3）簡單性，即分割算法簡單、高效。文獻[1]提出動態(tài)最小負載優(yōu)先算法，將數(shù)據(jù)優(yōu)先分配給負載最輕的結點。文獻[2]中加入了數(shù)據(jù)預過濾和緩沖聚類，將檢測結點的一部分功能轉移到分割模塊中，降低了后續(xù)模塊的處理壓力。文獻[3]提出的隨意分割集中學習的方法，此種算法滿足了分割算法的簡單性和負載均衡性，但后續(xù)的檢測較為復雜，不利于實時網(wǎng)絡入侵檢測的實施。文獻[4]綜合考慮了影響各結點負載均衡性的因素，優(yōu)先將數(shù)據(jù)分配給負載最輕的結點，實現(xiàn)了負載均衡性，然而并沒有考慮到數(shù)據(jù)包之間的聯(lián)系，破壞了數(shù)據(jù)的完整性。文獻[5]提出基于流粒度的負載均衡算法，以會話流為單位分發(fā)數(shù)據(jù)包，保持數(shù)據(jù)的完整性。

本文基于一致性哈希算法，給出一種改進的算法，并用于分布式入侵檢測的數(shù)據(jù)分割，該算法針對采集的數(shù)據(jù)包，通過維護TCP連接記錄并重組TCP數(shù)據(jù)鏈，保持數(shù)據(jù)流的完整性；再通過改進的一致性哈希算法，減小結點間數(shù)據(jù)的遷移量，同時通過負載均衡策略維持結點間的負載均衡。

2 改進的一致性哈希數(shù)據(jù)分割方法

在分布式入侵檢測中，數(shù)據(jù)分割的優(yōu)劣一直是制約分布式入侵檢測系統(tǒng)性能的瓶頸。首先，若以單一數(shù)據(jù)包為最小檢測單元，不關心數(shù)據(jù)包的狀態(tài)信息，將相互關聯(lián)的數(shù)據(jù)包分配到結點，會導致許多攻擊行為無法檢測出；其次，為了準確檢測出攻擊行為，有時還需獲取歷史告警記錄。若采用傳統(tǒng)哈希函數(shù)，當分布式系統(tǒng)中有結點的添加和刪除時，將導致整個哈希函數(shù)重新分布，為了保證歷史記錄的準確性，需要遷移大量的歷史告警信息，為系統(tǒng)增加負擔；最后，若分割算法不能實現(xiàn)負載均衡，則無法充分發(fā)揮各結點的計算性能，導致系統(tǒng)整體陷入瓶頸。

針對以上問題，本文首先采用TCP流重組技術，以會話流為最小單元保持數(shù)據(jù)的完整性。TCP協(xié)議在網(wǎng)絡中進行傳輸?shù)臅r候，由于經(jīng)過不同的路由，在到達的時間與順序上會產(chǎn)生混亂，因此要提取出數(shù)據(jù)流中的TCP包進行重組才能還原成一個完整的數(shù)據(jù)鏈。為保證將海量的網(wǎng)絡數(shù)據(jù)分割成一個個完整的數(shù)據(jù)子集，在數(shù)據(jù)重組時，計算數(shù)據(jù)包的哈希值。一條TCP連接可以由四元組<源IP地址，源端口，目的IP地址，目的端口>唯一確定，因此，可以通過哈希函數(shù)計算四元組的哈希值，作為此連接的唯一標識，結合報文中的連接序號就可以實現(xiàn)正確的 TCP流重組。針對重組形成的一個個TCP流鏈，進一步采用改進的一致性哈希算法，將不同的TCP流鏈分配到不同的結點，實現(xiàn)數(shù)據(jù)的分割。

2.1改進的一致性哈希算法

一致性哈希算法是實際結點對應的虛擬結點映射到0～232的環(huán)上，數(shù)據(jù)求取哈希值后同樣映射到該環(huán)上，并按順時針方向查找與之最接近的虛擬結點，通過虛擬結點與實際結點之間的映射關系將數(shù)據(jù)分布到真實結點。當有新結點加入或舊結點退出時，僅影響順時針方向的下一個結點的數(shù)據(jù)，減少數(shù)據(jù)的遷移量。

然而傳統(tǒng)一致性哈希算法主要針對同構主機，當兩個結點的性能相差過大時，需要引入大量的虛擬結點，從而導致虛擬結點需要的存儲空間增加和查找速度的降低。假設結點i的計算能力為 ai，由文獻[6]得知，每臺主機引入的虛擬設備為klog|N|，其中k為常數(shù)，N為設備總數(shù)。若結點i的計算能力為ai，計算能力最低結點的計算能力為amin，則傳統(tǒng)一致性哈希函數(shù)所需要分配的虛擬結點個數(shù)為:

當ai/amin的值很大時，將引入大量的虛擬結點，降低整個一致性哈希函數(shù)性能。

本文改進算法中，將計算能力相差不大的結點分為一組，組間按照各組結點計算能力的大小比例分割整個哈希值的值域，數(shù)據(jù)先分配到不同的組中，在組內采用一致性哈希算法，再將數(shù)據(jù)分配到不同的結點上。由于組內結點計算能力相差不大，因此可以采用均勻分配的方式。采用此方法可以解決異構主機引入虛擬結點過多的問題。假設結點共分為 p組，組i中有ni個結點，由于結點計算能力相差不大，則每組中引入的虛擬結點總數(shù)為niklog|N|，整個分割系統(tǒng)引入總結點數(shù)為：

當結點計算能力相差很大時，式（1）的值遠遠大于式（2）的值。

2.2負載均衡策略

在傳統(tǒng)一致性哈希算法中，數(shù)據(jù)的分配是由概率決定的，因此在容易產(chǎn)生負載不均衡。針對該問題，本文基于上述的改進一致性哈希算法，進一步進行負載均衡調整。系統(tǒng)周期性進行結點負載情況檢查，并根據(jù)不同組結點數(shù)據(jù)處理能力不同，設定不同的負載均衡調整門限，當負載不均衡程度超過門限時，進行結點的負載均衡調整。

假設組i的權重為ci，表示結點的計算能力，計算能力越強的組ci的值越大，計算能力最低的一組權重為cmin，其中p為結點組的個數(shù)。組i負載均衡調整門限為Thresholdi,計算能力最低一組的負載均衡調整門限為Thresholdmin則有：

設組內負載最輕結點負載為 Lmin，負載最重結點負載為Lmax，負載居中結點為 Lmid，若類 i中Lmax-Lmid>Thresholdi，則進行負載過重調整，減少 Lmax對應結點的虛擬結點，同時將分配到該結點的數(shù)據(jù)產(chǎn)生的 T時間內的告警信息遷移到順時針方向的下一個結點，并清空該虛擬結點的告警信息。同理，若組i中Lmid-Lmin>Thresholdi，進行負載過輕調整，增加Lmin對應的虛擬結點個數(shù)，同時將下一結點中的T時間內部分告警信息遷移到新的結點中，并清空舊節(jié)中遷移部分的告警信息。

負載均衡調整將有效提升一致性哈希算法負載均衡性。使調整后的結點負載接近負載中間結點。同時，檢測攻擊行為并不需要太長時間的歷史記錄，因此結點告警信息的遷移量很小，并不會給系統(tǒng)增添過重的負擔。

3 實驗仿真

3.1實驗環(huán)境

本文采用C語言實現(xiàn)了網(wǎng)絡數(shù)據(jù)抓包、TCP流重組，以及分組一致性哈希算法和負載均衡調整算法，并對該算法進行了測試。仿真測試主要測試算法改進后的負載均衡情況。仿真測試網(wǎng)絡環(huán)境為實驗室局域網(wǎng)通過 100M 交換機連接到校園網(wǎng)，并連接互聯(lián)網(wǎng)。模擬設置了15個結點，分為3組，每組 5個結點；各組中結點計算能力分別分布在1000,3000,6000附近區(qū)間；設置計算能力最低的一組的虛擬結點數(shù)為20。

3.2實驗結果與分析

3.2.1組間負載均衡實驗

由于各組分配的數(shù)據(jù)量與各組計算能力成正比，若各組負載均衡則該組中處理數(shù)據(jù)的總量比該組計算能力的值應大致相同。這個值定義為組間相對數(shù)據(jù)量。各組組間相對數(shù)據(jù)量差值越小，說明組間負載均衡性越好。均方誤差能較好的反應數(shù)據(jù)之間的離散程度，均方誤差越小說明數(shù)據(jù)之間的離散程度越低。因此本文采用組間相對數(shù)據(jù)量的均方誤差作為評價組間負載均衡的評價指標，并將本文改進算法與傳統(tǒng)一致性哈希函數(shù)進行對比測試。實驗結果如圖1所示。

圖1　組間相對數(shù)據(jù)量均方誤差對比圖

由圖 1可以看出，本文改進算法中各組組間數(shù)據(jù)量均方誤差遠小于傳統(tǒng)一致性哈希算法，其原因在于本文算法將數(shù)據(jù)按照相對權重值的比例均勻分布到各組結點，組間負載性能良好，充分發(fā)揮結點的計算能力。

3.2.2組內負載均衡實驗

本實驗將本文算法與傳統(tǒng)哈希分割算法、傳統(tǒng)一致性哈希算法進行對比測試。對比的兩種算法將計算能力相同的結點視為一組，同時取第二組結點在不同的數(shù)據(jù)量下進行負載均衡性測試。實驗引入文獻[7]中提出的負載均衡度作為評價指標。負載均衡度越小，說明負載均衡性能越好。實驗結果如圖2所示。

圖2　負載均衡度對比圖

由上圖可以觀察到，由于傳統(tǒng)算法沒有加入動態(tài)調整策略，當局部流量增大時，將導致嚴重的負載不均衡現(xiàn)象，此種情況需要經(jīng)過較長時間的調整，才能略有改善。本文算法進行負載均衡調整后，負載均衡性能良好，且波動范圍很小，基本實現(xiàn)組內各結點負載均衡。

4 結束語

近年來網(wǎng)絡安全形勢日趨嚴峻，分布式入侵檢測技術成為維護網(wǎng)絡安全的有效手段，分割算法又是影響分布式入侵檢測系統(tǒng)性能的關鍵因素。本文給出改進的一致性哈希算法，并應用于分布式入侵檢測中進行數(shù)據(jù)分割。算法基于對采集數(shù)據(jù)的TCP流重組，并采用分組方法進行結點分組并實現(xiàn)組間和組內的數(shù)據(jù)分配，減少虛擬結點數(shù)量，并通過對結點的負載均衡檢測和調整，改善了系統(tǒng)的負載均衡性。

[1] 李信滿,趙大哲,趙宏,等.基于應用的高速網(wǎng)絡入侵檢測系統(tǒng)研究[J].通信學報,2002,23(9):1-7.

[2] Xinidis K,Charitakis I,Antonatos S, et al. An active splitter architecture for intrusion detection and prevention[J]. Dependable and Secure Computing, IEEE Transactions on,2006, 3(1): 31-44.

[3] 劉衍珩,田大新,余雪崗,等.基于分布式學習的大規(guī)模網(wǎng)絡入侵檢測算法[J].軟件學報,2008,19(4): 993-1003.

[4] Jiang W, Song H, Dai Y. Real-time intrusion detection for high-speed networks[J].Computers & security,2005,24(4): 287-294.

[5] 高明.高速網(wǎng)絡入侵檢測負載均衡機制研究[D].武漢:華中科技大學,2009.

[6] Karger D,Lehman E, Leighton T, et al. Consistent hashing and random trees:Distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM,1997: 654-663.

[7] 陳一驕,盧錫城,時向泉,等.一種面向會話的自適應負載均衡算法[J].軟件學報,2008,19(7):1828-1836.

Improved consistent hash algorithm and application

Aiming at data segmentation problem in distributed intrusion detection, this paper proposes an improved consistent hash algorithm to solve this problem. The algorithm uses TCP stream reassembly technology to rebuild TCP links to ensure data integrity; then divided nodes into different group to improve the consistent hash algorithm. Through the improved consistent hash algorithm, the data can be divided in node and the number of required virtual node is reduced; Load balancing detection of node and adjustment strategy to improve the load balance of the system. The simulation results show that the algorithm has better load balance.

Distributed Intrusion Detection;TCP stream reassembly;Consistent hash;Load balancing

TP393

A

1008-1151(2015)04-0005-03

2015-02-10

廣西自然科學基金(2012GXNSFAA053224)和廣西無線寬帶通信與信號處理重點實驗室2014年開放基金項目(GXKL0614110)資助。

方堃（1990-）男，湖北武漢人，桂林電子科技大學信息與通信學院碩士研究生，研究方向為信息安全。

武小年（1972-），男，湖北監(jiān)利人，桂林電子科技大學副教授，研究方向為信息安全，分布式計算。