分布式环境下信任路径选择性搜索及聚合研究

秦艳琳，吴晓平，高键鑫

（海军工程大学 信息安全系，湖北 武汉 430033）

1 引言

现今计算机为了达到资源共享及高使用率的目标，大都采用分布式的结构，即由多个软件服务组成的动态协作系统。地域分散的多个组织又通过Internet动态结盟构成一种大规模分布式网络计算环境，如当前流行的普适计算、P2P计算、网格、服务计算等。在这些计算环境中，节点拥有更多的自由,节点之间的交互也更加频繁和复杂。各主体往往隶属于不同的权威管理机构，拟交互主体很可能分布在陌生的网络环境中从而很难建立起一种信任关系。这就使得各类恶意节点能进入网络，提供欺骗服务，滥用网络资源，给合法用户造成不同程度的损失。在大规模分布式系统中引入信任机制的研究已经受到了重视，信任机制可以使节点在交互前评价对方的信任度，从而判定交互的安全性、可靠性，抵制恶意节点的攻击。

目前，国内外相关学者基于不同数学理论开展了适用于各种开放分布式网络系统中信任模型的研究，研究成果共同推动了信任建模理论的不断发展，但仍有一些问题没有得到很好的解决。

1) 目前基于信誉的信任模型在计算推荐节点的推荐可信度时方法不一，部分模型直接将推荐可信度等同于直接信任度，部分模型虽进一步细化了推荐可信度的影响因素，但并不完善；

2) 现有的大多数信任模型仍建立在洪泛搜索结果的基础上讨论推荐信任的传递与聚合，部分模型虽考虑到洪泛搜索结果中信任路径的相互依赖问题，但都是对已搜索得到的推荐信任网络进行了简化或依赖关系消除，并未在搜索过程中直接实现信任路径的选择性搜索，造成搜索效率不高，难以避免恶意节点进入推荐信任网络，进而不利于推荐信任路径的高效合成。

针对上述问题，本文在分析邻居节点间推荐可信度影响因素的基础上，给出了新的推荐可信度随时间更新算法，进而提出了以邻居节点间推荐可信度、评分相似度、路径长度等作为控制条件的选择性推荐信任路径搜索策略，对搜索结果的聚合算法则采用了一种改进的D-S证据理论合成算法以有效处理冲突较大的推荐信息，得到更趋合理的合成结果。

论文第2节介绍了相关工作，第3节给出了具体的推荐可信度更新算法，讨论了一种推荐信任路径选择性搜索算法，并在搜索得到的推荐信任网络的基础上，结合一种改进的D-S证据合成方法给出了节点推荐信任度的聚合算法，第4节进行了仿真实验及实例分析，第5节对全文进行总结。

2 相关工作

在信任机制研究中,通常利用节点之间的交互经历来建立信任关系。当缺乏直接交互经历时,就需要使用来自第三方的推荐信息来建立推荐信任（信誉），这就需要对推荐者的推荐可信程度进行量化处理，各类信任模型提出各自不同的处理方法。

部分信任模型[1～3]直接将邻居节点间的直接信任度作为推荐可信度，事实上并不符合人类社会的认知规律，交互能力强仅代表该节点执行某些动作的能力较强，并不完全代表该节点在为其他节点提供推荐信息时的诚信度更高，也即可能出现交互能力很强却为其邻居提供虚假信息的情况。文献[4]提出了一个针对恶意推荐者的信任模型，针对服务节点所提供的文件来评价其推荐的可靠程度。文献[5]定义了可疑交易来识别虚假反馈。文献[6]提出了一种区分服务信任与反馈信任的概率信任获取方法，增强了信任模型抵抗恶意实体策略行为攻击的能力。

文献[7]提出推荐可信度由请求节点与反馈节点的交易密度因子和评分相似度共同决定，该方法未考虑反馈节点的诚实性，具有一定的片面性。文献[8]又对上述方法进行了改进，提出推荐节点的推荐可信度由评分相似度和交易差异因子共同决定，但交易差异度因子利用推荐节点及请求节点对目标节点直接信任度的差值来刻画，而在大多数情况下只有当请求节点对目标节点的直接经验不足时，才会搜集其他节点的推荐信任，因此得出的交易差异度因子也缺乏依据。

