張 琳, 姜民明, 王汝傳, 王海艷

(1.南京郵電大學(xué)計算機(jī)學(xué)院,江蘇 南京 210003;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室,江蘇 南京210003;3.寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點實驗室,江蘇南京210003)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展,舊的封閉式的,流動性不強(qiáng)的網(wǎng)絡(luò)環(huán)境已經(jīng)不能滿足人們的日常需求,更加多元、開放的網(wǎng)絡(luò)環(huán)境隨之出現(xiàn)。網(wǎng)絡(luò)環(huán)境正從面向封閉的、熟識用戶群體和相對靜態(tài)的形式向開放的、公共可訪問的和動態(tài)協(xié)作的服務(wù)模式轉(zhuǎn)變。開放式的網(wǎng)絡(luò)主要運用分布式計算方式,如網(wǎng)格計算、P2P計算、無線傳感器網(wǎng)絡(luò)等。

開放網(wǎng)絡(luò)環(huán)境對安全提出了新的需求,傳統(tǒng)的安全機(jī)制,包括認(rèn)證[1]和授權(quán)[2]等,都在一定程度上預(yù)先默認(rèn)了實體間可信任關(guān)系的存在,面對開放、動態(tài)的網(wǎng)絡(luò)環(huán)境以及日益靈活多變的應(yīng)用需求,如何確保系統(tǒng)的可靠運行和可信利用,已成為實現(xiàn)可信網(wǎng)絡(luò)最終目標(biāo)亟待解決的關(guān)鍵問題。國內(nèi)外學(xué)者針對開放網(wǎng)絡(luò)環(huán)境下的信任模型已經(jīng)有了比較深入的研究[3-6],其中,信任傳播是一個關(guān)鍵部分。但多數(shù)模型只是對找到的信任傳播路徑如何進(jìn)行信任值的計算展開了研究,至于如何搜索可信的傳播路徑,目前的研究還不夠深入。文獻(xiàn)[7,8]給出的信任傳播算法就有如下不足：

(1)信任信息在傳遞的過程當(dāng)中沒有對節(jié)點的交互能力和誠實能力做出區(qū)分,直接把交互能力當(dāng)成誠實能力來參與傳播路徑信任值的計算;

(2)針對信任的傳播過程,考慮的影響因素不夠全面,比如,沒有考慮傳播路徑中是否出現(xiàn)了循環(huán)或稱死鎖現(xiàn)象;

(3)傳播算法描述的不夠詳細(xì)。如,算法中使用條件語句完成遞歸遍歷的結(jié)束,但結(jié)束具體代表什么含義文獻(xiàn)并未給出,這樣會讓讀者誤認(rèn)為只要找到一條傳播路徑不滿足遍歷的條件,程序就會結(jié)束,不再繼續(xù)遍歷下一條路徑。因此,該遞歸算法有可能會漏掉一部分合理的推薦路徑。

鑒于以上原因,設(shè)計了一種具體的可信路徑搜索方法,已經(jīng)應(yīng)用于南京郵電大學(xué)網(wǎng)格安全項目組開發(fā)的原型系統(tǒng)平臺上,測試結(jié)果驗證了方法的可行性以及信任搜索結(jié)果的完備性。

2 可信路徑搜索方法

2.1 方法思想

與現(xiàn)有的認(rèn)證和訪問控制等安全技術(shù)不同,信任機(jī)制是從主觀性出發(fā),根據(jù)網(wǎng)絡(luò)中各節(jié)點自身存儲的和其他節(jié)點交互的信任歷史經(jīng)驗信息,并在相應(yīng)的綜合計算策略下選擇出可以信賴的資源節(jié)點進(jìn)行作業(yè)的交互,其目標(biāo)是排除懷有欺騙意圖的惡意節(jié)點,輔助認(rèn)證和訪問控制等客觀安全技術(shù),在分布式環(huán)境下建立可信網(wǎng)絡(luò)。

在每個節(jié)點上都放置一個數(shù)據(jù)庫,來存放對自我做出決策有用的信任歷史信息,并在各節(jié)點上部署信任評估系統(tǒng),實現(xiàn)節(jié)點間信任信息的傳播與共享,進(jìn)而找到可信的節(jié)點并與之進(jìn)行作業(yè)的交互。信任評估器如圖1所示。

