網(wǎng)構(gòu)軟件信任機(jī)制的形式化研究

董宇欣，印桂生，謝新強(qiáng)，馬志強(qiáng)

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

網(wǎng)構(gòu)軟件是一種新型軟件形態(tài)，它具有自主適應(yīng)性、協(xié)同性、反應(yīng)性、在線演化性、多態(tài)性等形態(tài)特征，是傳統(tǒng)軟件在開(kāi)放、動(dòng)態(tài)、多變的網(wǎng)絡(luò)環(huán)境下的延伸［1］.與傳統(tǒng)軟件形態(tài)不同，網(wǎng)構(gòu)軟件的出現(xiàn)使得Internet平臺(tái)上存在著大量的可重復(fù)利用的構(gòu)件資源.如何能夠充分利用這些構(gòu)件資源使其形成一個(gè)具有全面共享、自主協(xié)同的統(tǒng)一計(jì)算平臺(tái)，從而解決大規(guī)?？茖W(xué)和工程計(jì)算問(wèn)題［2］已成為網(wǎng)構(gòu)軟件技術(shù)面臨的重要挑戰(zhàn)之一.此外，由于網(wǎng)構(gòu)軟件系統(tǒng)的自組織特性，各類(lèi)復(fù)雜系統(tǒng)中應(yīng)用不同的信任管理機(jī)制，使得不同的應(yīng)用系統(tǒng)中對(duì)信任的形式化定義和理解也存在著不一致性.例如，Lampson等［3］提出的訪問(wèn)控制演算邏輯以及BAN邏輯給出了安全認(rèn)證協(xié)議的邏輯模型.Blaze等［4］提出了基于功能的靜態(tài)概念信任模型PolicyMaker.Maurer等［5］提出的PKI信任模型［6］.信任是主體間的一種關(guān)系，目前還沒(méi)有一個(gè)被廣泛接受的嚴(yán)格定義［7］.對(duì)于信任的理解和定義大多局限于自然語(yǔ)言的描述，缺乏嚴(yán)密的數(shù)學(xué)模型及形式化方法對(duì)信任關(guān)系進(jìn)行推導(dǎo)和量化.J?sang［8］認(rèn)為信任是主體間的一種信念，信念表達(dá)了對(duì)信任實(shí)體行為和表現(xiàn)的期望，信任實(shí)體具有感性和理性之分，因此信念的背后必然存在著某種推理.本文基于信念邏輯給出信念公式和信任關(guān)系的形式化定義、分析、邏輯推理及證明過(guò)程，并給出了信任鏈建立以及多路徑信任聚合的相關(guān)算法.

1 信念邏輯

假設(shè)信任關(guān)系模型采用五元組σ(ρ，α，η，κ，ν)表示，其中ρ表示構(gòu)件主體集合，α表示假設(shè)的屬性和不變量的集合，η表示主體的信念公式全集，信念強(qiáng)調(diào)的是主體根據(jù)自身知識(shí)和經(jīng)驗(yàn)對(duì)外部環(huán)境的一種邏輯判斷能力.κ表示主體ρ在α×η上的映射集合，表示主體的一個(gè)推理.ν是置信函數(shù)，ν(Qi，Qj)∈［0，1］，表示Qi對(duì)Qj的信任程度.φ表示命題符號(hào)，命題包含對(duì)信任主體的信任屬性、權(quán)限、性能指標(biāo)等特征的斷言.邏輯連接詞┐、∧、∨、?、∪、∩、→、|?優(yōu)先級(jí)依次遞減.|?表示信念關(guān)系推理符號(hào).

定義1(信念公式)對(duì)于?Q∈ρ，?R?κ，如果主體Q在集合R上可以推導(dǎo)出一個(gè)真命題φ，則稱存在信念公式(Q，R)|?φ.下面給出公式(Q，R)|?φ的如下遞歸定義:

1)如果φ是一個(gè)命題符號(hào)，則φ是原子公式.

2)如果φ是一個(gè)命題符號(hào)，則(Q，R)|?φ是一個(gè)信念公式.

3)如果η1、η2是信念公式，則邏輯運(yùn)算η1∧η2，η1∨η2，η1→η2，┐η也是信念公式.

定理1 對(duì)于主體Q在條件R上的一條信任斷言φi，如果(Q，R)|?φi成立，則必有φi∈κ成立，反之，如果φi∈κ，則(Q，R)|?φi成立.

證明:∵主體Q在條件R上存在信念φi，即(Q，R)|?φi成立，∴φi必然是Q的信念集合κ映射的一個(gè)子集.反之，當(dāng)φi∈κ成立時(shí)，∵κ表示主體ρ×α×η上的一個(gè)映射子集，∴主體Q必然能夠通過(guò)信念公式η推導(dǎo)出命題φi，顯然定理1成立.證畢.