文献[9]引入了更新幅度和更新力度2个参数来更新推荐可信度，并通过考察请求节点与推荐节点间的评价差异（由二者对目标节点的直接信任偏差和评价相似度共同决定）来决定推荐可信度的增减，在请求节点对目标节点的直接交互经验不足时并不能公正的对推荐节点的推荐可信度进行奖惩。

文献[10]用成功推荐次数对推荐总次数的比率来刻画节点反馈可信度，没有考虑反馈可信度随时间衰减情况且对虚假推荐的惩罚力度不够。

在信任传递与聚合研究方面，部分文献[10～17]仍建立在洪泛搜索的基础上对推荐信任网络进行分析聚合。

文献[10]研究了证据信任模型中的信任传递和聚合，基于图论对信任网络中相互依赖路径进行了消除，并采用证据合成规则对消除依赖路径后的信任子图进行信任聚合。但该模型也是建立在洪泛搜索结果的基础上，在信任路径搜索效率上并未提高且搜索结果中包含各类恶意节点，导致证据冲突量大，合成结果可能与实际情况不符。

文献[15]提出一种传递信任网络分析方法，通过分裂洪泛搜索得到的信任图中引发信任路径间依赖关系的边和节点来获得规范信任图，也即各条信任链相互独立的信任网络。

文献[17]基于洪泛搜索结果将信任网中推荐链的依赖关系分为无依赖关系与依赖关系，依赖关系又分为部分依赖与完全依赖，并给出了相应的解决策略。

文献[18]提出基于多影响因素的网格信任传播算法，对节点的交互能力和诚实能力进行了区分，但并未给出节点诚实能力的具体刻画方法，搜索算法对大量相互依赖的搜索路径未加取舍，导致算法效率不高且搜索结果存在大量冗余信息。

为此，本文在给出新的推荐可信度更新算法的基础上提出了一种选择性推荐信任路径搜索策略，该搜索策略符合人类的心理认知习惯，贴近人类社会信任网络的形成机理，能直接在搜索过程中规避恶意节点，停止对蕴含冗余信息的推荐路径的搜索，搜索得到的推荐信任网络可直接进行推荐信任的聚合运算。聚合算法采用了改进的D-S证据理论合成算法，在一定程度上削弱了信任网络中少量伪装节点不实推荐的影响。

3 一种新的信任路径选择性搜索策略及聚合算法

3.1 基本概念

定义1 大规模分布式网络环境下，信任是关于各对等节点安全、可靠、高效且低风险的执行某种特定动作的可能性的主观测度和预期，其主要由2部分组成，即直接信任度与推荐信任度。

定义2 推荐可信度是节点i对其推荐节点j提供的推荐信息的信赖程度，记为ijCr。

定义3 推荐吻合度rji表示某一时间段tΔ内j向i提供的关于目标节点O的推荐信息与i与O最终交互结果的吻合程度，规定j向i提供的关于O的推荐信任度较高（较低），而i与O交互成功（失败），则本次推荐为吻合推荐，否则为不吻合推荐，推荐吻合度可定义为

定义4 交互成功率r′ij为时间段tΔ内节点i与节点j之间进行直接交互的成功次数与总次数的比率，即

3.2 推荐可信度更新算法

本文对邻居节点间的推荐可信度进行了全面分析，引入了时间衰减因子，推荐吻合度因子及交互成功率因子对邻居节点间的推荐可信度进行更新：

1) 推荐可信度随时间动态变化，节点将更加关注其邻居推荐节点近期的行为；

2) 推荐可信度应随诚实的推荐行为提高而随着虚假的推荐行为降低，且诚实的推荐行为使得推荐可信度增加缓慢而虚假的推荐行为使得推荐可信度急剧下降；

3) 推荐可信度也在一定程度上与两邻居节点间的直接交互经验相关（这符合人类社会的认知规律，即人们往往倾向于接受与自己交往密切且行为能力较强的人的推荐信息）。为简化推荐可信度的更新算法，上述算法中未考虑邻居节点间的评价相似度因子，而直接将该因子作为下文信任路径搜索算法的控制条件之一。

3.3 推荐信任路径选择性搜索算法

