基于信任度的分布式證書鏈搜索算法

雷建云，方小海，侯 睿

(中南民族大學計算機科學學院，武漢430074)

在信任管理系統(tǒng)實施訪問控制判定的時候，需要查找一條從授權(quán)源到訪問請求者的合法授權(quán)委托鏈，這就是證書鏈的搜索問題［1-2］.如果在進行證書鏈搜索的時候，所有相關(guān)的證書都已經(jīng)存放在本地或某一個具體的地點，則此時面對的是集中式的證書鏈搜索問題，但由于在信任管理系統(tǒng)中存在著主體之間分散式授權(quán)的特點，證書一般是分布式地發(fā)布和存儲的，所以由前述問題就衍生出分布式證書鏈的搜索問題.

分布式證書鏈的搜索算法通常是以集中式搜索算法為基礎(chǔ)并進行擴充的，但并不是所有的集中式搜索算法都能擴充到相應的分布式搜索算法.集中式搜索算法大致可分為自底向上和自頂向下的兩種.由于在分布式環(huán)境下，許多證書并不存放在本地，所以基于系統(tǒng)中全部的證書進行這種推演過程是不現(xiàn)實的.而自頂向下的算法則可以非常容易地擴充為分布式算法，它由某個具體的目標(主體、角色或證書)為起點開始進行相關(guān)證書的查找.例如以某個角色為目標，到系統(tǒng)中去查找定義該角色的證書，然后根據(jù)證書中的主體，得到新的目標，并循環(huán)多次地進行查找.它并不像集中式算法那樣需要把所有的證書進行統(tǒng)一存儲，而只需要根據(jù)提供的相應目標，查找那些與其相關(guān)的證書的集合.

1 分布式證書的存儲及格式

要設(shè)計一種分布式證書鏈的搜索算法，首先面對的問題是要設(shè)計證書的分布存儲方案，即證書到底由誰來負責存儲.假設(shè)證書C是由實體S來負責存儲的，則當知道S是誰以后，就可以方便地找到證書C.實體S也并不是需要直接存儲證書，他可以由另外的實體代表S來實施具體證書存儲過程，例如一個輕量級目錄訪問協(xié)議目錄(LDAP)等等.因為一個證書中一般都包含發(fā)行者和主體這兩個字段，所以證書既可以由發(fā)行者來實施存儲，也可以由證書的主體來進行存儲，證書的分布存儲方案也由此而可以分為3類.

(1)由主體實施證書存儲的方案;

(2)由發(fā)行者實施證書存儲的方案;

(3)一部分證書由主體實施證書存儲，一部分由發(fā)行者實施證書存儲，或一部分由兩者共同實施證書存儲的方案.

針對上述3類方案，在實施的過程中只將訪問控制列表存放在本地，而忽略證書在分布式系統(tǒng)中的存儲位置等細節(jié)，只需要保證能夠通過相應的算法找到分布式存儲的所有的與主體相關(guān)或無關(guān)的證書集合.

在信任管理系統(tǒng)中增加信任度的概念［3］，即一個主體對一個客體用一個信任值來表示相應的授權(quán)委托，用三元組(S，O，T)來表示，其中，S表示證書中的主體，O表示證書中的客體，T表示證書中的信任度的值，其含義是S對O的信任度的值為T.把三元組(S，O，T)標記作:.信任度的具體計算可參見文獻［4］.

本地訪問控制列表中的條目則是用三元組(R，Q，T)來表示.其中，R表示權(quán)限，Q表示訪問請求的提出者，T表示信任度的閾值，即要求Q擁有的信任度的值要超過T，才能獲得權(quán)限R.把三元組(R，Q，T)記作:

要注意的是，在授權(quán)委托證書中，主體S和客體O都可能是本地訪問控制列表中訪問請求的提出者Q.

2 基于信任度的分布式證書鏈搜索算法

為了能夠快速地找到證書鏈，首先要對訪問者所提供的證書和本地訪問控制列表進行相應的預處理:驗證訪問請求者所提供的證書的有效性.有效性驗證包括這些工作:驗證證書是否已經(jīng)過期，信任度的取值是否在合法的范圍之內(nèi)等等.這樣做的目的是為了剪枝式地去掉一些多余的選項，提高證書搜索算法的效率.

定義1假設(shè)存在證書的集合C、本地的訪問控制列表L和一個訪問控制權(quán)限r(nóng)，則在系統(tǒng)中擁有訪問控制權(quán)限r(nóng)的所有實體所構(gòu)成的集合稱作權(quán)限r(nóng)在證書集C和本地訪問控制列表L上的成員集，記為M(r).