推理1 對(duì)于一個(gè)命題φi∈κ，(Q，R)|?φi與κ(Q，R)?φi相互等價(jià)，即主體Q在條件R上存在信念φi，當(dāng)且僅當(dāng)從相應(yīng)的理論κ(Q，R)能夠推導(dǎo)出命題φi，κ(Q，R)表示主體Q的一個(gè)理論.

由推理1，對(duì)于φi∈κ，φj∈κ，可以得出如下推理的等價(jià)關(guān)系:

其中，?表示信念公式組合算子.

下面分別給出具體證明過(guò)程:

1)由推理1可知，(Q，R)|?φi?κ(Q，R)?φi，又∵(Q，R)|?(φi→φj)?κ(Q，R)?(φi→φj)，而κ(Q，R)?(φi→φj)?(κ(Q，R)?φi)→(κ(Q，R)?φj)?((Q，R)|?φi)→((Q，R)|?φj).證畢.

2)由推理1可知(Q，R)|?┐φi?κ(Q，R)?┐φi，而κ(Q，R)?┐φi?┐(κ(Q，R)?φi)?┐((Q，R)|?φi)，所以式(2)得證.

3)∵(Q，R)|?(φi∧φj)?κ(Q，R)?(φi∧φj)，κ(Q，R)?(φi∧φj)?(κ(Q，R)?φi)∧(κ(Q，R)?φj).又由推理1可得((κ(Q，R)?φi)∧(κ(Q，R)?φj)?((Q，R)|?φi)∧((Q，R)|?φj)，∴式(3)得證，同理式(4)、(5)、(6)可證.

2 信任關(guān)系形式化

根據(jù)ITU X.509對(duì)信任的自然語(yǔ)言描述為:“當(dāng)主體A假設(shè)主體B將嚴(yán)格按照其所期望的那樣行動(dòng)時(shí)，則稱A信任B”，也就是說(shuō)對(duì)于主體B在條件R下推導(dǎo)出的命題，即信念ηi為真，則主體A在條件R下推導(dǎo)出的ηi也為真，即A對(duì)于B的斷言是信任的，下面給出信任關(guān)系的形式化描述.

定義2 對(duì)于主體Qi在信念集合R上的一條斷言φi，如果主體Qj在信念集合R上推導(dǎo)出的斷言也是φi，則認(rèn)為主體Qj在信念集合R上對(duì)φi的斷言被主體Qi所信任，即如果(Qj，R)|?φi→(Qi，R) |?φi為真，則稱主體Qi信任主體Qj，記作Qi(R，φ)?Qj，其中?表示信任關(guān)系推導(dǎo)符號(hào).

信念強(qiáng)調(diào)的是主體的一種邏輯判斷，是從主觀上依據(jù)充分的證據(jù)得出的判斷，不同的主體由于所處的環(huán)境、自身的條件差異，往往一個(gè)主體對(duì)事物的判斷并不一定能被另一個(gè)主體所接受，因此信任鏈傳遞過(guò)程中必然存在著不同程度的損失.下面給出信任關(guān)系傳播過(guò)程的形式化描述:

推理2 如果?μ1?R，?μ2?R，使得Qi(μ1，φ)?Qj，并且Qi(μ2，φ)?Qj同時(shí)成立，則可以推出Qi(μ1?μ2，φ)?Qj，其中?為信念邏輯組合算子.推理2表明如果環(huán)境不變量對(duì)μ1、μ2同時(shí)成立，那么環(huán)境不變量對(duì)它們的組合也成立，μ1?μ2表示2個(gè)信任策略的組合，下面給出證明.

證明:由條件Qi(μ1，φ)?Qj，并根據(jù)定義2得: (Qj，μ1)|?φ→(Qi，μ1)|?φ，同理由Qi(μ2，φ)?Qj得:(Qj，μ2)|?φ→(Qi，μ2)|?φ，又由推理1的等價(jià)關(guān)系(6)可得:(Qj，μ1?μ2)|?φ→(Qi，μ1?μ2)|?φ，∴Qi(μ1?μ2，φ)?Qj成立.證畢.

推理2提供了一個(gè)對(duì)復(fù)雜信任策略分解和進(jìn)一步評(píng)估的途徑，構(gòu)件從外部獲得的信任存在組合與分解關(guān)系，而信任評(píng)估所面對(duì)的對(duì)象大多是具有復(fù)雜結(jié)構(gòu)的協(xié)議，不同的信任策略之間往往存在著多層次、多粒度的依賴和交互關(guān)系.

推理3 如果?φ1?R，?φ2?R，對(duì)于Qi、Qj、Qk，假設(shè)它們?yōu)椴煌臉?gòu)件主體，如果存在Qi(μ，φ1)?Qj，Qj(μ，φ2)?Qk同時(shí)成立，則可以推出Qi(μ，φ1∧φ2)?Qk成立.