首先，对按照文献[19]中的方法搜索得到的信任网络中的信任路径，如图1所示，进行分析以确定相互依赖路径的取舍。

图1 请求节点S与目标节点O间的推荐信任网络

图1中存在相互独立的推荐信任路径，如S→B→E→F→O与S→G→H→O，同时存在大量相互依赖的信任路径，如S→A→D→O与S→B→C→D→O，S→B→G→H→O与S→G→H→O等。在这些相互依赖的信任路径中，有相当一部分推荐路径蕴含冗余信息，可在搜索过程中舍弃而不影响最终对目标节点推荐信任的评判。下面将对信任网络中相互依赖的路径进行分析，以决定相关路径的取舍。

1) S→I→J→O与S→K→J→O，经由2条路径向S反馈的推荐信息均为节点J关于目标节点O的直接交互经验，但S对J提供的关于目标节点O的推荐信息的信赖程度将由两条路径共同决定，因此2条信任路径对目标节点的推荐信任度计算存在同等重要的价值。同理，S→B→C→F→O、S→B→E→F→O与S→G→E→F→O 3条路径同时搜索也是必要的。

2) S→G→H→O、S→B→G→H→O与S→I→G→H→O，按照人类社会的认知规律，S将直接采纳其邻居节点G提供的来自于H关于目标节点O的推荐信息，而不会通过第三方即B或I搜集来自于G的相关信息，因此在推荐路径搜索过程中应停止对第2、3两条路径的搜索而直接进行第1条路径的搜索。类似的，S→G→H→O与S→G→E→H→O也应停止对第2条路径的搜索。

3）S→G→H→O与S→G→H→J→O，由于节点H与目标节点O有足够的直接交互经验，它将直接把关于O的推荐信息经由G反馈给S，而不需再向其邻居J请求关于O的推荐信息，因此搜索过程中应停止第2条路径的搜索。

4）S→B→C→D→O与S→B→C→F→O，2条路径虽然部分重合，但是S通过第1、2条路径得到的推荐信息分别来自于节点D及F对O的直接信任，因此2条路径的同时搜索是必要的。

在对推荐信任网络中相互依赖的路径进行详细分析后，将给出具体的推荐信任路径选择性搜索算法。

算法1 选择性信任路径搜索算法STPSA

每个节点预先计算其相邻节点的推荐可信度（按照式(1)计算）和评价相似度（按照文献[19]中的方法计算）并存储在本地。

输入：信任请求者Re，目标节点Ob， Re的相邻节点集合Neighbor(Re)

输出：信任路径集合Set(pathRe,Ob)

Info数据结构：

{上级节点标识向量p;

已发送节点标识集合rSet(R);

目标结点ob;

实际推荐节点对目标节点的直接信任度dt；

回传信息标识flag}

请求节点Re发送搜索信息算法STPSA1：

中间节点Mi以收到Info数据包为事件，处理此事件的算法为STPSA2。

STPSA2算法：

输入：上级节点发送信息Info1; 本节点Mi的相邻节点集合Neighbor(Mi)

输出：本节点发送信息Info2

图2为使用算法STPSA搜索得到的结果。

图2 使用本文搜索算法得到的推荐信任网络

3.4 基于改进D-S证据理论的信任路径合成算法

定义5 2节点间直接交互信任的识别框架Θ为集合{DT（交互信任）、﹁DT（交互不信任）}，Θ 的幂集2Θ为{Φ，{DT}，{﹁DT }，{DT,﹁DT}}。节点间的直接交互信任关系采用三元组{m({DT})，m({﹁DT })，m({DT,﹁DT})}描述，其中DT表示交互信任，﹁DT表示交互不信任，{DT,﹁DT}表示不能确定，且有m({DT})+m({﹁DT })+m({DT,﹁DT})=1。当前时刻节点i对j的直接信任关系可以表示为

定义6 推荐可信的识别框架Θ为集合{CR（推荐可信）、﹁CR（推荐不可信）}，Θ的幂集2Θ为{Φ ，{CR}，{﹁CR }，{CR,﹁CR}}。节点间的推荐可信关系采用三元组{m({CR})，m({﹁CR })，m({CR,﹁CR})}描述，其中CR表示推荐可信，﹁CR表示推荐不可信，{CR,﹁CR}表示不能确定，且有m({CR})+m({﹁CR })+m({CR,﹁CR})=1。当前时刻节点i对j的推荐可信关系可以表示为