r的成員集的求解過程是一個循環(huán)求解過程.如果把每次循環(huán)求解得到的中間結(jié)果記作Mi(r)，那么權(quán)限r(nóng)的成員集包括計算出的中間結(jié)果加上此結(jié)果中的元素(成員)授權(quán)委托給的新的成員;所以，M1(r)={Q|(R，Q，T)∈L∩R?r}，即直接擁有權(quán)限r(nóng)的成員的集合，Mi+1(r)=Mi(r)∪{O|(S，O，T)∈C∩S∈Mi(r)}.當Mi+1(r)與Mi(r)相等時，表示已經(jīng)沒有新的成員被授權(quán)委托，此時終止求解過程，Mi+1(r)或Mi(r)就是所求的成員集M(r).

定義2假設(shè)存在證書的集合C、本地的訪問控制列表L和一個實體E，則實體E在系統(tǒng)中所擁有的全部權(quán)限所構(gòu)成的集合稱作實體E在集合C和本地訪問控制列表L上的權(quán)限集，記為P(E).

E的權(quán)限集的求解過程也是一個循環(huán)求解過程.如果把每次循環(huán)求解得到的中間結(jié)果記作Ai(E)，A集合用來表示包含著E和有直接或間接授權(quán)委托給E的所有主體的集合;A1(E)={E}，Ai+1(E)=Ai(E)∪ {S|(S，O，T)∈C∩O∈Ai(E)}，表示E的權(quán)限集包含E本身的權(quán)限，加上別的主體直接或間接授權(quán)委托給E的權(quán)限.當Ai+1(E)=Ai(E)時，表示已經(jīng)沒有新的可求出的授權(quán)委托給E的主體，此時終止求解過程，{R|(R，Q，T)∈L∩Q∈Ai+1(E)}就是所求的權(quán)限集P(E).

證書鏈搜索的算法包括前向搜索算法、后向搜索算法和雙向搜索算法等3種.分別對應于以權(quán)限為起點求成員集，以實體委托為起點求權(quán)限集和同時以兩個為起點進行雙向匹配的算法.

2.1 前向搜索算法

前向搜索算法的基本思想是從本地訪問控制列表中的權(quán)限為起點進行證書鏈的搜索.從定義1可以知道，只要訪問請求者是他所提交的訪問請求所需要的權(quán)限的成員集中的元素之一，就可以證明他擁有相應的證書鏈;否則，不存在相應的證書鏈.

假設(shè)訪問者U需要擁有的最小權(quán)限為r.則前向搜索算法的描述如下.

(1)在本地訪問控制列表中進行搜索，計算出M1(r).M1(r)={Q|(R，Q，T)∈L∩R?r}.如果M1(r)為空集，則不存在證明訪問請求者U擁有權(quán)限r(nóng)的證書鏈，并結(jié)束計算.如果訪問者U已經(jīng)是M1(r)中的一個元素，則本地訪問控制列表中的訪問控制條目(R，U，T)就構(gòu)成了U擁有權(quán)限r(nóng)的證書鏈.

(2)如果(1)中U不是M1(r)中的一個元素且M1(r)不是空集.則根據(jù)定義1來循環(huán)計算Mi(r)(i≥2).Mi+1(r)=Mi(r)∪ {O|(S，O，T)∈C∩S∈Mi(r)}.在此，為了避免進行重復的搜索，要對曾經(jīng)搜索過的證書和中間結(jié)果Mi-1(r)中的元素加以標識，并記錄證書與證書之間存在的聯(lián)系(記住它的上一條證書條目)，以便構(gòu)造證書鏈.如果訪問請求者U是Mi(r)中的一個元素，則可以找到訪問請求者U擁有權(quán)限r(nóng)的證書鏈，并轉(zhuǎn)到第(3)步去執(zhí)行;如果訪問者U不屬于求解出來的成員集Mi(r)，并且Mi(r)已經(jīng)與Mi-1(r)相等，則不存在需要查找的證書鏈，結(jié)束計算并退出.

(3)存在證明訪問請求者U擁有權(quán)限r(nóng)的證書鏈，根據(jù)記錄的證書間的聯(lián)系，構(gòu)造出相應的證書鏈.

2.2 后向搜索算法

后向搜索算法的基本思想是從委托的主體為起點進行證書鏈的搜索.從定義2可以知道，如果訪問請求者提出的訪問請求所需要的權(quán)限是他的權(quán)限集合中的元素之一，則存在他擁有相應訪問權(quán)限的證書鏈;否則訪問請求所需要的權(quán)限不是訪問請求者的權(quán)限集合中的元素，也就是訪問請求者沒有相應的權(quán)限來實施相應的訪問，所以不存在相應的證書鏈.

