Kad網(wǎng)絡(luò)節(jié)點資源探測分析

劉祥濤，龔才春，劉 悅，白 碩

(1. 中國科學(xué)院計算技術(shù)研究所,北京 100190; 2. 中國科學(xué)院研究生院,北京 100190; 3. 北京市計算中心,北京 100005)

1 引言

eMule網(wǎng)絡(luò)[1]是一種混合類型的文件共享對等網(wǎng)絡(luò)，它由兩部分：集中式網(wǎng)絡(luò)和純分布式網(wǎng)絡(luò)組成。其中純分布式網(wǎng)絡(luò)采用了Kademlia協(xié)議[2]，是eMule網(wǎng)絡(luò)的主要組成部分。一般來說，采用Kademlia協(xié)議的eMule網(wǎng)絡(luò)稱為Kad網(wǎng)絡(luò)。Ipoque 2008～2009年度的因特網(wǎng)流量報告表明：依地理位置的不同，eMule占P2P流量的2%～47%，占因特網(wǎng)流量1%～26%[3]，且呈上漲趨勢[4-5]。

Kad網(wǎng)絡(luò)為不健康內(nèi)容的傳播提供了方便，在Kad網(wǎng)絡(luò)中存在數(shù)百萬的共享資源，其中有相當(dāng)一部分不合適讓特定人群觀看，我們稱這些資源為敏感資源。所以對Kad網(wǎng)絡(luò)中的共享資源進行探測分析是相當(dāng)必要的，這樣不僅可以了解敏感資源的擴散程度，也可以為不健康內(nèi)容的過濾做好鋪墊工作。從而減少特定人群受不健康內(nèi)容侵蝕的影響，有助于社會精神文明建設(shè)。

Kad網(wǎng)絡(luò)的探測分析存在如下挑戰(zhàn)：

? 雖然對等網(wǎng)絡(luò)爬蟲研究已經(jīng)取得了較大進展[6，9-11]，但直到現(xiàn)在，也不存在一個可以探測“節(jié)點”即被指定了一定標(biāo)識的物理機器的共享資源的爬蟲；

? 節(jié)點資源名是多語言的，比如英語、中文、日語、韓語、法語、西班牙語等，給資源的敏感判別增加了難度；

? 節(jié)點資源名通常都較短，從而其特征往往不足以判定其是否為敏感資源。

針對上述挑戰(zhàn)：

? 在已有對等網(wǎng)絡(luò)爬蟲的工作基礎(chǔ)上，設(shè)計和實現(xiàn)可以采集節(jié)點資源的爬蟲；

? 本文只對中文、英語和其他易判資源進行敏感判別和統(tǒng)計分析，但是分析方法也適用于其他語言；

? 采用兩種增加文件名特征的方法。a)file-content-hash是通過哈希文件內(nèi)容獲得的128位標(biāo)識符。一個file-content-hash可能對應(yīng)多個文件名，本文稱為“FCH1N現(xiàn)象”。我們將對應(yīng)同一個file-content-hash的多個文件名集中起來加強文件名特征。b)通過在流行搜索引擎上輸入文件名中包含的關(guān)鍵詞，獲得更多信息以加強文件名特征。

本文后續(xù)章節(jié)安排如下，第2節(jié)介紹研究背景，第3節(jié)介紹相關(guān)工作，第4節(jié)對節(jié)點資源進行探測和統(tǒng)計分析。最后，我們在第5節(jié)對全文進行總結(jié)。

2 背景

節(jié)點資源名是多語言的且長度較短，導(dǎo)致對其進行敏感判別的難度，見表1。為提高敏感判別的準(zhǔn)確性，本文適當(dāng)簡化問題和進行特征擴展(詳見4.4.1節(jié))。

表1 文件名的復(fù)雜性

為降低問題的復(fù)雜性，本文只對英文或中文簡體可識別文件名進行敏感判別。同時將文件分為3個類別：敏感文件、正常文件、忽略文件，分別簡稱C1、C2和C3類文件。

定義1.敏感文件(C1類文件)：其內(nèi)容不合適讓特定人群瀏覽的文件。

