W3C

XML Signature Streaming Profile of XPath 1.0

W3C Candidate Recommendation 24 January 2012

This version:
http://www.w3.org/TR/2012/CR-xmldsig-xpath-20120124/
Latest published version:
http://www.w3.org/TR/xmldsig-xpath/
Latest editor's draft:
http://www.w3.org/2008/xmlsec/Drafts/xmldsig-xpath/
Previous version:
http://www.w3.org/TR/2011/WD-xmldsig-xpath-20110421/
Editors:
Pratik Datta, pratik.datta@oracle.com
Frederick Hirsch, frederick.hirsch@nokia.com
Meiko Jensen, Meiko.Jensen@ruhr-uni-bochum.de

Abstract

This document defines a streamable profile of XPath 1.0 suitable for use with XML Signature 2.0.

Status of This Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is a W3C Candidate Recommendation Working Draft of "XML Signature Streaming Profile of XPath 1.0". The W3C publishes a Candidate Recommendation to indicate that the document is believed to be stable and to encourage implementation by the developer community. The XML Security Working Group expects to request that the Director advance this document to Proposed Recommendation once the Working Group has verified two interoperable implementations of the Candidate Recommendation. The XML Security Working Group does not have an estimate of when this will be achieved. There is no preliminary interop or implementation report.

No features have been marked as "at risk".

Changes since the previous publication include formatting, correction of spelling errors and an update of the references. A diff-marked version of the specification that highlights changes against the previous version is available.

This document was originally derived from material in an earlier publication of XML Signature 2.0, see http://www.w3.org/TR/2010/WD-xmldsig-core2-20100304/#sec-XPath-2.0.

This document was published by the XML Security Working Group as a Candidate Recommendation. This document is intended to become a W3C Recommendation. If you wish to make comments regarding this document, please send them to public-xmlsec@w3.org (subscribe, archives). W3C publishes a Candidate Recommendation to indicate that the document is believed to be stable and to encourage implementation by the developer community. This Candidate Recommendation is expected to advance to Proposed Recommendation no earlier than 12 April 2012. All feedback is welcome.

Publication as a Candidate Recommendation does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1. Introduction

This document specifies a streamable profile of XPath 1.0 [XPATH] for use in XML Signature 2.0 [XMLDSIG-CORE2]. It is a proper subset of XPath 1.0, i.e. any XPath expression that is part of this subset is also a valid XPath 1.0 expression, and when evaluated using the streaming algorithm mentioned here, produces exactly the same results as those produced by a regular DOM based XPath engine. Although this XPath subset has been designed in the context of XML Signature 2.0, it is a general purpose subset and can be used in other contexts too.

The motivation for introducing this profile is outlined here.

XML Signature lets one sign parts of the XML document. In 1.x version of XML Signature [XMLDSIG-CORE1], the part to be signed can be identified in one of the following ways:

  1. ID based references This is the simplest and the most popular mechanism. An ID attribute is added to the element to be signed, and the signature refers to this element by this ID. However this approach has certain problems:

    1. the document needs to be changed to add the id, this may not be possible in all situations, especially if the schema does not allow an ID attribute for that element.
    2. ID based references are subject to wrapping attacks, these attacks can be avoided by using XPath expressions.
    3. this mechanism can only sign complete subtrees, i.e. parts of a subtree cannot be excluded.

  2. XPath Filter Transform This is the original XPath mechanism in XML Signature 1.0. It solves the three problems mentioned above, but it introduces new problems:

    1. it is extremely inefficient, because the XPath needs to be evaluated for every node of the document.
    2. the XPath is not a "normal" XPath, because it has to be of the form of a boolean expression that is evaluated with every node as the context node. For example the XPath //chapter/ (i.e. all chapter) descendants has to be expressed as ancestor-or-self::chapter (i.e. a boolean expression which evaluates to true for a node, if that node has an ancestor call chapter). Not only is this very hard to understand , but also some XPaths cannot be expressed like this at all. For example it is not possible to express /book/chapter[3] in this model.

  3. XPath Filter 2 Transform This was introduced to solve the problems in above problems [XMLDSIG-XPATH-FILTER2]. However it has a few problems of its own:

    1. although there are implementations of it, it was not popular because it is marked as optional to implement.
    2. it is not streamable in general, although some limited set may be streamable. Note ID based references are streamable.

  4. XPointer At the time the XML Signature 1.0 was written, XPointer supported a full XPath model, but it was still under development. Later on it split up into multiple specs, the full XPath support remained as a Working draft [XPTR-XPOINTER], and only the XPointer element scheme [XPTR-ELEMENT] became an official W3C Recommendation. The XPointer element scheme does not support generic XPaths, it only allows basic addressing of XML elements e.g. element(/1/2) identifies the 2nd child of the root element.

    1. there are almost no implementations of XPointer with XPath, in fact the XML Signature specification actively discourages it.
    2. this mechanism can only sign complete subtrees, with no exclusions.

