Databases Reference
In-Depth Information
There are several restricted variants of PolicyMaker's proof of compliance
problem that are decidable with various complexities. A polynomial variant
can be obtained by imposing two complementary restrictions. The first of
these is the monotonicity of the assertions themselves. The second involves
restricting the resources available to the compliance checker and denying ac-
cess should any resource limit be exceeded. The authors call it
locally bounded
proof of compliance
(LBPOC), which actually subsumes four subordinate re-
strictions. The first limits the time used to execute each assertion to be a
polynomial in the size of the blackboard's content. The second bounds by a
constant the number of acceptance records that can be written to the black-
board. The third bounds by a constant the size of acceptance records written
on the blackboard. The fourth bounds by a constant the length of the sequence
of assertions that make up the proof of compliance. PolicyMaker provides no
assistance to the policy author in ensuring that assertions do not violate these
restrictions.
There are other drawbacks to basing assertion semantics on program ex-
ecution semantics rather than on some more declarative approach, such as
logic or relational algebra. To understand the meaning of a program-based
assertion, a human must mentally simulate its various executions, which can
be dicult to do correctly, and the human may find it quite dicult to un-
derstand how the effects of different assertions will combine when executed.
Furthermore, as we discuss further in later sections, this approach to policy
definition provides no assistance in answering questions such as where one
can find credentials that may be relevant to evaluating a given query, or in
answering more general questions, such as “who are all the principals that are
authorized for this resource?”
In addition to becoming more declarative, credentials in later TM systems
typically identify a credential subject as well as the credential issuer. The
subject is the principal to which the credential is issued and that is charac-
terized by the credential. Explicitly identifying the subject greatly facilitates
determining which credentials might be useful at various points in the proof
of compliance as it is under construction.
SPKI/SDSI [18] represents authorizations and delegations in structured
formats with dedicated fields. Issuers, subjects, delegation bit and authoriza-
tion tag are specified separately and can easily be recognized by the evalu-
ator. The evaluation is of authorization queries is based on
composition
,a
basic operation that takes two valid, compatible certificates as input and out-
puts another valid certificate. The evaluation algorithm uses composition to
compute a closure in a bottom-up manner [18]. The resulting set contains all
certificates that can be derived by composition from the given input set. The
time complexity of the evaluation algorithm is polynomial in the size of the
input set. The closure process must be repeated whenever any certificate is
added, expired or revoked, so it is not well suited to be used with a very large
and frequently changed certificate pool.