證明:由條件Qi(μ，φ1)?Qj，并根據(jù)定義2可知:對(duì)?ε∈φ1，式(1):(Qj，μ)|?ε→(Qi，μ)|?ε成立，從而對(duì)于?ε∈(φ1∧φ2)，亦滿足公式1):(Qj，μ)|?ε→(Qi，μ)|?ε，同理，對(duì)于?~ω∈φ2，(Qk，μ) |?~ω→(Qj，μ)|?~ω成立，則?~ω(φ1∧φ2)，式(2): (Qk，μ)|?~ω→(Qj，μ)|?~ω顯然成立.∴由式(1)、(2)可知，?λ∈(~ω∧ε)?(φ1∧φ2)，使得(Qk，μ) |?λ→(Qi，μ)|?λ成立.又由定義2可知Qi(μ，λ)?Qk成立，即Qi(μ，φ1∧φ2)?Qk成立.證畢.

推理3細(xì)化了信任關(guān)系的分析粒度，給出了信任傳遞性成立的語(yǔ)義解釋和約束條件.例如，A信任B是針對(duì)命題q，B信任C是針對(duì)命題p，顯然不能認(rèn)為A信任C.下面給出信任傳遞的進(jìn)一步推導(dǎo)關(guān)系.

推理4 如果?φ?κ，?μ?R，對(duì)于公式Qi(μ，φ)?Qj，Qj(μ，φ)?Qk都成立，則Qi(μ，φ)?Qk成立.推理4表明當(dāng)Qi與Qj的信念公式集合μ及φ等價(jià)時(shí)，Qi對(duì)Qj的任何斷言都認(rèn)為是可信的，而Qi對(duì)Qk的信任則是通過(guò)Qj的直接推薦得到的.對(duì)推理4進(jìn)一步推廣可以得出信任鏈的定義.

推理5(信任鏈) 如果對(duì)于?φ?κ，?μ?R，Qi(μ，φ)?Qi+1，Qi+1(μ，φ)?Qi+2，…，Qn－1(μ，φ)?Qn同時(shí)成立，則可以推導(dǎo)出Qi(μ，φ)?Qn成立.

如圖1所示序列Qi，Qi+1，…，Qn－1，Qn為從主體Qi到Qn的一條信任鏈，虛線顯示了通過(guò)信任傳遞使得互不相連的主體間也能夠建立信任關(guān)系.構(gòu)件間信任關(guān)系的建立過(guò)程實(shí)際上也是信任鏈建立和傳播的過(guò)程，2個(gè)構(gòu)件節(jié)點(diǎn)之間往往存在著若干條信任鏈，如何選擇一條置信度較高的信任鏈作為構(gòu)件之間交互的通道顯得尤為重要，因此本文3.3節(jié)給出了一種基于貪心策略的最優(yōu)信任鏈計(jì)算方法的形式化描述.

圖1 信任鏈Fig.1 The trust chain

推理 6(信任聚合)如果?φ1，?φ2，?φ3，?φ4?κ，公式 Qi(μ，φ1)?Qj，Qj(μ，φ2)?Qk，Qi(μ，φ3)?Qt，Qt(μ，φ4)?Qk都成立，則可以得出Qi(μ，(φ1∧φ2)?(φ3∧φ4))?Qk，其中?表示多路徑信任聚合算子.

如圖2所示，虛線描述了從Qi到Qk所有可以選擇的路徑.Qi與Qk間存在著多條可達(dá)的信任路徑，通過(guò)多個(gè)路徑的聚合來(lái)計(jì)算Qi與Qk之間的置信度，3.3節(jié)將進(jìn)一步研究多路徑聚合問(wèn)題并給出了一種基于約束條件的多路徑聚合算法.

圖2 多路徑信任聚合Fig.2 The multiple path trust aggregation

3 信任關(guān)系建立的形式化描述

本節(jié)通過(guò)信任關(guān)系的形式化定義對(duì)PKI［9］信任模型進(jìn)行形式化描述和推演.

如圖3所示為橋CA結(jié)構(gòu)模型，采用BCA橋接方式互通3個(gè)不同的PKI域，即嚴(yán)格等級(jí)CA域、獨(dú)立CA域和網(wǎng)狀CA域，其中圓形為CA實(shí)體，箭頭表示證書(shū)，雙向箭頭為交叉證書(shū)，長(zhǎng)方形表示構(gòu)件實(shí)體，橋BCA用三角形表示，虛線描述了其中的一條信任鏈傳遞過(guò)程.不同的信任域采用的信任策略不同，各種信任域之間通過(guò)BCA互通形成更大規(guī)模的信任域.假設(shè)＜G＞是信任網(wǎng)絡(luò)的無(wú)負(fù)權(quán)有向圖，且不存在環(huán)路，下面給出在PKI模型中信任關(guān)系建立的過(guò)程.

圖3 BCA信任模型拓?fù)浣Y(jié)構(gòu)Fig.3 The topology structure for BCA trust model

3.1 信任鏈隨機(jī)搜索算法RSTC的形式化與推演

