基于人工免疫的p2p文件共享防污染系统

1、基于人工免疫的P2P文件共享防污染系统摘 要：文件污染是当前P2P文件共享系统普遍存在的问题，极大的降低了系统的可用性。P2P文件共享系统和生物免疫系统一样，都是高度分布、自适应和自组织的。利用向量空间相似度赋予投票权重，采用自适应的信誉阈值判断文件可信性，建立了基于人工免疫的防污染对象信誉机制来进行邻居节点集的选取，以改进系统可用性。仿真实验表明，系统具有很高的识别精确度，能够以低通讯代价很好的抑制污染文件在网络中的传播。关键词：污染；人工免疫系统；可用性；文件共享；P2P引 言目前，P2P文件共享已经成为Internet上的主要应用之一，对Internet的使用和流量产生了巨大的影响。P2

2、P网络具有很多优良特性，但是它的分布性、开放性和自治性使它不可避免的遭遇安全问题的挑战，比如P2P文件共享系统中的文件污染问题。所谓文件污染问题，是指在P2P文件共享系统中，恶意用户发布与所标示主题不相符合的文件内容，并通过P2P文件共享进行传播。文件污染问题给P2P文件共享系统造成了很大的危害：首先，如果用户频繁遭遇污染文件，其感受到的可用性会急剧降低，甚至最终放弃使用该系统；而且，它为病毒、蠕虫等恶意程序的传播提供了便利，造成了网络安全上的隐患。对P2P网络的实际测量数据表明，现实存在的文件污染现象十分普遍，尤其是对于最近流行的内容。在FastTrack/KaZaA、eDonkey、Ove

3、rnet等P2P系统中，有半数流行内容的拷贝是被污染的或是伪造的12。作为一个高度进化的复杂系统，生物免疫系统能够区分外部有害物质和自身组织，从而清除病原并保持有机体的稳定。从计算的角度来看，生物免疫系统具有高度分布、自适应和自组织的特性，具备很强的学习、识别、记忆和特征提取能力。受到生物免疫系统的启发，人们提出了人工免疫系统（Artificial Immune System, AIS）的概念3。由于它提供了一种强大的信息处理和问题求解范式，近年来，基于免疫系统原理的各种模型和算法已经被广泛的应用在信息安全4、模式识别5、数据挖掘6、智能优化7等研究领域中。与生物免疫系统一样，P2P文件共享系

4、统也具有高度分布、自适应和自组织等特性。在P2P文件共享系统中，通过建立基于人工免疫原理的对象信誉机制，使用人工免疫方法进行邻居节点的选择过程，对候选的节点使用人工免疫算法进行筛选，选取出和本节点具有较高投票相似度的邻居节点，可以减少恶意节点传播污染文件的可能性，避免恶意节点的共谋攻击，从而提高文件共享系统的可用性。本文以下部分的结构为：第一部分介绍相关研究工作，第二部分描述对象信誉机制，第三部分提出基于人工免疫原理的邻居选择算法，第四部分进行仿真实验分析，最后总结本文并展望下一步工作。1. 相关研究工作抑制文件污染的方法有很多8，比如基于原始文件的方法、基于专家意见的方法、基于简单投票的方法

5、、基于信任关系的方法等。在基于简单投票方法的基础上，通过对历史行为的分析，某些专家节点被认为比其它节点更为可信，于是它们的投票就被赋予较大的权重，使用一个信誉系统来保存、更新和传播这些权重，然后结合投票来对文件的可信性进行评估。Credence系统9采用基于对象信誉的方法，节点通过gossip过程收集其它节点的投票，使用Pearson相关相似系数作为节点投票相似度的衡量标准，赋予其它节点的投票以权重，并对所收集的投票进行二次抽样。由于采用gossip过程，需要对投票逐一进行加密和解密验证，带来了很大开销，而且没有解决freeloading问题，也没有考虑到邻居节点的选取。XRep10和X2Re

6、p11系统都引入了对象信誉，并依据过去的投票行为赋予节点以权重，但是都没有在节点之间共享信誉信息，并且要求节点在评价阶段在线进行投票的计算和传播，不适合动态的P2P环境。在KaZaA12系统中，节点对自己所共享的文件给出评分，表示为四个级别的真实度。但是，系统是根据节点自己对所共享文件的评分来决定文件的信誉值，没有节点之间相互评分的机制，使信誉系统容易受到恶意节点的攻击。eMule和eDonkey网络通过Jugle real-time FakeCheck服务13来抑制文件污染，但是很容易受到暂时副本诱骗的攻击。在查询的返回结果中选取下载地址时，有的系统采用选取最佳返回结果的策略，容易受到恶意节

