I have just read the notes at
http://www.mediacity.com/~norm/CapTheory/CapBits.html, and I have a few
comments on them.
I find the use of the terms "protected" and "unprotected" in the first
paragraph very confusing. I think that what is probably meant is
"partitioned" or "unpartitioned". I dislike the term "protected" because it
already has many other uses in the context of the capability discussion, and
I believe the that "partition" term captures the distinction that Norm is
trying to make. If not, I'ld be very interested to be corrected, and perhaps
the term I suggest below may be useful.
A password capability system need not keep the object identity bits in
cleartext. The password can apply to the entire capability. The fact that
the object bits were left in the clear in the Pose systems is, I think, a
flaw. It was probably motivated by a desire to simplify the memory
translation hardware, but in the context of modern processor design it's an
unnecessary simplification. Indeed, I recently had occasion to review that
paper in connection with examining a patent for prior art, and was very very
disappointed that the object bits were not protected.
There is a hybrid design that is possible, which is a cryptographic or
sparse capability system (bits exposed) in which the kernel must perform
some protection-domain-specific transformation in order to obtain the true
capability representation, such as applying a process-specific XOR late in
the game. I believe that we may consider designs of this form to be
partitioned, because the process never has access to the true representation
of the capability. This presumes that the XOR value is unknown to the
process, obviously.
Non-partitioned systems suffer from a total failure of confineability,
because it is impossible to determine whether the binary image has embedded
within it one or more capabilities that are unknown to the confinement
checker. A conservative approximation check can be done, but the cost is
probably prohibitive and the need to run this check has unfortunate
consequences for sharing of connected structures in transitive read only
form (i.e. you can no longer do so).
For the purpose of this objection, the E system does not suffer, because the
type system allows the checker to make the necessary determination.
For the purpose of this objection, a tagged memory system may or may not be
partitioned. The issue is once again the shared transitive read only
struture problem.
Indeed, as I wrote the above, it occurred to me that we have a failure of
specification. In EROS/KeyKOS, there are two simultaneous problems being
solved, and each has implications for choice of capability protection
strategy. The first might perhaps be called the "referential encapsulation
property", by which I mean that the process cannot generate bits that will
later be interpreted as a capability [I ignore number capabilities, and we
must someday think them through]. The second is transitive read-only
shareability, or what KeyKOS calls "sensory access". This is somewhat
generalized in EROS, and is further complicated by metadata indirection. A
reasonable treatment is given in the Diminish Take chapter of my
dissertation (archival paper real soon now, I promise!).
Norm has been focused on the referenctial encapsulation property, but there
is enormous leverage in the sensory access idea as well. Sensory access is
certainly not necessary, but if you remove it, you must enforce deep copy at
process instantiation. Deep copy is expensive, but worse than that it
requires a widely held means by which to compare two capabilities for
identity of their underlying representation object in order to preserve
object identity during the deep copy. That is *frought* with unfortunate
implications.
Ultimately, the most basic difficulty with password and cryptographic
capabilities is that there is no way to determine when all capabilities to
an object are gone. In EROS/KeyKOS we have not implemented GC, but I am
prepared to believe that it will prove desirable to do so in time. I even
think I can see how to avoid the covert channel issues implied by the
presence of GC. The reason to want GC is mostly for lost space recovery.
Programs do err in explicit storage management, and it is desirable to be
able to address this problem. In a "user bits are capabilities" style of
system, collection is possible but only if done conservatively, and only at
the cost of a much more complete scan of the disk (all sectors must be
examined) This strikes me as problematic.