秦艷琳,吳曉平,高鍵鑫
(海軍工程大學 信息安全系,湖北 武漢 430033)
現今計算機為了達到資源共享及高使用率的目標,大都采用分布式的結構,即由多個軟件服務組成的動態協作系統。地域分散的多個組織又通過Internet動態結盟構成一種大規模分布式網絡計算環境,如當前流行的普適計算、P2P計算、網格、服務計算等。在這些計算環境中,節點擁有更多的自由,節點之間的交互也更加頻繁和復雜。各主體往往隸屬于不同的權威管理機構,擬交互主體很可能分布在陌生的網絡環境中從而很難建立起一種信任關系。這就使得各類惡意節點能進入網絡,提供欺騙服務,濫用網絡資源,給合法用戶造成不同程度的損失。在大規模分布式系統中引入信任機制的研究已經受到了重視,信任機制可以使節點在交互前評價對方的信任度,從而判定交互的安全性、可靠性,抵制惡意節點的攻擊。
目前,國內外相關學者基于不同數學理論開展了適用于各種開放分布式網絡系統中信任模型的研究,研究成果共同推動了信任建模理論的不斷發展,但仍有一些問題沒有得到很好的解決。
1) 目前基于信譽的信任模型在計算推薦節點的推薦可信度時方法不一,部分模型直接將推薦可信度等同于直接信任度,部分模型雖進一步細化了推薦可信度的影響因素,但并不完善;
2) 現有的大多數信任模型仍建立在洪泛搜索結果的基礎上討論推薦信任的傳遞與聚合,部分模型雖考慮到洪泛搜索結果中信任路徑的相互依賴問題,但都是對已搜索得到的推薦信任網絡進行了簡化或依賴關系消除,并未在搜索過程中直接實現信任路徑的選擇性搜索,造成搜索效率不高,難以避免惡意節點進入推薦信任網絡,進而不利于推薦信任路徑的高效合成。
針對上述問題,本文在分析鄰居節點間推薦可信度影響因素的基礎上,給出了新的推薦可信度隨時間更新算法,進而提出了以鄰居節點間推薦可信度、評分相似度、路徑長度等作為控制條件的選擇性推薦信任路徑搜索策略,對搜索結果的聚合算法則采用了一種改進的D-S證據理論合成算法以有效處理沖突較大的推薦信息,得到更趨合理的合成結果。
論文第2節介紹了相關工作,第3節給出了具體的推薦可信度更新算法,討論了一種推薦信任路徑選擇性搜索算法,并在搜索得到的推薦信任網絡的基礎上,結合一種改進的D-S證據合成方法給出了節點推薦信任度的聚合算法,第4節進行了仿真實驗及實例分析,第5節對全文進行總結。
在信任機制研究中,通常利用節點之間的交互經歷來建立信任關系。當缺乏直接交互經歷時,就需要使用來自第三方的推薦信息來建立推薦信任(信譽),這就需要對推薦者的推薦可信程度進行量化處理,各類信任模型提出各自不同的處理方法。
部分信任模型[1~3]直接將鄰居節點間的直接信任度作為推薦可信度,事實上并不符合人類社會的認知規律,交互能力強僅代表該節點執行某些動作的能力較強,并不完全代表該節點在為其他節點提供推薦信息時的誠信度更高,也即可能出現交互能力很強卻為其鄰居提供虛假信息的情況。文獻[4]提出了一個針對惡意推薦者的信任模型,針對服務節點所提供的文件來評價其推薦的可靠程度。文獻[5]定義了可疑交易來識別虛假反饋。文獻[6]提出了一種區分服務信任與反饋信任的概率信任獲取方法,增強了信任模型抵抗惡意實體策略行為攻擊的能力。
文獻[7]提出推薦可信度由請求節點與反饋節點的交易密度因子和評分相似度共同決定,該方法未考慮反饋節點的誠實性,具有一定的片面性。文獻[8]又對上述方法進行了改進,提出推薦節點的推薦可信度由評分相似度和交易差異因子共同決定,但交易差異度因子利用推薦節點及請求節點對目標節點直接信任度的差值來刻畫,而在大多數情況下只有當請求節點對目標節點的直接經驗不足時,才會搜集其他節點的推薦信任,因此得出的交易差異度因子也缺乏依據。
文獻[9]引入了更新幅度和更新力度2個參數來更新推薦可信度,并通過考察請求節點與推薦節點間的評價差異(由二者對目標節點的直接信任偏差和評價相似度共同決定)來決定推薦可信度的增減,在請求節點對目標節點的直接交互經驗不足時并不能公正的對推薦節點的推薦可信度進行獎懲。
文獻[10]用成功推薦次數對推薦總次數的比率來刻畫節點反饋可信度,沒有考慮反饋可信度隨時間衰減情況且對虛假推薦的懲罰力度不夠。
在信任傳遞與聚合研究方面,部分文獻[10~17]仍建立在洪泛搜索的基礎上對推薦信任網絡進行分析聚合。
文獻[10]研究了證據信任模型中的信任傳遞和聚合,基于圖論對信任網絡中相互依賴路徑進行了消除,并采用證據合成規則對消除依賴路徑后的信任子圖進行信任聚合。但該模型也是建立在洪泛搜索結果的基礎上,在信任路徑搜索效率上并未提高且搜索結果中包含各類惡意節點,導致證據沖突量大,合成結果可能與實際情況不符。
文獻[15]提出一種傳遞信任網絡分析方法,通過分裂洪泛搜索得到的信任圖中引發信任路徑間依賴關系的邊和節點來獲得規范信任圖,也即各條信任鏈相互獨立的信任網絡。
文獻[17]基于洪泛搜索結果將信任網中推薦鏈的依賴關系分為無依賴關系與依賴關系,依賴關系又分為部分依賴與完全依賴,并給出了相應的解決策略。
文獻[18]提出基于多影響因素的網格信任傳播算法,對節點的交互能力和誠實能力進行了區分,但并未給出節點誠實能力的具體刻畫方法,搜索算法對大量相互依賴的搜索路徑未加取舍,導致算法效率不高且搜索結果存在大量冗余信息。
為此,本文在給出新的推薦可信度更新算法的基礎上提出了一種選擇性推薦信任路徑搜索策略,該搜索策略符合人類的心理認知習慣,貼近人類社會信任網絡的形成機理,能直接在搜索過程中規避惡意節點,停止對蘊含冗余信息的推薦路徑的搜索,搜索得到的推薦信任網絡可直接進行推薦信任的聚合運算。聚合算法采用了改進的D-S證據理論合成算法,在一定程度上削弱了信任網絡中少量偽裝節點不實推薦的影響。
定義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之間進行直接交互的成功次數與總次數的比率,即
本文對鄰居節點間的推薦可信度進行了全面分析,引入了時間衰減因子,推薦吻合度因子及交互成功率因子對鄰居節點間的推薦可信度進行更新:

1) 推薦可信度隨時間動態變化,節點將更加關注其鄰居推薦節點近期的行為;
2) 推薦可信度應隨誠實的推薦行為提高而隨著虛假的推薦行為降低,且誠實的推薦行為使得推薦可信度增加緩慢而虛假的推薦行為使得推薦可信度急劇下降;
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 使用本文搜索算法得到的推薦信任網絡
定義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的推薦信任


仿真實驗使用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提供的推薦信息。
本文對大規模分布式網絡環境中鄰居節點間推薦可信度的影響因素進行了分析,給出了一種新的推薦可信度隨時間更新算法,并在此基礎上提出了以推薦可信度、評分相似度及路徑長度等作為控制條件的選擇性推薦信任路徑搜索算法,該搜索算法能直接在搜索過程中規避惡意節點,停止對冗余路徑的搜索同時保留對有價值的推薦路徑的搜索,符合人類的心理認知習慣。本文采用了改進的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.