DRAFT: The tainting-*-proxy pattern
This draft tries to be an aid in the discussion on the cap-talk
mailing-list about the possibility of defining (and thus solving) a
confinement subset of the coordinating conspirators problem.
In this discussion I (Rob Meijer) refer to a work in progress that
on the list was named a tainting-*-proxy that could possibly
be used as an abstraction pattern that would allow such a subset to
be defined.
The Draft status
When reading this please note the following. The below setup is currently
partially unproven design. The parts that have been shown to work have
been shown to work as a multi process partial proof of concept a unix
environment.
I've attempted to translate my findings into an object type of modeling
as I believe that this makes more sense for the discussion. It is however
quite possible that I have made major mistakes in this attempt that would
invalidate the graph as drawn below. Further I am quite a bit handicapped
both a little bit in using the English language, in not being trenched in
capability lingo, and by the fact that I am an engineer not an
academic. Having said this I hope the reader will still find it useful
to try and either confirm or invalidate my bold claims that:
- A multi clearance (confinement) subset of the CC problem could be defined.
- The tainting-*-proxy is at least on its way to become an abstraction
pattern able to make this subset practically usable.
If at least one person on the list could agree with at least the first
of the two statements, maybe he could help in re-wording the below
into more proper wording.
tainting-*-proxy
In order to do confinement there are two properties that at any point
in time should be adhered to with respect to the confined. The
ss-property (no read up) and the *-property (no write down). One widely
spread misconception is that confinement mandates that any single active
object needs to be locked down to a single level in order to adhere to
the ss-property. If we define that an active object can always be promoted
to a higher clearance level (no confinement properties get violated by
such a promotion, we can effectively replace the ss-property by what we
choose to call tainting. That means that instead of statically
enforcing the *-property and the ss-property, we dynamically enforce
the *-property based on the active tainting level defined by keeping
track of the ss-property as dynamically defined by the changing state
of the active object. Thus it would be logical to name a proxy that thus
enforces the confinement properties a tainting-*-proxy.
Multiple incarnations but effectively one object
By using the tainting mechanism, an active object during its life will
only increase its clearance level and would thus potentially get stuck
at a high level overly confined by the *-property to do any effective
work. To solve this problem we need to look at what effectively gets
tainted. It is not the active object itself that gets tainted, but in fact
it is the active object its internal memory that gets tainted by the data
it (potentially) stores. This means that what we need to allow an active
object to forget, this active object may go back to a lower
tainting level. Making an active object forget is basically extremely
simple, just destroy and repawn it. But if you do so without taking
further actions, the new incarnation will effectively be just that.
There are a few issues we need to solve in order to make the new
incarnations effectively the same object:
- Forgetting must effectively be reduced to the tainted part of
the memory.
- External objects with references to the active object must maintain
valid references.
- On re-tainting previously forgotten memory can be regained.
- Incoming references may not be handled while state is
forgotten from previous invocations.
In order to accommodate this the tainting-*-proxy should provide effective
measures.
Non-Preemptive-ness during normal operations
In order to make the implementation of the tainting-*-proxy possible
and not overly complicated while at the same time retaining as much
as possible natural program flow within the proxied object, we choose
to define the tainting-*-proxy to during normal operations only use
non-preemptive re-tainting. This puts some limitations on the object being
encapsulated by the proxy. In order to accommodate 4, any incoming
invocation will need to wait on the object to be scheduled up or down
to the proper level, thus the contract between the encapsulated object
and its tainting-*-proxy will guarantee only uninterrupted (and remembered)
work for short tasks done by the encapsulated object. Please note that
this is only a design restriction not a restriction dictated by anything
conceptual, as I believe that a more complex version of the
described pattern could in theory allow for pre-emptive taint switches.
This document aims however to show the viability of defining a confinement
subset of the CC problem, not to maximize the size of this subset. For this
means the simpler pattern should suffice.
References imply clearance
In order to be able to solve problem 4 while at the same time making sure
tainting and *-property are not violated, it is essential to subject
the way of thinking about clearance to a bit of a tuning. In the here
described pattern, instead of an active object being locked down to a
single clearance level, instead any incoming or outgoing reference is
locked down to such a clearance level. This paradigm makes formal analysis
real easy. We can safely say that any data communicated over such a
reference will have a classification level equal to or lower than the
clearance level of the reference. To simplify the model and to put it in
sync with common paradigms in capability modeling, we go beyond what
is formally required by tainting and the *-property for communication of
references by requiring that the tainting-*-proxy enforces the full
separation of clearances. Although this goes a bit further than
confinement requires, it largely simplifies the model and the formal
analysis of the resulting multi level system design. Lets make a short
list of what this full separation of clearances implies:
- References can only be communicated over references with the same clearance level, resulting in a per level version of the only connectivity begets connectivity paradigm used in capability design.
- During its invocation trough a reference, only references at the same
level as the invocating reference can be used.
This paradigm will lead to a rather curious issue when looking at secrets and powers in the next section, but seems to be usable for both distinct subsets of the CC problem.
The multi clearance version of the CC problem
The CC problem is considered known to the reader, but to make a simple but incomplete sketch of the situation: Allice holds a reference that she wants to share with Bob, but she does not want Bob sharing it with Mallet. Bob and Mallet
both want Mallet to be able to use the reference, and Bob and Mallet are required to be in full communication for legitimate reasons. It is commonly believes that the CC problem has no solution. I (Rob Meijer) would like
to claim that a practically usable subset of this problem could be solved
by defining a multi clearance version of the problem definition.
Lets say that both Allice and Mallet have a reference to Bob, if as in the previous section we state that reference implies clearance, we could define
Allice her reference to Bob at a different clearance level than Mallet her reference. We have stated that clearances on different levels can not be used
together at the same time. This would stop Bob from re-delegating the
reference to Mallet, but will it stop Bob from proxying reference usage
for Mallet?
The answer to this depends on two issues:
- Does the reference pertain to a power, a secret or both?
- Does Allice her reference imply a higher or a lower clearance than
Mallets reference to Bob?
The answer to the second question might for all intuitive purposes appear to
be that Allice holding the restricted reference should have a higher
clearance than Mallet, but as it turns out this is not always the case.
In fact, if the reference pertains to a Power rather than a
Secret, Allice should have a lower clearance reference to Bob than
Mallet.
The reason for this non intuitive result lies in the fact that Bob can
remember what happened during its High references. Thus Mallet if using a Low reference
could ask Bob to use the power on her behalf, and Bob would be able
to remember once Bob would again have access to the power.
If however we give Allice the Low clearance reference to Bob and Mallet the high
clearance reference, than Bob would not be able to remember that Mallet
asked him to use the power on her behalf. Given that with secrets the
intuitive Allice High, Mallet Low would be required, any reference
to a combined secret/power must be considdered to fall outside of the
confinement solvable subset of the CC problem.
The (draft) tainting-*-proxy patern
Now that I hope to have shown the intend and limitations, lets see
if we can elaborate on how I believe the proposed requirements for
a proxy could be translated into a design. I've tried to strip out
some of the more confusing stuff that I believe to be less generic
in order to come to the basic setup that could be used for the
CC issue we are discussing here. Please keep in mind that although
the patern may still seem a bit complicated, in theory it would
be a reusable abstraction patern that could have a reusable
implementation. This means we only have to be concerned with the
abstraction and its formal validation ones.
To avoid any confusion with respect to the clearances and the power
version of the CC problem, this image shows the secret subset
being adressed. Rather than going truegh the scenario of the CC problem
within this patern, I've used the CC problem to draw the patern
in a state where Bob has gotten access to the reference form allice,
and I will describe the different objects in this picture.
Understanding how these objects would work together to solve the
apropriate subset of the CC problem is lett as an excercise to the reader.
The input proxies
As you can see in the abouve picture, each level (in this case High and Low) has its own distinct input proxy assosiated with it. Any reference to Bob
at that level of clearance will in fact be a reference to the input proxy at that level. So what are the tasks of the input proxies:
- Inform the coordinator object that an invocation at the given level is in progress.
- Delay the handling of incomming invocation untill the coordinator
indicates that Bob is or has arived at the proper tainting level equal
to level of the input proxy.
- For any invocation that transfers a reference, invoke the output
proxy factory of that level in order to hand a proxied reference to Bob.
Invoke Bob truegh the IncarnationFacade.
The output proxy factories
These objects are used by the different proxies at the given level in order to create output proxies that are proxies to any reference that Bob acumulates.
The incarnation proxies
Given that Bob will exist in many incarnations of the actual low level Bob object, the incarnation proxies proxy references to Bob that are helt by external objects in such a way that the references will keep working eventhough a new incaration of Bob has become active.
The coordinator
The coordinator object is responsible for keeping track of tainting
of the active Bob process, and for keeping track of incoming invocations
of Bob and invocations done by Bob of extenal active objects.
If Bob either indicates that he is ready to be interrupted, if Bob
explicitly violates confinement, or if Bob does not in time return
controll to the coordinator, the coordinator depending on incomming
invocations will ask the Respawner to kill and ressurect Bob.
The interuptability informer
The intinformer object is Bobs way to let the coordinator know if it is
in a state were it can safely be interrupted, that is where it can
be switched to an other tainting level, if needed by being respawned.
The respawner
The respawner object will on request by the coordinator kill and respawn
the Bob process. For this it has access to a BobFactory. Further it has the task to keep all incarnation facades informed about the thus changing reference to the active Bob object.
The scratchpad object
The scratchpad object allows Bob to transparently store most of its state
outside of the actual low level Bob object itself, that is all of its
variables including all of its references. The scratchpad will when reading or writing data consult with the coordinating about the active tainting of the Bob object. From Bobs point of view the scratchpad will abstract away access
do differently clasified (or potentialy clasified) partitions of data.
For Bob the scratchpad will mostly apear as a map.
Writing data to the scratchpad
When Bob writes to the scratchpad, the data will be written to the TmpPad.
If for any reason the Bob object violates Coordinator pollicies and the
coordinator indicates this, the values in the TmpPad will be discarded.
At the moment that Bob is about to be tainted to an other level for
legitimate reasons , the TmpPad values will get coppied to the per level
scratchpad.
Reading data from the scratchpad
For reading, the scratchpad will overlay the per level scratchpads for
each level upto the current tainting level, including the TmpPad.
If a variable is not found on the TmpPad, the scratchpad of the current
tainting level is checked, if the variable is not found there either,
one level lower is checked, etc.
Version controll for variables by Bob
Most of the time the scratchpad map abstraction works straigth forward.
There is however one particular situation where the scratchpad abstraction requires a litle help from the Bob object. The folowing scenario would be
where the trouble arises:
- Bob while tainted high sets a variable.
- Bob is brought down to low tainting and sets the same variable
without remembrance of its previous action.
- Bob returns to the high tainting level.
The problem is that the scratchpad does not posses the knowledge to
make a descission about what version of the variable is most valid.
- The newest version.
- The highest version.
This means that the scratchpad will need to be able to ask bob about these
issues. This is the only time that Bob will actualy notice that he is
moving between levels while not atempting to violate any confinement.
Usage of references on the scratchpad
When Bob atempts to use a reference on the scratchpad, the overlaying
will hapen in the opposite direction, given that access to low clearance references may violate the *-property, and accessing high clearance references may by tainting be made to not to violate the ss-property, one may think that
this auto-tainting could always be used. We must note however that while
handling an invocation itself, the invocation of high clearance references
will actualy still lead to a potential violation of the ss-propery.
If a violation is detected by checking these rules, the coordinator will
be notified, the TmpPad will be flushed, and the coordinator will bring the
Bob process down to a previous tainting level. It will be the task of the coordinator to take care of logging auditing information about attempted violations. Please note that the scratchpad only checks access to references it holds, not usage of these references.
The output proxies
Any reference that Bob holds, wheter in volatile object memory or helt by the scratchpad is proxied by an output proxy. The output proxy has two simple tasks that partialy mirror those of the input proxy.
- Check with the coordinator if the tainting level matches the clearance level of the reference.
- Indicate violation of confinement rules to the coordinator if the
levels do not match.
- If a reference is returned from an invocation, wrap this reference
with a new output proxy object.