An Efficient Policy Analysis Algorithm for SPKI/SDSI2.0

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.