The Fort

[Mark S. Miller]

At 10:22 PM 12/15/98 , Norman Hardy wrote:
>See <http://www.mediacity.com/~norm/CapTheory/durability.html> for recent
>elaborations on the old idea of a "dual factory" that ensures persistence
>instead of confinement.

I take it that what you mean by "persistence" in the above sentence is what 
you refer to elsewhere as "durability", and not what you refer to elsewhere 
as "persistence"?

On the eros list,
At 12:22 PM 12/16/98 , Kragen Sitaker wrote:
>On Wed, 16 Dec 1998, Ben Laurie wrote:
>> Kragen Sitaker wrote:
>> > Does this still fall under the factory patent?
>> 
>> Forgive my ignorance: what factory patent???
>
>There's a US patent covering the factory.  Norm has it linked from some
>of his web pages.

http://www.MediaCity.com/~norm/CapTheory/Patent.html or
http://patent.womplex.ibm.com/details?pn10=US04584639&s_all=1

>Shap said to me (before I read the patent) that he didn't think it
>would be a problem for implementing EROS.  I think that he's right, as
>long as we don't try to provide the services the factory provides.

Impenetrable Abstract:

Though this is not yet explained at http://www.erights.org E can do
confinement as well.  As with EROS, it does so by losing some power
compared to KeyKOS.  I've asked Norm about the two services provided by
KeyKOS confinement but not E confinement:  Hole checking and Sensory
capabilities.  About hole checking, he said that, in practice, this extra
power wan't used by KeyLogic or its customers.  Confinement without hole
checking would have been perfectly adequate.  It remains to be seen whether
E can make do without Sensory capabilities.