構(gòu)件節(jié)點(diǎn)間信任關(guān)系的建立過(guò)程也是信任鏈搜索和計(jì)算的過(guò)程.一種思路是通過(guò)考察G中所有可能的路徑來(lái)確定是否存在從Qi到Qj的信任鏈，一條最長(zhǎng)的路徑就是＜G＞中長(zhǎng)度最多為n的節(jié)點(diǎn)序列(假定不存在環(huán)路)，n是＜G＞中的節(jié)點(diǎn)數(shù)(如果從Qi到Qj存在有向路徑，那么就存在長(zhǎng)度不超過(guò)n的有向路徑，因?yàn)槁窂缴喜恍枰貜?fù)節(jié)點(diǎn))，但是這些路徑數(shù)最壞情況下有nn條，即＜G＞中節(jié)點(diǎn)數(shù)的指數(shù)倍.顯然，當(dāng)構(gòu)件集群規(guī)模足夠大時(shí)，算法時(shí)間復(fù)雜度是NP類(lèi)的.下面給出一種基于標(biāo)記的隨機(jī)搜索算法(random searching for trust chain，RSTC)的形式化描述如下:

1)對(duì)于輸入＜G＞，Qi，Qj;

2)在節(jié)點(diǎn)Qi上做標(biāo)記;

3)重復(fù)下面步驟4)～6)，直到不再有節(jié)點(diǎn)被標(biāo)記;

4)掃描＜G＞的所有邊.非確定性的選擇一條邊(a，b)，并且滿足a被標(biāo)記而b沒(méi)有被標(biāo)記，并轉(zhuǎn)向5);

5)如果a使用公鑰驗(yàn)證b的證書(shū)成立，則a的信任策略集合為ηQa=ηQa∪ηQb;

6)計(jì)算置信函數(shù)ν(a，b)，如果置信度ν(a，b)≥νmin，νmin為最小置信度閾值，那么標(biāo)記b;

7)若Qj被標(biāo)記，則接受;否則拒絕;

下面進(jìn)一步分析算法的可行性，顯然步驟1)、7)只執(zhí)行1次，步驟4)、5)、6)最多執(zhí)行n次，其中n為節(jié)點(diǎn)總數(shù)，用到的總步數(shù)是1+1+3n，所以時(shí)間復(fù)雜度為O(n)，因此RSTC屬于P類(lèi)問(wèn)題.以圖3構(gòu)件Q1對(duì)Q2建立信任關(guān)系的過(guò)程為例，假定Q1隨機(jī)選擇的路徑為圖中虛線所示的路徑，即 p1: Q1→Qk→Qc→QB→Qg→Qf→Q2.根據(jù)上述算法描述，對(duì)構(gòu)件Q1與Q2信任機(jī)制的建立過(guò)程進(jìn)行形式化推演.

根據(jù)定義2的形式化定義，對(duì)p1上相關(guān)構(gòu)件主體的初始信任策略集合作如下形式化描述:

其中:{Qk}key_Qk表示構(gòu)件主體Qk的密鑰綁定為key _Qk，Q1(Rk，{Qk}key_Qk)?Qk表示構(gòu)件主體Q1信任Qk的密鑰為key_Qk.路徑上相關(guān)節(jié)點(diǎn)的數(shù)字證書(shū)語(yǔ)義表述為

假設(shè)Rij=Ri?Rj，表示Qi與Qj不同信任策略及約束條件Ri、Rj的合成運(yùn)算.Φij=φi∧φj表示Qi與Qj的信任斷言φi、φj的合取運(yùn)算.下面給出p1路徑上信任關(guān)系建立的推演過(guò)程:

1)構(gòu)件 Q1使用公鑰 key_Qc驗(yàn)證證書(shū){ηQc}key_Qc－1，如果驗(yàn)證成功，則計(jì)算置信度 ν(Q1， Qc)，如果(Q1，Qc)≥νmin則對(duì)Qc做標(biāo)記，否則選擇其他節(jié)點(diǎn).Q1的信任策略集合為ηQ1=ηQ1∪ηQc.構(gòu)件Q1根據(jù)Q1(Rkc，φkc)?Qc;Qc(RB，φB)?QB應(yīng)用推理2、3可得Q1(RkcB，φkcB)?QB;Q1(RkcB，{QB}key_QB)?QB}.其中RkcB=Rkc?RB，φkcB=φkc∧φB.

2)構(gòu)件Q1驗(yàn)證Q1(RkcB，{QB}key_QB)?QB是否正確，如果QB的密鑰在策略組合及約條件RkcB= Rkc?RB，φkcB=φkc∧φB下滿足key_QB?RkcB則轉(zhuǎn)向下一步驗(yàn)證，否則認(rèn)證失敗.

3)依次類(lèi)推，經(jīng)過(guò)圖3虛線上各節(jié)點(diǎn)直到構(gòu)件Q1根據(jù)Q1(RkcBgf，φkcBgf)?Qf，Qf(R2，φ2)?Q2應(yīng)用推理2、3可得Q1(RkcBgf2，φkcBgf2)?Q2;如果ν(Q1，Q2)≥νmin，則Q1與Q2成功建立起信任關(guān)系，并對(duì)Q2做標(biāo)記，其中RkcBgf=RkcBg?Rf，φkcBgf=φkcBg∧φf(shuō).

