一种基于深度优先的开放网络可信路径搜索方法

张 琳, 姜民明, 王汝传, 王海艳

(1.南京邮电大学计算机学院,江苏 南京 210003;2.江苏省无线传感网高技术研究重点实验室,江苏 南京210003;3.宽带无线通信与传感网技术教育部重点实验室,江苏南京210003)

1 引言

随着互联网技术的快速发展,旧的封闭式的,流动性不强的网络环境已经不能满足人们的日常需求,更加多元、开放的网络环境随之出现。网络环境正从面向封闭的、熟识用户群体和相对静态的形式向开放的、公共可访问的和动态协作的服务模式转变。开放式的网络主要运用分布式计算方式,如网格计算、P2P计算、无线传感器网络等。

开放网络环境对安全提出了新的需求,传统的安全机制,包括认证[1]和授权[2]等,都在一定程度上预先默认了实体间可信任关系的存在,面对开放、动态的网络环境以及日益灵活多变的应用需求,如何确保系统的可靠运行和可信利用,已成为实现可信网络最终目标亟待解决的关键问题。国内外学者针对开放网络环境下的信任模型已经有了比较深入的研究[3-6],其中,信任传播是一个关键部分。但多数模型只是对找到的信任传播路径如何进行信任值的计算展开了研究,至于如何搜索可信的传播路径,目前的研究还不够深入。文献[7,8]给出的信任传播算法就有如下不足：

(1)信任信息在传递的过程当中没有对节点的交互能力和诚实能力做出区分,直接把交互能力当成诚实能力来参与传播路径信任值的计算;

(2)针对信任的传播过程,考虑的影响因素不够全面,比如,没有考虑传播路径中是否出现了循环或称死锁现象;

(3)传播算法描述的不够详细。如,算法中使用条件语句完成递归遍历的结束,但结束具体代表什么含义文献并未给出,这样会让读者误认为只要找到一条传播路径不满足遍历的条件,程序就会结束,不再继续遍历下一条路径。因此,该递归算法有可能会漏掉一部分合理的推荐路径。

鉴于以上原因,设计了一种具体的可信路径搜索方法,已经应用于南京邮电大学网格安全项目组开发的原型系统平台上,测试结果验证了方法的可行性以及信任搜索结果的完备性。

2 可信路径搜索方法

2.1 方法思想

与现有的认证和访问控制等安全技术不同,信任机制是从主观性出发,根据网络中各节点自身存储的和其他节点交互的信任历史经验信息,并在相应的综合计算策略下选择出可以信赖的资源节点进行作业的交互,其目标是排除怀有欺骗意图的恶意节点,辅助认证和访问控制等客观安全技术,在分布式环境下建立可信网络。

在每个节点上都放置一个数据库,来存放对自我做出决策有用的信任历史信息,并在各节点上部署信任评估系统,实现节点间信任信息的传播与共享,进而找到可信的节点并与之进行作业的交互。信任评估器如图1所示。

当网络中的某个节点作为信任请求者,需要计算其他节点的可信度从而筛选出信任值比较高的节点进行交互。首先要考察自身存储的信任信息,但当自身信息不足,或想参考别的节点对目标节点的信任评价时,就需要通过熟人机制搜索可信的信任传递链,然后根据相关的算法计算出信任路径推荐的信任值,最后提交给信任请求者进行参考。文中重点研究可信路径的搜索方法,致力于用较少的管理成本找出所有的符合条件的信任传递路径。

图1给出了搜索可信路径的重要部件,每个节点的评估器都有两个接口,其中消息接收器接收前一个推荐节点发送过来的消息1,借助本地的信任信息该节点对消息1进行加工,形成消息2,然后由消息转发器将消息2继续传播到下一个中间推荐者。

消息处理器的加工过程中涉及到的一些概念：

(1)cycle：信任传播树的层次。初始时信任搜索的层次为第1层,即,cycle=1。参考图2所示的信任传播树,其中,节点a为信任请求者,a信任b,b信任c,这条信任链可以表达为a→b→c→…,同理还有a→c→…和a→c→…a→d→c→…。这样,以 a为起点就形成了一个层次式的信任传播树。在搜索以某个节点为目标的各传递路径的时候,文章采用了深度优先的路径搜索方法,用cycle变量记录遍历的深度,默认节点a所在的顶层为第一层,即 cycle=1,其他依次类推。

(2)reco-tr-value：信任传递过程中的推荐信任值。初始值reco-tr-value=1。

(3)reco-path：信任传递过程中的推荐路径。初始值reco-path=信任请求者。

(4)thresh-honesty：推荐能力的上限值。当某个推荐节点的推荐能力值大于上限值时,那么所有来自于该节点的关于目标节点的推荐信任值都可看作是不可信的,即,推荐路径是无效的。