3.4.1 S对各反馈节点推荐可信度的合成算法

由于请求节点S最终得到的推荐信息分别来自于目标节点O的邻居节点Wi(1≤i≤r（)图2中的D、F、H、J），把这些节点称为实际推荐节点。下面利用证据理论和搜索到的有效推荐信任路径合成实际推荐节点的推荐可信度。

文献[10]在采用证据理论融合多源推荐信息时，没有考虑证据之间存在冲突的情况，事实上在证据高冲突或完全冲突的情况下使用传统的证据合成方法会出现融合结果与实际情形不符或失效等问题。为此，本文采用以下方法对证据Ei(1≤i≤n)进行合成。

2) 根据Ki的大小对所有证据Ei进行编号，Ki最小的证据编号为L1，Ki最大的证据编号为LM，Ki相等或近似相等的证据编号相同。

3) 对具有相同编号Ls(1≤s≤M)的证据计算其间的冲突量，并按下式进行合成。

下面给出请求节点S对实际推荐节点Wi(1≤i≤r)推荐可信度的合成算法。

算法2 推荐可信度合成算法

算法中的“⊕”按照给出的改进后的证据合成算法进行运算，“⊗”按照下述规则进行运算。

若推荐信任路径为：A→B→C，则

3.4.2 S对目标节点O推荐信任度的合成算法

利用算法2得到S对各实际推荐节点Wi(1≤i≤r)的推荐可信关系后，即可合成S对目标节点O的推荐信任

4 实例及仿真分析

仿真实验使用QueryCycleSimulator模拟P2P环境下的文件共享应用,同时实现了本文模型、Eigen Trust及文献[10]中的信任模型。仿真环境设置如表1所示。

表1 仿真环境设置

假设网络中的节点依据行为表现分为以下几种。

1) 正常节点，该类节点无论在提供服务与对其他节点的推荐都是真实的；

2) 简单恶意节点（SM），始终提供恶意服务和恶意推荐的节点；

3) 策略恶意节点（TM），为掩盖自己的恶意行为，以较高概率(0.7)为其他节点提供可靠服务，同时以较低概率（0.3）对其他节点给出符合实际的评价；

4) 合谋节点（CM），合谋欺诈的SM、TM类恶意节点形成协同作弊的团体，每个节点竭力夸大同一团体内的同伙或同时贬低某些节点的信任度或伪造信任度；

5) 伪装节点（DM），某些节点在通过提供可靠服务和有效推荐得到高信任度后，对其恶意同伙做出虚假推荐或诋毁正常节点。

假设网络中恶意节点比例为[0.1～0.5]，仿真周期为100次，仿真次数为3次，实验结果取均值。成功交互是指请求节点从响应节点准确无误的下载到所需要的文件，否则为一次失败交互。成功交互率能够体现信任模型在抵制恶意节点攻击方面的能力强弱。图3、4、5、6分别显示仿真网络内存在SM，TM，CM和DM 4类恶意节点时，随着恶意节点比例变换，系统的成功交互率变化情况。

由图3可知，随着SM类恶意节点比例的增加，成功交互率均维持在一个较高的水平，这说明3种信任模型都能比较容易的识别此类恶意节点，而使用本文的信任路径搜索策略，直接将此类节点排除在信任网络之外，因此相较其他2类信任模型而言本文模型对该类恶意节点攻击的抵制能力更强。

图3 SM攻击下成功交互率对比

图4是随着TM类恶意节点比例变化3种信任模型下系统成功交互率的对比情况。由于EigenTrust方案将推荐可信度等同于直接信任，部分恶意推荐信息在信任度计算中被赋予较高权重，导致请求节点的误判率升高，系统成功交互率下降较快。文献[10]虽区分了直接信任与推荐可信度，但推荐可信度简单的用诚实推荐数占总推荐数的比例刻画，且信任模型建立在洪泛搜索的基础上，部分TM类节点进入推荐网络，其提供的恶意推荐在一定程度上被请求节点采纳，导致系统成功交互率的有所降低。本文模型提出的推荐可信度算法对节点不吻合推荐及提供虚假服务的惩罚力度远大于对吻合推荐及提供可靠服务的奖励力度，因此经过一段时间的仿真，TM类节点的推荐可信度将迅速降低，同时结合评价相似度的搜索控制条件，此类节点将在搜索过程中被排除在推荐信任网络之外，使系统不受此类节点虚假推荐的影响，进而维持较高的成功交互率。