4)判斷Q2是否被標(biāo)記，如果已被標(biāo)記則接受;否則拒絕.

由于構(gòu)件之間可能存在多條信任路徑，信任關(guān)系的建立要考慮多條信任路徑的綜合情況，如圖3所示，Qk與Qc存在著不同的信任路徑Qk→Qc與Qk→QW→Qc，如果Qk對(duì)Qc不存在直接信任關(guān)系，而Qk信任Qw，Qw信任Qc顯然不能說(shuō)Qk不信任Qc.因此，3.2節(jié)將提出一種新的信任鏈搜索算法.

3.2 一種優(yōu)化的信任鏈搜索算法的形式化

構(gòu)件節(jié)點(diǎn)之間建立信任關(guān)系的過(guò)程也就是通過(guò)搜索網(wǎng)絡(luò)節(jié)點(diǎn)尋找信任鏈的過(guò)程，2個(gè)構(gòu)件之間可能存在多條信任鏈，某些時(shí)候構(gòu)件節(jié)點(diǎn)只需要找到一條置信度最高的信任鏈作為交互的通道.現(xiàn)實(shí)信任關(guān)系網(wǎng)絡(luò)中往往通過(guò)搜索一條具有較高置信度的最優(yōu)信任鏈，通過(guò)該信任鏈上節(jié)點(diǎn)間的特殊關(guān)系和“連帶”效應(yīng)能夠在一定程度上起到監(jiān)督和限制節(jié)點(diǎn)，使其提供可靠服務(wù)減少惡意行為的作用.

基于上述分析并借鑒貪心策略在求解最優(yōu)化問(wèn)題的基本思想，提出一種基于貪心策略尋找最優(yōu)信任鏈的算法(greedy strategy for trust chain，GSTC)算法，對(duì)GSTC形式化描述如下:

1)輸入＜G＞，Qi，Qj:

2)初始化S={Qi};V={＜G＞中所有節(jié)點(diǎn)}; ν(Qi，Qt)={Qi初始時(shí)對(duì) V中節(jié)點(diǎn) Qt的置信度|t∈V－S};

3)若S≠V則重復(fù)4)～11)操作:

4)構(gòu)件Qi使用公鑰key_Qt驗(yàn)證與其相鄰的各節(jié)點(diǎn)Qt的證書(shū){ηQt}key_Qt－1，其中t∈V－S，并且Qt是Qi相鄰節(jié)點(diǎn);

5)如果驗(yàn)證成功則轉(zhuǎn)向7)，否則轉(zhuǎn)向6);

6)將驗(yàn)證失敗的邊Qi→Qt的置信度置為0，即ν(Qk，Qt)=0;

7)此時(shí)構(gòu)件Qi的信任策略集合ηQi=ηQi∪ηQt;

8)求出與當(dāng)前節(jié)點(diǎn)Qt相鄰節(jié)點(diǎn)中置信度最大的邊，即ν(Qt，Qk)=max{ν(Qt，Qx)|x∈V－S};

9)S=S∪{k};

10)對(duì)于每一個(gè)t∈V－S修改ν(Qi，Qt)=max {ν(Qi，Qt)，ν(Qi，Qk)?(Qk，Qt)}，其中?為信任聚合算子;

11)判斷若S=V則算法結(jié)束并返回集合S，否則轉(zhuǎn)向3);

12)如果Qj∈S，則接受，否則拒絕.

顯然，上述算法的時(shí)間復(fù)雜度為O(n2)，因此屬于P類(lèi)問(wèn)題.當(dāng)算法成功結(jié)束時(shí)，集合S中存儲(chǔ)的信任鏈就是從Qi到Qj的置信度最大的一條信任鏈，構(gòu)件Qi依次經(jīng)過(guò)集合S中的節(jié)點(diǎn)與構(gòu)件Qj進(jìn)行交互，由于每次交互時(shí)選擇的都是最可靠的交互對(duì)象，從而有效降低了信任傳播過(guò)程中的風(fēng)險(xiǎn).對(duì)于信任鏈置信度的具體計(jì)算可以根據(jù)路徑上節(jié)點(diǎn)的重要程度而分配不同的權(quán)重，而對(duì)于信任鏈過(guò)長(zhǎng)的問(wèn)題，我們也可以進(jìn)一步修改上述算法，設(shè)置信任鏈最大跳數(shù)，限制由于信任鏈過(guò)長(zhǎng)所帶來(lái)的風(fēng)險(xiǎn)以及計(jì)算過(guò)于復(fù)雜等問(wèn)題.此外，當(dāng)存在多條信任鏈具有相同置信度時(shí)，我們應(yīng)該從中選擇一條抖動(dòng)系數(shù)最小的.雖然上述算法是可行的，但是這種最優(yōu)化信任鏈也存在著缺點(diǎn)，比如抗干擾能力差，評(píng)估帶有片面性等.為此我們可以修改算法，找到k條信任鏈進(jìn)行信任鏈聚合，其中k∈［1，2n］，當(dāng)k取1時(shí)顯然是GSTC算法的特例，當(dāng)k=pathn時(shí)，是一種信任鏈聚合的綜合評(píng)價(jià)方式，pathn是2個(gè)節(jié)點(diǎn)間所有可達(dá)的全路徑數(shù).一般取k=0.5pathn，因?yàn)橥ǔＧ闆r下認(rèn)為，當(dāng)網(wǎng)絡(luò)規(guī)模很大時(shí)，網(wǎng)絡(luò)中惡意節(jié)點(diǎn)數(shù)不會(huì)超過(guò)網(wǎng)絡(luò)規(guī)模的一半.

