Re: Object tag crashes Internet Explorer 4.0

[peak () kerberos troja mff cuni cz (Pavel Kankovsky)]

On Tue, 4 Aug 1998, Paul Leach wrote:

> The possibility of infinite loops and infinite recursion in HTML has been
> discussed on the lists before. Trying to detect and prevent them is an
> instance of the "Turing machine halting" problem, and it is well known among
> computer scientists to be impossible.

No, it is an instance of "directed graph search halting" problem.

The programs can always detect a finite loop because it has found the loop
iff the current object name (URL) is already present on the stack.
(Assuming your computer has enough memory to remember it.) The only way to
cause infinite recursion is to create an "infinite loop" of names. Natural
numbers generate a simple example of such a "loop." Object N includes
object N+1, N+1 includes N+2... et cetera ad infinitum.

Let's assume the natural number N is encoded as the sequence of N "1"'s.
Adding 1 to such a number is as easy as prepending or appending one "1" to
it. A program acting as a filter can do it in O(N) time and O(1) space.
Therefore it is feasible to create a "server" which generates an infinite
chain of objects.

Nevertheless, the defense is trivial: it is always possible to impose an
artificial (perhaps customizable) limit on the depth of recursion, the
number of searched objects or anything else. Or let the user interrupt
the search when his/her patience is over.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"You can't be truly paranoid unless you're sure they have already got you."