基于二叉推荐树的可信评估模型

潘萍萍，程玉胜，龚尚福，陈小祥

（1.贵池职业教育中心，安徽池州 247100；2.安庆师范学院计算机与信息学院，安徽安庆 246133；3.西安科技大学计算机学院，陕西西安 710000；4.安庆职业技术学院电子信息系，安徽安庆 246003）

基于二叉推荐树的可信评估模型

潘萍萍1，3，程玉胜2，龚尚福3，陈小祥4

（1.贵池职业教育中心，安徽池州 247100；2.安庆师范学院计算机与信息学院，安徽安庆 246133；3.西安科技大学计算机学院，陕西西安 710000；4.安庆职业技术学院电子信息系，安徽安庆 246003）

在网络安全领域，可信被定义为一个实体期望另外一个实体执行某个特定动作的可能性大小。为了加强网络的安全性，允许某个结点去评估其他结点的可信性是非常重要的。本文主要讨论的是对可信事件的推荐评估。首先介绍了可信的相关概念和特性；接着，网络被抽象成一个有向图，在该图中，顶点代表实体或用户，边被看成可信关系，这样，评估过程可以看成是在有向图当中寻找最短路径问题，通过对影响推荐信任的因素分析，得到间接信任计算公式，为每个结点建立一个二叉推荐树，用来存储该结点能够推荐的结点以及这些结点推荐信任值，并在每个周期后动态地调整和整理该二叉推荐树；最后，对该模型的有效性进行了分析。

可信；可信评估；可信评估模型；二叉树

在网络安全领域，信任被定义为一个实体期望另外一个实体执行某个特定动作的可能性的大小［1］。可信对网络安全的影响是巨大的，表现在访问控制规则、公钥决策等方面。实体可以依照与之准备进行交互的客体的可信程度来决定是否与客体进行相互操作，文献［1］提出了用最可信的路径来代替路由选择当中的最短路径，依此来加强路由的安全性。随着公共密钥鉴定［2-6］、电子商务［7］以及P2P网络［8，9］等的飞速发展，不同领域的专家提出了各种不同的可信定义以及可信评估的方法。在这些方法中，有利用语义来描述可信的［3-10］，文献［11］提出了决策者可信管理系统，文献［12］提出了分布式可信模型，文献［13］提出了信任决策模型，而文献［14］则是基于公钥基础设施结构的。这些理论都是从语义上的可信概念及模糊逻辑出发来研究可信关系的。文献［4］认为可信度是［0，1］之间的数值来表示，文献［5］则通过三元组［0，1］3来表示，信任被分成了三类：可信、非可信、不确定，文献［12］则利用离散的整数来标识可信度，均用数值来表示可信度。另外，George Theodorakopoulos提出了基于半环的可信评估模型［15］，Yan Lindsay Sun提出了信息理论评估模型［16］，田俊峰教授提出了基于软件行为轨迹的可信性评价模型［17］，谢四江等提出了一种基于可信等级的安全互操作模型［18］。

在现有的工作中，普遍都认为间接信任跟两个因素相关：被推荐者对推荐者的信任度和推荐者对被推荐对象的推荐度，而没有考虑推荐者对被推荐者的信任度以及被推荐对象对推荐者的信任度，而这两者对于判定推荐者对被推荐对象的信任度的评估也是非常重要的，因为只要两者都相互信任时，才能更大程度地增强相互操作的效率。同时，也没有提出如何推荐以及怎样组织推荐。本文依据影响推荐信任的以上四个因素提出新的推荐信任度计算公式，并建立一个新的二叉推荐树模型。

1 可信的基本特征

可信关系可以分为两类：直接可信关系和间接可信关系。直接可信关系是通过实体之间的直接交互得到，而间接可信关系是通过中间结点的推荐来获得，例如结点A，C都跟结点B有直接可信关系，则A结点可以通过B结点得到对C的间接可信关系，由此可以看出可信具备传递性。

