一种高效的SPKI/SDSI2.0策略分析算法

An Efficient Policy Analysis Algorithm for SPKI/SDSI2.0

信任管理方法提供了一种新的思路,弥补了传统授权机制应用于分布式系统的不足.SPKI/SDSI2.0是目前较普及的信任管理系统,系统中的每个主体都可以发放证书.在一个特定的系统状态中,系统管理员需要知道关于系统的一些"特性",如某一主体是否有权访问被保护资源、一个本地名有哪些成员等.当证书数量庞大时,这些问题需要借助一定的工具才能回答.但以前的算法均集中于对授权问题的讨论,没有考虑与名字相关的系统策略分析,且分析效率偏低.提出了一种基于逻辑的SPKI/SDSI2.0策略分析算法EPAAS,从本质上拓宽了策略分析的领域,利用它不仅可以分析SPKI/SDSI2.0的授权问题及名字问题,还可以将这两类问题结合起来对系统策略进行综合查询;此外,EPAAS将策略分析的时间复杂度由原先算法的O(n3l)降至O(n),提高了分析效率.EPAAS用标准的Datalog程序表示SPKI/SDSI2.0的系统状态,以Datalog程序的最小Herbrand模型作为它的语义,证明了该语义的可靠性.

Trust management is a mechanism for large-scale, open, distributed access control and it is flexible and safe compared with traditional methods. SPKI/SDSI2.0 is a popular trust management system at present, and each principal in it can issue policy statements. A set of SPKI/SDSI2. 0 certificates form a state of system. In a given state, many important properties need to be known and analyzed, such as whether a principal is authorized to access a protected resource？ Which principals are members of one local name？ For a specific right, who are granted？ When the number of certificates is huge, a special algorithm is needed to answer these questions. However, previous algorithms only study the problems about authorization, ignoring the policy analysis to involved names. Moreover, the efficiency of those algorithms is not high. In this paper, EPAAS （efficient policy analysis algorithm for SPKI/SDSI2.0） is presented. EPAAS expands the area of policy analysis essentially, so it can analyze properties not only about authorization and name but about integrated properties. The time complexity of query is improved from previous algorithms＇ O（n^3l） to O（n）. The logic programs are gotten based on translating each policy statement into some Datalog clauses. The minimal Herbrand model of Datalog program is used as the program＇s semantics and it can be evaluated in polynomial time. In addition, the soundness of the semantics is proved.