Home » forums » LtU Forum

Distributed capabilities versus network latency

With distributed capabilities we can send an object from computer X to computer Y. We do not want computer Y to be able to look at the internals of the object, hence we send a distributed reference to the object. If Y wants to do something with it, it will have to ask computer X to do it instead. This has two problems: (1) it causes latency on computer Y because of the network round-trip (2) it causes extra load on computer X.

In some cases the security we get from using references is not necessary. The data inside the object might not be secret, or it might be partially secret. For example suppose we have an Employee object, and send it over to computer Y. The name and ID of the employee are not secret, so we can send them over so that Y can do its work without further contacting X.

Another case is a mutable Employee object. Suppose that its name and ID are Mutable[String] and Mutable[Number] respectively. A Mutable is a mutable reference. When we send the object over to Y, we want to give it read access but not write access to the name and ID. Hence we should not send the distributed references to the Mutable[String] and Mutable[Number] objects, because then Y would have the ability to invoke the name.set(newname) method of the mutable reference. Instead we have to send over an immutable version of the Mutables.

Suppose the Employee object has a method incrementID that sets its ID to ID+1. When we invoke this on computer Y we will have to send a network request to X because we do not have write access to the ID. In this case it is not possible to eliminate problem (2) but it is still possible to eliminate (1). We can give Y write access to its own mutable ID reference. When Y calls incrementID it updates its local ID to ID+1, *and* it sends a network request invoking the method incrementID on X. This way Y can continue its further execution immediately, instead of waiting for the network request to complete. A malicious Y can do what it pleases with its own ID, for example it can decrement it. But it cannot mutate the ID stored on X other than via incrementID.

Is there a paper that describes primitives for doing this? Something along the lines of marking some objects as not secret, and then automatically provide either latency reducing operations (such as incrementID) or provide operations that completely eliminate network usage (such as getName), as appropriate. There might be problems with keeping the local and remote objects in sync, and not duplicating remote calls to other objects. Any ideas/input is appreciated.

By Jules Jacobs at 2012-03-15 12:14 | LtU Forum | previous forum topic | next forum topic | other blogs | 4961 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Under which conditions do

Under which conditions do you not want computer Y to be able to look at the internals of the object? Under which conditions would computer Y not want to host the object? Would it be possible to send the object to another system in between X and Y (aka the `cloud`)? How do we upgrade code for an object after distributing it? How do we handle the problems of disruption and latency?

The problem of automated code distribution is one that has interested me for eight years now, and I've spent much time thinking about these questions and how to achieve it. Object capability security is insufficient to decide whether a particular unit of code can be shared. But there are other techniques that are suitable, based on information flow analysis (tainting code that information touches, and weakening information that is combined or hashed in certain ways).

To support flexible distribution to intermediate systems, we need heterogeneous trust models - i.e. not just server vs. client, but "this data is trusted with hosts certified for Foo, that data is trusted with hosts certified for Bar" where Foo and Bar are your own certificates or those from a group you trust. Including cert requirements directly in code would be too onerous, but they can be attached to a data source (database) easily enough and propagated through taint models.

Of course, just because Alice trusts Bob with her code doesn't mean Bob is willing to host Alice's code.

Object capability security helps here a great deal. Bob can at least know that the Alice's code won't access anything that Alice isn't already authorized to access. This, IMO, is the greatest benefit of object capability security - the ability to deliver code or batches that contain diverse, ad-hoc, provably authorized hooks into different parts of a remote system.

Bob also wants a guarantee that the code won't spin in infinite loops or consume all his resources - various real-time and safety properties, the ability to safely disrupt the code. Or, alternatively, Bob may ask to be paid by Alice for the onerous task. (Market integration, i.e. agoric software, is an effective defense against denial of service risks.)

There are many papers on the subjects of tracing information flows. It's actually one of the most valuable security models, a viable alternative to object capability security with its own community of staunch adherents. I don't recall many by name, but the most recent I read regarded Ur/Web, which provides a nifty known predicate for proving certain information is known or will not be known by a client.

It helps to have a language suitable for dataflow analysis. Capability security can help there, too (by eliminating ad-hoc communication through the environment), but the use of internal state also does a lot to hinder precise analysis.

By dmbarbour at Thu, 2012-03-15 15:48 | login or register to post comments

The programmer specifies

The programmer specifies which Y's can look at which parts of each object. The idea is that the programmer can relax the security requirements that the system provides to gain better performance. For example suppose we have an array data type. In the traditional capability model we send a reference to Y instead of copying the array over to Y. This means that every time Y wants to look up an element it has to send a network request to X. However, as a programmer we already know that due to how an array works, Y is able to gain access to each element anyway via an array's public interface. So we might as well send the whole array over instead of a reference (if the array is not too big). It is perhaps possible to determine automatically with sufficient precision which parts of an object Y could get access to anyway, but it is no problem to have the programmer specify this for now (and in some cases we might want to also send non secret data over that Y could not get access to via a the public interface).

