基于信任度的分布式证书链搜索算法

雷建云，方小海，侯 睿

(中南民族大学计算机科学学院，武汉430074)

在信任管理系统实施访问控制判定的时候，需要查找一条从授权源到访问请求者的合法授权委托链，这就是证书链的搜索问题［1-2］.如果在进行证书链搜索的时候，所有相关的证书都已经存放在本地或某一个具体的地点，则此时面对的是集中式的证书链搜索问题，但由于在信任管理系统中存在着主体之间分散式授权的特点，证书一般是分布式地发布和存储的，所以由前述问题就衍生出分布式证书链的搜索问题.

分布式证书链的搜索算法通常是以集中式搜索算法为基础并进行扩充的，但并不是所有的集中式搜索算法都能扩充到相应的分布式搜索算法.集中式搜索算法大致可分为自底向上和自顶向下的两种.由于在分布式环境下，许多证书并不存放在本地，所以基于系统中全部的证书进行这种推演过程是不现实的.而自顶向下的算法则可以非常容易地扩充为分布式算法，它由某个具体的目标(主体、角色或证书)为起点开始进行相关证书的查找.例如以某个角色为目标，到系统中去查找定义该角色的证书，然后根据证书中的主体，得到新的目标，并循环多次地进行查找.它并不像集中式算法那样需要把所有的证书进行统一存储，而只需要根据提供的相应目标，查找那些与其相关的证书的集合.

1 分布式证书的存储及格式

要设计一种分布式证书链的搜索算法，首先面对的问题是要设计证书的分布存储方案，即证书到底由谁来负责存储.假设证书C是由实体S来负责存储的，则当知道S是谁以后，就可以方便地找到证书C.实体S也并不是需要直接存储证书，他可以由另外的实体代表S来实施具体证书存储过程，例如一个轻量级目录访问协议目录(LDAP)等等.因为一个证书中一般都包含发行者和主体这两个字段，所以证书既可以由发行者来实施存储，也可以由证书的主体来进行存储，证书的分布存储方案也由此而可以分为3类.

(1)由主体实施证书存储的方案;

(2)由发行者实施证书存储的方案;

(3)一部分证书由主体实施证书存储，一部分由发行者实施证书存储，或一部分由两者共同实施证书存储的方案.

针对上述3类方案，在实施的过程中只将访问控制列表存放在本地，而忽略证书在分布式系统中的存储位置等细节，只需要保证能够通过相应的算法找到分布式存储的所有的与主体相关或无关的证书集合.

在信任管理系统中增加信任度的概念［3］，即一个主体对一个客体用一个信任值来表示相应的授权委托，用三元组(S，O，T)来表示，其中，S表示证书中的主体，O表示证书中的客体，T表示证书中的信任度的值，其含义是S对O的信任度的值为T.把三元组(S，O，T)标记作:.信任度的具体计算可参见文献［4］.

本地访问控制列表中的条目则是用三元组(R，Q，T)来表示.其中，R表示权限，Q表示访问请求的提出者，T表示信任度的阈值，即要求Q拥有的信任度的值要超过T，才能获得权限R.把三元组(R，Q，T)记作:

要注意的是，在授权委托证书中，主体S和客体O都可能是本地访问控制列表中访问请求的提出者Q.

2 基于信任度的分布式证书链搜索算法

为了能够快速地找到证书链，首先要对访问者所提供的证书和本地访问控制列表进行相应的预处理:验证访问请求者所提供的证书的有效性.有效性验证包括这些工作:验证证书是否已经过期，信任度的取值是否在合法的范围之内等等.这样做的目的是为了剪枝式地去掉一些多余的选项，提高证书搜索算法的效率.

定义1假设存在证书的集合C、本地的访问控制列表L和一个访问控制权限r，则在系统中拥有访问控制权限r的所有实体所构成的集合称作权限r在证书集C和本地访问控制列表L上的成员集，记为M(r).

r的成员集的求解过程是一个循环求解过程.如果把每次循环求解得到的中间结果记作Mi(r)，那么权限r的成员集包括计算出的中间结果加上此结果中的元素(成员)授权委托给的新的成员;所以，M1(r)={Q|(R，Q，T)∈L∩R⊇r}，即直接拥有权限r的成员的集合，Mi+1(r)=Mi(r)∪{O|(S，O，T)∈C∩S∈Mi(r)}.当Mi+1(r)与Mi(r)相等时，表示已经没有新的成员被授权委托，此时终止求解过程，Mi+1(r)或Mi(r)就是所求的成员集M(r).

定义2假设存在证书的集合C、本地的访问控制列表L和一个实体E，则实体E在系统中所拥有的全部权限所构成的集合称作实体E在集合C和本地访问控制列表L上的权限集，记为P(E).