在計算U的權(quán)限集的過程中，其權(quán)限集包含U本身的權(quán)限，加上別的主體直接或間接授權(quán)委托給U的權(quán)限，不妨用A集合來表示包含著U和有直接或間接授權(quán)委托給U的所有主體的集合.

假設(shè)訪問者U需要擁有的最小權(quán)限為r.則后向搜索算法的描述如下.

(1)循環(huán)計算Ai(U)(i≥1).A1(U)={U}，Ai+1(U)=Ai(U)∪ {S|(S，O，T)∈C∩O∈Ai(U)}.當Ai+1(U)=Ai(U)時，終止循環(huán)計算.為了避免進行重復的搜索，需要對曾經(jīng)搜索過的證書和得到的中間結(jié)果Ai(U)中的元素加上相應的標識，并記錄證書與證書之間存在的聯(lián)系(即記住它的上一條證書條目)，以便在后面的步驟中進行證書鏈的構(gòu)造.

(2)計算訪問者U的權(quán)限集P(U).P(U)={R|(R，Q，T)∈L∩Q∈Ai+1(U)}.如果r∈P(U)，則存在訪問請求者U擁有權(quán)限r(nóng)的證書鏈;如果r?P(U)，則不存在相應的證書鏈.

(3)如果存在訪問請求者U擁有權(quán)限r(nóng)的證書鏈，則根據(jù)計算過程中記錄的證書之間的聯(lián)系，構(gòu)造出相應的證書鏈.

2.3 雙向搜索算法

雙向搜索算法的基本思想是同時使用上述前向搜索法和后向搜索法進行證書鏈的搜索.在搜索的過程中，算法每進行循環(huán)搜索一次就做一次判斷，看是否存在前向搜索算法求解出的中間結(jié)果與后向搜索算法求解出的中間結(jié)果中包含著相同的元素，假如存在，則存在訪問請求者擁有該權(quán)限的證書鏈，可以根據(jù)中間結(jié)果來構(gòu)造相應的證書鏈;否則，不存在相應的證書鏈.

假設(shè)訪問者U需要擁有的最小權(quán)限為r.則雙向搜索算法描述如下.

(1)搜索本地訪問控制列表，計算M1(r)，A1(U).M1(r)={Q|(R，Q，T) ∈L∩R?r}，A1(U)={U}.如果M1(r)為空集，則不存在證明訪問請求者U擁有權(quán)限r(nóng)的證書鏈，并退出.如果M1(r)∩A1(U)≠?，則已經(jīng)找到了訪問請求者U擁有權(quán)限r(nóng)的證書鏈，該證書鏈就是本地的訪問控制條目(r，U，T).

(2) 循環(huán)計算Mi(r)，Ai(U)(i＞1).Mi(r)，Ai(U)的計算方法與前向搜索法和后向搜索法中的計算方法相同.如果Mi(r)∩Ai(U)≠?，則已經(jīng)找到訪問請求者U擁有權(quán)限r(nóng)的證書鏈，并轉(zhuǎn)第(3)步執(zhí)行.如果Mi+1(r)=Mi(r)，Ai+1(U)=Ai(U)且Mi(r)∩Ai(U)≠?，則不存在訪問請求者U擁有權(quán)限r(nóng)的證書鏈.

(3)如果存在訪問請求者U擁有權(quán)限r(nóng)的證書鏈，則根據(jù)計算過程中記錄的證書之間的聯(lián)系，構(gòu)造出相應的證書鏈.

在實際的應用中，由于雙向搜索算法的特殊性，其搜索的效率可能比前兩種搜索算法要更高一些，但實際用到的內(nèi)存開銷會更大一些.

3 算法的性能分析與比較

假設(shè)證書集合C有N個證書，則上述3種證書鏈查找算法的時間復雜度全部是O(N2).

另外，由于在整個搜索過程中，每個證書都只需要進行一次存儲.所以搜索算法的空間復雜度為O(N).

同其他人提出的信任管理模型中的證書鏈搜索算法，例如 Li Ninghui等人［5］提出的 RT0以及其中的證書鏈搜索算法、Freudenthal等人提出的dRBAC模型［6］等等相比，本文提出的證書鏈搜索算法是基于信任度的，在實體與實體之間存在著一定的信任值，在主體對資源進行訪問的時候也需要該主體對該資源的直接或間接的信任值大于某個閾值，基于此前提，在進行分布式證書鏈的搜索的時候，可以根據(jù)該閾值進行預處理，將那些多余的證書刪除，大大提高證書搜索效率.

