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: 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.


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:
  1. Forgetting must effectively be reduced to the tainted part of the memory.
  2. External objects with references to the active object must maintain valid references.
  3. On re-tainting previously forgotten memory can be regained.
  4. 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: 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:
  1. Does the reference pertain to a power, a secret or both?
  2. 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:

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: The problem is that the scratchpad does not posses the knowledge to make a descission about what version of the variable is most valid. 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.