(5)thresh-path：推荐路径长度的上限值。当某个推荐路径的长度大于该值时,路径无效。

(6)交互能力(accuracy)：反映了节点与其它节点进行直接交互时完成作业的能力。

(7)诚实能力(honesty)：反映了节点作为中间推荐者在传播路径中向邻近的下一个中间推荐者提供有关目标节点信任信息的推荐诚实能力。在此,不考虑该节点作为目标节点完成作业的能力,只考虑其推荐诚实能力。

当消息接收器收到消息1后,根据自身存储的信任信息找到熟人集合,逐一判断这些熟人是否符合相关条件,从而决定信任路径是否需要从熟人那里继续往下层传递。比如,如果熟人的推荐能力很低,那么推荐路径立刻中断,不再继续往下层搜索,但会退到上层继续下条路径的搜索。当熟人满足所有的判定条件时,路径将接着熟人继续往下层传递,消息处理器则对消息1进行相关处理,如：cycle++;reco-path=reco-path+″←″+熟人;reco-tr-value=reco-tr-value×熟人的honesty值等。

2.2 细节设计

2.2.1 种能力的区分

在信任关系模型中,每个节点都有2种身份,既可以作为推荐节点,也可以作为作业的交互节点,这两种节点在信任关系传递过程中的作用是完全不一样的。

图1 信任评估器结构图

作为推荐节点,只关心它的推荐诚实能力而不是其交互能力,比如,当信任值传递到该节点处时,它可能会根据自己的主观意愿故意抬高或贬低目标节点的信任值,将其称为恶意节点,这种现象在信任传递的过程中随时都可能发生,将极大地影响信任传递的合理性和正确性。需要强调的是,当称某个节点是恶意节点时,并不是讲它完成作业的能力很差。正如人类社会中,都是对同一个人做出的评价,评论这个人做事的能力很强,以及评论这个人很诚实,虽然都来自于对这个人的直接认识,但却是完全不同的两个概念。个人能力强并不代表人品很诚实,同样,人品很差也并不代表做事的能力差。文中强调这两种能力是每个节点必备的属性,只不过在信任的传播过程中,节点扮演的角色不一样,被关注的属性也不一样。

作为目标交互节点,只会关心它的交互能力而不是推荐诚实能力。目前的文献对这两种能力做出进一步区分的不多,或者不够突出,甚至混淆了二者的概念[7,8],将诚实能力用交互能力来代替。现将对节点能力的描述进行细化,明确的区分节点的交互能力和诚实能力,并将其贯穿到可信路径的搜索过程中。

2.2.2 3个影响因素

影响一条推荐信任路径是否为有效传播路径的因素很多,在筛选有效传播路径的过程当中,考虑了3个因素：死锁现象、推荐路径的长度限值[7,8]、推荐节点的诚实限值[7,8]。

循环路径：以推荐路径 A←B←C←D为例,即,节点 A信任节点B,节点B信任节点C,节点C信任节点D。如果正在被搜索的节点为节点B,不难发现其已经出现在推荐路径中,若节点D也信任节点B,那么,会出现有新的推荐路径为 A←B←C←D←B,此刻便出现了循环,或者说搜索过程发生了“死锁”,说明该节点B不可以再次被选为推荐节点,而该路径则被评判为无效传播路径。

长度限值(Thresh-Path)：由于信任随着推荐路径的增长而有不同程度的衰减,所以对传播路径中中间推荐者的个数必须要有限值的要求,即,长度限值,当推荐路径的长度大于了长度限值,那么,该推荐路径被判为无效路径。

诚实限值(Thresh-Honesty)：推荐路径如果为有效路径,那么对各中间推荐者的诚实能力是有要求的,即,各推荐者的honesty值一定要大于诚实限值,否则,该节点不可作为中间推荐节点。

2.2.3 特殊位置的处理

以图2的树状信任关系为例,节点a为信任请求者,b,c和d是他的熟人,同理,c,d和e是节点b的熟人。这样,通过熟人的推荐,从a开始可以找到关于目标节点的多条推荐路径。

结合文中对可信路径搜索提出的细粒度要求,可知,并不是所有的推荐路径都是有效的。比如,a相信b是诚实的,但b对d的诚实度评判不高,即,b并不相信d提供的关于目标节点的信任信息,则,在路径的搜索过程中,由a到b再到d这条推荐路径是无效的,当程序遍历到d时就不再往下层继续遍历。这时,程序面临着两种可能：(a)继续广度遍历;(b)退到上一层继续遍历。具体选择哪一种遍历的方法视节点的特殊位置而定。