由于网络当中的结点众多，而众多的网络结点两两都是相互可达的，但是结点A对结点B的可信度较高并不能代表结点B对结点A的可信度也一样高，因而，我们把网络抽象成一个有向带权图，在此图中，结点表示用户或者实体，边表示实体之间的可信度，直接相邻的结点直接具备直接可信关系。那么，如何在两个没有直接可信关系的结点之间建立间接可信关系呢？当然需要中间结点的推荐，中间结点可根据自己的直接可信关系给出自己的推荐可信值。

由以上分析，可信具备如下基本特征：

1）可信度建立在两个将要发生某个行为的实体间。

2）不确定性。在某个时刻，可能可信关系的主体因为没有采集到足够的关于客体是否可信的相关信息，它对于客体是否可信是不确定的，因而可信是具备不确定性的。

3）可度量性。在研究当中，需要某个时刻主体对客体可信度的大小，此时可信度是可度量的。

4）相异性。主体对不同客体执行同一行为的可信值可能是不相同的。

5）不对称性。亦即在网络交互中主体A信任客体B的事实并不能得出主体B也相信客体A。

2 信任值的取得

定义1信任

前面已经提到可信指的是一个实体期望另外一个实体执行某个特定动作的可能性的大小。信任关系包括两个实体和一个特定的动作，用｛subject：agent，action｝来描述，信任度用T｛subject：agent，action｝来表示。

定义2可信区间

2.1 建立初始信任值

在网络初始状态下，每个结点都是通过直接可信关系与那些同自己相互操作的结点来建立可信关系，得出可信值的大小。可信值的大小可以通过结点之间相互操作的成功率来计算，例如，主体作为主动发生关系者同客体进行了N次交互，其中k次成功，则可以采用公式来计算主体A对客体B的直接信任度，依次对所有作为主体的结点进行该操作，可以得到网络当中的所有结点的直接可信关系。

2.2 影响信任度的因素

在实际网络中，由于主体A到客体B的路由有很多条，而在不同的路由当中，主体A对客体B的可信度是不一样的，可信度如何计算呢？在众多路由当中，哪条是最为可信的呢？亦即需要找到一个结点序列〈v0=A，v1，…，vk=B〉∶（vi，vi+1）∈E，0≤i≤k-1，使之在众多的路由当中具有最高的可信值，而这两个问题都是需要考虑的。

图1

首先看第一个问题，如图1所示，A是被推荐者，B是推荐者，C是被推荐对象，A跟B有直接相互操作关系，B跟C也有直接相互操作关系，若已知A对B的观点TAB，B对C的推荐观点RBC，如何得到A对C的信任观点？根据George Theodorakopoulos与John S.Baras的半环理论得到的计算公式如下

在此，没有考虑推荐者对被推荐者的信任度以及被推荐对象对推荐者的信任度，加入这两个因素，可以得到影响信任值的因素：

1）A对B的信任度TA→B

2）B对C的信任度TB→C

3）C对B的信任度TC→B

4）B对A的信任度TB→A

5）B对A给出的对C的推荐信任度RB→C

其中5）可由2）的值参考得到，可以看作一体，即RB→C=TB→C，因为推荐信任值就是推荐者对于被推荐对象的信任度。综上，得到新的求信任值的公式：

在此，有一个问题需要考虑，逆向信任值如何获得？可以通过与之相邻的结点的推荐值进行加权平均得到：其中Ci是与A相邻的可信邻接点，RCi→A是Ci对A给出的其认为B对A的推荐信任度。在实际计算中，采取如下方案：

再看第二个问题，在实际的网络当中，从A到B的路径可能不止一条，那么在这些路径当中取最可信的路径，在可信值相同的情况下，取经过中间结点个数最少的，如图2所示。

图2

其中Bi是从A到C的第i条路径的所有中间结点的集合，在可信值相同的情况下，取n（Bi）也就是中间结点个数最少的。在具体的计算公式当中，采用Yan Lindsay Sun的基于熵的方案：