3.3 多路徑信任聚合算法MPTA的形式化

單一信任鏈在一些情況下是可以用于評(píng)價(jià)構(gòu)件節(jié)點(diǎn)信任狀況的，而在一些對(duì)信任度要求很高的網(wǎng)絡(luò)中，單一信任鏈難以滿足這一要求，為此本節(jié)提出一種基于遞歸回溯思想［10］求解多路徑信任聚合的受限問(wèn)題的方法，并在多路徑信任鏈搜索過(guò)程設(shè)置了顯示約束條件，通過(guò)約束來(lái)限定信任鏈的某些屬性，如通過(guò)限制信任鏈置信度的最小閾值和信任鏈的最大長(zhǎng)度來(lái)減小動(dòng)態(tài)解空間樹(shù)的規(guī)模，同時(shí)這種顯示約束也能夠有效的減小信任鏈的“抖動(dòng)”，限制單個(gè)節(jié)點(diǎn)波動(dòng)過(guò)大的問(wèn)題，以及由于信任鏈過(guò)長(zhǎng)導(dǎo)致風(fēng)險(xiǎn)系數(shù)增加等.

求解多路徑信任聚合算法的基本思路是:對(duì)于節(jié)點(diǎn)Qi與Qj，搜索從Qi到Qj滿足約束條件的所有可達(dá)路徑，并對(duì)這些路徑進(jìn)行分類(lèi)，分別賦予相應(yīng)的權(quán)重，通過(guò)加權(quán)求和的方法對(duì)節(jié)點(diǎn)Qj進(jìn)行多路徑聚合評(píng)價(jià).設(shè)path［n］用于暫存遍歷過(guò)程中的當(dāng)前路徑，visited［n］為節(jié)點(diǎn)訪問(wèn)標(biāo)志，visited［i］=1表示節(jié)點(diǎn)Qi已被遍歷過(guò)，visited［i］=0表示節(jié)點(diǎn)Qi未被遍歷過(guò).value用于存儲(chǔ)節(jié)點(diǎn)Qi對(duì)Qj的多路徑信任聚合值，初值為0，設(shè)置計(jì)數(shù)器count用于記錄符合約束條件的信任鏈的條數(shù)，初值為0.下面給出多路徑聚合算法MPTA(multiple path trust aggregation)的形式化描述如下:

MPTA(＜G＞，Qi，Qj，len):

1)初始化向量path［len］={Qi}，len記錄當(dāng)前信任鏈的長(zhǎng)度，初始值為0，標(biāo)記當(dāng)前節(jié)點(diǎn)Qi即visited［Qi］=1;

2)如果已經(jīng)找到一條信任鏈，即當(dāng)前節(jié)Qi等于Qj，則執(zhí)行以下3)～7)，否則轉(zhuǎn)向8);

3)判斷此信任鏈的長(zhǎng)度，如果不大于最長(zhǎng)信任鏈限定的閾值，則轉(zhuǎn)向4)，否則，放棄此信任鏈;

4)判斷此信任鏈的置信度 是否大于最低信任閾值，如果是，則轉(zhuǎn)向5)，否則，放棄此信任鏈;

5)判斷此信任鏈抖動(dòng)因子是否小于最小閾值，如果是，則轉(zhuǎn)向6)，否則，放棄該信任鏈;

6)根據(jù)此信任鏈上節(jié)點(diǎn)序列的重要程度或者權(quán)威性對(duì)此信任鏈的相關(guān)數(shù)據(jù)進(jìn)行分類(lèi)和挖掘，并賦予相應(yīng)的權(quán)重μi，其中μi∈［0，1］，∑μi=1，i=1，2，3…n;

7)計(jì)算:value=value+μi*ν，count=count+1;

8)查找當(dāng)前構(gòu)件節(jié)點(diǎn)Qi的所有鄰節(jié)點(diǎn)p，當(dāng)visited［p］=0時(shí)遞歸執(zhí)行MPTA(＜G＞，p，Qj，len+ 1);

9)將當(dāng)前節(jié)點(diǎn)Qi的訪問(wèn)標(biāo)志visited［Qi］置為0，path［len］置為0以便進(jìn)入回溯過(guò)程;

