Synergy
Aqua Regia is a mixture of nitric acid and hydrochloric acid.
Neither of these two reagents dissolves gold.
Aqua regia dissolves gold.
Synergy is a general pattern in capability systems.
It takes several forms:
rights amplification, sibling communication, sealing or branding — even the equality operator.
Synergy is a phenomenon where a program that holds two capabilities can do something by bringing these two capabilities together that it cannot do with them separately.
In the systems we know the only way to bring capabilities together is to send one to the other in a message, or alternatively to send both to the some other object, but then that other object must either send one to the other or send both to a yet more fundamental object.
By “fundamental” I mean older in the sense described here.
This paragraph needs much rework to match these issues.
“Bringing together” may not be critical.
Unfortunately the following is heavily into Keykos details.
We need a more accessible introduction to synergy.
Synergy Nexus
We consider first an example of rights amplification in Keykos.
(See this for a more generic introduction to amplification.)
A domain service key to a particular domain D is stronger than a start key to D.
This is because there is an order on the domain service key that yields the start key to the same domain and there are things that you can do with the domain service key that you can’t do with the start key.
By invoking the particular domain creator that made the domain one can retrieve the domain service key from the start key by virtue of the fact that the brand of the domain matches the brander of the particular creator.
This operation is an example of rights amplification; given the weaker start key we have amplified those rights to include the rights conveyed by the stronger domain service key (to the same domain!).
(The synergy is between the domain creator key and the start key.)
Most programs cannot perform this amplification for they lack a key to this particular domain creator.
There are two important questions to answer:
- why is this a good design?
- how is it accomplished?
Why is rights amplification a good idea?
This in turn breaks down into two questions:
- is it harmful?
- is it useful?
Harm from some feature may occur when some program is able to do something that it would not be able to do without the feature.
That this is harmful is the peculiar perspective of the design of secure systems.
The argument that rights amplification is harmless is subtle.
Without loss of generality we take the domain example above.
An exclusive holder of a domain creator key may choose to retain each domain service key ever returned by the creator.
With this collection the holder can perform the amplification function without synergy as follows:
- Accept a start key,
- For each retained domain service key, produce all 256 possible start keys,
- Compare each of these with the given start key for equality,
- Return the domain service key that produced the matching start key.
We have thus shown how the amplification can be done without the feature.
There is thus no harm in the feature if comparing keys for equality is possible.
The reader may have felt a flaw in the above argument.
Without the amplification feature two holders of the same domain creator key are unable to amplify start keys for domains from the other holder.
This may be important if the two do not trust each other.
The presence of the amplification feature in the domain creator means the domain creators should not be shared across trust boundaries.
There are other reasons for this policy however and it is not expensive.
This is generally the case with rights amplification.
Some will see another flaw here: “How do you compare keys for equality?”.
Such an operation sends two keys to a primitive comparator (via a key to the comparator).
Indeed this is a form of synergy.
Capability system designers in good standing differ on how widely access to a comparator should be spread.
Here is a description of a solution for a large class of synergy problems without EQ?.
As to whether synergy is useful there are several uses.
Here are three:
- If a domain obeys a program with a bug it may be important to be able to debug the program starting from the state of the broken domain.
This requires the domain service key to the domain.
The start key for the domain is likely to be available and held by whoever gathers evidence that the code is wrong.
The domain service key is generally not required after domain launch, however.
With rights amplification the domain creator together with the start key can reproduce the required domain service key at less cost than always keeping the domain service key.
This pattern means that the whoever holds the domain creator key must cooperate with whoever has the start key to the guilty domain.
In the factory pattern this may be two agents with limited trust of each other.
This separation must be respected lest the goals of the factory be violated.
- It is often required that an object be able to communicate with siblings in ways that others cannot.
One example is money objects.
Mondex cards use a combination of obscurity and crypto to communicate between themselves to prevent counterfeiting Mondex money.
Capability systems with synergy can do the same without crypto.
Here is a sample design in Keykos.
Another example of sibling communication is to optimize computation by taking advantage of state representation.
It might indeed be more than an optimization such as proprietary data formats.
- Sometimes two properties of an object are desired and for each property there is some agent within the system, denoted by a key that you hold, that is trusted to ensure that property.
In Keykos you may hold a factory key that you trust to produce objects that are competent to perform some particular form of data processing, and another agent able, given such a factory key, to vouch for the enforced limits beyond which such processed data can get to.
By sending the first key to the second such dual assurance may be produced.
Neither body of code trusted to ensure these two properties, is a subset of the other.
How is synergy accomplished in Keykos?
How does the domain creator produce the domain service key upon the rights-amplification order more easily than the above procedure?
The domain creator holds the domain tool which is a one-of-a kind object implemented by the kernel.
An order on the domain tool takes a start key and another key b.
If b matches the key (is equal to) in slot 0 of the node, D, designated by the start key, then the domain tool returns the node key for D.
Key b is the domain creator’s brander and the key in slot 0 is the brand.
The domain creator then produces, with the domain tool, again, the domain service key that designates D, which is returned to the caller of the domain creator.
In summary the domain creator performs synergy by invoking a synergy function of a more primitive object.
In general this pattern continues until an object, such as a kernel object, is reached that is not constrained by capability discipline.
Such programs are generally entrusted to enforce such discipline.
Sibling Communication
In Keykos, if someone asks you to do some work he may pass you access to a space-bank B which will provide working storage for the job.
You may want assurance that this bank plays by the known rules of space banks.
You should already have a bank T that you trust and who you can ask about B.
To do this you invoke T sending B.
If B is a real bank T will be able to determine this and tell you so, in which case you can trust that B will behave as T except for allocating storage on your customer’s nickel, but storage that your customer cannot see.
To do this the bank retains from birth a key to its creator.
When asked to vouch for a sibling it asks its creator to whom the question is merely a matter of rights amplification.
The creator may return a special start key to the sibling bank so that inter bank messages can pass efficiently with the recipient knowing that the message is from a true sibling.
Banks can then engage in bank-talk.
C++ code of some class can directly access members of another object of the same class.
This provides efficient primitive sibling communication.
The checking is a compile-time function.
Many modern languages, such as OCaml, have this function with real protection.
The first hint of synergy that I know in the literature is sealing in James H. Morris’ “Protection in Programming Languages”, CACM, 16(1):15-21, 1973.
That paper suggested that language scope rules could solve real security problems.
In particular Morris introduced a pair of matched functions, seal and unseal.
These were created by matched pairs by a commonly available service.
If S and U are a matched pair then for all x, U(S(x)) = x.
S(x), on the other hand, is useless to anyone without access to U.
It is much like public key crypto without all of the arithmetic.
It is a particularly simple primitive upon which many other synergy functions can be based.
Scenario
You want to distribute to some netherworld, some sort of access to compound values that you make, yet limit the netherworld to accessing your values only by calling you.
Often this can be accomplished by exporting a function which you write and which holds onto the value by merely binding a variable, local to that function, to that value.
Code in the netherworld invokes that function for access and your code applies whatever access rules you want and no other access to your value exists from the netherworld.
But if you want your values to denote sets, you may want to provide code that forms the union of two such values X & Y.
If the netherworld sends either X to Y, or Y to X then your code gets control but either way one of the abstracted sets is still abstracted, even from you.
If on the other hand you could put your values each in a sealed box, as proposed in 1973 by Morris, the netherworld could call you, passing two such boxes, you could unseal both, produce the union efficiently, return the sealed result.
(See this.)
The netherworld may need to guard these abstract values and some part there may hold a box with one of your values.
For its purposes the box is as good as the represented value, but it may be a secret from other parts of the netherworld.
The box thus provides to the netherworld capability access to your abstracted values.
See how to define types of synergy in Scheme starting from “eq?” and a proposed new Scheme primitive called the safe for efficient Scheme synergy.
Stiegler’s code
See Stiegler’s solution using ordinary lexical scoping with persistent functions, and a Scheme module.
WeakMap
Does the weak map or weak pointer provide synergy?
I think so.
They are fairly heavy weight, however.
They serve sibling communication poorly.
JavaScript has the Weak Map which provides run-time synergy.
OCaml has weak arrays which also provide run-time synergy.
Keykos has the KID which does not return keys.
Run-time vs. Compile-time
An important distinction is whether the facility is run-time or compile-time.
In languages with the class concept exemplified by C++, there is in effect a fixed finite set of seals or brands and a permanent assignment to code of which seals or brands the code may wield.
Indeed there is no attributable cost to that facility.
The mint maker is an example of a situation where a dynamic supply of seals or brands are needed.
There are many others in Keykos.
I do not exclude the possibility that some platforms could justify both.
Cookies
And then there the cookies of http which are used as if they were sealed.
I conclude from the Grant Matcher exercise that the eq? form of synergy is necessary in Keykos.
Sealer synergy does not suffice for a preemptively scheduled system.
The claim: those who wish to exclude eq? really want to be able to always introduce forwarders without being exposed by eq?
My suspicion is that eq? is harmless in this situation because he would invoke is harmless in this situation does not hold bot caps by virtue of membrane logic.
Much synergy without eq?