|
Hi Folks, Does your XML language [1] contain polymorphic elements? Recursive content? Open content? Co-constraints? Internal references? How do those features impact the complexity [2] of your language?
Clearly if a feature elevates the language's complexity to "recursively enumerable" then you will want to avoid that feature.
Recall that as a language increases in complexity its attack surface increases. For a recursively enumerable language "no amount of programmer or QA effort can expose a comprehensive selection
of the language's exploitable vulnerabilities" [3]. In other words, your language and its processing applications cannot be secured. I am compiling a list of features that may be used in XML languages. The below is a start at a list. I seek your additions to the list.
Once I have compiled a comprehensive list, then I will start assessing the complexity-impact of each feature. Would you like to help with this?
XML Language Features 1. Polymorphism – an element is polymorphic if it can be substituted by other elements or if its content can be substituted by other content. For example, this <Publication> element is polymorphic:
in <Bookstore> each <Publication> may be substituted by <Book> or <Magazine>. 2. Recursion – the content of an element is recursive. For example, this <section> element is recursive: each <section> contains a <title> followed by an optional <section>. 3. Open content – the content of an element is arbitrary content. 4. Internal references – the value of an IDREF attribute must match the value of an ID attribute. 5. Co-constraints – the language imposes a dependency between two or more sets of elements. Examples: (a) Require the number of occurrences of element A equal the number of occurrences of element
B. (b) Require the number of occurrences of elements A, B, and C all be equal. 6. Exponentially expanding user-defined entities – the content of an element contains a reference to an exponentially expanding user-defined entity.
What other features could an XML language have that might impact its complexity? /Roger [1] An XML language is the set of XML instance documents that are acceptable. For example, you may define a Bookstore XML language as the set of all instance documents that have Store as the
root element and its content is zero or more Book elements. Here is a member of the language: <Store> That document has a Store element containing two Book elements. An XML document that contains three (or four or five or …) Book elements is also a member of the language. A document that contains,
say, cellphone elements is not a member of the language. [2] Complexity of languages: regular < deterministic context-free < non-deterministic context-free < recursive < recursively enumerable [3]
http://www.cs.dartmouth.edu/~sergey/langsec/papers/Sassaman.pdf |