PP5: A Theory of Templating Languages

[Lisa Dusseault <[e-mail]>]

Begin forwarded message:

> From: "Joe Gregorio" <[e-mail]>
> Date: December 14, 2007 8:20:17 AM PST
> To: "Lisa Dusseault" <[e-mail]>, [e-mail]
> Subject: Re: Position papers due Dec 14
>
> Here is my brief position paper:
>
> Working on the URI Templating specification has made me realize that
> there is a pretty substantial hole
> in computer science theory: a lack of a theory of templating
> languages. For example, the current version of
> URI Templates is not Turing-complete, which excludes a whole bunch of
> possible attacks. In the specification I state:
>
>     On the balance, the template processing is not Turing complete,
> thus avoiding a number of
>      security issues, ala the billion-laughs attack of XML DTDs.
>
> I was rightly called out on this on the W3C URI mailing list:
>
>     This reads a little odd, as not being Turing-complete is not  
> sufficient
>     to avoid the attack.  (And DTDs are not Turing-complete either.)
>
> The criticism is correct. The problem is that I don't know of any
> finer grained levels of classifications
> of templating languages than Turing/non-Turing, and not only for
> security reasons, but for general capabilities.
>
> For example, if there were classes of templating languages, I could
> say that URI Templates fell into 'class X', and
> if that class had a known set of limitations and capabilities then I
> could say that URI Templates thus had those
> limitations and capabilities. The weakness to the billion laughs
> attack comes from two facets of DTD usage, the
> first being that templates can be defined in terms of other templates,
> and the second is that the depth of template
> definition, in terms of other templates, isn't limited. But the
> converse isn't true, that is, I don't have a general
> theory of templating to lean on that says since URI Template
> expansions are never defined in terms of other
> expansions then URI Templates are immune to such resource  
> exhaustion attacks.
>
> I did find one paper that makes a start at such work, "Enforcing
> Strict Model-View Separation in Template Engines",
> but the theory is a little weak and it focuses on the nebulous idea of
> separation of model and view, as opposed to
> a classification of capabilities and limitations. In addition there
> seems to not be a lot of work on sub-turing languages,
> and most interestingly the contemporary work that is being done is on
> Membrane Computing Systems, which
> is in turn motivated by studying cell evolutions and chemical
> reactions. I am bringing this topic forward in the
> hopes of learning of other pointers into the literature, and also
> learning if this problem applies to others
> in the Apps area, of if I'm all alone with this problem in URI  
> Templates.