Avoiding an Infinite Loop in Arbitrary eval(user_code)

[Bill Mill]

Hello all,

I want to have a user able to eval code in a text box. However, if he
accidentally types "while(1) { i=0; }" and hits "run", I also want him
to be able to hit a stop button such that his browser does not go into
an infinite, soul-crushing, interface-locking loop. The stop button
would not need to be instantly responsive, but of course the more
responsive the better.

Short of writing a javascript-in-javascript interpreter, is there any
way to do so? Does Caja make this sort of thing possible? Will I need
to restrict myself to Gears+threads to do this?

Thanks for any help,
Bill Mill
bill.mill@gmail .com

[Erwin Moller]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

Bill Mill schreef:

Hello all,
>
I want to have a user able to eval code in a text box. However, if he
accidentally types "while(1) { i=0; }" and hits "run", I also want him
to be able to hit a stop button such that his browser does not go into
an infinite, soul-crushing, interface-locking loop. The stop button
would not need to be instantly responsive, but of course the more
responsive the better.

Hi Bill,

My Firefox notices long running scripts and offers to abort them after a
while.
What browser are you using?

Regards,
Erwin Moller

>
Short of writing a javascript-in-javascript interpreter, is there any
way to do so? Does Caja make this sort of thing possible? Will I need
to restrict myself to Gears+threads to do this?
>
Thanks for any help,
Bill Mill
bill.mill@gmail .com

[Captain Paralytic]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On 23 Apr, 07:29, Erwin Moller
<Since_humans_r ead_this_I_am_s pammed_too_m... @spamyourself.c om

Hi Bill,
>
My Firefox notices long running scripts and offers to abort them after a
while.
What browser are you using?

Surely what browser the OP is using has no bearing on this. The
question is what browser will the arbitrary user be using?

[Thomas 'PointedEars' Lahn]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

Bill Mill wrote:

I want to have a user able to eval code in a text box. However, if he
accidentally types "while(1) { i=0; }" and hits "run", I also want him
to be able to hit a stop button such that his browser does not go into
an infinite, soul-crushing, interface-locking loop. The stop button
would not need to be instantly responsive, but of course the more
responsive the better.
>
Short of writing a javascript-in-javascript interpreter, is there any
way to do so?

No. ECMAScript implementations so far are single-threaded, and there is yet
an algorithm to be written for a universal solution of the Halting Problem.

http://en.wikipedia.org/wiki/Halting_problem

You will have to rely on the user's user agent to recognize a not-responding
script, and provide the user with such a dialog window, as Gecko-based UAs
(e.g. Mozilla Firefox) do.

Does Caja make this sort of thing possible?

I don't think so:

http://code.google.com/p/google-caja/wiki/AttackVectors

Please be more verbose next time.

Will I need to restrict myself to Gears+threads to do this?

Never heard of those.


PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann

[Bill Mill]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On Apr 23, 1:07 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:

Bill Mill wrote:

I want to have a user able to eval code in a text box. However, if he
accidentally types "while(1) { i=0; }" and hits "run", I also want him
to be able to hit a stop button such that his browser does not go into
an infinite, soul-crushing, interface-locking loop. The stop button
would not need to be instantly responsive, but of course the more
responsive the better.

>

Short of writing a javascript-in-javascript interpreter, is there any
way to do so?

>
No.  ECMAScript implementations so far are single-threaded, and there isyet
an algorithm to be written for a universal solution of the Halting Problem..
>
http://en.wikipedia.org/wiki/Halting_problem

Thanks, I know just what that is, and I'm not asking for a solution to
it. Allowing a user to stop an eval is not equivalent to determining
prior to the eval whether or not it will ever complete.

>
You will have to rely on the user's user agent to recognize a not-responding
script, and provide the user with such a dialog window, as Gecko-based UAs
(e.g. Mozilla Firefox) do.

I can't rely on this, since I would like to allow the user to write
scripts that take a while to run. Thus, he's likely to disable this
dialog for the page.

>

Does Caja make this sort of thing possible?