當(dāng)網(wǎng)絡(luò)中的某個節(jié)點作為信任請求者,需要計算其他節(jié)點的可信度從而篩選出信任值比較高的節(jié)點進(jìn)行交互。首先要考察自身存儲的信任信息,但當(dāng)自身信息不足,或想?yún)⒖紕e的節(jié)點對目標(biāo)節(jié)點的信任評價時,就需要通過熟人機(jī)制搜索可信的信任傳遞鏈,然后根據(jù)相關(guān)的算法計算出信任路徑推薦的信任值,最后提交給信任請求者進(jìn)行參考。文中重點研究可信路徑的搜索方法,致力于用較少的管理成本找出所有的符合條件的信任傳遞路徑。

圖1給出了搜索可信路徑的重要部件,每個節(jié)點的評估器都有兩個接口,其中消息接收器接收前一個推薦節(jié)點發(fā)送過來的消息1,借助本地的信任信息該節(jié)點對消息1進(jìn)行加工,形成消息2,然后由消息轉(zhuǎn)發(fā)器將消息2繼續(xù)傳播到下一個中間推薦者。

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

(1)cycle：信任傳播樹的層次。初始時信任搜索的層次為第1層,即,cycle=1。參考圖2所示的信任傳播樹,其中,節(jié)點a為信任請求者,a信任b,b信任c,這條信任鏈可以表達(dá)為a→b→c→…,同理還有a→c→…和a→c→…a→d→c→…。這樣,以 a為起點就形成了一個層次式的信任傳播樹。在搜索以某個節(jié)點為目標(biāo)的各傳遞路徑的時候,文章采用了深度優(yōu)先的路徑搜索方法,用cycle變量記錄遍歷的深度,默認(rèn)節(jié)點a所在的頂層為第一層,即 cycle=1,其他依次類推。

(2)reco-tr-value：信任傳遞過程中的推薦信任值。初始值reco-tr-value=1。

(3)reco-path：信任傳遞過程中的推薦路徑。初始值reco-path=信任請求者。

(4)thresh-honesty：推薦能力的上限值。當(dāng)某個推薦節(jié)點的推薦能力值大于上限值時,那么所有來自于該節(jié)點的關(guān)于目標(biāo)節(jié)點的推薦信任值都可看作是不可信的,即,推薦路徑是無效的。

(5)thresh-path：推薦路徑長度的上限值。當(dāng)某個推薦路徑的長度大于該值時,路徑無效。

(6)交互能力(accuracy)：反映了節(jié)點與其它節(jié)點進(jìn)行直接交互時完成作業(yè)的能力。

(7)誠實能力(honesty)：反映了節(jié)點作為中間推薦者在傳播路徑中向鄰近的下一個中間推薦者提供有關(guān)目標(biāo)節(jié)點信任信息的推薦誠實能力。在此,不考慮該節(jié)點作為目標(biāo)節(jié)點完成作業(yè)的能力,只考慮其推薦誠實能力。

當(dāng)消息接收器收到消息1后,根據(jù)自身存儲的信任信息找到熟人集合,逐一判斷這些熟人是否符合相關(guān)條件,從而決定信任路徑是否需要從熟人那里繼續(xù)往下層傳遞。比如,如果熟人的推薦能力很低,那么推薦路徑立刻中斷,不再繼續(xù)往下層搜索,但會退到上層繼續(xù)下條路徑的搜索。當(dāng)熟人滿足所有的判定條件時,路徑將接著熟人繼續(xù)往下層傳遞,消息處理器則對消息1進(jìn)行相關(guān)處理,如：cycle++;reco-path=reco-path+″←″+熟人;reco-tr-value=reco-tr-value×熟人的honesty值等。

2.2 細(xì)節(jié)設(shè)計

2.2.1 種能力的區(qū)分

在信任關(guān)系模型中,每個節(jié)點都有2種身份,既可以作為推薦節(jié)點,也可以作為作業(yè)的交互節(jié)點,這兩種節(jié)點在信任關(guān)系傳遞過程中的作用是完全不一樣的。

圖1 信任評估器結(jié)構(gòu)圖

作為推薦節(jié)點,只關(guān)心它的推薦誠實能力而不是其交互能力,比如,當(dāng)信任值傳遞到該節(jié)點處時,它可能會根據(jù)自己的主觀意愿故意抬高或貶低目標(biāo)節(jié)點的信任值,將其稱為惡意節(jié)點,這種現(xiàn)象在信任傳遞的過程中隨時都可能發(fā)生,將極大地影響信任傳遞的合理性和正確性。需要強(qiáng)調(diào)的是,當(dāng)稱某個節(jié)點是惡意節(jié)點時,并不是講它完成作業(yè)的能力很差。正如人類社會中,都是對同一個人做出的評價,評論這個人做事的能力很強(qiáng),以及評論這個人很誠實,雖然都來自于對這個人的直接認(rèn)識,但卻是完全不同的兩個概念。個人能力強(qiáng)并不代表人品很誠實,同樣,人品很差也并不代表做事的能力差。文中強(qiáng)調(diào)這兩種能力是每個節(jié)點必備的屬性,只不過在信任的傳播過程中,節(jié)點扮演的角色不一樣,被關(guān)注的屬性也不一樣。