XML Signature 2.0, retains all 1.x mechanisms for backwards compatibility, but it introduces a new mechanism <ds2:Selection> which can be viewed as a very simplified form of XPath Filter 2 Transform. It consists of URI which can be used for ID based references and an IncludedXPath and ExcludedXPath for inclusions and exclusions. The result of the selection is subtrees identified by included XPath, minus the subtrees identified by excluded XPath. These IncludedXPath and ExcludedXPath take a profile of XPath, and and it is this profile that this document describes.

This 2.0 selection mechanism, has all the advantages of XPath Filter 2 transform, and additionally it is designed to support streaming. However it does the restrict the kind of selection - only subtrees with one round of subtree exclusion can be selected. This restriction is required for high performance.

2. Streamable

The XPath profile defined in this document is streamable with single-pass pre-order XPath recognition. This means

2.1 Streaming for XML signatures

In the context of XML Signature, streaming is absolutely essential for XML gateways which need to perform XML Signature and Encryption operations for messages on the wire. It is also important for performance sensitive applications; as streaming improves performance by conserving memory, which greatly reduces temporary memory allocation, resulting in far less memory garbage collection.

For XML Signatures it is not only the XPath expressions that need to be evaluated in streaming, but the rest of the signature processing as well (e.g. canonicalization and digesting also need to be performed in streaming mode). For example a streaming Signature processor could compute Reference digests for 2.0 Signatures as follows:

For simplicity the above steps make a simplifying assumption that all the <Reference>s have a <Selection> of Type="http://www.w3.org/2010/xmldsig2#xml", and each of the <Selection> URIs are same document references. If the <Selection> URIs refer to external resource, the URI should be dereferenced to fetch the external XML document, and the XPaths be evaluated on this external document, instead of the current document.

2.2 Limitations with one-pass streaming

Note that it is not always possible to apply or verify XML Signatures in a one-pass streaming fashion. For instance, the verification of an enveloped signature requires an XPath for selection that matches an element that is located prior to the XML Signature itself (in document order). Hence, on signature verification, the selected elements are processed by the streaming parser before the selection XPath itself gets parsed. Example:

<Document>

  <DataBlock1 />

  <Signature xmlns="http://www.w3.org/2000/09/xmldsig#">
    <SignedInfo> 
      [...]
      <Reference>
        <Transforms>
          <Transform Algorithm="http://www.w3.org/2010/xmldsig2#transform">
            <dsig2:Selection xmlns:dsig2="http://www.w3.org/2010/xmldsig2#"
                 type="http://www.w3.org/2010/xmldsig2#xml"  URI="" />
            [...]
          </Transform>
        </Transforms>
        [...]
      </Reference>
    </SignedInfo>
    [...]
  </Signature>  

  <DataBlock2 />

</Document>

As can be seen, the XML Signature selects the whole document, hence all XML elements therein must be processed on signature verification. However, when parsing this document using a streaming approach, the verifying application might not know in advance which parts of the document are protected by the XML Signature. Hence, it will start parsing the document to extract the XPath expressions used for selection, but once it encounters that information, all the elements processed before have already been processed and dismissed (such as the <Document> and <DataBlock1> elements). Thus, these elements have not been digested, and hence there is no way to verify such an XML Signature in a one-pass streaming fashion.