图4 TM攻击下成功交互率对比

图5是仿真网络中存在CM类节点时系统成功交互率的对比情况。由于EigenTrust对此类恶意节点缺乏足够的识别与惩罚机制，造成系统成功交互率的下降。文献[10]中的信任模型通过多条推荐链之间依赖关系的消除与聚合，减轻了CM类节点提供的不实推荐的影响，但由于其推荐可信度刻画不细致等原因，使得成功交互率仍有一定程度的降低。本文模型的推荐可信度更新算法使合谋节点的推荐可信度迅速降低从而直接被排除在推荐信任网络之外，因此系统受CM类节点的虚假推荐的影响很小，能够保持较高的成功交互率。

图5 CM攻击下成功交互率对比

图6是3种信任模型下系统成功交互率随DM类节点比例增加的对比情况。可以看出，EigenTrust无法抵制此类恶意节点的攻击。文献[10]中的信任模型使用一般的证据合成方法对推荐信息进行合成，导致当部分伪装节点提供与其他诚实推荐节点冲突较大的虚假信息时，合成结果受影响较大，并且在伪装节点提供虚假推荐后对该节点的推荐可信度未采取及时的惩罚更新机制，从而使系统成功交互率降低。本文使用改进的D-S证据理论合成方法，减轻了冲突信息对合成结果的影响，且推荐可信度更新算法中引入时间衰减因子和严格的惩罚因子，使得伪装节点在提供虚假推荐后，其推荐可信度迅速降低，从而很快被排除在推荐信任网络之外，进而使系统维持较高的成功交互率。

图6 DM攻击下成功交互率对比

通过下例也可以说明，伪装节点恶意推荐的影响在改进的证据理论合成过程中也被削弱。

可以看出，节点W2提供的推荐信息与W1、W3提供的推荐信息存在较大冲突（可能为伪装节点的不实推荐）。

结果表明，若使用一般的证据合成方法进行合成，则合成结果（即请求节点S对O的推荐信任）受W2提供的推荐信息的影响较大，可能产生误判。但是使用改进后的证据合成方法，将削弱W2提供推荐信息的影响，合成结果贴近W1与W3提供的推荐信息。

5 结束语

本文对大规模分布式网络环境中邻居节点间推荐可信度的影响因素进行了分析，给出了一种新的推荐可信度随时间更新算法，并在此基础上提出了以推荐可信度、评分相似度及路径长度等作为控制条件的选择性推荐信任路径搜索算法，该搜索算法能直接在搜索过程中规避恶意节点，停止对冗余路径的搜索同时保留对有价值的推荐路径的搜索，符合人类的心理认知习惯。本文采用了改进的D-S证据理论合成算法对搜索得到的推荐信任网络直接进行推荐信任的聚合运算。仿真实验和实例分析结果表明，本文模型克服了已有模型的部分局限性，增强了系统抵御各类恶意节点攻击的能力。

[1] KAMWAR S D, SCHLOSSER M T, HECTOR GARCIA-MOLINA.The eigentrust algorithm for reputation management in P2P networks[A]. Proceedings of the 12th International Conference on World Wide Web[C]. Budapest, Hungary, 2003. 640-651.

[2] 李小勇, 桂小林. 可信网络中基于多维决策属性的信任量化模型[J]. 计算机学报, 2009, 32(3):405-416.LI X Y, GUI X L. Trust quantitative model with multiple decision factors in trusted network[J]. Chinese Journal of Computers, 2009,32(3):405-416.

[3] 李小勇, 桂小林. 动态信任预测的认知模型[J]. 软件学报, 2010,21(1):163-176.LI X , GUI X L. Cognitive model of dynamic trust forecasting[J].Journal of Software, 2010, 21(1):163-176.

[4] LEE S Y , KOWN O H, KIM J, etal. Agents and Peer-to-Peer Computing[M] . Heidelberg : Springer , 2008. 111-122.