In my case Y is always willing to run any code that X sends it (it will run in a sandbox, and Y doesn't care about computing costs, but it *does* care about the latency that is eliminated by running the code locally). On the other hand, X does not trust Y. Therefore a method such as incrementID should run on X. Because X does not trust Y to increment the ID correctly we don't want to give Y arbitrary write access to the mutable ID, but only through incrementID. In the case that Y does not want to run any code, it can do so very easily by using the reference to the object instead.

By Jules Jacobs at Fri, 2012-03-16 10:28 | login or register to post comments

Remote Batching

Regarding the latency issue, we can also use remote batching, which works well with capability security. We simply create a procedure that might access multiple objects on a remote system and do some processing in between.

William Cook and Oleg Kiselyov have both received mentions for such work on LtU. Oleg's work is very like promise pipelining in E.

By dmbarbour at Thu, 2012-03-15 15:55 | login or register to post comments

Batching & promise

Batching & promise pipelining does eliminate multiple latency hits, but it does not eliminate the initial one, which is what I'm most concerned about. For example suppose a user interface on Y displays the ID and a button "increment ID". There is also a callback registered on the mutable ID that notifies the user interfaces when it changes, so that the ID displayed can be updated. When you click the button the ID gets incremented. With normal capabilities, Y sends a network request to X to increment the ID. Then X will invoke the callback on Y which updates the user interface. This incurs a whole network round-trip before the ID on the user interface gets updated. What I'd like to achieve is that the ID is also represented on Y, so that the ID in the interface gets updated immediately and the network request to X to increment the ID gets sent in the background.

By Jules Jacobs at Fri, 2012-03-16 10:33 | login or register to post comments

Unum Pattern

Unum pattern, developed in E, seems quite relevant to your last two paragraphs.

By dmbarbour at Thu, 2012-03-15 16:08 | login or register to post comments

This is really close to what

This is really close to what I'm looking for :) Essentially I'd like a way to automatically derive an unum from a normal object + security policy. Ideally the semantics would be unchanged when using the unum instead of a far reference to the object, but I realize that this is not possible. So some model for reasoning about the reduced consistency of the system is required. It could be that Uni-Tea is exactly what I'm looking for, but the link is broken...

By Jules Jacobs at Fri, 2012-03-16 10:37 | login or register to post comments

State Model

You might be able to achieve consistent semantics (between client and server) if you push object state into an external resource - a mesh of data that is essentially an unum (i.e. a cloud-like database, where part of the cloud is `on` the client). This is a design I've been favoring, at least. I'll get back to it in a later post.

I've sent a few e-mails to hopefully get that link fixed in the next few days.

By dmbarbour at Fri, 2012-03-16 15:08 | login or register to post comments

Uni-Tea

I was just informed by MarkM that the site should be up again (except for a certificate warning).

By dmbarbour at Mon, 2012-03-26 17:45 | login or register to post comments

Quite a bit of work in

Quite a bit of work in Mozart/Oz. See for instance:

A Lightweight Reliable Object Migration Protocol

A Fault Tolerant Abstraction for Transparent Distributed Programming

There's also a full thesis on the subject of Oz's automatic network transparency with configurable fault tolerance managers, but I always have trouble finding it. Ah, here it is:

The Limits of Network Transparency in a Distributed Programming Language (previously mentioned here on LtU).

By naasking at Thu, 2012-03-15 17:29 | login or register to post comments

Client-Immediate EC

A useful design pattern is to model state updates in a primarily monotonic, idempotent manner. Break state into a lot of miniature databases. Each database has only one master, who is allowed to perform non-monotonic operations (deletions, updates). But other agents may be granted authority to add to the database (monotonically) and view it.

The master database is synchronized with agents that view it. They have their own copy of the database, and they add to it. Eventually those additions are pushed back to the master, who is free to delete them. Usually, the master will update some summary records before deleting the added records.

In your example case, the server would be responsible for (at least) one database, representing server interests. The client might also have its own client-side database, which keeps track of client-side events (e.g. reporting when the network is disrupted). The client's UI is then a reactive view of these two databases. Reactions can over time modify the client-side database and add elements to the server-side database. (IMO, the reactive view should be internally stateless.)

So, for example, the client might view a particular text field as being a summary of the local copy of the server-side database - i.e. a particular summary record, +1 for each record of the form `Client C increments ID at time T`.

Consistency, then, is based on ensuring that the client's view is consistent with how the server would actually adjust the summary record. This is a relatively easy problem to reason about, and is answered by the same sort of unum distribution pattern I mentioned earlier. It scales well to multiple clients, too, since it is easy for multiple clients to share a consistent view even if none of them is the master.

Security is achieved through modularity - lots of small databases, no global access. This also makes it easy to delete whole databases, for GC. The design is also disruption and partitioning tolerant.

By dmbarbour at Fri, 2012-03-16 16:13 | login or register to post comments

Overview

No mention of objects, but journal.info.unlp.edu.ar/journal/journal16/papers/jcst-dec05-22.pdf gives an overview of security issues in process migration and systems that support it.

By Andrew Moss at Fri, 2012-03-16 18:24 | login or register to post comments