Erights - User contributions [en]

Proposed Asynchronous Control Flow Operators

2007-11-20T19:49:56Z

DavidHopwood: /* Later */ typo

TODO possibly there should be per-operator pages.

This page describes some not implemented asynchronous control flow operators that could simplify creation of asynchronous application. The intial set of operators is based on experience of implementing the AsyncObjects framework and Sebyla project design.

== Later ==
This is an extremely simple construct. But is useful when it is requited to execute code in this or other vat at some later time. In AsyncObjects this constructs is implemented using AsyncAction class, and it was used quite a lot in applications.
<pre>
“later” ( “(” <vatHandle> “)” )? “->” “{“
<code>
“}”
</pre>
When code is executed in other vat, the runtime checks that code closes only over deep frozen or pass by copy objects. If vat is not specified, the code is scheduled to be executed at later turn in this vat. The vatHandle is an expression that evaluates to capability of executing actions on the vat.

==Using==

This is a very simple construct that helps with resource management. The syntax is like the following:
<pre>
“using” “(“ ( (“def” <varName> “:=” )? <eventualOpenExpression> )+ “)” “->” “{“
<statements>
“}”
</pre>
The operator is executed as the following:
#All resources are opened in the specified order. If expression returns promise, the next expression is not executed before first one complete. If <varName> is specified for resource, the resolved resource is assigned to it and it can be used in subsequent expressions and <statements>.
#If opening of some resource fails, the proposed result of operator is that failure.
#Statements are executed, the proposed result of operator is value of last expression. If the result is promise, the operator waits until it is resolved.
#All opened connections are closed, in reverse order. It includes connections that has not been named. If some close operations fail, the most top level one is returned.
Example:
<pre>
using(def r1 := factory1<-openConnection, def r2 := factory2<-openConnection, lock<-lockEnter()) -> {
doSomething(r1,r1); // assuming that lock is being held
}
</pre>
The constructs expands to the following:
<pre>
when(def r1 := factory1<-openConnection()) {
when(def r2:= factory2<-openConnection()) {
when( def tmpVar := lock<-lockEnter()) {
doSomething(r1,r1);
} finally {
tmpVar<-close();
}
} finally {
r2<-close();
}
} finally {
r1<-close();
}
</pre>

==Seq==

The are several form of seq operator.
The basis form is the following.
<pre>
“seq” (“def” <varName> “:=”)? “{“
<statements-1>
“}” ( “then” (“def” <varName> “:=”)? “{“
<statements-i>
“}” ) * ( “catch” “(“ <exceptionVar> “)” “{“
<catchStatements>
“}” )? (“finally” “{“
<finallyStatements>
“}”)?
</pre>
The code is executed like the following:
#The code in <statements-i> is executed sequentially. The next code block is executed only if promise returned from previous code block is resolved. If the block yields near value, the next block is executed on the same turn.
#The result of operator is the value of the last block.
#If some of blocks fails, the next blocks are not executed, and control is passed to the catch section and the result of operator will be the result of executing catch statement. If there is no catchSection, the operator fails with expression.
#If there is a finally statement, it is executed after last block or after catch statement. If it fails, the entire seq expression fails with the same exception.
Example:
<pre>
seq def a := {
doA()
} then {
doSomething(a)
} catch(e) {
print(e)
throw e
} finally {
cleanup()
}
</pre>
Example is expanded as the following:
<pre>
when(someTempResolvedPromise) {
def aVow := {
doA();
}
when (def a := aVow) {
doSomething(a);
}
} catch(e) {
print(e)
throw e
} finally {
cleanup()
}
</pre>
There is also a short form:
<pre>
“seq” “(“ (“def” <varName> “:=” )? <eventualExpression> ( “,” (“def” <varName> “:=” )? <eventualExpression> )* “)”
</pre>
The comma separated expressions are executed in sequence. The named values are available at later expressions.
The are three loops forms:
<pre>
“seq” “do” “{“
<statements>
“}” “while” “(“ <eventualExpressions> “)”

“seq” “while” “(“ <eventualExpressions> “)” “{“
<statements>
“}”

“seq” “for” <pattern> “in” <collection> “{“
<statements>
“}”
</pre>
The semantics is the same as for normal loops. The next iteration starts only after previous completed.
TODO it might be useful to keep intermediate results of previous iteration and to make them available in the body of the loop and conditions. On other hand, it is quite easy to use basic seq operator to achieve the same result.
TODO “seq for” needs support for eventual iterators.
==All==
This operator allows execution of eventual expressions in parallel. The basic form is the following:
<pre>
“all” “{“
<expression>
“}” ( “and” “{“
<expression>
“}” )+
</pre>
The short form is the following:
<pre>
“all” “(“ <expression> ( “,” <expression> )+ “)”
</pre>
Semantics is the following:
#All expressions starts to be executed.
#If all expressions completed successfully, a list of results is returned.
#If at least one expression fails, an exception that contains generated results and failures is generated.

Example:
<pre>
all {
first()
} and {
second()
}
</pre>
It is translated like the following:
<pre>
{
var wereFaults = false;
var results = makeFlexList();
results.setSize(2)
var faults = makeFlexList();
faults.setSize(2)
def vow1 := seq def r: = {
first()
} then {
results[0] := r
} catch(e) {
wereFaults = true
faults[0] := e
null
}
def vow2 := seq def r: = {
second()
} then {
results[1] := r
} catch(e) {
wereFaults = true
faults[1] := e
null
}
when (def v1:=vow1, def v2:=vow2) {
if(wereFaults) {
throw makeAllFault(results,faults)
} else {
results.toConsList()
}
}
}
</pre>
There is also a loop form that returns conslist of results.
<pre>
“all” “for” <pattern> “in” <collection> “ “{“
<expression>
“}”
</pre>

Walnut/Secure Distributed Computing/Capability Patterns

2007-08-14T15:36:25Z

DavidHopwood: /* Pet Names and Forgery among partially trusted participants */

[[Category:Walnut|4]]

===Capability Patterns===

====Facets====

As discussed in the minChat security review, facets are objects that act as intermediaries between powerful objects and users that do not need (and should not be granted) its full power. We saw a facet in use in the audited version of the eChat program, where the chatFacet. was interposed between the chatController and the remote chat participant. Here is a little general-purpose facet maker:

<pre>

<nowiki># E sample
/**
* <param> target is the underlying powerful object
* <param> allowedMethods is a map. The key is a method name, the value
* is the set of allowed numbers of arguments. So ["receive" =>[0, 2].asSet()]
* would allow the receive method, with either 0 or 2 arguments, to be forwarded.
**/
def makeFacet(target, allowedMethods) {
def filteringFacet {
match [verb, args] {
if (allowedMethods.maps(verb) &&
allowedMethods[verb].contains(args.size())) {
return E.call(target, verb, args)
}
}
}
return filteringFacet
}
def chatController
def chatFacet := makeFacet(chatController, ["receive"=>[1].asSet(),
"receiveFriend"=>[1].asSet()])
</nowiki>

</pre>

Facets of this type can be retrofitted onto an existing system. We did this with very little effort for minChat with the chatFacet, but the technique works for far more complicated problems as well. The capability-secure windowing toolkits that ''E'' has placed on top of Swing and SWT uses facetization as the main tool.

Facets can be made much more sophisticated in their restrictions on access to their underlying object. You can make a facet that logs requests and sends email when certain methods are called. In an SEC-regulated stock exchange facet, you might wish to grant the capability to make a trade only from 9AM to 3PM excluding weekends and holidays.

One interesting example is the use-once facet, which allows the holder of the facet to use the facet only one time. For example, this version of a chatReceiver only allows a single message to be sent:

<pre>

<nowiki># E sample
def onceOnlyReceiver(baseChatController) {
var chatController := baseChatController
def onceOnlyReceiver {
to receive(text) {
chatController.receive(text)
chatController := null
}
}
}</nowiki>

</pre>

This version will throw an exception back to the sender of a second message.

It can be tempting in a facet to suppress a couple of powerful methods in the underlying powerful object and delegate the rest.

<pre>

<nowiki># E sample
def powerfulObject {
to doPowerfulOperation() {
#do powerful operation
}
to doWeak1() {}
to doWeak2() {}
to doWeak3() {}
#....
to doWeak99() {}
}
def badFacet extends powerfulObject {
to doPowerfulOperation() {
#do nothing, no forwarding for the powerful operation, but forward everything else
}
} </nowiki>

</pre>

''Avoid this''. For a facet to remain secure during maintenance, it should never just delegate by default. If a new method is added to a powerful object (in this example, suppose powerfulObject is updated with a new method, doPowerful2()), it should not be exposed through the facet by default: rather, the facet must by default not expose it.

This risk can be exhausting to avoid, but it is always dangerous to accept. The first version of the capability windowing toolkit on Swing suppressed the handful of dangerous methods in the Java version 1.3 of Swing rather than explicitly allowing the safe methods, of which there were thousands. Within 30 days, the entire system was broken: the Java 1.4 Beta included hundreds of new, security-breaking methods. The only saving grace was that we had always known that the first version, thrown together in haste on weekends, was just a proof-of-principle and would have to be replaced. We just hadn't appreciated how soon replacement would be required.

====Revocable Capabilities====

If you wish to give someone restricted access to an object with facets, it is quite likely you will want to revoke access at some point as well.

The simplest way of making a capability revocable is to use a transparent forwarder that includes a revocation method:

<pre>

<nowiki># E sample
def revocableCapabilityMaker(baseCapableObject) {
var capableObject := baseCapableObject
def forwarder {
to revoke() {capableObject := null}
match [verb, args] {E.call(capableObject, verb, args)}
}
return forwarder
}</nowiki>

</pre>

Note that, even though the forwarder is nominally delegating all method invocations (except revoke()) to the capableObject, we cannot use the ''extends'' keyword to capture the behavior. "Extends" creates an immutable reference, so the fact that the capableObject is a var wouldn't allow you to revoke the delegating behavior. Instead we use the match[verb, args] pattern.

Capability revocation, like facet forwarding, can be based on complex sets of conditions: revoke after a certain number of uses, revoke after a certain number of days. This example uses a simple manual revocation. Indeed, this version is too simple to work reliably during system maintenance and upgrade, and a more sophisticated pattern is generally recommended:

<pre>

<nowiki># E sample
def makeCapabilityRevokerPair(baseCapableObject) {
var capableObject := baseCapableObject
def revoker {
to revoke() {capableObject := null}
}
def forwarder {match[verb, args] {E.call(capableObject, verb, args)}}
return [forwarder, revoker]
}
def powerfulObject {
#...big powers
}
def [power, revoker] := makeCapabilityRevokerPair(powerfulObject)</nowiki>

</pre>

In this pattern, the authority of the object and the authority to revoke are separated: you can hand the power to revoke to an object you would not trust with the authority itself. Also, the separate revoker can itself be made revocable.

====Sealers and Unsealers====

A sealer/unsealer pair makes it possible to use untrusted intermediaries to pass objects safely. Use the sealer to make a sealed box that can only be opened by the matching unsealer. E has built-in support for sealer/unsealer pairs:

<pre>

<nowiki>? def makeBrandPair := <elib:sealing.makeBrand>
# value: <makeBrand>

? def [sealer, unsealer] := makeBrandPair("BrandNickName")
# value: [<BrandNickName sealer>, <BrandNickName unsealer>]

? def sealedBox := sealer.seal("secret data")
# value: <sealed by BrandNickName>

? unsealer.unseal(sealedBox)
# value: "secret data"
</nowiki>

</pre>

If you hold the unsealer private, and give the sealer away publicly, everyone can send messages that only you can read. If you hold the sealer private, but give the unsealer away publicly, then you can send messages that recipients know you created, i.e., you can use it as a signature. If you are thinking that this is much like a public/private key pair from public key cryptography, you are correct, though in E no actual encryption is required if the sender, recipient, brand maker, and sent object all reside in the same vat.

While the Brand is built-in, it is possible to construct a sealer/unsealer pair maker in E without special privileges. The "shared variable" technique for making the maker is interesting, and because the same pattern appears in other places (such as the Notary/Inspector, coming up next), we demonstrate it here:

<pre>

<nowiki># E sample
def makeBrandPair(nickname) {
def noObject{}
var shared := noObject
def makeSealedBox(obj) {
def box {
to shareContent() {shared := obj}
}
return box
}
def sealer {
to seal(obj) {return makeSealedBox(obj)}
}
def unsealer {
to unseal(box) {
shared := noObject
box.shareContent()
if (shared == noObject) {throw("invalid box")}
def contents := shared
shared := noObject
return contents
}
}
return [sealer, unsealer]
}
</nowiki>

</pre>

The variable "shared" normally contains the value "noObject", which is private to a particular sealer/unsealer pair and so could never the the actual value that someone wanted to pass in a sealed box. The unsealer tells the box to shareContent, which puts the content into the shared variable, from which the unsealer then extracts the value for the invoker of the unseal method. In a conventional language that used threads for concurrency control, this pattern would be a disaster: different unseal requests could rumble through, overwriting each others' shared content. But by exploiting the atomicity of operational sequences enabled by promise pipelining, this peculiar pattern becomes a clean solution for this, and several other security-related operations.

====Vouching with Notary/Inspector====

Suppose Bob is the salesman for Widget Inc. He persuades Alice to buy a widget. Bob hands Alice a Widget Order Form with a money-receiving capability. It is important to Bob that Alice use the form he gives her, because this particular form (which Bob got from Widget Inc.) remembers that Bob is the salesman who should get the commission. It is important to Alice that she know for sure that, even though she got the order-form from Bob, this is really a Widget Inc. order form, and not something Bob whipped up that will transfer her money directly to his own account. In this case, Alice wants to have Widget Inc. vouch for the order-form she received from Bob. She does this using an Inspector that she gets directly from Widget Inc. The Inspector is the public part of a notary/inspector pair of objects that provide verification of the originator of an object. To be vouchable, the orderForm must implement the startVouch method as shown here:

<pre>

<nowiki># E sample
####### Widget Inc. software #####

#vouching system
#returns a private notary that offers a public inspector
#throws problem if the object being vouched is not vouchable
def makeNotary() {
def nonObject {}
def unvouchedException(obj) {throw(`Object not vouchable: $obj`)}
var vouchableObject := nonObject
def inspector {
to vouch(obj) {
vouchableObject := nonObject
try {
obj.startVouch()
if (vouchableObject == nonObject) {
return unvouchedException(obj)
} else {
def vouchedObject := vouchableObject
vouchableObject := nonObject
return vouchedObject
}
} catch err {unvouchedException(obj)}
}
}
def notary {
to startVouch(obj) { vouchableObject := obj}
to getInspector() {return inspector}
}
return notary
}

#create Widget Inc's notary
def widgetNotary := makeNotary()

#Order form maker
def makeOrderForm(salesPerson) {
def orderForm {
# .... methods for implementing orderForm
to startVouch() {widgetNotary.startVouch(orderForm)}
}
return orderForm
}

#publicly available inspector object
#(accessible through a uri posted on Widget Inc's web site)
def WidgetInspectionService {
to getInspector() {return widgetNotary.getInspector()}
}

##### bob software #####

#scaffold for sample
def getOrderFormFromBob() {return makeOrderForm("scaffold")}

########## Alice's software to vouch for the order form she received from Bob #####

def untrustedOrderForm := getOrderFormFromBob()
def inspector := WidgetInspectionService.getInspector()
def trustedOrderForm := inspector.vouch(untrustedOrderForm)</nowiki>

</pre>

====Proof of Purchase====

"Proof of Purchase" is the simplest of a series of capability patterns in which the goal is not to transfer an authority, but rather to show someone that you have the authority so that they can comfortably proceed to use the authority on your behalf. In Proof of Purchase, the requester of a service is demonstrating to the server that the client already has capability that the server is being asked to use. Unlike the more sophisticated upcoming Claim Check patterns, the proof of purchase client is not concerned about giving the server an excess authority.

An interesting example of Proof of Purchase is [http://www.erights.org/javadoc/java/awt/Component.html Component.transferFocus(fromComponentsList, toComponent)] found in the tamed Swing package. In standard Swing, the holder of any panel reference can steal the focus (with component.requestFocus()). Hence any keystrokes, including passwords, can be swiped from wherever the focus happens to be by sneaking in a focus change. This is a clear violation of POLA. You should be able to transfer focus from one panel to another panel ''only if you have references to both panels''. If you have a reference to the panel that currently has the focus, then you can never steal the focus from anyone but yourself.

A natural-seeming replacement for component.requestFocus() would be requestFocus(currentFocusHolder). It was decided during the taming of Swing, however, that this would be breach-prone. If Alice transferred to Bob, not a panel itself, but rather a simple transparent forwarder on that panel, Alice could collect authorities to other panels whenever Bob changed focus.

Since we had a convenient trusted third party available that already had authority over all the panels anyway (the javax.swing.Component class object), we used the "proof of purchase" pattern instead. The globally available Component.transferFocus method accepts two arguments:

* a list of panels that the client believes to contain, somewhere in their subpanel hierarchies, the focus
* the target panel that should receive the focus

In the common case where a whole window lies inside a single trust realm, the client can simply present a reference to the whole window and be confident that the focus will be transferred.

The interesting thing about Component.transferFocus is that the recipient does not actually need the client's authority to reach the component that already has the focus. The Component class already has that authority. The client must send the authority merely to prove he has it, too.

====Basic Claim Check====

A common activity that brings security concerns into sharp focus is the delicate dance we perform when we use a car valet service. In this situation, we are handing the authority over our most precious and costly possession to a teenager with no more sense of responsibility than a stray cat. The whole valet system is a toothsome exercise in POLA.

In this example, we focus on the sequence of events and trust relationships involved in ''reclaiming'' our car at the end of the evening. The participants include the car owner, the valet service itself, and the random new attendant who is now on duty.

We have already chosen, for better or for worse, to trust the valet service with a key to the car. As the random new attendant comes running up to us, we are reluctant to hand over yet another key to the vehicle. After all, this new attendant might actually be an imposter, eager to grab that new Ferrari and cruise out over the desert. And besides, we already handed the valet service a key to the car. They should be able to use the key they already have, right?

Meanwhile, the attendant also has a trust problem. It would be a career catastrophe to serve up the Ferrari from his parking lot if I actually own the dented 23-year-old Chevy Nova sitting next to it.

In the physical world, we use a ''claim check'' to solve the problem. We present to the attendant, not a second set of car keys, but rather, a proof that we have the authority that we are asking the attendant to use on our behalf.

<pre>

<nowiki># E sample
def claimMgr := {
def carKeys := [].asMap().diverge()
def claimMgr {
to makeClaim(car) :any {
# the claim object has no interesting
# properties except it has
# a unique unforgeable identity
def claim {}
carKeys[claim] := car
return claim
}
to reclaim(claim) :any {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
}
}
}

def attendant {
#return a claim check when car is parked
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}

def car {}
def carOwner := {
var claim := null
def carOwner {
to letAttendantParkCar() :void {
claim := attendant.parkCar(car)
println(claim)
}
to getCarFromAttendant() :void {
println(attendant.retrieveCar(claim))
}
}
}

carOwner.letAttendantParkCar()
carOwner.getCarFromAttendant()
</nowiki>

</pre>

====Basic Claim Check Default Behavior====

Suppose the owner of the car loses the claim check. He can still prove he owns the car by presenting another key. In software, this situation would be comparable to the situation in which the owner hands the attendant a direct reference rather than handing the attendant merely the claim check. The car owner has violated his own security, but it is hard to visualize situations in which this is not a reasonable argument to pass to express his desire. We can cover this case with a small modification to the claimMgr's reclaim method:

<pre>to reclaim(claim) :any {
try {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
} catch prob {
if (carKeys.contains(claim)) {
return claim
} else {throw(prob)}
}
}</pre>

What should the claimMgr return if the carOwner hands in a car reference for reclaim, if the car is not actually in the claimMgr's parking lot? The answer depends on the application, but such a situation violates the expectations of all the participants sufficiently that throwing an exception seems the safest choice.

====NonTransferable Claim Check====

We are far from done with claim checks. A careful car owner will not actually hand his claim check to the parking lot attendant. Rather, he will merely show the claim check to the attendant. After all, if you hand the claim check over to an imposter, the imposter can turn around and hand the claim check to a real attendant, pretending that he is the owner of the car.

The problem is somewhat different in cyberspace. The good news is, in cyberspace the attendant doesn't return a reference to the car just because you hand him the claim check. Instead, he merely performs the action you ask of him with the car. This set of actions is limited by the attendant's willing behavior. So the claim check is not as powerful a capability as the car itself. But it can still be a powerful capability. And the bad news is, in cyberspace, you can't just "show" it to the attendant. You have to give it to him.

Here we demonstrate a "nontransferable" claim check. This claim check can be handed out at random to a thousand car thieves, and it does them no good. The trick is, before handing over the claim check, the owner inserts into the claim check a reference to the individual he is treating as an attendant. The ClaimMgr compares the person to whom the owner handed the claim, with the attendant who eventually hands the claim to the claimMgr . If these two people are the same, then the owner handed the claim directly to the attendant. Otherwise, there was an intermediary party, and the request should not be honored.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def valetService := {
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def claimMgr {
to makeClaim(car) :any {
def transferableClaim {
to makeNontransferableClaim(intendedRecipient) :any {
return claimSealer.seal([car, intendedRecipient])
}
}
return transferableClaim
}
to reclaim(claim, actualRecipient) :any {
def [car, intendedRecipient] := claimUnsealer.unseal(claim)
if (actualRecipient == intendedRecipient) {
return car
} else {throw("claim not transferable, invalid attendant")}
}
}
def valetService {
to authorizeAttendant(attendant) :void {
attendant.setClaimMgr(claimMgr)
}
}
}

def makeAttendant() :any {
def claimMgr
def attendant {
to setClaimMgr(mgr) :void {bind claimMgr := mgr}
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim, attendant)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}
return attendant
}

def legitAttendant := makeAttendant()
valetService.authorizeAttendant(legitAttendant)

def carThief {
to parkCar(car) :any {
return println ("Ha! stole the car")
}
to retrieveCar(claim) :void {
try {
legitAttendant.retrieveCar(claim)
println("Ha! didn't get car, but got control")
} catch prob {println(`rats! foiled again: $prob`)}
}
}

def carOwner := {
def car{}
var claim := null
def carOwner {
to letValetPark(attendant) :void {
claim := attendant.parkCar(car)
println(claim)
}
to letValetRetrieve(attendant) :void {
def noTransferClaim := claim.makeNontransferableClaim(attendant)
println(attendant.retrieveCar(noTransferClaim))
}
}
}

carOwner.letValetPark(legitAttendant)
carOwner.letValetRetrieve(carThief)
carOwner.letValetRetrieve(legitAttendant)
</nowiki>

</pre>

Note an important implication in this pattern: the ClaimMgr winds up in a position to accumulate references to all the entities a claim check holder treats as an attendant. In this example, the ClaimMgr gets a reference to the carThief as a result of the carOwner's casual handing out of claim checks. It seems unlikely that the ClaimMgr can harm the carOwner's interests with this reference, but in other circumstances the reference may not be so harmless. To reduce our risk exposure to the alleged attendants to whom we hand the claim check, we have increased our risk exposure to the ClaimMgr.

Note also the limitations on the nontransferability of this pattern. The carOwner can still transfer authority, either by handing someone a reference to the car, or by handing out the transferableClaim from which nontransferableClaims can be made. The nontransferability is voluntarily chosen by the carOwner. You can't prevent people from delegating their authority, and even this pattern doesn't change that fact.

====Oblivious Claim Check: Loan Officer Protocol====