7、点的欺骗攻击。于是，很多系统采用随机选取返回结果的策略来抑制污染的传播，能够使可信文件的搜索结果随攻击者数目的增加呈线性下降，但是在污染程度很低的时候，却造成较大的性能损失14。大多数推荐系统中采用了相关的协同过滤技术，但是它们依赖于集中式的控制，不合适于具有分布特性的P2P系统。2. 对象信誉机制在P2P文件共享网络上，建立基于对象的信誉机制，从而抵御文件污染。这里的对象信誉，是指系统中所共享的文件对象的可信程度。在网络中的每个节点上存储两个哈希表，一个是投票箱(Ballot Box)，一个是相似度表(Similarity Table)。投票箱中的每一项对应着对某个文件的投票集，是一个子哈希

8、表，子哈希表中的每一项则对应着某个节点对该文件的投票。相似度表的每一项对应着本节点与某个节点的投票相似度，相似度值在-1,1之间，显然，每个节点与自身的相似度为1.0。2.1 初始化过程每个节点开始共享自己的文件时，对自己的每个文件进行投票。由于对文件受污染与否的判断结论是确定性的，不需要采用多等级的评定标准，同时为了能够表达中性的意见，采用最简单的奇数等级值，将评分分为-1,0,+1三个等级，其中，-1表示用户认为该文件为污染文件，+1表示用户认为该文件为可信文件，0表示用户没有进行评价。恶意节点为了使污染文件能够得到广泛的传播，会将对污染文件的投票值也设为+1。2.2 投票收集过程查询消息

9、可以被用来触发节点传播投票，在节点进行搜索的过程中，收到查询的节点除了要完成转发处理的任务，如果它对这个文件有投票，还要返回自己的投票给发起查询的节点，假设底层P2P网络的路由传输是安全可靠的，恶意节点不能够任意操控网络上传输的消息，所以发起查询的节点能够保证得到的这个投票是真实的。这个节点将收集到的投票加入投票箱中，然后进行相似度表的更新过程。2.3 相似度的计算在传统的人工免疫系统模型里，抗体和抗原的亲和力，一般是采用简单的Euclidean距离、Manhattan距离或Hamming距离等字符串距离或向量距离来表示的。在这里的对象信誉机制中，节点的投票相似度就是匹配特异性。对投票箱中存在

10、投票的每个文件，统计本节点和待评估节点的投票，计算两者的相似度，并记入相似度表中。相似度的计算，一般有相似距离和相似系数两类衡量方法，相比而言，后者更为精确的反映了数据之间的相似程度，其中包括Pearson相关相似系数、指数相似系数、向量空间相似系数等多种衡量标准。这里采用以向量夹角余弦表示的向量空间相似系数作为衡量标准来计算节点投票之间的相似度。(1)节点投票构成了K维文件对象空间上的向量，如果节点没有对某个文件进行评价，则相应分量为0。设节点ni和节点nj在K维文件对象空间上的投票值分别表示为K维向量和，则节点ni和节点nj之间的投票相似度为：其中，节点ni和nj共同投票的文件集合用Iij

11、表示，节点ni和nj投票的文件集合分别用Ii和Ij表示，Vi,k和Vj,k分别表示节点ni和nj对文件k的投票值。2.4 文件可信性的判定更新相似度表之后，在投票箱中查询对该文件的投票，在相似度表中查询相应投票节点与本节点的相似度，将投票值与相似度的乘积累加得到文件的信誉值estimate。当estimate超过某个阈值acceptThreshold时，接受这个文件；当estimate低于某个阈值rejectThreshold时，拒绝这个文件；介于两者之间，则以概率接受这个文件。一般来说，判断文件是否污染的信誉阈值有三种取值方案：全局阈值、多数阈值、本地阈值。全局阈值方案由全局共享一个固定的值

12、，不能够灵活取值；多数阈值方案由局部的大多数节点共同决定一个值，存在节点之间相互信任的问题。所以采用本地阈值方案，并且引入自适应的阈值取值方案。G(t)和P(t)分别表示在时刻t，系统中可信文件和污染文件的数目，则表示污染文件所占的比例，也就是污染文件的扩散程度。用户感知污染率表示用户在下载过程中遭遇污染文件的概率，h(t)和污染文件的扩散程度相关，表示相关程度的()是单调增函数。表示节点采用对象信誉机制时在处理一个可信文件时接受它的概率，表示节点采用对象信誉机制时在处理一个污染文件时拒绝它的概率。显然，和的值越接近1，系统的精确度越高。(2)在引入对象信誉机制之后，用户感知污染率由原来的h(

13、t)变为：H(t)的值用户可以通过统计得到。用户对衡量系统精确度的指标和的值并不知情，只能通过统计得到的用户感知污染率H(t)来评判当前的系统性能。当H(t)超过用户预期的值H时，同时提高acceptThreshold和rejectThreshold的值；当H(t)低于某个很小的值时，同时降低acceptThreshold和rejectThreshold的值。采用自适应的阈值取值方案，使得系统在网络动态变化的情况下，仍然能够保持和的值同时处于较高水平。3. 邻居选择算法通过不断调整P2P文件共享系统overlay网络的拓扑结构，可以增强普通节点的集聚性，而对恶意节点进行有效的屏蔽，从而减少恶意