作為目標(biāo)交互節(jié)點,只會關(guān)心它的交互能力而不是推薦誠實能力。目前的文獻(xiàn)對這兩種能力做出進(jìn)一步區(qū)分的不多,或者不夠突出,甚至混淆了二者的概念[7,8],將誠實能力用交互能力來代替?，F(xiàn)將對節(jié)點能力的描述進(jìn)行細(xì)化,明確的區(qū)分節(jié)點的交互能力和誠實能力,并將其貫穿到可信路徑的搜索過程中。

2.2.2 3個影響因素

影響一條推薦信任路徑是否為有效傳播路徑的因素很多,在篩選有效傳播路徑的過程當(dāng)中,考慮了3個因素：死鎖現(xiàn)象、推薦路徑的長度限值[7,8]、推薦節(jié)點的誠實限值[7,8]。

循環(huán)路徑：以推薦路徑 A←B←C←D為例,即,節(jié)點 A信任節(jié)點B,節(jié)點B信任節(jié)點C,節(jié)點C信任節(jié)點D。如果正在被搜索的節(jié)點為節(jié)點B,不難發(fā)現(xiàn)其已經(jīng)出現(xiàn)在推薦路徑中,若節(jié)點D也信任節(jié)點B,那么,會出現(xiàn)有新的推薦路徑為 A←B←C←D←B,此刻便出現(xiàn)了循環(huán),或者說搜索過程發(fā)生了“死鎖”,說明該節(jié)點B不可以再次被選為推薦節(jié)點,而該路徑則被評判為無效傳播路徑。

長度限值(Thresh-Path)：由于信任隨著推薦路徑的增長而有不同程度的衰減,所以對傳播路徑中中間推薦者的個數(shù)必須要有限值的要求,即,長度限值,當(dāng)推薦路徑的長度大于了長度限值,那么,該推薦路徑被判為無效路徑。

誠實限值(Thresh-Honesty)：推薦路徑如果為有效路徑,那么對各中間推薦者的誠實能力是有要求的,即,各推薦者的honesty值一定要大于誠實限值,否則,該節(jié)點不可作為中間推薦節(jié)點。

2.2.3 特殊位置的處理

以圖2的樹狀信任關(guān)系為例,節(jié)點a為信任請求者,b,c和d是他的熟人,同理,c,d和e是節(jié)點b的熟人。這樣,通過熟人的推薦,從a開始可以找到關(guān)于目標(biāo)節(jié)點的多條推薦路徑。

結(jié)合文中對可信路徑搜索提出的細(xì)粒度要求,可知,并不是所有的推薦路徑都是有效的。比如,a相信b是誠實的,但b對d的誠實度評判不高,即,b并不相信d提供的關(guān)于目標(biāo)節(jié)點的信任信息,則,在路徑的搜索過程中,由a到b再到d這條推薦路徑是無效的,當(dāng)程序遍歷到d時就不再往下層繼續(xù)遍歷。這時,程序面臨著兩種可能：(a)繼續(xù)廣度遍歷;(b)退到上一層繼續(xù)遍歷。具體選擇哪一種遍歷的方法視節(jié)點的特殊位置而定。

在圖2所示的信任傳遞路徑中,以節(jié)點b為例,他的熟人不止有一個,對這些熟人要做出明確的區(qū)分：最后一個熟人e;非最后一個熟人c和d。其中,最后一個熟人e就是一個特殊位置的節(jié)點。

當(dāng)路徑搜索到特殊位置的節(jié)點時,若該節(jié)點不滿足上文提到的3個影響因素時,路徑則被評判為無效路徑,程序?qū)?zhí)行(b)這種可能,退到上一層繼續(xù)遍歷,執(zhí)行：①reco-path去掉最后一個子字符;②Cycle=Cycle-1;③break推出循環(huán)。否則,節(jié)點為有效的中間推薦節(jié)點,執(zhí)行：①reco-path=reco-path+″←″+節(jié)點;②Cycle=Cycle+1;③調(diào)用遞歸算法。

