Kad网络的联合污染模型

收稿日期:2011-02-18;修回日期:2011-04-01。基金项目:国家863计划项目（2009AA01Z424）。

作者简介:孔拢1981-），男，陕西西安人，博士研究生，主要研究方向：网络信息安全、P2P网络污染； 蔡皖东（1955-），男，陕西西安人，教授，博士生导师，主要研究方向：网络安全、信息对抗。

文章编号:1001-9081（2011）08-02152-04doi:10.3724/SP.J.1087.2011.02152

（西北工业大学 计算机学院，西安710129）

（）

摘 要:将Kad网络中的关键词污染和文件源污染结合起来，使用状态转移分析的方法构造了一种联合污染模型。模型中综合考虑了污染程度、退出率、等待率等因素。对模型的仿真实验数据显示，受到联合污染时，Kad网络中查询失败的用户数远大于查询成功的用户数，并随着时间的增加而趋于稳定。在影响联合污染效果的若干因素中，污染程度对联合污染的效果有决定性的影响，退出率的影响次之，等待率的影响最小。

关键词:Kad网络；对等网；关键词污染；文件源污染；联合污染模型；状态转移

中图分类号: TP393.08文献标志码:A

Joint pollution model in Kad network

KONG Jie, CAI Wan-dong

（School of Computer Science and Technology, Northwestern Polytechnical University, Xi'an Shannxi 710129, China）

Abstract: In this paper, a joint pollution model, which combined the pollution of keyword and the pollution of location, was proposed. The degree of pollution, the rate of exit and the rate of waiting were taken into account in the model. The simulation results show that the quantity of user of querying failed is much larger than the quantity of user of querying successfully by the impact of joint pollution and become stable with time increasing. The degree of pollution is the key factor which influence the effect of the joint pollution, the effect of exit rate is smaller than the degree of pollution and the effect of waiting rate is the smallest.

Key words: Kad network; Peer-to-Peer （P2P）; keyword pollution; file source pollution; joint pollution model; state transfer

0 引言

近年来，为了提高系统的鲁棒性，基于分布式散列表（Distributed Hash Table, DHT）技术的Kademlia算法［1］被引入到Peer-to-Peer （P2P）文件共享系统中，使用户不查询中心服务器即可找到资源的提供者。采用Kademlia算法构建的网络，其拓扑结构属于全分布式结构化拓扑，在eMule系统中被称为Kad网络，在BitTorrent系统中被称为DHT网络。

P2P污染是一种用于控制特定文件在P2P文件共享系统中传播的文件下载控制技术，最早用于控制盗版音像制品通过P2P文件共享系统非法传播。2005年，Liang等人［2］对当时已发现的P2P污染给出了详细的描述。在接下来几年中，又派生出多种P2P污染技术，主要可分为内容污染与索引污染。内容污染通过在P2P网络中传播虚假的文件内容实现对文件传播的控制。Dhungel等人［3］介绍了被称为Fake-Block Attack和Uncooperative-Peer Attack的内容污染方法，并对这两种污染方法在BitTorrent系统中的效果进行了评估。索引污染则通过干扰P2P网络的索引系统，使其无法提供资源索引服务到控制特定文件传播的目的。Liang等人［4］介绍了非结构化的FastTrack系统与结构化的Overnet系统中的索引污染，并对污染效果进行了测量分析。目前学术界对P2P污染的研究一方面是对P2P污染效果进行测量分析，文献［1-4］都属于此类研究；另一方面是对P2P污染进行建模分析。胡辛遥［5］提出了污染统一模型，将内容污染与索引污染结合起来进行建模分析。左敏等人［6］用状态转移模型描述P2P文件污染现象以及污染散播过程的时间特性。方群等人［7］基于Markov生灭过程建立了污染传播模型,另外方群［8］基于古典概率模型创建了文件污染模型。云燕［9］对P2P文件共享中污染版本的传播情况进行建模。Mao等人［10］通过建模分析了资源流行度和传播时间对污染效果的影响。文献［5-10］的建模分析主要针对非结构化的P2P系统，没有考虑结构化P2P系统的污染建模问题。本文对结构化的Kad网络中的P2P污染进行建模分析，得到污染效果的时间特性，并对影响Kad网络污染效果的因素进行分析。

1 面向Kad网络的P2P污染

1.1 Kad网络的资源与查询机制

在eMule系统中，Kad主要充当文件信息检索协议的角色。Kad网络中有2种重要的散列值：关键词散列值和文件散列值。对eMule客户端的共享资源的描述信息进行分词，得到共享资源的关键词，再使用SHA1算法对关键词进行计算得到的散列值被称为关键词散列值。对eMule客户端的共享资源使用SHA1算法计算出的散列值被称为文件散列值。