在图2所示的信任传递路径中,以节点b为例,他的熟人不止有一个,对这些熟人要做出明确的区分：最后一个熟人e;非最后一个熟人c和d。其中,最后一个熟人e就是一个特殊位置的节点。

当路径搜索到特殊位置的节点时,若该节点不满足上文提到的3个影响因素时,路径则被评判为无效路径,程序将执行(b)这种可能,退到上一层继续遍历,执行：①reco-path去掉最后一个子字符;②Cycle=Cycle-1;③break推出循环。否则,节点为有效的中间推荐节点,执行：①reco-path=reco-path+″←″+节点;②Cycle=Cycle+1;③调用递归算法。

当路径搜索到非特殊位置的节点时,若节点不满足文中提到的3个影响因素,程序将执行(a)这种可能,继续广度遍历,执行：continue操作而非break操作。否则,节点为有效的中间推荐节点,执行上面类似的操作。

图2 信任路径的一个树状搜索范例

2.3 方法实现

针对主观信任,其重要的特点是信任具有传递性。信任传递算法则致力于根据历史交互记录和熟人机制找到两节点间所有有效的传递路径,然后通过整合这些传递路径和直接信任值便可得到目标节点的可信值。

目前,讨论信任传递算法的文献并不多。下面将给出一种具体的传递方案,方法采用了递归的思想,通过将其应用于校园网格安全平台中,验证了该方法的正确性及完备性。

具体的递归算法 Tr如下：

通过在校园网格安全平台上的实际运行与测试,在一定程度上验证了该方法的合理性、正确性和有效性。

3 实例分析

论文在可信路径搜索过程中强调要对节点的能力进行细粒度的划分,即,区分节点的交互能力accuracy和诚实能力honesty,并基于此设计了递归的可信路径搜索方法。以图2为应用实例,背景为开放网络环境中的5个节点,他们彼此之间有过信任的交互经验,具体的信任状态如表1所示。

表1 a对其他节点诚实能力的评判值

表2 a对各节点的最终信任值

为了突出3个影响因素对传播算法的作用,对各节点的交互能力accuracy没有过多要求,各节点的推荐能力以节点c为例,作为典型的不诚实节点,设其honesty=0.5。另外,模型中用到的其他变量不妨设长度限值Thresh-Path=4,诚实限值Thresh-Honesty=0.8。

将这些状态和各参数值输入给递归算法T r,可以找到以b、c、d、e分别为目标节点的所有的有效推荐路径,比如,节点a和c之间存在有4条有效的推荐路径,a和d之间存在一条推荐路径等。该方法已经应用于校园网格安全项目组的系统平台上,经验证,平台运行的推荐路径搜索结果与人工找到的推荐路径结果完全相同,这表明,方法所进行的信任路径的搜索是正确和可行的。

4 结束语

结合开放网络环境对可信节点的能力进行了细粒度的划分,区分了节点的交互能力和诚实能力,并将其用于可信路径的搜索过程中,增强了模型的合理性。结合深度优先遍历技术,研究了可信路径的搜索方案,其中考虑了影响可信传递的多种因素,包括循环路径、路径限长、推荐限值。通过仿真实验证明该方法更加符合人类社会的思维习惯。

感谢南京邮电大学科研基金项目(NY20915);江苏高校优势学科建设工程项目(YX002001)对本文的资助。

[1]Wang Hai-yan,Wang Ru-chuan.CPK-based grid authentication：a step forward[J].The Journal of China U-niversities of Posts and Telecommunications,2007,14(1)：26-31.

[2]邓勇,陈建刚,王汝传,张琳.网格计算环境的一种基于信任度的授权委托机制[J].通信学报,2008,29(9)：10-17.

[3]SUN Yu-Xing,HUANG Song-Hua,CHEN Li-Jun.Bayesian Decision-Making Based Recommendation Trust Revision Model in Ad Hoc Networks[J].Journal of Software,2009,20(9)：2574-2586.

[4]张琳,王汝传,张永平.一种基于模糊集合的可用于网格环境的信任评估模型[J].电子学报,2008,36(5)：27-34.

[5]ZHANG Lin,WANG Ru-chuan,WANG Hai-yan.Trusted decision mechanism based on fuzzy logic for open network[J].Journal of Computers,2008,3(12)：76-83.

[6]王守信,张莉,李鹤松.一种基于云模型的主观信任评价方法[J].计算机学报,2010,21(6)：1341-1352.

[7]李小勇,桂小林.动态信任预测的认知模型[J].软件学报,2010,21(1)：163-176.

[8]李小勇,桂小林,赵娟,冯大鹏.一种可扩展的反馈信任信息聚合算法[J].西安交通大学学报,2007,41(8)：879-883.