Defending from long-running or infinite loops

31 views
Skip to first unread message

Michael FIG

unread,
Oct 14, 2018, 6:46:59 PM10/14/18
to Google Caja Discuss
Hi,

Thanks so much for Caja!  It's exactly what I'm looking for to allow client extensions to my platform.

I was wondering if there is a way to have the host program provide an interceptor for entering a function/backward branches (such as before "continue" statements or just before the end for loops, while loops and do...while loops).

Basically, I would want this interceptor to be called every time we execute non-linear code and either risk freezing the browser or blowing out the stack.

Then, I could have this interceptor either just return to allow the execution or throw an exception to prevent the code from continuing to run.

This would greatly extend the security of my Caja sandbox, and prevent one of the main attacks I can forsee from my client code.

while (true) {
   // infinite loop
}

or

var j = 2;
for (var i = 0; i < j; i ++) {
  j ++;
}

or

function loopme() {
  part2();
}

function part2() {
  part3();
}

function part3() {
  loopme();
}

loopme();

Any advice would be much appreciated!

Michael.

Mark Miller

unread,
Oct 14, 2018, 11:05:27 PM10/14/18
to Google Caja Discuss
Hi Michael, the problem with any such mechanism is how to avoid corrupted state. The only consistent states for the heap, considered without the stack, are between turns when the stack is empty. Once a turn starts, it must be viewed as a transaction, to either roll forward to the end of turn committing the transaction, or roll back to the last inter-turn state, aborting the transaction. For the kinds of scenarios that Caja was built for, we could not afford the bookkeeping to roll back to beginning of turn, so there's no way to recover that vat from an infinite loop.

At Agoric we (together with Salesforce) have reconstructed SES for modern JavaScript at https://github.com/Agoric/SES . This is currently no better at coping with the issue you raise than is the old SES (SES5) component of Caja. However, one of our main motivating use cases is running SES on blockchains, where this issue becomes unavoidable. Fortunately, on blockchains, we can afford the bookkeeping needed for abortable transactions.

To do the metering, we're planning to do a source-to-source rewrite inserting the equivalent of calls to your interceptor at least at function entries and loop body entries.This is essentially the approach ewasm takes to throttling wasm computations.

Crucially, if the interceptor decides against continuing the computation, it does not throw an exception, as that would leave corrupted state. Instead it aborts the transaction, rolling back all effects that had happened so far during that turn.

Unfortunately, until both of those bits of engineering are done --- the source-to-source rewrite and the abortable turn bookkeeping --- I can't offer any practical advice.



--

---
You received this message because you are subscribed to the Google Groups "Google Caja Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-caja-dis...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.


--
  Cheers,
  --MarkM

Michael FIG

unread,
Oct 15, 2018, 1:52:53 AM10/15/18
to Google Caja Discuss
Thanks for the speedy reply, Mark.


On Sunday, October 14, 2018 at 9:05:27 PM UTC-6, MarkM wrote:
Hi Michael, the problem with any such mechanism is how to avoid corrupted state. The only consistent states for the heap, considered without the stack, are between turns when the stack is empty.
[...]
To do the metering, we're planning to do a source-to-source rewrite inserting the equivalent of calls to your interceptor at least at function entries and loop body entries.

That's what I was planning.

Crucially, if the interceptor decides against continuing the computation, it does not throw an exception, as that would leave corrupted state. Instead it aborts the transaction, rolling back all effects that had happened so far during that turn.

I'm not understanding why throwing an exception at the beginning of a loop body or function call in a Javascript implementation can create corrupted state.  Does that mean if I have client code that does:

for (var i = 0; i < 20; i ++) {
  throw Error('I just corrupted your heap');
}

the host will die a horrible death?

Is this (and "transactions') part of the Caja internals?

Unfortunately, until both of those bits of engineering are done --- the source-to-source rewrite and the abortable turn bookkeeping --- I can't offer any practical advice.

I would have thought that the source-to-source transform would be fairly easy, but don't understand the abortable bookkeeping.

Glad to see this is on your radar, though.  I've been a follower since erights.org went live, and it's great to see that the concepts are in use.

Thanks,
Michael.

Mike Stay

unread,
Oct 15, 2018, 10:47:51 AM10/15/18
to Google Caja Discuss
On Sun, Oct 14, 2018 at 11:52 PM Michael FIG <kekit...@gmail.com> wrote:
>
> Thanks for the speedy reply, Mark.
>
> On Sunday, October 14, 2018 at 9:05:27 PM UTC-6, MarkM wrote:
>>
>> Hi Michael, the problem with any such mechanism is how to avoid corrupted state. The only consistent states for the heap, considered without the stack, are between turns when the stack is empty.
>
> [...]
>>
>> To do the metering, we're planning to do a source-to-source rewrite inserting the equivalent of calls to your interceptor at least at function entries and loop body entries.
>
>
> That's what I was planning.

I'd recommend Babel for any source-to-source rewriting of javascript.

>> Crucially, if the interceptor decides against continuing the computation, it does not throw an exception, as that would leave corrupted state. Instead it aborts the transaction, rolling back all effects that had happened so far during that turn.
>
>
> I'm not understanding why throwing an exception at the beginning of a loop body or function call in a Javascript implementation can create corrupted state.

It has to do with security invariants of the code. Without explicit
throws, programmers don't think about the possibility of throwing an
exception at that point. There have even been attacks on javascript
code that measures the depth of the stack by recursing with a counter,
catching the resulting stack overflow error, and then invoking a
function at a certain stack depth so it throws an error in a critical
place.

All that said, your particular use case may not care about the
security invariants of plugins, just the invariants of your own code.
If that's the case, then your plan may work. Be sure that any host
code that calls into guest code handles thrown exceptions properly.
--
Mike Stay - meta...@gmail.com
http://math.ucr.edu/~mike
https://reperiendi.wordpress.com

Michael FIG

unread,
Oct 15, 2018, 7:49:18 PM10/15/18
to google-ca...@googlegroups.com
Thank you, that makes perfect sense.

Yes, I'm only concerned about defending my host code, which will be aware of this potential.  I'll put together some simple tests that illustrate what I'm aiming for, and get back to the list when I have a strawman implementation completed.

But yes, I'm looking forward to the robust implementation MarkM has in mind!

Many thanks,
Michael.

--

---
You received this message because you are subscribed to a topic in the Google Groups "Google Caja Discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/google-caja-discuss/swKiyyJ8hRw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to google-caja-dis...@googlegroups.com.

Michael FIG

unread,
Oct 15, 2018, 10:15:21 PM10/15/18
to Google Caja Discuss
I think I will also call the interceptor at the top of every catch block, to allow it to keep throwing all the way up the stack.

Michael.

Mark Miller

unread,
Oct 16, 2018, 1:49:10 AM10/16/18
to Google Caja Discuss
On Mon, Oct 15, 2018 at 7:15 PM Michael FIG <kekit...@gmail.com> wrote:
I think I will also call the interceptor at the top of every catch block, to allow it to keep throwing all the way up the stack.

And finally block!

That is a nice elegant solution for turning these situations into clean transaction aborts rather than thrown errors. With such extra calls inserted, you should indeed be able to guarantee that no further guest code executes once it hits this exhaustion condition. Nice!
 

Michael.

--

---
You received this message because you are subscribed to the Google Groups "Google Caja Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-caja-dis...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.


--
  Cheers,
  --MarkM
Reply all
Reply to author
Forward
0 new messages