The Anthropic Side Channel (was: How would shallow generators compose with lambda?)

[Mark S. Miller-2]

On Thu, May 14, 2009 at 3:42 PM, Brendan Eich <brendan@...> wrote:

> On May 14, 2009, at 2:50 PM, Mark S. Miller wrote:
>
>>> If so, did you have a different way of reasoning about the reasons today
>>> why
>>> finally might not run that I mentioned (iloop detection or other hard
>>> stop)?
>>
>> Those hard stops kill all further activity within that event loop.
>> Once a universe has been destroyed, no further bad things can happen
>> in that universe.
>
> There's always the next universe (new event starts another control flow).
> Life goes on, in the JS serial multiverse, and those finally clauses failed
> to run even though control abruptly left the lambda under the hypothesis.

I am assuming that a hard stop destroying an event loop also destroys
(at least makes inaccessible) all objects that were able to execute
within that event loop. For example, if the event loop corresponds to
a page, a hard stop might force a reload of that page, allocating a
disjoint fresh set of objects. If objects that were able to execute
within a suddenly terminated event loop were still reachable by later
events, then we'd have all the consistency problems explained at
<http://java.sun.com/javase/6/docs/technotes/guides/concurrency/threadPrimitiveDeprecation.html>.
The invariant hazards explained there may be more vivid in the face of
multithreading, but they do not depend on multithreading.




>> Infinite loops don't kill their universe, so this case is similar but
>> different. As the halting problem teaches us, an infinite loop is
>> generally indistinguishable from a loop that hasn't terminated yet.
>> Since control flow has not yet escaped the loop, it hasn't yet
>> bypassed the finally, and so no invariants have yet been violated.
>
> True enough, but see above.

While the iloop is running, the event loop is busy, so no further
events can enter.


> This isn't entirely academic, since information leaks include termination
> channels.

I do not expect to be able to plug such information leakage channels,
and was not trying to. But again, this doesn't endanger any object
invariants.

A similar, but (to me at least) more surprising information leakage
channel is something I've called "The Anthropic Side Channel":

Within universe U, under normal conditions, A will run B and then A
will run C. B and C have no access to each other, and A invokes each
of them careful to not let info flow from B to C. However, this
universe is built on fail stop foundations. No agent can cause the
universe to diverge from its laws of physics, but any agent may induce
a condition such that the universe cannot proceed without diverging.
Under such conditions, the universe halts so that there's no
detectable violation.

Three concrete examples:

* Virtually all formal semantics for memory safe languages can only be
implemented faithfully given an infinite memory. Of course, infinite
memory is a bit too expensive, so instead hi integrity languages (e.g.
Erlang) halt and terminate the process in question. If B allocates too
much memory, this universe is destroyed before C can execute.

* In a sequential imperative system such as JavaScript, if B goes into
an infinite loop, C is never executed.

* In transactional systems, often there is an ambient abort()
primitive available, such that any participant in a transaction can
cause that transaction as a whole to abort, abandoning all state
changes that had happened during the transaction. If B aborts, C is
never executed. More to the point, nothing that C would have done gets
committed.

So, the anthropic side channel enables B to communicate what Brendan
might call a half a bit of information to C. If B does

  if (x) { abort() }

then, if C gets to execute at all, it knows !x. If x is true, then C
never does get to know it, which is why less than a bit has been
communicated.

--
    Cheers,
    --MarkM
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Brendan Eich-3]

On May 14, 2009, at 5:42 PM, Mark S. Miller wrote:

> On Thu, May 14, 2009 at 3:42 PM, Brendan Eich <brendan@...>  
> wrote:
>> On May 14, 2009, at 2:50 PM, Mark S. Miller wrote:
>>
>>>> If so, did you have a different way of reasoning about the  
>>>> reasons today
>>>> why
>>>> finally might not run that I mentioned (iloop detection or other  
>>>> hard
>>>> stop)?
>>>
>>> Those hard stops kill all further activity within that event loop.
>>> Once a universe has been destroyed, no further bad things can happen
>>> in that universe.
>>
>> There's always the next universe (new event starts another control  
>> flow).
>> Life goes on, in the JS serial multiverse, and those finally  
>> clauses failed
>> to run even though control abruptly left the lambda under the  
>> hypothesis.
>
>
> I am assuming that a hard stop destroying an event loop also destroys
> (at least makes inaccessible) all objects that were able to execute
> within that event loop.

