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" (pdf), 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. I'd love to be proven wrong and find that there's a rich theory that I'm over-looking, if so let me know in the comments.