PP5: A Theory of Templating Languages

Lisa Dusseault <lisa@osafoundation.org> Fri, 11 January 2008 01:22 UTC

Return-path: <discuss-bounces@apps.ietf.org>
Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1JD8bY-0007du-SZ; Thu, 10 Jan 2008 20:22:40 -0500
Received: from discuss by megatron.ietf.org with local (Exim 4.43) id 1JD8bW-0007cJ-U2 for discuss-confirm+ok@megatron.ietf.org; Thu, 10 Jan 2008 20:22:38 -0500
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1JD8bW-0007cB-KH for discuss@apps.ietf.org; Thu, 10 Jan 2008 20:22:38 -0500
Received: from laweleka.osafoundation.org ([204.152.186.98]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1JD8bV-0002we-JS for discuss@apps.ietf.org; Thu, 10 Jan 2008 20:22:38 -0500
Received: from localhost (laweleka.osafoundation.org [127.0.0.1]) by laweleka.osafoundation.org (Postfix) with ESMTP id 801FC14220C for <discuss@apps.ietf.org>; Thu, 10 Jan 2008 17:22:39 -0800 (PST)
X-Virus-Scanned: by amavisd-new and clamav at osafoundation.org
Received: from laweleka.osafoundation.org ([127.0.0.1]) by localhost (laweleka.osafoundation.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UYEUKQiUaHI8 for <discuss@apps.ietf.org>; Thu, 10 Jan 2008 17:22:34 -0800 (PST)
Received: from [10.1.1.107] (unknown [157.22.41.236]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by laweleka.osafoundation.org (Postfix) with ESMTP id 00D9A142203 for <discuss@apps.ietf.org>; Thu, 10 Jan 2008 17:22:33 -0800 (PST)
Mime-Version: 1.0 (Apple Message framework v752.3)
To: Apps Discuss <discuss@apps.ietf.org>
Message-Id: <328AD3B5-F0E1-46D5-8203-B51EE70C51BF@osafoundation.org>
Content-Type: multipart/alternative; boundary=Apple-Mail-9-516535019
References: <3f1451f50712140820p14e08eberc8799e5a517e81d3@mail.gmail.com>
From: Lisa Dusseault <lisa@osafoundation.org>
Subject: PP5: A Theory of Templating Languages
Date: Thu, 10 Jan 2008 17:22:30 -0800
X-Mailer: Apple Mail (2.752.3)
X-Spam-Score: -4.0 (----)
X-Scan-Signature: e367d58950869b6582535ddf5a673488
X-BeenThere: discuss@apps.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: general discussion of application-layer protocols <discuss.apps.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/discuss>, <mailto:discuss-request@apps.ietf.org?subject=unsubscribe>
List-Post: <mailto:discuss@apps.ietf.org>
List-Help: <mailto:discuss-request@apps.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/discuss>, <mailto:discuss-request@apps.ietf.org?subject=subscribe>
Errors-To: discuss-bounces@apps.ietf.org


Begin forwarded message:

> From: "Joe Gregorio" <joe@bitworking.org>
> Date: December 14, 2007 8:20:17 AM PST
> To: "Lisa Dusseault" <lisa@osafoundation.org>rg>, Chris.Newman@sun.com
> 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.