當(dāng)路徑搜索到非特殊位置的節(jié)點時,若節(jié)點不滿足文中提到的3個影響因素,程序?qū)?zhí)行(a)這種可能,繼續(xù)廣度遍歷,執(zhí)行：continue操作而非break操作。否則,節(jié)點為有效的中間推薦節(jié)點,執(zhí)行上面類似的操作。

圖2 信任路徑的一個樹狀搜索范例

2.3 方法實現(xiàn)

針對主觀信任,其重要的特點是信任具有傳遞性。信任傳遞算法則致力于根據(jù)歷史交互記錄和熟人機(jī)制找到兩節(jié)點間所有有效的傳遞路徑,然后通過整合這些傳遞路徑和直接信任值便可得到目標(biāo)節(jié)點的可信值。

目前,討論信任傳遞算法的文獻(xiàn)并不多。下面將給出一種具體的傳遞方案,方法采用了遞歸的思想,通過將其應(yīng)用于校園網(wǎng)格安全平臺中,驗證了該方法的正確性及完備性。

具體的遞歸算法 Tr如下：

通過在校園網(wǎng)格安全平臺上的實際運行與測試,在一定程度上驗證了該方法的合理性、正確性和有效性。

3 實例分析

論文在可信路徑搜索過程中強(qiáng)調(diào)要對節(jié)點的能力進(jìn)行細(xì)粒度的劃分,即,區(qū)分節(jié)點的交互能力accuracy和誠實能力honesty,并基于此設(shè)計了遞歸的可信路徑搜索方法。以圖2為應(yīng)用實例,背景為開放網(wǎng)絡(luò)環(huán)境中的5個節(jié)點,他們彼此之間有過信任的交互經(jīng)驗,具體的信任狀態(tài)如表1所示。

表1 a對其他節(jié)點誠實能力的評判值

表2 a對各節(jié)點的最終信任值

為了突出3個影響因素對傳播算法的作用,對各節(jié)點的交互能力accuracy沒有過多要求,各節(jié)點的推薦能力以節(jié)點c為例,作為典型的不誠實節(jié)點,設(shè)其honesty=0.5。另外,模型中用到的其他變量不妨設(shè)長度限值Thresh-Path=4,誠實限值Thresh-Honesty=0.8。

將這些狀態(tài)和各參數(shù)值輸入給遞歸算法T r,可以找到以b、c、d、e分別為目標(biāo)節(jié)點的所有的有效推薦路徑,比如,節(jié)點a和c之間存在有4條有效的推薦路徑,a和d之間存在一條推薦路徑等。該方法已經(jīng)應(yīng)用于校園網(wǎng)格安全項目組的系統(tǒng)平臺上,經(jīng)驗證,平臺運行的推薦路徑搜索結(jié)果與人工找到的推薦路徑結(jié)果完全相同,這表明,方法所進(jìn)行的信任路徑的搜索是正確和可行的。

4 結(jié)束語

結(jié)合開放網(wǎng)絡(luò)環(huán)境對可信節(jié)點的能力進(jìn)行了細(xì)粒度的劃分,區(qū)分了節(jié)點的交互能力和誠實能力,并將其用于可信路徑的搜索過程中,增強(qiáng)了模型的合理性。結(jié)合深度優(yōu)先遍歷技術(shù),研究了可信路徑的搜索方案,其中考慮了影響可信傳遞的多種因素,包括循環(huán)路徑、路徑限長、推薦限值。通過仿真實驗證明該方法更加符合人類社會的思維習(xí)慣。

感謝南京郵電大學(xué)科研基金項目(NY20915);江蘇高校優(yōu)勢學(xué)科建設(shè)工程項目(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]鄧勇,陳建剛,王汝傳,張琳.網(wǎng)格計算環(huán)境的一種基于信任度的授權(quán)委托機(jī)制[J].通信學(xué)報,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]張琳,王汝傳,張永平.一種基于模糊集合的可用于網(wǎng)格環(huán)境的信任評估模型[J].電子學(xué)報,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].計算機(jī)學(xué)報,2010,21(6)：1341-1352.

[7]李小勇,桂小林.動態(tài)信任預(yù)測的認(rèn)知模型[J].軟件學(xué)報,2010,21(1)：163-176.

[8]李小勇,桂小林,趙娟,馮大鵬.一種可擴(kuò)展的反饋信任信息聚合算法[J].西安交通大學(xué)學(xué)報,2007,41(8)：879-883.