unmap() guaranteed to succeed?

[Marcus Brinkmann]

At Wed, 13 Dec 2006 11:51:52 +0100,
Marcus Voelp <voelp at os.inf.tu-dresden.de> wrote:
> in short: you are right. Both L4.sec and my solution have this problem. 
> Fiasco does not. Details below.

Hi Marcus,

thanks for the detailed explanation, I find them very helpful.  Also
thanks to Espen for describing Pistachio and the new implementation.
I somehow managed to miss the preorder sweep, but as you point out
there is a corresponding problem there.  I can see how locking would
change the picture.  Another concern is that the time is bounded in
principal, but depends on actions taken by subordinate processes (from
a security point of view), but my question was not about that, I think
the trade-offs there are sufficiently clear.  More comments inline.

> > ...
> > I have the feeling that this is an obvious threat scenario and thus is
> > probably addressed already, but I can't find where.  
> So far we mostly ignored this problem as far as the main-stream 
> implementations go. One of the reasons I think was that map and unmap 
> were not used by real-time tasks so their potentially unbounded 
> execution time was not much of a problem. Volkmar's Beleg discusses some 
> ideas how to solve this problem.

Is some of that material online?
 
>  From a security perspective this may really be a problem. Do you know 
> how other systems solve it? Like Eros e.g., implements immediate 
> revocation by destruction of the intermediate objects. However, 
> internally they also have a list  in which address spaces a capability 
> is mapped.

Not really.  "Removing an object" in EROS/KeyKOS means incrementing
its allocation count, which immediately invalidates all keys pointing
to the object, as long as the keys are on disk (recall we are talking
about persistent systems).  The story is a bit different for objects
in memory ("prepared"): For this case, there is a table of
indirection, and the indirection entry is invalidated.  The rest is
done at the next checkpoint by the scavenger.

The details are a bit complicated.  The costs for keeping track of
everything are swallowed up and thus amortized by the object cache
magic.  I am not sure, but it might be possible for a malicious
process to try to screw with the checkpointing mechanism, for example
by forcing early checkpoints and thus degrading the performance of the
system, but if that is a possible threat scenario or just a paranoid
feeling is difficult for me to assess at this point, and may be
very difficult to analyse.  Eventually you will run out of allocation
counts, and then you can only recover object space by a garbage
collection on the object store.

There is an article by Jonathan Shapiro about the dependency tracking
on the EROS website:

http://www.eros-os.org/design-notes/DependencyMgmt/DependencyMgmt.html

Thanks,
Marcus