一種基于深度優先的開放網絡可信路徑搜索方法

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

(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.