Re: Object tag crashes Internet Explorer 4.0

[paulle () MICROSOFT COM (Paul Leach)]

> -----Original Message-----
> From: Pavel Kankovsky [mailto:peak () KERBEROS TROJA MFF CUNI CZ]
> Sent: Wednesday, August 05, 1998 2:29 AM
> To: BUGTRAQ () NETSPACE ORG
> Subject: Re: Object tag crashes Internet Explorer 4.0
>
>
> 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.

For the specific example of values of the "data" field in the object tag,
you're right.

However, web pages can contain more complex constructs than that, constructs
that can make them into (in the general case) full fledged, Turing complete,
programs.

As many people have pointed out to me as if I were an idiot, in many cases,
whether these halt is also determinable by examining the page. I knew that.
However, it is not possible in general to so determine -- and it was to the
more general problem that I was referring, not the specific example. That's
the context I intended to set by the phrase "the possibility of infinite
loops and infinite recursion in HTML has been discussed before". Judged by
the reactions, that didn't come across. There was also controversy over
whether HTML, strictly defined, was Turing complete. I will plead guilty to
not knowing that -- HTML 1.0 was surely not Turing complete, but I don't
know exactly what specification introduces the ability to script, and
whether it was "HTML n.0" or DHTML, or what.

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

We do. It's the depth of the stack. The actual objection of many
correspondents, after their joy in pointing out my incompetence to me fades,
seems to be the behavior of IE when the stack overflows. But no one has been
very clear about what it is in the cases they've seen (if they've indeed
seen any); when IE 4 has died on me (all pre-SP1 of course :-), it restarted
and about all I lost was the history list that drives the "back" button. If
it doesn't restart as clean as that in all cases of stack overflow, then
that should be looked at, and reports would be appreciated, especially if it
can be reporduced easily.

Paul