算法執(zhí)行結(jié)束返回從Qi到Qj滿足約束條件的所有信任鏈的置信度之和value，取value的平均值即value/count作為多路徑信任聚合的置信度.分析上述算法的時(shí)間復(fù)雜度，假設(shè)采用鄰接表作為圖＜G＞的存儲(chǔ)結(jié)構(gòu)，可知每次遞歸回溯的最大深度為O(e)，其中e為＜G＞弧數(shù)，e的最大值為n(n－1)/2，又由8)可知執(zhí)行遞歸的可能鄰節(jié)點(diǎn)為n個(gè)，其中n為＜G＞重節(jié)點(diǎn)總數(shù)，因此時(shí)間復(fù)雜度為O (n3).多路徑信任聚合算法提出能夠解決了當(dāng)存在多條信任鏈時(shí)的聚合問(wèn)題，這一算法同樣可以用于求解多個(gè)節(jié)點(diǎn)對(duì)某一個(gè)節(jié)點(diǎn)的綜合推薦問(wèn)題，第4節(jié)將進(jìn)一步通過(guò)實(shí)驗(yàn)給出多路徑信任聚合算法的分析.

4 對(duì)GSTC和MPTA算法的實(shí)驗(yàn)分析

以圖3的拓?fù)浣Y(jié)構(gòu)圖為實(shí)驗(yàn)配置模型，模擬構(gòu)件Q1與Q2建立信任關(guān)系的過(guò)程，對(duì)于圖3中Q1搜索Q2的信任路徑所經(jīng)過(guò)的所有可能的弧有:(f，2)，(g，f)，(B，g)，(c，B)，(1，k)，(k，w)，(k，c)，(k，n)，(w，c)，(n，w)，(m，c)，(w，m)，(n，m).基于統(tǒng)計(jì)學(xué)理論可以認(rèn)為網(wǎng)絡(luò)中節(jié)點(diǎn)的信任狀況是服從正態(tài)分布的，即服從N(μ，σ2)的分布，因此，采用正態(tài)隨機(jī)數(shù)模擬上述所有弧的權(quán)值即節(jié)點(diǎn)間的置信度ν，實(shí)驗(yàn)基于C++平臺(tái)分別實(shí)現(xiàn)了 RSTC算法、GSTC算法和MPTA算法，每次對(duì)所有弧的權(quán)值采用正態(tài)隨機(jī)數(shù)賦值，分別輸出單一信任鏈和多路徑信任聚合情況下節(jié)點(diǎn)Q1到Q2的置信度.實(shí)驗(yàn)共模擬了100次，分別對(duì) μ=0.95，σ2=0.005和 μ= 0.5，σ2=0.005兩種情況進(jìn)行了實(shí)驗(yàn)對(duì)比.

實(shí)驗(yàn)結(jié)果分析如下:如圖4、5所示當(dāng)μ=0.95，σ2=0.005，μ=0.5，σ2=0.005時(shí)，采用GSTC算法每次得到的置信度都是最大的，但從曲線的波動(dòng)幅度不難看出GSTC算法抖動(dòng)現(xiàn)象比RSTC算法的抖動(dòng)現(xiàn)象明顯.如圖5所示，當(dāng)網(wǎng)絡(luò)信任狀況較差時(shí)RSTC與GSTC曲線的波動(dòng)幅度更大，這表明當(dāng)網(wǎng)絡(luò)信任狀況較差時(shí)抖動(dòng)會(huì)更加明顯.RSTC每次得到的信任鏈的置信度相對(duì)于GSTC較低.此外，RSTC與GSTC曲線的整體抖動(dòng)性都比MPTA較大，顯然對(duì)于穩(wěn)定性而言MPTA要優(yōu)于RSTC和GSTC，這也是之所以采用MPTA信任聚合算法原因之一.雖然一次交互過(guò)程中選擇最優(yōu)信任鏈并不一定意味著受益一定是最大的，但是如果每次都選擇一條最佳的信任路徑，那么從概率上講當(dāng)交互次數(shù)n達(dá)到一定數(shù)量時(shí)，采用最優(yōu)信任鏈獲到可靠服務(wù)的機(jī)會(huì)要遠(yuǎn)大于采用隨機(jī)搜索算法.

圖4 當(dāng)μ=0.95，σ2=0.005，n=100時(shí)的置信度Fig.4 Confidence curves when μ=0.95，σ2=0.005，n=100

