OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Re: [xml-dev] RE: XML parsers use what computational power?

I think we had this conversation at least a dozen years ago, in 
conversation about the million-laughs attack.

As attack surface area goes, entity resolution isn't exactly drastic. 
It's not hard to apply a minor amount of defensive programming to halt 
this attack.  It's also an extremely dull attack, a denial of service at 

While I recognize that you are compiling rules for an extremely 
conservative audience, I often worry that they and their experts fear 
their own shadows most of all.  Perhaps they should stick to plain 
unformatted text 'processed' by humans with security clearances?


On 4/10/13 5:43 AM, Costello, Roger L. wrote:
> Hi Folks,
> Resolving these entities:
> <!ENTITY ha1 "ha"> <!ENTITY ha2 "&ha1;&ha1;"> ... <!ENTITY ha128
> "&ha127;&ha127;">
> requires an amount of memory that is exponential to the number of
> entities.
> Therefore an XML parser requires more computational power than a
> linear bounded automata [1]. Furthermore:
> Linear bounded automata are acceptors for the class of
> context-sensitive languages. [1]
> Therefore XML is more powerful than a context-sensitive language.
> Experts recommend [2] that an input language not require more
> computational power than a deterministic pushdown automata. The XML
> language requires much more computational power than this.
> Therefore, XML as an input language is too complex. It requires too
> much computational power. It's attack surface is too large (as
> evidenced by the dozens (hundreds) of vulnerabilities exposed in the
> last decade).
> /Roger
> [1] Linear automata:
> http://en.wikipedia.org/wiki/Linear_bounded_automaton
> [2] Input languages should not require a computational power greater
> than D-PDA:
> http://www.cs.dartmouth.edu/~sergey/langsec/papers/Sassaman.pdf
> _______________________________________________________________________
>  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

Simon St.Laurent

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS