W3C home > Mailing lists > Public > www-voice@w3.org > January to March 2013

RE: Guarding against infinite loops and other poorly-designed machines

From: Michael Bodell <bodell@247-inc.com>
Date: Thu, 7 Feb 2013 02:27:52 +0000
To: Gavin Kistner <phrogz@me.com>, "www-voice@w3.org" <www-voice@w3.org>, "www-voice@w3.org" <www-voice@w3.org>
CC: Chris Nuernberger <chrisn@nvidia.com>
Message-ID: <99155A875ACA0F41BDE9B4DA3E307426119A9717@HKNPRD0310MB350.apcprd03.prod.outlook.com>
My personal take is that yes there is a difference between a state machine that hanks and one that tries for an illegal configuration.  While it is reasonable for an interpreter implementation to put limits on this sort of thing (infinite loops), it is a legitimate state machine despite the fact that it may never terminate.  If you have a time based counter, for instance, that adds one each time through the state machine loop while sleeping for a second it might be reasonable that this machine never terminates but just keeps the counter growing ever bigger (seconds since the epoch if you will).  In contrast, a state machine that tries to go to an illegal configuration (in both states a and b where a and b are leaf states in the same parallel sub-region) is not a legitimate state machine.

Other web programming standards that I'm familiar with (primarily VXML and HTML) also don't limit what legitimate programs can do (infinite JS loops and the like), partially I think in the same spirit, partially because no one wants to have to solve the halting problem to be compliant.  But browsers and OS allow certain mechanisms to stop (or offer a dialog to stop) when content is consuming too many resources or has turned into a "Not responding" situation.  I think that is the right model to use.

From: Gavin Kistner [mailto:phrogz@me.com]
Sent: Wednesday, February 06, 2013 2:58 PM
To: www-voice@w3.org; www-voice@w3.org
Cc: Chris Nuernberger
Subject: Guarding against infinite loops and other poorly-designed machines

Consider this terrible machine:

<scxml xmlns="http://www.w3.org/2005/07/scxml" version="1.0">
  <state id="a">
    <onentry><raise event="e"/></onentry>
    <transition event="e" target="a1" />
    <state id="a1"/>
  </state>
</scxml>

Because the transition defaults to external, the interpreter exits state 'a' and re-enters it each time the transition runs. This causes a new event to be placed on the internal queue. As a result, the mainEventLoop gets stuck in the "while running and not stable" internal queue processing.

My own implementation happens to place a counter on this loop: "while running and not stable and iterations < MAX_ITERATIONS".

Is it the official position of the group that there are a variety of ways to write a dumb state machine, and neither the standard algorithm nor the validity constraints will attempt to prevent them?

Having written it, this seems like a question with an obvious answer. Of course we aren't going to guard against someone writing <script>while(true) explode()</script>

However, the "valid value" for the "target" attribute of transitions, along with section 3.11, already go to some lengths to explicitly declare as invalid any set of targets that would put the machine in an invalid configuration. If we are not going to guard against one form of broken/silly state machine, why do we try to guard against another? Is it considered more acceptable to have an interpreter that may hang (given a broken input) versus an interpreter that enters an illegal configuration (given a different broken input)?
Received on Thursday, 7 February 2013 02:28:26 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 7 February 2013 02:28:32 GMT