3二叉树推荐策略

定义3操作成功指的是结点在规定的时间内按照期望值完成给定的任务。

定义4二叉树是由n（n≥0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

在以前的工作当中，都是需要推荐信任的时候，被推荐者才要求推荐者给出其对被推荐对象的推荐信任值，而推荐者则在收到每次要求之后都计算它对所有邻接点的信任度（也就是推荐信任度），额外增加了计算频度和时间的开销。基于以上原因，本文提出了一个基于二叉树的推荐模型，首先为每个结点建立一个推荐二叉树，在收到给出推荐的要求时，只需要在该二叉树当中找出当前推荐信任值最大的结点进行推荐即可，可以减少操作次数，大大减少收到要求后的反应时间。

3.1 二叉推荐树的建立

定义5二叉推荐树是由n（n≥0）个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右二子树组成，并且左右子树都是二叉推荐树。其结点的定义如下。

为每个结点都建立一个二叉推荐树，此树当中的每个结点都跟该结点有相互操作，即相邻的结点，也就是有直接信任，此树的构建如下：在所有的邻接点当中选择一个该结点当前最信任的结点作为根，对于其他的邻接点，信任值大于等于当前最高信任值的进入左子树，否则进入右子树，如此反复就建立了一个二叉树，树的根就是最信任的结点，在推荐中获得的权重最高，同样，左子树当中的结点比右子树的推荐权重高，如图3所示。

图3

其中，Ci为一个结点，也可为一棵二叉推荐树。

3.2 二叉推荐树的操作

在前面提过，信任随着时间的推移会发生变化，对于此树有四个基本操作：

1）升级：在某个结点的可信值升高时，为其在二叉推荐树当中找到合适的位置并记录之；

2）降级：在某个结点的可信值降低时，为其在二叉推荐树当中找到合适的位置，并存储；

3）新增：一个以前没有与该二叉树的所有者进行相互操作的结点现在跟所有者有了相互操作以后，根据该结点的当前可信值将之插入到二叉推荐树当中；

4）删除：在经过n个周期以后都没有与二叉推荐树的所有者进行操作的结点要在该二叉树中删除。

3.3 影响推荐信任度的因素

1）时间的推移。

2）交互操作次数，其中分为两类：相互操作的结点个数和交互操作的总次数。

3）交互操作的成功率。

在每个时间周期T0（T0为某个时间周期，用来循环计算推荐信任度的时间间隔，其值根据具体的网络进行调整）之后，该结点会依照上面的三个因素重新计算该树当中的信任度，并依据新计算的每个结点的信任度来整理该二叉推荐树，重新计算每个结点的信任度的公式如下

其中t表示总的操作次数，tsuc表示操作成功的次数，f（T）是时间衰减函数，定义如下

n的取值根据具体的网络情况而定。

第一阶段 专业的特色与定位。首先,基于本专业的标准,在充分调研分析的基础上确定本专业的特色与定位。教研室组织骨干教师组成核心团队,从培养方案、课程计划开始列出本专业培养目标。通过对教师、学生、校友、用人单位的调查,对本专业国内外发展趋势的分析修订本专业培养目标,将修订后的培养目标发给全系教师,然后召开全系教师会议再讨论确定本专业的培养目标,以专业培养目标为基础将本专业的培养目标细化为学生的学习结果,形成专业培养标准。

3.4 二叉推荐树的推荐原则

1）相邻原则，被推荐的对象都是二叉树的结点，当然都跟二叉树的拥有者相邻；

2）可信原则，如果一个结点的可信值在可信区间以下，那么该结点不获得推荐；

3）二叉树中最左的相邻结点获得推荐。

在推荐信任度一致的情况下，与相互操作结点个数多并且成功率高的结点获得推荐。

3.5 惩罚策略