14、节点传播污染文件的可能，提高文件共享系统的可用性。由于P2P网络的分布性特点，从单个节点的角度来看，可以采用有效的邻居选择算法，以达到这个目的。为了能够在网络节点中找到一个子集，作为自己的邻居节点，节点需要采用一种有效的邻居选择算法，如果仅仅选取与自身相似度最高的k个节点作为邻居，这样做并不能够选取出最具有潜力的良好节点来防止文件污染，而且容易遭到共谋攻击的威胁。生物免疫系统具有高度分布、自适应和自组织的特性。通过模仿自然生物免疫，建立人工免疫系统来进行节点的邻居选择过程，对候选的节点使用人工免疫算法进行筛选，选取出和本节点具有高相似度的邻居节点，同时，保持邻居节点的多样性，从而使系统达到很高

15、的集聚性。算法的伪代码如下所示：(1)AIS系统初始化；(2)将本地的投票信息编码为抗原Ag；(3)WHILE 还有候选节点存在(4)加入下一个候选节点；(5)将其投票信息编码为抗体Ab；(6)计算Ag与Ab的投票相似度；(7)计算Ab与其它抗体的投票相似度；(8)WHILE 邻居节点集合未满(9)执行浓度更新过程；(10)END WHILE(11)END WHILE其中，浓度更新过程的算法伪代码如下所示：(1)根据Ab与Ag的相似度提高Ab的浓度；(2)根据Ab与其它抗体的相似度降低Ab的浓度；(3)根据自然衰减常数降低Ab的浓度；(4)IF Ab的浓度大于某个阈值(5)将Ab加入到邻居集合

16、中；(6)ELSE(7)将Ab清除出候选集合；根据算法所描述的抗体浓度更新过程，得到抗体Ab的浓度变化满足以下微分方程式：其中，xi表示抗体Ab的浓度，y表示抗原Ag的浓度，xj表示其它抗体的浓度，N是其它抗体的个数，k1、k2、k3是相应的常数参数。方程式中的第一项表示抗体Ab的抗原刺激，它的强度与Ab和Ag的相似度mi成正比，第二项表示抗体被其它抗体识别时所受到的抑制，它的强度与Ab和其它抗体的相似度mij成正比，第三项表示抗体细胞没有受到刺激而自然衰亡的过程。4. 仿真实验分析4.1 实验场景通过在开源的P2P模拟器NeuroGrid Simulator15的基础上加入文件共享功能，使得

17、被搜索到的文件能够在网络中复制传播，然后根据前面描述的节点投票算法和人工免疫算法，实现基于人工免疫的对象信誉机制模块，来验证该机制抑制P2P系统中文件污染的能力。实验场景为模拟一个具有1000个节点和10000个初始文件对象(G(0)+P(0)=10000)的P2P文件共享网络，网络拓扑结构符合参数为(1.5, 1.0)的Power-law分布，节点上的文件分布和文件中的关键字分布都符合Zipf分布规律。网络中查询消息的TTL设为7，平均每个节点每天发起10次搜索，模拟进行10天(t=10)共发生100000次搜索。另外，系统中设置(x) = x，即用户感知污染率h(t)与污染文件的扩散程度p

18、(t)相同。节点角色分为三种：良好节点(Benign Peer)、恶意节点(Adversarial Peer)、搭便车节点(Freeriding Peer)。三种所占比例设为：BENIGN_RATE =80%，ADVERSARY_RATE=10%，FREERIDING_RATE=10%。4.2 实验结果很多P2P客户端将查询的结果按照所发现的文件拷贝数降序排列，这就产生了马太效应，用户更愿意选择拷贝数多的文件进行下载，而这又进一步增加了其拷贝数。所以系统初始状态对整个系统的精确度性能表现影响很大。在对比系统精确度时，设置两组参数：POLLUTION_RATE分别为10%和50%，模拟低污染率和

19、高污染率两种环境，其它实验中，设置POLLUTION_RATE为高污染率条件，即50%。图1 低污染率下对象识别的精确度 图2 高污染率下对象识别的精确度由实验结果图1和图2可见，在各种污染程度下，系统的精确度值（BenignPeers Beta）都能够达到90%以上，对搭便车节点的惩罚（Freeriders Beta）也随着污染程度的增加而变得更为严厉。在图1的低污染率条件下，搭便车节点利用系统所获得的识别精确度非常接近于良好节点；而在图2的高污染率条件下，搭便车节点利用系统所获得的识别精确度大大降低，搭便车节点几乎不能够从对象信誉机制中得到益处。从图3可以看到可信文件与污染文件传播速度的对