比如：文件名為“風(fēng)騷的女子_俄羅斯.rar”的文件是敏感文件。又比如：“Water Melons cd1 .www.EMuleX.es.avi”單從文件名看不出是否敏感，但通過搜索引擎查找相關(guān)信息可以獲知是一個色情敏感電影。

定義2.正常文件(C2類文件)：其內(nèi)容合適讓特定人群瀏覽的文件。

比如：“漢初軍事史研究.pdf”是一個正常的電子書文件；“The Pointer Sisters - Automatic.mp3”是一個正常的音樂文件。

定義3. 忽略文件(C3類文件)：因為文件名及其相關(guān)信息不足或因為語言差異以至不能正確區(qū)分某文件是否敏感或正常的文件。

比如：“?????.bmp”、“0094.gif”和“(Reggaeton)Tito Y Hector - Gata Salvaje.mp3”都是忽略文件。

3 相關(guān)工作

對等網(wǎng)絡(luò)爬蟲探測工作開展較早，2002年，Saroiu等人率先使用主動測量方法對當(dāng)時最為流行的Gnutella和Napster進行了拓撲測量[6]。2005年，Stutzbach等人在前人的工作基礎(chǔ)上改進了主動測量方法并開發(fā)出了快速分布式Gnutella拓撲采集器：Cruiser，證明了因為節(jié)點震蕩(churn)和Crawler采集速度太慢可能導(dǎo)致錯誤的實驗結(jié)論[7]。因此，使得提高Crawler的采集速度成為提高拓撲測量準(zhǔn)確性的關(guān)鍵問題。2008年，王勇等人針對Gnutella網(wǎng)絡(luò)設(shè)計了基于正反饋的分布式Gnutella拓撲采集器：D-Crawler，提出了度量采集器準(zhǔn)確性、完整性的衡量指標(biāo)，分析了Gnutella網(wǎng)絡(luò)拓撲圖的度等級分布特征、度頻率分布特征以及小世界特性[10]。

Kademlia協(xié)議的實現(xiàn)有Kad網(wǎng)絡(luò)和Bittorrent的DHT網(wǎng)絡(luò)等。2006年Stutzbach等人針對Kad網(wǎng)絡(luò)提出了計算查詢性能的分析框架，并開發(fā)出了兩個軟件：kFetch和kLookup用于采集和計算Kad網(wǎng)絡(luò)的查詢性能[8]。2006年Stutzbach 等人對三個P2P網(wǎng)絡(luò)：Gnutella、Kad網(wǎng)絡(luò)和Bittorrent進行了測量分析，針對Kad網(wǎng)絡(luò)，他們用Cruiser采集了兩天的拓撲數(shù)據(jù)，然后對節(jié)點可用性進行了分析[9]。2007年Steiner等人設(shè)計了Kad網(wǎng)絡(luò)采集器：Blizzard并進行了為期179天的Kad網(wǎng)絡(luò)采集，獲得了節(jié)點的地理分布、會話時間、節(jié)點可用性和生命周期等測度的測量結(jié)果[11-13]。2007年Falkner等人在PlanetLab實驗條件下，對Bittorrent的一個客戶端Azureus的DHT網(wǎng)絡(luò)進行了測量[14]。

與節(jié)點資源分析相關(guān)的工作有對等網(wǎng)絡(luò)垃圾過濾(P2P Spam Filtering)等，2005年，J.Liang等提出了一種垃圾過濾方法：首先下載共享音樂文件，若該文件是不可解碼或者長度超出官方公布的文件長度±10%范圍，則認(rèn)為是垃圾文件[15]。D. Jia等將P2P垃圾文件分為四類，然后對垃圾文件的特征進行分析，最后提出確定每類垃圾文件的方法。他們的方法特點在于：不需要下載整個文件，只需要文件的相關(guān)信息(比如：文件大小)即可判斷文件是否為垃圾文件[16]。2003年，D. Dutta等通過建立信譽系統(tǒng)，使節(jié)點可以評價彼此從而建立信譽系統(tǒng)以進一步檢測垃圾文件，他們的方法也不需要下載整個文件，但是存在的信譽欺詐行為可能使這類方法失效[17]。

