[cap-talk] HRU and its implications for the decidability of safety in commodity OSs

[Toby Murray]

On the EROS wikipedia page, it says

"Of greater practical importance, safety has been shown to be false/ 
/for all of the primitive protection mechanisms shipping in current 
commodity operating systems (see HRU)."

Here, HRU refers to "Protection in Operating Systems" by Harrison, Ruzzo 
and Ullman, in Communications of the ACM, 19(8), August 1976.

I just read HRU and that's not how I interpreted their undecidability 
result. Being a seminal paper in the area, I would very much like to 
udnerstand this paper properly, particularly its implications. If anyone 
could indulge me here for a discussion of this paper, I would be very 
much obliged.

HRU describes a what I see as a very general model for protection 
systems. This model is loosely based on the traditional access matrix 
but does not specify any rules for how the matrix should be updated etc. 
The definition of these rules is what would determine the difference 
between an object-capability system and say Unix file permissions, I 
think. When wanting to model a particular protection system in this 
model, you have to define your own rules for how the matrix evolves over 
time.

They show that there is no general algorithm that can decide the safety 
of any protection system you can build on top of this model (which would 
include the object-capability model and Unix file permissions, for 
example, because I believe you can model both of these on top of their 
model). The way they show this is by showing that you can model a Turing 
machine on top of their general model. Solving the halting problem for 
the Turing machine is then equivalent to deciding safety.

To me, the argument is then: if we can't decide the safety for a 
particular system (a Turing machine) built on top of our model, then we 
obviously can't find an algorithm to decide safety for the model itself 
(which is obviously more general).

I don't see how this result applies to current commodity operating 
systems anymore than it does to EROS, for example. By my reading of the 
paper, the result does not apply to access-control list systems in 
general (which I believe is the connection to "current commodity 
operating systems" that the wikipedia entry is getting at). If we take 
Unix file permissions, for example, they are a specialisation of HRU's 
general model. Safety might be undecidable for Unix file permissions (I 
don't know). From my reading of HRU, they don't examine whether safety 
is decidable in such a system (although they do show how to model it -- 
or at least Unix file permissions as they existed in the 1970s, well 
before my time :) ).

Can anyone tell me how HRU indicates that the protection system of (say) 
Unix file permissions is undecidable? If this fact can be deduced from 
HRU, I really would like to understand how.

Thanks all,
Toby

-- 
Toby Murray
Advanced Computer Capabilities Group
Information Networks Division
DSTO, Australia

IMPORTANT: This e-mail remains the property of the Australian Defence
Organisation and is subject to the jurisdiction of section 70 of the
Crimes Act 1914. If you have received this e-mail in error, you are
requested to contact the sender and delete the e-mail.