Note that this impossibility of one-pass streaming is not only affecting enveloping signatures. For instance, an XML Signature verification with a selection of

<dsig2:Selection type="http://www.w3.org/2010/xmldsig2#xml"
   xmlns:dsig2="http://www.w3.org/2010/xmldsig2#" URI="" >
   <dsig2:IncludedXPath> //DataBlock1 </dsig2:IncludedXPath>
</dsig2:Selection>
would have also failed due to the same issue, though not being an enveloped signature. The same holds for ID-based selection if the selected elements occur prior to the XML Signature in document order.

These problems can be alleviated by doing the verification in two passes, the first pass merely scanning the document for the <Signature> and the second pass actually evaluating the XPath , canonicalizing and computing the digest. Applications that require pure one pass processing should avoid backward references of any kind.

3. Other requirements

Apart from streaming, the XPath profile also needs to satisfy the following requirements:

4. Definition of the Profile

The following tables define this XPath profile. It is a restricted version of grammar in [XPATH]. Although this grammar appears to deviate from the [XPATH] grammar, it is in fact a proper subset of XPath 1.0, i.e. any XPath expression defined by this grammar is also a valid XPath 1.0 expression and has exactly the same meaning as that defined by the XPath 1.0 specification.

4.1 Top level XPath expression

Grammar

Explanation

XPath ::=
      (AbsoluteLocationPath '|' )* AbsoluteLocationPath
At the top level it is union of absolute locationPaths. e.g. /a/b | //a[@c].

Note: [XPATH] allows a generic Expr in top level, e.g count(/a/b) + string-length(/a) is a perfectly valid XPath 1.0 expression, but these are not allowed in this subset. That's because the whole goal of this subset is to select a set of subtrees, identified by subtree root elements. E.g. the XPath /a/b returns all b child elements of the top level element a. But when this XPath expression is used in an IncludedXPath in XML Signature 2.0, it means not only these b elements, but all b's descendants as well are to be selected for signing.

Relative Location Paths e.g. ../../a are currently not allowed, This is because relative would be most useful in Enveloped signatures in which the signature is contained inside the element to be signed. In such a situation, the relative signature XPath would need to use the ancestor axis to reach the element to be signed, however the ancestor axis is not streamable.

4.2 LocationPaths

Grammar

Explanation

      
AbsoluteLocationPath ::=  
       '/' RelativeLocationPath? 
     | AbbreviatedAbsoluteLocationPath

RelativeLocationPath ::= 
       Step 
     | RelativeLocationPath '/' Step
     | AbbreviatedRelativeLocationPath

AbbreviatedAbsoluteLocationPath ::=  
       '//' RelativeLocationPath

AbbreviatedRelativeLocationPath ::=  
       RelativeLocationPath '//' Step
An absolute location path starts with a slash and has consists of one or many "steps" separated by slash. e.g. /a/b. Double slashes are also allowed, they are short for /descendant-or-self::node()/.
Step ::= 
      AxisSpecifier NameTest RestrictedPredicate*
    | AbbreviatedStep
   

AxisSpecifier ::=  
      AxisName '::' 
    | AbbreviatedAxisSpecifier

AbbreviatedAxisSpecifier ::= 
       '@'?

AxisName ::= 
      'attribute' 
    | 'child' 
    | 'descendant' 
    | 'descendant-or-self' 
    | 'following' 
    | 'following-sibling' 
    | 'self'
    
NameTest ::= 
      '*' 
    | NCName ':' '*' 
    | QName
   
A Step consists of an AxisSpecifier a NameTest, and zero or more predicates. The AxisSpecifier allows only forward axes; all the backward axes ancestor, ancestor-or-self, parent, preceding, preceding-sibling are not streamable, and hence not allowed. The namespace is also not streamable, so it is disallowed too.

Examples of allowed Steps : b[2], *, following::chapter.

This Step is a restricted form of the Step in XPath 1.0 in two aspects. First it only allows a restricted set of Predicate expressions that use attributes only, this restriction is described in the next section; and second it doesn't allow NodeTests. e.g. child::text() is not an allowed Step. This is because some predicates involving text nodes are not streamable.