總之，之前針對實際存在的P2P網(wǎng)絡(luò)的測量工作主要是對Gnutella和Kademlia協(xié)議網(wǎng)絡(luò)展開的。針對Kad網(wǎng)絡(luò)的測量也只是局限于節(jié)點可用性測量[9，11]，獲取的節(jié)點信息相當(dāng)有限。而我們設(shè)計的Kad網(wǎng)絡(luò)爬蟲Rainbow可對節(jié)點進行TCP協(xié)議層次的探測，能獲得節(jié)點更豐富的共享資源信息，本文在這基礎(chǔ)上，首度對Kad網(wǎng)絡(luò)的節(jié)點資源進行了相關(guān)統(tǒng)計分析。

4 Kad網(wǎng)絡(luò)節(jié)點資源探測分析

4.1 節(jié)點資源探測分析框架

如圖1所示，Kad網(wǎng)絡(luò)節(jié)點資源統(tǒng)計分析框架由兩個模塊：數(shù)據(jù)采集模塊、統(tǒng)計分析模塊組成。

圖1 Kad網(wǎng)絡(luò)節(jié)點資源探測分析框架

1) 數(shù)據(jù)采集模塊采用我們設(shè)計實現(xiàn)的Kad網(wǎng)絡(luò)節(jié)點信息爬蟲Rainbow進行數(shù)據(jù)采集，數(shù)據(jù)庫使用SQL Server 2005；

2) 統(tǒng)計分析模塊對數(shù)據(jù)庫從兩方面進行分析：a)資源總體統(tǒng)計分析：對采集數(shù)據(jù)的總體就資源的節(jié)點共享情況、文件長度和文件流行度等進行統(tǒng)計分析； b)資源抽樣統(tǒng)計分析：抽樣方式比較以確定最有代表性的抽樣方式，特征擴展以更準(zhǔn)確地進行人工標(biāo)注，并從文件長度、共享用戶數(shù)量、文件類型等方面對敏感文件和正常文件進行比較分析。

4.2 實驗環(huán)境

本文設(shè)計并實現(xiàn)隨機采集方式的Rainbow采集器，通過改造eMule客戶端，模擬一個Kad網(wǎng)絡(luò)正常節(jié)點，加入Kad網(wǎng)絡(luò)，開始隨機采集。進行如下三個階段的操作：UDP節(jié)點采集階段、TCP節(jié)點信息收集階段和寫數(shù)據(jù)庫階段。本文對Kad網(wǎng)絡(luò)進行隨機采集，即不固定k位前綴，只采集部分節(jié)點信息。其優(yōu)點為：