4 應用實例

在某個系統(tǒng)中本地訪問控制列表如表1所示，相關(guān)的委托的集合C如圖1所示，信任傳遞的計算采用的是文獻［7］中提出的f(t1，t2)=t1*t2/100.則Tom在2011年10月能否擁有Right_1的權(quán)限?

表1 訪問控制列表的格式與內(nèi)容Tab.1 Format and content of the access control list

圖1 支持Tom申請服務的委托Fig.1 Delegations supporting Tom's service application

根據(jù)表1和圖1可以來實施相應的計算，分別使用前向搜索、后向搜索和雙向搜索算法，首先進行預處理，可以將委托集合中的第4條和第6條刪除，因為這兩條委托記錄是過期的委托.

使用前向搜索算法，可以得到如下結(jié)果:

從權(quán)限Right_1出發(fā)來查找其成員集M，可以從本地訪問控制列表中找到Sailor，Kasi，Grace等用戶，繼而搜索委托集合，第一重循環(huán)就可以得到Kate的信任值為80，雖然通過Kate→John和John→Tom還可能搜索到Right_1到Tom的證書鏈，但因為Grace→Tom的信任值為90，所以已經(jīng)成功地搜索到了相應的證書鏈，算法終止并構(gòu)造出Grace→Tom的證書鏈.

使用后向搜索算法，可以得到如下結(jié)果:

從用戶Tom出發(fā)來查找其權(quán)限集R，可以找到A集合中包含元素Grace和John，繼而由于本地訪問控制列表中的第3條，可以搜索到相應的證書鏈，算法終止并構(gòu)造出Grace→Tom的證書鏈.

使用雙向搜索算法，可以得到如下結(jié)果:

分別從權(quán)限Right_1和用戶Tom出發(fā)，搜索Right_1的用戶集和用戶Tom的權(quán)限集，只需一重循環(huán)即可發(fā)現(xiàn)Grace對Right_1的權(quán)限和Grace→Tom委托，從而搜索到了相應的證書鏈，算法終止并構(gòu)造出Grace→Tom的證書鏈.

可以發(fā)現(xiàn)，雙向搜索算法效率相對較高，只需一重循環(huán)即可解決問題，但其存儲開銷較大，因為它需要同時存儲Right_1的成員集中間結(jié)果和Tom的權(quán)限集中間結(jié)果.

5 結(jié)語

分布式環(huán)境中，結(jié)點與結(jié)點之間可以先通過信任的評估手段來獲得信任度的值，繼而采用基于信任度的證書鏈搜索算法，通過結(jié)點之間信任度的判斷來實現(xiàn)選擇性地進行相應證書鏈的搜索，提高搜索效率.本文給出分布式環(huán)境下證書鏈搜索過程中的成員集和權(quán)限集的定義，具有一定的理論價值，并給出了信任管理系統(tǒng)中基于信任度的證書鏈前向、后向和雙向搜索算法，結(jié)合具體實例說明了算法的應用與實現(xiàn)過程.

［1］Li N，Winsborough W H，Mitchell J C.Distributed credential chain discovery in trust management［J］.Journal of Computer Security，2003，11(1):35-86.

［2］Zhu X，Wang S，Hong F，et al.Distributed credential chain discovery in trust-management with parameterized toles［C］//Desmedt Y G.Proceedings of the 4th International Conference on Cryptology and Network Security(CANS05)LNCS 3810.Xiamen:Springer-Verlag，2005:334-348.

［3］廖俊國，洪 帆，朱更明，等.基于信任度的授權(quán)委托模型［J］.計算機學報，2006，29(8):1265-1270.

［4］Lei Jianyun，Cui Guohua，Xing Guanglin.Trust calculation and delivery control in trust-based access control［J］.Wuhan University Journal of Nature Science，2008，13(6):765-768.

［5］Li N，Mitchell JC，Winsborough W H.Design of a rolebased trust-management framework ［C］//IEEE.Proceeding of the 2002 IEEE Symposium on Security and Privacy，Claremont Resort Oakland.California:IEEE，2002:114-130.

［6］Freudenthal E，Pesin T，Port L，et al.dRBAC:distributed role-based access control for dynamic coalition environments.［C］//ICDCS.Proceedings of the 22nd International Conference on Distributed Computing Systems(ICDCS＇02)，Vienna:ICDCS，2002:411-434.

［7］雷建云，崔國華，邢光林，等.可計算的基于信任的授權(quán)委托模型［J］.計算機科學，2008，35(10):73-75，85.