如圖6、7所示為μ=0.95和0.5，方差σ2= 0.005的情況，虛線為非約束條件下MPTA的置信度變化曲線，所謂非約束條件即是指不對(duì)信任鏈的長(zhǎng)度、抖動(dòng)系數(shù)、和最低置信度閾值加以限制.實(shí)線為約束條件下的MPTA的置信度變化曲線，假定限制信任鏈的長(zhǎng)度不超過(guò)0.5n，其中n為網(wǎng)絡(luò)構(gòu)件節(jié)點(diǎn)總數(shù)，抖動(dòng)系數(shù)最大為σ2.通過(guò)圖6、7可以看出，多路徑信任聚合過(guò)程中對(duì)于信任鏈的顯示約束能夠有效減少抖動(dòng)現(xiàn)象，使網(wǎng)絡(luò)整體信任狀況趨于相對(duì)穩(wěn)定，避免置信度較差的節(jié)點(diǎn)通過(guò)信任鏈傳播到整個(gè)網(wǎng)絡(luò)，能夠有效控制惡意信任鏈的傳播，同時(shí)減少了信任評(píng)估過(guò)程中的計(jì)算開(kāi)銷(xiāo)和網(wǎng)絡(luò)負(fù)載.對(duì)于某些置信度較低的惡意信任鏈，如果不能及時(shí)的加以限制很可能導(dǎo)致對(duì)其他可信度較高的節(jié)點(diǎn)的評(píng)估出現(xiàn)較大偏差.

圖5 當(dāng)μ=0.5，σ2=0.005，n=100時(shí)的置信度Fig.5 Confidence curves when=0.5，σ2=0.005，n=100

圖6 當(dāng)μ=0.95，σ2=0.005，n=100時(shí)的置信度Fig.6 Confidence curves when μ=0.95，σ2=0.005，n=100

圖7 當(dāng)μ=0.5，σ2=0.005，n=100時(shí)的置信度Fig.7 Confidence curves when μ=0.5，σ2=0.005，n=100

5 結(jié)束語(yǔ)

由于構(gòu)件集群環(huán)境是一個(gè)涉及多層次、多粒度、錯(cuò)綜交織的動(dòng)態(tài)環(huán)境，在這種環(huán)境中信任關(guān)系的定義、推理和建立過(guò)程是一個(gè)極其復(fù)雜的過(guò)程，本文基于信念邏輯，給出了信任關(guān)系的形式化描述，對(duì)信任關(guān)系的建立過(guò)程進(jìn)行了推演，對(duì)于信任鏈、多路徑信任聚合算法的提出有利于網(wǎng)構(gòu)軟件信任機(jī)制的進(jìn)一步深入研究.目前，對(duì)于多路徑、全路徑信任聚合方法的研究不多，解決多路徑、全路徑信任聚合問(wèn)題的關(guān)鍵是尋找一種時(shí)間復(fù)雜度較低的多路徑搜索方法，本文尚有不足之處需要改進(jìn)，比如對(duì)信任鏈上各節(jié)點(diǎn)的分析，對(duì)惡意節(jié)點(diǎn)的發(fā)現(xiàn)和預(yù)警、惡意信任鏈的傳播缺乏有效的應(yīng)對(duì)機(jī)制，此外，對(duì)于存在環(huán)路的信任鏈的信任傳播過(guò)程中可能造成死鎖的情況沒(méi)有加以考慮.下一步工作將深入研究網(wǎng)構(gòu)軟件信任系統(tǒng)的形式化、自動(dòng)化驗(yàn)證的方法，在此基礎(chǔ)上開(kāi)展信任策略自動(dòng)評(píng)估工作.

［1］YANG F Q.Thinking on the development of software engineering technology［J］.Journal of Software，2005，16(1):1－7.

［2］袁祿來(lái)，曾國(guó)蓀，王偉.基于Pi－演算的信任網(wǎng)絡(luò)形式化建模［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(1):57－61.

YUAN Lulai，ZENG Guosun，WANG Wei.Formal modeling of trust networks using Pi－calculus［J］.Journal of System Simulation，2008，20(1):57－61.

［3］LAMPSON B，ABADI M，BURROWS M，WOBBERE.Authentication in distributed systems:theory and practice［J］.ACM Transactions on Computer Systems，1992，10(4):265－310.

［4］BLAZE M，F(xiàn)EIGENBAUM J，LACY J.Decentralized trust management［C］//Proceedings of the IEEE Symposium on Security and Privacy.Oakland，1996:164－173.

［5］LI N，MITCHELL J C，WINSBOROUGH W H.Design of a role－based trust management framework［C］//Proceedings of the 2002 IEEE Symposium on Security and Privacy.Berkeley，2002:114－130.

［6］MOSES T.Trust management in the public key infrastructure［EB/OL］.［2002－06－03］.http://www.entrust.corn/resources/pdf/trustmodels.pdf.

［7］GRANDISON T，SLOMAN M.A survey of trust inInternet applications［J］.IEEE Communications Surveys，2000，4 (4):2－16.

［8］J?SANG A.The right type of trust for distributed systems［C］//Proceedings of the 1996 Workshop on New security Paradigms.San Diego，USA，1996:119－131.

［9］SIPSER M.Introduction to the theory of computation［M］.Boston:PWS Publishing Company，2008:136－145.

［10］FOMIN F V，GRANDONI F.A measure＆conquer approach for the analysis of exact algorithms［J］.Journal of the ACM，2009:56(5):25－27.