At Wed, 13 Dec 2006 11:51:52 +0100, Marcus Voelp voelp@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