eMule客户端在Kad网络中资源信息时，首先将关键词信息到Kad网络中节点ID等于或最接近关键词散列值的若干个节点（具体查询过程可参阅文献［1］），将这些节点称为“关键词信息中间节点”。关键词信息是一个〈key,value〉的属性对，其中key的值等于关键词散列值，value为一个列表，该列表给出了关键词对应的文件信息，格式为：（文件名，文件长度，文件散列值）。随后eMule客户端还需要文件源信息。客户端首先文件源信息到Kad网络中节点ID等于或最接近文件散列值的节点上，这些节点被称为“文件源信息中间节点”。文件源信息也是一个〈key,value〉的属性对，其中key的值等于所资源的文件散列值；value值为拥有该文件的节点（即者）的网址信息，格式为：（拥有者IP，端口号，拥有者节点ID）。

资源请求者通过输入关键词查询资源时，搜索Kad网络中节点ID等于或最接近关键词散列值的节点，可从关键词信息中间节点获得与关键词对应的文件散列值。随后根据获得的文件散列值，搜索Kad网络中节点ID与之相等或最接近的节点，即可找到文件源信息中间节点，得到资源提供者的地址信息，进而请求与资源提供者建立连接，开始数据传输。

1.2 Kad网络的关键词污染和文件源污染

污染者进行关键词污染时，首先提取欲污染文件的关键词信息，并计算关键词散列值，根据关键词散列值查询到关键词信息中间节点。随后，污染者向这些节点大量虚假的关键词信息，即（文件名，文件长度，文件散列值）三元组中文件散列值是无效的。由于Kad网络的资源查询过程中，资源请求者从关键词信息中间节点获取正确的文件散列值是进行文件源查询的前提条件，因此关键词污染将导致资源请求节点无法找到正确的资源提供节点。

污染者进行文件源污染时，首先查询关键词或解析文件eD2k链接获得文件的文件散列值，并根据文件散列值查询到文件源信息中间节点。随后，污染者向这些节点大量虚假的文件源信息，即将虚假的（拥有者IP，端口号，拥有者节点ID）三元组到文件源信息中间节点。文件源信息中间节点受文件源污染后，资源请求者无法由文件散列值得到正确的资源提供节点的地址信息。

2 Kad网络的联合污染模型

根据前述Kad网络污染的基本原理，本文提出了一种Kad网络的联合污染模型，模型同时考虑了Kad网络中关键词污染与文件源污染对查询结果带来的影响。模型从用户的角度进行建模，通过模拟用户在Kad查询过程中的状态转移来反映污染在Kad网络中的效果。

2.1 Kad网络受到污染时的状态转移分析

受到联合污染时，用户通过Kad网络查询资源的状态转移情况如图1所示。在不同状态之间转移所需的时间被标注在连接状态的线条上，没有标注数字的线条代表两个状态之间的转换时间可以忽略不计。

图1 受联合污染的Kad网络的户状态转移图

在状态S1，设用户到达Kad网络的到达率服从参数为λ的泊松分布。用户输入欲搜索文件的关键词，开始关键词信息查询。设查询成功的概率为Pc，查询到虚假关键词信息的概率为Pf，以概率Pc在T1个时间单位后转入状态S2；以概率Pf在T2个时间单位后转入状态S3；以概率1－Pc－Pf在T3个时间单位后转入状态S4。

在状态S2，用户的客户端获得关键词信息，并根据关键词信息查询文件源信息。设查询成功的概率为Pic，查询到虚假文件源信息的概率为Pif；以概率Pif在T4个时间单位后转入状态S5；以概率Pic在T5个时间单位后转入状态S6；以概率1－Pic－Pif在T6个时间单位后转入状态S7。

在状态S3，由于受到关键词污染的影响，用户的客户端获得虚假的关键词信息，并根据虚假的关键词信息查询对应的文件源信息，经过1个时间单位后转向状态S8。

在状态S4，由于关键词查询失败，用户的客户端将不显示任何与关键词相关的资源信息。设用户选择结束查询的概率为θ4，则以概率θ4转向状态S10；以概率1－θ4在1个时间单位后转向状态S1。

在状态S5，由于受到文件源污染的影响，用户的客户端获得虚假的文件源信息，并根据虚假的文件源信息查询资源提供者的地址信息，经过1个时间单位后转向状态S9。

在状态S6，文件源信息查询成功，用户的客户端获得资源提供者的地址信息，查询结束，转向状态S10。