Consider this Step child::text()[contains(.,"foo")], it selects all child text nodes that contain the string "foo". But as mentioned earlier, text nodes can be extremely long, so a streaming XPath processor will be processing text nodes in chunks. The "foo" substring may be present at the very end of a large text node, so when the streaming XPath processor encounters the "foo", it would have already gotten past all previous chunks of this text node, and with streaming there is no way to rewind back to the beginning of this text node.

Because of this possibility of large text nodes, this XPath subset eliminates all mechanisms of selecting text nodes, either directly or through other mechanisms e.g. string-value.

Although the node() is not allowed, // which is an abbreviation for /descendant-or-self::node()/ is still allowed, because // always need to be followed by Step, so it cannot be used to select text nodes.

4.3 Predicates

Although this XPath subset allows predicates, with all kinds of arithmetic, relational and boolean operators, including functions and variables, these predicates are restricted to only referring to the attributes of the current element. So an XPath expression like /a/b[c/d] is not allowed.

These kinds of XPath expressions cannot be streamed in general, e.g. in the /a/b[c/d] 'b' may have a lot of children, with 'c' being the last one. To determine if 'b' is included or not, the XPath processor needs to traverse through all the children of 'b', searching for the existence of 'c'. By the time it finds 'c', all the previous children of 'b' have already been passed, and there is no way to rewind back to beginning of 'b'.

Grammar

Explanation

RestrictedPredicate ::= 
     '[' AttributeExpr ']'

AttributeExpr ::= 
      OrExpr

OrExpr ::= 
      AndExpr 
    | OrExpr 'or' AndExpr

AndExpr ::= 
      EqualityExpr 
    | AndExpr 'and' EqualityExpr

EqualityExpr ::= 
      RelationalExpr
    | EqualityExpr '=' RelationalExpr
    | EqualityExpr '!=' RelationalExpr
    
RelationalExpr ::= 
      AdditiveExpr
    | RelationalExpr '<' AdditiveExpr
    | RelationalExpr '>' AdditiveExpr
    | RelationalExpr '<=' AdditiveExpr
    | RelationalExpr '>=' AdditiveExpr

AdditiveExpr ::=
      MultiplicativeExpr
    | AdditiveExpr '+' MultiplicativeExpr
    | AdditiveExpr '-' MultiplicativeExpr
    
MultiplicativeExpr ::= 
      UnaryExpr
    | MultiplicativeExpr MultiplyOperator UnaryExpr
    | MultiplicativeExpr 'div' UnaryExpr
    | MultiplicativeExpr 'mod' UnaryExpr

UnaryExpr ::= 
      PrimaryExpr
    | AttributeReference
    | '-' UnaryExpr

AttributeReference ::=  
      'attribute' '::' NameTest
    | '@' NameTest

An AttributeExpression is an expression involving arithmetic, boolean and relational operators. It can only involve AttributeReferences or PrimaryExprs.

An AttributeReference is reference to an attribute of the current element. e.g. @title.

 
PrimaryExpr ::= 
      VariableReference
    | '(' AttributeExpr ')'
    | Literal
    | Number
    | FunctionCall