[5] MEKOUAR L, IRAQI Y, BOUTABA R. Detecting malicious peers in a reputation-based peer-to-peer system[EB/OL]. http://bcr2.uwaterloo.ca/ ～iraqi/Papers/Conferences/CCNC2005. pdf,2005.

[6] SWAMYNATHAN G, ZHAO B Y, KEVIN C, etal. Globally decoupled reputations for large distributed networks[J]. Advances in Multimedia,2007,(1):12-25.

[7] 胡建理, 吴泉源, 周斌.一种基于反馈可信度的分布式P2P信任模型[J]. 软件学报, 2009, 20(10): 2885-2898.HU J L, WU Q Y, ZHOU B. Robust feedback credibility-based distributed P2P Trust model[J]. Journal of Software, 2009, 20(10):2885-2898.

[8] 胡建理, 周斌, 吴泉源. P2P网络中具有激励机制的信任管理研究[J].通信学报, 2011,32(5):22-32.HU J L, ZHOU B, WU Q Y. Research on incentive mechanism integrated trust management for P2P networks[J].Journal on Communications, 2011, 32(5):22-32.

[9] 于真, 申贵成, 刘丙午等. 一种P2P网络信任模型METrust[J]. 电子学报, 2010,38(11):2600-2605.YU Z, SHEN G C, LIU B W, etal. METrust: a trust model in P2P networks[J].Chinese Journal of Electronics，2010, 38(11):2600-2605.

[10] 蒋黎明, 张琨, 徐建等. 证据信任模型中的信任传递与聚合研究[J].通信学报, 2011, 32(8):91-100.JIANG L M, ZHANG K, XU J, etal. Research on trust transitivity and aggregation in evidential trust model[J]. Journal on Communications,2011, 32(8):91-100.

[11] 张明武, 杨波, 禹勇. 基于D-S理论的分布式信任模型[J]. 武汉大学学报(理学版),2009,55(1):41-44.ZHANG M W, YANG B, YU Y. Distributed trust model based on D-S theory[J]. Journal of Wuhan University(Nat Sci Ed) ,2009, 55(1):41-44.

[12] CHEN H G, WU H F, CAO X, etal. Trust propagation and aggregation in wireless sensor networks[A]. Japan-China Joint Workshop on-Frontier of Computer Science and Technology[C]. Wuhan, China,2007.

[13] JØSANG A, GRAY E, KINATEDER M. Simplification and analysis of transitive trust networks[J]. Web Intelligence and Agent System,2006,4(2):139-161.

[14] YANG W Z, HUANG C H, etal.A general trust model based on trust algebra[A]. Proceedings of International Conference on Multimedia Information Networking and Security[C]. Wuhan,China,2007.

[15] JØSANG A. Optimal trust networks anaysis with subjectivelogic[A].The Second International Conference on EmergingSecurity Information, Systems and Technologies[C]. France, 2008.

[16] CHEN Y X, ZHANG M, ZHU H, etal. Average transitive trustworthy degrees for trustworthy networks [A]. Proceedings of the 4th InternationalConference on Rough Sets and Knowledge Technology[C].Gold Coast, Australia,2009.

[17] 苏锦钿, 郭荷清, 高英. 基于信任网的推荐机制[J]. 华南理工大学学报(自然科学版)，2008，36(4):98-103.SU J D, GUO H Q, GAO Y. Recommendation mechanism based on Web of trust[J]. Journal of South China University of Technology(Natural Science Edition), 2008, 36(4):98-103.

[18] 张琳, 王汝传, 王海艳. 基于多影响因素的网格信任传播算法[J].通信学报, 2011, 32(7):161-168.ZHANG L, WANG R C, WANG H Y. Trust transitivity algorithm based on multiple influencing factors for grid environment[J]. Journal on Communications, 2011, 32(7): 161-168.

[19] 苗光胜, 冯登国, 苏璞睿. P2P信任模型中基于行为相似度的共谋团体识别模型[J]. 通信学报, 2009, 30(8): 2-9.MIAO G S, FENG D G, SU P R. Colluding clique detector based on activity similarity in P2P trust model[J]. Journal on Communications,2009, 30(8): 2-9.