1、Kad 网络节点资源探测分析 刘祥涛 1, 2，龚才春 3，刘悦 1，白 硕 11（中国科学院计算技术研究所 北京 100190）2（中国科学院研究生院 北京 100190）3（北京市计算中心 北京 100005）摘 要 Kad 网络中存在数以亿计的共享资源，而其中有相当一部分可被评定为敏感资源。首先用我们的Kad 网络采集器：Rainbow 对节点拥有的文件资源进行探测；然后对节点资源和敏感资源进行相关统计分析。我们发现：1)文件流行度和文件所对应的文件名数量都近似符合 Zipf 分布；2)利用同一个“文件内容哈希”(即 file-content-hash)的多个文件名的共现词可以更准确地进
2、行敏感判别； 3)敏感资源占随机样本的6.34%，且敏感资源中 74.8%为 video 文件。关键词 对等网络；Kad 网络；探测分析；敏感资源Peer Resource Measurement and Analysis in Kad NetworkLiu Xiang-Tao1,2, Gong Cai-Chun3, Liu Yue1, Bai Shuo11(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)2(Graduate University, Chinese Academy o
3、f Sciences, Beijing 100190)3(Beijing Computing Center, Beijing 100005)Abstract In Kad network, there are hundreds of millions of shared resources, among which a considerable part can be rated as sensitive resources. Firstly, the file resources of peers are measured using our Kad-network crawler: Rai
4、nbow, then, those resources and sensitive resources are statistically analyzed. We find that: 1) both the popularity of files and the number of filenames corresponding to a file approximately fit Zipf distribution; 2) the sensitivity of files can be judged more accurately using co-occurrence-words i
5、n multiple filenames corresponding to the same file-content-hash; 3) sensitive resources only occupy 6.34% of random sample, and 74.8% of sensitive resources are video files.Keywords Peer-to-peer network; Kad network; measurement and analysis; sensitive resource1 引言eMule 网络 1是一种混合类型的文件共享对等网络，它由两部分：集
6、中式网络和纯分布式网络组成。其中纯分布式网络采用了 Kademlia 协议 2，是 eMule 网络的主要组成部分。一般来说，采用 Kademlia 协议的 eMule 网络称为 Kad 网络。Ipoque 20082009 年度的因特网流量报告表明：依地理位置的不同，eMule 占 P2P 流量的 2%47%，占因特网流量基金项目：本课题得到国家自然科学基金（No.60803085, No. 60873245）；国家高技术研究发展计划(863计划) （2006AA01Z452）的资助。作者简介：刘祥涛，男，1977年生，博士研究生，研究方向：P2P网络安全，数据挖掘等，Email ： . 龚
7、才春，男，1978年生，博士，研究方向：信息检索，数据挖掘等. 刘悦，女，1971年生，副研究员，研究方向：信息检索，社区挖掘与分析，分布式计算等. 白硕，男，1956年生，博士，研究员，博士生导师，研究方向：自然语言处理，网络安全等.1%26%3，且呈上涨趋势 45。Kad 网络为不健康内容的传播提供了方便，在 Kad 网络中存在数百万的共享资源，其中有相当一部分不合适让特定人群观看，我们称这些资源为敏感资源。所以对 Kad 网络中的共享资源进行探测分析是相当必要的，这样不仅可以了解敏感资源的扩散程度，也可以为不健康内容的过滤做好铺垫工作。从而减少特定人群受不健康内容侵蚀的影响，有助于社会精
8、神文明建设。Kad 网络的探测分析存在如下挑战： 虽然对等网络爬虫研究已经取得了较大进展 691011，但直到现在，也不存在一个可以探测“节点”即被指定了一定标识的物理机器的 共享资源 的爬虫； 节点资源名是多语言的，比如英语、中文、日语、韩语、法语、西班牙语等，给资源的敏感判别增加了难度； 节点资源名通常都较短，从而其特征往往不足以判定其是否为敏感资源。针对上述挑战： 在已有对等网络爬虫的工作基础上，设计和实现可以采集节点资源的爬虫； 本文只对中文、英语和其他易判资源进行敏感判别和统计分析，但是分析方法也适用于其他语言； 采用两种增加文件名特征的方法。a)file-content-hash
9、是通过哈希文件内容获得的128 位标识符。一个 file-content-hash 可能对应多个文件名，本文称为“FCH1N 现象” 。我们将对应同一个 file-content-hash 的多个文件名集中起来加强文件名特征。b)通过在流行搜索引擎上输入文件名中包含的关键词，获得更多信息以加强文件名特征。本文后续章节安排如下，第二节介绍研究背景，第三节介绍相关工作，第四节对节点资源进行探测和统计分析。最后，我们在第五节对全文进行总结。2 背景节点资源名是多语言的且长度较短，导致对其进行敏感判别的难度，见表 1。为提高敏感判别的准确性，本文适当简化问题和进行特征扩展（详见 4.4.1 节） 。表
10、 1 文件名的复杂性Tab.1 the complexity of filename无意义名 ?.bmp无法区分名 0094.gif中文简体 驱动之家-驱动分类查询.url中文繁体 張惠妹 A-mei - 妹力最精選 -24-灰姑娘.mp3日文 (av)浜崎(森下、篠原絵梨香)青木玲 峰 .avi英文 csi.6x17.i.like.to.watch.hdtv-lol.avi西班牙语 (Reggaeton)Tito Y Hector - Gata Salvaje.mp3其他 为降低问题的复杂性，本文只对英文或中文简体可识别文件名进行敏感判别。同时将文件分为 3 个类别：敏感文件、正常文件、忽略
11、文件，分别简称 C1、C 2和 C3类文件。定义 1.敏感文件(C 1类文件)：其内容不合适让特定人群浏览的文件。比如：文件名为“风骚的女子_俄罗斯.rar”的文件是敏感文件。又比如：“Water Melons cd1 .www.EMuleX.es.avi”单从文件名看不出是否敏感，但通过搜索引擎查找相关信息可以获知是一个色情敏感电影。定义 2.正常文件( C2类文件)：其内容合适让特定人群浏览的文件。比如：“汉初军事史研究.pdf”是一个正常的电子书文件；“The Pointer Sisters - Automatic.mp3”是一个正常的音乐文件。定义 3. 忽略文件( C3类文件)：因为
12、文件名及其相关信息不足或因为语言差异以至不能正确区分某文件是否敏感或正常的文件。比如：“?.bmp” 、 “0094.gif”和“(Reggaeton)Tito Y Hector - Gata Salvaje.mp3”都是忽略文件。3 相关工作对等网络爬虫探测工作开展较早，2002 年，Saroiu 等人率先使用主动测量方法对当时最为流行的 Gnutella 和 Napster 进行了拓扑测量 6。2005 年，Stutzbach 等人在前人的工作基础上改进了主动测量方法并开发出了快速分布式 Gnutella 拓扑采集器：Cruiser，证明了因为节点震荡(churn)和采集器采集速度太慢可能
13、导致错误的实验结论 7。因此，使得提高Crawler 的采集速度成为提高拓扑测量准确性的关键问题。 2008 年，王勇等人针对 Gnutella网络设计了基于正反馈的分布式 Gnutella 拓扑采集器：D-Crawler，提出了度量采集器准确性、完整性的衡量指标，分析了 Gnutella 网络拓扑图的度等级分布特征、度频率分布特征以及小世界特性 10。Kademlia 协议的实现有 Kad 网络和 Bittorrent 的 DHT 网络等。2006 年 Stutzbach 等人针对 Kad 网络提出了计算查询性能的分析框架，并开发出了两个软件：kFetch 和 kLookup用于采集和计算
14、Kad 网络的查询性能 8。2006 年 Stutzbach 等人对三个 P2P 网络：Gnutella、Kad 网络和 Bittorrent 进行了测量分析，针对 Kad 网络，他们用 Cruiser 采集了两天的拓扑数据，然后对节点可用性进行了分析 9。2007 年 Steiner 等人设计了 Kad 网络采集器：Blizzard 并进行了为期 179 天的 Kad 网络采集，获得了节点的地理分布、会话时间、节点可用性和生命周期等测度的测量结果 111213。2007 年 Falkner 等人在 PlanetLab 实验条件下，对 Bittorrent 的一个客户端 Azureus 的 D
15、HT 网络进行了测量 14。与节点资源分析相关的工作有对等网络垃圾过滤(P2P Spam Filtering)等，2005 年，J.Liang 等提出了一种垃圾过滤方法：首先下载共享音乐文件，若该文件是不可解码或者长度超出官方公布的文件长度 10%范围，则认为是垃圾文件 15。D. Jia 等将 P2P 垃圾文件分为四类，然后对垃圾文件的特征进行分析，最后提出确定每类垃圾文件的方法。他们的方法特点在于：不需要下载整个文件，只需要文件的相关信息(比如：文件大小) 即可判断文件是否为垃圾文件 16。2003 年，D. Dutta 等通过建立信誉系统，使节点可以评价彼此从而建立信誉系统以进一步检测垃
16、圾文件，他们的方法也不需要下载整个文件，但是存在的信誉欺诈行为可能使这类方法失效 17。总之，之前针对实际存在的 P2P 网络的测量工作主要是对 Gnutella 和 Kademlia 协议网络展开的。针对 Kad 网络的测量也只是局限于节点可用性测量 911，获取的节点信息相当有限。而我们设计的 Kad 网络爬虫 Rainbow 可对节点进行 TCP 协议层次的探测，能获得节点更丰富的共享资源信息，本文在这基础上，首度对 Kad 网络的节点资源进行了相关统计分析。4 Kad 网络节点资源探测分析4.1 节点资源探测分析框架如图 1 所示，Kad 网络节点资源统计分析框架由两个模块：数据采集模
17、块、统计分析模块组成。K a d N e t w o r kR a i n b o w资源总体统计分析资源抽样统计分析数据库节点共享情况文件长度文件流行度统计分析模块数据采集模块抽样方式比较特征扩展敏感资源分析图 1 Kad网络节点资源探测分析框架Fig.1 Peer resource measurement and analysis framework in Kad network1) 数据采集模块采用我们设计实现的 Kad 网络节点信息爬虫 Rainbow 进行数据采集，数据库使用 SQL Server 2005；2) 统计分析模块对数据库从两方面进行分析：a)资源总体统计分析：对采集数据
18、的总体就资源的节点共享情况、文件长度和文件流行度等进行统计分析；b)资源抽样统计分析：抽样方式比较以确定最有代表性的抽样方式，特征扩展以更准确地进行人工标注，并从文件长度、共享用户数量、文件类型等方面对敏感文件和正常文件进行比较分析。4.2 实验环境本文设计并实现随机采集方式的 Rainbow 采集器，通过改造 eMule 客户端，模拟一个Kad 网络正常节点，加入 Kad 网络，开始随机采集。进行如下三个阶段的操作：UDP 节点采集阶段、TCP 节点信息收集阶段和写数据库阶段。本文对 Kad 网络进行随机采集，即不固定 k 位前缀，只采集部分节点信息。其优点为： 采集的节点规模可调，典型值为
19、 4,000100,000； 进行一次采集的时空复杂度较低，例如，对 20,000 节点进行一次资源探测耗时约45 分钟(其中的 TCP 节点信息收集阶段因试图与 20,000 个节点建立 TCP 连接，为主要的耗时瓶颈，其耗时量约为 40 分钟)； 采集随机目标节点，可知单次采集的节点比区域采集获得的样本节点更具有随机性,而且进行多次随机采集会比区域采集获得更多的记录条数。应用 Rainbow 在如下配置的机器上进行了数据采集。硬件环境：Intel 双核 2.8GHZ/内存 2G/带宽 2Mb/s ADSL PC 一台；软件环境：Windows Server 2003 SP2，SQL Ser
20、ver 2005 Developer Edition。我们让 Rainbow 在 2009 年 5 月 29 日到 2009 年 6 月 9 日期间持续运行，共进行 443 次随机采集，为尽快获得节点资源信息，每次采集的节点数量阈值设为 4,000，文件信息表共获得 7,172,189 条去重文件记录，后文简称这些文件为“总体” ，且后文的分析主要对这个总体或者从中抽取样本进行统计分析。 4.3 资源总体统计分析4.3.1 节点共享情况统计表 2 对数据集的节点/文件数目进行了统计。由表 2 可见，UDP 节点采集阶段采集的节点集合 SUDP 中只有 65.09%的节点可以建立 TCP 连接，
21、称这部分节点为 Sonline。剩下的34.91%的节点可能位于防火墙或 NAT (network address translation)后，或者在试图与其建立TCP 连接时已经离开 Kad 网络。在和 Sonline中的节点建立 TCP 连接后，向它们发送 view_shared_files 消息并等待 TCP响应消息：view_shared_files_answer。由表 2 可见，S online中只有 3.09%的节点会发回view_shared_files_answer 消息且该消息中的“result count”字段大于 0，在此， “result count”字段表示响应节点拥
22、有的总文件数量；S online中其它节点会发回 view shared files answer 消息且其“result count”字段为 0，或者发回 view sharedfiles denied 消息( 表示不愿意告诉询问节点其共享文件情形)，或者无任何响应消息。 Rainbow 采集器共收集了7,172,189 条文件信息，包括文件的元信息，即文件名，文件内容哈希(file-content-hash)，文件大小，文件类型。表 2 采集节点与文件统计Tab.2 Statistics of crawled peers and files 数量 比率UDP 节点采集阶段探测到总节点（S
23、UDP） 1,786,312 100%能建立 TCP 连接的节点 1,162,771 65.09%有至少一个共享文件的节点 55,238 3.09%没有共享文件的节点 892,030 49.94%发回 View shared folder or content denied 消息的节点 25,799 1.44%不发回任何 TCP 消息的节点 189,704 10.62%去重后节点共享文件 7,172,189 -4.3.2 文件长度统计对总体的文件长度进行了统计。文件长度的中位数为 4,597,982B(B 为字节)，即4.38MB，这正是流行音乐的文件尺寸，表示 Kad 网络中流行音乐占据了较
24、大比例。最大文件长度为 4,294,967,295 字节，约为 4G 字节，正好是 32 位操作系统文件大小的最大值，我们发现总体中有 12 个文件具有这种尺寸，其中 10 个为 iso 光盘映像文件，2 个为 vido 视频文件，说明共享的大文件一般是较大的光盘映像文件或 DVD 视频文件。最小文件长度为 0Byte，我们发现总体中有 5 个此类文件，表示总体中存在无用资源。4.3.3 文件流行度排名分布文件流行度排名即将每个文件按照节点共享数量的大小进行排名，图 2 对总体的文件流行度进行统计，其中横轴表示文件，纵轴表示每个文件对应的共享用户数量，越接近原点的文件对应的共享用户数量越多，横
25、纵轴为 log-log 坐标，可见文件流行度排名近似服从Zipf 分布 18：lg y(x)=lgC lgx，并求得 约为 0.073074，lgC 约为 3.681060。110100100010000文 件共享用户数量图 2 文件流行度排名分布(log-log 曲线)Fig.2 Rank distribution of file popularity (log-log scale)4.4 资源抽样统计分析4.4.1 抽样方式比较抽样流行度 Top1000 文件，简称抽样方式 1；抽样 file-content-hash 对应文件数量最多的 Top100 个文件，简称抽样方式 2；不放回随机
26、抽样 100 个文件，简称抽样方式 3。表 4 三种抽样方式比较Tab.4 Comparison among three kinds of sample method 分类依据 类别 抽样方式 1 比例 抽样方式 2 比例 抽样方式 3 比例video 59.9% 86.0% 28.0%audio 12.3% 2.0% 28.0%arc 0.6% 12.0% 10.0%文件类型other 27.2% 0% 34.0%敏感类别 C1类 0% 65.0% 8.0%C2类 100.0% 23.0% 38.0%C3类 0% 12.0% 54.0%表 4 对三种抽样方式，从文件类型和敏感类别方面进行了统
27、计，其中文件类型的类别有 video（视频） 、audio （音频） 、arc（存档）和 other（其他） 。比较表 4 的三种抽样方式的比例可见，三种抽样方式的统计结果存在较大差异。可见，用抽样方式 1 或 2 来进行敏感分类统计是不合适的。所以我们决定采取抽样方式 3 即不放回随机抽样方式获得样本，并在此基础上对敏感文件进行统计。4.4.2 资源特征扩展eMule 应用中，因文件名可以被用户更改，一个文件可能具有多个文件名，即 FCH1N现象。如图 3 所示，我们采用抽样方式 3 即随机不放回抽样从 eMule 应用中抽取了 31,490个文件，并对其文件与文件名的一对多关系进行了观察。
28、我们观察到一个文件平均对应约8.94 个文件名。100 101 10200.20.40.60.81一一一一一一一一一一一一一一一一一一(CDF)图 3 FCH1N现象（log-线性坐标）Fig.3 FCH1N phenomenon (log-linear scale)图 4 表示总体的文件名数量排名分布，其中横轴表示文件，纵轴表示每个文件对应的文件名数量，越接近原点的文件对应的文件名数量越多，横纵轴为 log-log 坐标。可见文件名数量排名近似服从 Zipf 分布，可求得 约为 0.003117，lgC 约为 2.281033。1101001000文 件文件名数量图 4 文件名数量排名分布（
29、log-log 坐标）Fig.4 Rank distribution of filenames number (log-log scale)同时，观察文件名规律得出如下规律：根据同一个 file-content-hash 对应的多个文件名的共现词或同义词，基本可以进行正确敏感判别。例如：file-content-hash =”DA61E48B2B9611DB4E628808C0E41474”的文件名有 103 个，其中“Share Accelerator”共出现了 102 次，根据这个特征（表示这个文件是个共享的加速器软件） ，可以将之标注为非敏感文件。又例如：见表 3，file-conten
30、t-hash=“6049E44451B7F262ACF094418EBA461C ”的文件名有 45 个，其中 lesbian 和他的同根词 lesbo 等和同义词“女同”共出现 19 次。根据这个特征，可以将之人工标注为敏感文件。表 3 共现词共现次数统计Tab.3 Appearing times statistics of co-occurrence-words 共现词 次数 共现词 次数lesbian 10 lesben 1lesbo 4 女同 2lesbiche 2 共现次数 19为充分利用这个特征来准确进行资源敏感判别，我们将同一个 file-content-hash 对应的文件名放
31、到一起，利用共现词/ 同义词来进行人工标注。如果仍然无法利用共现词进行人工标注，通过在搜索引擎上查找共现词来获得更多信息以进行人工标注。4.4.3 敏感资源统计采用抽样方式 3，对 6,261 个文件名进行了敏感判别，其中 C1类有 397 个，占6.34%； C2类有 2,226 个，占 35.55%；C 3类有 3,638 个，占 58.11%，由判别结果可见，虽然敏感文件所占的总体比例不高(6.34%)，但由于 eMule 网络存在的文件数量极大，故敏感文件的绝对数量不容小视 *。敏感文件与正常文件在很多方面具有各自的特点，图 5 分别从文件长度(见图 5(a)，共享用户数量(见图 5(
32、b)和文件类型(见图 5(c)(d)等方面对敏感文件与正常文件进行了比较。从图 5(a)可见，敏感文件比正常文件的平均大小大。具体而言，我们观察到敏感文件和正常文件的平均大小分别为 353.54MB 和 134.67MB。从图 5(b)可见，敏感文件比正常文件的共享用户数量多。具体而言，我们观察到敏感文件和正常文件的平均共享用户数量大小分别为 5.06 和 2.82。由此可见，敏感文件更受 eMule 用户的欢迎。从图 5(c)(d)可见，虽然绝大部分敏感文件和正常文件的文件类型都是影音文件(即 video 和 audio 类型的文件) ，但是，敏感文件的主要类型为 video 文件(占 74
33、.8%)，而正常文件的主要类型为 audio 文件(占 38.6%)。由此可见，eMule 用户倾向于共享影音文件，其中尤以较大的敏感 video 文件受到 eMule用户的喜爱。据我们观察，55,238个节点即共享了 7,172,189个文件，而eMule用户数量以百万计 11，因而eMule应用中的文件数量应该上亿，导致其中敏感文件的绝对数量应该数以百万计。100 105 101000.20.40.60.81一一一一CDF(a) 一一一一CDF一1 10 10000.20.40.60.81一一一一一一CDF(b) 一一一一一一CDF一一一一一一一一一一一一一一一一一0.6% audio74
34、.8% video3.0% arc0.6% doc13.8% image7.2% other(c) 一一一一一一一一一38.6% audio22.8% video11.6% arc7.0% doc3.3% image16.7% other(d) 一一一一一一一一一图 5敏感文件与正常文件在文件长度、共享用户数量和文件类型等方面的比较（图(a)(b)为 log-线性坐标）Fig.5 Comparison of file size, number of shared users and file types between vulgar and normal files. Figure (a) a
35、nd (b) are log-linear scale.5 结论本文为了解 Kad 网络中资源分布规律，首先利用我们设计实现的节点信息爬虫Rainbow，对节点所拥有的文件资源在 2009 年 5 月 29 日到 2009 年 6 月 9 日期间进行了探测，获得了 7,172,189 条文件信息；然后对节点资源就如下方面进行了总体统计：节点资源情况、文件长度、文件流行度等；最后从采集数据总体中抽取较大样本进行敏感判别，并从文件长度、共享用户数量、文件类型等方面对敏感文件和正常文件进行了比较。实验分析结果表明，虽然敏感资源占共享资源的相对比率不大，但其绝对数量不容小视，故对敏感资源尤其是敏感视频
36、文件的判别和监管是很有必要的。进一步的工作有：利用随机样本的敏感判别结果，形成训练集，采用机器学习方法对节点资源进行自动敏感判别。参 考 文 献1 eMule. http：/www.eMule-, 2009.2 P.Maymounkov and D.Mazieres, Kademlia: A Peer-to-peer Information System Based on the XOR MetricC. In International Workshop on Peer-to-Peer Systems, 2002.3 Ipoque,http:/ 2009.4 Thomas Karagiann
37、is, Andre Broido, Nevil Brownlee, Kc Claffy and Michalis Faloutsos, Is P2P dying or just hidingC. In GlobeCom, 2004.5 Thomas Karagiannis， Andre Broido， Michalis Faloutsos and Kc Claffy, Transport Layer Identification of P2P TrafficC. In Proc. Internet Measurement Conference(IMC), 2004.6 Saroiu S, Gu
38、mmadi PK, Gribble SD., A measurement study of peer-to-peer file sharing systemsC. In Proc. of the Multimedia Computing and Networking(MMCN), 2002. p.156-170. 7 D. Stutzbach, R. Rejaie and Sen S., Characterizing unstructured overlay Topologies in modern P2P file-sharing systemsC. In Proc. of the 5th
39、ACM SIGCOMM Conf. on Internet Measurement, 2005.8 D. Stutzbach and R. Rejaie, Improving lookup performance over a widely-deployed DHTC. In Proc. INFOCOM, 2006.9 D. Stutzbach and R. Rejaie, Understanding churn in peer-to-peer networksC. In Proc. Internet Measurement Conference(IMC), 2006.10 王勇, 云晓春,
40、李奕飞, 对等网络拓扑测量与特性分析J. 软件学报. 2008. 19(4):p.981-992.11 M. Steiner, T. En-Najjary, and E. W. Biersack, Long term study of peer behavior in the KAD DHTJ. In IEEE/ACM Transaction on Networking, 2009, 17(5):p.1371-1384.12 M. Steiner, T. En-Najjary, and E. W. Biersack, A Global View of KadC. In Proc. Intern
41、et Measurement Conference(IMC), 2007.13 M. Steiner, E. W. Biersack， and T. Ennajjary, Actively monitoring peers in KadC. In 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, Pr
42、ofiling a million user DHTC. In Proc. Internet Measurement Conference(IMC), 2007.15 D. Jia, W. G. Yee, O. Frieder, Spam Characterization and Detection in Peer-to-Peer File-Sharing SystemsC. In Proc. ACM Conf. on Inf. and Knowl. Mgt. (CIKM), 2008.16 J. Liang, R. Kumar, Y. Xi and K. Ross, Pollution in
43、 P2P File Sharing SystemsC. In 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 SystemsC. In Proc. of Workshop on the Economics of Peer-to-Peer Systems, 2003.18 ChrisTopher D. Manning and Hinrich Schtze, Foundations of Statistical Natural Language ProcessingM. MIT Press, ISBN 978-0262133609, 1999. p. 24.