? 采集的節(jié)點規(guī)?？烧{(diào)，典型值為4 000～100 000；

? 進行一次采集的時空復(fù)雜度較低，例如，對20 000節(jié)點進行一次資源探測耗時約45分鐘(其中的TCP節(jié)點信息收集階段因試圖與20 000個節(jié)點建立TCP連接，為主要的耗時瓶頸，其耗時量約為40分鐘)；

? 采集隨機目標(biāo)節(jié)點，可知單次采集的節(jié)點比區(qū)域采集獲得的樣本節(jié)點更具有隨機性,而且進行多次隨機采集會比區(qū)域采集獲得更多的記錄條數(shù)。

限于篇幅，在此不再贅述，詳情參見文獻[18]。應(yīng)用Rainbow在如下配置的機器上進行了數(shù)據(jù)采集。硬件環(huán)境：Intel雙核2.8GHZ/內(nèi)存2G/帶寬2Mb/s ADSL PC一臺；軟件環(huán)境：Windows Server 2003 SP2，SQL Server 2005 Developer Edition。我們讓Rainbow在2009年5月29日到2009年6月9日期間持續(xù)運行，共進行443次隨機采集，為盡快獲得節(jié)點資源信息，每次采集的節(jié)點數(shù)量閾值設(shè)為4 000，文件信息表共獲得7 172 189條去重文件記錄，后文簡稱這些文件為“總體”，且后文的分析主要對這個總體或者從中抽取樣本進行統(tǒng)計分析。

4.3 資源總體統(tǒng)計分析

4.3.1 節(jié)點共享情況統(tǒng)計

表2對數(shù)據(jù)集的節(jié)點/文件數(shù)目進行了統(tǒng)計。由表2可見，UDP節(jié)點采集階段采集的節(jié)點集合SUDP中只有65.09%的節(jié)點可以建立TCP連接，稱這部分節(jié)點為Sonline。剩下的34.91%的節(jié)點可能位于防火墻或NAT (Network Address Translation)后，或者在試圖與其建立TCP連接時已經(jīng)離開Kad網(wǎng)絡(luò)。

在和Sonline中的節(jié)點建立TCP連接后，向它們發(fā)送view_shared_files消息并等待TCP響應(yīng)消息：view_shared_files_answer。由表2可見，Sonline中只有3.09%的節(jié)點會發(fā)回view_shared_files_answer消息且該消息中的“result count”字段大于0，在此，“result count”字段表示響應(yīng)節(jié)點擁有的總文件數(shù)量；Sonline中其他節(jié)點會發(fā)回view shared files answer消息且其“result count”字段為0，或者發(fā)回view sharedfiles denied消息(表示不愿意告訴詢問節(jié)點其共享文件情形)，或者無任何響應(yīng)消息。Rainbow采集器共收集了7 172 189條文件信息，包括文件的元信息，即文件名，文件內(nèi)容哈希(File-content-Hash)，文件大小，文件類型。

表2 采集節(jié)點與文件統(tǒng)計

4.3.2 文件長度統(tǒng)計

對總體的文件長度進行了統(tǒng)計。文件長度的中位數(shù)為4 597 982B(B為字節(jié))，即4.38MB，這正是流行音樂的文件尺寸，表示Kad網(wǎng)絡(luò)中流行音樂占據(jù)了較大比例。最大文件長度為4 294 967 295字節(jié)，約為4G字節(jié)，正好是32位操作系統(tǒng)文件大小的最大值，我們發(fā)現(xiàn)總體中有12個文件具有這種尺寸，其中10個為iso光盤映像文件，2個為vido視頻文件，說明共享的大文件一般是較大的光盤映像文件或DVD視頻文件。最小文件長度為0Byte，我們發(fā)現(xiàn)總體中有5個此類文件，表示總體中存在無用資源。

4.3.3 文件流行度排名分布

文件流行度排名即將每個文件按照節(jié)點共享數(shù)量的大小進行排名，圖2對總體的文件流行度進行統(tǒng)計，其中橫軸表示文件，縱軸表示每個文件對應(yīng)的共享用戶數(shù)量，越接近原點的文件對應(yīng)的共享用戶數(shù)量越多，橫縱軸為log-log坐標(biāo)，可見文件流行度排名近似服從Zipf分布[18]：lgy(x)=lgC-αlgx，并求得α約為0.073 074，lgC約為3.681 060。

圖2 文件流行度排名分布(log-log曲線)

4.4 資源抽樣統(tǒng)計分析

4.4.1 抽樣方式比較

抽樣流行度Top1000文件，簡稱抽樣方式1；抽樣file-content-hash對應(yīng)文件數(shù)量最多的Top100個文件，簡稱抽樣方式2；不放回隨機抽樣100個文件，簡稱抽樣方式3。

表3對三種抽樣方式， 從文件類型和敏感類別方面進行了統(tǒng)計，其中文件類型的類別有video(視頻)、audio(音頻)、arc(存檔)和other(其他)。比較表3的三種抽樣方式的比例可見，三種抽樣方式的統(tǒng)計結(jié)果存在較大差異?？梢?，用抽樣方式1或2來進行敏感分類統(tǒng)計是不合適的。所以我們決定采取抽樣方式3即不放回隨機抽樣方式獲得樣本，并在此基礎(chǔ)上對敏感文件進行統(tǒng)計。

表3 三種抽樣方式比較

4.4.2 資源特征擴展

eMule應(yīng)用中，因文件名可以被用戶更改，一個文件可能具有多個文件名，即FCH1N現(xiàn)象。如圖3所示，我們采用抽樣方式3即隨機不放回抽樣從eMule應(yīng)用中抽取了31 490個文件，并對其文件與文件名的一對多關(guān)系進行了觀察。我們觀察到一個文件平均對應(yīng)約8.94個文件名。

圖3 FCH1N現(xiàn)象(log-線性坐標(biāo))

圖4表示總體的文件名數(shù)量排名分布，其中橫軸表示文件，縱軸表示每個文件對應(yīng)的文件名數(shù)量，越接近原點的文件對應(yīng)的文件名數(shù)量越多，橫縱軸為log-log坐標(biāo)?？梢娢募麛?shù)量排名近似服從Zipf分布，可求得α約為0.003 117，lgC約為2.281 033。