E的权限集的求解过程也是一个循环求解过程.如果把每次循环求解得到的中间结果记作Ai(E)，A集合用来表示包含着E和有直接或间接授权委托给E的所有主体的集合;A1(E)={E}，Ai+1(E)=Ai(E)∪ {S|(S，O，T)∈C∩O∈Ai(E)}，表示E的权限集包含E本身的权限，加上别的主体直接或间接授权委托给E的权限.当Ai+1(E)=Ai(E)时，表示已经没有新的可求出的授权委托给E的主体，此时终止求解过程，{R|(R，Q，T)∈L∩Q∈Ai+1(E)}就是所求的权限集P(E).

证书链搜索的算法包括前向搜索算法、后向搜索算法和双向搜索算法等3种.分别对应于以权限为起点求成员集，以实体委托为起点求权限集和同时以两个为起点进行双向匹配的算法.

2.1 前向搜索算法

前向搜索算法的基本思想是从本地访问控制列表中的权限为起点进行证书链的搜索.从定义1可以知道，只要访问请求者是他所提交的访问请求所需要的权限的成员集中的元素之一，就可以证明他拥有相应的证书链;否则，不存在相应的证书链.

假设访问者U需要拥有的最小权限为r.则前向搜索算法的描述如下.

(1)在本地访问控制列表中进行搜索，计算出M1(r).M1(r)={Q|(R，Q，T)∈L∩R⊇r}.如果M1(r)为空集，则不存在证明访问请求者U拥有权限r的证书链，并结束计算.如果访问者U已经是M1(r)中的一个元素，则本地访问控制列表中的访问控制条目(R，U，T)就构成了U拥有权限r的证书链.

(2)如果(1)中U不是M1(r)中的一个元素且M1(r)不是空集.则根据定义1来循环计算Mi(r)(i≥2).Mi+1(r)=Mi(r)∪ {O|(S，O，T)∈C∩S∈Mi(r)}.在此，为了避免进行重复的搜索，要对曾经搜索过的证书和中间结果Mi-1(r)中的元素加以标识，并记录证书与证书之间存在的联系(记住它的上一条证书条目)，以便构造证书链.如果访问请求者U是Mi(r)中的一个元素，则可以找到访问请求者U拥有权限r的证书链，并转到第(3)步去执行;如果访问者U不属于求解出来的成员集Mi(r)，并且Mi(r)已经与Mi-1(r)相等，则不存在需要查找的证书链，结束计算并退出.

(3)存在证明访问请求者U拥有权限r的证书链，根据记录的证书间的联系，构造出相应的证书链.

2.2 后向搜索算法

后向搜索算法的基本思想是从委托的主体为起点进行证书链的搜索.从定义2可以知道，如果访问请求者提出的访问请求所需要的权限是他的权限集合中的元素之一，则存在他拥有相应访问权限的证书链;否则访问请求所需要的权限不是访问请求者的权限集合中的元素，也就是访问请求者没有相应的权限来实施相应的访问，所以不存在相应的证书链.

在计算U的权限集的过程中，其权限集包含U本身的权限，加上别的主体直接或间接授权委托给U的权限，不妨用A集合来表示包含着U和有直接或间接授权委托给U的所有主体的集合.

假设访问者U需要拥有的最小权限为r.则后向搜索算法的描述如下.

(1)循环计算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)时，终止循环计算.为了避免进行重复的搜索，需要对曾经搜索过的证书和得到的中间结果Ai(U)中的元素加上相应的标识，并记录证书与证书之间存在的联系(即记住它的上一条证书条目)，以便在后面的步骤中进行证书链的构造.

(2)计算访问者U的权限集P(U).P(U)={R|(R，Q，T)∈L∩Q∈Ai+1(U)}.如果r∈P(U)，则存在访问请求者U拥有权限r的证书链;如果r∉P(U)，则不存在相应的证书链.

(3)如果存在访问请求者U拥有权限r的证书链，则根据计算过程中记录的证书之间的联系，构造出相应的证书链.

2.3 双向搜索算法

双向搜索算法的基本思想是同时使用上述前向搜索法和后向搜索法进行证书链的搜索.在搜索的过程中，算法每进行循环搜索一次就做一次判断，看是否存在前向搜索算法求解出的中间结果与后向搜索算法求解出的中间结果中包含着相同的元素，假如存在，则存在访问请求者拥有该权限的证书链，可以根据中间结果来构造相应的证书链;否则，不存在相应的证书链.

假设访问者U需要拥有的最小权限为r.则双向搜索算法描述如下.