Btw, the patent was filed Dec 23, 1983 and issued April 22, 1986.  If it
goes 17 years from issuing or 20 years from filing, then we only have to
wait till 2003.  (Now that I know how slow internet time really is, that
doesn't seem so far away anymore.)  Or is it 20 years from issuing?  Anyone
know what the story is?

--------------------------------------------------------------------------

In order to understand KeyKOS confinement, let's build up to it in stages.

Hypothetical factory design stage 1:

Bob writes a proprietary program, BobProg, that he wishes to enable Alice
to use but not read.  Alice wishes to use this program on proprietary data
of hers that she wishes Bob to not read.  Fortunately, they know a trusted
intermediary, the FactoryFactory.  Bob hands the FactoryFactory the
compiled BobProg program + any initial pure data, asking it to make a
BobProgFactory, which he hands to Alice.  The stage 1 factory accepts only
pure data from Bob, not capabilities.

Alice asks the FactoryFactory whether the BobProgFactory is indeed a
Factory (ie, something the FactoryFactory made).  Assume the FactoryFactory
has some way of answering this question in a trustworthy fashion (this is
more of a trick than it seems, but is true in KeyKOS, EROS, and E).
Assured that this is indeed a Factory of some sort, Alice asks it to
produce its yield.  If you think of the factory as a class, Alice has asked
for an instance of the class.

This yield starts with BobProg as its code + any initial pure data provided
by Bob, but has no initial capabilities other than those provided by Alice
in her instantiation request.  Since the yield has no abilities to
communicate in or out, other than those provided by Alice, Alice considers
it to be confined.  The "confinement check" in this story is simply the
check that BobProgFactory is indeed a Factory.

In stage 1 Bob provided data, but not the memory for the data.  The memory
was allocated and written to once by the FactoryFactory in making the
BobProgFactory.  Afterwards, this memory is exclusively held by
BobProgFactory and its yield, and never written to.  Since the yield obey
the untrusted BobProg program, either they are given a separate copy or
they are given read-only access.  This memory is therefore effectively
immutable.  If we ignore the deallocation issue, our stage 1 story provides
both confinement and durability.


Stage 2: Encapsulated Factory Graphs

Let's say Alice wishes to create a confined service for use by Carol, just
as Bob has created a confined service for use by Alice.  However, the
program Alice wishes to write makes use of the functionality provided by
BobProgFactory.  Alice has no access to the BobProg code, and so cannot
incorporate it into the code used to make the AliceProgFactory.  In stage
2, we extend the description provided to the FactoryFactory to make
AliceProgFactory so that it can contain pointers to other factories.  The
yield of the AliceProgFactory is then born with these as initially
accessible capabilities, and can use them to create confined objects it can
use.  Just as Carol cannot read the code of AliceProg, Carol also cannot
find out that the yield of AliceProgFactory uses yield from BobProgFactory.
 By the sane token, Alice never knew whether BobProgFactory's yield uses
yet other factories.

The actual KeyKOS protocol doesn't provide the yield description all at
once in asking to create a factory.  Rather, it first gets a blank factory,
then installs into it the description of the yield, and finally seals it --
turning it into an instantiable factory.  This has the advantage that one
can form cyclic encapsulated factory graphs.

At this point, the one abstraction still provides both confinement and
durability.


Stage 3: Adding Sensory Capabilities

To be filled in later, or hopefully by Norm, Jon, Dean or some other
interested party (hint hint).


Stage 4: Hole Checking

Alice doesn't necessarily care whether the yield of the BobProgFactory has
capabilities to non-confined entities.  Rather, she care whether these
objects have capabilities *other than those she approves of*.  The factory
creation logic now allows Bob to provide arbitrary capabilities as the
initial endowment of the yield of BobProgFactory, since these might be ones
that Alice does approve of.  These capabilities which are not guaranteed
confined on previous grounds are called "holes".

To determine whether the yield of BobProgFactory is confined *as far as she
is concerned*, she performs a "hole check" on BobProgFactory.  A hole check
involves a HoleChecker encapsulating a table of approved holes.  The
HoleChecker implementation is in bed with the Factory implementation (see
Norm on synergy http://www.MediaCity.com/~norm/CapTheory/Synergy.html ),
and in KeyKOS actually happens to be a Factory.  The hole check asks the
question

"Are there any holes in the transitive factory graph starting at
BobProgFactory not on the approved list?"

The answer is only yes or no, because more detail would violate
encapsulation.  Since the question is now relative to an approved list, we
are no longer asking about an object property of the factory.  The Joule
language http://www.agorics.com/joule.html clarifies this by using
"confinement" only for the objective property (as dealt with in stages #1,
#2, and #3) as opposed to "discretion" for the more flexible relative
property (as dealt with in stage #4).

Since Alice has to provide the approved hole list, what generality is lost
if we skip discretion, and instead have Alice provide to the yield of a
confined factory a name-table of some sort from which the yield can obtain
those holes Alice approves of?  Alice doesn't necessarily have access to
the list of approved holes, merely a HoleChecker that contains an
encapsulated list.  How can this come about?  The HoleChecker could have
come from, for example, Alice's administrator.

I asked Norm if the extra flexibility of hole checking, or discretion of
confinement, was ever useful in practice at KeyLogic or any of its
customers.  If I recall, the answer was no.

--------------------------------------------------------------------------

E doesn't have factories, sensory keys, or hole checking.  Speaking
somewhat in advance of the current implementation or documentation, E
instead has a set of declared "audited properties" of an object expression.
 The property corresponding to the above stages #1 and #2 is "transitively
immutable".

To declare an object expression
http://www.erights.org/doc/elang/blocks/defObject.html transitively
immutable, the "transitive immutability" auditor must determine, by
examining the expression, that the objects it evaluates to cannot change
their own state, and can only contain references to instances of object
expressions that are themselves declared transitively immutable.  An
instance of an object expression that has passed this audit is itself
marked as having the audited property.  Given such an instance, there is a
trustworthy check that it carries the mark.  (Implementationally, the mark
will be on the object's vtable rather than the object.)

Intervat references and external i/o or device capabilities are not
considered immutable.  With these definitions, a transitively immutable
object is like a confined and durable factory, corresponding to stages #1
and #2.  The same transitive auditing & marking logic plausibly could give
us checkable sensory capabilities, taking us into stage #3, but first I'd
like to hear a case that we'll need those.  I'd love for "transitive
immutability auditors" to remain all our TCB support for confinement.


	Cheers,
	--MarkM