圖4 文件名數(shù)量排名分布(log-log坐標(biāo))

同時，觀察文件名規(guī)律得出如下規(guī)律：根據(jù)同一個file-content-hash對應(yīng)的多個文件名的共現(xiàn)詞或同義詞，基本可以進行正確敏感判別。例如：file-content-hash ="DA61E48B2B9611DB4E628808C0E41474"的文件名有103個，其中“Share Accelerator”共出現(xiàn)了102次，根據(jù)這個特征(表示這個文件是個共享的加速器軟件)，可以將之標(biāo)注為非敏感文件。又例如：見表4，file-content-hash=“6049E44451B7F262ACF094418EBA461C”的文件名有45個，其中l(wèi)esbian和他的同根詞lesbo等和同義詞“女同”共出現(xiàn)19次。根據(jù)這個特征，可以將之人工標(biāo)注為敏感文件。

表4 共現(xiàn)詞共現(xiàn)次數(shù)統(tǒng)計

為充分利用這個特征來準(zhǔn)確進行資源敏感判別，我們將同一個file-content-hash對應(yīng)的文件名放到一起，利用共現(xiàn)詞/同義詞來進行人工標(biāo)注。如果仍然無法利用共現(xiàn)詞進行人工標(biāo)注，通過在搜索引擎上查找共現(xiàn)詞來獲得更多信息以進行人工標(biāo)注。

4.4.3 敏感資源統(tǒng)計

采用抽樣方式3，對6 261個文件名進行了敏感判別，其中C1類有397個，占6.34%；C2類有2 226個，占35.55%；C3類有3 638個，占58.11%，由判別結(jié)果可見，雖然敏感文件所占的總體比例不高(6.34%)，但由于eMule網(wǎng)絡(luò)存在的文件數(shù)量極大，故敏感文件的絕對數(shù)量不容小視*據(jù)我們觀察，55 238個節(jié)點即共享了7 172 189個文件，而eMule用戶數(shù)量以百萬計[11]，因而eMule應(yīng)用中的文件數(shù)量應(yīng)該上億，導(dǎo)致其中敏感文件的絕對數(shù)量應(yīng)該數(shù)以百萬計。。

敏感文件與正常文件在很多方面具有各自的特點，圖5分別從文件長度(見圖5(a))，共享用戶數(shù)量(見圖5(b))和文件類型(見圖5(c)(d))等方面對敏感文件與正常文件進行了比較。從圖5(a)可見，敏感文件比正常文件的平均大小大。具體而言，我們觀察到敏感文件和正常文件的平均大小分別為353.54MB和134.67MB。從圖5(b)可見，敏感文件比正常文件的共享用戶數(shù)量多。具體而言，我們觀察到敏感文件和正常文件的平均共享用戶數(shù)量大小分別為5.06和2.82。由此可見，敏感文件更受eMule用戶的歡迎。從圖5(c)、(d)可見，雖然絕大部分敏感文件和正常文件的文件類型都是影音文件(即video和audio類型的文件)，但是，敏感文件的主要類型為video文件(占74.8%)，而正常文件的主要類型為audio文件(占38.6%)。由此可見，eMule用戶傾向于共享影音文件，其中尤以較大的敏感video文件受到eMule用戶的喜愛。

圖5 敏感文件與正常文件在文件長度、共享用戶數(shù)量和文件類型等方面的比較(圖(a)、(b)為log-線性坐標(biāo))

5 結(jié)論

