[cap-talk] Lua, Javascript, and the Object Capability Model

[James Graves]

Mike Samuel wrote:
> That might be useful if the limiting mechanism was fundamentally
> sound, but it does nothing to guarantee the soundness of the limiting
> mechanism.
>
> What happens when an instruction limit is reached?  Is the entire
> context marked invalid so no further side-effecting computations can
> occur on a possibly inconsistent object-graph?
>
> And that kind of drastic action -- throwing away the entire program
> state -- is awfully harsh when a programmer has no way to compute a
> reasonable upper limit on the number of instructions a complex
> operation might take.  Consider the case where a you have two mutually
> referencing modules that communicate by passing functions to one
> another -- neither module author can compute a limit since every time
> control crosses a module boundary, they have to treat it as a black
> box, and there is no clear way to determine against whom the cost of
> an operation should be debited, since these calls might be
> co-recursive.
>
> Without some kind of transactional semantics to limit the scope of
> what you have to throw away when a limit is reached, you are
> sacrificing either a lot of correctness/security or a lot of one kind
> of availability for a little bit of another kind of availability.
>   
These are all good points.  It wasn't my intention that an execution 
limit would be the only means to control a sub-environment.

However, it seems to me that all modules will eventually have to 
advertise time and space requirements for their use.  It may become a 
standard part of the contract / module interface.

Rather than having the programmer specify this manually, we could 
develop some kind of worst-case analysis, along the lines of if the 
input is X in size, then the computation will take Y units of time.  
Perhaps using the techniques of QuickCheck from Haskell.

This all came up for me in the context of starting the design of AI 
systems that compete inside a real time strategy game.  It is necessary 
to limit the execution time of the AI code to fit within the desired 
game clock ticks.  But it isn't fair to just use wall clock time either, 
if some other process is bogging down the system.  So a violation of the 
time limits is a bug and will result in the forfeit of the game.  Hence 
the limit on instruction cycles.

For that particular application, I was thinking about a soft limit that 
merely generates an exception to the running code.  And when the hard 
limit is exceeded, that will shut down the thread containing the AI code.

And from that I was thinking about the needs for executing untrusted 
code in general.

BR,

James