>
I don't think so:
>
http://code.google.com/p/google-caja/wiki/AttackVectors

How is that relevant to what I asked? I've read the Caja website, as
well as the PDF describing the system, and I'm still not clear on
whether it can or not.

>
Please be more verbose next time.

what more would you like to know?

>

Will I need to restrict myself to Gears+threads to do this?

>
Never heard of those.

I meant that I might be able to use Google Gears' threads to achieve
what I'm looking for.

-Bill Mill

[Bill Mill]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On Apr 23, 1:57 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:

Bill Mill wrote:

[...] Thomas 'PointedEars' Lahn [...] wrote:

Bill Mill wrote:
>I want to have a user able to eval code in a text box. However, if he
>accidentally types "while(1) { i=0; }" and hits "run", I also want him
>to be able to hit a stop button such that his browser does not go into
>an infinite, soul-crushing, interface-locking loop. The stop button
>would not need to be instantly responsive, but of course the more
>responsive the better.
>Short of writing a javascript-in-javascript interpreter, is there any
>way to do so?
No.  ECMAScript implementations so far are single-threaded, and thereis yet
an algorithm to be written for a universal solution of the Halting Problem.

>

>http://en.wikipedia.org/wiki/Halting_problem

>

Thanks, I know just what that is, and I'm not asking for a solution to
it. Allowing a user to stop an eval is not equivalent to determining
prior to the eval whether or not it will ever complete.

>
But you will need a threaded implementation

Or a way to bounce out of the eval every x seconds/operations to check
for user input. May I take it that you are saying that once an eval is
started, it's impossible to break escape with a setTimeout or such?
This is the way it seemed to me but I am no expert so I thought I
would ask here.

I could, for example, solve this problem by writing a javascript
interpreter in javascript, then executing the user's code in my
interpreter, which checks for a user interrupt before each operation
and stops if there has been one. (right?) So this problem is not
impossible, but it is a big pain. It also does not intrinsically
require either threads or a solution to the halting problem.

ISTM the developers of Google Caja have not even realized that code as you
suggest would qualify as an attack vector, so it would seem unlikely that
they have succeeded in implementing a counter-measure against it in their code.

Whether or not they have considered it as an attack vector is
irrelevant to the question of whether I could use their code to eval
my user's code in such a way that I could stop it.

-Bill

[Thomas 'PointedEars' Lahn]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

Bill Mill wrote:

On Apr 23, 1:57 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.dewrote:

>Bill Mill wrote:

>>[...] Thomas 'PointedEars' Lahn [...] wrote:
>>>Bill Mill wrote:
>>>>I want to have a user able to eval code in a text box. However,
>>>>if he accidentally types "while(1) { i=0; }" and hits "run", I
>>>>also want him to be able to hit a stop button such that his
>>>>browser does not go into an infinite, soul-crushing,
>>>>interface-locking loop. The stop button would not need to be
>>>>instantly responsive, but of course the more responsive the
>>>>better. Short of writing a javascript-in-javascript interpreter,
>>>>is there any way to do so?
>>>No. ECMAScript implementations so far are single-threaded, and
>>>there is yet an algorithm to be written for a universal solution of
>>> the Halting Problem. http://en.wikipedia.org/wiki/Halting_problem
>>Thanks, I know just what that is, and I'm not asking for a solution
>>to it. Allowing a user to stop an eval is not equivalent to
>>determining prior to the eval whether or not it will ever complete.

>But you will need a threaded implementation

>
Or a way to bounce out of the eval every x seconds/operations to check
for user input. May I take it that you are saying that once an eval is
started, it's impossible to break escape with a setTimeout or such?

(Probably you meant "eval" instead of "escape".) Yes, that is correct.

This is the way it seemed to me but I am no expert so I thought I would
ask here.
>
I could, for example, solve this problem by writing a javascript
interpreter in javascript, then executing the user's code in my
interpreter, which checks for a user interrupt before each
operation and stops if there has been one. (right?)