You're right that this is necessary with threads and fail-stop  
information flow systems, but plain old iloop DOS prevention as  
practiced in browsers does *not* reload the page. And the browser APIs  
are full of  ways to detect that finallys didn't run, through effects  
overt and covert.


>> This isn't entirely academic, since information leaks include  
>> termination
>> channels.
>
> I do not expect to be able to plug such information leakage channels,
> and was not trying to. But again, this doesn't endanger any object
> invariants.

Just consider iloop DOS prevention as practiced in browsers today:  
finally may not run. That's enough.


> A similar, but (to me at least) more surprising information leakage
> channel is something I've called "The Anthropic Side Channel":

[fun example snipped]


> So, the anthropic side channel enables B to communicate what Brendan
> might call a half a bit of information to C.

You must be referring to my slides at http://www.dagstuhl.de/Materials/index.en.phtml?09141 
  -- I should have better slides blogged next week.

/be
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Mark S. Miller-2]

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan@...> wrote:

>> I am assuming that a hard stop destroying an event loop also destroys
>> (at least makes inaccessible) all objects that were able to execute
>> within that event loop.
>
> You're right that this is necessary with threads and fail-stop information
> flow systems, but plain old iloop DOS prevention as practiced in browsers
> does *not* reload the page. And the browser APIs are full of  ways to detect
> that finallys didn't run, through effects overt and covert.
> [...]
> Just consider iloop DOS prevention as practiced in browsers today: finally
> may not run. That's enough.

JavaScript is used in many hosting environments besides browsers. In
particular, there is rapidly rising enthusiasm for server-side use of
JavaScript, where integrity may matter more, and the equivalent of
reloading may be perfectly fine after a preemptive termination. The
language spec should avoid making such higher integrity uses harder.

I'm curious: What ways do you have in mind to detect that finallys didn't run?


>> So, the anthropic side channel enables B to communicate what Brendan
>> might call a half a bit of information to C.
>
> You must be referring to my slides at
> http://www.dagstuhl.de/Materials/index.en.phtml?09141 -- I should have
> better slides blogged next week.

I was indeed. I look forward to your new slides.


--
    Cheers,
    --MarkM
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Mark S. Miller-2]

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan@...> wrote:
> [...] but plain old iloop DOS prevention as practiced in browsers
> does *not* reload the page. And the browser APIs are full of  ways to detect
> that finallys didn't run, through effects overt and covert.
> [...]
> Just consider iloop DOS prevention as practiced in browsers today: finally
> may not run. That's enough.

Have you tried this lately? In a squarefree shell on several browser I typed in

   var x = 8; try { while (true) {} } finally { x = 7; }

Results:

Safari promped. I told it to "stop" scripts. Afterwards, the event was
terminated, but scripts on the page were still able to run. x was 7,
indicating that finallys were executed on the way out.

IE: Similar, but x was 8 indicating that no finallys were run.

FF, Opera, Chrome: That squarefree shell remained hung and I never got
prompted, even after leaving these to run overnight. I am surprised. I
have not heard of this behavior.


--
    Cheers,
    --MarkM
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Brendan Eich-3]

On May 16, 2009, at 11:25 AM, Mark S. Miller wrote:

> On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan@...>  
> wrote:
>> [...] but plain old iloop DOS prevention as practiced in browsers
>> does *not* reload the page. And the browser APIs are full of  ways  
>> to detect
>> that finallys didn't run, through effects overt and covert.
>> [...]
>> Just consider iloop DOS prevention as practiced in browsers today:  
>> finally
>> may not run. That's enough.
>
> Have you tried this lately? In a squarefree shell on several browser  
> I typed in
>
>  var x = 8; try { while (true) {} } finally { x = 7; }
>
> Results:
>
> Safari promped. I told it to "stop" scripts. Afterwards, the event was
> terminated, but scripts on the page were still able to run. x was 7,
> indicating that finallys were executed on the way out.

