[cap-talk] Capabilities and Freedom vs. Safety

[Toby Murray]

On Wed, 2007-07-25 at 13:04 -0400, Jonathan S. Shapiro wrote:
> The "safety property" is:
> 
>    Given an initial configuration of a system, and an arbitrary choice
>    of right 'r', object 'o', and subject 's', is it possible in
>    principle to prevent subject 's' from obtaining right 'r' on object
>    'o'.
> 
> The answer (summarizing HRU's formal results):
> 
>   In the general case this question is undecidable. It is always
>     decidable if the system configuration is finite.
> 
>   In cap systems it is decidable in O(|S+O|) (that is: in linear time)
>     and the answer is "yes, we can prevent that". This is true even if
>     the system is infinite.

Is this second result from SW or from take-grant systems or what
formalism? Certainly, HRU didn't examine restricting their semantics so
as to match those for capability systems.

> 
>   In RBAC systems the answer is "yes, we can prevent that". I do not
>     know (I haven't looked) whether the RBAC case is decidable for
>     infinite systems, but it is certainly decidable for all finite
>     systems, which is good enough. I do not know the order statistic
>     on the decision procedure.
> 
>   For all other known protection systems, the problem is decidable in
>     the finite case and the answer is "no, we cannot prevent that."

Where does this last result come from? That seems like a pretty bold
claim.