20、比，可信文件在系统中持续增长，而污染文件只是略有增加，两者的差距越来越悬殊，污染文件的传播受到了很大的抑制。4.3 收敛速度由于网络带宽和节点计算能力的限制，节点进行投票收集的范围是受限的，同时，人工免疫系统还处在初始阶段，因此系统在启动初期由于节点之间没有充分的共享投票信息，所以处于不稳定的状态，对象识别的精确度有一个收敛过程。通过实验结果图1和图2可以看出，该系统具有较短的学习曲线，虽然在初始启动阶段（小于Day2时）处于不稳定的抖动状态，但能够在较短时间内（在Day2附近）达到并保持稳定状态。采用带有有效期的路径缓存机制或是受控的更新传播方案可以带来收敛速度和性能的进一步改善。4.4 系

21、统开销对象信誉机制的引入会带来额外的开销，由于应用范围是文件共享系统，所以主要关注的性能指标是通信开销。从图4可以看到，额外的投票通信开销与搜索本身产生的开销相比起来很小（介于0.06%-0.11%），不会加重网络的负载。图3 可信文件与污染文件的传播 图4 对象信誉机制通信开销5. 结论与展望在P2P文件共享系统中，建立了基于人工免疫原理的对象信誉机制，使用人工免疫算法从候选节点中选取出和本节点具有较高投票相似度的节点作为邻居节点。在该系统中，通过计算节点之间投票向量的夹角余弦来衡量节点投票的相似性，并以此赋予投票权重，在判断文件可信性时运用自适应的信誉阈值。该系统以较低的开销有效的抑制了污

22、染文件在文件共享网络中的传播扩散，避免了恶意节点的共谋攻击，提高了P2P文件共享系统的可用性。在下一步的工作中，希望建立动态自适应的邻居选择算法以进一步优化拓扑结构；利用文件的流行度信息，针对易受污染的热门文件进行投票，以降低系统开销；另外，研究如何利用兴趣类聚提高网络的集聚度也是下一步的工作。参考文献：1 J. Liang, R. Kumar, Y. Xi, et al. Pollution in P2P File Sharing Systems. Proceedings of IEEE Infocom 2005, Miami, FL, USA, March 2005.2 J. Liang,

23、 N. Naoumov, K.W. Ross. The Index Poisoning Attack in P2P File-Sharing Systems. Proceedings of IEEE Infocom 2006, Barcelona, Spain, April 2006.3 Dasgupta D, Attoh-Okine N. Immunity based systems: A survey. Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Orlando, Florid

24、a, 1997. 369374.4 Kim J, Bentley P. Towards an artificial immune system for network intrusion detection: An investigation of clonal selection with a negative selection operator. Proceedings of Congress on Evolutionary Computation, Seoul, Korea, 2001. 2730.5 Carter J H. The immune system as a model f

25、or pattern recognition and classification. Journal of the American Medical Informatics Association, 2000, 7(3):2841.6 Timmis J, Neal M. A resource limited artificial immune system for data analysis. Knowledge Based Systems, 2001, 14(3-4):121130.7 Chun J S, Lim J P, Jung H K. Optimal design of synchr

26、onous motor with parameter correction using immune algorithm. IEEE Transaction on Energy Conversion, 1999, 14(3):610615.8 Neil Daswani, Hector Garcia-Molina, Beverly Yang. Open Problems in Data-Sharing Peer-to-Peer Systems. Proceedings of the 9th International Conference on Database Theory, January

27、08-10, 2003. 115.9 K. Walsh, E. G. Sirer. Experience with an Object Reputation System for Peer-to-Peer Filesharing. Proceedings of Symposium on Networked Systems Design and Implementation 2006, San Jose, USA, May 2006.10 E. Damiani, S.D.C. di Vimercati, S. Paraboschi, et al. A Reputation-Based Appro

28、ach for Choosing Reliable Resources in Peer-to-Peer Networks. Proceedings of ACM Conference on Computers and Communications Security, Washington, DC, USA, October 2002.11 N. Curtis, R. Safavi-Naini, W. Susilo. X2Rep: Enhanced Trust Semantics for the XRep Protocol. Proceedings of Applied Cryptography

29、 and Network Security, Yellow Mountain, China, June 2004.12 Kazaa. .13 Jugle real-time fake check for eMule and eDonkey. .14 D. Dumitriu, E. Knightly, A. Kuzmanovic, et al. Denial-of-service resilience in peer-to-peer file-sharing systems. Proceedings of ACM Sigmetrics 2005, Banff, Canada, June 2005.15 S. Joseph. An extendible o