同时，某个结点为了获得某个目标结点的信任，开始一直相互操作成功，等到完全获得了目标结点的信任之后，就开始从事恶意的行为，例如泄漏隐私的信息。为了防止这种情况的出现，在此提出一个惩罚策略，如果某个本来一直是可信的结点泄漏了涉及隐私的信息，那么这个结点就不再被信任，降级成不可信结点。

4 方案可行性分析

如果一个结点被推荐，那么必然是可信区间的某个左子树上的结点，即该结点是可信的、当前可推荐结点当中可信值是最高的，这样该推荐结点是有效的。如果某个结点没有被推荐，则该结点或者是不可信的或者不是当前推荐结点当中可信值最高的，那么该结点如果被推荐，就不是一个最优的推荐选择。

4.2 方案可行性分析

建立一棵二叉树之后，利用推荐二叉树的推荐原则进行推荐，随着结点之间相互操作次数的增多，该二叉树依据影响推荐信任度的因素来对该树进行动态地调整，使得可推荐的结点总是处于可信区间的左子树上。同时通过惩罚策略来对某些一直表现为可信结点的恶意结点在恶意行为表现出来以后降级为不可信结点，从而提高整个二叉树的推荐信任值。

4.3 方案效率分析

该方案的效率就是当二叉树进行更新时所需要的工作量，因为该方案都是对二叉树进行操作的，所以该工作量都同二叉树相关。假设该二叉树的结点数为n，深度为k，那么在一个结点需要调整的时候，只需要先找到该结点在该二叉树中的新位置，然后插入即可，所以整个操作都花费在查找新位置上，而对于二叉树的查找，其效率跟遍历二叉树相同，即O（n），所需的辅助空间为遍历过程中栈的最大容量，即树的深度，在最坏的情况下为n，则空间复杂度也为O（n）。

4.4 各种可信评估模型对比

本文采用的信任评估方法是半环理论模型算法，其算法是Dijkstra算法的扩展。由于半环理论采取的算法没有考虑初始信任值的获取问题，本文解决了该问题。

表1 二叉树推荐模型与其他方法的比较

从表1可以看出，二叉树推荐模型是在继承了半环理论模型和信息理论模型的算法基础上，综合了二者的优点，该模型改进了半环理论模型没有考虑如何取得初始可信值，以及如何推荐策略，改进了信息理论模型没有考虑逆向可信值问题，从而把整个网络看成是一个虚拟的人际信任网络。在这样的信任网络中，任何个体的可信度都不是绝对可靠的，但可以作为其他个体决定其交互行为的依据。

5 结束语

本文介绍了可信的相关概念和特性，将网络抽象成一个有向带权图，在该有向图中结点表示实体或者用户，边表示可信关系，这样，可信评估就被看成了在该有向图当中寻找最短路径问题。通过对影响推荐信任的因素的分析，得到间接信任的计算公式，为每个结点建立一个二叉推荐树，用来存储该结点能够推荐的结点，并在每个周期后动态地调整和整理该二叉推荐树，并验证分析了该模型的有效性。

［1］S.Marti，P.Ganesan，and H.Garcia-Molina.Sprout：P2P routing with social networks［M］.Stanford Univ.，Stanford，CA，Tech.Rep.，Jan.2004：1-19.

［2］M.K.Reiter and S.G.Stubblebine.Resilient authentication using path independence［J］.IEEE Transactions on Computers，1998，47（12）：1351–1362.

［3］W.Stallings.Protect Your Privacy（AGuide for PGPUsers）［S］. Prentice Hall，1995.

［4］U.Maurer.Modelling a public-key infrastructure［C］//in Proceedings1996 European Symposium on Research in Computer Security（ESORICS'96），volume1146 of Lecture Notes in Computer Science，1996：325–350.

［5］A.Jsang.An algebra for assessing trust in certification chains［C］//in Proceedings of the Network and Distributed Systems Security（NDSS'99）Symposium，1999.

［6］R.Levien and A.Aiken.Attack-resistant trustmetrics for public key certification［C］//in Proceedings of the 7th USENIX Security Symposium，January 1998：229–242.