(1)搜索本地访问控制列表，计算M1(r)，A1(U).M1(r)={Q|(R，Q，T) ∈L∩R⊇r}，A1(U)={U}.如果M1(r)为空集，则不存在证明访问请求者U拥有权限r的证书链，并退出.如果M1(r)∩A1(U)≠ø，则已经找到了访问请求者U拥有权限r的证书链，该证书链就是本地的访问控制条目(r，U，T).

(2) 循环计算Mi(r)，Ai(U)(i＞1).Mi(r)，Ai(U)的计算方法与前向搜索法和后向搜索法中的计算方法相同.如果Mi(r)∩Ai(U)≠ø，则已经找到访问请求者U拥有权限r的证书链，并转第(3)步执行.如果Mi+1(r)=Mi(r)，Ai+1(U)=Ai(U)且Mi(r)∩Ai(U)≠ø，则不存在访问请求者U拥有权限r的证书链.

(3)如果存在访问请求者U拥有权限r的证书链，则根据计算过程中记录的证书之间的联系，构造出相应的证书链.

在实际的应用中，由于双向搜索算法的特殊性，其搜索的效率可能比前两种搜索算法要更高一些，但实际用到的内存开销会更大一些.

3 算法的性能分析与比较

假设证书集合C有N个证书，则上述3种证书链查找算法的时间复杂度全部是O(N2).

另外，由于在整个搜索过程中，每个证书都只需要进行一次存储.所以搜索算法的空间复杂度为O(N).

同其他人提出的信任管理模型中的证书链搜索算法，例如 Li Ninghui等人［5］提出的 RT0以及其中的证书链搜索算法、Freudenthal等人提出的dRBAC模型［6］等等相比，本文提出的证书链搜索算法是基于信任度的，在实体与实体之间存在着一定的信任值，在主体对资源进行访问的时候也需要该主体对该资源的直接或间接的信任值大于某个阈值，基于此前提，在进行分布式证书链的搜索的时候，可以根据该阈值进行预处理，将那些多余的证书删除，大大提高证书搜索效率.

4 应用实例

在某个系统中本地访问控制列表如表1所示，相关的委托的集合C如图1所示，信任传递的计算采用的是文献［7］中提出的f(t1，t2)=t1*t2/100.则Tom在2011年10月能否拥有Right_1的权限?

表1 访问控制列表的格式与内容Tab.1 Format and content of the access control list

图1 支持Tom申请服务的委托Fig.1 Delegations supporting Tom's service application

根据表1和图1可以来实施相应的计算，分别使用前向搜索、后向搜索和双向搜索算法，首先进行预处理，可以将委托集合中的第4条和第6条删除，因为这两条委托记录是过期的委托.

使用前向搜索算法，可以得到如下结果:

从权限Right_1出发来查找其成员集M，可以从本地访问控制列表中找到Sailor，Kasi，Grace等用户，继而搜索委托集合，第一重循环就可以得到Kate的信任值为80，虽然通过Kate→John和John→Tom还可能搜索到Right_1到Tom的证书链，但因为Grace→Tom的信任值为90，所以已经成功地搜索到了相应的证书链，算法终止并构造出Grace→Tom的证书链.

使用后向搜索算法，可以得到如下结果:

从用户Tom出发来查找其权限集R，可以找到A集合中包含元素Grace和John，继而由于本地访问控制列表中的第3条，可以搜索到相应的证书链，算法终止并构造出Grace→Tom的证书链.

使用双向搜索算法，可以得到如下结果:

分别从权限Right_1和用户Tom出发，搜索Right_1的用户集和用户Tom的权限集，只需一重循环即可发现Grace对Right_1的权限和Grace→Tom委托，从而搜索到了相应的证书链，算法终止并构造出Grace→Tom的证书链.

可以发现，双向搜索算法效率相对较高，只需一重循环即可解决问题，但其存储开销较大，因为它需要同时存储Right_1的成员集中间结果和Tom的权限集中间结果.

5 结语

分布式环境中，结点与结点之间可以先通过信任的评估手段来获得信任度的值，继而采用基于信任度的证书链搜索算法，通过结点之间信任度的判断来实现选择性地进行相应证书链的搜索，提高搜索效率.本文给出分布式环境下证书链搜索过程中的成员集和权限集的定义，具有一定的理论价值，并给出了信任管理系统中基于信任度的证书链前向、后向和双向搜索算法，结合具体实例说明了算法的应用与实现过程.

［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］廖俊国，洪 帆，朱更明，等.基于信任度的授权委托模型［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］雷建云，崔国华，邢光林，等.可计算的基于信任的授权委托模型［J］.计算机科学，2008，35(10):73-75，85.