{| style="float: right; width: 2in; border-style: inset; border-width: 3;background-color: #FFFF99; font-size:80%"
|
Voluntary Oblivious Compliance, or VOC, was pioneered by the [http://www.erights.org/history/client-utility.html Client Utility System]. VOC is a field only recently recognized by the capability-security community as an important area of exploration; the claim check patterns here are early fruit of that research. VOC is irrelevant in the classical cypherpunk view of the world, where every person is a rugged individualist making all his own authority-granting decisions with little regard for other people's issues. In a world filled with corporations, governments, and other policy-intensive organizations, however, it is an area of real value even though it is not really a security matter. Why is it not security? We consider it beyond the scope of "security" for a simple but compelling reason: it is not enforceable. Unenforceable security in cyberspace has been proven, over and over again in the course of the last decade, to be a joke played on all the participants. VOC states in its very name the limits of its applicability: it only works with volunteers. Don't be fooled into thinking this is security.
|}

Let us consider a somewhat different problem. Suppose that different attendants are trusted to handle different cars by the valet service. One valet has a motorcycle license and parks all the Harleys. Another has a multi-engine pilot's license and parks all the Boeing 747s. Of course, the one with the motorcycle license is a teenager who has always wanted to try his hand at parking a 747, and knows his lack of experience is not a problem. In this situation, each attendant has a different set of authorities at his command; just because you hand your claim check to a legit attendant doesn't mean the valet service thinks it would be a good idea to let that attendant drive your vehicle. A more generalized way of stating the problem is, in this case the authorities of the individual receivers of the claim checks vary, and management of the individual receiver's authorities is beyond the scope of what the ClaimManager should be trying to figure out. After all, the individuals know all their own authorities; it would be poor design (and unmaintainable at scale) for the ClaimManager to try to duplicate this information.

This situation, while not a part of the real-world valet service problem, has a significant area of application in cyberspace. This area is ''Voluntary Oblivious Compliance'', or VOC. Let us consider a more sensible example. Alice works for HPM, and Bob works for Intil. HPM and Intil are often competitors, but Alice and Bob are working on a joint project from which both companies expect to profit handsomely. The Official Policy Makers of HPM have identified a number of documents which can be shared with Intil, and indeed have forwarded to Intil references to the allowed docs. Alice wants to refer Bob to a particular HPM document, but ''only if sharing the document is allowed'' under the HPM policy. In this case, the VOCclaimCheck that Alice sends to Bob demands that Bob demonstrate to HPM's ClaimMgr that he already has authority on the document before fulfilling the claim. To prove his authority, Bob sends to the ClaimMgr all the HPM doc authorities he has (i.e., the list of docs HPM handed to Intil). Only if both Alice and Bob already have authority on the object does Bob get the document. This is sometimes called the Loan Officer Protocol, in reference to the old adage that a loan officer will not give you the loan unless you first prove that you don't need it.

Since bob can't get the reference unless he proves he doesn't need it, we can now see why this is a pattern of Voluntary Oblivious Compliance. It is voluntary, because Alice could just send Bob the document and circumvent the system. And it is oblivious, because Alice doesn't need to know whether a document can be shared with Bob before sending it.

Going back to the parking lot attendant who wants to park the 747, he has to demonstrate to the ClaimManager that he has the keys to the 747 before the Claim Manager will let him go for it. The owner of the 747 is much relieved.

Humorous as the 747 example might be, we will now switch to the scenario with Alice, Bob, HPM, and Intil for our sample code. The basic strategy is that the ClaimMgr not only examines the claim check from Alice, it also examines the list of authorities that Bob hands over to see if any of Bob's authorities match the one inside Alice's claim.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def HPMDocClaimMgr {
to makeClaim(doc) :any {
return claimSealer.seal(doc)
}
to matchClaim(claim, listOfCandidates) :any {
def doc := claimUnsealer.unseal(claim)
for each in listOfCandidates {
if (doc == each) {return each}
}
throw("No match from claimCheck to candidate auths")
}
}

def intilSharedDocs := [def doc1{}, def doc2{}, def doc3{}]

def bob {
to lookAtHPMDoc(claim) :void {
try {
def doc := HPMDocClaimMgr.matchClaim(claim, intilSharedDocs)
println(`reading doc: $doc`)
} catch prob {
println(`can't read: $claim`)
}
}
}

def alice {
to sendDoc(doc, recipient) :void {
def claim := HPMDocClaimMgr.makeClaim(doc)
recipient.lookAtHPMDoc(claim)
}
}
alice.sendDoc(doc2, bob)
alice.sendDoc(def doc4{}, bob)
</nowiki>

</pre>

The oblivious claim check pattern can require scattering even more authority to the winds than the nontransferable claim check. The recipient of the claim check (bob) needs to have all the authorities that alice might give to him, rather than merely the ones she actually does give to him. And the trusted third party who matches the claim check against the list of possibilities (the HPMDocClaimMgr) gets to accumulate authority to everything that bob thinks alice might be trying to send him. In the example scenario, this is just fine. But some care is required.

====Oblivious Claim Checks as Guards====

An elegant style of using VOC claim checks is to set up the pattern as a pair of guards. Alice would use the ClaimCheck guard to send a reference to Bob, and Bob would use the CheckedClaim guard, with the list of candidate references, to receive the authority. We will show the implementation of the BuildGuards ClaimCheck and CheckedClaim guards in [[Walnut/Advanced_Topics|Advanced Topics]] when we talk about writing your own guards, but their usage would appear as follows:

<pre># E syntax
def bob {
to lookAtHPMDoc(doc :CheckedClaim[intilSharedDocs]) :void {
if (!E.isBroken(doc)) {
println(`reading doc: $doc`)
} else {println(`can't read: $claim`)}
}
}

def alice {
to sendDoc(doc, recipient) :void {
recipient.lookAtHPMDoc(doc :ClaimCheck)
}
}</pre>

The ClaimCheck guard coerces the doc into a sealed representation of itself. The CheckedClaim guard unseals the claim and matches it against the authorities in the intilSharedDocs list. As a guard, it is better style to return a broken reference than to throw an exception if something goes wrong. In the parameter guard, if an exception were thrown, the recipient would have no chance to do anything with the problem, the exception would be thrown directly back to the sender before the recipient was even aware there was an issue.

====Oblivious NonTransferable Claim Check====

It is possible to make nontransferable oblivious claim checks as well. We leave the code as an exercise for the reader.

====Powerbox Capability Manager====

The powerbox pattern collects diverse elements of authority management into a single object. That object, the ''powerbox'', then becomes the arbiter of authority transfers across a complex trust boundary. One of the powerbox's most distinctive features is that it may be used for dynamic negotiations for authority during operation. The less trusted subsystem may, during execution, request new authorities. The powerbox owner may, in response to the request, depending on other context that it alone may have, decide to confer that authority, deny the authority, or even grant the request authority after revoking other authorities previously granted.

The powerbox is particularly useful in situations where the object in the less trusted realm does not always get the same authorities, and when those authorities may change during operation. If the authority grant is static, a simple emaker-style authorization step suffices, and a powerbox is not necessary. If the situation is more complex, however, collecting all the authority management into a single place can make it much easier to review and maintain the extremely security-sensitive authority management code.

Key aspects of the powerbox pattern include:

* A powerbox uses strict guards on all arguments received from the less trusted realm. In the absence of guards, even an integer argument received from untrusted code can play tricks: the first time the integer-like object (that is not really an integer) is asked to "add", it returns the value "123"; but the second time, it returns the value "456", with unpredictable (and therefore insecure) results. An ":int" guard on the parameter will prevent such a fake integer from crossing into your realm.
* A powerbox enables revocation of all the authorities that have been granted. When you are done using a less trusted subsystem, the authorities granted to it must be explicitly revoked. This is true even if the subsystem is executing in your own vat and you nominally have the power to disconnect all references to the subsystem and leave the subsystem for the garbage collector. Even after being severed in this fashion, the subsystem will still exist for an unbound amount of time until the garbage collector reaches it. If the authorities it has received have not been revoked, it can surprise you with its continued operations, and continued use of authority. Not all kinds of objects in the Java API can be made directly revocable at this time, because an ''E'' revocable forwarder cannot be used in all the places where an actual authority-carrying Java object is required. For example, the untrusted object may want to create a new image from an url. The natural way of doing this would be to call the Java Icon class constructor with (url) as the argument. But if an E forwarder were handed to this class constructor, the constructor would throw a type exception. Different solutions to such impedence mismatches with the Java type system are required in different situations. For the icon maker, it might be acceptable to require that the untrusted object read the bits of the image from the url (through a revocable forwarder) and then convert the bits into an icon.
* A new powerbox is created for each subsystem that needs authorities from within your trust realm. If a powerbox is shared across initiations of multiple subsystems, the powerbox may become the channel by which subsystems can illicitly communicate, or the channel by which an obsolete untrusted subsystem can interfere with a new one. When the old untrusted subsystem is discarded, its powers must all be revoked, which necessarily implies that a new subsystem will need a new powerbox.

In the following example, the less trusted object may be granted a Timer, a FileMaker that makes new files, and a url. The object may request a different url in the course of operations, in which case the powerbox will ask the user for authorization on the objects's behalf; the old url is revoked, and the new one substituted, so that the object never has authority for more than one url at a time. The object that operates the powerbox may revoke all authorities at any time, or it may choose to revoke the Timer alone. Finally, the operator of this powerbox may, for reasons external to the powerbox's knowledge, decide to grant an additional authority during operations, an authority whose nature is not known to the powerbox.

<pre>
# E sample
# The authorized url may change during operations, so it is a var
def makePowerboxController(optTimer,
optMakeFile,
var optUrl,
optMakeUrl,
makeDialogVow) {

# In the revokers map, the object being revoked is the key, the revoker
# is the value. Note it is the actual object, not the forwarder to the
# object, that is the key.
var revokers := [].asMap()

# when a revokable forwarder is made, the revoker is automatically
# placed in the map of revokers
def makeRevokableForwarder(object) :near {
var innerObject := object
def revoker {
to revoke() {innerObject := null}
}
revokers with= (object, revoker)
def forwarder {match [verb, args] {return E.call(innerObject, verb, args)}}
return forwarder
}

# makeFileFacet is exposed to less trusted realm; guard the path it receives
# This simple file facet only supplies 2 methods that return immutables
# If the file handed out mutable objects, such as streams, these would have
# to be wrapped with revokableForwarders as well.
def makeFileFacet(path :String) :near {
def theFile := optMakeFile(path)
def fileFacet {
to getText() :String {theFile.getText()}
to setText(text :String) {theFile.setText(text)}
}
return makeRevokableForwarder(fileFacet)
}

# makeFile is actually handed to the less trusted object
# It is either null or a revokable forwarder for makeFileFacet
# In other words, makeFile is a revokable maker of revokable file facets
def makeFile
if (optMakeFile == null) {
bind makeFile := null
} else {
bind makeFile := makeRevokableForwarder(makeFileFacet)
}

# Like the file facet, this url facet only supports methods that return
# immutables.
def makeRevokableUrlFacet(optUrl) :near {
if (optUrl == null) {
return null
} else {
def urlFacet {
to getBytes() :pbc {optUrl.getBytes()}
}
return makeRevokableForwarder(urlFacet)
}
}

# Return a vow for a new url
# Use dialog with user to determine if new url should be granted
# Vow resolves to null if anything goes wrong
def makeRevokableUrlVow := {
def makeUrlVow(requestedUrl :String, why :String) :vow {
def urlDialogVow :=
makeDialogVow("Url Request",
`<html>
Confined Object requesting url for this reason:$why
</html>`,
requestedUrl,
["Grant", "Refuse"])
return when (urlDialogVow) -> {
if (urlDialogVow.getButton() == "Grant") {
optUrl := optMakeUrl(urlDialogVow.getText())
makeRevokableUrlFacet(optUrl)
} else {null}
} catch prob {null}
}
return makeRevokableForwarder(makeUrlVow)
}

var caps := [].asMap()
caps with= ("TIMER", makeRevokableForwarder(timer))
caps with= ("FILEMAKER", makeFile)
caps with= ("URL", makeRevokableUrlFacet(optUrl))

def powerbox {

# any of these capabilities may be null, i.e., all are optional
# in a powerbox, strictly at the whim of the powerbox operator
# who created the powerboxcontroller and the powerbox
to optCap(key :String) :any {return caps.get(key, null)}

# When the less trusted object requests a new url, the
# old url is immediately revoked, and the promise for the
# new url is substituted
# If the powerbox has revokedAll, any attempt to requestUrl
# will throw an exception back to the untrusted object
# The "why" parameter is the less trusted object's justification
# for needing the url
to requestUrl(requestedUrl :String, why :String):vow {
if (optUrl != null) {revokers[optUrl].revoke()}
def revokableUrlVow := makeRevokableUrlVow(requestedUrl, why)
caps with= ("URL", revokableUrlVow)
return revokableUrlVow
}
}

def powerboxController {
to revokeAll() {
for each in revokers {each.revoke()}
}
to revokeTimer() {revokers[timer].revoke()}
# Confer an additional capability during execution
to conferCap(key, cap) {
caps with= (key, makeRevokableForwarder(cap))
}
to getPowerbox() {return powerbox}
}
}

# now, show how to create a powerbox and hand it to an untrusted object

def makeUntrustedObject(powerbox) {
def timer := powerbox.optCap("TIMER")
def urlVow := powerbox.requestUrl("http://www.skyhunter.com")
def untrustedObject {
#...
}
return untrustedObject
}

def powerboxOperator() {
def makeDialogVow {#...construct dialog vow
}
# use real objects, not nulls, in typical operation, though nulls are valid arguments
def controller := makePowerboxController(null,
null,
null,
null,
makeDialogVow)
def powerbox := controller.getPowerbox()
def untrusted := makeUntrustedObject(powerbox)
# later, confer an additional authority
def special
controller.conferCap("SPECIAL", special)
# when done with the untrusted object, revoke its powers
controller.revokeAll()
}
</pre>

Both the file facet and the url facet restrict the user to methods that return immutables. If these facets returned mutables, like streams, then those mutables would also have to be wrapped in revokable forwarders. In the general case, this requires the use of a membrane. write section on membranes, and link

====Petnames and Forgery among partially trusted participants====

E's encrypted authenticated references ensure that random attackers get no traction trying to break into your distributed system. As mentioned in the earlier minChat audit, this means that all interesting break-ins will be made by "insiders", i.e., people who have been granted some capabilities inside your system. We have talked so far about low-level attacks that attempt to acquire or use inappropriately conveyed authority. At a higher conceptual level, people can try to present themselves as someone else and get your user to intentionally, but erroneously, grant other information or capabilities.

minChat dodged this problem because it is a 2-person chat system: the person at the other end of the line will have difficulty convincing your user he is someone else, because your user knows the one and only person given the URI (because he used PGP encryption as described earlier to ensure that only one person got it). But in a multi-person chat system, Bill could try to pretend to be Bob and lure your user into telling him Bob's secrets.

There is no single all-purpose solution to this risk. However, one critical part of any specific solution must be this: Do not allow the remote parties to impose their own names for themselves upon your user.

[[Petnames]]

The general solution is to use ''petnames'', i.e., names your user chooses for people, regardless of how those people might name themselves. Of course, it is reasonable to allow the other people to propose names to your user (called ''nicknames''), but the user must make the final decision. The user must also be able to change her mind at a later date, when her list of participants grows to include not only Bob Smith but also Bob Jones, and she must disambiguate the pet name "Bob" she had for Smith.

The general layout of such a petname setup might be as follows:

petname sample

Walnut/Secure Distributed Computing/Capability Patterns

2007-08-14T15:30:27Z

DavidHopwood: /* Pet Names and Forgery among partially trusted participants */

[[Category:Walnut|4]]

===Capability Patterns===

====Facets====

As discussed in the minChat security review, facets are objects that act as intermediaries between powerful objects and users that do not need (and should not be granted) its full power. We saw a facet in use in the audited version of the eChat program, where the chatFacet. was interposed between the chatController and the remote chat participant. Here is a little general-purpose facet maker:

<pre>

<nowiki># E sample
/**
* <param> target is the underlying powerful object
* <param> allowedMethods is a map. The key is a method name, the value
* is the set of allowed numbers of arguments. So ["receive" =>[0, 2].asSet()]
* would allow the receive method, with either 0 or 2 arguments, to be forwarded.
**/
def makeFacet(target, allowedMethods) {
def filteringFacet {
match [verb, args] {
if (allowedMethods.maps(verb) &&
allowedMethods[verb].contains(args.size())) {
return E.call(target, verb, args)
}
}
}
return filteringFacet
}
def chatController
def chatFacet := makeFacet(chatController, ["receive"=>[1].asSet(),
"receiveFriend"=>[1].asSet()])
</nowiki>

</pre>

Facets of this type can be retrofitted onto an existing system. We did this with very little effort for minChat with the chatFacet, but the technique works for far more complicated problems as well. The capability-secure windowing toolkits that ''E'' has placed on top of Swing and SWT uses facetization as the main tool.

Facets can be made much more sophisticated in their restrictions on access to their underlying object. You can make a facet that logs requests and sends email when certain methods are called. In an SEC-regulated stock exchange facet, you might wish to grant the capability to make a trade only from 9AM to 3PM excluding weekends and holidays.

One interesting example is the use-once facet, which allows the holder of the facet to use the facet only one time. For example, this version of a chatReceiver only allows a single message to be sent:

<pre>

<nowiki># E sample
def onceOnlyReceiver(baseChatController) {
var chatController := baseChatController
def onceOnlyReceiver {
to receive(text) {
chatController.receive(text)
chatController := null
}
}
}</nowiki>

</pre>

This version will throw an exception back to the sender of a second message.

It can be tempting in a facet to suppress a couple of powerful methods in the underlying powerful object and delegate the rest.

<pre>

<nowiki># E sample
def powerfulObject {
to doPowerfulOperation() {
#do powerful operation
}
to doWeak1() {}
to doWeak2() {}
to doWeak3() {}
#....
to doWeak99() {}
}
def badFacet extends powerfulObject {
to doPowerfulOperation() {
#do nothing, no forwarding for the powerful operation, but forward everything else
}
} </nowiki>

</pre>

''Avoid this''. For a facet to remain secure during maintenance, it should never just delegate by default. If a new method is added to a powerful object (in this example, suppose powerfulObject is updated with a new method, doPowerful2()), it should not be exposed through the facet by default: rather, the facet must by default not expose it.

This risk can be exhausting to avoid, but it is always dangerous to accept. The first version of the capability windowing toolkit on Swing suppressed the handful of dangerous methods in the Java version 1.3 of Swing rather than explicitly allowing the safe methods, of which there were thousands. Within 30 days, the entire system was broken: the Java 1.4 Beta included hundreds of new, security-breaking methods. The only saving grace was that we had always known that the first version, thrown together in haste on weekends, was just a proof-of-principle and would have to be replaced. We just hadn't appreciated how soon replacement would be required.

====Revocable Capabilities====

If you wish to give someone restricted access to an object with facets, it is quite likely you will want to revoke access at some point as well.

The simplest way of making a capability revocable is to use a transparent forwarder that includes a revocation method:

<pre>

<nowiki># E sample
def revocableCapabilityMaker(baseCapableObject) {
var capableObject := baseCapableObject
def forwarder {
to revoke() {capableObject := null}
match [verb, args] {E.call(capableObject, verb, args)}
}
return forwarder
}</nowiki>

</pre>

Note that, even though the forwarder is nominally delegating all method invocations (except revoke()) to the capableObject, we cannot use the ''extends'' keyword to capture the behavior. "Extends" creates an immutable reference, so the fact that the capableObject is a var wouldn't allow you to revoke the delegating behavior. Instead we use the match[verb, args] pattern.

Capability revocation, like facet forwarding, can be based on complex sets of conditions: revoke after a certain number of uses, revoke after a certain number of days. This example uses a simple manual revocation. Indeed, this version is too simple to work reliably during system maintenance and upgrade, and a more sophisticated pattern is generally recommended:

<pre>

<nowiki># E sample
def makeCapabilityRevokerPair(baseCapableObject) {
var capableObject := baseCapableObject
def revoker {
to revoke() {capableObject := null}
}
def forwarder {match[verb, args] {E.call(capableObject, verb, args)}}
return [forwarder, revoker]
}
def powerfulObject {
#...big powers
}
def [power, revoker] := makeCapabilityRevokerPair(powerfulObject)</nowiki>

</pre>

In this pattern, the authority of the object and the authority to revoke are separated: you can hand the power to revoke to an object you would not trust with the authority itself. Also, the separate revoker can itself be made revocable.

====Sealers and Unsealers====

A sealer/unsealer pair makes it possible to use untrusted intermediaries to pass objects safely. Use the sealer to make a sealed box that can only be opened by the matching unsealer. E has built-in support for sealer/unsealer pairs:

<pre>

<nowiki>? def makeBrandPair := <elib:sealing.makeBrand>
# value: <makeBrand>

? def [sealer, unsealer] := makeBrandPair("BrandNickName")
# value: [<BrandNickName sealer>, <BrandNickName unsealer>]

? def sealedBox := sealer.seal("secret data")
# value: <sealed by BrandNickName>

? unsealer.unseal(sealedBox)
# value: "secret data"
</nowiki>

</pre>

If you hold the unsealer private, and give the sealer away publicly, everyone can send messages that only you can read. If you hold the sealer private, but give the unsealer away publicly, then you can send messages that recipients know you created, i.e., you can use it as a signature. If you are thinking that this is much like a public/private key pair from public key cryptography, you are correct, though in E no actual encryption is required if the sender, recipient, brand maker, and sent object all reside in the same vat.

While the Brand is built-in, it is possible to construct a sealer/unsealer pair maker in E without special privileges. The "shared variable" technique for making the maker is interesting, and because the same pattern appears in other places (such as the Notary/Inspector, coming up next), we demonstrate it here:

<pre>

<nowiki># E sample
def makeBrandPair(nickname) {
def noObject{}
var shared := noObject
def makeSealedBox(obj) {
def box {
to shareContent() {shared := obj}
}
return box
}
def sealer {
to seal(obj) {return makeSealedBox(obj)}
}
def unsealer {
to unseal(box) {
shared := noObject
box.shareContent()
if (shared == noObject) {throw("invalid box")}
def contents := shared
shared := noObject
return contents
}
}
return [sealer, unsealer]
}
</nowiki>

</pre>

The variable "shared" normally contains the value "noObject", which is private to a particular sealer/unsealer pair and so could never the the actual value that someone wanted to pass in a sealed box. The unsealer tells the box to shareContent, which puts the content into the shared variable, from which the unsealer then extracts the value for the invoker of the unseal method. In a conventional language that used threads for concurrency control, this pattern would be a disaster: different unseal requests could rumble through, overwriting each others' shared content. But by exploiting the atomicity of operational sequences enabled by promise pipelining, this peculiar pattern becomes a clean solution for this, and several other security-related operations.

====Vouching with Notary/Inspector====

Suppose Bob is the salesman for Widget Inc. He persuades Alice to buy a widget. Bob hands Alice a Widget Order Form with a money-receiving capability. It is important to Bob that Alice use the form he gives her, because this particular form (which Bob got from Widget Inc.) remembers that Bob is the salesman who should get the commission. It is important to Alice that she know for sure that, even though she got the order-form from Bob, this is really a Widget Inc. order form, and not something Bob whipped up that will transfer her money directly to his own account. In this case, Alice wants to have Widget Inc. vouch for the order-form she received from Bob. She does this using an Inspector that she gets directly from Widget Inc. The Inspector is the public part of a notary/inspector pair of objects that provide verification of the originator of an object. To be vouchable, the orderForm must implement the startVouch method as shown here:

<pre>

<nowiki># E sample
####### Widget Inc. software #####

#vouching system
#returns a private notary that offers a public inspector
#throws problem if the object being vouched is not vouchable
def makeNotary() {
def nonObject {}
def unvouchedException(obj) {throw(`Object not vouchable: $obj`)}
var vouchableObject := nonObject
def inspector {
to vouch(obj) {
vouchableObject := nonObject
try {
obj.startVouch()
if (vouchableObject == nonObject) {
return unvouchedException(obj)
} else {
def vouchedObject := vouchableObject
vouchableObject := nonObject
return vouchedObject
}
} catch err {unvouchedException(obj)}
}
}
def notary {
to startVouch(obj) { vouchableObject := obj}
to getInspector() {return inspector}
}
return notary
}

#create Widget Inc's notary
def widgetNotary := makeNotary()

#Order form maker
def makeOrderForm(salesPerson) {
def orderForm {
# .... methods for implementing orderForm
to startVouch() {widgetNotary.startVouch(orderForm)}
}
return orderForm
}

#publicly available inspector object
#(accessible through a uri posted on Widget Inc's web site)
def WidgetInspectionService {
to getInspector() {return widgetNotary.getInspector()}
}

##### bob software #####

#scaffold for sample
def getOrderFormFromBob() {return makeOrderForm("scaffold")}

########## Alice's software to vouch for the order form she received from Bob #####

def untrustedOrderForm := getOrderFormFromBob()
def inspector := WidgetInspectionService.getInspector()
def trustedOrderForm := inspector.vouch(untrustedOrderForm)</nowiki>

</pre>

====Proof of Purchase====

"Proof of Purchase" is the simplest of a series of capability patterns in which the goal is not to transfer an authority, but rather to show someone that you have the authority so that they can comfortably proceed to use the authority on your behalf. In Proof of Purchase, the requester of a service is demonstrating to the server that the client already has capability that the server is being asked to use. Unlike the more sophisticated upcoming Claim Check patterns, the proof of purchase client is not concerned about giving the server an excess authority.

An interesting example of Proof of Purchase is [http://www.erights.org/javadoc/java/awt/Component.html Component.transferFocus(fromComponentsList, toComponent)] found in the tamed Swing package. In standard Swing, the holder of any panel reference can steal the focus (with component.requestFocus()). Hence any keystrokes, including passwords, can be swiped from wherever the focus happens to be by sneaking in a focus change. This is a clear violation of POLA. You should be able to transfer focus from one panel to another panel ''only if you have references to both panels''. If you have a reference to the panel that currently has the focus, then you can never steal the focus from anyone but yourself.

A natural-seeming replacement for component.requestFocus() would be requestFocus(currentFocusHolder). It was decided during the taming of Swing, however, that this would be breach-prone. If Alice transferred to Bob, not a panel itself, but rather a simple transparent forwarder on that panel, Alice could collect authorities to other panels whenever Bob changed focus.

Since we had a convenient trusted third party available that already had authority over all the panels anyway (the javax.swing.Component class object), we used the "proof of purchase" pattern instead. The globally available Component.transferFocus method accepts two arguments:

* a list of panels that the client believes to contain, somewhere in their subpanel hierarchies, the focus
* the target panel that should receive the focus

In the common case where a whole window lies inside a single trust realm, the client can simply present a reference to the whole window and be confident that the focus will be transferred.

The interesting thing about Component.transferFocus is that the recipient does not actually need the client's authority to reach the component that already has the focus. The Component class already has that authority. The client must send the authority merely to prove he has it, too.

====Basic Claim Check====

A common activity that brings security concerns into sharp focus is the delicate dance we perform when we use a car valet service. In this situation, we are handing the authority over our most precious and costly possession to a teenager with no more sense of responsibility than a stray cat. The whole valet system is a toothsome exercise in POLA.

In this example, we focus on the sequence of events and trust relationships involved in ''reclaiming'' our car at the end of the evening. The participants include the car owner, the valet service itself, and the random new attendant who is now on duty.

We have already chosen, for better or for worse, to trust the valet service with a key to the car. As the random new attendant comes running up to us, we are reluctant to hand over yet another key to the vehicle. After all, this new attendant might actually be an imposter, eager to grab that new Ferrari and cruise out over the desert. And besides, we already handed the valet service a key to the car. They should be able to use the key they already have, right?

Meanwhile, the attendant also has a trust problem. It would be a career catastrophe to serve up the Ferrari from his parking lot if I actually own the dented 23-year-old Chevy Nova sitting next to it.

In the physical world, we use a ''claim check'' to solve the problem. We present to the attendant, not a second set of car keys, but rather, a proof that we have the authority that we are asking the attendant to use on our behalf.

<pre>

<nowiki># E sample
def claimMgr := {
def carKeys := [].asMap().diverge()
def claimMgr {
to makeClaim(car) :any {
# the claim object has no interesting
# properties except it has
# a unique unforgeable identity
def claim {}
carKeys[claim] := car
return claim
}
to reclaim(claim) :any {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
}
}
}

def attendant {
#return a claim check when car is parked
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}

def car {}
def carOwner := {
var claim := null
def carOwner {
to letAttendantParkCar() :void {
claim := attendant.parkCar(car)
println(claim)
}
to getCarFromAttendant() :void {
println(attendant.retrieveCar(claim))
}
}
}

carOwner.letAttendantParkCar()
carOwner.getCarFromAttendant()
</nowiki>

</pre>

====Basic Claim Check Default Behavior====

Suppose the owner of the car loses the claim check. He can still prove he owns the car by presenting another key. In software, this situation would be comparable to the situation in which the owner hands the attendant a direct reference rather than handing the attendant merely the claim check. The car owner has violated his own security, but it is hard to visualize situations in which this is not a reasonable argument to pass to express his desire. We can cover this case with a small modification to the claimMgr's reclaim method:

<pre>to reclaim(claim) :any {
try {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
} catch prob {
if (carKeys.contains(claim)) {
return claim
} else {throw(prob)}
}
}</pre>

What should the claimMgr return if the carOwner hands in a car reference for reclaim, if the car is not actually in the claimMgr's parking lot? The answer depends on the application, but such a situation violates the expectations of all the participants sufficiently that throwing an exception seems the safest choice.

====NonTransferable Claim Check====

We are far from done with claim checks. A careful car owner will not actually hand his claim check to the parking lot attendant. Rather, he will merely show the claim check to the attendant. After all, if you hand the claim check over to an imposter, the imposter can turn around and hand the claim check to a real attendant, pretending that he is the owner of the car.

The problem is somewhat different in cyberspace. The good news is, in cyberspace the attendant doesn't return a reference to the car just because you hand him the claim check. Instead, he merely performs the action you ask of him with the car. This set of actions is limited by the attendant's willing behavior. So the claim check is not as powerful a capability as the car itself. But it can still be a powerful capability. And the bad news is, in cyberspace, you can't just "show" it to the attendant. You have to give it to him.

Here we demonstrate a "nontransferable" claim check. This claim check can be handed out at random to a thousand car thieves, and it does them no good. The trick is, before handing over the claim check, the owner inserts into the claim check a reference to the individual he is treating as an attendant. The ClaimMgr compares the person to whom the owner handed the claim, with the attendant who eventually hands the claim to the claimMgr . If these two people are the same, then the owner handed the claim directly to the attendant. Otherwise, there was an intermediary party, and the request should not be honored.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def valetService := {
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def claimMgr {
to makeClaim(car) :any {
def transferableClaim {
to makeNontransferableClaim(intendedRecipient) :any {
return claimSealer.seal([car, intendedRecipient])
}
}
return transferableClaim
}
to reclaim(claim, actualRecipient) :any {
def [car, intendedRecipient] := claimUnsealer.unseal(claim)
if (actualRecipient == intendedRecipient) {
return car
} else {throw("claim not transferable, invalid attendant")}
}
}
def valetService {
to authorizeAttendant(attendant) :void {
attendant.setClaimMgr(claimMgr)
}
}
}

def makeAttendant() :any {
def claimMgr
def attendant {
to setClaimMgr(mgr) :void {bind claimMgr := mgr}
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim, attendant)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}
return attendant
}

def legitAttendant := makeAttendant()
valetService.authorizeAttendant(legitAttendant)

def carThief {
to parkCar(car) :any {
return println ("Ha! stole the car")
}
to retrieveCar(claim) :void {
try {
legitAttendant.retrieveCar(claim)
println("Ha! didn't get car, but got control")
} catch prob {println(`rats! foiled again: $prob`)}
}
}

def carOwner := {
def car{}
var claim := null
def carOwner {
to letValetPark(attendant) :void {
claim := attendant.parkCar(car)
println(claim)
}
to letValetRetrieve(attendant) :void {
def noTransferClaim := claim.makeNontransferableClaim(attendant)
println(attendant.retrieveCar(noTransferClaim))
}
}
}

carOwner.letValetPark(legitAttendant)
carOwner.letValetRetrieve(carThief)
carOwner.letValetRetrieve(legitAttendant)
</nowiki>

</pre>

Note an important implication in this pattern: the ClaimMgr winds up in a position to accumulate references to all the entities a claim check holder treats as an attendant. In this example, the ClaimMgr gets a reference to the carThief as a result of the carOwner's casual handing out of claim checks. It seems unlikely that the ClaimMgr can harm the carOwner's interests with this reference, but in other circumstances the reference may not be so harmless. To reduce our risk exposure to the alleged attendants to whom we hand the claim check, we have increased our risk exposure to the ClaimMgr.

Note also the limitations on the nontransferability of this pattern. The carOwner can still transfer authority, either by handing someone a reference to the car, or by handing out the transferableClaim from which nontransferableClaims can be made. The nontransferability is voluntarily chosen by the carOwner. You can't prevent people from delegating their authority, and even this pattern doesn't change that fact.

====Oblivious Claim Check: Loan Officer Protocol====

{| style="float: right; width: 2in; border-style: inset; border-width: 3;background-color: #FFFF99; font-size:80%"
|
Voluntary Oblivious Compliance, or VOC, was pioneered by the [http://www.erights.org/history/client-utility.html Client Utility System]. VOC is a field only recently recognized by the capability-security community as an important area of exploration; the claim check patterns here are early fruit of that research. VOC is irrelevant in the classical cypherpunk view of the world, where every person is a rugged individualist making all his own authority-granting decisions with little regard for other people's issues. In a world filled with corporations, governments, and other policy-intensive organizations, however, it is an area of real value even though it is not really a security matter. Why is it not security? We consider it beyond the scope of "security" for a simple but compelling reason: it is not enforceable. Unenforceable security in cyberspace has been proven, over and over again in the course of the last decade, to be a joke played on all the participants. VOC states in its very name the limits of its applicability: it only works with volunteers. Don't be fooled into thinking this is security.
|}

Let us consider a somewhat different problem. Suppose that different attendants are trusted to handle different cars by the valet service. One valet has a motorcycle license and parks all the Harleys. Another has a multi-engine pilot's license and parks all the Boeing 747s. Of course, the one with the motorcycle license is a teenager who has always wanted to try his hand at parking a 747, and knows his lack of experience is not a problem. In this situation, each attendant has a different set of authorities at his command; just because you hand your claim check to a legit attendant doesn't mean the valet service thinks it would be a good idea to let that attendant drive your vehicle. A more generalized way of stating the problem is, in this case the authorities of the individual receivers of the claim checks vary, and management of the individual receiver's authorities is beyond the scope of what the ClaimManager should be trying to figure out. After all, the individuals know all their own authorities; it would be poor design (and unmaintainable at scale) for the ClaimManager to try to duplicate this information.

This situation, while not a part of the real-world valet service problem, has a significant area of application in cyberspace. This area is ''Voluntary Oblivious Compliance'', or VOC. Let us consider a more sensible example. Alice works for HPM, and Bob works for Intil. HPM and Intil are often competitors, but Alice and Bob are working on a joint project from which both companies expect to profit handsomely. The Official Policy Makers of HPM have identified a number of documents which can be shared with Intil, and indeed have forwarded to Intil references to the allowed docs. Alice wants to refer Bob to a particular HPM document, but ''only if sharing the document is allowed'' under the HPM policy. In this case, the VOCclaimCheck that Alice sends to Bob demands that Bob demonstrate to HPM's ClaimMgr that he already has authority on the document before fulfilling the claim. To prove his authority, Bob sends to the ClaimMgr all the HPM doc authorities he has (i.e., the list of docs HPM handed to Intil). Only if both Alice and Bob already have authority on the object does Bob get the document. This is sometimes called the Loan Officer Protocol, in reference to the old adage that a loan officer will not give you the loan unless you first prove that you don't need it.

Since bob can't get the reference unless he proves he doesn't need it, we can now see why this is a pattern of Voluntary Oblivious Compliance. It is voluntary, because Alice could just send Bob the document and circumvent the system. And it is oblivious, because Alice doesn't need to know whether a document can be shared with Bob before sending it.

Going back to the parking lot attendant who wants to park the 747, he has to demonstrate to the ClaimManager that he has the keys to the 747 before the Claim Manager will let him go for it. The owner of the 747 is much relieved.

Humorous as the 747 example might be, we will now switch to the scenario with Alice, Bob, HPM, and Intil for our sample code. The basic strategy is that the ClaimMgr not only examines the claim check from Alice, it also examines the list of authorities that Bob hands over to see if any of Bob's authorities match the one inside Alice's claim.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def HPMDocClaimMgr {
to makeClaim(doc) :any {
return claimSealer.seal(doc)
}
to matchClaim(claim, listOfCandidates) :any {
def doc := claimUnsealer.unseal(claim)
for each in listOfCandidates {
if (doc == each) {return each}
}
throw("No match from claimCheck to candidate auths")
}
}

def intilSharedDocs := [def doc1{}, def doc2{}, def doc3{}]

def bob {
to lookAtHPMDoc(claim) :void {
try {
def doc := HPMDocClaimMgr.matchClaim(claim, intilSharedDocs)
println(`reading doc: $doc`)
} catch prob {
println(`can't read: $claim`)
}
}
}

def alice {
to sendDoc(doc, recipient) :void {
def claim := HPMDocClaimMgr.makeClaim(doc)
recipient.lookAtHPMDoc(claim)
}
}
alice.sendDoc(doc2, bob)
alice.sendDoc(def doc4{}, bob)
</nowiki>

</pre>

The oblivious claim check pattern can require scattering even more authority to the winds than the nontransferable claim check. The recipient of the claim check (bob) needs to have all the authorities that alice might give to him, rather than merely the ones she actually does give to him. And the trusted third party who matches the claim check against the list of possibilities (the HPMDocClaimMgr) gets to accumulate authority to everything that bob thinks alice might be trying to send him. In the example scenario, this is just fine. But some care is required.

====Oblivious Claim Checks as Guards====

An elegant style of using VOC claim checks is to set up the pattern as a pair of guards. Alice would use the ClaimCheck guard to send a reference to Bob, and Bob would use the CheckedClaim guard, with the list of candidate references, to receive the authority. We will show the implementation of the BuildGuards ClaimCheck and CheckedClaim guards in [[Walnut/Advanced_Topics|Advanced Topics]] when we talk about writing your own guards, but their usage would appear as follows:

<pre># E syntax
def bob {
to lookAtHPMDoc(doc :CheckedClaim[intilSharedDocs]) :void {
if (!E.isBroken(doc)) {
println(`reading doc: $doc`)
} else {println(`can't read: $claim`)}
}
}

def alice {
to sendDoc(doc, recipient) :void {
recipient.lookAtHPMDoc(doc :ClaimCheck)
}
}</pre>

The ClaimCheck guard coerces the doc into a sealed representation of itself. The CheckedClaim guard unseals the claim and matches it against the authorities in the intilSharedDocs list. As a guard, it is better style to return a broken reference than to throw an exception if something goes wrong. In the parameter guard, if an exception were thrown, the recipient would have no chance to do anything with the problem, the exception would be thrown directly back to the sender before the recipient was even aware there was an issue.

====Oblivious NonTransferable Claim Check====

It is possible to make nontransferable oblivious claim checks as well. We leave the code as an exercise for the reader.

====Powerbox Capability Manager====

The powerbox pattern collects diverse elements of authority management into a single object. That object, the ''powerbox'', then becomes the arbiter of authority transfers across a complex trust boundary. One of the powerbox's most distinctive features is that it may be used for dynamic negotiations for authority during operation. The less trusted subsystem may, during execution, request new authorities. The powerbox owner may, in response to the request, depending on other context that it alone may have, decide to confer that authority, deny the authority, or even grant the request authority after revoking other authorities previously granted.

The powerbox is particularly useful in situations where the object in the less trusted realm does not always get the same authorities, and when those authorities may change during operation. If the authority grant is static, a simple emaker-style authorization step suffices, and a powerbox is not necessary. If the situation is more complex, however, collecting all the authority management into a single place can make it much easier to review and maintain the extremely security-sensitive authority management code.

Key aspects of the powerbox pattern include:

* A powerbox uses strict guards on all arguments received from the less trusted realm. In the absence of guards, even an integer argument received from untrusted code can play tricks: the first time the integer-like object (that is not really an integer) is asked to "add", it returns the value "123"; but the second time, it returns the value "456", with unpredictable (and therefore insecure) results. An ":int" guard on the parameter will prevent such a fake integer from crossing into your realm.
* A powerbox enables revocation of all the authorities that have been granted. When you are done using a less trusted subsystem, the authorities granted to it must be explicitly revoked. This is true even if the subsystem is executing in your own vat and you nominally have the power to disconnect all references to the subsystem and leave the subsystem for the garbage collector. Even after being severed in this fashion, the subsystem will still exist for an unbound amount of time until the garbage collector reaches it. If the authorities it has received have not been revoked, it can surprise you with its continued operations, and continued use of authority. Not all kinds of objects in the Java API can be made directly revocable at this time, because an ''E'' revocable forwarder cannot be used in all the places where an actual authority-carrying Java object is required. For example, the untrusted object may want to create a new image from an url. The natural way of doing this would be to call the Java Icon class constructor with (url) as the argument. But if an E forwarder were handed to this class constructor, the constructor would throw a type exception. Different solutions to such impedence mismatches with the Java type system are required in different situations. For the icon maker, it might be acceptable to require that the untrusted object read the bits of the image from the url (through a revocable forwarder) and then convert the bits into an icon.
* A new powerbox is created for each subsystem that needs authorities from within your trust realm. If a powerbox is shared across initiations of multiple subsystems, the powerbox may become the channel by which subsystems can illicitly communicate, or the channel by which an obsolete untrusted subsystem can interfere with a new one. When the old untrusted subsystem is discarded, its powers must all be revoked, which necessarily implies that a new subsystem will need a new powerbox.

In the following example, the less trusted object may be granted a Timer, a FileMaker that makes new files, and a url. The object may request a different url in the course of operations, in which case the powerbox will ask the user for authorization on the objects's behalf; the old url is revoked, and the new one substituted, so that the object never has authority for more than one url at a time. The object that operates the powerbox may revoke all authorities at any time, or it may choose to revoke the Timer alone. Finally, the operator of this powerbox may, for reasons external to the powerbox's knowledge, decide to grant an additional authority during operations, an authority whose nature is not known to the powerbox.

<pre>
# E sample
# The authorized url may change during operations, so it is a var
def makePowerboxController(optTimer,
optMakeFile,
var optUrl,
optMakeUrl,
makeDialogVow) {

# In the revokers map, the object being revoked is the key, the revoker
# is the value. Note it is the actual object, not the forwarder to the
# object, that is the key.
var revokers := [].asMap()

# when a revokable forwarder is made, the revoker is automatically
# placed in the map of revokers
def makeRevokableForwarder(object) :near {
var innerObject := object
def revoker {
to revoke() {innerObject := null}
}
revokers with= (object, revoker)
def forwarder {match [verb, args] {return E.call(innerObject, verb, args)}}
return forwarder
}

# makeFileFacet is exposed to less trusted realm; guard the path it receives
# This simple file facet only supplies 2 methods that return immutables
# If the file handed out mutable objects, such as streams, these would have
# to be wrapped with revokableForwarders as well.
def makeFileFacet(path :String) :near {
def theFile := optMakeFile(path)
def fileFacet {
to getText() :String {theFile.getText()}
to setText(text :String) {theFile.setText(text)}
}
return makeRevokableForwarder(fileFacet)
}

# makeFile is actually handed to the less trusted object
# It is either null or a revokable forwarder for makeFileFacet
# In other words, makeFile is a revokable maker of revokable file facets
def makeFile
if (optMakeFile == null) {
bind makeFile := null
} else {
bind makeFile := makeRevokableForwarder(makeFileFacet)
}

# Like the file facet, this url facet only supports methods that return
# immutables.
def makeRevokableUrlFacet(optUrl) :near {
if (optUrl == null) {
return null
} else {
def urlFacet {
to getBytes() :pbc {optUrl.getBytes()}
}
return makeRevokableForwarder(urlFacet)
}
}

# Return a vow for a new url
# Use dialog with user to determine if new url should be granted
# Vow resolves to null if anything goes wrong
def makeRevokableUrlVow := {
def makeUrlVow(requestedUrl :String, why :String) :vow {
def urlDialogVow :=
makeDialogVow("Url Request",
`<html>
Confined Object requesting url for this reason:$why
</html>`,
requestedUrl,
["Grant", "Refuse"])
return when (urlDialogVow) -> {
if (urlDialogVow.getButton() == "Grant") {
optUrl := optMakeUrl(urlDialogVow.getText())
makeRevokableUrlFacet(optUrl)
} else {null}
} catch prob {null}
}
return makeRevokableForwarder(makeUrlVow)
}

var caps := [].asMap()
caps with= ("TIMER", makeRevokableForwarder(timer))
caps with= ("FILEMAKER", makeFile)
caps with= ("URL", makeRevokableUrlFacet(optUrl))

def powerbox {

# any of these capabilities may be null, i.e., all are optional
# in a powerbox, strictly at the whim of the powerbox operator
# who created the powerboxcontroller and the powerbox
to optCap(key :String) :any {return caps.get(key, null)}

# When the less trusted object requests a new url, the
# old url is immediately revoked, and the promise for the
# new url is substituted
# If the powerbox has revokedAll, any attempt to requestUrl
# will throw an exception back to the untrusted object
# The "why" parameter is the less trusted object's justification
# for needing the url
to requestUrl(requestedUrl :String, why :String):vow {
if (optUrl != null) {revokers[optUrl].revoke()}
def revokableUrlVow := makeRevokableUrlVow(requestedUrl, why)
caps with= ("URL", revokableUrlVow)
return revokableUrlVow
}
}

def powerboxController {
to revokeAll() {
for each in revokers {each.revoke()}
}
to revokeTimer() {revokers[timer].revoke()}
# Confer an additional capability during execution
to conferCap(key, cap) {
caps with= (key, makeRevokableForwarder(cap))
}
to getPowerbox() {return powerbox}
}
}

# now, show how to create a powerbox and hand it to an untrusted object

def makeUntrustedObject(powerbox) {
def timer := powerbox.optCap("TIMER")
def urlVow := powerbox.requestUrl("http://www.skyhunter.com")
def untrustedObject {
#...
}
return untrustedObject
}

def powerboxOperator() {
def makeDialogVow {#...construct dialog vow
}
# use real objects, not nulls, in typical operation, though nulls are valid arguments
def controller := makePowerboxController(null,
null,
null,
null,
makeDialogVow)
def powerbox := controller.getPowerbox()
def untrusted := makeUntrustedObject(powerbox)
# later, confer an additional authority
def special
controller.conferCap("SPECIAL", special)
# when done with the untrusted object, revoke its powers
controller.revokeAll()
}
</pre>

Both the file facet and the url facet restrict the user to methods that return immutables. If these facets returned mutables, like streams, then those mutables would also have to be wrapped in revokable forwarders. In the general case, this requires the use of a membrane. write section on membranes, and link

====Pet Names and Forgery among partially trusted participants====

E's encrypted authenticated references ensure that random attackers get no traction trying to break into your distributed system. As mentioned in the earlier minChat audit, this means that all interesting break-ins will be made by "insiders", i.e., people who have been granted some capabilities inside your system. We have talked so far about low-level attacks that attempt to acquire or use inappropriately conveyed authority. At a higher conceptual level, people can try to present themselves as someone else and get your user to intentionally, but erroneously, grant other information or capabilities.

minChat dodged this problem because it is a 2-person chat system: the person at the other end of the line will have difficulty convincing your user he is someone else, because your user knows the one and only person given the URI (because he used PGP encryption as described earlier to ensure that only one person got it). But in a multi-person chat system, Bill could try to pretend to be Bob and lure your user into telling him Bob's secrets.

There is no single all-purpose solution to this risk. However, one critical part of any specific solution must be this: Do not allow the remote parties to impose their own names for themselves upon your user.

[[Petnames]]

The general solution is to use ''petnames'', i.e., names your user chooses for people, regardless of how those people might name themselves. Of course, it is reasonable to allow the other people to propose names to your user (called ''nicknames''), but the user must make the final decision. The user must also be able to change her mind at a later date, when her list of participants grows to include not only Bob Smith but also Bob Jones, and she must disambiguate the pet name "Bob" she had for Smith.

The general layout of such a petname setup might be as follows:

petname sample

Walnut/Secure Distributed Computing/Capability Patterns

2007-08-14T15:29:37Z

DavidHopwood: /* Pet Names and Forgery among partially trusted participants */

[[Category:Walnut|4]]

===Capability Patterns===

====Facets====

As discussed in the minChat security review, facets are objects that act as intermediaries between powerful objects and users that do not need (and should not be granted) its full power. We saw a facet in use in the audited version of the eChat program, where the chatFacet. was interposed between the chatController and the remote chat participant. Here is a little general-purpose facet maker:

<pre>

<nowiki># E sample
/**
* <param> target is the underlying powerful object
* <param> allowedMethods is a map. The key is a method name, the value
* is the set of allowed numbers of arguments. So ["receive" =>[0, 2].asSet()]
* would allow the receive method, with either 0 or 2 arguments, to be forwarded.
**/
def makeFacet(target, allowedMethods) {
def filteringFacet {
match [verb, args] {
if (allowedMethods.maps(verb) &&
allowedMethods[verb].contains(args.size())) {
return E.call(target, verb, args)
}
}
}
return filteringFacet
}
def chatController
def chatFacet := makeFacet(chatController, ["receive"=>[1].asSet(),
"receiveFriend"=>[1].asSet()])
</nowiki>

</pre>

Facets of this type can be retrofitted onto an existing system. We did this with very little effort for minChat with the chatFacet, but the technique works for far more complicated problems as well. The capability-secure windowing toolkits that ''E'' has placed on top of Swing and SWT uses facetization as the main tool.

Facets can be made much more sophisticated in their restrictions on access to their underlying object. You can make a facet that logs requests and sends email when certain methods are called. In an SEC-regulated stock exchange facet, you might wish to grant the capability to make a trade only from 9AM to 3PM excluding weekends and holidays.

One interesting example is the use-once facet, which allows the holder of the facet to use the facet only one time. For example, this version of a chatReceiver only allows a single message to be sent:

<pre>

<nowiki># E sample
def onceOnlyReceiver(baseChatController) {
var chatController := baseChatController
def onceOnlyReceiver {
to receive(text) {
chatController.receive(text)
chatController := null
}
}
}</nowiki>

</pre>

This version will throw an exception back to the sender of a second message.

It can be tempting in a facet to suppress a couple of powerful methods in the underlying powerful object and delegate the rest.

<pre>

<nowiki># E sample
def powerfulObject {
to doPowerfulOperation() {
#do powerful operation
}
to doWeak1() {}
to doWeak2() {}
to doWeak3() {}
#....
to doWeak99() {}
}
def badFacet extends powerfulObject {
to doPowerfulOperation() {
#do nothing, no forwarding for the powerful operation, but forward everything else
}
} </nowiki>

</pre>

''Avoid this''. For a facet to remain secure during maintenance, it should never just delegate by default. If a new method is added to a powerful object (in this example, suppose powerfulObject is updated with a new method, doPowerful2()), it should not be exposed through the facet by default: rather, the facet must by default not expose it.

This risk can be exhausting to avoid, but it is always dangerous to accept. The first version of the capability windowing toolkit on Swing suppressed the handful of dangerous methods in the Java version 1.3 of Swing rather than explicitly allowing the safe methods, of which there were thousands. Within 30 days, the entire system was broken: the Java 1.4 Beta included hundreds of new, security-breaking methods. The only saving grace was that we had always known that the first version, thrown together in haste on weekends, was just a proof-of-principle and would have to be replaced. We just hadn't appreciated how soon replacement would be required.

====Revocable Capabilities====

If you wish to give someone restricted access to an object with facets, it is quite likely you will want to revoke access at some point as well.

The simplest way of making a capability revocable is to use a transparent forwarder that includes a revocation method:

<pre>

<nowiki># E sample
def revocableCapabilityMaker(baseCapableObject) {
var capableObject := baseCapableObject
def forwarder {
to revoke() {capableObject := null}
match [verb, args] {E.call(capableObject, verb, args)}
}
return forwarder
}</nowiki>

</pre>

Note that, even though the forwarder is nominally delegating all method invocations (except revoke()) to the capableObject, we cannot use the ''extends'' keyword to capture the behavior. "Extends" creates an immutable reference, so the fact that the capableObject is a var wouldn't allow you to revoke the delegating behavior. Instead we use the match[verb, args] pattern.

Capability revocation, like facet forwarding, can be based on complex sets of conditions: revoke after a certain number of uses, revoke after a certain number of days. This example uses a simple manual revocation. Indeed, this version is too simple to work reliably during system maintenance and upgrade, and a more sophisticated pattern is generally recommended:

<pre>

<nowiki># E sample
def makeCapabilityRevokerPair(baseCapableObject) {
var capableObject := baseCapableObject
def revoker {
to revoke() {capableObject := null}
}
def forwarder {match[verb, args] {E.call(capableObject, verb, args)}}
return [forwarder, revoker]
}
def powerfulObject {
#...big powers
}
def [power, revoker] := makeCapabilityRevokerPair(powerfulObject)</nowiki>

</pre>

In this pattern, the authority of the object and the authority to revoke are separated: you can hand the power to revoke to an object you would not trust with the authority itself. Also, the separate revoker can itself be made revocable.

====Sealers and Unsealers====

A sealer/unsealer pair makes it possible to use untrusted intermediaries to pass objects safely. Use the sealer to make a sealed box that can only be opened by the matching unsealer. E has built-in support for sealer/unsealer pairs:

<pre>

<nowiki>? def makeBrandPair := <elib:sealing.makeBrand>
# value: <makeBrand>

? def [sealer, unsealer] := makeBrandPair("BrandNickName")
# value: [<BrandNickName sealer>, <BrandNickName unsealer>]

? def sealedBox := sealer.seal("secret data")
# value: <sealed by BrandNickName>

? unsealer.unseal(sealedBox)
# value: "secret data"
</nowiki>

</pre>

If you hold the unsealer private, and give the sealer away publicly, everyone can send messages that only you can read. If you hold the sealer private, but give the unsealer away publicly, then you can send messages that recipients know you created, i.e., you can use it as a signature. If you are thinking that this is much like a public/private key pair from public key cryptography, you are correct, though in E no actual encryption is required if the sender, recipient, brand maker, and sent object all reside in the same vat.

While the Brand is built-in, it is possible to construct a sealer/unsealer pair maker in E without special privileges. The "shared variable" technique for making the maker is interesting, and because the same pattern appears in other places (such as the Notary/Inspector, coming up next), we demonstrate it here:

<pre>

<nowiki># E sample
def makeBrandPair(nickname) {
def noObject{}
var shared := noObject
def makeSealedBox(obj) {
def box {
to shareContent() {shared := obj}
}
return box
}
def sealer {
to seal(obj) {return makeSealedBox(obj)}
}
def unsealer {
to unseal(box) {
shared := noObject
box.shareContent()
if (shared == noObject) {throw("invalid box")}
def contents := shared
shared := noObject
return contents
}
}
return [sealer, unsealer]
}
</nowiki>

</pre>

The variable "shared" normally contains the value "noObject", which is private to a particular sealer/unsealer pair and so could never the the actual value that someone wanted to pass in a sealed box. The unsealer tells the box to shareContent, which puts the content into the shared variable, from which the unsealer then extracts the value for the invoker of the unseal method. In a conventional language that used threads for concurrency control, this pattern would be a disaster: different unseal requests could rumble through, overwriting each others' shared content. But by exploiting the atomicity of operational sequences enabled by promise pipelining, this peculiar pattern becomes a clean solution for this, and several other security-related operations.

====Vouching with Notary/Inspector====

Suppose Bob is the salesman for Widget Inc. He persuades Alice to buy a widget. Bob hands Alice a Widget Order Form with a money-receiving capability. It is important to Bob that Alice use the form he gives her, because this particular form (which Bob got from Widget Inc.) remembers that Bob is the salesman who should get the commission. It is important to Alice that she know for sure that, even though she got the order-form from Bob, this is really a Widget Inc. order form, and not something Bob whipped up that will transfer her money directly to his own account. In this case, Alice wants to have Widget Inc. vouch for the order-form she received from Bob. She does this using an Inspector that she gets directly from Widget Inc. The Inspector is the public part of a notary/inspector pair of objects that provide verification of the originator of an object. To be vouchable, the orderForm must implement the startVouch method as shown here:

<pre>

<nowiki># E sample
####### Widget Inc. software #####

#vouching system
#returns a private notary that offers a public inspector
#throws problem if the object being vouched is not vouchable
def makeNotary() {
def nonObject {}
def unvouchedException(obj) {throw(`Object not vouchable: $obj`)}
var vouchableObject := nonObject
def inspector {
to vouch(obj) {
vouchableObject := nonObject
try {
obj.startVouch()
if (vouchableObject == nonObject) {
return unvouchedException(obj)
} else {
def vouchedObject := vouchableObject
vouchableObject := nonObject
return vouchedObject
}
} catch err {unvouchedException(obj)}
}
}
def notary {
to startVouch(obj) { vouchableObject := obj}
to getInspector() {return inspector}
}
return notary
}

#create Widget Inc's notary
def widgetNotary := makeNotary()

#Order form maker
def makeOrderForm(salesPerson) {
def orderForm {
# .... methods for implementing orderForm
to startVouch() {widgetNotary.startVouch(orderForm)}
}
return orderForm
}

#publicly available inspector object
#(accessible through a uri posted on Widget Inc's web site)
def WidgetInspectionService {
to getInspector() {return widgetNotary.getInspector()}
}

##### bob software #####

#scaffold for sample
def getOrderFormFromBob() {return makeOrderForm("scaffold")}

########## Alice's software to vouch for the order form she received from Bob #####

def untrustedOrderForm := getOrderFormFromBob()
def inspector := WidgetInspectionService.getInspector()
def trustedOrderForm := inspector.vouch(untrustedOrderForm)</nowiki>

</pre>

====Proof of Purchase====

"Proof of Purchase" is the simplest of a series of capability patterns in which the goal is not to transfer an authority, but rather to show someone that you have the authority so that they can comfortably proceed to use the authority on your behalf. In Proof of Purchase, the requester of a service is demonstrating to the server that the client already has capability that the server is being asked to use. Unlike the more sophisticated upcoming Claim Check patterns, the proof of purchase client is not concerned about giving the server an excess authority.

An interesting example of Proof of Purchase is [http://www.erights.org/javadoc/java/awt/Component.html Component.transferFocus(fromComponentsList, toComponent)] found in the tamed Swing package. In standard Swing, the holder of any panel reference can steal the focus (with component.requestFocus()). Hence any keystrokes, including passwords, can be swiped from wherever the focus happens to be by sneaking in a focus change. This is a clear violation of POLA. You should be able to transfer focus from one panel to another panel ''only if you have references to both panels''. If you have a reference to the panel that currently has the focus, then you can never steal the focus from anyone but yourself.

A natural-seeming replacement for component.requestFocus() would be requestFocus(currentFocusHolder). It was decided during the taming of Swing, however, that this would be breach-prone. If Alice transferred to Bob, not a panel itself, but rather a simple transparent forwarder on that panel, Alice could collect authorities to other panels whenever Bob changed focus.

Since we had a convenient trusted third party available that already had authority over all the panels anyway (the javax.swing.Component class object), we used the "proof of purchase" pattern instead. The globally available Component.transferFocus method accepts two arguments:

* a list of panels that the client believes to contain, somewhere in their subpanel hierarchies, the focus
* the target panel that should receive the focus

In the common case where a whole window lies inside a single trust realm, the client can simply present a reference to the whole window and be confident that the focus will be transferred.

The interesting thing about Component.transferFocus is that the recipient does not actually need the client's authority to reach the component that already has the focus. The Component class already has that authority. The client must send the authority merely to prove he has it, too.

====Basic Claim Check====

A common activity that brings security concerns into sharp focus is the delicate dance we perform when we use a car valet service. In this situation, we are handing the authority over our most precious and costly possession to a teenager with no more sense of responsibility than a stray cat. The whole valet system is a toothsome exercise in POLA.

In this example, we focus on the sequence of events and trust relationships involved in ''reclaiming'' our car at the end of the evening. The participants include the car owner, the valet service itself, and the random new attendant who is now on duty.

We have already chosen, for better or for worse, to trust the valet service with a key to the car. As the random new attendant comes running up to us, we are reluctant to hand over yet another key to the vehicle. After all, this new attendant might actually be an imposter, eager to grab that new Ferrari and cruise out over the desert. And besides, we already handed the valet service a key to the car. They should be able to use the key they already have, right?

Meanwhile, the attendant also has a trust problem. It would be a career catastrophe to serve up the Ferrari from his parking lot if I actually own the dented 23-year-old Chevy Nova sitting next to it.

In the physical world, we use a ''claim check'' to solve the problem. We present to the attendant, not a second set of car keys, but rather, a proof that we have the authority that we are asking the attendant to use on our behalf.

<pre>

<nowiki># E sample
def claimMgr := {
def carKeys := [].asMap().diverge()
def claimMgr {
to makeClaim(car) :any {
# the claim object has no interesting
# properties except it has
# a unique unforgeable identity
def claim {}
carKeys[claim] := car
return claim
}
to reclaim(claim) :any {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
}
}
}

def attendant {
#return a claim check when car is parked
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}

def car {}
def carOwner := {
var claim := null
def carOwner {
to letAttendantParkCar() :void {
claim := attendant.parkCar(car)
println(claim)
}
to getCarFromAttendant() :void {
println(attendant.retrieveCar(claim))
}
}
}

carOwner.letAttendantParkCar()
carOwner.getCarFromAttendant()
</nowiki>

</pre>

====Basic Claim Check Default Behavior====

Suppose the owner of the car loses the claim check. He can still prove he owns the car by presenting another key. In software, this situation would be comparable to the situation in which the owner hands the attendant a direct reference rather than handing the attendant merely the claim check. The car owner has violated his own security, but it is hard to visualize situations in which this is not a reasonable argument to pass to express his desire. We can cover this case with a small modification to the claimMgr's reclaim method:

<pre>to reclaim(claim) :any {
try {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
} catch prob {
if (carKeys.contains(claim)) {
return claim
} else {throw(prob)}
}
}</pre>

What should the claimMgr return if the carOwner hands in a car reference for reclaim, if the car is not actually in the claimMgr's parking lot? The answer depends on the application, but such a situation violates the expectations of all the participants sufficiently that throwing an exception seems the safest choice.

====NonTransferable Claim Check====

We are far from done with claim checks. A careful car owner will not actually hand his claim check to the parking lot attendant. Rather, he will merely show the claim check to the attendant. After all, if you hand the claim check over to an imposter, the imposter can turn around and hand the claim check to a real attendant, pretending that he is the owner of the car.

The problem is somewhat different in cyberspace. The good news is, in cyberspace the attendant doesn't return a reference to the car just because you hand him the claim check. Instead, he merely performs the action you ask of him with the car. This set of actions is limited by the attendant's willing behavior. So the claim check is not as powerful a capability as the car itself. But it can still be a powerful capability. And the bad news is, in cyberspace, you can't just "show" it to the attendant. You have to give it to him.

Here we demonstrate a "nontransferable" claim check. This claim check can be handed out at random to a thousand car thieves, and it does them no good. The trick is, before handing over the claim check, the owner inserts into the claim check a reference to the individual he is treating as an attendant. The ClaimMgr compares the person to whom the owner handed the claim, with the attendant who eventually hands the claim to the claimMgr . If these two people are the same, then the owner handed the claim directly to the attendant. Otherwise, there was an intermediary party, and the request should not be honored.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def valetService := {
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def claimMgr {
to makeClaim(car) :any {
def transferableClaim {
to makeNontransferableClaim(intendedRecipient) :any {
return claimSealer.seal([car, intendedRecipient])
}
}
return transferableClaim
}
to reclaim(claim, actualRecipient) :any {
def [car, intendedRecipient] := claimUnsealer.unseal(claim)
if (actualRecipient == intendedRecipient) {
return car
} else {throw("claim not transferable, invalid attendant")}
}
}
def valetService {
to authorizeAttendant(attendant) :void {
attendant.setClaimMgr(claimMgr)
}
}
}

def makeAttendant() :any {
def claimMgr
def attendant {
to setClaimMgr(mgr) :void {bind claimMgr := mgr}
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim, attendant)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}
return attendant
}

def legitAttendant := makeAttendant()
valetService.authorizeAttendant(legitAttendant)

def carThief {
to parkCar(car) :any {
return println ("Ha! stole the car")
}
to retrieveCar(claim) :void {
try {
legitAttendant.retrieveCar(claim)
println("Ha! didn't get car, but got control")
} catch prob {println(`rats! foiled again: $prob`)}
}
}

def carOwner := {
def car{}
var claim := null
def carOwner {
to letValetPark(attendant) :void {
claim := attendant.parkCar(car)
println(claim)
}
to letValetRetrieve(attendant) :void {
def noTransferClaim := claim.makeNontransferableClaim(attendant)
println(attendant.retrieveCar(noTransferClaim))
}
}
}

carOwner.letValetPark(legitAttendant)
carOwner.letValetRetrieve(carThief)
carOwner.letValetRetrieve(legitAttendant)
</nowiki>

</pre>

Note an important implication in this pattern: the ClaimMgr winds up in a position to accumulate references to all the entities a claim check holder treats as an attendant. In this example, the ClaimMgr gets a reference to the carThief as a result of the carOwner's casual handing out of claim checks. It seems unlikely that the ClaimMgr can harm the carOwner's interests with this reference, but in other circumstances the reference may not be so harmless. To reduce our risk exposure to the alleged attendants to whom we hand the claim check, we have increased our risk exposure to the ClaimMgr.

Note also the limitations on the nontransferability of this pattern. The carOwner can still transfer authority, either by handing someone a reference to the car, or by handing out the transferableClaim from which nontransferableClaims can be made. The nontransferability is voluntarily chosen by the carOwner. You can't prevent people from delegating their authority, and even this pattern doesn't change that fact.

====Oblivious Claim Check: Loan Officer Protocol====

{| style="float: right; width: 2in; border-style: inset; border-width: 3;background-color: #FFFF99; font-size:80%"
|
Voluntary Oblivious Compliance, or VOC, was pioneered by the [http://www.erights.org/history/client-utility.html Client Utility System]. VOC is a field only recently recognized by the capability-security community as an important area of exploration; the claim check patterns here are early fruit of that research. VOC is irrelevant in the classical cypherpunk view of the world, where every person is a rugged individualist making all his own authority-granting decisions with little regard for other people's issues. In a world filled with corporations, governments, and other policy-intensive organizations, however, it is an area of real value even though it is not really a security matter. Why is it not security? We consider it beyond the scope of "security" for a simple but compelling reason: it is not enforceable. Unenforceable security in cyberspace has been proven, over and over again in the course of the last decade, to be a joke played on all the participants. VOC states in its very name the limits of its applicability: it only works with volunteers. Don't be fooled into thinking this is security.
|}

Let us consider a somewhat different problem. Suppose that different attendants are trusted to handle different cars by the valet service. One valet has a motorcycle license and parks all the Harleys. Another has a multi-engine pilot's license and parks all the Boeing 747s. Of course, the one with the motorcycle license is a teenager who has always wanted to try his hand at parking a 747, and knows his lack of experience is not a problem. In this situation, each attendant has a different set of authorities at his command; just because you hand your claim check to a legit attendant doesn't mean the valet service thinks it would be a good idea to let that attendant drive your vehicle. A more generalized way of stating the problem is, in this case the authorities of the individual receivers of the claim checks vary, and management of the individual receiver's authorities is beyond the scope of what the ClaimManager should be trying to figure out. After all, the individuals know all their own authorities; it would be poor design (and unmaintainable at scale) for the ClaimManager to try to duplicate this information.

This situation, while not a part of the real-world valet service problem, has a significant area of application in cyberspace. This area is ''Voluntary Oblivious Compliance'', or VOC. Let us consider a more sensible example. Alice works for HPM, and Bob works for Intil. HPM and Intil are often competitors, but Alice and Bob are working on a joint project from which both companies expect to profit handsomely. The Official Policy Makers of HPM have identified a number of documents which can be shared with Intil, and indeed have forwarded to Intil references to the allowed docs. Alice wants to refer Bob to a particular HPM document, but ''only if sharing the document is allowed'' under the HPM policy. In this case, the VOCclaimCheck that Alice sends to Bob demands that Bob demonstrate to HPM's ClaimMgr that he already has authority on the document before fulfilling the claim. To prove his authority, Bob sends to the ClaimMgr all the HPM doc authorities he has (i.e., the list of docs HPM handed to Intil). Only if both Alice and Bob already have authority on the object does Bob get the document. This is sometimes called the Loan Officer Protocol, in reference to the old adage that a loan officer will not give you the loan unless you first prove that you don't need it.

Since bob can't get the reference unless he proves he doesn't need it, we can now see why this is a pattern of Voluntary Oblivious Compliance. It is voluntary, because Alice could just send Bob the document and circumvent the system. And it is oblivious, because Alice doesn't need to know whether a document can be shared with Bob before sending it.

Going back to the parking lot attendant who wants to park the 747, he has to demonstrate to the ClaimManager that he has the keys to the 747 before the Claim Manager will let him go for it. The owner of the 747 is much relieved.

Humorous as the 747 example might be, we will now switch to the scenario with Alice, Bob, HPM, and Intil for our sample code. The basic strategy is that the ClaimMgr not only examines the claim check from Alice, it also examines the list of authorities that Bob hands over to see if any of Bob's authorities match the one inside Alice's claim.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def HPMDocClaimMgr {
to makeClaim(doc) :any {
return claimSealer.seal(doc)
}
to matchClaim(claim, listOfCandidates) :any {
def doc := claimUnsealer.unseal(claim)
for each in listOfCandidates {
if (doc == each) {return each}
}
throw("No match from claimCheck to candidate auths")
}
}

def intilSharedDocs := [def doc1{}, def doc2{}, def doc3{}]

def bob {
to lookAtHPMDoc(claim) :void {
try {
def doc := HPMDocClaimMgr.matchClaim(claim, intilSharedDocs)
println(`reading doc: $doc`)
} catch prob {
println(`can't read: $claim`)
}
}
}

def alice {
to sendDoc(doc, recipient) :void {
def claim := HPMDocClaimMgr.makeClaim(doc)
recipient.lookAtHPMDoc(claim)
}
}
alice.sendDoc(doc2, bob)
alice.sendDoc(def doc4{}, bob)
</nowiki>

</pre>

The oblivious claim check pattern can require scattering even more authority to the winds than the nontransferable claim check. The recipient of the claim check (bob) needs to have all the authorities that alice might give to him, rather than merely the ones she actually does give to him. And the trusted third party who matches the claim check against the list of possibilities (the HPMDocClaimMgr) gets to accumulate authority to everything that bob thinks alice might be trying to send him. In the example scenario, this is just fine. But some care is required.

====Oblivious Claim Checks as Guards====

An elegant style of using VOC claim checks is to set up the pattern as a pair of guards. Alice would use the ClaimCheck guard to send a reference to Bob, and Bob would use the CheckedClaim guard, with the list of candidate references, to receive the authority. We will show the implementation of the BuildGuards ClaimCheck and CheckedClaim guards in [[Walnut/Advanced_Topics|Advanced Topics]] when we talk about writing your own guards, but their usage would appear as follows:

<pre># E syntax
def bob {
to lookAtHPMDoc(doc :CheckedClaim[intilSharedDocs]) :void {
if (!E.isBroken(doc)) {
println(`reading doc: $doc`)
} else {println(`can't read: $claim`)}
}
}

def alice {
to sendDoc(doc, recipient) :void {
recipient.lookAtHPMDoc(doc :ClaimCheck)
}
}</pre>

The ClaimCheck guard coerces the doc into a sealed representation of itself. The CheckedClaim guard unseals the claim and matches it against the authorities in the intilSharedDocs list. As a guard, it is better style to return a broken reference than to throw an exception if something goes wrong. In the parameter guard, if an exception were thrown, the recipient would have no chance to do anything with the problem, the exception would be thrown directly back to the sender before the recipient was even aware there was an issue.

====Oblivious NonTransferable Claim Check====

It is possible to make nontransferable oblivious claim checks as well. We leave the code as an exercise for the reader.

====Powerbox Capability Manager====

The powerbox pattern collects diverse elements of authority management into a single object. That object, the ''powerbox'', then becomes the arbiter of authority transfers across a complex trust boundary. One of the powerbox's most distinctive features is that it may be used for dynamic negotiations for authority during operation. The less trusted subsystem may, during execution, request new authorities. The powerbox owner may, in response to the request, depending on other context that it alone may have, decide to confer that authority, deny the authority, or even grant the request authority after revoking other authorities previously granted.

The powerbox is particularly useful in situations where the object in the less trusted realm does not always get the same authorities, and when those authorities may change during operation. If the authority grant is static, a simple emaker-style authorization step suffices, and a powerbox is not necessary. If the situation is more complex, however, collecting all the authority management into a single place can make it much easier to review and maintain the extremely security-sensitive authority management code.

Key aspects of the powerbox pattern include:

* A powerbox uses strict guards on all arguments received from the less trusted realm. In the absence of guards, even an integer argument received from untrusted code can play tricks: the first time the integer-like object (that is not really an integer) is asked to "add", it returns the value "123"; but the second time, it returns the value "456", with unpredictable (and therefore insecure) results. An ":int" guard on the parameter will prevent such a fake integer from crossing into your realm.
* A powerbox enables revocation of all the authorities that have been granted. When you are done using a less trusted subsystem, the authorities granted to it must be explicitly revoked. This is true even if the subsystem is executing in your own vat and you nominally have the power to disconnect all references to the subsystem and leave the subsystem for the garbage collector. Even after being severed in this fashion, the subsystem will still exist for an unbound amount of time until the garbage collector reaches it. If the authorities it has received have not been revoked, it can surprise you with its continued operations, and continued use of authority. Not all kinds of objects in the Java API can be made directly revocable at this time, because an ''E'' revocable forwarder cannot be used in all the places where an actual authority-carrying Java object is required. For example, the untrusted object may want to create a new image from an url. The natural way of doing this would be to call the Java Icon class constructor with (url) as the argument. But if an E forwarder were handed to this class constructor, the constructor would throw a type exception. Different solutions to such impedence mismatches with the Java type system are required in different situations. For the icon maker, it might be acceptable to require that the untrusted object read the bits of the image from the url (through a revocable forwarder) and then convert the bits into an icon.
* A new powerbox is created for each subsystem that needs authorities from within your trust realm. If a powerbox is shared across initiations of multiple subsystems, the powerbox may become the channel by which subsystems can illicitly communicate, or the channel by which an obsolete untrusted subsystem can interfere with a new one. When the old untrusted subsystem is discarded, its powers must all be revoked, which necessarily implies that a new subsystem will need a new powerbox.

In the following example, the less trusted object may be granted a Timer, a FileMaker that makes new files, and a url. The object may request a different url in the course of operations, in which case the powerbox will ask the user for authorization on the objects's behalf; the old url is revoked, and the new one substituted, so that the object never has authority for more than one url at a time. The object that operates the powerbox may revoke all authorities at any time, or it may choose to revoke the Timer alone. Finally, the operator of this powerbox may, for reasons external to the powerbox's knowledge, decide to grant an additional authority during operations, an authority whose nature is not known to the powerbox.

<pre>
# E sample
# The authorized url may change during operations, so it is a var
def makePowerboxController(optTimer,
optMakeFile,
var optUrl,
optMakeUrl,
makeDialogVow) {

# In the revokers map, the object being revoked is the key, the revoker
# is the value. Note it is the actual object, not the forwarder to the
# object, that is the key.
var revokers := [].asMap()

# when a revokable forwarder is made, the revoker is automatically
# placed in the map of revokers
def makeRevokableForwarder(object) :near {
var innerObject := object
def revoker {
to revoke() {innerObject := null}
}
revokers with= (object, revoker)
def forwarder {match [verb, args] {return E.call(innerObject, verb, args)}}
return forwarder
}

# makeFileFacet is exposed to less trusted realm; guard the path it receives
# This simple file facet only supplies 2 methods that return immutables
# If the file handed out mutable objects, such as streams, these would have
# to be wrapped with revokableForwarders as well.
def makeFileFacet(path :String) :near {
def theFile := optMakeFile(path)
def fileFacet {
to getText() :String {theFile.getText()}
to setText(text :String) {theFile.setText(text)}
}
return makeRevokableForwarder(fileFacet)
}

# makeFile is actually handed to the less trusted object
# It is either null or a revokable forwarder for makeFileFacet
# In other words, makeFile is a revokable maker of revokable file facets
def makeFile
if (optMakeFile == null) {
bind makeFile := null
} else {
bind makeFile := makeRevokableForwarder(makeFileFacet)
}

# Like the file facet, this url facet only supports methods that return
# immutables.
def makeRevokableUrlFacet(optUrl) :near {
if (optUrl == null) {
return null
} else {
def urlFacet {
to getBytes() :pbc {optUrl.getBytes()}
}
return makeRevokableForwarder(urlFacet)
}
}

# Return a vow for a new url
# Use dialog with user to determine if new url should be granted
# Vow resolves to null if anything goes wrong
def makeRevokableUrlVow := {
def makeUrlVow(requestedUrl :String, why :String) :vow {
def urlDialogVow :=
makeDialogVow("Url Request",
`<html>
Confined Object requesting url for this reason:$why
</html>`,
requestedUrl,
["Grant", "Refuse"])
return when (urlDialogVow) -> {
if (urlDialogVow.getButton() == "Grant") {
optUrl := optMakeUrl(urlDialogVow.getText())
makeRevokableUrlFacet(optUrl)
} else {null}
} catch prob {null}
}
return makeRevokableForwarder(makeUrlVow)
}

var caps := [].asMap()
caps with= ("TIMER", makeRevokableForwarder(timer))
caps with= ("FILEMAKER", makeFile)
caps with= ("URL", makeRevokableUrlFacet(optUrl))

def powerbox {

# any of these capabilities may be null, i.e., all are optional
# in a powerbox, strictly at the whim of the powerbox operator
# who created the powerboxcontroller and the powerbox
to optCap(key :String) :any {return caps.get(key, null)}

# When the less trusted object requests a new url, the
# old url is immediately revoked, and the promise for the
# new url is substituted
# If the powerbox has revokedAll, any attempt to requestUrl
# will throw an exception back to the untrusted object
# The "why" parameter is the less trusted object's justification
# for needing the url
to requestUrl(requestedUrl :String, why :String):vow {
if (optUrl != null) {revokers[optUrl].revoke()}
def revokableUrlVow := makeRevokableUrlVow(requestedUrl, why)
caps with= ("URL", revokableUrlVow)
return revokableUrlVow
}
}

def powerboxController {
to revokeAll() {
for each in revokers {each.revoke()}
}
to revokeTimer() {revokers[timer].revoke()}
# Confer an additional capability during execution
to conferCap(key, cap) {
caps with= (key, makeRevokableForwarder(cap))
}
to getPowerbox() {return powerbox}
}
}

# now, show how to create a powerbox and hand it to an untrusted object

def makeUntrustedObject(powerbox) {
def timer := powerbox.optCap("TIMER")
def urlVow := powerbox.requestUrl("http://www.skyhunter.com")
def untrustedObject {
#...
}
return untrustedObject
}

def powerboxOperator() {
def makeDialogVow {#...construct dialog vow
}
# use real objects, not nulls, in typical operation, though nulls are valid arguments
def controller := makePowerboxController(null,
null,
null,
null,
makeDialogVow)
def powerbox := controller.getPowerbox()
def untrusted := makeUntrustedObject(powerbox)
# later, confer an additional authority
def special
controller.conferCap("SPECIAL", special)
# when done with the untrusted object, revoke its powers
controller.revokeAll()
}
</pre>

Both the file facet and the url facet restrict the user to methods that return immutables. If these facets returned mutables, like streams, then those mutables would also have to be wrapped in revokable forwarders. In the general case, this requires the use of a membrane. write section on membranes, and link

====Pet Names and Forgery among partially trusted participants====

E's encrypted authenticated references ensure that random attackers get no traction trying to break into your distributed system. As mentioned in the earlier minChat audit, this means that all interesting break-ins will be made by "insiders", i.e., people who have been granted some capabilities inside your system. We have talked so far about low-level attacks that attempt to acquire or use inappropriately conveyed authority. At a higher conceptual level, people can try to present themselves as someone else and get your user to intentionally, but erroneously, grant other information or capabilities.

minChat dodged this problem because it is a 2-person chat system: the person at the other end of the line will have difficulty convincing your user he is someone else, because your user knows the one and only person given the URI (because he used PGP encryption as described earlier to ensure that only one person got it). But in a multi-person chat system, Bill could try to pretend to be Bob and lure your user into telling him Bob's secrets.

There is no single all-purpose solution to this risk. However, one critical part of any specific solution must be this: Do not allow the remote parties to impose their own names for themselves upon your user.

[[Petnames]]

The general solution is to use ''petnames'', i.e., names your user chooses for people, regardless of how those people might name themselves. Of course, it is reasonable to allow the other people to propose names to your user (called ''nicknames''), but the user must make the final decision. The user must also be able to change her mind at a later date, when her list of participants grows to include not only Bob Smith but also Bob Jones, and she must disambiguate the pet name "Bob" she had had for Smith.

The general layout of such a petname setup might be as follows:

petname sample

Walnut/Secure Distributed Computing/Capability Patterns

2007-08-14T13:07:33Z

DavidHopwood: /* Powerbox Capability Manager */

[[Category:Walnut|4]]

===Capability Patterns===

====Facets====

As discussed in the minChat security review, facets are objects that act as intermediaries between powerful objects and users that do not need (and should not be granted) its full power. We saw a facet in use in the audited version of the eChat program, where the chatFacet. was interposed between the chatController and the remote chat participant. Here is a little general-purpose facet maker:

<pre>

<nowiki># E sample
/**
* <param> target is the underlying powerful object
* <param> allowedMethods is a map. The key is a method name, the value
* is the set of allowed numbers of arguments. So ["receive" =>[0, 2].asSet()]
* would allow the receive method, with either 0 or 2 arguments, to be forwarded.
**/
def makeFacet(target, allowedMethods) {
def filteringFacet {
match [verb, args] {
if (allowedMethods.maps(verb) &&
allowedMethods[verb].contains(args.size())) {
return E.call(target, verb, args)
}
}
}
return filteringFacet
}
def chatController
def chatFacet := makeFacet(chatController, ["receive"=>[1].asSet(),
"receiveFriend"=>[1].asSet()])
</nowiki>

</pre>

Facets of this type can be retrofitted onto an existing system. We did this with very little effort for minChat with the chatFacet, but the technique works for far more complicated problems as well. The capability-secure windowing toolkits that ''E'' has placed on top of Swing and SWT uses facetization as the main tool.

Facets can be made much more sophisticated in their restrictions on access to their underlying object. You can make a facet that logs requests and sends email when certain methods are called. In an SEC-regulated stock exchange facet, you might wish to grant the capability to make a trade only from 9AM to 3PM excluding weekends and holidays.

One interesting example is the use-once facet, which allows the holder of the facet to use the facet only one time. For example, this version of a chatReceiver only allows a single message to be sent:

<pre>

<nowiki># E sample
def onceOnlyReceiver(baseChatController) {
var chatController := baseChatController
def onceOnlyReceiver {
to receive(text) {
chatController.receive(text)
chatController := null
}
}
}</nowiki>

</pre>

This version will throw an exception back to the sender of a second message.

It can be tempting in a facet to suppress a couple of powerful methods in the underlying powerful object and delegate the rest.

<pre>

<nowiki># E sample
def powerfulObject {
to doPowerfulOperation() {
#do powerful operation
}
to doWeak1() {}
to doWeak2() {}
to doWeak3() {}
#....
to doWeak99() {}
}
def badFacet extends powerfulObject {
to doPowerfulOperation() {
#do nothing, no forwarding for the powerful operation, but forward everything else
}
} </nowiki>

</pre>

''Avoid this''. For a facet to remain secure during maintenance, it should never just delegate by default. If a new method is added to a powerful object (in this example, suppose powerfulObject is updated with a new method, doPowerful2()), it should not be exposed through the facet by default: rather, the facet must by default not expose it.

This risk can be exhausting to avoid, but it is always dangerous to accept. The first version of the capability windowing toolkit on Swing suppressed the handful of dangerous methods in the Java version 1.3 of Swing rather than explicitly allowing the safe methods, of which there were thousands. Within 30 days, the entire system was broken: the Java 1.4 Beta included hundreds of new, security-breaking methods. The only saving grace was that we had always known that the first version, thrown together in haste on weekends, was just a proof-of-principle and would have to be replaced. We just hadn't appreciated how soon replacement would be required.

====Revocable Capabilities====

If you wish to give someone restricted access to an object with facets, it is quite likely you will want to revoke access at some point as well.

The simplest way of making a capability revocable is to use a transparent forwarder that includes a revocation method:

<pre>

<nowiki># E sample
def revocableCapabilityMaker(baseCapableObject) {
var capableObject := baseCapableObject
def forwarder {
to revoke() {capableObject := null}
match [verb, args] {E.call(capableObject, verb, args)}
}
return forwarder
}</nowiki>

</pre>

Note that, even though the forwarder is nominally delegating all method invocations (except revoke()) to the capableObject, we cannot use the ''extends'' keyword to capture the behavior. "Extends" creates an immutable reference, so the fact that the capableObject is a var wouldn't allow you to revoke the delegating behavior. Instead we use the match[verb, args] pattern.

Capability revocation, like facet forwarding, can be based on complex sets of conditions: revoke after a certain number of uses, revoke after a certain number of days. This example uses a simple manual revocation. Indeed, this version is too simple to work reliably during system maintenance and upgrade, and a more sophisticated pattern is generally recommended:

<pre>

<nowiki># E sample
def makeCapabilityRevokerPair(baseCapableObject) {
var capableObject := baseCapableObject
def revoker {
to revoke() {capableObject := null}
}
def forwarder {match[verb, args] {E.call(capableObject, verb, args)}}
return [forwarder, revoker]
}
def powerfulObject {
#...big powers
}
def [power, revoker] := makeCapabilityRevokerPair(powerfulObject)</nowiki>

</pre>

In this pattern, the authority of the object and the authority to revoke are separated: you can hand the power to revoke to an object you would not trust with the authority itself. Also, the separate revoker can itself be made revocable.

====Sealers and Unsealers====

A sealer/unsealer pair makes it possible to use untrusted intermediaries to pass objects safely. Use the sealer to make a sealed box that can only be opened by the matching unsealer. E has built-in support for sealer/unsealer pairs:

<pre>

<nowiki>? def makeBrandPair := <elib:sealing.makeBrand>
# value: <makeBrand>

? def [sealer, unsealer] := makeBrandPair("BrandNickName")
# value: [<BrandNickName sealer>, <BrandNickName unsealer>]

? def sealedBox := sealer.seal("secret data")
# value: <sealed by BrandNickName>

? unsealer.unseal(sealedBox)
# value: "secret data"
</nowiki>

</pre>

If you hold the unsealer private, and give the sealer away publicly, everyone can send messages that only you can read. If you hold the sealer private, but give the unsealer away publicly, then you can send messages that recipients know you created, i.e., you can use it as a signature. If you are thinking that this is much like a public/private key pair from public key cryptography, you are correct, though in E no actual encryption is required if the sender, recipient, brand maker, and sent object all reside in the same vat.

While the Brand is built-in, it is possible to construct a sealer/unsealer pair maker in E without special privileges. The "shared variable" technique for making the maker is interesting, and because the same pattern appears in other places (such as the Notary/Inspector, coming up next), we demonstrate it here:

<pre>

<nowiki># E sample
def makeBrandPair(nickname) {
def noObject{}
var shared := noObject
def makeSealedBox(obj) {
def box {
to shareContent() {shared := obj}
}
return box
}
def sealer {
to seal(obj) {return makeSealedBox(obj)}
}
def unsealer {
to unseal(box) {
shared := noObject
box.shareContent()
if (shared == noObject) {throw("invalid box")}
def contents := shared
shared := noObject
return contents
}
}
return [sealer, unsealer]
}
</nowiki>

</pre>

The variable "shared" normally contains the value "noObject", which is private to a particular sealer/unsealer pair and so could never the the actual value that someone wanted to pass in a sealed box. The unsealer tells the box to shareContent, which puts the content into the shared variable, from which the unsealer then extracts the value for the invoker of the unseal method. In a conventional language that used threads for concurrency control, this pattern would be a disaster: different unseal requests could rumble through, overwriting each others' shared content. But by exploiting the atomicity of operational sequences enabled by promise pipelining, this peculiar pattern becomes a clean solution for this, and several other security-related operations.

====Vouching with Notary/Inspector====

Suppose Bob is the salesman for Widget Inc. He persuades Alice to buy a widget. Bob hands Alice a Widget Order Form with a money-receiving capability. It is important to Bob that Alice use the form he gives her, because this particular form (which Bob got from Widget Inc.) remembers that Bob is the salesman who should get the commission. It is important to Alice that she know for sure that, even though she got the order-form from Bob, this is really a Widget Inc. order form, and not something Bob whipped up that will transfer her money directly to his own account. In this case, Alice wants to have Widget Inc. vouch for the order-form she received from Bob. She does this using an Inspector that she gets directly from Widget Inc. The Inspector is the public part of a notary/inspector pair of objects that provide verification of the originator of an object. To be vouchable, the orderForm must implement the startVouch method as shown here:

<pre>

<nowiki># E sample
####### Widget Inc. software #####

#vouching system
#returns a private notary that offers a public inspector
#throws problem if the object being vouched is not vouchable
def makeNotary() {
def nonObject {}
def unvouchedException(obj) {throw(`Object not vouchable: $obj`)}
var vouchableObject := nonObject
def inspector {
to vouch(obj) {
vouchableObject := nonObject
try {
obj.startVouch()
if (vouchableObject == nonObject) {
return unvouchedException(obj)
} else {
def vouchedObject := vouchableObject
vouchableObject := nonObject
return vouchedObject
}
} catch err {unvouchedException(obj)}
}
}
def notary {
to startVouch(obj) { vouchableObject := obj}
to getInspector() {return inspector}
}
return notary
}

#create Widget Inc's notary
def widgetNotary := makeNotary()

#Order form maker
def makeOrderForm(salesPerson) {
def orderForm {
# .... methods for implementing orderForm
to startVouch() {widgetNotary.startVouch(orderForm)}
}
return orderForm
}

#publicly available inspector object
#(accessible through a uri posted on Widget Inc's web site)
def WidgetInspectionService {
to getInspector() {return widgetNotary.getInspector()}
}

##### bob software #####

#scaffold for sample
def getOrderFormFromBob() {return makeOrderForm("scaffold")}

########## Alice's software to vouch for the order form she received from Bob #####

def untrustedOrderForm := getOrderFormFromBob()
def inspector := WidgetInspectionService.getInspector()
def trustedOrderForm := inspector.vouch(untrustedOrderForm)</nowiki>

</pre>

====Proof of Purchase====

"Proof of Purchase" is the simplest of a series of capability patterns in which the goal is not to transfer an authority, but rather to show someone that you have the authority so that they can comfortably proceed to use the authority on your behalf. In Proof of Purchase, the requester of a service is demonstrating to the server that the client already has capability that the server is being asked to use. Unlike the more sophisticated upcoming Claim Check patterns, the proof of purchase client is not concerned about giving the server an excess authority.

An interesting example of Proof of Purchase is [http://www.erights.org/javadoc/java/awt/Component.html Component.transferFocus(fromComponentsList, toComponent)] found in the tamed Swing package. In standard Swing, the holder of any panel reference can steal the focus (with component.requestFocus()). Hence any keystrokes, including passwords, can be swiped from wherever the focus happens to be by sneaking in a focus change. This is a clear violation of POLA. You should be able to transfer focus from one panel to another panel ''only if you have references to both panels''. If you have a reference to the panel that currently has the focus, then you can never steal the focus from anyone but yourself.

A natural-seeming replacement for component.requestFocus() would be requestFocus(currentFocusHolder). It was decided during the taming of Swing, however, that this would be breach-prone. If Alice transferred to Bob, not a panel itself, but rather a simple transparent forwarder on that panel, Alice could collect authorities to other panels whenever Bob changed focus.

Since we had a convenient trusted third party available that already had authority over all the panels anyway (the javax.swing.Component class object), we used the "proof of purchase" pattern instead. The globally available Component.transferFocus method accepts two arguments:

* a list of panels that the client believes to contain, somewhere in their subpanel hierarchies, the focus
* the target panel that should receive the focus

In the common case where a whole window lies inside a single trust realm, the client can simply present a reference to the whole window and be confident that the focus will be transferred.

The interesting thing about Component.transferFocus is that the recipient does not actually need the client's authority to reach the component that already has the focus. The Component class already has that authority. The client must send the authority merely to prove he has it, too.

====Basic Claim Check====

A common activity that brings security concerns into sharp focus is the delicate dance we perform when we use a car valet service. In this situation, we are handing the authority over our most precious and costly possession to a teenager with no more sense of responsibility than a stray cat. The whole valet system is a toothsome exercise in POLA.

In this example, we focus on the sequence of events and trust relationships involved in ''reclaiming'' our car at the end of the evening. The participants include the car owner, the valet service itself, and the random new attendant who is now on duty.

We have already chosen, for better or for worse, to trust the valet service with a key to the car. As the random new attendant comes running up to us, we are reluctant to hand over yet another key to the vehicle. After all, this new attendant might actually be an imposter, eager to grab that new Ferrari and cruise out over the desert. And besides, we already handed the valet service a key to the car. They should be able to use the key they already have, right?

Meanwhile, the attendant also has a trust problem. It would be a career catastrophe to serve up the Ferrari from his parking lot if I actually own the dented 23-year-old Chevy Nova sitting next to it.

In the physical world, we use a ''claim check'' to solve the problem. We present to the attendant, not a second set of car keys, but rather, a proof that we have the authority that we are asking the attendant to use on our behalf.

<pre>

<nowiki># E sample
def claimMgr := {
def carKeys := [].asMap().diverge()
def claimMgr {
to makeClaim(car) :any {
# the claim object has no interesting
# properties except it has
# a unique unforgeable identity
def claim {}
carKeys[claim] := car
return claim
}
to reclaim(claim) :any {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
}
}
}

def attendant {
#return a claim check when car is parked
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}

def car {}
def carOwner := {
var claim := null
def carOwner {
to letAttendantParkCar() :void {
claim := attendant.parkCar(car)
println(claim)
}
to getCarFromAttendant() :void {
println(attendant.retrieveCar(claim))
}
}
}

carOwner.letAttendantParkCar()
carOwner.getCarFromAttendant()
</nowiki>

</pre>

====Basic Claim Check Default Behavior====

Suppose the owner of the car loses the claim check. He can still prove he owns the car by presenting another key. In software, this situation would be comparable to the situation in which the owner hands the attendant a direct reference rather than handing the attendant merely the claim check. The car owner has violated his own security, but it is hard to visualize situations in which this is not a reasonable argument to pass to express his desire. We can cover this case with a small modification to the claimMgr's reclaim method:

<pre>to reclaim(claim) :any {
try {
def car := carKeys[claim]
carKeys.removeKey(claim)
return car
} catch prob {
if (carKeys.contains(claim)) {
return claim
} else {throw(prob)}
}
}</pre>

What should the claimMgr return if the carOwner hands in a car reference for reclaim, if the car is not actually in the claimMgr's parking lot? The answer depends on the application, but such a situation violates the expectations of all the participants sufficiently that throwing an exception seems the safest choice.

====NonTransferable Claim Check====

We are far from done with claim checks. A careful car owner will not actually hand his claim check to the parking lot attendant. Rather, he will merely show the claim check to the attendant. After all, if you hand the claim check over to an imposter, the imposter can turn around and hand the claim check to a real attendant, pretending that he is the owner of the car.

The problem is somewhat different in cyberspace. The good news is, in cyberspace the attendant doesn't return a reference to the car just because you hand him the claim check. Instead, he merely performs the action you ask of him with the car. This set of actions is limited by the attendant's willing behavior. So the claim check is not as powerful a capability as the car itself. But it can still be a powerful capability. And the bad news is, in cyberspace, you can't just "show" it to the attendant. You have to give it to him.

Here we demonstrate a "nontransferable" claim check. This claim check can be handed out at random to a thousand car thieves, and it does them no good. The trick is, before handing over the claim check, the owner inserts into the claim check a reference to the individual he is treating as an attendant. The ClaimMgr compares the person to whom the owner handed the claim, with the attendant who eventually hands the claim to the claimMgr . If these two people are the same, then the owner handed the claim directly to the attendant. Otherwise, there was an intermediary party, and the request should not be honored.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def valetService := {
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def claimMgr {
to makeClaim(car) :any {
def transferableClaim {
to makeNontransferableClaim(intendedRecipient) :any {
return claimSealer.seal([car, intendedRecipient])
}
}
return transferableClaim
}
to reclaim(claim, actualRecipient) :any {
def [car, intendedRecipient] := claimUnsealer.unseal(claim)
if (actualRecipient == intendedRecipient) {
return car
} else {throw("claim not transferable, invalid attendant")}
}
}
def valetService {
to authorizeAttendant(attendant) :void {
attendant.setClaimMgr(claimMgr)
}
}
}

def makeAttendant() :any {
def claimMgr
def attendant {
to setClaimMgr(mgr) :void {bind claimMgr := mgr}
to parkCar(car) :any {
# ...code to park the car...
return claimMgr.makeClaim(car)
}
to retrieveCar(claim) :void {
def car := claimMgr.reclaim(claim, attendant)
# ...code to retrieve car...
# no need to return the car reference, the owner of the claim
# presumably already has such a reference
}
}
return attendant
}

def legitAttendant := makeAttendant()
valetService.authorizeAttendant(legitAttendant)

def carThief {
to parkCar(car) :any {
return println ("Ha! stole the car")
}
to retrieveCar(claim) :void {
try {
legitAttendant.retrieveCar(claim)
println("Ha! didn't get car, but got control")
} catch prob {println(`rats! foiled again: $prob`)}
}
}

def carOwner := {
def car{}
var claim := null
def carOwner {
to letValetPark(attendant) :void {
claim := attendant.parkCar(car)
println(claim)
}
to letValetRetrieve(attendant) :void {
def noTransferClaim := claim.makeNontransferableClaim(attendant)
println(attendant.retrieveCar(noTransferClaim))
}
}
}

carOwner.letValetPark(legitAttendant)
carOwner.letValetRetrieve(carThief)
carOwner.letValetRetrieve(legitAttendant)
</nowiki>

</pre>

Note an important implication in this pattern: the ClaimMgr winds up in a position to accumulate references to all the entities a claim check holder treats as an attendant. In this example, the ClaimMgr gets a reference to the carThief as a result of the carOwner's casual handing out of claim checks. It seems unlikely that the ClaimMgr can harm the carOwner's interests with this reference, but in other circumstances the reference may not be so harmless. To reduce our risk exposure to the alleged attendants to whom we hand the claim check, we have increased our risk exposure to the ClaimMgr.

Note also the limitations on the nontransferability of this pattern. The carOwner can still transfer authority, either by handing someone a reference to the car, or by handing out the transferableClaim from which nontransferableClaims can be made. The nontransferability is voluntarily chosen by the carOwner. You can't prevent people from delegating their authority, and even this pattern doesn't change that fact.

====Oblivious Claim Check: Loan Officer Protocol====

{| style="float: right; width: 2in; border-style: inset; border-width: 3;background-color: #FFFF99; font-size:80%"
|
Voluntary Oblivious Compliance, or VOC, was pioneered by the [http://www.erights.org/history/client-utility.html Client Utility System]. VOC is a field only recently recognized by the capability-security community as an important area of exploration; the claim check patterns here are early fruit of that research. VOC is irrelevant in the classical cypherpunk view of the world, where every person is a rugged individualist making all his own authority-granting decisions with little regard for other people's issues. In a world filled with corporations, governments, and other policy-intensive organizations, however, it is an area of real value even though it is not really a security matter. Why is it not security? We consider it beyond the scope of "security" for a simple but compelling reason: it is not enforceable. Unenforceable security in cyberspace has been proven, over and over again in the course of the last decade, to be a joke played on all the participants. VOC states in its very name the limits of its applicability: it only works with volunteers. Don't be fooled into thinking this is security.
|}

Let us consider a somewhat different problem. Suppose that different attendants are trusted to handle different cars by the valet service. One valet has a motorcycle license and parks all the Harleys. Another has a multi-engine pilot's license and parks all the Boeing 747s. Of course, the one with the motorcycle license is a teenager who has always wanted to try his hand at parking a 747, and knows his lack of experience is not a problem. In this situation, each attendant has a different set of authorities at his command; just because you hand your claim check to a legit attendant doesn't mean the valet service thinks it would be a good idea to let that attendant drive your vehicle. A more generalized way of stating the problem is, in this case the authorities of the individual receivers of the claim checks vary, and management of the individual receiver's authorities is beyond the scope of what the ClaimManager should be trying to figure out. After all, the individuals know all their own authorities; it would be poor design (and unmaintainable at scale) for the ClaimManager to try to duplicate this information.

This situation, while not a part of the real-world valet service problem, has a significant area of application in cyberspace. This area is ''Voluntary Oblivious Compliance'', or VOC. Let us consider a more sensible example. Alice works for HPM, and Bob works for Intil. HPM and Intil are often competitors, but Alice and Bob are working on a joint project from which both companies expect to profit handsomely. The Official Policy Makers of HPM have identified a number of documents which can be shared with Intil, and indeed have forwarded to Intil references to the allowed docs. Alice wants to refer Bob to a particular HPM document, but ''only if sharing the document is allowed'' under the HPM policy. In this case, the VOCclaimCheck that Alice sends to Bob demands that Bob demonstrate to HPM's ClaimMgr that he already has authority on the document before fulfilling the claim. To prove his authority, Bob sends to the ClaimMgr all the HPM doc authorities he has (i.e., the list of docs HPM handed to Intil). Only if both Alice and Bob already have authority on the object does Bob get the document. This is sometimes called the Loan Officer Protocol, in reference to the old adage that a loan officer will not give you the loan unless you first prove that you don't need it.

Since bob can't get the reference unless he proves he doesn't need it, we can now see why this is a pattern of Voluntary Oblivious Compliance. It is voluntary, because Alice could just send Bob the document and circumvent the system. And it is oblivious, because Alice doesn't need to know whether a document can be shared with Bob before sending it.

Going back to the parking lot attendant who wants to park the 747, he has to demonstrate to the ClaimManager that he has the keys to the 747 before the Claim Manager will let him go for it. The owner of the 747 is much relieved.

Humorous as the 747 example might be, we will now switch to the scenario with Alice, Bob, HPM, and Intil for our sample code. The basic strategy is that the ClaimMgr not only examines the claim check from Alice, it also examines the list of authorities that Bob hands over to see if any of Bob's authorities match the one inside Alice's claim.

<pre>

<nowiki># E sample
def makeBrandPair := <elib:sealing.makeBrand>
def [claimSealer, claimUnsealer] := makeBrandPair("claim")
def HPMDocClaimMgr {
to makeClaim(doc) :any {
return claimSealer.seal(doc)
}
to matchClaim(claim, listOfCandidates) :any {
def doc := claimUnsealer.unseal(claim)
for each in listOfCandidates {
if (doc == each) {return each}
}
throw("No match from claimCheck to candidate auths")
}
}

def intilSharedDocs := [def doc1{}, def doc2{}, def doc3{}]

def bob {
to lookAtHPMDoc(claim) :void {
try {
def doc := HPMDocClaimMgr.matchClaim(claim, intilSharedDocs)
println(`reading doc: $doc`)
} catch prob {
println(`can't read: $claim`)
}
}
}

def alice {
to sendDoc(doc, recipient) :void {
def claim := HPMDocClaimMgr.makeClaim(doc)
recipient.lookAtHPMDoc(claim)
}
}
alice.sendDoc(doc2, bob)
alice.sendDoc(def doc4{}, bob)
</nowiki>

</pre>

The oblivious claim check pattern can require scattering even more authority to the winds than the nontransferable claim check. The recipient of the claim check (bob) needs to have all the authorities that alice might give to him, rather than merely the ones she actually does give to him. And the trusted third party who matches the claim check against the list of possibilities (the HPMDocClaimMgr) gets to accumulate authority to everything that bob thinks alice might be trying to send him. In the example scenario, this is just fine. But some care is required.

====Oblivious Claim Checks as Guards====

An elegant style of using VOC claim checks is to set up the pattern as a pair of guards. Alice would use the ClaimCheck guard to send a reference to Bob, and Bob would use the CheckedClaim guard, with the list of candidate references, to receive the authority. We will show the implementation of the BuildGuards ClaimCheck and CheckedClaim guards in [[Walnut/Advanced_Topics|Advanced Topics]] when we talk about writing your own guards, but their usage would appear as follows:

<pre># E syntax
def bob {
to lookAtHPMDoc(doc :CheckedClaim[intilSharedDocs]) :void {
if (!E.isBroken(doc)) {
println(`reading doc: $doc`)
} else {println(`can't read: $claim`)}
}
}

def alice {
to sendDoc(doc, recipient) :void {
recipient.lookAtHPMDoc(doc :ClaimCheck)
}
}</pre>

The ClaimCheck guard coerces the doc into a sealed representation of itself. The CheckedClaim guard unseals the claim and matches it against the authorities in the intilSharedDocs list. As a guard, it is better style to return a broken reference than to throw an exception if something goes wrong. In the parameter guard, if an exception were thrown, the recipient would have no chance to do anything with the problem, the exception would be thrown directly back to the sender before the recipient was even aware there was an issue.

====Oblivious NonTransferable Claim Check====

It is possible to make nontransferable oblivious claim checks as well. We leave the code as an exercise for the reader.

====Powerbox Capability Manager====

The powerbox pattern collects diverse elements of authority management into a single object. That object, the ''powerbox'', then becomes the arbiter of authority transfers across a complex trust boundary. One of the powerbox's most distinctive features is that it may be used for dynamic negotiations for authority during operation. The less trusted subsystem may, during execution, request new authorities. The powerbox owner may, in response to the request, depending on other context that it alone may have, decide to confer that authority, deny the authority, or even grant the request authority after revoking other authorities previously granted.

The powerbox is particularly useful in situations where the object in the less trusted realm does not always get the same authorities, and when those authorities may change during operation. If the authority grant is static, a simple emaker-style authorization step suffices, and a powerbox is not necessary. If the situation is more complex, however, collecting all the authority management into a single place can make it much easier to review and maintain the extremely security-sensitive authority management code.

Key aspects of the powerbox pattern include:

* A powerbox uses strict guards on all arguments received from the less trusted realm. In the absence of guards, even an integer argument received from untrusted code can play tricks: the first time the integer-like object (that is not really an integer) is asked to "add", it returns the value "123"; but the second time, it returns the value "456", with unpredictable (and therefore insecure) results. An ":int" guard on the parameter will prevent such a fake integer from crossing into your realm.
* A powerbox enables revocation of all the authorities that have been granted. When you are done using a less trusted subsystem, the authorities granted to it must be explicitly revoked. This is true even if the subsystem is executing in your own vat and you nominally have the power to disconnect all references to the subsystem and leave the subsystem for the garbage collector. Even after being severed in this fashion, the subsystem will still exist for an unbound amount of time until the garbage collector reaches it. If the authorities it has received have not been revoked, it can surprise you with its continued operations, and continued use of authority. Not all kinds of objects in the Java API can be made directly revocable at this time, because an ''E'' revocable forwarder cannot be used in all the places where an actual authority-carrying Java object is required. For example, the untrusted object may want to create a new image from an url. The natural way of doing this would be to call the Java Icon class constructor with (url) as the argument. But if an E forwarder were handed to this class constructor, the constructor would throw a type exception. Different solutions to such impedence mismatches with the Java type system are required in different situations. For the icon maker, it might be acceptable to require that the untrusted object read the bits of the image from the url (through a revocable forwarder) and then convert the bits into an icon.
* A new powerbox is created for each subsystem that needs authorities from within your trust realm. If a powerbox is shared across initiations of multiple subsystems, the powerbox may become the channel by which subsystems can illicitly communicate, or the channel by which an obsolete untrusted subsystem can interfere with a new one. When the old untrusted subsystem is discarded, its powers must all be revoked, which necessarily implies that a new subsystem will need a new powerbox.

In the following example, the less trusted object may be granted a Timer, a FileMaker that makes new files, and a url. The object may request a different url in the course of operations, in which case the powerbox will ask the user for authorization on the objects's behalf; the old url is revoked, and the new one substituted, so that the object never has authority for more than one url at a time. The object that operates the powerbox may revoke all authorities at any time, or it may choose to revoke the Timer alone. Finally, the operator of this powerbox may, for reasons external to the powerbox's knowledge, decide to grant an additional authority during operations, an authority whose nature is not known to the powerbox.

<pre>
# E sample
# The authorized url may change during operations, so it is a var
def makePowerboxController(optTimer,
optMakeFile,
var optUrl,
optMakeUrl,
makeDialogVow) {

# In the revokers map, the object being revoked is the key, the revoker
# is the value. Note it is the actual object, not the forwarder to the
# object, that is the key.
var revokers := [].asMap()

# when a revokable forwarder is made, the revoker is automatically
# placed in the map of revokers
def makeRevokableForwarder(object) :near {
var innerObject := object
def revoker {
to revoke() {innerObject := null}
}
revokers with= (object, revoker)
def forwarder {match [verb, args] {return E.call(innerObject, verb, args)}}
return forwarder
}

# makeFileFacet is exposed to less trusted realm; guard the path it receives
# This simple file facet only supplies 2 methods that return immutables
# If the file handed out mutable objects, such as streams, these would have
# to be wrapped with revokableForwarders as well.
def makeFileFacet(path :String) :near {
def theFile := optMakeFile(path)
def fileFacet {
to getText() :String {theFile.getText()}
to setText(text :String) {theFile.setText(text)}
}
return makeRevokableForwarder(fileFacet)
}

# makeFile is actually handed to the less trusted object
# It is either null or a revokable forwarder for makeFileFacet
# In other words, makeFile is a revokable maker of revokable file facets
def makeFile
if (optMakeFile == null) {
bind makeFile := null
} else {
bind makeFile := makeRevokableForwarder(makeFileFacet)
}

# Like the file facet, this url facet only supports methods that return
# immutables.
def makeRevokableUrlFacet(optUrl) :near {
if (optUrl == null) {
return null
} else {
def urlFacet {
to getBytes() :pbc {optUrl.getBytes()}
}
return makeRevokableForwarder(urlFacet)
}
}

# Return a vow for a new url
# Use dialog with user to determine if new url should be granted
# Vow resolves to null if anything goes wrong
def makeRevokableUrlVow := {
def makeUrlVow(requestedUrl :String, why :String) :vow {
def urlDialogVow :=
makeDialogVow("Url Request",
`<html>
Confined Object requesting url for this reason:$why
</html>`,
requestedUrl,
["Grant", "Refuse"])
return when (urlDialogVow) -> {
if (urlDialogVow.getButton() == "Grant") {
optUrl := optMakeUrl(urlDialogVow.getText())
makeRevokableUrlFacet(optUrl)
} else {null}
} catch prob {null}
}
return makeRevokableForwarder(makeUrlVow)
}

var caps := [].asMap()
caps with= ("TIMER", makeRevokableForwarder(timer))
caps with= ("FILEMAKER", makeFile)
caps with= ("URL", makeRevokableUrlFacet(optUrl))

def powerbox {

# any of these capabilities may be null, i.e., all are optional
# in a powerbox, strictly at the whim of the powerbox operator
# who created the powerboxcontroller and the powerbox
to optCap(key :String) :any {return caps.get(key, null)}

# When the less trusted object requests a new url, the
# old url is immediately revoked, and the promise for the
# new url is substituted
# If the powerbox has revokedAll, any attempt to requestUrl
# will throw an exception back to the untrusted object
# The "why" parameter is the less trusted object's justification
# for needing the url
to requestUrl(requestedUrl :String, why :String):vow {
if (optUrl != null) {revokers[optUrl].revoke()}
def revokableUrlVow := makeRevokableUrlVow(requestedUrl, why)
caps with= ("URL", revokableUrlVow)
return revokableUrlVow
}
}

def powerboxController {
to revokeAll() {
for each in revokers {each.revoke()}
}
to revokeTimer() {revokers[timer].revoke()}
# Confer an additional capability during execution
to conferCap(key, cap) {
caps with= (key, makeRevokableForwarder(cap))
}
to getPowerbox() {return powerbox}
}
}

# now, show how to create a powerbox and hand it to an untrusted object

def makeUntrustedObject(powerbox) {
def timer := powerbox.optCap("TIMER")
def urlVow := powerbox.requestUrl("http://www.skyhunter.com")
def untrustedObject {
#...
}
return untrustedObject
}

def powerboxOperator() {
def makeDialogVow {#...construct dialog vow
}
# use real objects, not nulls, in typical operation, though nulls are valid arguments
def controller := makePowerboxController(null,
null,
null,
null,
makeDialogVow)
def powerbox := controller.getPowerbox()
def untrusted := makeUntrustedObject(powerbox)
# later, confer an additional authority
def special
controller.conferCap("SPECIAL", special)
# when done with the untrusted object, revoke its powers
controller.revokeAll()
}
</pre>

Both the file facet and the url facet restrict the user to methods that return immutables. If these facets returned mutables, like streams, then those mutables would also have to be wrapped in revokable forwarders. In the general case, this requires the use of a membrane. write section on membranes, and link

====Pet Names and Forgery among partially trusted participants====

E's encrypted authenticated references ensure that random attackers get no traction trying to break into your distributed system. As mentioned in the earlier minChat audit, this means that all interesting break-ins will be made by "insiders", i.e., people who have been granted some capabilities inside your system. We have talked so far about low-level attacks that attempt to acquire or use inappropriately conveyed authority. At a higher conceptual level, people can try to present themselves as someone else and get your user to intentionally, but erroneously, grant other information or capabilities.

minChat dodged this problem because it is a 2-person chat system: the person at the other end of the line will have difficulty convincing your user he is someone else, because your user knows the one and only person given the URI (because he used PGP encryption as described earlier to ensure that only one person got it). But in a multi-person chat system, Bill could try to pretend to be Bob and lure your user into telling him Bob's secrets.

There is no single all-purpose solution to this risk. However, one critical part of any specific solution must be this: Do not allow the remote parties to impose their own names for themselves upon your user.

[[Pet_Names]]

The general solution is to use ''pet names'', i.e., names your user chooses for people, regardless of how those people might name themselves. Of course, it is reasonable to allow the other people to propose names to your user (called ''nicknames''), but the user must make the final decision. The user must also be able to change her mind at a later date, when her list of participants grows to include not only Bob Smith but also Bob Jones, and she must disambiguate the pet name "Bob" she had had for Smith.

The general layout of such a pet name setup might be as follows:

pet name sample

Safe Serialization Under Mutual Suspicion/Introducing Data E

2007-08-09T23:44:35Z

DavidHopwood: /* Lessons of ''Deconstruction Serialization'' */

=Lessons of ''Deconstruction Serialization''=
The body of each chapter is presented using running code examples, and with detailed enough explanation that you should be able to follow this code. For those that wish only to understand the general lessons and how they may be applied to more conventional serialization systems, see the "Lessons of..." and "Corresponding Concepts in Convention Serialization" sections at the beginning and end of each chapter

The "Deconstruction Serialization" chapter defines our serialization format, Data-E, by subsetting a programming language, '''''E'''''. This move is inessential, but it allows us to more easily understand what's happening.

Many existing systems (Lisps, Smalltalk) often print an object as an expression that, if evaluated, would reconstruct that object. We can understand the data by reusing a subset of our code reading skills. When these printing systems do so reliably, they are often grown into serialization systems, in which the depiction actually is the program it appears to be. We can then understand the semantics of the serialized form by reusing a subset of our understanding of the semantics of the programming language.

(Serialization in Mozart creates the equivalent of a compiled module, providing the semantic correspondence but not the visibility. Perhaps these can be decompiled.)

In these terms, Java has three very different depiction systems.
* The printed form of a Java object is simply its response to <tt>toString()</tt>. While these are often in the form of expressions that would reconstruct the object, often they're not, and there's no general convention.
* Java Object Serialization Streams, or JOSS [ref JOSS], defines a complex opaque binary format which few know how to parse, and which is rarely made visible. JOSS is implemented using special powers (native methods for violating encapsulation) not available to other objects, making it too dangerous to use under mutual suspicion. However, JOSS also has an extensive and well thought out set of hooks for customizing serialization and unserialization. The logic of these hooks strikes the balance we need between flexibility and security. The corresponding hooks in Data-E are based on lessons learned from JOSS.
* In apparent reaction to the maintenance problems created by opacity and the private access, Java now has an additional serialization framework, the XMLEncoder [ref XMLEncoder]. The XMLEncoder writes depictions which are semantically identical to Java programs. This format combines the semantics of Java with the readability of XML. Like Data-E, this system serializes only by interacting with the public protocol of the original objects, and unserializes by evaluating the depiction-as-program which again only uses public protocols to perform the reconstruction. Unfortunately, the XMLEncoder is designed around the ''Java Beans'' conventions, which conflates access with initialization, rendering its design useless for our present purposes.

To produce a depiction of an object graph, a serializer must somehow obtain a representation of each object adequate for calculating an overall depiction. In the printing frameworks, like Java's <tt>toString()</tt>, the representation offered is a ''depiction'' -- it is already only bits, and each object is responsible for traversing the portion of the subgraph rooted in itself. This is maximally flexible -- it allows an object to claim anything it likes. Used for serialization, this flexibility has fatal security problems, as explained in the [[Safe_Serialization_Under_Mutual_Suspicion/Manipulating_Authority_at_the_Exits|next chapter]].

<a name="self-portrait"></a>
In our approach, the serializer must obtain for each object a ''portrayal'' -- a representation of that object in terms of live references to other objects. The serializer's traversal proceeds as it obtains a portrayal for each of these "components", etc. A serializer can simply ask an object to provide a portrayal of itself -- the object's ''self portrait'' -- or, as we will see, it can derive or substitute its own portrayal of the object as an expression of some other policy objective. However it obtains these portrayals, the resulting depiction is a literal picture only of the graph of these portrayals, rather than the actual graph of objects being serialized.

=Concrete Embodiment in '''''E'''''=

{{:Old 0.8 updoc prelude}}

Although the ideas in this paper should be applicable to any object-capability language and many serialization formats, as previously mentioned, for concreteness, we present the implementation of these ideas in '''''E''''' as applied to Data-E. When an example is shown as an '''''E''''' command line session, like

<code>
? 2 + 3
# value: 5
</code>

then the example also doubles as an executable regression test. By [http://www.erights.org/elang/tools/updoc.html updocing] the page containing the examples, you can see whether the system behaves as shown by the example. If you installed '''''E''''' at, for example, "<tt>c:/Program Files/erights.org</tt>" and placed "<tt>c:/Program Files/erights.org/scripts</tt>" on your <tt>PATH</tt>, then in a directory containing the chapters of this paper, at a shell prompt you can type:

<code>
$ updoc.e deconstructing.html
directory-path/deconstructing.html:...............................
</code>

(Though please see "[http://www.erights.org/elang/tools/updoc.html#security Security Considerations]" before running this or any other Updoc script.)Each of the dots is a test case that successfully passed, like the above "<tt>2 + 3</tt>". As you read, if you are curious about how a variation of an example would behave, make a copy of the page, edit appropriately, and updoc it. Or try the examples interactively at a <tt>rune</tt> command-line:

<code>
$ rune
? 2 + 3
# value: 5

?
</code>

The <tt>rune</tt> program starts an '''''E''''' read-eval-print loop. The "?" is the '''''E''''' prompt. To exit <tt>rune</tt>, type the end-of-file character: Control-D or Control-Z depending on your shell.

In order to have a common point of reference, this paper assumes a basic prior knowledge of Java. JOSS (Java's Object Serialization Streams) [ref JOSS] is occasionally used for comparison, so a prior knowledge of it will help, but is not required.

We assume only that prior knowledge of '''''E''''' explained in the Ode ("Capability-based Financial Instruments") [ref Ode] and that explained in the next section on "'''''E''''''s URI Expressions". '''''E''''' syntactically resembles other C tradition object languages, such as Java, C++, C#, and Python. When the meaning of '''''E''''' code isn't covered by the Ode or the next section, and isn't obvious by analogy with Java, we will explain as we go. For more on '''''E''''', please see [ref erights.org, Walnut].

<a name="uri-exprsns"></a>
=='''''E''''''s URI Expressions==

An unfamiliar bit of '''''E''''' syntax, needed to understand the examples in this paper, is the ''URI expression'', written as a URI string between angle brackets.

<pre>? def f := <file:/foo/bar>
# value: <file:c:/foo/bar>
</pre>

The protocol name to the left of the URI's colon (<tt>file</tt> here, but any identifier) is transformed (mangled) into the name of the variable (<tt>file__uriGetter</tt>) whose value is asked to retrieve the named resource. The characters between the colon and the close angle bracket (which must be [http://www.erights.org/javadoc/org/quasiliteral/syntax/URIKit.html#isURIC(char) legal characters] for a URI body), becomes the literal resource name to be looked up (<tt>"/foo/bar"</tt>). So the above session is a shorthand for the equivalent:

<pre>? def f := file__uriGetter.get("/foo/bar")
# value: <file:c:/foo/bar>
</pre>

Besides accessing the kind of resources normally accessed by URLs, the URI expression is also used as '''''E''''''s module import mechanism. The typical form of import in '''''E''''' is

<pre>def name := <import:fully-qualified-name></pre>

where ''fully-qualified-name'' is the full name, including package prefix, of an '''''E''''' module or a [http://www.erights.org/elib/legacy/taming.html safe] Java class. (In order to make the extensive Java libraries available in '''''E''''' without sacrificing capability security, we must ''tame'' them -- determine what subset of their public interface is consistent with capability security principles. As part of this taming process, we declare certain Java classes to be "safe", and therefore generally importable.) Because fully qualified names can be long, they are often factored as follows:

<pre>def <packgeName> := <import:package-prefix.*>
...
def name := <packageName:rest-of-path></pre>

The package subtree rooted at <tt>"org.erights.e.elib"</tt> is provided as a built-in convenience, as if we had already executed

<pre>def <elib> := <import:org.erights.e.elib.*>
</pre>

As a result,
<pre>? def deSubgraphKit := <elib:serial.deSubgraphKit>
# value: <deSubgraphKit>
</pre>

is equivalent to

<pre>? def deSubgraphKit := <import:org.erights.e.elib.serial.deSubgraphKit>
# value: <deSubgraphKit>
</pre>

Such a package subtree root gives access only to that subtree of the original package tree. Similarly, as will be explained in [http://www.erights.org/data/serial/jhu-paper/exit-security.html Manipulating Authority at the Exits], a directory can be used as a uriGetter in order to give access only to a subtree of the file system, as retrieved by names relative to that directory.

<a name="previews"></a>

=Previews of Data-E Serialization=
In the Data-E System, we compose a serializer or unserializer from a pair of ''Data-E Kits'', such as the <tt>deSubgraphKit</tt> already imported above. Each kit knows how to ''recognize'' and ''build'' a given kind of Data-E representation. The <tt>deSubgraphKit</tt> is special, in that the representation it traffics in is subgraphs of actual objects. All the other representations are depictions of subgraphs expressed in the Data-E "language". For example, the <tt>deSrcKit</tt> traffics in representations of Data-E as source strings, written in the Data-E subset of the '''''E''''' source language. In this document, to make clear when we're looking at Data-E rather than '''''E''''' source, all Data-E source strings are shown prefixed with <tt>"de: "</tt>.

<pre>? def deSrcKit := <elib:serial.deSrcKit>
# value: <deSrcKit>
</pre>

To ''serialize'' is to recognize a subgraph and to build a depiction.

<pre>? "de: " + deSubgraphKit.recognize([false, 3], deSrcKit.makeBuilder())
# value: "de: def t__0 := [false, def t__2 := 3]"
</pre>

Each <tt>recognize(..)</tt> method takes two arguments -- the input representation to recognize (here, the subgraph to traverse), and a builder to call as parts of the representation are recognized, in order to build the output representation (here, a Data-E source string). Each kit provides a <tt>recognize(..)</tt> method for accepting its form of representation as input, and a <tt>makeBuilder()</tt> for making a builder to build its form of representation as output. The <tt>recognize(..)</tt> method returns its argument builder's final output.

The <tt>deASTKit</tt> manages another depiction of Data-E programs: as Abstract Syntax Trees, as explained in [[Safe_Serialization_Under_Mutual_Suspicion/Appendix_A|Appendix A: The Data-E Manual]]. For present purposes, we care only about one feature of this kit, that it simplifies the expression a bit during building; for example, by removing unnecessary temporary variables. Interposing it between between the <tt>deSubgraphKit</tt> and the <tt>deSrcKit</tt>, we build our first expository serialize function, <tt>serialize_a</tt>. (All functions so named are for expository purposes only. See Appendix A for a guide to realistic usage.)

<pre>? def deASTKit := <elib:serial.deASTKit>
# value: <deASTKit>

? def serialize_a(root) :String {
> def ast := deSubgraphKit.recognize(root, deASTKit.makeBuilder())
> "de: " + deASTKit.recognize(ast, deSrcKit.makeBuilder())
> }
# value: <serialize_a>

? serialize_a([false, 3])
# value: "de: [false, 3]"</pre>

To ''unserialize'' is to recognize a depiction and to build a subgraph. The matching expository unserialize function follows. Parameters in '''''E''''' are actually patterns, of which the most common is a simple variable name, which defines the variable and binds it to the specimen (the argument passed in). Here we see [http://www.erights.org/elang/grammar/quasi-overview.html a pattern] for stripping off the additional prefix we added above. This pattern matches a string beginning with <tt>"de: "</tt>. If the specimen is such a string, then it matches the rest of the string against the pattern following the <tt>"@"</tt> -- in this case a simple variable name which is bound to the remainder of the string.

<pre>? def unserialize_a(`de: @src`) :any {
> deSrcKit.recognize(src, deSubgraphKit.makeBuilder())
> }
# value: <unserialize_a>

? unserialize_a("de: [false, 3]")
# value: [false, 3]</pre>

The result of evaluating the depiction-as-expression is a reconstruction of the original subgraph. The case shown above stays clear of all the problematic cases for serialization: All the objects in the graph being serialized here (a boolean, an integer, and a list) are ''transparent'' -- they willingly divulge all their state to their clients through their public protocol. All the objects participating in the above serialization -- the serialize function and the objects being depicted -- seek only literal accuracy; and likewise during the above unserialization. We call this unproblematic starting case ''literal realism for transparent subgraphs''.

==A Proper Failure==

Objects defined in '''''E''''' are encapsulated by default. If we make an encapsulated object and try to serialize it:

<pre>? def capsule {}
# value: <capsule>

? serialize_a(capsule)
# problem: Can't uneval <capsule></pre>

we find our simple serialize function fails, as it must. Usually this failure will be the desired behavior. When it isn't, we have several alternatives.

==Unconditional Transparency==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#FFFFE8"
|
In Java or Smalltalk, the methods on class <tt>Object</tt> define the messages all objects are expected to respond to, and provide default behaviors for those methods. The equivalent in '''''E''''' are the [http://www.erights.org/elang/blocks/miranda.html Miranda Methods]. To avoid collision with programmer-chosen names, Miranda method names begin with a double underscore.
|}A serializer asks an object for its [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E#self-portrait| self portrait]] with the <tt>__optUncall()</tt> message. The corresponding default (Miranda) method returns <tt>null</tt>, indicating that no self portrait is offered. An object which overrides this to return a triple is ''unconditionally transparent'' -- it offers its self portrait to any client, just for the asking. The triple describes a call to be performed during unserialization to create the reconstruction of the original object. We start with a simple example:

<pre>? def iAmFive {
> to __optUncall() :__Portrayal {
> [2, "add", [3]]
> }
> }
# value: <iAmFive>

? serialize_a(iAmFive)
# value: "de: 2.add(3)"</pre>

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#FFFFE8"
|
The expression after the ":" on the __optUncall() method declares what kinds of values it can return. __Portrayal is predefined to be Tuple[any, String, any[]] which allows any three element list in which the second item is a string and the third item is a list of anything.
|}The expression "<tt>2 + 3</tt>" is just a syntactic shorthand for "<tt>2.add(3)</tt>".

<pre>? unserialize_a("de: 2.add(3)")
# value: 5

? unserialize_a("de: 2 + 3")
# value: 5</pre>

The object <tt>iAmFive</tt> is unconditionally transparent, but is not literally, or even usefully, realistic. When we reconstruct an object according to its self-portrait, the result can be quite different from the original.

==Named Exit Points==

Another approach to dealing with problematic objects is ''serialization avoidance'' by making references to these into named exit points. The traversal of a subgraph stops whenever it encounters such references, writing out named exit points instead (the jigsaw plugs shown on [http://www.erights.org/data/serial/jhu-paper/intro.html#depiction-diagram Figure 2: The Three Faces]). We define matching <tt>serialize</tt> and <tt>unserialize</tt> functions customized to treat references to <tt>capsule</tt> as an exit point.To create a custom <tt>serialize</tt> function, we first create a custom ''unscope'' -- a table mapping from exit references to names. This is most conveniently done by modifying the default unscope table -- the one used implicitly in the previous examples.

<pre>? def unscope_b := deSubgraphKit.getDefaultUnscope().diverge()
? unscope_b[capsule] := "foo"
# value: "foo"

? def recognizer_b := deSubgraphKit.makeRecognizer(null, unscope_b)
# value: <unevaler>

? def serialize_b(root) :String {
> def ast := recognizer_b.recognize(root, deASTKit.makeBuilder())
> "de: " + deASTKit.recognize(ast, deSrcKit.makeBuilder())
> }
# value: <serialize_b>

? serialize_b([capsule, 3])
# value: "de: [foo, 3]"</pre>

As we see, in the Data-E expression produced by serialization, a named exit reference becomes a free variable reference. Data-E unserialization ''is'' expression evaluation -- that subset of '''''E''''' expression evaluation applicable to the Data-E subset of '''''E'''''. The inverse of the unscope is therefore just the conventional notion of a ''scope'' (or ''environment''), a mapping from variable names to values. On reconstruction, the named exit points will be reconnected to these values.

<pre>? def scope_b := deSubgraphKit.getDefaultScope().diverge()
? scope_b["foo"] := def newCapsule {}
# value: <newCapsule>

? def unserialize_b(`de: @src`) :any {
> # Just a way of saying eval(src, scope_b)
> deSrcKit.recognize(src, deSubgraphKit.makeBuilder(scope_b))
> }
# value: <unserialize_b>

? unserialize_b("de: [foo, 3]")
# value: [<newCapsule>, 3]</pre>

Each set of exit names together with a mutual understanding about what they may be bound to forms a unique ''micro-standard data format''. Serializers and unserializers must agree on such a micro-standard, and so often come in matched pairs, as above. This agreement still leaves room for separate customization on each side, as with our unserializer's choice to bind a somewhat different object to the name <tt>"foo"</tt> in the scope, perhaps to adapt to a difference in the unserializer's context.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#FFFFE8"
|
We name this abstraction the ''Gordian Surgeon'' both because it simply answers the question "How do we cut this tangle of references?", and also in honor of [http://www.cyclesoft.com/ Gordie Freeman], the co-inventor, along with myself, of its main security property, unforgeable unscope lookup, as explained in the [[Safe_Serialization_Under_Mutual_Suspicion/Exit_Security|next chapter]].
|}

==The Gordian Surgeon==

Since the serialize function, unserialize function, scope, unscope, and (as we will see) uncallers list are often manipulated together, as above, we introduce the ''Gordian Surgeon'' -- an object that knows how to manipulate and wield these five tools in a coordinated fashion to, in effect, cut a subgraph from a donor context, freeze it, thaw it, and transplant it into a recipient graph. The following session is like that above, except that the same <tt>capsule</tt> is used for serialization and unserialization -- as this is the common pattern the surgeon makes convenient. The <tt>addExit(..)</tt> below adds the value-name association to the unscope and adds the inverse name-value association to the scope.

<pre>? def makeSurgeon := <elib:serial.makeSurgeon>
? def surgeon := makeSurgeon.withSrcKit("de: ").diverge()

? surgeon.serialize([capsule, 3])
# problem: Can't uneval <capsule>

? surgeon.addExit(capsule, "foo")

? surgeon.serialize([capsule, 3])
# value: "de: [foo, 3]"

? surgeon.unserialize("de: [foo, 3]")
# value: [<capsule>, 3]</pre>

==Counting "Generations"==

Our first realistic example uses both self-portraits (with unconditional transparency) and named exit points:

<pre>? def makeGenerationCounter(count :int) :any {
> def generationCounter {
>
> /**
> * Make my successor with the next larger count
> */
> to __optUncall() :__Portrayal {
> [makeGenerationCounter, "run", [count+1]]
> }
>
> /** similar purpose as Java's .toString() */
> to __printOn(out :TextWriter) :void {
> out.print(`<gen $count>`)
> }
> }
> }
# value: <makeGenerationCounter>

? def genCounter := makeGenerationCounter(0)
# value: <gen 0></pre>

A <tt>generationCounter</tt> is an object with a single instance variable, <tt>count</tt>. The <tt>makeGenerationCounter</tt> function acts like a constructor -- it makes new <tt>generationCounter</tt> instances. Above, we make the <tt>genCounter</tt> instance with a count of zero. Each <tt>generationCounter</tt> uses the underlined code above to "misrepresent" itself as something that would be made by calling <tt>makeGenerationCounter</tt> with a <tt>count</tt> value one greater than its own.

However, this portrayal enables us to serialize a <tt>generationCounter</tt> only if we can serialize <tt>makeGenerationCounter</tt>, which is just as encapsulated as our earlier <tt>capsule</tt>. Since it is stateless, it is plausible to "serialize" it by not serializing it -- by making it into a named exit point.

<pre>? surgeon.addExit(makeGenerationCounter, "makeGenerationCounter")

? surgeon.serialize(genCounter)
# value: "de: makeGenerationCounter(1)"

? surgeon.unserialize("de: makeGenerationCounter(1)")
# value: <gen 1></pre>

A reconstructed <tt>generationCounter</tt> has a count one greater than its original, thereby accumulating a count of the number of serialize / unserialize cycles it has been through since it was born. Rather than seeing the underlined "misrepresentation" as a problem to prohibit, this example shows how this representational freedom is an opportunity.

=Unserialization as Evaluation=

(This is approximately an abridged presentation of the [[Safe_Serialization_Under_Mutual_Suspicion/Appendix_A|Unserialization as Evaluation]] section of Appendix A: The Data-E Manual.)

As shown above, unserialization can be thought of, or even implemented as, expression evaluation [ref Rees, XMLEncoder]. A depiction is an expression in some programming language, the unserializer is the eval function, the exit references to be reconnected are free variable references, the values to reconnect them to come from the scope (i.e., environment) provided to eval, and the root of the reconstructed subgraph is the value the expression evaluates to. Serialization is the logically inverse process, in which an uneval function is applied to a root and an unscope, and writes out an expression that, were it evaluated in the corresponding scope, would reconstruct the subgraph.

Data-E is the subset of '''''E''''' used for depicting a subgraph as an expression. Ignoring precedence, it consists of the following productions:

==Fundamental Data-E Constructs==
<table cellpadding="6">
<tr valign="top">
<td> <div align="right"><tt>expr ::=</tt></div></td>

<td> <div align="left"><tt>literal | varName | tempName | 
call | defexpr</tt></div></td>
</tr>
<tr valign="top">
<td> <div align="right"><tt>literal ::=</tt></div></td>
<td> <tt>LiteralInt | LiteralFloat64 | 

LiteralChar | LiteralString</tt>
<tt># Each are written as
they are in Java. 
# Examples: 37, 42.3, 'c',
"What me worry?"</tt></td>
</tr>
<tr valign="top">

<td> <div align="right"><tt>varName ::=</tt></div></td>
<td> <div align="left">
<tt>Identifier # but not of the form
"t__"Digit*</tt>
<tt> # These variable names are only
used freely. 

# Example: foo</tt>
</div></td>
</tr>
<tr valign="top">
<td> <div align="right"><tt>tempName ::=</tt></div></td>
<td> <div align="left">

<tt>"t__"Digit* </tt>
<tt># These variable names are never
used freely. 
# Example: t__12</tt>
</div></td>
</tr>
<tr valign="top">

<td> <div align="right"><tt>call ::=</tt></div></td>
<td> <div align="left">
<tt>expr "." Identifier
"(" exprs ")"</tt>

<tt># Example: __makeList.run("foo",
49)</tt>
</div></td>
</tr>
<tr valign="top">
<td> <div align="right"><tt>defexpr ::=</tt></div></td>

<td> <div align="left">
<tt>"def" tempName
":=" expr</tt>
<tt># Where expr may refer to tempName 
# Example: def t__0

:= __makeList.run(1, t__0, 3)</tt>
</div></td>
</tr>
<tr valign="top">
<td> <div align="right"><tt>exprs ::=</tt></div></td>
<td> <div align="left"><tt>(expr (","

expr)*)?</tt></div></td>
</tr>
</table>

==''E'' Syntactic Shorthands generated by <tt>deSrcKit</tt>==

Since we use <tt>deSrcKit</tt> to build the depictions we present for expository purposes, we need to know the shorthands it builds, which are a subset of the shorthands recognized and expanded by '''''E'''''. Going the other way, all '''''E''''' syntactic shorthands, including those below, are recognized by <tt>deSrcKit</tt>, since it uses the '''''E''''' parser to parse and expand its input.

Any valid '''''E''''' expression that expands only into the above Data-E primitives is a valid Data-E expression with the same meaning. Likewise any valid Data-E expression is a valid '''''E''''' expression with the same meaning.
<table cellpadding="6">
<tr valign="top">
<td> <tt>expr "(" exprs ")"</tt>
</td>

<td> is shorthand for 
<tt>expr ".run(" exprs ")"</tt>
If the message name is
left out, it defaults to "<tt>run</tt>". For example, 
 <tt>__makeList("foo",
49)</tt> is shorthand for 

<tt>__makeList.run("foo",
49)</tt>.</td>
</tr>
<tr valign="top">
<td> <tt>"[" exprs "]"</tt></td>
<td> is shorthand for 

<tt>"__makeList.run(" exprs ")"</tt>
Square brackets can be
used to express lists. For example, 
 <tt>["foo",
49]</tt> is shorthand for <tt> 

__makeList.run("foo",
49)</tt>.</td>
</tr>
<tr valign="top">
<td> <tt>expr "[" exprs "]"</tt>
</td>

<td> is shorthand for 
<tt>expr ".get(" exprs ")"</tt>
 For example, 
 <tt>vec[i]</tt> is shorthand for 

<tt>vec.get(i)</tt>.</td>
</tr>
<tr valign="top">
<td> <tt>"<"Identifier">"</tt></td>
<td> is shorthand for 
<tt>Identifier"__uriGetter"</tt>

For example, 
<tt><file></tt> is shorthand
for 
<tt>file__uriGetter</tt> 
</td>
</tr>
<tr valign="top">
<td> <tt>"<"Identifier":"URIC*">"</tt></td>

<td> is shorthand for 
<tt>Identifier"__uriGetter.get(" URIBody ")"</tt>
Where the URIBody is a
literal string whose value is the sequence of URI characters.
As explained earlier in <a href="#uri-exprs">E's
URI Expressions</a>, 

<tt><file:/foo/bar></tt>
is shorthand for 
<tt>file__uriGetter.get("/foo/bar")</tt> 
</td>
</tr>
</table>

Using several cases together:

<pre>? def root := [1, root, 1, <import:java.lang.makeStringBuffer>]
# value: [1, <***CYCLE***>, 1, <makeStringBuffer>]

? def depiction := surgeon.serialize(root)
# value: "de: def t__0 := [def t__2 := 1,
# t__0,
# t__2,
# <import:java.lang.makeStringBuffer>]"

? surgeon.unserialize(depiction)
# value: [1, <***CYCLE***>, 1, <makeStringBuffer>]</pre>

The depiction is shown in the middle following the "de: ". It is written in Data-E and has the following meaning:
* The value of the '''''E''''' expression <tt><import:java.lang.makeStringBuffer></tt> serializes as the Data-E expression <tt>import__uriGetter.get("java.lang.makeStringBuffer")</tt>, as will be explained in the [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation#uncalling|next chapter]]. The <tt>deSrcKit</tt> shows this expression using the URI shorthand, which in this case looks like the original '''''E'''''.
* The <tt>def t__2 := 1</tt> is non-cyclic instance of the <tt>defexpr</tt> production, since <tt>t__2</tt> is not used on its right hand side, even though <tt>t__2</tt> is used later in the serialization.
* The <tt>def t__0 := ...</tt> is a cyclic instance of the <tt>defexpr</tt> production, since t__0 is used on its right hand side, expressing a cyclic data structure.

For those familiar with Java, Data-E should be mostly familiar, but with a few important differences:

* In '''''E''''', a variable definition is an expression. Like assignment, the value of a definition expression is the value of the right hand side.

* <tt>null</tt>, <tt>false</tt>, and <tt>true</tt> are not keywords in '''''E''''', but rather are variable names in '''''E''''''s universal scope and in Data-E's default scope and unscope. This means an expression can count on them having their normal values, so these don't need to be literals. The "<tt>false</tt>" in the first example of [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E#previews| Previews of Data-E Serialization]] above was a variable reference, not a literal, just as it is in '''''E'''''.

* Using only the <tt>literal</tt>, <tt>varName</tt>, and <tt>call</tt> productions, we can write Data-E expressions that will evaluate to new tree structures whose leaves are reattached exit points.

* In '''''E''''', a variable is in scope starting from its defining occurrence, left-to-right, until the close-curly that closes the [http://www.erights.org/elang/blocks/ifExpr.html scope box] (lexical contour) in which it is defined, and not counting regions of nested scope boxes where it is shadowed by a definition of the same name. In Data-E, since there are no constructs that introduce scope boxes (i.e., no constructs with curly brackets), every variable is in scope from its defining occurrence until the end of the depiction as a whole.

* With the <tt>tempName</tt> and non-cyclic <tt>defexpr</tt> productions, we can use Data-E to represent DAGs. For those values that are multiply referenced, we can write out the sub-expression for calculating this value at the first position it needs to appear, as the right hand side of a <tt>define</tt>, capturing its value in a temp variable (<tt>def t__2 := 1</tt>). Everywhere else this value is needed, we use <tt>tempName</tt> to reuse this captured value (<tt>t__2</tt>).

* With a cyclic <tt>defexpr</tt>, we can use Data-E to represent graphs. Unlike other block structured languages, even when the name being defined on the left is used on the right, '''''E''''' still holds strictly to the left-to-right rule. This may seem strange, since <tt>defexpr</tt> must execute right-to-left -- the expression on the right must be evaluated to a value before the variable on the right can be defined to hold this value. When this not yet defined but in-scope variable name is used within the expression on the right, what does it evaluate to before its actual value has been determined? The answer is an ''unresolved promise'', similar to a logic variable or a future. An unresolved promise is an object reference whose designation has not yet been determined. At the moment the above list is created by evaluating the "<tt>[..]</tt>" expression on the right, <tt>t__0</tt> is still an unresolved promise.Once the expression on the right has evaluated to a value, then the promise bound to the variable on the left is resolved to be this value. Once a promise is resolved, it becomes like any normal reference to the object it designates. This value is also the value of the <tt>defexpr</tt> as a whole. By the time <tt>def t__0 := ...</tt> finishes evaluating, the promise within the list becomes a direct reference to the list itself.

By using promises to reconstruct cycles, we safely avoid a host of hazards. Most other serialization systems [ref JOSS, XMLEncoder, BOSS, ...] are defined in systems without any kind of delayed references (promises, logic variables, futures), but which still allow user-defined unserialize-time behavior by the objects being unserialized. In any such system, when unserializing a cycle, user-defined behavior may interact with graph neighbors that are not yet fully initialized. Before an object is fully initialized, it may be easily confused. In a conventional system this is only a minor source of bugs. But in a graph of mutually suspicious objects this would be a [[Safe_Serialization_Under_Mutual_Suspicion/Abstract_and_Introduction#cyclebug|major opportunity]] for an adversary. By referring to an object only with promises until its fully initialized, we make such bugs safely fail-stop, enabling an adversary in the graph only to mount a denial-of-unserialization attack, which it can trivially do anyway, and which we make [[Safe_Serialization_Under_Mutual_Suspicion/Abstract_and_Introduction#denial| no effort or claim to prevent]].

Data-E is a true subset of '''''E''''', both syntactically and semantically. Since '''''E''''' is a secure object-capability language, the security issues surrounding evaluation of '''''E''''' programs are already well understood. By using a subset of '''''E''''' in this way, we get to leverage this understanding.

Safe Serialization Under Mutual Suspicion/Abstract and Introduction

2007-08-09T23:16:28Z

DavidHopwood: /* Serialization ''vs.'' Parallelism */

=Safe Serialization Under Mutual Suspicion=

by Mark S. Miller

=Abstract=

''Serialization'' and ''object-capabilities'' [ref [http://www.erights.org/elib/capability/ode/index.html Ode], [http://www.erights.org/talks/asian03/index.html Paradigm]] are two extensions of the object paradigm that seem to pull in opposing directions. Serialization sees an object graph as apparently open data, to convert to bits and back again. The object-capability paradigm sees an object graph as a set of dynamically evolving relationships between mutually suspicious encapsulated autonomous objects, voluntarily cooperating with one another each to pursue their own interests, within limits set by their vulnerability to and trust in each other [ref [http://www.erights.org/history/actors.html Hewitt]].

Serialization is often used to extend the reach of the object model across barriers of space, time, and version; stitching local ephemeral object systems together into a virtual graph of distributed persistent upgradable objects. With serialization we ''create the illusion of object continuity'' by adapting to these changes of context. There are many kinds of change and no single adequate adaptation strategy, so we seek general ''mechanisms'' supporting a diversity of coexisting adaptation ''policies''.

Likewise, serialization is often used to extend the object-capability model across such barriers. By enhancing the illusion to include capability security properties, we create a virtual persistent graph of mutually suspicious objects spread over mutually suspicious machines. Mechanism / policy separation is also needed here, though if too much authority is needed to express a policy choice, few objects will be able to, and little actual policy diversity will occur.

While there is a long history of ''distributed'' capability protocols that meet all these goals [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Donnelley76 Donnelley76], [http://www.erights.org/elib/capability/ode/ode-references.html#Sansom86 Sansom86]/88, Actors?, [http://www.erights.org/elib/capability/ode/ode-references.html#Tanenbaum86 Amoeba]?], prior ''persistent'' capability systems have always granted their persistence service godlike authority over the subsystem it is persisting, leading to single mandated one-size-fits-all solutions [ref KeyKOS, EROS, PJama, Grasshopper, Mach, Waterken?, Mozart?]. By contrast, this paper explains a simple serialization framework able to stretch the full object-capability illusion across all these barriers, able to express a wide range of policies, and requiring only reasonable authority. A diversity of policies may coexist within one system, each able to deal sensibly with mutual suspicion issues

* among objects being serialized,
* between these objects and a serializer,
* between a serializer and an unserializer,
* between an unserializer and its context,
* between an unserializer and the objects it reconstructs, and
* among the reconstructed objects.

For concreteness, we sketch how these ideas are applied in '''''E, '''''a pure object-capability-based secure programming language, thereby turning it into a securely distributed, persistent, and upgradable language as well.

=Introduction=

=Serialization ''vs.'' Security?=

In the pure object model of computation, an ''object'' is an encapsulated combination of state and behavior, where the ''state'' consists of references to other objects. The ''computational system'' is the dynamic graph of objects held together by these references, and rewired by messages sent along these references.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
A note on terminology: Since 1966 [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Dennis66 Dennis and Van Horn]] the ''object-capability'' model has been known simply as the ''capability ''model. Unfortunately, some other very different models are also called "capabilities", so we introduce the term ''object-capability'' [ref Wagner, [http://www.erights.org/talks/asian03/index.html Paradigm]] to escape from this legacy of confusion.
|}

The ''object-capability ''model of secure computation recognizes the security inherent in the object model. To get from objects to object-capabilities, we need merely prohibit certain primitive abilities which are not part of the pure object model anyway (like forged pointers, direct access to another's private state, mutable static variables) but which the object model by itself doesn't require us to prohibit [ref [http://www.erights.org/elib/capability/ode/index.html Ode]]. For example, C++, with its ability to cast ints into pointers, is still an object language, but is not an object-capability language.

Whereas the ''functionality'' of an object program depends only on the abilities provided by its underlying system, the ''security'' of an object-capability program depends on underlying inabilities as well. In a graph of mutually suspicious objects, one object's correctness depends not only on what the rules of the game say it can do, but also on what the rules say its potential adversaries cannot do. By imposing the object-capability prohibitions, we give the object model new power and meaning. Object-capability computation is no longer just the manipulation of information, but also of secure authority and identity. The object graph becomes a fabric for arranging patterns of ''safe cooperation'' among mutually suspicious objects.

Within the pure object model, because of encapsulation, objects cannot perceive or operate on the graph they are embedded in — they have access only to the behavior (in response to messages) of their immediate graph-neighbors — but not to their neighbors' state. This limited access is adequate for many purposes, but, it would seem, not all. ''Serialization'', explained below, is an example of a tool for use by objects within an object system for operating on the graph they are embedded in. This seems to require violating the encapsulation provided by the pure object model. Given the conventional rationale for encapsulation — that it aids only modularity — one could argue that it is simply prudent engineering to add new primitives for violating encapsulation when needed, as a tradeoff for other benefits. Many object systems provide serialization in precisely this way [ref JOSS, Mozart?].

==Threats and Opportunities==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
To encourage anthropomorphism, this paper often gives objects human names such as "Alice". Unless we explicitly state we're referring to humans, these always refer to objects.
|}

But adding such primitives destroys the security properties inherent in the pure object model. These are exactly the kinds of additions the object-capability model must prohibit. For example, they might allow Mallet, a client of encapsulated Alice, to serialize Alice and then reverse engineer the values of her private instance variables from her serialized form.

This paper shows how to provide the rough equivalent of conventional serialization for use in object-capability systems. This shift of context gives us both new problems to solve and new opportunities to exploit:

* '''Play by the rules'''. We show how to serialize and unserialize purely within object-capability rules, without introducing new primitives or requiring undue authority, thereby guaranteeing that we preserve base level (pre-illusion) object-capability security.
* '''Adapting authority and identity'''. Our serialization framework enables us to manipulate secure authority and identity in addition to information, enabling adaptation to changes involving these issues as well.
* '''Ensure accuracy of claimed authority'''. By object-capability rules, our serializer can only ask Mallet to voluntarily divulge that information he alleges about himself -- his ''portrayal''. If Mallet could convincingly portray himself as having authority he doesn't, the corresponding unserializer could be fooled into granting his reconstruction corresponding authority in its new context. Such a serialization system fails to enforce object-capability rules within the illusion it's attempting to create. We explain how to render this attack inexpressible.
* '''Selective transparency'''. Our serializer can only interact with Alice by sending messages to her public interface, just like any of Alice's other clients. Our serializer can only serialize Alice if she offers her portrayal in response -- if she doesn't, she's not serializable by this serializer. But if she does, what prevents Alice's client Mallet from asking these same question and obtaining this same portrayal, rendering Alice effectively unencapsulated? We show how a serializer and a set of objects may exploit a prior relationship of some additional trust, so that these object may divulge to this serializer portrayals of itself it wouldn't divulge to other clients or serializers.
* '''Invoke no object before its time'''. As with many objects, during Alice's construction / initialization, she may be in a fragile and easily confused state. Under normal conditions this is easily addressed -- don't give Mallet a reference to Alice until she is fully initialized. As programmers, we carefully design the order of object construction to get such issues right. However, during unserialization, object reconstruction does not have this luxury -- the order is often determined by the happenstance of the original graph's traversal. In the absence of cycles we could always reconstruct in bottom up order, but cycles are not absent. If Mallet's reconstruction (Mallet2) is given access to a not-yet-fully-initialized reconstruction of Alice (Alice2), Mallet2 may exploit Alice2's confusability. The defensive programming needed for Alice2 to be unconfusable is surprisingly hard -- we may not raise the price for security this high. Instead, we explain how to prevent this attack in those systems supporting ''delayed references'' (e.g., promises, logic variables, futures). For other systems, we know of no good solution other than to simulate delayed references. Unfortunately, our technique will occasionally cause valid cyclic serializations to fail to unserialize. Fortunately, the defensive programming needed to overcome this problem, though unpleasant, is straightforward. (** Need to explain that most of this problem is universal, though typically unadmitted.)

{| border="1" cellpadding="12" bgcolor="#ffffe8"
|

==Serialization ''vs.'' Parallelism==
Serialization raises concurrency problems — what if the graph changes while the serializer is traversing it. Although not the topic of this paper, within '''''E''''' we have easy answers: '''''E''''' is a system of [http://www.erights.org/elib/concurrency/index.html communicating event loops]. Each event loop is identified with a ''vat'' — essentially an address space full of objects together with a single thread of control for servicing the event loop. Objects only have synchronous access to other objects within their own vat. Inter-vat interactions only queue message deliveries to be serviced eventually in their own event. Therefore, during each event, each object runs with exclusive access to everything it has synchronous access to. We assume that each act of serializing and unserializing occurs during a single event, and therefore only traverses objects within the same vat. In the absence of malice, this provides adequate atomicity. (For systems like Java, built on shared memory multithreading with fine-grained locking, it's hard to imagine any correct general way to address this issue.) However, objects visited early in a traversal can react by causing side effects to shared parts of the graph that are revisited later in the same traversal. Given a normal degree of defensive programming, it's hard to imagine what vulnerability an attacker may find in this issue, but we would be remiss not to raise the possibility. Applications should also arrange to initiate serialization and unserialization at the beginning of an event, as is easily done. Between events there's no stack, so the heap must be consistent by itself. During an event, only the call stack + the heap can be assumed to be fully consistent, but our serialization tools are only able to examine state in the heap.
|}

==What We Have Not Done==

The present work does not address the following issues:

* '''The serializer is able to steal authorities'''. Using the architecture we present, the serializer obtains direct access to each object it traverses, which it can use, if it wishes, for other purposes. By the goals set out in this paper this represents inexcusably excess authority, as the serializer's proper duties include only the gathering of information from these objects [ref Karp, KeyKOS Sensory]. This is a pressing area for future work. Reducing the authority made available to the serializer reduces the risks it imposes on others, enabling them to more often chose to participate in a serialization in which they place limited trust.
* '''Performance'''. The speed achieved by high performance serialization systems [ref Parcels] may be incompatible with the architecture presented here. However, most serialization systems, such as JOSS, are unable to achieve such high performance either. While we know of no flaw in the present design that would preclude the performance achieved by these more common serialization systems, no such engineering has been done, and the question is mostly unexamined.
* '''Dirty bits & in-place stubifying'''. In order to use serialization to build an object-oriented virtual memory system [ref Loom] or object database, for each subgraph that would be separately saved and faulted back in we would need dirty bits to know if it changed. To unload a subgraph (purge it from memory), we would need to turn incoming references (references into the subgraph from outside it) into references to faulting stubs. While we believe that such techniques and those presented in this paper are compatible and complementary, this question is also mostly unexamined.
* '''Denial of service'''. Just as '''''E''''' makes no attempts or claims to resist denial of service attacks within a vat, so our serialization tools likewise do nothing to resist a denial of service attack from within a subgraph. If Mallet or his reconstruction simply throws an exception when traversed, this will abort the traversal preventing that act of serialization or unserialization. The '''''E''''' approach is to prevent breach attacks (inappropriate acquisition or exercise of authority) at the fine granularity of individual objects, as we do here, but to defend against resource exhaustion and denial of service attacks only at the coarser granularity of vats. Is there a corresponding coarser grain for serialization, at which such questions should be addressed? We don't know.
* '''Typed serialization'''. '''''E''''' itself is a dynamically typed language, in the tradition of Smalltalk, Actors, Lisp, or Python. The serialized form used in this paper, Data-E, is a subset of '''''E''''' and is equally untyped. Serialization systems for statically typed object languages like Java generally leverage the existence of static type declarations. One serialization system for Java (the XMLEncoder [ref]) outputs the equivalent of typed Java programs as its serialization format, providing an existence proof of a sort. Do the techniques presented here combine smoothly with static types? One known problem is the unserialization of cycles -- our technique of using delayed references will more often cause unserialization to fail, simply because a delayed references momentarily violates a declared type. A possible solution may be a type system designed to accommodate delayed references. (Note that XML Schema are inapplicable to typed serialization, since declared types constrain all references in the graph, whereas XML schema only constrains a tree.)
* '''Upgrade by refactoring'''. <nowiki>*** explain</nowiki>.
* '''Cryptographic Tunneling'''. <nowiki>*** explain</nowiki>.

=What is Serialization?=

<table width="30%" border="1" style="float:left;margin:5px;">
<tr><td bgcolor="#ffffe8" >
[[Image:lit-real.gif]]
</td></tr><tr><td bgcolor="#ffffe8">
==Figure 1: Literal Realism==
''Time proceeds from top to bottom, as an original live graph gets serialized into a depiction, which gets unserialized into a new live graph we take to be a reconstruction of the original. Although graphs may contain cycles, we generally show object references going from left to right across each diagram.'' 
</td></tr></table>

The Literal Realism diagram on the left represents the common elements of serialization and unserialization. A ''serializer'' (shown as the <tt>serialize</tt> function) takes as input a graph of live ''original'' objects, where this graph is a subgraph, delimited somehow, of an overall object graph. A serializer builds a depiction (shown in the picture frame) of this subgraph in a format it expects a compatible ''unserializer'' to understand. The depiction contains no objects; only bits depicting objects.

(Never mind that objects themselves are implemented using only bits. This view from the implementation isn't available to the objects so implemented -- and must not be -- so we may ignore it for present purposes. By contrast, the depiction consists only of bits, not just in fact, but also as perceived by the objects wielding our serialization tools.)

An ''unserializer'' takes this depiction as input, and uses it to build a new graph of live objects that can, in some sense, be said to be a ''reconstruction'' of the original. The reconstructed objects may or may not resemble the original in a number of different ways, explained below. The reconstructed graph is connected, somehow, into the overall graph at this new context, becoming a subgraph of it. When performed in service of, for example, distributing, persisting, or upgrading objects, the serializer, unserializer, original, and reconstructed objects generally cooperate to create the illusion that the reconstructed objects are a continuation -- across space, time, versions, etc. -- of the original objects.

==Literal Realism==

Within the overall notion of serialization, there are many variations. The following explanation of serialization in Mozart [[http://www.erights.org/data/serial/jhu-paper/acks-n-refs.html#Duchier98 Duchier98]] expresses well the extreme we call ''literal realism''.

{|
|
| Let x be the original data structure and y be a clone of x. Then the graphs reachable from x and y must be graph isomorphic with respect to their roots x and y. Moreover, the (mutable?) cells reachable from x must all be different from the [mutable?] cells reachable from y.
|}

(We are not claiming that actual support for customizing serialization in Mozart is limited in this manner, just that these are the limits implied by the cited spec.)

In this system, in terms of the diagram on the left, the subgraph to be depicted would be all objects reachable from the root object, A1. Non-root incoming references on the left, such as the incoming references to B1 and C1, would not be depicted. Serialization would not cut off any outgoing references on the right. There would be exactly one entry -- the root -- and no exits. A graph containing an unserializable object, such as an open TCP socket, simply cannot be serialized. Unserializing connects the reconstructed subgraph to its new context only at the root. Besides the root, the reconstructed subgraph is completely isolated. Holding no references to anything outside itself, it has no authority to affect anything outside itself. Literal realism of objects must also record and reload code, as a reconstruction must act just like the original.

Literal realism makes for a very clean spec. Unfortunately, it lacks the adaptability we need to create illusions of continuity across many kinds of changes. It also conflicts with the normal constraints of object-capability programming, in which an object's behavior in response to messages is the most that may be ascertained about it.

==Society of Impressionists==

In the object paradigm, objects have no direct access to one another's state. For example, when Alice asks Richard the Rectangle for his height (<tt>r.getHeight()</tt>), she cannot tell, and should not care, whether the answer is part of Richard's state or is computed. All she knows is that she's received the answer Richard wishes to divulge.

To build a serialization system for unprivileged use, it is best to build the serialization system without use of special privileges, thereby forcing it to play by the same rules imposed on all other objects. Within these constraints Literal Realism isn't possible. Literal Realism would require the depiction to reflect the actual state, whereas object constraints limit us to depicting a composition of what each object portrays its state to be. (*** note exception: Auditors) The subgraph the serializer is able to perceive is not the real subgraph of objects in memory, but rather a kind of story spun by the objects being traversed, each for its own purposes.

In this view, represented well by Java's Object Serialization Streams (JOSS) [ref JOSS], a serialization system is a framework for customizing, and for composing customizations of, the processes of depiction and reconstruction. We expect both serialization and unserialization to proceed with the intention that the reconstructed graph be somehow meaningfully similar to the original, but with differences as needed in order to satisfy other goals.

The unserializer builds whatever new objects it likes (subject to the limits of what objects it ''can'' build), but it normally chooses to build along the lines of its interpretation of the intentions of the serializer, as recorded in the depiction. The serializer paints whatever depiction it wishes (subject to the limits of what knowledge it can gain), but it normally chooses to depict along the lines of each original object's expressed intentions of how and whether it would like to be portrayed. Each object portrays that its alleged instance variables -- the set of references it would have the serializer represent as its state and further traverse from there -- is any set of references it likes (subject to the limits of what references it can produce).

(*** Find quote from "I Pencil")

''Modern civilization has given man undreamt of powers largely because, without understanding it, he has developed methods of utilizing more knowledge and resources than any one mind is aware of. ''--Friedrich Hayek [Hayek78]

When all these expressions of intent reflect the code written by one programmer all at once, then they are all aspects of one underlying intent and the architecture for composing intentions may not matter so much. When they are written by different programmers at different times in different companies, all with little knowledge of each other's specifics, then an architecture should be well adapted to the expected locality of knowledge -- demanding from each component the expression of intent which that component is in a better position to contribute. It should compose these together into a result which successfully utilizes more knowledge than any one component plausibly has. JOSS does quite well at this. The Data-E architecture presented below does similarly well for similar reasons -- partially as a result of thinking about and learning from JOSS.

As with many object frameworks translated into an object-capability world, a serialization framework is a system for ''composing knowledge by the rule-based mixing of intentions expressed by mutually suspicious interests''. When these all seek only literal accuracy (the default behavior), and when all the objects to be depicted are transparent (defined below), then the result must be according to Literal Realism. Given this, we can explain the effects of each kind of customization in terms of how it causes the result to deviate from Literal Realism, and of how multiple customizations interact.

==A Model of Serialization==

In the next chapter of the paper, [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E|Deconstructing Serialization Part 1: Introducing Data-E]] and [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation|Part 2: "Reversing" Evaluation]], sets the stage for the remainder of the paper by explaining one concrete serialization system, ''the Data-E System'', designed for expository use in this paper. The depiction format used by the Data-E System, ''Data-E'', is a small subset of the '''''E''''' language. Unserialization in the Data-E System is equivalent to the corresponding subset of '''''E''''' expression evaluation [ref Rees]. This choice enables us to immediately understand the meaning of a depiction by applying our understanding of expressions. This technique can easily be applied to many languages [ref XMLEncoder].

This initial presentation of Data-E will show it living within the constraints of capability discipline, but without yet showing how to live well within those constraints. The resulting loss of power compared to conventional serialization will be repaired in the chapters which follow.

Data-E will be presented in terms of its implementation in '''''E''''' for use in '''''E''''', although Data-E is in no sense specific to '''''E'''''.

Although the ideas in this chapter are mostly specific to Data-E, the ideas in the remainder of the paper are not. They have also been applied to JOSS, and we expect to apply them to Waterken Object Serialization (''WOS'') [ref WOS] as well. They should be applicable in any object-capability language [ref W7, Mozart, M] and starting from any sufficiently customizable serialization mechanism [ref JOSS, XMLEncoder?, WOS, BOSS?], given that it has the crucial property that ''portrayals are only in terms of other objects'', as explained later.

{| width="30%" border="1" align="right" bgcolor="#ffffe8"
|
[[Image:depiction.gif]]
|-
|
==Figure 2: The Three Faces==
''The diagram can be seen in terms of three rows cross three columns. The three rows, progressing in time, are again original, depiction, and reconstruction. The "faces" refers to the three columns, progressing by pointing topology: left (entries), middle (the subgraph interior), and right (exits). Our exposition proceeds instead from right to left. ''
|}

==The Three Faces of Serialization==

To serialize a subgraph of an overall graph, we need to delimit the bounds of the subgraph. Both serialization and unserialization raise issues that can naturally be classified according to the three columnar aspects of the diagram, which we explain in right-to-left order: the exits, the interior, and the entries.

===The Exit Points===

The right edge represents ''outgoing'' references -- references from objects within the subgraph to objects outside it (references leaving A1, B1, and C1). Of these, the ones depicted -- shown crossing the frame as convex jigsaw puzzle plugs -- are ''exits''(references leaving B and C), which the unserializer is expected to reconnect to something appropriate. (Following JOSS, we call outgoing references that aren't depicted, such as the one leaving A1, ''transient''.)

In an object-capability system, an object's only source of authority to affect the world outside of itself is according to the references it holds. By composition, the only authority held by the original subgraph as a whole to affect the world outside that subgraph is according to these outgoing references. To reconnect the exits to corresponding sources of authority is to determine what objects within the reconstructed subgraph can initially ''do''. To the extent that the new authorities resemble the original, we can say the objects holding these reconnected exit references are ''heir'' to these authorities from their original.

A reconstructed subgraph may find itself in a world quite different than the original's. Individual original objects held access to various resources of their hosting platform, and may expect to be reconnected to corresponding resources on their new host.

For example, let's say the original Joe held write access to <tt>/etc/motd</tt>. What criteria should come to play to determine what corresponding resource on the new platform to give to the reconstructed Joe? The chapter [[Manipulating_Authority_at_the Exits]] presents the ''Gordian Surgeon'' as the mechanism, and the legal concept of ''Comity Among Nations'' [ref??] as the metaphor for guiding policy choices, for the security issues of reconnecting exits.

===The Interior Subgraph===

The interior of the picture represents the subgraph itself (A,B,C and the references among them). To reconstruct the subgraph is to replicate information from the original, determining what the reconstructed objects initially ''know''. To the extent that information represented by a reconstructed object resembles information represented by the original, we may say the reconstructed object is a ''replica'' of the original.

The chapter [[Selective_Transparency_within_the_Subgraph]] enhances our idealized model of serialization to regain much of the lost conventional power while remaining within capability discipline. Within capability discipline, the serializer is only able to obtain knowledge of the original subgraph to the extent that the objects within that graph are willing to divulge that knowledge. This chapter shows a rights-amplification pattern by which a serializer may prearrange a relationship with set of objects, enabling these objects to divulge more to that serializer than they are willing to divulge to their normal clients or to other serializers.

===The Entry Points: Transcending Space and Time===

The left edge of the picture represents the ''incoming'' references -- references into the subgraph from objects outside the subgraph. Of these, the ones depicted -- shown crossing the frame as concave jigsaw puzzle sockets -- are ''entries'', those incoming connections the unserializer is expected to reconnect to something appropriate.

In any object system, the meaning of identity is in the behavior of references. To ''be'' a particular identity is to be designated by a particular reference, and thereby to be able to receive those messages (invocations) sent on that reference. In the object model, the philosophy of identity is simple: If I alone receive all communications directed to Joe, then I am Joe. In the object-capability model, the exclusive right to receive messages sent to Joe is the right to be Joe. When a reconstructed object acquires and employs this right from an original, we say it is a ''reincarnation'' of the original.

In a conventional single-process non-distributed, non-persistent object system (a space-time-local system), reincarnation is not really needed. Indeed, in a sense to be explained, it is not even possible. But we often stretch such systems across space and time by building distributed persistent object systems on top of such conventional systems. For example, the JVM itself only provides a space-time-local system, but RMI is built mostly in Java to stretch Java references across space. A number of persistence mechanisms (EJB, JDO) have been built mostly in Java to stretch Java objects and references across time. '''''E''''' is layered in this way, but in '''''E''''', the distributed persistent object system must still be a secure object-capability system. When building this layer of infrastructure, reincarnation is both possible and necessary.

The chapter [[Manipulating_Identity_at_the_Entries]] first explains the cryptographic implementation of distributed identity in '''''E''''''s remote messaging protocol, CapTP. We then show a simple use of cryptographic hashing that securely allows a new object to become the object designated by all outstanding references to the original. With a further elaboration on the hashing theme, we then enable unprivileged fault handlers to delay the act of unserializing and reincarnating from saved depictions until needed to handle incoming requests.

==Transcending Change: Upgrade==

''The art of upgrade is to preserve state amid change and to enable change amid state. ''--with apologies to Alfred North Whitehead [acks-n-refs.html#_ftn1 1]

An object is a bundle of state and behavior. Conventionally, an object's state may be mutable, but not its code. Like a dog that can't learn new tricks, an object conventionally has the same behavior for the duration of its lifetime. Once persistence extends this lifetime well beyond the product release cycles of the programs run by these objects, this inability can become an intolerable problem. To repair this, we must at least deal with the ''schema evolution ''problem -- to convert the concrete representation of the objects to a correct representation compatible with the new code that most closely preserves their original meaning and preserves their assumptions about each other. But schema evolution can be hard. To succeed at complex upgrades of complex systems at reasonable cost, a system should be designed to avoid schema evolution where possible, so that the programmers can afford to invest the attention needed to get it right in the remaining places where it's necessary [ref Arturo].

The chapter [[Persistence_and_Upgrade]] explains how these mechanism have been employed to create user-level persistence in '''''E''''', and how these mechanisms support persistence-with-upgrade by ''schema-evolution-avoidance'' in addition to schema evolution.

=Other Approaches=

The chapter [[Related Work]] surveys other work on serialization and security: Mozart. JOSS. WOS. XMLEncoder. ***What else? The origins of the Gordian Surgeon at Kalieda and NeXT. Abstraction in ToonTalk. Rights amplification for accessing representation: The KeyKOS / EROS Brand. PJama and XOF. Cardelli, Vijay. Rees' uneval. State Bundles

Safe Serialization Under Mutual Suspicion/Abstract and Introduction

2007-08-09T23:16:01Z

DavidHopwood: /* Serialization ''vs.'' Parallelism */

=Safe Serialization Under Mutual Suspicion=

by Mark S. Miller

=Abstract=

''Serialization'' and ''object-capabilities'' [ref [http://www.erights.org/elib/capability/ode/index.html Ode], [http://www.erights.org/talks/asian03/index.html Paradigm]] are two extensions of the object paradigm that seem to pull in opposing directions. Serialization sees an object graph as apparently open data, to convert to bits and back again. The object-capability paradigm sees an object graph as a set of dynamically evolving relationships between mutually suspicious encapsulated autonomous objects, voluntarily cooperating with one another each to pursue their own interests, within limits set by their vulnerability to and trust in each other [ref [http://www.erights.org/history/actors.html Hewitt]].

Serialization is often used to extend the reach of the object model across barriers of space, time, and version; stitching local ephemeral object systems together into a virtual graph of distributed persistent upgradable objects. With serialization we ''create the illusion of object continuity'' by adapting to these changes of context. There are many kinds of change and no single adequate adaptation strategy, so we seek general ''mechanisms'' supporting a diversity of coexisting adaptation ''policies''.

Likewise, serialization is often used to extend the object-capability model across such barriers. By enhancing the illusion to include capability security properties, we create a virtual persistent graph of mutually suspicious objects spread over mutually suspicious machines. Mechanism / policy separation is also needed here, though if too much authority is needed to express a policy choice, few objects will be able to, and little actual policy diversity will occur.

While there is a long history of ''distributed'' capability protocols that meet all these goals [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Donnelley76 Donnelley76], [http://www.erights.org/elib/capability/ode/ode-references.html#Sansom86 Sansom86]/88, Actors?, [http://www.erights.org/elib/capability/ode/ode-references.html#Tanenbaum86 Amoeba]?], prior ''persistent'' capability systems have always granted their persistence service godlike authority over the subsystem it is persisting, leading to single mandated one-size-fits-all solutions [ref KeyKOS, EROS, PJama, Grasshopper, Mach, Waterken?, Mozart?]. By contrast, this paper explains a simple serialization framework able to stretch the full object-capability illusion across all these barriers, able to express a wide range of policies, and requiring only reasonable authority. A diversity of policies may coexist within one system, each able to deal sensibly with mutual suspicion issues

* among objects being serialized,
* between these objects and a serializer,
* between a serializer and an unserializer,
* between an unserializer and its context,
* between an unserializer and the objects it reconstructs, and
* among the reconstructed objects.

For concreteness, we sketch how these ideas are applied in '''''E, '''''a pure object-capability-based secure programming language, thereby turning it into a securely distributed, persistent, and upgradable language as well.

=Introduction=

=Serialization ''vs.'' Security?=

In the pure object model of computation, an ''object'' is an encapsulated combination of state and behavior, where the ''state'' consists of references to other objects. The ''computational system'' is the dynamic graph of objects held together by these references, and rewired by messages sent along these references.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
A note on terminology: Since 1966 [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Dennis66 Dennis and Van Horn]] the ''object-capability'' model has been known simply as the ''capability ''model. Unfortunately, some other very different models are also called "capabilities", so we introduce the term ''object-capability'' [ref Wagner, [http://www.erights.org/talks/asian03/index.html Paradigm]] to escape from this legacy of confusion.
|}

The ''object-capability ''model of secure computation recognizes the security inherent in the object model. To get from objects to object-capabilities, we need merely prohibit certain primitive abilities which are not part of the pure object model anyway (like forged pointers, direct access to another's private state, mutable static variables) but which the object model by itself doesn't require us to prohibit [ref [http://www.erights.org/elib/capability/ode/index.html Ode]]. For example, C++, with its ability to cast ints into pointers, is still an object language, but is not an object-capability language.

Whereas the ''functionality'' of an object program depends only on the abilities provided by its underlying system, the ''security'' of an object-capability program depends on underlying inabilities as well. In a graph of mutually suspicious objects, one object's correctness depends not only on what the rules of the game say it can do, but also on what the rules say its potential adversaries cannot do. By imposing the object-capability prohibitions, we give the object model new power and meaning. Object-capability computation is no longer just the manipulation of information, but also of secure authority and identity. The object graph becomes a fabric for arranging patterns of ''safe cooperation'' among mutually suspicious objects.

Within the pure object model, because of encapsulation, objects cannot perceive or operate on the graph they are embedded in — they have access only to the behavior (in response to messages) of their immediate graph-neighbors — but not to their neighbors' state. This limited access is adequate for many purposes, but, it would seem, not all. ''Serialization'', explained below, is an example of a tool for use by objects within an object system for operating on the graph they are embedded in. This seems to require violating the encapsulation provided by the pure object model. Given the conventional rationale for encapsulation — that it aids only modularity — one could argue that it is simply prudent engineering to add new primitives for violating encapsulation when needed, as a tradeoff for other benefits. Many object systems provide serialization in precisely this way [ref JOSS, Mozart?].

==Threats and Opportunities==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
To encourage anthropomorphism, this paper often gives objects human names such as "Alice". Unless we explicitly state we're referring to humans, these always refer to objects.
|}

But adding such primitives destroys the security properties inherent in the pure object model. These are exactly the kinds of additions the object-capability model must prohibit. For example, they might allow Mallet, a client of encapsulated Alice, to serialize Alice and then reverse engineer the values of her private instance variables from her serialized form.

This paper shows how to provide the rough equivalent of conventional serialization for use in object-capability systems. This shift of context gives us both new problems to solve and new opportunities to exploit:

* '''Play by the rules'''. We show how to serialize and unserialize purely within object-capability rules, without introducing new primitives or requiring undue authority, thereby guaranteeing that we preserve base level (pre-illusion) object-capability security.
* '''Adapting authority and identity'''. Our serialization framework enables us to manipulate secure authority and identity in addition to information, enabling adaptation to changes involving these issues as well.
* '''Ensure accuracy of claimed authority'''. By object-capability rules, our serializer can only ask Mallet to voluntarily divulge that information he alleges about himself -- his ''portrayal''. If Mallet could convincingly portray himself as having authority he doesn't, the corresponding unserializer could be fooled into granting his reconstruction corresponding authority in its new context. Such a serialization system fails to enforce object-capability rules within the illusion it's attempting to create. We explain how to render this attack inexpressible.
* '''Selective transparency'''. Our serializer can only interact with Alice by sending messages to her public interface, just like any of Alice's other clients. Our serializer can only serialize Alice if she offers her portrayal in response -- if she doesn't, she's not serializable by this serializer. But if she does, what prevents Alice's client Mallet from asking these same question and obtaining this same portrayal, rendering Alice effectively unencapsulated? We show how a serializer and a set of objects may exploit a prior relationship of some additional trust, so that these object may divulge to this serializer portrayals of itself it wouldn't divulge to other clients or serializers.
* '''Invoke no object before its time'''. As with many objects, during Alice's construction / initialization, she may be in a fragile and easily confused state. Under normal conditions this is easily addressed -- don't give Mallet a reference to Alice until she is fully initialized. As programmers, we carefully design the order of object construction to get such issues right. However, during unserialization, object reconstruction does not have this luxury -- the order is often determined by the happenstance of the original graph's traversal. In the absence of cycles we could always reconstruct in bottom up order, but cycles are not absent. If Mallet's reconstruction (Mallet2) is given access to a not-yet-fully-initialized reconstruction of Alice (Alice2), Mallet2 may exploit Alice2's confusability. The defensive programming needed for Alice2 to be unconfusable is surprisingly hard -- we may not raise the price for security this high. Instead, we explain how to prevent this attack in those systems supporting ''delayed references'' (e.g., promises, logic variables, futures). For other systems, we know of no good solution other than to simulate delayed references. Unfortunately, our technique will occasionally cause valid cyclic serializations to fail to unserialize. Fortunately, the defensive programming needed to overcome this problem, though unpleasant, is straightforward. (** Need to explain that most of this problem is universal, though typically unadmitted.)

{| border="1" cellpadding="12" bgcolor="#ffffe8"
|

==Serialization ''vs.'' Parallelism==
Serialization raises concurrency problems -- what if the graph changes while the serializer is traversing it. Although not the topic of this paper, within '''''E''''' we have easy answers: '''''E''''' is a system of [http://www.erights.org/elib/concurrency/index.html communicating event loops]. Each event loop is identified with a ''vat'' — essentially an address space full of objects together with a single thread of control for servicing the event loop. Objects only have synchronous access to other objects within their own vat. Inter-vat interactions only queue message deliveries to be serviced eventually in their own event. Therefore, during each event, each object runs with exclusive access to everything it has synchronous access to. We assume that each act of serializing and unserializing occurs during a single event, and therefore only traverses objects within the same vat. In the absence of malice, this provides adequate atomicity. (For systems like Java, built on shared memory multithreading with fine-grained locking, it's hard to imagine any correct general way to address this issue.) However, objects visited early in a traversal can react by causing side effects to shared parts of the graph that are revisited later in the same traversal. Given a normal degree of defensive programming, it's hard to imagine what vulnerability an attacker may find in this issue, but we would be remiss not to raise the possibility. Applications should also arrange to initiate serialization and unserialization at the beginning of an event, as is easily done. Between events there's no stack, so the heap must be consistent by itself. During an event, only the call stack + the heap can be assumed to be fully consistent, but our serialization tools are only able to examine state in the heap.
|}

==What We Have Not Done==

The present work does not address the following issues:

* '''The serializer is able to steal authorities'''. Using the architecture we present, the serializer obtains direct access to each object it traverses, which it can use, if it wishes, for other purposes. By the goals set out in this paper this represents inexcusably excess authority, as the serializer's proper duties include only the gathering of information from these objects [ref Karp, KeyKOS Sensory]. This is a pressing area for future work. Reducing the authority made available to the serializer reduces the risks it imposes on others, enabling them to more often chose to participate in a serialization in which they place limited trust.
* '''Performance'''. The speed achieved by high performance serialization systems [ref Parcels] may be incompatible with the architecture presented here. However, most serialization systems, such as JOSS, are unable to achieve such high performance either. While we know of no flaw in the present design that would preclude the performance achieved by these more common serialization systems, no such engineering has been done, and the question is mostly unexamined.
* '''Dirty bits & in-place stubifying'''. In order to use serialization to build an object-oriented virtual memory system [ref Loom] or object database, for each subgraph that would be separately saved and faulted back in we would need dirty bits to know if it changed. To unload a subgraph (purge it from memory), we would need to turn incoming references (references into the subgraph from outside it) into references to faulting stubs. While we believe that such techniques and those presented in this paper are compatible and complementary, this question is also mostly unexamined.
* '''Denial of service'''. Just as '''''E''''' makes no attempts or claims to resist denial of service attacks within a vat, so our serialization tools likewise do nothing to resist a denial of service attack from within a subgraph. If Mallet or his reconstruction simply throws an exception when traversed, this will abort the traversal preventing that act of serialization or unserialization. The '''''E''''' approach is to prevent breach attacks (inappropriate acquisition or exercise of authority) at the fine granularity of individual objects, as we do here, but to defend against resource exhaustion and denial of service attacks only at the coarser granularity of vats. Is there a corresponding coarser grain for serialization, at which such questions should be addressed? We don't know.
* '''Typed serialization'''. '''''E''''' itself is a dynamically typed language, in the tradition of Smalltalk, Actors, Lisp, or Python. The serialized form used in this paper, Data-E, is a subset of '''''E''''' and is equally untyped. Serialization systems for statically typed object languages like Java generally leverage the existence of static type declarations. One serialization system for Java (the XMLEncoder [ref]) outputs the equivalent of typed Java programs as its serialization format, providing an existence proof of a sort. Do the techniques presented here combine smoothly with static types? One known problem is the unserialization of cycles -- our technique of using delayed references will more often cause unserialization to fail, simply because a delayed references momentarily violates a declared type. A possible solution may be a type system designed to accommodate delayed references. (Note that XML Schema are inapplicable to typed serialization, since declared types constrain all references in the graph, whereas XML schema only constrains a tree.)
* '''Upgrade by refactoring'''. <nowiki>*** explain</nowiki>.
* '''Cryptographic Tunneling'''. <nowiki>*** explain</nowiki>.

=What is Serialization?=

<table width="30%" border="1" style="float:left;margin:5px;">
<tr><td bgcolor="#ffffe8" >
[[Image:lit-real.gif]]
</td></tr><tr><td bgcolor="#ffffe8">
==Figure 1: Literal Realism==
''Time proceeds from top to bottom, as an original live graph gets serialized into a depiction, which gets unserialized into a new live graph we take to be a reconstruction of the original. Although graphs may contain cycles, we generally show object references going from left to right across each diagram.'' 
</td></tr></table>

The Literal Realism diagram on the left represents the common elements of serialization and unserialization. A ''serializer'' (shown as the <tt>serialize</tt> function) takes as input a graph of live ''original'' objects, where this graph is a subgraph, delimited somehow, of an overall object graph. A serializer builds a depiction (shown in the picture frame) of this subgraph in a format it expects a compatible ''unserializer'' to understand. The depiction contains no objects; only bits depicting objects.

(Never mind that objects themselves are implemented using only bits. This view from the implementation isn't available to the objects so implemented -- and must not be -- so we may ignore it for present purposes. By contrast, the depiction consists only of bits, not just in fact, but also as perceived by the objects wielding our serialization tools.)

An ''unserializer'' takes this depiction as input, and uses it to build a new graph of live objects that can, in some sense, be said to be a ''reconstruction'' of the original. The reconstructed objects may or may not resemble the original in a number of different ways, explained below. The reconstructed graph is connected, somehow, into the overall graph at this new context, becoming a subgraph of it. When performed in service of, for example, distributing, persisting, or upgrading objects, the serializer, unserializer, original, and reconstructed objects generally cooperate to create the illusion that the reconstructed objects are a continuation -- across space, time, versions, etc. -- of the original objects.

==Literal Realism==

Within the overall notion of serialization, there are many variations. The following explanation of serialization in Mozart [[http://www.erights.org/data/serial/jhu-paper/acks-n-refs.html#Duchier98 Duchier98]] expresses well the extreme we call ''literal realism''.

{|
|
| Let x be the original data structure and y be a clone of x. Then the graphs reachable from x and y must be graph isomorphic with respect to their roots x and y. Moreover, the (mutable?) cells reachable from x must all be different from the [mutable?] cells reachable from y.
|}

(We are not claiming that actual support for customizing serialization in Mozart is limited in this manner, just that these are the limits implied by the cited spec.)

In this system, in terms of the diagram on the left, the subgraph to be depicted would be all objects reachable from the root object, A1. Non-root incoming references on the left, such as the incoming references to B1 and C1, would not be depicted. Serialization would not cut off any outgoing references on the right. There would be exactly one entry -- the root -- and no exits. A graph containing an unserializable object, such as an open TCP socket, simply cannot be serialized. Unserializing connects the reconstructed subgraph to its new context only at the root. Besides the root, the reconstructed subgraph is completely isolated. Holding no references to anything outside itself, it has no authority to affect anything outside itself. Literal realism of objects must also record and reload code, as a reconstruction must act just like the original.

Literal realism makes for a very clean spec. Unfortunately, it lacks the adaptability we need to create illusions of continuity across many kinds of changes. It also conflicts with the normal constraints of object-capability programming, in which an object's behavior in response to messages is the most that may be ascertained about it.

==Society of Impressionists==

In the object paradigm, objects have no direct access to one another's state. For example, when Alice asks Richard the Rectangle for his height (<tt>r.getHeight()</tt>), she cannot tell, and should not care, whether the answer is part of Richard's state or is computed. All she knows is that she's received the answer Richard wishes to divulge.

To build a serialization system for unprivileged use, it is best to build the serialization system without use of special privileges, thereby forcing it to play by the same rules imposed on all other objects. Within these constraints Literal Realism isn't possible. Literal Realism would require the depiction to reflect the actual state, whereas object constraints limit us to depicting a composition of what each object portrays its state to be. (*** note exception: Auditors) The subgraph the serializer is able to perceive is not the real subgraph of objects in memory, but rather a kind of story spun by the objects being traversed, each for its own purposes.

In this view, represented well by Java's Object Serialization Streams (JOSS) [ref JOSS], a serialization system is a framework for customizing, and for composing customizations of, the processes of depiction and reconstruction. We expect both serialization and unserialization to proceed with the intention that the reconstructed graph be somehow meaningfully similar to the original, but with differences as needed in order to satisfy other goals.

The unserializer builds whatever new objects it likes (subject to the limits of what objects it ''can'' build), but it normally chooses to build along the lines of its interpretation of the intentions of the serializer, as recorded in the depiction. The serializer paints whatever depiction it wishes (subject to the limits of what knowledge it can gain), but it normally chooses to depict along the lines of each original object's expressed intentions of how and whether it would like to be portrayed. Each object portrays that its alleged instance variables -- the set of references it would have the serializer represent as its state and further traverse from there -- is any set of references it likes (subject to the limits of what references it can produce).

(*** Find quote from "I Pencil")

''Modern civilization has given man undreamt of powers largely because, without understanding it, he has developed methods of utilizing more knowledge and resources than any one mind is aware of. ''--Friedrich Hayek [Hayek78]

When all these expressions of intent reflect the code written by one programmer all at once, then they are all aspects of one underlying intent and the architecture for composing intentions may not matter so much. When they are written by different programmers at different times in different companies, all with little knowledge of each other's specifics, then an architecture should be well adapted to the expected locality of knowledge -- demanding from each component the expression of intent which that component is in a better position to contribute. It should compose these together into a result which successfully utilizes more knowledge than any one component plausibly has. JOSS does quite well at this. The Data-E architecture presented below does similarly well for similar reasons -- partially as a result of thinking about and learning from JOSS.

As with many object frameworks translated into an object-capability world, a serialization framework is a system for ''composing knowledge by the rule-based mixing of intentions expressed by mutually suspicious interests''. When these all seek only literal accuracy (the default behavior), and when all the objects to be depicted are transparent (defined below), then the result must be according to Literal Realism. Given this, we can explain the effects of each kind of customization in terms of how it causes the result to deviate from Literal Realism, and of how multiple customizations interact.

==A Model of Serialization==

In the next chapter of the paper, [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E|Deconstructing Serialization Part 1: Introducing Data-E]] and [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation|Part 2: "Reversing" Evaluation]], sets the stage for the remainder of the paper by explaining one concrete serialization system, ''the Data-E System'', designed for expository use in this paper. The depiction format used by the Data-E System, ''Data-E'', is a small subset of the '''''E''''' language. Unserialization in the Data-E System is equivalent to the corresponding subset of '''''E''''' expression evaluation [ref Rees]. This choice enables us to immediately understand the meaning of a depiction by applying our understanding of expressions. This technique can easily be applied to many languages [ref XMLEncoder].

This initial presentation of Data-E will show it living within the constraints of capability discipline, but without yet showing how to live well within those constraints. The resulting loss of power compared to conventional serialization will be repaired in the chapters which follow.

Data-E will be presented in terms of its implementation in '''''E''''' for use in '''''E''''', although Data-E is in no sense specific to '''''E'''''.

Although the ideas in this chapter are mostly specific to Data-E, the ideas in the remainder of the paper are not. They have also been applied to JOSS, and we expect to apply them to Waterken Object Serialization (''WOS'') [ref WOS] as well. They should be applicable in any object-capability language [ref W7, Mozart, M] and starting from any sufficiently customizable serialization mechanism [ref JOSS, XMLEncoder?, WOS, BOSS?], given that it has the crucial property that ''portrayals are only in terms of other objects'', as explained later.

{| width="30%" border="1" align="right" bgcolor="#ffffe8"
|
[[Image:depiction.gif]]
|-
|
==Figure 2: The Three Faces==
''The diagram can be seen in terms of three rows cross three columns. The three rows, progressing in time, are again original, depiction, and reconstruction. The "faces" refers to the three columns, progressing by pointing topology: left (entries), middle (the subgraph interior), and right (exits). Our exposition proceeds instead from right to left. ''
|}

==The Three Faces of Serialization==

To serialize a subgraph of an overall graph, we need to delimit the bounds of the subgraph. Both serialization and unserialization raise issues that can naturally be classified according to the three columnar aspects of the diagram, which we explain in right-to-left order: the exits, the interior, and the entries.

===The Exit Points===

The right edge represents ''outgoing'' references -- references from objects within the subgraph to objects outside it (references leaving A1, B1, and C1). Of these, the ones depicted -- shown crossing the frame as convex jigsaw puzzle plugs -- are ''exits''(references leaving B and C), which the unserializer is expected to reconnect to something appropriate. (Following JOSS, we call outgoing references that aren't depicted, such as the one leaving A1, ''transient''.)

In an object-capability system, an object's only source of authority to affect the world outside of itself is according to the references it holds. By composition, the only authority held by the original subgraph as a whole to affect the world outside that subgraph is according to these outgoing references. To reconnect the exits to corresponding sources of authority is to determine what objects within the reconstructed subgraph can initially ''do''. To the extent that the new authorities resemble the original, we can say the objects holding these reconnected exit references are ''heir'' to these authorities from their original.

A reconstructed subgraph may find itself in a world quite different than the original's. Individual original objects held access to various resources of their hosting platform, and may expect to be reconnected to corresponding resources on their new host.

For example, let's say the original Joe held write access to <tt>/etc/motd</tt>. What criteria should come to play to determine what corresponding resource on the new platform to give to the reconstructed Joe? The chapter [[Manipulating_Authority_at_the Exits]] presents the ''Gordian Surgeon'' as the mechanism, and the legal concept of ''Comity Among Nations'' [ref??] as the metaphor for guiding policy choices, for the security issues of reconnecting exits.

===The Interior Subgraph===

The interior of the picture represents the subgraph itself (A,B,C and the references among them). To reconstruct the subgraph is to replicate information from the original, determining what the reconstructed objects initially ''know''. To the extent that information represented by a reconstructed object resembles information represented by the original, we may say the reconstructed object is a ''replica'' of the original.

The chapter [[Selective_Transparency_within_the_Subgraph]] enhances our idealized model of serialization to regain much of the lost conventional power while remaining within capability discipline. Within capability discipline, the serializer is only able to obtain knowledge of the original subgraph to the extent that the objects within that graph are willing to divulge that knowledge. This chapter shows a rights-amplification pattern by which a serializer may prearrange a relationship with set of objects, enabling these objects to divulge more to that serializer than they are willing to divulge to their normal clients or to other serializers.

===The Entry Points: Transcending Space and Time===

The left edge of the picture represents the ''incoming'' references -- references into the subgraph from objects outside the subgraph. Of these, the ones depicted -- shown crossing the frame as concave jigsaw puzzle sockets -- are ''entries'', those incoming connections the unserializer is expected to reconnect to something appropriate.

In any object system, the meaning of identity is in the behavior of references. To ''be'' a particular identity is to be designated by a particular reference, and thereby to be able to receive those messages (invocations) sent on that reference. In the object model, the philosophy of identity is simple: If I alone receive all communications directed to Joe, then I am Joe. In the object-capability model, the exclusive right to receive messages sent to Joe is the right to be Joe. When a reconstructed object acquires and employs this right from an original, we say it is a ''reincarnation'' of the original.

In a conventional single-process non-distributed, non-persistent object system (a space-time-local system), reincarnation is not really needed. Indeed, in a sense to be explained, it is not even possible. But we often stretch such systems across space and time by building distributed persistent object systems on top of such conventional systems. For example, the JVM itself only provides a space-time-local system, but RMI is built mostly in Java to stretch Java references across space. A number of persistence mechanisms (EJB, JDO) have been built mostly in Java to stretch Java objects and references across time. '''''E''''' is layered in this way, but in '''''E''''', the distributed persistent object system must still be a secure object-capability system. When building this layer of infrastructure, reincarnation is both possible and necessary.

The chapter [[Manipulating_Identity_at_the_Entries]] first explains the cryptographic implementation of distributed identity in '''''E''''''s remote messaging protocol, CapTP. We then show a simple use of cryptographic hashing that securely allows a new object to become the object designated by all outstanding references to the original. With a further elaboration on the hashing theme, we then enable unprivileged fault handlers to delay the act of unserializing and reincarnating from saved depictions until needed to handle incoming requests.

==Transcending Change: Upgrade==

''The art of upgrade is to preserve state amid change and to enable change amid state. ''--with apologies to Alfred North Whitehead [acks-n-refs.html#_ftn1 1]

An object is a bundle of state and behavior. Conventionally, an object's state may be mutable, but not its code. Like a dog that can't learn new tricks, an object conventionally has the same behavior for the duration of its lifetime. Once persistence extends this lifetime well beyond the product release cycles of the programs run by these objects, this inability can become an intolerable problem. To repair this, we must at least deal with the ''schema evolution ''problem -- to convert the concrete representation of the objects to a correct representation compatible with the new code that most closely preserves their original meaning and preserves their assumptions about each other. But schema evolution can be hard. To succeed at complex upgrades of complex systems at reasonable cost, a system should be designed to avoid schema evolution where possible, so that the programmers can afford to invest the attention needed to get it right in the remaining places where it's necessary [ref Arturo].

The chapter [[Persistence_and_Upgrade]] explains how these mechanism have been employed to create user-level persistence in '''''E''''', and how these mechanisms support persistence-with-upgrade by ''schema-evolution-avoidance'' in addition to schema evolution.

=Other Approaches=

The chapter [[Related Work]] surveys other work on serialization and security: Mozart. JOSS. WOS. XMLEncoder. ***What else? The origins of the Gordian Surgeon at Kalieda and NeXT. Abstraction in ToonTalk. Rights amplification for accessing representation: The KeyKOS / EROS Brand. PJama and XOF. Cardelli, Vijay. Rees' uneval. State Bundles

Safe Serialization Under Mutual Suspicion/Abstract and Introduction

2007-08-09T23:15:03Z

DavidHopwood: /* Threats and Opportunities */

=Safe Serialization Under Mutual Suspicion=

by Mark S. Miller

=Abstract=

''Serialization'' and ''object-capabilities'' [ref [http://www.erights.org/elib/capability/ode/index.html Ode], [http://www.erights.org/talks/asian03/index.html Paradigm]] are two extensions of the object paradigm that seem to pull in opposing directions. Serialization sees an object graph as apparently open data, to convert to bits and back again. The object-capability paradigm sees an object graph as a set of dynamically evolving relationships between mutually suspicious encapsulated autonomous objects, voluntarily cooperating with one another each to pursue their own interests, within limits set by their vulnerability to and trust in each other [ref [http://www.erights.org/history/actors.html Hewitt]].

Serialization is often used to extend the reach of the object model across barriers of space, time, and version; stitching local ephemeral object systems together into a virtual graph of distributed persistent upgradable objects. With serialization we ''create the illusion of object continuity'' by adapting to these changes of context. There are many kinds of change and no single adequate adaptation strategy, so we seek general ''mechanisms'' supporting a diversity of coexisting adaptation ''policies''.

Likewise, serialization is often used to extend the object-capability model across such barriers. By enhancing the illusion to include capability security properties, we create a virtual persistent graph of mutually suspicious objects spread over mutually suspicious machines. Mechanism / policy separation is also needed here, though if too much authority is needed to express a policy choice, few objects will be able to, and little actual policy diversity will occur.

While there is a long history of ''distributed'' capability protocols that meet all these goals [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Donnelley76 Donnelley76], [http://www.erights.org/elib/capability/ode/ode-references.html#Sansom86 Sansom86]/88, Actors?, [http://www.erights.org/elib/capability/ode/ode-references.html#Tanenbaum86 Amoeba]?], prior ''persistent'' capability systems have always granted their persistence service godlike authority over the subsystem it is persisting, leading to single mandated one-size-fits-all solutions [ref KeyKOS, EROS, PJama, Grasshopper, Mach, Waterken?, Mozart?]. By contrast, this paper explains a simple serialization framework able to stretch the full object-capability illusion across all these barriers, able to express a wide range of policies, and requiring only reasonable authority. A diversity of policies may coexist within one system, each able to deal sensibly with mutual suspicion issues

* among objects being serialized,
* between these objects and a serializer,
* between a serializer and an unserializer,
* between an unserializer and its context,
* between an unserializer and the objects it reconstructs, and
* among the reconstructed objects.

For concreteness, we sketch how these ideas are applied in '''''E, '''''a pure object-capability-based secure programming language, thereby turning it into a securely distributed, persistent, and upgradable language as well.

=Introduction=

=Serialization ''vs.'' Security?=

In the pure object model of computation, an ''object'' is an encapsulated combination of state and behavior, where the ''state'' consists of references to other objects. The ''computational system'' is the dynamic graph of objects held together by these references, and rewired by messages sent along these references.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
A note on terminology: Since 1966 [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Dennis66 Dennis and Van Horn]] the ''object-capability'' model has been known simply as the ''capability ''model. Unfortunately, some other very different models are also called "capabilities", so we introduce the term ''object-capability'' [ref Wagner, [http://www.erights.org/talks/asian03/index.html Paradigm]] to escape from this legacy of confusion.
|}

The ''object-capability ''model of secure computation recognizes the security inherent in the object model. To get from objects to object-capabilities, we need merely prohibit certain primitive abilities which are not part of the pure object model anyway (like forged pointers, direct access to another's private state, mutable static variables) but which the object model by itself doesn't require us to prohibit [ref [http://www.erights.org/elib/capability/ode/index.html Ode]]. For example, C++, with its ability to cast ints into pointers, is still an object language, but is not an object-capability language.

Whereas the ''functionality'' of an object program depends only on the abilities provided by its underlying system, the ''security'' of an object-capability program depends on underlying inabilities as well. In a graph of mutually suspicious objects, one object's correctness depends not only on what the rules of the game say it can do, but also on what the rules say its potential adversaries cannot do. By imposing the object-capability prohibitions, we give the object model new power and meaning. Object-capability computation is no longer just the manipulation of information, but also of secure authority and identity. The object graph becomes a fabric for arranging patterns of ''safe cooperation'' among mutually suspicious objects.

Within the pure object model, because of encapsulation, objects cannot perceive or operate on the graph they are embedded in — they have access only to the behavior (in response to messages) of their immediate graph-neighbors — but not to their neighbors' state. This limited access is adequate for many purposes, but, it would seem, not all. ''Serialization'', explained below, is an example of a tool for use by objects within an object system for operating on the graph they are embedded in. This seems to require violating the encapsulation provided by the pure object model. Given the conventional rationale for encapsulation — that it aids only modularity — one could argue that it is simply prudent engineering to add new primitives for violating encapsulation when needed, as a tradeoff for other benefits. Many object systems provide serialization in precisely this way [ref JOSS, Mozart?].

==Threats and Opportunities==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
To encourage anthropomorphism, this paper often gives objects human names such as "Alice". Unless we explicitly state we're referring to humans, these always refer to objects.
|}

But adding such primitives destroys the security properties inherent in the pure object model. These are exactly the kinds of additions the object-capability model must prohibit. For example, they might allow Mallet, a client of encapsulated Alice, to serialize Alice and then reverse engineer the values of her private instance variables from her serialized form.

This paper shows how to provide the rough equivalent of conventional serialization for use in object-capability systems. This shift of context gives us both new problems to solve and new opportunities to exploit:

* '''Play by the rules'''. We show how to serialize and unserialize purely within object-capability rules, without introducing new primitives or requiring undue authority, thereby guaranteeing that we preserve base level (pre-illusion) object-capability security.
* '''Adapting authority and identity'''. Our serialization framework enables us to manipulate secure authority and identity in addition to information, enabling adaptation to changes involving these issues as well.
* '''Ensure accuracy of claimed authority'''. By object-capability rules, our serializer can only ask Mallet to voluntarily divulge that information he alleges about himself -- his ''portrayal''. If Mallet could convincingly portray himself as having authority he doesn't, the corresponding unserializer could be fooled into granting his reconstruction corresponding authority in its new context. Such a serialization system fails to enforce object-capability rules within the illusion it's attempting to create. We explain how to render this attack inexpressible.
* '''Selective transparency'''. Our serializer can only interact with Alice by sending messages to her public interface, just like any of Alice's other clients. Our serializer can only serialize Alice if she offers her portrayal in response -- if she doesn't, she's not serializable by this serializer. But if she does, what prevents Alice's client Mallet from asking these same question and obtaining this same portrayal, rendering Alice effectively unencapsulated? We show how a serializer and a set of objects may exploit a prior relationship of some additional trust, so that these object may divulge to this serializer portrayals of itself it wouldn't divulge to other clients or serializers.
* '''Invoke no object before its time'''. As with many objects, during Alice's construction / initialization, she may be in a fragile and easily confused state. Under normal conditions this is easily addressed -- don't give Mallet a reference to Alice until she is fully initialized. As programmers, we carefully design the order of object construction to get such issues right. However, during unserialization, object reconstruction does not have this luxury -- the order is often determined by the happenstance of the original graph's traversal. In the absence of cycles we could always reconstruct in bottom up order, but cycles are not absent. If Mallet's reconstruction (Mallet2) is given access to a not-yet-fully-initialized reconstruction of Alice (Alice2), Mallet2 may exploit Alice2's confusability. The defensive programming needed for Alice2 to be unconfusable is surprisingly hard -- we may not raise the price for security this high. Instead, we explain how to prevent this attack in those systems supporting ''delayed references'' (e.g., promises, logic variables, futures). For other systems, we know of no good solution other than to simulate delayed references. Unfortunately, our technique will occasionally cause valid cyclic serializations to fail to unserialize. Fortunately, the defensive programming needed to overcome this problem, though unpleasant, is straightforward. (** Need to explain that most of this problem is universal, though typically unadmitted.)

{| border="1" cellpadding="12" bgcolor="#ffffe8"
|

==Serialization ''vs.'' Parallelism==
Serialization raises concurrency problems -- what if the graph changes while the serializer is traversing it. Although not the topic of this paper, within '''''E''''' we have easy answers: '''''E''''' is a system of [http://www.erights.org/elib/concurrency/index.html communicating event loops]. Each event loop is identified with a ''vat'' -- essentially an address space full of objects together with a single thread of control for servicing the event loop. Objects only have synchronous access to other objects within their own vat. Inter-vat interactions only queue message deliveries to be serviced eventually in their own event. Therefore, during each event, each object runs with exclusive access to everything it has synchronous access to. We assume that each act of serializing and unserializing occurs during a single event, and therefore only traverses objects within the same vat. In the absence of malice, this provides adequate atomicity. (For systems like Java, built on shared memory multithreading with fine-grained locking, it's hard to imagine any correct general way to address this issue.)However, objects visited early in a traversal can react by causing side effects to shared parts of the graph that are revisited later in the same traversal. Given a normal degree of defensive programming, it's hard to imagine what vulnerability an attacker may find in this issue, but we would be remiss not to raise the possibility.Applications should also arrange to initiate serialization and unserialization at the beginning of an event, as is easily done. Between events there's no stack, so the heap must be consistent by itself. During an event, only the call stack + the heap can be assumed to be fully consistent, but our serialization tools are only able to examine state in the heap.
|}

==What We Have Not Done==

The present work does not address the following issues:

* '''The serializer is able to steal authorities'''. Using the architecture we present, the serializer obtains direct access to each object it traverses, which it can use, if it wishes, for other purposes. By the goals set out in this paper this represents inexcusably excess authority, as the serializer's proper duties include only the gathering of information from these objects [ref Karp, KeyKOS Sensory]. This is a pressing area for future work. Reducing the authority made available to the serializer reduces the risks it imposes on others, enabling them to more often chose to participate in a serialization in which they place limited trust.
* '''Performance'''. The speed achieved by high performance serialization systems [ref Parcels] may be incompatible with the architecture presented here. However, most serialization systems, such as JOSS, are unable to achieve such high performance either. While we know of no flaw in the present design that would preclude the performance achieved by these more common serialization systems, no such engineering has been done, and the question is mostly unexamined.
* '''Dirty bits & in-place stubifying'''. In order to use serialization to build an object-oriented virtual memory system [ref Loom] or object database, for each subgraph that would be separately saved and faulted back in we would need dirty bits to know if it changed. To unload a subgraph (purge it from memory), we would need to turn incoming references (references into the subgraph from outside it) into references to faulting stubs. While we believe that such techniques and those presented in this paper are compatible and complementary, this question is also mostly unexamined.
* '''Denial of service'''. Just as '''''E''''' makes no attempts or claims to resist denial of service attacks within a vat, so our serialization tools likewise do nothing to resist a denial of service attack from within a subgraph. If Mallet or his reconstruction simply throws an exception when traversed, this will abort the traversal preventing that act of serialization or unserialization. The '''''E''''' approach is to prevent breach attacks (inappropriate acquisition or exercise of authority) at the fine granularity of individual objects, as we do here, but to defend against resource exhaustion and denial of service attacks only at the coarser granularity of vats. Is there a corresponding coarser grain for serialization, at which such questions should be addressed? We don't know.
* '''Typed serialization'''. '''''E''''' itself is a dynamically typed language, in the tradition of Smalltalk, Actors, Lisp, or Python. The serialized form used in this paper, Data-E, is a subset of '''''E''''' and is equally untyped. Serialization systems for statically typed object languages like Java generally leverage the existence of static type declarations. One serialization system for Java (the XMLEncoder [ref]) outputs the equivalent of typed Java programs as its serialization format, providing an existence proof of a sort. Do the techniques presented here combine smoothly with static types? One known problem is the unserialization of cycles -- our technique of using delayed references will more often cause unserialization to fail, simply because a delayed references momentarily violates a declared type. A possible solution may be a type system designed to accommodate delayed references. (Note that XML Schema are inapplicable to typed serialization, since declared types constrain all references in the graph, whereas XML schema only constrains a tree.)
* '''Upgrade by refactoring'''. <nowiki>*** explain</nowiki>.
* '''Cryptographic Tunneling'''. <nowiki>*** explain</nowiki>.

=What is Serialization?=

<table width="30%" border="1" style="float:left;margin:5px;">
<tr><td bgcolor="#ffffe8" >
[[Image:lit-real.gif]]
</td></tr><tr><td bgcolor="#ffffe8">
==Figure 1: Literal Realism==
''Time proceeds from top to bottom, as an original live graph gets serialized into a depiction, which gets unserialized into a new live graph we take to be a reconstruction of the original. Although graphs may contain cycles, we generally show object references going from left to right across each diagram.'' 
</td></tr></table>

The Literal Realism diagram on the left represents the common elements of serialization and unserialization. A ''serializer'' (shown as the <tt>serialize</tt> function) takes as input a graph of live ''original'' objects, where this graph is a subgraph, delimited somehow, of an overall object graph. A serializer builds a depiction (shown in the picture frame) of this subgraph in a format it expects a compatible ''unserializer'' to understand. The depiction contains no objects; only bits depicting objects.

(Never mind that objects themselves are implemented using only bits. This view from the implementation isn't available to the objects so implemented -- and must not be -- so we may ignore it for present purposes. By contrast, the depiction consists only of bits, not just in fact, but also as perceived by the objects wielding our serialization tools.)

An ''unserializer'' takes this depiction as input, and uses it to build a new graph of live objects that can, in some sense, be said to be a ''reconstruction'' of the original. The reconstructed objects may or may not resemble the original in a number of different ways, explained below. The reconstructed graph is connected, somehow, into the overall graph at this new context, becoming a subgraph of it. When performed in service of, for example, distributing, persisting, or upgrading objects, the serializer, unserializer, original, and reconstructed objects generally cooperate to create the illusion that the reconstructed objects are a continuation -- across space, time, versions, etc. -- of the original objects.

==Literal Realism==

Within the overall notion of serialization, there are many variations. The following explanation of serialization in Mozart [[http://www.erights.org/data/serial/jhu-paper/acks-n-refs.html#Duchier98 Duchier98]] expresses well the extreme we call ''literal realism''.

{|
|
| Let x be the original data structure and y be a clone of x. Then the graphs reachable from x and y must be graph isomorphic with respect to their roots x and y. Moreover, the (mutable?) cells reachable from x must all be different from the [mutable?] cells reachable from y.
|}

(We are not claiming that actual support for customizing serialization in Mozart is limited in this manner, just that these are the limits implied by the cited spec.)

In this system, in terms of the diagram on the left, the subgraph to be depicted would be all objects reachable from the root object, A1. Non-root incoming references on the left, such as the incoming references to B1 and C1, would not be depicted. Serialization would not cut off any outgoing references on the right. There would be exactly one entry -- the root -- and no exits. A graph containing an unserializable object, such as an open TCP socket, simply cannot be serialized. Unserializing connects the reconstructed subgraph to its new context only at the root. Besides the root, the reconstructed subgraph is completely isolated. Holding no references to anything outside itself, it has no authority to affect anything outside itself. Literal realism of objects must also record and reload code, as a reconstruction must act just like the original.

Literal realism makes for a very clean spec. Unfortunately, it lacks the adaptability we need to create illusions of continuity across many kinds of changes. It also conflicts with the normal constraints of object-capability programming, in which an object's behavior in response to messages is the most that may be ascertained about it.

==Society of Impressionists==

In the object paradigm, objects have no direct access to one another's state. For example, when Alice asks Richard the Rectangle for his height (<tt>r.getHeight()</tt>), she cannot tell, and should not care, whether the answer is part of Richard's state or is computed. All she knows is that she's received the answer Richard wishes to divulge.

To build a serialization system for unprivileged use, it is best to build the serialization system without use of special privileges, thereby forcing it to play by the same rules imposed on all other objects. Within these constraints Literal Realism isn't possible. Literal Realism would require the depiction to reflect the actual state, whereas object constraints limit us to depicting a composition of what each object portrays its state to be. (*** note exception: Auditors) The subgraph the serializer is able to perceive is not the real subgraph of objects in memory, but rather a kind of story spun by the objects being traversed, each for its own purposes.

In this view, represented well by Java's Object Serialization Streams (JOSS) [ref JOSS], a serialization system is a framework for customizing, and for composing customizations of, the processes of depiction and reconstruction. We expect both serialization and unserialization to proceed with the intention that the reconstructed graph be somehow meaningfully similar to the original, but with differences as needed in order to satisfy other goals.

The unserializer builds whatever new objects it likes (subject to the limits of what objects it ''can'' build), but it normally chooses to build along the lines of its interpretation of the intentions of the serializer, as recorded in the depiction. The serializer paints whatever depiction it wishes (subject to the limits of what knowledge it can gain), but it normally chooses to depict along the lines of each original object's expressed intentions of how and whether it would like to be portrayed. Each object portrays that its alleged instance variables -- the set of references it would have the serializer represent as its state and further traverse from there -- is any set of references it likes (subject to the limits of what references it can produce).

(*** Find quote from "I Pencil")

''Modern civilization has given man undreamt of powers largely because, without understanding it, he has developed methods of utilizing more knowledge and resources than any one mind is aware of. ''--Friedrich Hayek [Hayek78]

When all these expressions of intent reflect the code written by one programmer all at once, then they are all aspects of one underlying intent and the architecture for composing intentions may not matter so much. When they are written by different programmers at different times in different companies, all with little knowledge of each other's specifics, then an architecture should be well adapted to the expected locality of knowledge -- demanding from each component the expression of intent which that component is in a better position to contribute. It should compose these together into a result which successfully utilizes more knowledge than any one component plausibly has. JOSS does quite well at this. The Data-E architecture presented below does similarly well for similar reasons -- partially as a result of thinking about and learning from JOSS.

As with many object frameworks translated into an object-capability world, a serialization framework is a system for ''composing knowledge by the rule-based mixing of intentions expressed by mutually suspicious interests''. When these all seek only literal accuracy (the default behavior), and when all the objects to be depicted are transparent (defined below), then the result must be according to Literal Realism. Given this, we can explain the effects of each kind of customization in terms of how it causes the result to deviate from Literal Realism, and of how multiple customizations interact.

==A Model of Serialization==

In the next chapter of the paper, [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E|Deconstructing Serialization Part 1: Introducing Data-E]] and [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation|Part 2: "Reversing" Evaluation]], sets the stage for the remainder of the paper by explaining one concrete serialization system, ''the Data-E System'', designed for expository use in this paper. The depiction format used by the Data-E System, ''Data-E'', is a small subset of the '''''E''''' language. Unserialization in the Data-E System is equivalent to the corresponding subset of '''''E''''' expression evaluation [ref Rees]. This choice enables us to immediately understand the meaning of a depiction by applying our understanding of expressions. This technique can easily be applied to many languages [ref XMLEncoder].

This initial presentation of Data-E will show it living within the constraints of capability discipline, but without yet showing how to live well within those constraints. The resulting loss of power compared to conventional serialization will be repaired in the chapters which follow.

Data-E will be presented in terms of its implementation in '''''E''''' for use in '''''E''''', although Data-E is in no sense specific to '''''E'''''.

Although the ideas in this chapter are mostly specific to Data-E, the ideas in the remainder of the paper are not. They have also been applied to JOSS, and we expect to apply them to Waterken Object Serialization (''WOS'') [ref WOS] as well. They should be applicable in any object-capability language [ref W7, Mozart, M] and starting from any sufficiently customizable serialization mechanism [ref JOSS, XMLEncoder?, WOS, BOSS?], given that it has the crucial property that ''portrayals are only in terms of other objects'', as explained later.

{| width="30%" border="1" align="right" bgcolor="#ffffe8"
|
[[Image:depiction.gif]]
|-
|
==Figure 2: The Three Faces==
''The diagram can be seen in terms of three rows cross three columns. The three rows, progressing in time, are again original, depiction, and reconstruction. The "faces" refers to the three columns, progressing by pointing topology: left (entries), middle (the subgraph interior), and right (exits). Our exposition proceeds instead from right to left. ''
|}

==The Three Faces of Serialization==

To serialize a subgraph of an overall graph, we need to delimit the bounds of the subgraph. Both serialization and unserialization raise issues that can naturally be classified according to the three columnar aspects of the diagram, which we explain in right-to-left order: the exits, the interior, and the entries.

===The Exit Points===

The right edge represents ''outgoing'' references -- references from objects within the subgraph to objects outside it (references leaving A1, B1, and C1). Of these, the ones depicted -- shown crossing the frame as convex jigsaw puzzle plugs -- are ''exits''(references leaving B and C), which the unserializer is expected to reconnect to something appropriate. (Following JOSS, we call outgoing references that aren't depicted, such as the one leaving A1, ''transient''.)

In an object-capability system, an object's only source of authority to affect the world outside of itself is according to the references it holds. By composition, the only authority held by the original subgraph as a whole to affect the world outside that subgraph is according to these outgoing references. To reconnect the exits to corresponding sources of authority is to determine what objects within the reconstructed subgraph can initially ''do''. To the extent that the new authorities resemble the original, we can say the objects holding these reconnected exit references are ''heir'' to these authorities from their original.

A reconstructed subgraph may find itself in a world quite different than the original's. Individual original objects held access to various resources of their hosting platform, and may expect to be reconnected to corresponding resources on their new host.

For example, let's say the original Joe held write access to <tt>/etc/motd</tt>. What criteria should come to play to determine what corresponding resource on the new platform to give to the reconstructed Joe? The chapter [[Manipulating_Authority_at_the Exits]] presents the ''Gordian Surgeon'' as the mechanism, and the legal concept of ''Comity Among Nations'' [ref??] as the metaphor for guiding policy choices, for the security issues of reconnecting exits.

===The Interior Subgraph===

The interior of the picture represents the subgraph itself (A,B,C and the references among them). To reconstruct the subgraph is to replicate information from the original, determining what the reconstructed objects initially ''know''. To the extent that information represented by a reconstructed object resembles information represented by the original, we may say the reconstructed object is a ''replica'' of the original.

The chapter [[Selective_Transparency_within_the_Subgraph]] enhances our idealized model of serialization to regain much of the lost conventional power while remaining within capability discipline. Within capability discipline, the serializer is only able to obtain knowledge of the original subgraph to the extent that the objects within that graph are willing to divulge that knowledge. This chapter shows a rights-amplification pattern by which a serializer may prearrange a relationship with set of objects, enabling these objects to divulge more to that serializer than they are willing to divulge to their normal clients or to other serializers.

===The Entry Points: Transcending Space and Time===

The left edge of the picture represents the ''incoming'' references -- references into the subgraph from objects outside the subgraph. Of these, the ones depicted -- shown crossing the frame as concave jigsaw puzzle sockets -- are ''entries'', those incoming connections the unserializer is expected to reconnect to something appropriate.

In any object system, the meaning of identity is in the behavior of references. To ''be'' a particular identity is to be designated by a particular reference, and thereby to be able to receive those messages (invocations) sent on that reference. In the object model, the philosophy of identity is simple: If I alone receive all communications directed to Joe, then I am Joe. In the object-capability model, the exclusive right to receive messages sent to Joe is the right to be Joe. When a reconstructed object acquires and employs this right from an original, we say it is a ''reincarnation'' of the original.

In a conventional single-process non-distributed, non-persistent object system (a space-time-local system), reincarnation is not really needed. Indeed, in a sense to be explained, it is not even possible. But we often stretch such systems across space and time by building distributed persistent object systems on top of such conventional systems. For example, the JVM itself only provides a space-time-local system, but RMI is built mostly in Java to stretch Java references across space. A number of persistence mechanisms (EJB, JDO) have been built mostly in Java to stretch Java objects and references across time. '''''E''''' is layered in this way, but in '''''E''''', the distributed persistent object system must still be a secure object-capability system. When building this layer of infrastructure, reincarnation is both possible and necessary.

The chapter [[Manipulating_Identity_at_the_Entries]] first explains the cryptographic implementation of distributed identity in '''''E''''''s remote messaging protocol, CapTP. We then show a simple use of cryptographic hashing that securely allows a new object to become the object designated by all outstanding references to the original. With a further elaboration on the hashing theme, we then enable unprivileged fault handlers to delay the act of unserializing and reincarnating from saved depictions until needed to handle incoming requests.

==Transcending Change: Upgrade==

''The art of upgrade is to preserve state amid change and to enable change amid state. ''--with apologies to Alfred North Whitehead [acks-n-refs.html#_ftn1 1]

An object is a bundle of state and behavior. Conventionally, an object's state may be mutable, but not its code. Like a dog that can't learn new tricks, an object conventionally has the same behavior for the duration of its lifetime. Once persistence extends this lifetime well beyond the product release cycles of the programs run by these objects, this inability can become an intolerable problem. To repair this, we must at least deal with the ''schema evolution ''problem -- to convert the concrete representation of the objects to a correct representation compatible with the new code that most closely preserves their original meaning and preserves their assumptions about each other. But schema evolution can be hard. To succeed at complex upgrades of complex systems at reasonable cost, a system should be designed to avoid schema evolution where possible, so that the programmers can afford to invest the attention needed to get it right in the remaining places where it's necessary [ref Arturo].

The chapter [[Persistence_and_Upgrade]] explains how these mechanism have been employed to create user-level persistence in '''''E''''', and how these mechanisms support persistence-with-upgrade by ''schema-evolution-avoidance'' in addition to schema evolution.

=Other Approaches=

The chapter [[Related Work]] surveys other work on serialization and security: Mozart. JOSS. WOS. XMLEncoder. ***What else? The origins of the Gordian Surgeon at Kalieda and NeXT. Abstraction in ToonTalk. Rights amplification for accessing representation: The KeyKOS / EROS Brand. PJama and XOF. Cardelli, Vijay. Rees' uneval. State Bundles

Safe Serialization Under Mutual Suspicion/Abstract and Introduction

2007-08-09T23:12:44Z

DavidHopwood: /* Serialization ''vs.'' Security? */

=Safe Serialization Under Mutual Suspicion=

by Mark S. Miller

=Abstract=

''Serialization'' and ''object-capabilities'' [ref [http://www.erights.org/elib/capability/ode/index.html Ode], [http://www.erights.org/talks/asian03/index.html Paradigm]] are two extensions of the object paradigm that seem to pull in opposing directions. Serialization sees an object graph as apparently open data, to convert to bits and back again. The object-capability paradigm sees an object graph as a set of dynamically evolving relationships between mutually suspicious encapsulated autonomous objects, voluntarily cooperating with one another each to pursue their own interests, within limits set by their vulnerability to and trust in each other [ref [http://www.erights.org/history/actors.html Hewitt]].

Serialization is often used to extend the reach of the object model across barriers of space, time, and version; stitching local ephemeral object systems together into a virtual graph of distributed persistent upgradable objects. With serialization we ''create the illusion of object continuity'' by adapting to these changes of context. There are many kinds of change and no single adequate adaptation strategy, so we seek general ''mechanisms'' supporting a diversity of coexisting adaptation ''policies''.

Likewise, serialization is often used to extend the object-capability model across such barriers. By enhancing the illusion to include capability security properties, we create a virtual persistent graph of mutually suspicious objects spread over mutually suspicious machines. Mechanism / policy separation is also needed here, though if too much authority is needed to express a policy choice, few objects will be able to, and little actual policy diversity will occur.

While there is a long history of ''distributed'' capability protocols that meet all these goals [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Donnelley76 Donnelley76], [http://www.erights.org/elib/capability/ode/ode-references.html#Sansom86 Sansom86]/88, Actors?, [http://www.erights.org/elib/capability/ode/ode-references.html#Tanenbaum86 Amoeba]?], prior ''persistent'' capability systems have always granted their persistence service godlike authority over the subsystem it is persisting, leading to single mandated one-size-fits-all solutions [ref KeyKOS, EROS, PJama, Grasshopper, Mach, Waterken?, Mozart?]. By contrast, this paper explains a simple serialization framework able to stretch the full object-capability illusion across all these barriers, able to express a wide range of policies, and requiring only reasonable authority. A diversity of policies may coexist within one system, each able to deal sensibly with mutual suspicion issues

* among objects being serialized,
* between these objects and a serializer,
* between a serializer and an unserializer,
* between an unserializer and its context,
* between an unserializer and the objects it reconstructs, and
* among the reconstructed objects.

For concreteness, we sketch how these ideas are applied in '''''E, '''''a pure object-capability-based secure programming language, thereby turning it into a securely distributed, persistent, and upgradable language as well.

=Introduction=

=Serialization ''vs.'' Security?=

In the pure object model of computation, an ''object'' is an encapsulated combination of state and behavior, where the ''state'' consists of references to other objects. The ''computational system'' is the dynamic graph of objects held together by these references, and rewired by messages sent along these references.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
A note on terminology: Since 1966 [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Dennis66 Dennis and Van Horn]] the ''object-capability'' model has been known simply as the ''capability ''model. Unfortunately, some other very different models are also called "capabilities", so we introduce the term ''object-capability'' [ref Wagner, [http://www.erights.org/talks/asian03/index.html Paradigm]] to escape from this legacy of confusion.
|}

The ''object-capability ''model of secure computation recognizes the security inherent in the object model. To get from objects to object-capabilities, we need merely prohibit certain primitive abilities which are not part of the pure object model anyway (like forged pointers, direct access to another's private state, mutable static variables) but which the object model by itself doesn't require us to prohibit [ref [http://www.erights.org/elib/capability/ode/index.html Ode]]. For example, C++, with its ability to cast ints into pointers, is still an object language, but is not an object-capability language.

Whereas the ''functionality'' of an object program depends only on the abilities provided by its underlying system, the ''security'' of an object-capability program depends on underlying inabilities as well. In a graph of mutually suspicious objects, one object's correctness depends not only on what the rules of the game say it can do, but also on what the rules say its potential adversaries cannot do. By imposing the object-capability prohibitions, we give the object model new power and meaning. Object-capability computation is no longer just the manipulation of information, but also of secure authority and identity. The object graph becomes a fabric for arranging patterns of ''safe cooperation'' among mutually suspicious objects.

Within the pure object model, because of encapsulation, objects cannot perceive or operate on the graph they are embedded in — they have access only to the behavior (in response to messages) of their immediate graph-neighbors — but not to their neighbors' state. This limited access is adequate for many purposes, but, it would seem, not all. ''Serialization'', explained below, is an example of a tool for use by objects within an object system for operating on the graph they are embedded in. This seems to require violating the encapsulation provided by the pure object model. Given the conventional rationale for encapsulation — that it aids only modularity — one could argue that it is simply prudent engineering to add new primitives for violating encapsulation when needed, as a tradeoff for other benefits. Many object systems provide serialization in precisely this way [ref JOSS, Mozart?].

==Threats and Opportunities==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
To encourage anthropomorphism, this paper often gives objects human names such as "Alice". Unless we explicitly state we're referring to humans, these always refer to objects.
|}

But adding such primitives destroys the security properties inherent in the pure object model. These are exactly the kinds of additions the object-capability model must prohibit. For example, they might allow Mallet, a client of encapsulated Alice, to serialize Alice and then reverse engineer the values of her private instance variables from her serialized form.

This paper shows how to provide the rough equivalent of conventional serialization for use in object-capability systems. This shift of context gives us both new problems to solve and new opportunities to exploit:

* '''Play by the rules'''. We show how to serialize and unserialize purely within object-capability rules, without introducing new primitives or requiring undue authority, thereby guaranteeing that we preserve base level (pre-illusion) object-capability security.
* '''Adapting authority and identity'''. Our serialization framework enables us to manipulate secure authority and identity in addition to information, enabling adaptation to changes involving these issues as well.
* '''Ensure accuracy of claimed authority'''. By object-capability rules, our serializer can only ask Mallet to voluntarily divulge that information he alleges about himself -- his ''portrayal''. If Mallet could convincingly portray himself as having authority he doesn't, the corresponding unserializer could be fooled into granting his reconstruction corresponding authority in its new context. Such a serialization system fails to enforce object-capability rules within the illusion it's attempting to create. We explain how to render this attack inexpressible.
* '''Selective transparency'''. Our serializer can only interact with Alice by sending messages to her public interface, just like any of Alice's other clients. Our serializer can only serialize Alice if she offers her portrayal in response -- if she doesn't, she's not serializable by this serializer. But if she does, what prevents Alice's client Mallet from asking these same question and obtaining this same portrayal, rendering Alice effectively unencapsulated? We show how a serializer and a set of objects may exploit a prior relationship of some additional trust, so that these object may divulge to this serializer portrayals of itself it wouldn't divulge to other clients or serializers.
* '''Invoke no object before its time'''. As with many objects, during Alice's construction / initialization, she may be in a fragile and easily confused state. Under normal conditions this is easily addressed -- don't give Mallet a reference to Alice until she is fully initialized. As programmers, we carefully design the order of object construction to get such issues right. However, during unserialization, object reconstruction does not have this luxury -- the order is often determined by the happenstance of the original graph's traversal. In the absence of cycles we could always reconstruct in bottom up order, but cycles are not absent.But if Mallet's reconstruction (Mallet2) is given access to a not-yet-fully-initialized reconstruction of Alice (Alice2), Mallet2 may exploit Alice2's confusability. The defensive programming needed for Alice2 to be unconfusable is surprisingly hard -- we may not raise the price for security this high. Instead, we explain how to prevent this attack in those systems supporting ''delayed references'' (e.g., promises, logic variables, futures). For other systems, we know of no good solution other than to simulate delayed references. Unfortunately, our technique will occasionally cause valid cyclic serializations to fail to unserialize. Fortunately, the defensive programming needed to overcome this problem, though unpleasant, is straightforward. (** Need to explain that most of this problem is universal, though typically unadmitted.)

{| border="1" cellpadding="12" bgcolor="#ffffe8"
|
==Serialization ''vs.'' Parallelism==
Serialization raises concurrency problems -- what if the graph changes while the serializer is traversing it. Although not the topic of this paper, within '''''E''''' we have easy answers: '''''E''''' is a system of [http://www.erights.org/elib/concurrency/index.html communicating event loops]. Each event loop is identified with a ''vat'' -- essentially an address space full of objects together with a single thread of control for servicing the event loop. Objects only have synchronous access to other objects within their own vat. Inter-vat interactions only queue message deliveries to be serviced eventually in their own event. Therefore, during each event, each object runs with exclusive access to everything it has synchronous access to. We assume that each act of serializing and unserializing occurs during a single event, and therefore only traverses objects within the same vat. In the absence of malice, this provides adequate atomicity. (For systems like Java, built on shared memory multithreading with fine-grained locking, it's hard to imagine any correct general way to address this issue.)However, objects visited early in a traversal can react by causing side effects to shared parts of the graph that are revisited later in the same traversal. Given a normal degree of defensive programming, it's hard to imagine what vulnerability an attacker may find in this issue, but we would be remiss not to raise the possibility.Applications should also arrange to initiate serialization and unserialization at the beginning of an event, as is easily done. Between events there's no stack, so the heap must be consistent by itself. During an event, only the call stack + the heap can be assumed to be fully consistent, but our serialization tools are only able to examine state in the heap.
|}

==What We Have Not Done==

The present work does not address the following issues:

* '''The serializer is able to steal authorities'''. Using the architecture we present, the serializer obtains direct access to each object it traverses, which it can use, if it wishes, for other purposes. By the goals set out in this paper this represents inexcusably excess authority, as the serializer's proper duties include only the gathering of information from these objects [ref Karp, KeyKOS Sensory]. This is a pressing area for future work. Reducing the authority made available to the serializer reduces the risks it imposes on others, enabling them to more often chose to participate in a serialization in which they place limited trust.
* '''Performance'''. The speed achieved by high performance serialization systems [ref Parcels] may be incompatible with the architecture presented here. However, most serialization systems, such as JOSS, are unable to achieve such high performance either. While we know of no flaw in the present design that would preclude the performance achieved by these more common serialization systems, no such engineering has been done, and the question is mostly unexamined.
* '''Dirty bits & in-place stubifying'''. In order to use serialization to build an object-oriented virtual memory system [ref Loom] or object database, for each subgraph that would be separately saved and faulted back in we would need dirty bits to know if it changed. To unload a subgraph (purge it from memory), we would need to turn incoming references (references into the subgraph from outside it) into references to faulting stubs. While we believe that such techniques and those presented in this paper are compatible and complementary, this question is also mostly unexamined.
* '''Denial of service'''. Just as '''''E''''' makes no attempts or claims to resist denial of service attacks within a vat, so our serialization tools likewise do nothing to resist a denial of service attack from within a subgraph. If Mallet or his reconstruction simply throws an exception when traversed, this will abort the traversal preventing that act of serialization or unserialization. The '''''E''''' approach is to prevent breach attacks (inappropriate acquisition or exercise of authority) at the fine granularity of individual objects, as we do here, but to defend against resource exhaustion and denial of service attacks only at the coarser granularity of vats. Is there a corresponding coarser grain for serialization, at which such questions should be addressed? We don't know.
* '''Typed serialization'''. '''''E''''' itself is a dynamically typed language, in the tradition of Smalltalk, Actors, Lisp, or Python. The serialized form used in this paper, Data-E, is a subset of '''''E''''' and is equally untyped. Serialization systems for statically typed object languages like Java generally leverage the existence of static type declarations. One serialization system for Java (the XMLEncoder [ref]) outputs the equivalent of typed Java programs as its serialization format, providing an existence proof of a sort. Do the techniques presented here combine smoothly with static types? One known problem is the unserialization of cycles -- our technique of using delayed references will more often cause unserialization to fail, simply because a delayed references momentarily violates a declared type. A possible solution may be a type system designed to accommodate delayed references. (Note that XML Schema are inapplicable to typed serialization, since declared types constrain all references in the graph, whereas XML schema only constrains a tree.)
* '''Upgrade by refactoring'''. <nowiki>*** explain</nowiki>.
* '''Cryptographic Tunneling'''. <nowiki>*** explain</nowiki>.

=What is Serialization?=

<table width="30%" border="1" style="float:left;margin:5px;">
<tr><td bgcolor="#ffffe8" >
[[Image:lit-real.gif]]
</td></tr><tr><td bgcolor="#ffffe8">
==Figure 1: Literal Realism==
''Time proceeds from top to bottom, as an original live graph gets serialized into a depiction, which gets unserialized into a new live graph we take to be a reconstruction of the original. Although graphs may contain cycles, we generally show object references going from left to right across each diagram.'' 
</td></tr></table>

The Literal Realism diagram on the left represents the common elements of serialization and unserialization. A ''serializer'' (shown as the <tt>serialize</tt> function) takes as input a graph of live ''original'' objects, where this graph is a subgraph, delimited somehow, of an overall object graph. A serializer builds a depiction (shown in the picture frame) of this subgraph in a format it expects a compatible ''unserializer'' to understand. The depiction contains no objects; only bits depicting objects.

(Never mind that objects themselves are implemented using only bits. This view from the implementation isn't available to the objects so implemented -- and must not be -- so we may ignore it for present purposes. By contrast, the depiction consists only of bits, not just in fact, but also as perceived by the objects wielding our serialization tools.)

An ''unserializer'' takes this depiction as input, and uses it to build a new graph of live objects that can, in some sense, be said to be a ''reconstruction'' of the original. The reconstructed objects may or may not resemble the original in a number of different ways, explained below. The reconstructed graph is connected, somehow, into the overall graph at this new context, becoming a subgraph of it. When performed in service of, for example, distributing, persisting, or upgrading objects, the serializer, unserializer, original, and reconstructed objects generally cooperate to create the illusion that the reconstructed objects are a continuation -- across space, time, versions, etc. -- of the original objects.

==Literal Realism==

Within the overall notion of serialization, there are many variations. The following explanation of serialization in Mozart [[http://www.erights.org/data/serial/jhu-paper/acks-n-refs.html#Duchier98 Duchier98]] expresses well the extreme we call ''literal realism''.

{|
|
| Let x be the original data structure and y be a clone of x. Then the graphs reachable from x and y must be graph isomorphic with respect to their roots x and y. Moreover, the (mutable?) cells reachable from x must all be different from the [mutable?] cells reachable from y.
|}

(We are not claiming that actual support for customizing serialization in Mozart is limited in this manner, just that these are the limits implied by the cited spec.)

In this system, in terms of the diagram on the left, the subgraph to be depicted would be all objects reachable from the root object, A1. Non-root incoming references on the left, such as the incoming references to B1 and C1, would not be depicted. Serialization would not cut off any outgoing references on the right. There would be exactly one entry -- the root -- and no exits. A graph containing an unserializable object, such as an open TCP socket, simply cannot be serialized. Unserializing connects the reconstructed subgraph to its new context only at the root. Besides the root, the reconstructed subgraph is completely isolated. Holding no references to anything outside itself, it has no authority to affect anything outside itself. Literal realism of objects must also record and reload code, as a reconstruction must act just like the original.

Literal realism makes for a very clean spec. Unfortunately, it lacks the adaptability we need to create illusions of continuity across many kinds of changes. It also conflicts with the normal constraints of object-capability programming, in which an object's behavior in response to messages is the most that may be ascertained about it.

==Society of Impressionists==

In the object paradigm, objects have no direct access to one another's state. For example, when Alice asks Richard the Rectangle for his height (<tt>r.getHeight()</tt>), she cannot tell, and should not care, whether the answer is part of Richard's state or is computed. All she knows is that she's received the answer Richard wishes to divulge.

To build a serialization system for unprivileged use, it is best to build the serialization system without use of special privileges, thereby forcing it to play by the same rules imposed on all other objects. Within these constraints Literal Realism isn't possible. Literal Realism would require the depiction to reflect the actual state, whereas object constraints limit us to depicting a composition of what each object portrays its state to be. (*** note exception: Auditors) The subgraph the serializer is able to perceive is not the real subgraph of objects in memory, but rather a kind of story spun by the objects being traversed, each for its own purposes.

In this view, represented well by Java's Object Serialization Streams (JOSS) [ref JOSS], a serialization system is a framework for customizing, and for composing customizations of, the processes of depiction and reconstruction. We expect both serialization and unserialization to proceed with the intention that the reconstructed graph be somehow meaningfully similar to the original, but with differences as needed in order to satisfy other goals.

The unserializer builds whatever new objects it likes (subject to the limits of what objects it ''can'' build), but it normally chooses to build along the lines of its interpretation of the intentions of the serializer, as recorded in the depiction. The serializer paints whatever depiction it wishes (subject to the limits of what knowledge it can gain), but it normally chooses to depict along the lines of each original object's expressed intentions of how and whether it would like to be portrayed. Each object portrays that its alleged instance variables -- the set of references it would have the serializer represent as its state and further traverse from there -- is any set of references it likes (subject to the limits of what references it can produce).

(*** Find quote from "I Pencil")

''Modern civilization has given man undreamt of powers largely because, without understanding it, he has developed methods of utilizing more knowledge and resources than any one mind is aware of. ''--Friedrich Hayek [Hayek78]

When all these expressions of intent reflect the code written by one programmer all at once, then they are all aspects of one underlying intent and the architecture for composing intentions may not matter so much. When they are written by different programmers at different times in different companies, all with little knowledge of each other's specifics, then an architecture should be well adapted to the expected locality of knowledge -- demanding from each component the expression of intent which that component is in a better position to contribute. It should compose these together into a result which successfully utilizes more knowledge than any one component plausibly has. JOSS does quite well at this. The Data-E architecture presented below does similarly well for similar reasons -- partially as a result of thinking about and learning from JOSS.

As with many object frameworks translated into an object-capability world, a serialization framework is a system for ''composing knowledge by the rule-based mixing of intentions expressed by mutually suspicious interests''. When these all seek only literal accuracy (the default behavior), and when all the objects to be depicted are transparent (defined below), then the result must be according to Literal Realism. Given this, we can explain the effects of each kind of customization in terms of how it causes the result to deviate from Literal Realism, and of how multiple customizations interact.

==A Model of Serialization==

In the next chapter of the paper, [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E|Deconstructing Serialization Part 1: Introducing Data-E]] and [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation|Part 2: "Reversing" Evaluation]], sets the stage for the remainder of the paper by explaining one concrete serialization system, ''the Data-E System'', designed for expository use in this paper. The depiction format used by the Data-E System, ''Data-E'', is a small subset of the '''''E''''' language. Unserialization in the Data-E System is equivalent to the corresponding subset of '''''E''''' expression evaluation [ref Rees]. This choice enables us to immediately understand the meaning of a depiction by applying our understanding of expressions. This technique can easily be applied to many languages [ref XMLEncoder].

This initial presentation of Data-E will show it living within the constraints of capability discipline, but without yet showing how to live well within those constraints. The resulting loss of power compared to conventional serialization will be repaired in the chapters which follow.

Data-E will be presented in terms of its implementation in '''''E''''' for use in '''''E''''', although Data-E is in no sense specific to '''''E'''''.

Although the ideas in this chapter are mostly specific to Data-E, the ideas in the remainder of the paper are not. They have also been applied to JOSS, and we expect to apply them to Waterken Object Serialization (''WOS'') [ref WOS] as well. They should be applicable in any object-capability language [ref W7, Mozart, M] and starting from any sufficiently customizable serialization mechanism [ref JOSS, XMLEncoder?, WOS, BOSS?], given that it has the crucial property that ''portrayals are only in terms of other objects'', as explained later.

{| width="30%" border="1" align="right" bgcolor="#ffffe8"
|
[[Image:depiction.gif]]
|-
|
==Figure 2: The Three Faces==
''The diagram can be seen in terms of three rows cross three columns. The three rows, progressing in time, are again original, depiction, and reconstruction. The "faces" refers to the three columns, progressing by pointing topology: left (entries), middle (the subgraph interior), and right (exits). Our exposition proceeds instead from right to left. ''
|}

==The Three Faces of Serialization==

To serialize a subgraph of an overall graph, we need to delimit the bounds of the subgraph. Both serialization and unserialization raise issues that can naturally be classified according to the three columnar aspects of the diagram, which we explain in right-to-left order: the exits, the interior, and the entries.

===The Exit Points===

The right edge represents ''outgoing'' references -- references from objects within the subgraph to objects outside it (references leaving A1, B1, and C1). Of these, the ones depicted -- shown crossing the frame as convex jigsaw puzzle plugs -- are ''exits''(references leaving B and C), which the unserializer is expected to reconnect to something appropriate. (Following JOSS, we call outgoing references that aren't depicted, such as the one leaving A1, ''transient''.)

In an object-capability system, an object's only source of authority to affect the world outside of itself is according to the references it holds. By composition, the only authority held by the original subgraph as a whole to affect the world outside that subgraph is according to these outgoing references. To reconnect the exits to corresponding sources of authority is to determine what objects within the reconstructed subgraph can initially ''do''. To the extent that the new authorities resemble the original, we can say the objects holding these reconnected exit references are ''heir'' to these authorities from their original.

A reconstructed subgraph may find itself in a world quite different than the original's. Individual original objects held access to various resources of their hosting platform, and may expect to be reconnected to corresponding resources on their new host.

For example, let's say the original Joe held write access to <tt>/etc/motd</tt>. What criteria should come to play to determine what corresponding resource on the new platform to give to the reconstructed Joe? The chapter [[Manipulating_Authority_at_the Exits]] presents the ''Gordian Surgeon'' as the mechanism, and the legal concept of ''Comity Among Nations'' [ref??] as the metaphor for guiding policy choices, for the security issues of reconnecting exits.

===The Interior Subgraph===

The interior of the picture represents the subgraph itself (A,B,C and the references among them). To reconstruct the subgraph is to replicate information from the original, determining what the reconstructed objects initially ''know''. To the extent that information represented by a reconstructed object resembles information represented by the original, we may say the reconstructed object is a ''replica'' of the original.

The chapter [[Selective_Transparency_within_the_Subgraph]] enhances our idealized model of serialization to regain much of the lost conventional power while remaining within capability discipline. Within capability discipline, the serializer is only able to obtain knowledge of the original subgraph to the extent that the objects within that graph are willing to divulge that knowledge. This chapter shows a rights-amplification pattern by which a serializer may prearrange a relationship with set of objects, enabling these objects to divulge more to that serializer than they are willing to divulge to their normal clients or to other serializers.

===The Entry Points: Transcending Space and Time===

The left edge of the picture represents the ''incoming'' references -- references into the subgraph from objects outside the subgraph. Of these, the ones depicted -- shown crossing the frame as concave jigsaw puzzle sockets -- are ''entries'', those incoming connections the unserializer is expected to reconnect to something appropriate.

In any object system, the meaning of identity is in the behavior of references. To ''be'' a particular identity is to be designated by a particular reference, and thereby to be able to receive those messages (invocations) sent on that reference. In the object model, the philosophy of identity is simple: If I alone receive all communications directed to Joe, then I am Joe. In the object-capability model, the exclusive right to receive messages sent to Joe is the right to be Joe. When a reconstructed object acquires and employs this right from an original, we say it is a ''reincarnation'' of the original.

In a conventional single-process non-distributed, non-persistent object system (a space-time-local system), reincarnation is not really needed. Indeed, in a sense to be explained, it is not even possible. But we often stretch such systems across space and time by building distributed persistent object systems on top of such conventional systems. For example, the JVM itself only provides a space-time-local system, but RMI is built mostly in Java to stretch Java references across space. A number of persistence mechanisms (EJB, JDO) have been built mostly in Java to stretch Java objects and references across time. '''''E''''' is layered in this way, but in '''''E''''', the distributed persistent object system must still be a secure object-capability system. When building this layer of infrastructure, reincarnation is both possible and necessary.

The chapter [[Manipulating_Identity_at_the_Entries]] first explains the cryptographic implementation of distributed identity in '''''E''''''s remote messaging protocol, CapTP. We then show a simple use of cryptographic hashing that securely allows a new object to become the object designated by all outstanding references to the original. With a further elaboration on the hashing theme, we then enable unprivileged fault handlers to delay the act of unserializing and reincarnating from saved depictions until needed to handle incoming requests.

==Transcending Change: Upgrade==

''The art of upgrade is to preserve state amid change and to enable change amid state. ''--with apologies to Alfred North Whitehead [acks-n-refs.html#_ftn1 1]

An object is a bundle of state and behavior. Conventionally, an object's state may be mutable, but not its code. Like a dog that can't learn new tricks, an object conventionally has the same behavior for the duration of its lifetime. Once persistence extends this lifetime well beyond the product release cycles of the programs run by these objects, this inability can become an intolerable problem. To repair this, we must at least deal with the ''schema evolution ''problem -- to convert the concrete representation of the objects to a correct representation compatible with the new code that most closely preserves their original meaning and preserves their assumptions about each other. But schema evolution can be hard. To succeed at complex upgrades of complex systems at reasonable cost, a system should be designed to avoid schema evolution where possible, so that the programmers can afford to invest the attention needed to get it right in the remaining places where it's necessary [ref Arturo].

The chapter [[Persistence_and_Upgrade]] explains how these mechanism have been employed to create user-level persistence in '''''E''''', and how these mechanisms support persistence-with-upgrade by ''schema-evolution-avoidance'' in addition to schema evolution.

=Other Approaches=

The chapter [[Related Work]] surveys other work on serialization and security: Mozart. JOSS. WOS. XMLEncoder. ***What else? The origins of the Gordian Surgeon at Kalieda and NeXT. Abstraction in ToonTalk. Rights amplification for accessing representation: The KeyKOS / EROS Brand. PJama and XOF. Cardelli, Vijay. Rees' uneval. State Bundles

Safe Serialization Under Mutual Suspicion/Abstract and Introduction

2007-08-09T23:09:28Z

DavidHopwood: /* Abstract */

=Safe Serialization Under Mutual Suspicion=

by Mark S. Miller

=Abstract=

''Serialization'' and ''object-capabilities'' [ref [http://www.erights.org/elib/capability/ode/index.html Ode], [http://www.erights.org/talks/asian03/index.html Paradigm]] are two extensions of the object paradigm that seem to pull in opposing directions. Serialization sees an object graph as apparently open data, to convert to bits and back again. The object-capability paradigm sees an object graph as a set of dynamically evolving relationships between mutually suspicious encapsulated autonomous objects, voluntarily cooperating with one another each to pursue their own interests, within limits set by their vulnerability to and trust in each other [ref [http://www.erights.org/history/actors.html Hewitt]].

Serialization is often used to extend the reach of the object model across barriers of space, time, and version; stitching local ephemeral object systems together into a virtual graph of distributed persistent upgradable objects. With serialization we ''create the illusion of object continuity'' by adapting to these changes of context. There are many kinds of change and no single adequate adaptation strategy, so we seek general ''mechanisms'' supporting a diversity of coexisting adaptation ''policies''.

Likewise, serialization is often used to extend the object-capability model across such barriers. By enhancing the illusion to include capability security properties, we create a virtual persistent graph of mutually suspicious objects spread over mutually suspicious machines. Mechanism / policy separation is also needed here, though if too much authority is needed to express a policy choice, few objects will be able to, and little actual policy diversity will occur.

While there is a long history of ''distributed'' capability protocols that meet all these goals [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Donnelley76 Donnelley76], [http://www.erights.org/elib/capability/ode/ode-references.html#Sansom86 Sansom86]/88, Actors?, [http://www.erights.org/elib/capability/ode/ode-references.html#Tanenbaum86 Amoeba]?], prior ''persistent'' capability systems have always granted their persistence service godlike authority over the subsystem it is persisting, leading to single mandated one-size-fits-all solutions [ref KeyKOS, EROS, PJama, Grasshopper, Mach, Waterken?, Mozart?]. By contrast, this paper explains a simple serialization framework able to stretch the full object-capability illusion across all these barriers, able to express a wide range of policies, and requiring only reasonable authority. A diversity of policies may coexist within one system, each able to deal sensibly with mutual suspicion issues

* among objects being serialized,
* between these objects and a serializer,
* between a serializer and an unserializer,
* between an unserializer and its context,
* between an unserializer and the objects it reconstructs, and
* among the reconstructed objects.

For concreteness, we sketch how these ideas are applied in '''''E, '''''a pure object-capability-based secure programming language, thereby turning it into a securely distributed, persistent, and upgradable language as well.

=Introduction=

=Serialization ''vs.'' Security?=

In the pure object model of computation, an ''object'' is an encapsulated combination of state and behavior, where the ''state'' consists of references to other objects. The ''computational system'' is the dynamic graph of objects held together by these references, and rewired by messages sent along these references.

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
A note on terminology: Since 1966 [ref [http://www.erights.org/elib/capability/ode/ode-references.html#Dennis66 Dennis and Van Horn]] the ''object-capability'' model has been known simply as the ''capability ''model. Unfortunately, some other very different models are also called "capabilities", so we introduce the term ''object-capability'' [ref Wagner, [http://www.erights.org/talks/asian03/index.html Paradigm]] to escape from this legacy of confusion.
|}

The ''object-capability ''model of secure computation recognizes the security inherent in the object model. To get from objects to object-capabilities, we need merely prohibit certain primitive abilities which are not part of the pure object model anyway (like forged pointers, direct access to another's private state, mutable static variables) but which the object model by itself doesn't require us to prohibit [ref [http://www.erights.org/elib/capability/ode/index.html Ode]]. For example, C++, with its ability to cast ints into pointers, is still an object language, but is not an object-capability language.

Whereas the ''functionality'' of an object program depends only on the abilities provided by its underlying system, the ''security'' of an object-capability program depends on underlying inabilities as well. In a graph of mutually suspicious objects, one object's correctness depends not only on what the rules of the game say it can do, but also on what the rules say its potential adversaries cannot do. By imposing the object-capability prohibitions, we give the object model new power and meaning. Object-capability computation is no longer just the manipulation of information, but also of secure authority and identity. The object graph becomes a fabric for arranging patterns of ''safe cooperation'' among mutually suspicious objects.

Within the pure object model, because of encapsulation, objects cannot perceive or operate on the graph they are embedded in -- they have access only to the behavior (in response to messages) of their immediate graph-neighbors -- but not to their neighbors' state. This limited access is adequate for many purposes, but, it would seem, not all. ''Serialization'', explained below, is an example of a tool for use by objects within an object system for operating on the graph they are embedded in. This seems to require violating the encapsulation provided by the pure object model. Given the conventional rationale for encapsulation -- that it aids only modularity -- one could argue that it is simply prudent engineering to add new primitives for violating encapsulation when needed, as a tradeoff for other benefits. Many object systems provide serialization in precisely this way [ref JOSS, Mozart?].

==Threats and Opportunities==

{| width="30%" border="1" cellpadding="12" align="right" bgcolor="#ffffe8"
|
To encourage anthropomorphism, this paper often gives objects human names such as "Alice". Unless we explicitly state we're referring to humans, these always refer to objects.
|}

But adding such primitives destroys the security properties inherent in the pure object model. These are exactly the kinds of additions the object-capability model must prohibit. For example, they might allow Mallet, a client of encapsulated Alice, to serialize Alice and then reverse engineer the values of her private instance variables from her serialized form.

This paper shows how to provide the rough equivalent of conventional serialization for use in object-capability systems. This shift of context gives us both new problems to solve and new opportunities to exploit:

* '''Play by the rules'''. We show how to serialize and unserialize purely within object-capability rules, without introducing new primitives or requiring undue authority, thereby guaranteeing that we preserve base level (pre-illusion) object-capability security.
* '''Adapting authority and identity'''. Our serialization framework enables us to manipulate secure authority and identity in addition to information, enabling adaptation to changes involving these issues as well.
* '''Ensure accuracy of claimed authority'''. By object-capability rules, our serializer can only ask Mallet to voluntarily divulge that information he alleges about himself -- his ''portrayal''. If Mallet could convincingly portray himself as having authority he doesn't, the corresponding unserializer could be fooled into granting his reconstruction corresponding authority in its new context. Such a serialization system fails to enforce object-capability rules within the illusion it's attempting to create. We explain how to render this attack inexpressible.
* '''Selective transparency'''. Our serializer can only interact with Alice by sending messages to her public interface, just like any of Alice's other clients. Our serializer can only serialize Alice if she offers her portrayal in response -- if she doesn't, she's not serializable by this serializer. But if she does, what prevents Alice's client Mallet from asking these same question and obtaining this same portrayal, rendering Alice effectively unencapsulated? We show how a serializer and a set of objects may exploit a prior relationship of some additional trust, so that these object may divulge to this serializer portrayals of itself it wouldn't divulge to other clients or serializers.
* '''Invoke no object before its time'''. As with many objects, during Alice's construction / initialization, she may be in a fragile and easily confused state. Under normal conditions this is easily addressed -- don't give Mallet a reference to Alice until she is fully initialized. As programmers, we carefully design the order of object construction to get such issues right. However, during unserialization, object reconstruction does not have this luxury -- the order is often determined by the happenstance of the original graph's traversal. In the absence of cycles we could always reconstruct in bottom up order, but cycles are not absent.But if Mallet's reconstruction (Mallet2) is given access to a not-yet-fully-initialized reconstruction of Alice (Alice2), Mallet2 may exploit Alice2's confusability. The defensive programming needed for Alice2 to be unconfusable is surprisingly hard -- we may not raise the price for security this high. Instead, we explain how to prevent this attack in those systems supporting ''delayed references'' (e.g., promises, logic variables, futures). For other systems, we know of no good solution other than to simulate delayed references. Unfortunately, our technique will occasionally cause valid cyclic serializations to fail to unserialize. Fortunately, the defensive programming needed to overcome this problem, though unpleasant, is straightforward. (** Need to explain that most of this problem is universal, though typically unadmitted.)

{| border="1" cellpadding="12" bgcolor="#ffffe8"
|
==Serialization ''vs.'' Parallelism==
Serialization raises concurrency problems -- what if the graph changes while the serializer is traversing it. Although not the topic of this paper, within '''''E''''' we have easy answers: '''''E''''' is a system of [http://www.erights.org/elib/concurrency/index.html communicating event loops]. Each event loop is identified with a ''vat'' -- essentially an address space full of objects together with a single thread of control for servicing the event loop. Objects only have synchronous access to other objects within their own vat. Inter-vat interactions only queue message deliveries to be serviced eventually in their own event. Therefore, during each event, each object runs with exclusive access to everything it has synchronous access to. We assume that each act of serializing and unserializing occurs during a single event, and therefore only traverses objects within the same vat. In the absence of malice, this provides adequate atomicity. (For systems like Java, built on shared memory multithreading with fine-grained locking, it's hard to imagine any correct general way to address this issue.)However, objects visited early in a traversal can react by causing side effects to shared parts of the graph that are revisited later in the same traversal. Given a normal degree of defensive programming, it's hard to imagine what vulnerability an attacker may find in this issue, but we would be remiss not to raise the possibility.Applications should also arrange to initiate serialization and unserialization at the beginning of an event, as is easily done. Between events there's no stack, so the heap must be consistent by itself. During an event, only the call stack + the heap can be assumed to be fully consistent, but our serialization tools are only able to examine state in the heap.
|}

==What We Have Not Done==

The present work does not address the following issues:

* '''The serializer is able to steal authorities'''. Using the architecture we present, the serializer obtains direct access to each object it traverses, which it can use, if it wishes, for other purposes. By the goals set out in this paper this represents inexcusably excess authority, as the serializer's proper duties include only the gathering of information from these objects [ref Karp, KeyKOS Sensory]. This is a pressing area for future work. Reducing the authority made available to the serializer reduces the risks it imposes on others, enabling them to more often chose to participate in a serialization in which they place limited trust.
* '''Performance'''. The speed achieved by high performance serialization systems [ref Parcels] may be incompatible with the architecture presented here. However, most serialization systems, such as JOSS, are unable to achieve such high performance either. While we know of no flaw in the present design that would preclude the performance achieved by these more common serialization systems, no such engineering has been done, and the question is mostly unexamined.
* '''Dirty bits & in-place stubifying'''. In order to use serialization to build an object-oriented virtual memory system [ref Loom] or object database, for each subgraph that would be separately saved and faulted back in we would need dirty bits to know if it changed. To unload a subgraph (purge it from memory), we would need to turn incoming references (references into the subgraph from outside it) into references to faulting stubs. While we believe that such techniques and those presented in this paper are compatible and complementary, this question is also mostly unexamined.
* '''Denial of service'''. Just as '''''E''''' makes no attempts or claims to resist denial of service attacks within a vat, so our serialization tools likewise do nothing to resist a denial of service attack from within a subgraph. If Mallet or his reconstruction simply throws an exception when traversed, this will abort the traversal preventing that act of serialization or unserialization. The '''''E''''' approach is to prevent breach attacks (inappropriate acquisition or exercise of authority) at the fine granularity of individual objects, as we do here, but to defend against resource exhaustion and denial of service attacks only at the coarser granularity of vats. Is there a corresponding coarser grain for serialization, at which such questions should be addressed? We don't know.
* '''Typed serialization'''. '''''E''''' itself is a dynamically typed language, in the tradition of Smalltalk, Actors, Lisp, or Python. The serialized form used in this paper, Data-E, is a subset of '''''E''''' and is equally untyped. Serialization systems for statically typed object languages like Java generally leverage the existence of static type declarations. One serialization system for Java (the XMLEncoder [ref]) outputs the equivalent of typed Java programs as its serialization format, providing an existence proof of a sort. Do the techniques presented here combine smoothly with static types? One known problem is the unserialization of cycles -- our technique of using delayed references will more often cause unserialization to fail, simply because a delayed references momentarily violates a declared type. A possible solution may be a type system designed to accommodate delayed references. (Note that XML Schema are inapplicable to typed serialization, since declared types constrain all references in the graph, whereas XML schema only constrains a tree.)
* '''Upgrade by refactoring'''. <nowiki>*** explain</nowiki>.
* '''Cryptographic Tunneling'''. <nowiki>*** explain</nowiki>.

=What is Serialization?=

<table width="30%" border="1" style="float:left;margin:5px;">
<tr><td bgcolor="#ffffe8" >
[[Image:lit-real.gif]]
</td></tr><tr><td bgcolor="#ffffe8">
==Figure 1: Literal Realism==
''Time proceeds from top to bottom, as an original live graph gets serialized into a depiction, which gets unserialized into a new live graph we take to be a reconstruction of the original. Although graphs may contain cycles, we generally show object references going from left to right across each diagram.'' 
</td></tr></table>

The Literal Realism diagram on the left represents the common elements of serialization and unserialization. A ''serializer'' (shown as the <tt>serialize</tt> function) takes as input a graph of live ''original'' objects, where this graph is a subgraph, delimited somehow, of an overall object graph. A serializer builds a depiction (shown in the picture frame) of this subgraph in a format it expects a compatible ''unserializer'' to understand. The depiction contains no objects; only bits depicting objects.

(Never mind that objects themselves are implemented using only bits. This view from the implementation isn't available to the objects so implemented -- and must not be -- so we may ignore it for present purposes. By contrast, the depiction consists only of bits, not just in fact, but also as perceived by the objects wielding our serialization tools.)

An ''unserializer'' takes this depiction as input, and uses it to build a new graph of live objects that can, in some sense, be said to be a ''reconstruction'' of the original. The reconstructed objects may or may not resemble the original in a number of different ways, explained below. The reconstructed graph is connected, somehow, into the overall graph at this new context, becoming a subgraph of it. When performed in service of, for example, distributing, persisting, or upgrading objects, the serializer, unserializer, original, and reconstructed objects generally cooperate to create the illusion that the reconstructed objects are a continuation -- across space, time, versions, etc. -- of the original objects.

==Literal Realism==

Within the overall notion of serialization, there are many variations. The following explanation of serialization in Mozart [[http://www.erights.org/data/serial/jhu-paper/acks-n-refs.html#Duchier98 Duchier98]] expresses well the extreme we call ''literal realism''.

{|
|
| Let x be the original data structure and y be a clone of x. Then the graphs reachable from x and y must be graph isomorphic with respect to their roots x and y. Moreover, the (mutable?) cells reachable from x must all be different from the [mutable?] cells reachable from y.
|}

(We are not claiming that actual support for customizing serialization in Mozart is limited in this manner, just that these are the limits implied by the cited spec.)

In this system, in terms of the diagram on the left, the subgraph to be depicted would be all objects reachable from the root object, A1. Non-root incoming references on the left, such as the incoming references to B1 and C1, would not be depicted. Serialization would not cut off any outgoing references on the right. There would be exactly one entry -- the root -- and no exits. A graph containing an unserializable object, such as an open TCP socket, simply cannot be serialized. Unserializing connects the reconstructed subgraph to its new context only at the root. Besides the root, the reconstructed subgraph is completely isolated. Holding no references to anything outside itself, it has no authority to affect anything outside itself. Literal realism of objects must also record and reload code, as a reconstruction must act just like the original.

Literal realism makes for a very clean spec. Unfortunately, it lacks the adaptability we need to create illusions of continuity across many kinds of changes. It also conflicts with the normal constraints of object-capability programming, in which an object's behavior in response to messages is the most that may be ascertained about it.

==Society of Impressionists==

In the object paradigm, objects have no direct access to one another's state. For example, when Alice asks Richard the Rectangle for his height (<tt>r.getHeight()</tt>), she cannot tell, and should not care, whether the answer is part of Richard's state or is computed. All she knows is that she's received the answer Richard wishes to divulge.

To build a serialization system for unprivileged use, it is best to build the serialization system without use of special privileges, thereby forcing it to play by the same rules imposed on all other objects. Within these constraints Literal Realism isn't possible. Literal Realism would require the depiction to reflect the actual state, whereas object constraints limit us to depicting a composition of what each object portrays its state to be. (*** note exception: Auditors) The subgraph the serializer is able to perceive is not the real subgraph of objects in memory, but rather a kind of story spun by the objects being traversed, each for its own purposes.

In this view, represented well by Java's Object Serialization Streams (JOSS) [ref JOSS], a serialization system is a framework for customizing, and for composing customizations of, the processes of depiction and reconstruction. We expect both serialization and unserialization to proceed with the intention that the reconstructed graph be somehow meaningfully similar to the original, but with differences as needed in order to satisfy other goals.

The unserializer builds whatever new objects it likes (subject to the limits of what objects it ''can'' build), but it normally chooses to build along the lines of its interpretation of the intentions of the serializer, as recorded in the depiction. The serializer paints whatever depiction it wishes (subject to the limits of what knowledge it can gain), but it normally chooses to depict along the lines of each original object's expressed intentions of how and whether it would like to be portrayed. Each object portrays that its alleged instance variables -- the set of references it would have the serializer represent as its state and further traverse from there -- is any set of references it likes (subject to the limits of what references it can produce).

(*** Find quote from "I Pencil")

''Modern civilization has given man undreamt of powers largely because, without understanding it, he has developed methods of utilizing more knowledge and resources than any one mind is aware of. ''--Friedrich Hayek [Hayek78]

When all these expressions of intent reflect the code written by one programmer all at once, then they are all aspects of one underlying intent and the architecture for composing intentions may not matter so much. When they are written by different programmers at different times in different companies, all with little knowledge of each other's specifics, then an architecture should be well adapted to the expected locality of knowledge -- demanding from each component the expression of intent which that component is in a better position to contribute. It should compose these together into a result which successfully utilizes more knowledge than any one component plausibly has. JOSS does quite well at this. The Data-E architecture presented below does similarly well for similar reasons -- partially as a result of thinking about and learning from JOSS.

As with many object frameworks translated into an object-capability world, a serialization framework is a system for ''composing knowledge by the rule-based mixing of intentions expressed by mutually suspicious interests''. When these all seek only literal accuracy (the default behavior), and when all the objects to be depicted are transparent (defined below), then the result must be according to Literal Realism. Given this, we can explain the effects of each kind of customization in terms of how it causes the result to deviate from Literal Realism, and of how multiple customizations interact.

==A Model of Serialization==

In the next chapter of the paper, [[Safe_Serialization_Under_Mutual_Suspicion/Introducing_Data_E|Deconstructing Serialization Part 1: Introducing Data-E]] and [[Safe_Serialization_Under_Mutual_Suspicion/Reversing_Evaluation|Part 2: "Reversing" Evaluation]], sets the stage for the remainder of the paper by explaining one concrete serialization system, ''the Data-E System'', designed for expository use in this paper. The depiction format used by the Data-E System, ''Data-E'', is a small subset of the '''''E''''' language. Unserialization in the Data-E System is equivalent to the corresponding subset of '''''E''''' expression evaluation [ref Rees]. This choice enables us to immediately understand the meaning of a depiction by applying our understanding of expressions. This technique can easily be applied to many languages [ref XMLEncoder].

This initial presentation of Data-E will show it living within the constraints of capability discipline, but without yet showing how to live well within those constraints. The resulting loss of power compared to conventional serialization will be repaired in the chapters which follow.

Data-E will be presented in terms of its implementation in '''''E''''' for use in '''''E''''', although Data-E is in no sense specific to '''''E'''''.

Although the ideas in this chapter are mostly specific to Data-E, the ideas in the remainder of the paper are not. They have also been applied to JOSS, and we expect to apply them to Waterken Object Serialization (''WOS'') [ref WOS] as well. They should be applicable in any object-capability language [ref W7, Mozart, M] and starting from any sufficiently customizable serialization mechanism [ref JOSS, XMLEncoder?, WOS, BOSS?], given that it has the crucial property that ''portrayals are only in terms of other objects'', as explained later.

{| width="30%" border="1" align="right" bgcolor="#ffffe8"
|
[[Image:depiction.gif]]
|-
|
==Figure 2: The Three Faces==
''The diagram can be seen in terms of three rows cross three columns. The three rows, progressing in time, are again original, depiction, and reconstruction. The "faces" refers to the three columns, progressing by pointing topology: left (entries), middle (the subgraph interior), and right (exits). Our exposition proceeds instead from right to left. ''
|}

==The Three Faces of Serialization==

To serialize a subgraph of an overall graph, we need to delimit the bounds of the subgraph. Both serialization and unserialization raise issues that can naturally be classified according to the three columnar aspects of the diagram, which we explain in right-to-left order: the exits, the interior, and the entries.

===The Exit Points===

The right edge represents ''outgoing'' references -- references from objects within the subgraph to objects outside it (references leaving A1, B1, and C1). Of these, the ones depicted -- shown crossing the frame as convex jigsaw puzzle plugs -- are ''exits''(references leaving B and C), which the unserializer is expected to reconnect to something appropriate. (Following JOSS, we call outgoing references that aren't depicted, such as the one leaving A1, ''transient''.)

In an object-capability system, an object's only source of authority to affect the world outside of itself is according to the references it holds. By composition, the only authority held by the original subgraph as a whole to affect the world outside that subgraph is according to these outgoing references. To reconnect the exits to corresponding sources of authority is to determine what objects within the reconstructed subgraph can initially ''do''. To the extent that the new authorities resemble the original, we can say the objects holding these reconnected exit references are ''heir'' to these authorities from their original.

A reconstructed subgraph may find itself in a world quite different than the original's. Individual original objects held access to various resources of their hosting platform, and may expect to be reconnected to corresponding resources on their new host.

For example, let's say the original Joe held write access to <tt>/etc/motd</tt>. What criteria should come to play to determine what corresponding resource on the new platform to give to the reconstructed Joe? The chapter [[Manipulating_Authority_at_the Exits]] presents the ''Gordian Surgeon'' as the mechanism, and the legal concept of ''Comity Among Nations'' [ref??] as the metaphor for guiding policy choices, for the security issues of reconnecting exits.

===The Interior Subgraph===

The interior of the picture represents the subgraph itself (A,B,C and the references among them). To reconstruct the subgraph is to replicate information from the original, determining what the reconstructed objects initially ''know''. To the extent that information represented by a reconstructed object resembles information represented by the original, we may say the reconstructed object is a ''replica'' of the original.

The chapter [[Selective_Transparency_within_the_Subgraph]] enhances our idealized model of serialization to regain much of the lost conventional power while remaining within capability discipline. Within capability discipline, the serializer is only able to obtain knowledge of the original subgraph to the extent that the objects within that graph are willing to divulge that knowledge. This chapter shows a rights-amplification pattern by which a serializer may prearrange a relationship with set of objects, enabling these objects to divulge more to that serializer than they are willing to divulge to their normal clients or to other serializers.

===The Entry Points: Transcending Space and Time===

The left edge of the picture represents the ''incoming'' references -- references into the subgraph from objects outside the subgraph. Of these, the ones depicted -- shown crossing the frame as concave jigsaw puzzle sockets -- are ''entries'', those incoming connections the unserializer is expected to reconnect to something appropriate.

In any object system, the meaning of identity is in the behavior of references. To ''be'' a particular identity is to be designated by a particular reference, and thereby to be able to receive those messages (invocations) sent on that reference. In the object model, the philosophy of identity is simple: If I alone receive all communications directed to Joe, then I am Joe. In the object-capability model, the exclusive right to receive messages sent to Joe is the right to be Joe. When a reconstructed object acquires and employs this right from an original, we say it is a ''reincarnation'' of the original.

In a conventional single-process non-distributed, non-persistent object system (a space-time-local system), reincarnation is not really needed. Indeed, in a sense to be explained, it is not even possible. But we often stretch such systems across space and time by building distributed persistent object systems on top of such conventional systems. For example, the JVM itself only provides a space-time-local system, but RMI is built mostly in Java to stretch Java references across space. A number of persistence mechanisms (EJB, JDO) have been built mostly in Java to stretch Java objects and references across time. '''''E''''' is layered in this way, but in '''''E''''', the distributed persistent object system must still be a secure object-capability system. When building this layer of infrastructure, reincarnation is both possible and necessary.

The chapter [[Manipulating_Identity_at_the_Entries]] first explains the cryptographic implementation of distributed identity in '''''E''''''s remote messaging protocol, CapTP. We then show a simple use of cryptographic hashing that securely allows a new object to become the object designated by all outstanding references to the original. With a further elaboration on the hashing theme, we then enable unprivileged fault handlers to delay the act of unserializing and reincarnating from saved depictions until needed to handle incoming requests.

==Transcending Change: Upgrade==

''The art of upgrade is to preserve state amid change and to enable change amid state. ''--with apologies to Alfred North Whitehead [acks-n-refs.html#_ftn1 1]

An object is a bundle of state and behavior. Conventionally, an object's state may be mutable, but not its code. Like a dog that can't learn new tricks, an object conventionally has the same behavior for the duration of its lifetime. Once persistence extends this lifetime well beyond the product release cycles of the programs run by these objects, this inability can become an intolerable problem. To repair this, we must at least deal with the ''schema evolution ''problem -- to convert the concrete representation of the objects to a correct representation compatible with the new code that most closely preserves their original meaning and preserves their assumptions about each other. But schema evolution can be hard. To succeed at complex upgrades of complex systems at reasonable cost, a system should be designed to avoid schema evolution where possible, so that the programmers can afford to invest the attention needed to get it right in the remaining places where it's necessary [ref Arturo].

The chapter [[Persistence_and_Upgrade]] explains how these mechanism have been employed to create user-level persistence in '''''E''''', and how these mechanisms support persistence-with-upgrade by ''schema-evolution-avoidance'' in addition to schema evolution.

=Other Approaches=

The chapter [[Related Work]] surveys other work on serialization and security: Mozart. JOSS. WOS. XMLEncoder. ***What else? The origins of the Gordian Surgeon at Kalieda and NeXT. Abstraction in ToonTalk. Rights amplification for accessing representation: The KeyKOS / EROS Brand. PJama and XOF. Cardelli, Vijay. Rees' uneval. State Bundles

Main Page

2007-01-31T00:36:20Z

DavidHopwood: /* Community */

__NOTOC__
<big>'''Welcome to the ERights.org wiki.'''</big>

'''''E''''' is a secure, distributed, pure-object platform and P2P scripting language for writing ''Capability-based'' [[Smart Contracts]].

== [[Getting Started]] ==

[[Getting Started]] - Tips for '''''E''''' newbies

== What's New? ==

[http://www.erights.org/talks/index.html#google-abac Google Techtalk series on ABAC] - Authorization Based Access Control.

== [[Documentation]] ==

* [[Documentation#Books|Books]]
** [[Walnut|'''''E''''' in a Walnut]]
* [[Documentation#Tutorials|Tutorials]]
* [[FAQ]]
* [[Documentation#Papers|Papers]]
* [[Documentation#Talks and Presentations|Talks and Presentations]]

== [[Downloads]] ==

* [[Downloads#Releases|Releases]] - ready-to-install versions of '''''E'''''. Latest is 0.9.0, released on 2006-12-9.
* [[Downloads#Subversion|Subversion]] - development code

==[[Applications]]==
* [http://homepage.mac.com/kpreid/elang/den.html Den] - Distributed [[wikipedia:Multi-user dungeon|MUD]] system written in '''''E'''''.

== Community ==

[http://www.eros-os.org/pipermail/e-lang/ e-lang mailing list] - discussion of '''''E''''' and other capability languages.

[http://www.eros-os.org/pipermail/cap-talk/ cap-talk mailing list] - discussion of general issues regarding capability security.

== Related Sites ==

[http://www.erights.org Main Erights.org site]

[[wikipedia:E_(programming_language)|'''''E''''' on Wikipedia]]

[[wiki:EeLanguage|'''''E''''' on the C2 wiki]]

[http://www.combex.com/ Combex, Inc.] - The for-profit facet of the '''''E''''' project, featuring [[CapDesk]] -- the capability secure desktop, and [[caplet]] installation and launching framework.

[[Object-capability languages]]

[http://www.codepoetics.com/wiki/index.php?title=Topics:SICP_in_other_languages#E SICP Examples in '''''E'''''] ("SICP" is "Structure and Interpretation of Computer Programs", a classic textbook.)

[http://www.selnet.org/pubs/capbib.html Cap-talk Bibliography]