Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Javascript > Avoiding an Infinite Loop in Arbitrary eval(user_code)

Reply
Thread Tools

Avoiding an Infinite Loop in Arbitrary eval(user_code)

 
 
Bill Mill
Guest
Posts: n/a
 
      04-23-2008
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
Erwin Moller
Guest
Posts: n/a
 
      04-23-2008
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
> (E-Mail Removed)

 
Reply With Quote
 
 
 
 
Captain Paralytic
Guest
Posts: n/a
 
      04-23-2008
On 23 Apr, 07:29, Erwin Moller
<Since_humans_read_this_I_am_spammed_too_m...@spam yourself.com> >
> 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?
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      04-23-2008
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
 
Reply With Quote
 
Bill Mill
Guest
Posts: n/a
 
      04-23-2008
On Apr 23, 1:07*pm, Thomas 'PointedEars' Lahn <(E-Mail Removed)>
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
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      04-23-2008
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 an algorithm to solve the
Halting Problem in order to solve your problem. So, ...

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


.... tough luck.

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


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.

>> Please be more verbose next time.

>
> what more would you like to know?


Regarding the name of "Caja", you could have posted the URL to Google Caja,
so that someone who is not familiar with client-side Google code (as it is
recommended against around here because of its lack of quality) would know
what you mean without using, well, Google to find it out.

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


See above.


PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
 
Reply With Quote
 
Bill Mill
Guest
Posts: n/a
 
      04-23-2008
On Apr 23, 1:57*pm, Thomas 'PointedEars' Lahn <(E-Mail Removed)>
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
 
Reply With Quote
 
Thomas 'PointedEars' Lahn
Guest
Posts: n/a
 
      04-23-2008
Bill Mill wrote:
> On Apr 23, 1:57 pm, Thomas 'PointedEars' Lahn <(E-Mail Removed)> 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
>>>> 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 bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16
 
Reply With Quote
 
Dr J R Stockton
Guest
Posts: n/a
 
      04-23-2008
In comp.lang.javascript message <480ee566$0$14359$(E-Mail Removed)4all.n
l>, Wed, 23 Apr 2008 09:29:48, Erwin Moller <Since_humans_read_this_I_am
(E-Mail Removed)> posted:
>
>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.demon.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.
 
Reply With Quote
 
Joost Diepenmaat
Guest
Posts: n/a
 
      04-23-2008
Bill Mill <(E-Mail Removed)> writes:

> 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/
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Triple nested loop python (While loop insde of for loop inside ofwhile loop) Isaac Won Python 9 03-04-2013 10:08 AM
New python module to simulate arbitrary fixed and infinite precisionbinary floating point Rob Clewley Python 2 08-11-2008 05:10 PM
avoiding arbitrary local variable names Roedy Green Java 9 12-20-2007 01:35 AM
loop thru a STL list causes an infinite loop Allerdyce.John@gmail.com C++ 5 01-31-2006 03:21 PM
calling an arbitrary function w/ arbitrary arguments Honestmath C++ 5 12-13-2004 06:18 AM



Advertisments