[e-lang] [ANN] E-on-Common-Lisp now available

[Mark Miller]

David Wagner wrote:
> Mark Miller wrote:
>>Kevin Reid wrote:
>>I agree that this would be useful, if we could define a semantics for this 
>>which is clean, implementable, and useful. The problem is, what is such a weak 
>>pointer allowed to do if there exists an independently calculated instance of 
>>the same integer in the vat? Must this cause the weak pointer to retain it?
> 
> 
> Is there a danger of side channels here?
> [...] the weak
> pointer might be retained, and the cache operation might complete more
> quickly than in the latter case.
> 
> Is this what you were thinking of when you asked the question?

That's the kind of issue I was worried about, yes. The interesting thing about 
the apparently deterministic memoizing cache is that it can use such a weak 
table, be deemed to be DeepFrozen, and cause no loss of any of the security 
properties E claims.

However, the above statement is as revealing of the limits of E's claims as it 
is of the strengths of the memoizing cache at meeting these claims.

<review>
E does not claim to prevent "banging" -- the outward flow of bits on covert or 
side channels. It also doesn't claim to prevent those with access to timing 
information, or various other sorts of non-determinism, from being able to 
listen to that banging. But (using the names from the confinement example in 
Paradigm Regained), if Cassie (the confining customer) instantiates the 
calculator factory she receives from Max (the untrusted calculator 
manufacturer), and if she provides the calculator no sources of survivable[*] 
non-determinism (and therefore no ability to escape from fail-stop[*] 
determinism), and she provides it no channel which Max can overtly effect, the 
calculator can bang bits which Max can hear, but not vice versa!
</review>

Further, in this scenario, Cassie can allow Max and the calculator to share a 
deemed-DeepFrozen virtually deterministic memoizing cache which internally 
uses a "leaky" weak key table, and Max and the calculator still cannot use it 
to successfully communicate bits from Max to the calculator.

In the outward direction, this cache does increase the bandwidth of the 
covert/side channel from the calculator to Max, but E never made any claims 
about limiting this bandwidth.


[*] Given the constraints that E is implemented on top of other platforms, 
like Java, CL, or Squeak, whose precise memory usage E cannot control, 
predict, or be responsible for, E needs to treat memory consumption as 
unpredictable, and therefore memory exhaustion as a non-deterministic event. 
However, we assume that, on all these platforms, when it does occur, the E 
runtime can kill all effected vats without running any further E code. 
Therefore, if you're an E object, so long as you're alive, memory seems 
infinite, since you can't live to experience evidence of the finiteness of 
memory. (Note: This sudden death isn't implemented yet, even in E-on-Java.)

Even this minor leakage of non-determinism does open up a kind of covert 
channel from Max to the calculator: Since the calculator knows Max can decide 
to kill them both (assuming they're in the same vat), therefore, as long as 
the calculator is still alive, it knows that Max hasn't yet decided to do so, 
and the calculator may be able to act on that knowledge. However, the 
calculator can never act on knowledge of the opposite fact, so this is still 
limited to "communicating" something that's somehow less than a bit. I'm not 
sure how to think about this.

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM