[langsec-discuss] How do i prove a Domain Specific Language is of particular formal grammar

Jon Callas jon at callas.org
Thu Sep 6 16:13:00 UTC 2012

On Sep 6, 2012, at 12:53 AM, Krishna Sashank O V (MS2011006) wrote:

> Hi ,
> I have come across this interesting paper on langsec, that talks about "Security applications of formal language theory" , 
> At the page number 8 states that HTTP is context-sensitive , javascript is non deterministic context-free etc .
> Now, we have a domain specific language that is XML based i.e SAML ( Secure Assertion Mark Up Language )
> http://en.wikipedia.org/wiki/Security_Assertion_Markup_Language
> I would like to analyze and prove the class of chomsky hierarchy of languages it falls under , like whether it is regular, deterministic context-free , etc ?
> How do I start about this exercise , are there any references of similar exercises ? any directions ?

Here's some guidance, which is not a proof. I might even be incomplete in this, which is what I mean by *guidance*.

If it has parentheses or equivalent, it's context-sensitive. Any SGML derivative is context-sensitive, as are S-expressions. (Think of *ML as S-expressions with colored parens.) If you need a stack to parse it, it's context-sensitive. Or worse, to any of those. It is highly likely that if you can't know an object's size in advance, then it's almost certainly context-sensitive. That's why TLV (tag-length-value) records are desirable; they simplify. Note however, that TLVs can be embedded in a complex language.

If it's got control structures, it's at least context sensitive. If it has backwards gotos in any form, it's Turing-complete. Loops, recursion, etc. are backwards gotos. If-then-else is a forward goto.

I am no longer a SAML expert, but my bet is that it's only context-sensitive because it's S-expressions, and I don't believe it has loops etc. Optional arguments are only context sensitive (they're equivalent to if-then-else or more fundamentally, a forward goto).


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.langsec.org/pipermail/langsec-discuss/attachments/20120906/da8b29ab/attachment.html>

More information about the langsec-discuss mailing list