No. For your "javascript " interpreter written in "javascript ", there are
not operations but statements to consider (for example, the `while'
statement). And your "javascript " interpreter would run single-threaded,
in a single-threaded runtime environment:

User agent
|
'- built-in ECMAScript-compliant script engine
|
'- your "javascript " interpreter
|
'- the user's code

AFAICS, the only possibility that remains is that the user agent recognizes
that the ECMAScript-compliant engine has not returned a status result within
a defined interval and then presents the user with a choice to stop
execution, i.e. kill the engine's thread. And ISTM that is exactly what
Mozilla/5.0 does.

So this problem is not impossible,

Correct, the solution to it is.

but it is a big pain. It also does not intrinsically require either
threads or a solution to the halting problem.

I don't think so.

>ISTM the developers of Google Caja have not even realized that code as
>you suggest would qualify as an attack vector, so it would seem
>unlikely that they have succeeded in implementing a counter-measure
>against it in their code.

>
Whether or not they have considered it as an attack vector is irrelevant
to the question of whether I could use their code to eval my user's code
in such a way that I could stop it.

(Isn't it a bit presumptuous of you to make such sincere statements but
calling yourself a non-expert?)

Their code would run in a single-threaded environment as well. Unless they
have found a counter-measure to the attack vector of blocking code, it is
unlikely that their code is going to solve your problem. And for that they
would need to have recognized your problem as being one first.


PointedEars
--
var bugRiddenCrashP ronePieceOfJunk = (
navigator.userA gent.indexOf('M SIE 5') != -1
&& navigator.userA gent.indexOf('M ac') != -1
) // Plone, register_functi on.js:16

[Joost Diepenmaat]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

Bill Mill <bill.mill@gmai l.comwrites:

Or a way to bounce out of the eval every x seconds/operations to check
for user input. May I take it that you are saying that once an eval is
started, it's impossible to break escape with a setTimeout or such?

setTimeout & similar functions don't allow that, because of the
single-threadedness. By the way, it's not a rule that javascript
implementations themselves should be single-threaded, but the core specs
don't specify any mechanisms that would make multi-threading
manageable - IOW it may be possible to create a multi-threaded
javascript implementation, but it would need at least specify the
lower-level implications of multi-threading, and provide some
locking/synchronization primitives in addition to the standard.

I could, for example, solve this problem by writing a javascript
interpreter in javascript, then executing the user's code in my
interpreter, which checks for a user interrupt before each operation
and stops if there has been one. (right?)

Yes you could. If your interpreter is fine-grained enough it's perfectly
possible to halt it after some amount of time. A JS interpreter
implemented like that in javascript would probably be pretty slow,
though. You'd also have to take care to provide interruptable variants
of of all host-provided functions that could take a long time or
possibly not return at all (things like alert(), or a synchronized
XMLHttpRequest for example).

So this problem is not impossible, but it is a big pain. It also does
not intrinsically require either threads or a solution to the halting
problem.

Correct.

--
Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/

[Bill Mill]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

>

So this problem is not impossible, but it is a big pain. It also does
not intrinsically require either threads or a solution to the halting
problem.

>
Correct.
>
--
Joost Diepenmaat | blog:http://joost.zeekat.nl/| work:http://zeekat.nl/

Thank you very much Joost.

-Bill

[Dr J R Stockton]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

In comp.lang.javas cript message <480ee566$0$143 59$e4fe514c@new s.xs4all.n
l>, Wed, 23 Apr 2008 09:29:48, Erwin Moller <Since_humans_r ead_this_I_am
_spammed_too_mu ch@spamyourself .composted:

>
>My Firefox notices long running scripts and offers to abort them after
>a while.
>What browser are you using?

My Opera does not, which was useful today when I had code to check
several Easter algorithms for 5700000 years, at about 2000 years per
second.

My IE6 would allow longer and longer intervals between successive
warnings, but my IE7 warns every 31000 years or so - tiresome.

It would be nice to have a list of whether/how that can be changed for
various browsers. Obviously it ought not (by default) to be possible to
do it be code, but it would be good for a programmer to be able to ask a
user to make the change.

It would also be nice if the warning box had a control to disable the
feature for the current action or page.

--
(c) John Stockton, nr London, UK. ?@merlyn.demon. co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demo n.co.uk/- FAQqish topics, acronyms & links;
Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc.
No Encoding. Quotes before replies. Snip well. Write clearly. Don't Mail News.

[slebetman]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On Apr 24, 3:44 am, Dr J R Stockton <j...@merlyn.de mon.co.ukwrote:

In comp.lang.javas cript message <480ee566$0$143 59$e4fe5...@new s.xs4all.n
l>, Wed, 23 Apr 2008 09:29:48, Erwin Moller <Since_humans_r ead_this_I_am
_spammed_too_m. ..@spamyourself .composted:
>
>
>

My Firefox notices long running scripts and offers to abort them after
a while.
What browser are you using?

>
My Opera does not, which was useful today when I had code to check
several Easter algorithms for 5700000 years, at about 2000 years per
second.
>
My IE6 would allow longer and longer intervals between successive
warnings, but my IE7 warns every 31000 years or so - tiresome.
>
It would be nice to have a list of whether/how that can be changed for
various browsers.

For Firefox you can change dom.max_script_ run_time (defaults to 10
seconds) with about:config

[Jeremy J Starcher]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On Wed, 23 Apr 2008 12:00:16 -0700, Bill Mill wrote:

I could, for example, solve this problem by writing a javascript
interpreter in javascript, then executing the user's code in my
interpreter, which checks for a user interrupt before each operation and
stops if there has been one. (right?) So this problem is not impossible,
but it is a big pain. It also does not intrinsically require either
threads or a solution to the halting problem.

I wrote a BASIC compiler and VM in Javascript (GPLed) once. To say it
was a big pain would be an understatement and performance ... suffered.

Does, however, make a nice test of UA's Javascript speed. ;)

[dhtml]

Re: Avoiding an Infinite Loop in Arbitrary eval(user_code)

On Apr 23, 10:21 am, Bill Mill <bill.m...@gmai l.comwrote:

On Apr 23, 1:07 pm, Thomas 'PointedEars' Lahn <PointedE...@we b.de>
wrote:
>

Bill Mill wrote:

I want to have a user able to eval code in a text box. However, if he
accidentally types "while(1) { i=0; }" and hits "run", I also want him
to be able to hit a stop button such that his browser does not go into
an infinite, soul-crushing, interface-locking loop. The stop button
would not need to be instantly responsive, but of course the more
responsive the better.

>

Short of writing a javascript-in-javascript interpreter, is there any
way to do so?

>

No.  ECMAScript implementations so far are single-threaded, and there is yet
an algorithm to be written for a universal solution of the Halting Problem.

>

http://en.wikipedia.org/wiki/Halting_problem

>
Thanks, I know just what that is, and I'm not asking for a solution to
it. Allowing a user to stop an eval is not equivalent to determining
prior to the eval whether or not it will ever complete.
>
>
>

You will have to rely on the user's user agent to recognize a not-responding
script, and provide the user with such a dialog window, as Gecko-based UAs
(e.g. Mozilla Firefox) do.

>
I can't rely on this, since I would like to allow the user to write
scripts that take a while to run. Thus, he's likely to disable this
dialog for the page.
>
>
>

Does Caja make this sort of thing possible?

>

I don't think so:

>

http://code.google.com/p/google-caja/wiki/AttackVectors

>
How is that relevant to what I asked? I've read the Caja website, as
well as the PDF describing the system, and I'm still not clear on
whether it can or not.
>
>
>

Please be more verbose next time.

>
what more would you like to know?
>
>
>

Will I need to restrict myself toGears+threads to do this?

>

Never heard of those.

>
I meant that I might be able to use GoogleGears' threads to achieve
what I'm looking for.
>

I thought this was strange.

What made you think Gears would solve the problem? I think there's a
tendency -- and this might not apply to you -- but there's a tendency
for people to want a silver bullet solution. I think that's part of
the lure of the god object anti-pattern.

The JavaScript code in Gears is actually pretty bad and full of bugs.

-Bill Mill