在状态S7，文件源信息查询失败，用户的客户端会显示出资源的名称，但可用源数为0。由于Kad网络的查询是一个逐渐逼近目标节点的过程，可用源信息的显示可能会存在延迟，因此当可用源数为0时用户可能选择等待，也可能选择结束查询或重新查询。设用户选择等待的概率为ω7，选择退出查询的概率为θ7，则用户选择结束查询，转向状态S10的概率为θ7；选择重新查询，以概率1－ω7－θ7在1个时间单位后转向状态S1；选择等待，1个时间单位后用户停留在状态S7的概率为ω7。

在状态S8，由于根据虚假的关键词信息无法查询到正确的文件源信息中间节点，用户的客户端将不显示任何资源信息，设用户选择结束查询的概率为θ8，则以概率θ8转向状态S10；以概率1－θ8在1个时间单位后转向状态S1。

在状态S9，由于获得的资源提供者地址信息是虚假的，用户所在的客户端无法与正确的资源提供者建立连接。设用户选择继续等待建立起连接的概率为ω9，选择退出查询的概率为θ9，则用户选择结束查询，转向状态S10的概率为θ9；选择重新查询，以概率为1－ω9－θ9在1个时间单位后转向状态S1；选择等待，1个时间单位后用户停留在状态S9的概率为ω9。

2.2 模型的数学表示

设Xn（t）为t时刻状态Sn的用户数，Ys（t）与Yb（t）分别为t时刻通过Kad网络查询资源成功与失败的用户数，根据马尔可夫链的知识，得到联合污染模型的数学表达式为：

X1（t）（1－θ7－ω7）・X7（t－1）+（1－θ4）・

X4（t－1）+（1－θ8）・X8（t－1）+

（1－θ9－ω9）・X9（t－1）+λ（1）

X2（t）Pc・X1（t－T1）（2）

X3（t）Pf・X1（t－T2）（3）

X4（t）（1－Pc－Pf）・X1（t－T3）（4）

X5（t）Pif・X2（t－T4）（5）

X6（t）Pic・X2（t－T5）（6）

X7（t）（1－Pic－Pif）・X2（t－T6）+ω7・X7（t－1）（7）

X8（t）X3（t－1） （8）

X9（t）X5（t－1）+ω9・X9（t－1）（9）

Ys（t）X6（t）（10）

Yf（t）X5（t）+X3（t）（11）

3 模型的仿真

实验的硬件环境为：3.0GHz Intel 奔腾4处理器，1GB内存，80GB硬盘。实验的软件环境为：Windows XP SP3，Matlab 7.0，Visual C++ 6.0。实验的默认设置为：T1T2T3T4T5T610，λ100，实验迭代的次数为500次，即实验模拟的时间长度为500个时间单位。

3.1 联合污染条件下的Kad查询效果

受到联合污染时，对于方程（1）～（11），令θ4θ7θ8θ90.2，ω7ω90.6，PcPic0.3，PfPif0.5。仿真结果如图2所示。在图2中，“有污染查询成功”和“有污染查询失败”分别是Ys（t）、Yf（t）随时间变化的值。对比“有污染查询失败”和“有污染查询成功”可知，在受到联合污染的影响时，Kad网络中查询失败的用户数远大于查询成功的用户数。由图2还可知在联合污染模型中，Kad网络内某个时刻查询成功的用户数与查询失败的用户数都将随着时间的增加趋向于稳定。对Ys（t）、Yf（t）作回归分析，得到的回归方程如下。

Ys（t）－0.0060t2+0.6890t－4.8764

Yf（t）0.0004t3－0.0631t2+5.5480t－18.3700

3.2 污染程度对联合污染效果的影响

以用户查询到虚假关键词信息的概率Pf和查询到虚假文件源信息的概率Pif来反映Kad网络中的污染程度。对于方程（1）～（11），令θ4θ7θ8θ90.2，ω7ω90.6，Pic0.3，Pif0.5，Pc+Pf0.8，Pf的取值对联合污染效果的影响如图3（a）所示。令θ4θ7θ8θ90.2，ω7ω90.6，Pc0.3，Pf0.5，Pic+Pif0.8，Pif的取值对联合污染效果的影响如图3（b）所示。

图2 联合污染模型对查询结果的影响

图3 污染程度对联合污染效果的影响

由图3（a）可知，当Pif取固定值时，查询失败的用户数趋向的稳定值随着Pf的取值的增加而快速增加；由图3（b）可知，当Pf取固定值时，查询失败的用户数趋向的稳定值也随着Pif的取值的增加而增加，但是增加的速率要低于图3（a）中Pif取固定值，以Pf为变量的情况。这说明相对于文件源污染，关键词污染的程度对联合污染的效果影响更大。

3.3 退出率对联合污染效果的影响

退出率即用户选择结束查询的概率，反映在联合污染模型中为θ4、θ7、θ8、θ9这四个参数。对于方程（1）～（11），令ω7ω90.6，PcPic0.3，PfPif0.5，θ7θ8θ9