本文為了解Kad網(wǎng)絡(luò)中資源分布規(guī)律，首先利用我們設(shè)計實現(xiàn)的節(jié)點信息爬蟲Rainbow，對節(jié)點所擁有的文件資源在2009年5月29日到2009年6月9日期間進行了探測，獲得了7 172 189條文件信息；然后對節(jié)點資源就如下方面進行了總體統(tǒng)計：節(jié)點資源情況、文件長度、文件流行度等；最后從采集數(shù)據(jù)總體中抽取較大樣本進行敏感判別，并從文件長度、共享用戶數(shù)量、文件類型等方面對敏感文件和正常文件進行了比較。實驗分析結(jié)果表明，雖然敏感資源占共享資源的相對比率不大，但其絕對數(shù)量不容小視，故對敏感資源尤其是敏感視頻文件的判別和監(jiān)管是很有必要的。進一步的工作有：利用隨機樣本的敏感判別結(jié)果，形成訓(xùn)練集，采用機器學(xué)習(xí)方法對節(jié)點資源進行自動敏感判別。

[1] eMule. http://www.eMule-project.net, 2009.

[2] P.Maymounkov and D.Mazieres, Kademlia：A Peer-to-peer Information System Based on the XOR Metric[C]//International Workshop on Peer-to-Peer Systems, 2002.

[3] Ipoque,http://torrentfreak.com/bittorrent-still-king-of-p2p-traffic-090218/, 2009.

[4] Thomas Karagiannis, Andre Broido, Nevil Brownlee, Kc Claffy and Michalis Faloutsos, Is P2P dying or just hiding[C]//GlobeCom, 2004.

[5] Thomas Karagiannis， Andre Broido， Michalis Faloutsos and Kc Claffy, Transport Layer Identification of P2P Traffic[C]//Proc. Internet Measurement Conference(IMC), 2004.

[6] Saroiu S, Gummadi PK, Gribble SD., A measurement study of peer-to-peer file sharing systems[C]//Proc. of the Multimedia Computing and Networking(MMCN), 2002：156-170.

[7] D. Stutzbach, R. Rejaie and Sen S., Characterizing unstructured overlay Topologies in modern P2P file-sharing systems[C]//Proc. of the 5th ACM SIGCOMM Conf. on Internet Measurement, 2005.

[8] D. Stutzbach and R. Rejaie, Improving lookup performance over a widely-deployed DHT[C]//Proc. INFOCOM, 2006.

[9] D. Stutzbach and R. Rejaie, Understanding churn in peer-to-peer networks[C]//Proc. Internet Measurement Conference(IMC), 2006.

[10] 王勇, 云曉春, 李奕飛.對等網(wǎng)絡(luò)拓撲測量與特性分析[J]. 軟件學(xué)報， 2008，19(4)：981-992.

[11] M. Steiner, T. En-Najjary, and E. W. Biersack, Long term study of peer behavior in the KAD DHT[J]. IEEE/ACM Transaction on Networking, 2009, 17(5): 1371-1384.

[12] M. Steiner, T. En-Najjary, and E. W. Biersack, A Global View of Kad[C]//Proc. Internet Measurement Conference(IMC), 2007.

[13] M. Steiner, E. W. Biersack， and T. Ennajjary, Actively monitoring peers in Kad[C]//Proceedings of the 6th International Workshop on Peer-to-Peer Systems(IPTPS), 2007.

[14] Jarret Falkner, Michael Piatek, John P. John, Arvind Krishnamurthy and Thomas Anderson, Profiling a million user DHT[C]//Proc. Internet Measurement Conference(IMC), 2007.

[15] D. Jia, W. G. Yee, O. Frieder, Spam Characterization and Detection in Peer-to-Peer File-Sharing Systems[C]//Proc. ACM Conf. on Inf. and Knowl. Mgt. (CIKM), 2008.

[16] J. Liang, R. Kumar, Y. Xi and K. Ross, Pollution in P2P File Sharing Systems[C]//Proc. of INFOCOM, May 2005.

[17] D. Dutta, A. Goel, R. Govindan, H. Zhang, The Design of A Distributed Rating Scheme for Peer-to-peer Systems[C]//Proc. of Workshop on the Economics of Peer-to-Peer Systems, 2003.

[18] ChrisTopher D. Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing[M]. MIT Press, ISBN 978-0262133609, 1999.