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

This is a W3C Working Draft of "XML Signature Streaming Profile of XPath 1.0".

A diff-marked version of this specification that highlights changes against the previous version is available. Major changes in this version include:

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.

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.

Streamable

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

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.

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.

Other requirements

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

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.

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.

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.

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]].

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.

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.