［7］D.W.Manchala.Trustmetrics，models and protocols for electronic commerce transactions［C］//in Proceedings of the18th IEEE International Conference on Distributed Computing Systems，May 1998：312–321.

［8］S.D.Kamvar，M.T.Schlosser，and H.Garcia-Molina.The eigentrust algorithm for reputation management in p2p networks［C］//in Proceedings of 12th International World Wide Web Conferences，May 2003.

［9］R.Guha，R.Kumar，P.Raghavan，and A.T.Propagation of trust and distrust［C］.in Proceedings of International World Wide Web Conference，2004.

［10］P.R.Zimmermann.The Official PGP User's Guide［S］.MIT Press，1995.

［11］M.Blaze，J.Feigenbaum，and J.Lacy.Decentralized trustmanagement［J］.in Proceedings of the1996 IEEE Symposium on Security and Privacy，1996：164–173.

［12］A.Abdul-Rahman and S.Hailes.A distributed trust model［C］.in Proceedings of 1997 New Security Paradigms Workshop，ACMPress，1998：48–60.

［13］A.Herzberg，Y.Mass，J.Michaeli，D.Naor，and Y.Ravid. Access controlmeets public key infrastructure or：Assigning roles to strangers［C］//in Proceedings of the 2000 IEEE Symposium on Security and Privacy，2000：2-14.

［14］D.Clarke，J.-E.Elien，C.Ellison，et al.Certificate chain discovery in spki/sdsi［J］.Journal of Computer Security，2001，9（4）：285–322.

［15］George Theodorakopoulos and John S.Baras.On Trust Models and Trust Evaluation Metrics for Ad Hoc Networks［J］.IEEE Journal on Selected Areas in Communications，2006，24（2）：318-328.

［16］Yan Lindsay Sun，Wei Yu，Zhu Han，and K.J.Ray Liu.Information Theoretic Framework of Trust Modelling and Evaluation for Ad Hoc Networks［M］.IEEE Journal on Selected Area in Communications，2006，24（2）：305-317.

［17］田俊峰，韩金娥，杜瑞忠，等.基于软件行为轨迹的可信性评价模型［J］.计算机研究与发展，2012，07：1514-1524.

［18］谢四江，查雅行，迟亚平.一种基于可信等级的安全互操作模型［J］.计算机应用研究，2012，29（5）：1922-1926.

A Trust Evaluation Model Based on Bin-Recommended Tree

PAN Ping-ping1，3，CHENG Yu-sheng2，GONG Shang-fu3，CHEN Xiao-xiang4

（1.Vocational Education Center of Guichi，2.Department of Computer and Information，Anqing Teachers College，Anqing26133，China，3.Department of Computer，Xi'an University of Science and Technology，Xi′an 710000，China，4.Anqing Vocational and Technical College，Anqing246003，China）

In the field ofnetwork security，trust is defined as the possibilities an entity expecting another entity to perform a specific action；in order to strengthen the security of the network，itallows a node to evaluate the trust of the other nodes is very important.This article focuses on the trustof the event.First，we introduce relevant concepts and features of the trust.Then，the network ismodeled as a directed graph；the vertices represententities or users，while edge is seen as the trust.So，the evaluation process can be seen as the shortest path problem in a directed graph.Through the analysis of the recommendation trust factors，we give the indirect trust calculation formula，and for each node to create a binary recommended tree，which is used to store the node and can recommend these nodes recommendation trust value.After each cycle to dynamically adjust and organize the binary tree recommended，finally，the validity of themodel was analyzed.

trust，trust evaluation，trustmodel，binary tree

TP393

A

1007-4260（2014）03-0049-05

时间：2014-9-15 16：07 网络出版地址：http：//www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.013.html

2014-04-07

潘萍萍，女，安徽安庆人，贵池职业教育中心中学二级教师，研究方向为网络安全与可信计算。