Re: [xml-dev] RE: XML parsers use what computational power?

[David Sheets <kosmo.zb@gmail.com>]

On Tue, Apr 9, 2013 at 9:11 PM, Costello, Roger L. <costello@mitre.org> wrote:
> Bjoern wrote about entity resolution:
>
>> Whatever you pop() here from the stack would
>> be lost afterwards. If you need 'ha1', then you
>> have to forget 'ha2' to retrieve it. And all other
>> state you keep on the stack.
>
> Wow!
>
> As I understand it, you have just explained why entity resolution necessitates an XML parser be a Turing machine!
>
> This is big news (at least for me):
>
>     To implement a parser for the XML specification
>     requires the parser be Turing-complete.

I don't think this is true... an XML parser must be more powerful than
a pure stack machine HOWEVER I don't see how one could encode, e.g.,
SK calculus in XML's entity resolution semantics.

Can you set XML parsers into infinite loops via entity resolution?
Afaik, entities cannot be self-referential and support no
parameterization...

dS

> The ramifications of this are huge, particularly with regard to security and XML's attack surface.
>
> /Roger
>
> -----Original Message-----
> From: Bjoern Hoehrmann [mailto:derhoermi@gmx.net]
> Sent: Tuesday, April 09, 2013 1:53 PM
> To: Costello, Roger L.
> Cc: xml-dev@lists.xml.org
> Subject: Re: [xml-dev] RE: XML parsers use what computational power?
>
> * Costello, Roger L. wrote:
>>Can XML parsers be implemented using exclusively these two tools:
>>
>>1. A finite state machine (FSM)
>>2. A stack
>
> You seem to be missing that in the computational model the stack is all
> the memory you have. If you add a second stack, so you could e.g. pop()
> items from one and push() them to the other, you have a turing machine.
>
> Take your example:
>
>>Consider these two ENTITY declarations in the XML document's internal DTD subset:
>>
>><!ENTITY ha1 "ha">
>><!ENTITY ha2 "&ha1;&ha1;">
>>
>>Each entity name and replacement value could be stored in the stack.
>>
>>When the entity name is encountered within the XML document:
>>
>>    &ha2;
>>
>>the parser could pop the stack until it encounters the name ha2 and get its
>>replacement text, which involves getting ha1 and its replacement text. So I
>>could imagine that entity resolution could be implemented using a FSM plus
>>stack.
>
> Whatever you pop() here from the stack would be lost afterwards. If you
> need 'ha1', then you have to forget 'ha2' to retrieve it. And all other
> state you keep on the stack.
> --
> Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
> Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
> 25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/
>
> _______________________________________________________________________
>
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
>
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
> subscribe: xml-dev-subscribe@lists.xml.org
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>