Literal ::= '"' [^"]* '"' | "'" [^']* "'"

Number ::= Digits ('.' Digits?)?  | '.' Digits

Digits ::= [0-9]+
 
FunctionCall ::= 
      FunctionName '(' ( Argument ( ',' Argument )* )? ')'

Argument ::= AttributeExpr

FunctionName ::= QName - NodeType

VariableReference ::= '$' QName


A PrimaryExpr is either a literal e.g. "foo" or a number e.g. 23 or a variable reference e.g. $var1 or a function call e.g. sum(23, $price). It can also be a complete AttributeReference.

node(), comment(), text(), processing-instruction() are reserved names, and cannot be used for naming functions.

Node set functions
  • position()
  • count(nodeset)
  • local-name(nodeset)
  • namespace-uri(nodeset)
  • name(nodeset)
String functions
  • string(object?)
  • concat(string, string, string*)
  • starts-with(string, string)
  • contains(string, string)
  • substring-before(string, string)
  • substring-after(string, string)
  • substring(string, number, number)
  • string-length(string?)
  • normalize-space(string?)
Boolean functions
  • boolean(object)
  • true()
  • false()
  • lang(string)
Number functions
  • number(object?)
  • sum(node-set)
  • floor(number)
  • ceiling(number)
  • round(number)

Note:

All of these functions are only allowed inside a predicate.

A predicate's expression can only involve attribute nodes of the current element. Functions can also be used inside this expression, but this function's arguments also have to be expressions involving attribute nodes. There is no way to use elements, text nodes comments and processing instructions in predicate expressions.

The "string-value" of an attribute node is the attributes value. This XPath subset is designed in such a way that "string-value" only need to be evaluated on attribute nodes, never on elements, text nodes or others.

The last() function is not supported because that involves backtracking, streaming parsers cannot do that.

String, number and boolean functions are all supported. However the no argument forms of string(), string-length() and normalize-space() are not supported, because they involve computing a string-value of the current node, and this is not streamable as it involves looking ahead to collecting all descendant text nodes. Also as mentioned before some text nodes can be very large, and cannot be loaded all at once into memory.

The no argument forms of local-name(), namespace-uri() and name() are allowed. For example /a/*[local-name()="foo"] selects all "foo" children of "a" regardless of namespace.

Note: The descendant and related axes can be exploited by a denial of service attacks. See section "XPath selection that causes denial of service in streaming mode" in [XMLDSIG-BESTPRACTICES].

5. Examples of XPath expression that are part of this profile

This sections explains the profile with some XPath expressions that are part of this profile and some that aren't.

All the XPath examples below are based on the following XML document.

<book>
  <foreword>
  </foreword>
  
  <chapter type="preface">
  </chapter>

  <chapter>
    <title>Hybridism</title>
  </chapter>

  <chapter>
  </chapter>

</book>

Examples of XPath expression that are included in the profile.

# Example Description XML Dsig 2.0
1 /book/chapter all chapter children of book Y
2 /book/chapter[3] third chapter child of book Y
3 /book/chapter[@type="preface"] all chapter children of book that have a type attribute with value preface Y
4 /book/chapter[@type="preface"][1] the first chapter child of book that has a title attribute with value preface. Y
5 /book/chapter[2]/title[1] the first title child of the second chapter child of book. Y
6 /book/chapter[contains(@type,"pre")] all chapter children of book that have an attribute type whose value contains the string "pre". Y
7 /child::book/child::chapter[contains(attribute::type,"pre")] non abbreviated form of the above Y
8 /book/chapter[position() mod 2 != 0] chapter children of book whose position is an odd number, i.e. the odd numbered chapters of the book. Y
9 /book/chapter[position() mod 2 != 0][@type="preface"] all the odd numbered chapters whose type is "preface". Y
10 //chapter all chapter descendants Y
11 /book/chapter | /book/foreword all the chapter children of book and all the foreword children of book. Y
12 //* all the element nodes in the document. Y
Note: when this is used to identify a selection in XML Dsig 2.0, it is exactly equivalent to "/*" which select only the document root element.

These are examples of XPath expressions that are NOT included in the profile.

# Example Description XML Dsig 2.0
1 /book/chapter[title="Hybridism"] all chapter children of book that have a title sub element with value Hybridism N
expressions can only involve attributes
2 (/book)/chapter Evaluate the (/book) expression and set that to the context node, and get the chapter child of that context node. N
the top level expression cannot have parenthesis or any other operators except the union operator "|"
3 count(/book/chapter) count the number of chapter children of book N
4 chapter all chapter element children of context node. N
relative location paths not allowed.
5 . The context node. N
relative location paths are not allowed.
6 /book/chapter/title/ancestor-or-self::chapter the chapter ancestor of /book/chapter/title. N
Only child, descendant and self axes are allowed.
7 /book/chapter/title/text() the text child of /book/chapter/title. N
text, comment and processing-instructions cannot be selected.
8 id("i1") elements that have ID, whose value is "i1". N
Functions are only allowed inside predicates, and also the id() function is not part of this subset.
9 /book[chapter/title] the book element if it has a chapter/title grandchild. N
only attributes are allowed in predicates.
10 /book/*[local-name(self::node()) = "chapter"] the children of book element whose local name is "chapter". N
Only attributes are allowed in predicates.
11 /book/chapter[2]/node() all the child elements of the second chapter of the book. N
node() test is not allowed, because it can select text nodes too.
12 /book/chapter or /book/foreword boolean result is true, i.e. either of the location paths evaluate to non empty. N
or operator is not allowed at top level. Top level expression can only be union of location paths.

A. Algorithm

This section outlines an algorithm for a Streaming XPath engine that can execute this XPath subset. It is NOT NORMATIVE.

A streaming XML Parser e.g. [XML-PARSER-STAX] which will produce events like StartElement, EndElement, TextNode etc. This event stream will be the input for the XPath engine. The StartElement event includes all the attributes in that element. An streaming XML Parser may break up a large text node into multiple TextNode events.

  1. Split up the union expression by "|". i.e. break up the locationPath | locationPath | .. into individual location paths.
  2. For each location XPath create a state machine.
  3. Drive the state machines using the events.

B. References

Dated references below are to the latest known or appropriate edition of the referenced work. The referenced works may be subject to revision, and conformant implementations may follow, and are encouraged to investigate the appropriateness of following, some or all more recent editions or replacements of the works cited. It is in each case implementation-defined which editions are supported.

B.1 Normative references

[XPATH]
James Clark; Steven DeRose. XML Path Language (XPath) Version 1.0. 16 November 1999. W3C Recommendation. URL: http://www.w3.org/TR/1999/REC-xpath-19991116/

B.2 Informative references

[EBXML-MSG]
Ian Jones; Brian Gibb; David Fischer. OASIS ebXML Message Service Specification 1 April 2002. URL: http://www.oasis-open.org/committees/download.php/272/ebMS_v2_0.pdf
[HMRMC]
HM Revenue and customs Her Majesty's Revenue and Customs. URL: http://www.hmrc.gov.uk/softwaredevelopers/index.htm
Sample response message with XML signature: http://www.hmrc.gov.uk/ebu/responsemessages.pdf
[XML-PARSER-STAX]
Christopher Fry. JSR 173: Streaming API for XML for Java Specification 8th October 2003. v1.0 URL: http://jcp.org/en/jsr/detail?id=173
[XMLDSIG-BESTPRACTICES]
Pratik Datta; Frederick Hirsch. XML Signature Best Practices. 31 August 2010. W3C Working Draft. (Work in progress.) URL: http://www.w3.org/TR/2010/WD-xmldsig-bestpractices-20100831/
[XMLDSIG-CORE1]
D. Eastlake, J. Reagle, D. Solo, F. Hirsch, T. Roessler, K. Yiu. XML Signature Syntax and Processing Version 1.1. 3 March 2011. W3C Candidate Recommendation. (Work in progress.) URL: http://www.w3.org/TR/2011/CR-xmldsig-core1-20110303/
[XMLDSIG-CORE2]
Mark Bartel; John Boyer; Barb Fox et al. XML Signature Syntax and Processing Version 2.0. 24 January 2012. W3C Candidate Recommendation. (Work in progress.) URL: http://www.w3.org/TR/2012/CR-xmldsig-core2-20120124/
[XMLDSIG-XPATH-FILTER2]
Merlin Hughes; John Boyer; Joseph Reagle. XML-Signature XPath Filter 2.0. 8 November 2002. W3C Recommendation. URL: http://www.w3.org/TR/2002/REC-xmldsig-filter2-20021108/
[XPTR-ELEMENT]
Norman Walsh; et al. XPointer element() Scheme. 25 March 2003. W3C Recommendation. URL: http://www.w3.org/TR/2003/REC-xptr-element-20030325/
[XPTR-XPOINTER]
Ron Daniel Jr.; Eve Maler; Steven DeRose. XPointer xpointer() Scheme. 19 December 2002. W3C Working Draft. (Work in progress.) URL: http://www.w3.org/TR/2002/WD-xptr-xpointer-20021219/