0.2，则θ4的取值对联合污染效果的影响如图4（a）所示。同理，当其他三个退出率的取值为0.2时，θ7、θ8、θ9的取值对联合污染效果的影响分别如图4（b）～（d）所示。由于分别受到ω7与ω9取值的影响，θ7与θ9的取值在0.01到0.39之间。由图4可知，随着退出率的增加，查询失败的用户数趋向的稳定值减少，这是由于停留在Kad网络中的资源请求者数量减少，导致查询失败的用户数随之减少引起的。在四个退出率参数中，θ8的取值变化对联合污染效果的影响最大――即因为受到关键词污染，无法找到正确的文件源信息中间节点而退出Kad网络的节点的退出率对联合污染效果的影响最大。

图4 退出率对联合污染效果的影响

3.4 等待率对联合污染效果的影响

等待率即用户选择停留在当前状态的概率，反映在联合污染模型中为参数ω7和ω9。对于方程（1）～（11），令PcPic0.3，PfPif0.5，θ4θ7θ8θ90.2。当ω9为0.6时，ω7的取值对联合污染效果的影响如图5（a）所示；当ω7为0.6时，ω9的取值对联合污染效果的影响如图5（b）所示。由图5可知，随着等待率的增加，Kad网络内查询失败的用户数趋向的稳定值减少，但是ω7取值的变化对污染效果的影响非常小，几乎可以忽略不计。此外，对比图3、4可知，ω7和ω9的取值对污染效果的影响要小于其他因素。因此，在联合污染模型中，等待率属于影响污染效果的次要因素。

3.5 仿真结论

实验表明，联合污染对Kad查询的控制从原理上是有效的，在影响联合污染效果的若干因素中，污染程度对联合污染的效果有决定性的影响，退出率的影响次之，等待率的影响最小。由此可见，提高污染效果的最好办法是提高关键词污染

和文件源污染的污染程度。

4 结语

本文介绍了针对Kad网络的P2P污染的基本原理，提出了一种Kad网络中的联合污染模型，该模型将关键词污染和文件源污染结合起来，综合评估两种污染对于Kad网络的污染效果。通过对模型的数学建模与仿真实验，证明了联合污染的有效性，并分析了模型中不同的因素对污染效果的影响。实验结果表明，Kad网络受到联合污染后，系统内能正常完成查询的节点数明显少于无法完成查询的节点数，从理论上讲联合污染是有效的。此外，在影响联合污染效果的若干因素中，污染程度对联合污染效果的影响最大。

在未来的工作中，联合污染模型将进行进一步完善，使其不仅能反映Kad网络的查询过程，也能反映节点之间的数据传输过程。此外，更加精确地描述模型中各个参数的取值范围也是有待进一步研究的内容。

图5 等待率对联合污染效果的影响

参考文献:

[1] MAYOUNKOV P, MAZIERES D. Kademlia: A peer-to-peer information system based on the XOR metric ［C］// IPTPS'01: Proceedings of the First International Workshop on Peer-to-Peer Systems. Berlin: Springer-Verlag, 2001: 53-65.

［2］ LIANG J, KUMAR R, XI Y, et al. Pollution in P2P file sharing systems ［C］// INFOCOM 2005: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE Press, 2005: 1174-1185.

［3］ DHUNGEL P, WU D, SCHONHORST B, et al. A measurement study of attacks on BitTorrent leechers ［C］// IPTPS'08: Proceedings of the 7th International Conference on Peer-to-Peer Systems. Berkeley, CA: USENIX Association, 2008: 7-7.

［4］ LIANG J, NAOUMOV N, ROSS K W. The index poisoning attack in P2P file sharing systems ［C］// INFOCOM 2006: Proceedings of the 25th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies. Piscataway, NJ: IEEE Press, 2006: 1-12.

［5］ 胡辛遥.对等网络污染的建模［D］.上海:上海交通大学,2008.

［6］ 左敏,李建华,蒋兴浩.P2P文件污染的建模与仿真分析［J］.上海交通大学学报,2008,42（2）:239-243.

［7］ 方群,吴国新,于坤,等.P2P文件污染的Markov生灭模型［J］.东南大学学报:自然科学版,2008,38（4）:593-597.

［8］ 方群.P2P文件污染随机模型［J］.小型微型计算机系统,2009,30（10）:1980-1984.

［9］ 云燕.P2P文件污染的传播建模分析和防治策略研究［D］.大连:大连理工大学,2008.

［10］ MAO JUNPENG, CUI YANLI, HUANG JIANHUA, et al. Analysis of pollution disseminating model of P2P network ［C］// Proceedings of the Second International Symposium on Intelligent Information Technology Application 2008. Washington, DC: IEEE Computer Society, 2010: 790-794.