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

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

# Mark S. Miller (16 years ago)

On Thu, May 14, 2009 at 3:42 PM, Brendan Eich <brendan at mozilla.com> 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 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.

# Brendan Eich (16 years ago)

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

On Thu, May 14, 2009 at 3:42 PM, Brendan Eich <brendan at mozilla.com>
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 www.dagstuhl.de/Materials/index.en.phtml?09141 -- I should have better slides blogged next week.

# Mark S. Miller (16 years ago)

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan at mozilla.com> 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 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.

# Mark S. Miller (16 years ago)

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan at mozilla.com> 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.

# Brendan Eich (16 years ago)

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

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan at mozilla.com>
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).

# Brendan Eich (16 years ago)

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".

# Maciej Stachowiak (16 years ago)

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

On Fri, May 15, 2009 at 2:26 PM, Brendan Eich <brendan at mozilla.com>
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.

, Maciej

# Igor Bukanov (16 years ago)

2009/5/27 Maciej Stachowiak <mjs at apple.com>:

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); }');

, Igor

# Igor Bukanov (16 years ago)

2009/5/27 Igor Bukanov <igor at mir2.org>:

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