Seems like an exception (possibly uncatchable?) was thrown.


> IE: Similar, but x was 8 indicating that no finallys were run.
>
> FF, Opera, Chrome: That squarefree shell remained hung and I never got
> prompted, even after leaving these to run overnight. I am surprised. I
> have not heard of this behavior.

Not sure what's up there -- which version of Firefox? Also, you can  
run that code in a javascript: URL typed directly into the address  
bar, or into the Error Console's text input.

I just entered

javascript:var x = 8; try { while (true) {} } finally { x = 7; }; void 0

into the address bar in Firefox 3.5 pre-release, and after ten seconds  
(we use wall time to watchdog scripts) I got the slow script dialog.  
Clicking Stop then terminated the loop, and as with IE, the finally  
ran, as

javascript:alert(x)

confirmed by alerting 8 not 7.

The IE and Firefox policy is meant to stop the script for good.  
Running finallys might just re-iloop, leading to the slow script  
dialog, user picks Stop, finallys run, ad infinitum:

javascript:var x = 8; (function f() { try { while (true) {} } finally  
{ x = 7; f(); } })(); void 0

An implementation supporting tail call optimization wouldn't grow its  
stack so the stack growth limiting done by quality implementations ;-)  
would not save you.

This seems a good reason not to run finallys.

The same issue came up with our attempts to automate generator close  
from the GC, as Python does. This is a no-no in browsers. In other  
embeddings, it could be desirable, but it overconstrains the  
implementation (CPython uses refcounting with cycle GC, and the prompt  
finalization is expected by programmers).

/be
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Brendan Eich-3]

On May 21, 2009, at 10:41 AM, Brendan Eich wrote:

> Clicking Stop then terminated the loop, and as with IE, the finally  
> ran, as

er, "the finally did *not* run".

/be

>
>
> javascript:alert(x)
>
> confirmed by alerting 8 not 7.


_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Maciej Stachowiak]

On May 16, 2009, at 11:25 AM, Mark S. Miller wrote:

> On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan@...>  
> wrote:
>> [...] but plain old iloop DOS prevention as practiced in browsers
>> does *not* reload the page. And the browser APIs are full of  ways  
>> to detect
>> that finallys didn't run, through effects overt and covert.
>> [...]
>> Just consider iloop DOS prevention as practiced in browsers today:  
>> finally
>> may not run. That's enough.
>
> Have you tried this lately? In a squarefree shell on several browser  
> I typed in
>
>   var x = 8; try { while (true) {} } finally { x = 7; }
>
> Results:
>
> Safari promped. I told it to "stop" scripts. Afterwards, the event was
> terminated, but scripts on the page were still able to run. x was 7,
> indicating that finallys were executed on the way out.

I'm not sure but I think maybe the Safari behavior is a bug, as the  
finally clause could contain another infinite loop.

Regards,
Maciej

_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Igor Bukanov-2]

2009/5/27 Maciej Stachowiak <mjs@...>:
>
> I'm not sure but I think maybe the Safari behavior is a bug, as the finally
> clause could contain another infinite loop.

Indeed, if a browser respects finally clauses in the code after
terminating a too long running loop, then the following would be an
effective DOS:

javascript:Array(1e3).join('try {')+Array(1e3).join('} finally { while
(1); }');

Regards, Igor
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss

[Igor Bukanov-2]

2009/5/27 Igor Bukanov <igor@...>:
> Indeed, if a browser respects finally clauses in the code after
> terminating a too long running loop, then the following would be an
> effective DOS:
>
> javascript:Array(1e3).join('try {')+Array(1e3).join('} finally { while
> (1); }');

I meant

javascript:eval(Array(1e3).join('try {')+Array(1e3).join('} finally {
while (1); }'))

Igor
_______________________________________________
es-discuss mailing list
es-discuss@...
https://mail.mozilla.org/listinfo/es-discuss