XML Signature Streaming Profile of XPath 1.0

Table of Contents

• 1. Introduction
• 2. Streamable
• 3. Other requirements
• 4. Definition of the Profile
• 5. Examples of XPath expression that are part of this profile
• 6. Algorithm
• A. References
  • A.1 Normative references
  • A.2 Informative references

1. Introduction

This document specifies a streamable profile of XPath 1.0 [XPATH] for use in XML Signature 2.0 [XMLDSIG-CORE2]. 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 is 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 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 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 one-pass streamable. This means

1. It should be possible to evaluate this XPath on large XML documents without having having to load the entire document into memory. The implementation should read the XML one chunk at a time, and do a single forward only pass over the document.

2. More specifically, the XPath engine should work off a streaming XML parser. A streaming parser is a software module that reads the XML document, and constructs a stream of XML events like "beginElement", "text", "endElement" etc. [StAX] is an example of a streaming parser. At any point the streaming parser only has the current event in memory. The XPath engine needs to evaluate the XPath based on this stream of events, so it can only work off the current event, and some limited state e.g. the ancestors of this element. This means that the XPath should be evaluatable with this limited information.

3. The XPath itself might select a large portion of the document, or even the whole document. The result of the XPath evaluation should not be loaded all into memory if it is large. Instead it should be pipelined to the processing stage, which in case of XML signature 2.0 is canonicalization. i.e. an XML Signature 2.0 implementation should be able to select portions of the XML document using XPath, canonicalize the selected sections and then compute a digest, all in a pipeline with a limited amount of memory.

4. The XML document may have very large text nodes. The XPath engine should not be required to load such large nodes in their entirety.

In the context of XML Signature, streaming is absolutely essential for network appliances which need to perform XML Signature and Encryption operations for messages on the wire. It is also important for performance sensitive application as streaming, by conserving memory, greatly reduces memory allocation, deallocation and garbage collection calls, thereby improving performance.

3. Other requirements

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

• The profile should produce results that are compatible with the C14N 2.0 data model. i.e it should only result in element nodes or attribute nodes (but not xml: attribute and namespace attributes).

• This XPath profile should include some of the known usages of XPath in XML Signatures.

  1. ebXML messages require a signature to exclude elements whose @SOAP:actor attribute matches a certain value. Refer section 4.1.3 of [EBXML-MSG]
  2. UK government specification requires signature to include the GovTalkMessage/Body subtree, but exclude the GovTalkMessage/Body/IRevenvelope/IRHeader/IRmark subtree. [HMRMC]

4. Definition of the Profile

The following table defines this XPath profile. It is expressed as a diff of the XPath 1.0 grammar, and the rule numbers here match the rule numbers in the XPath 1.0 grammar [XPATH]. Insertions are underlined and deletions are in strikeout.

[0a] IncludedXPath ::= 
      ( LocationPath '|' )* LocationPath 
          
[0b] ExcludedXPath ::= 
      ( LocationPath '|' )* LocationPath

[1] LocationPath ::= 
     RelativeLocationPath
     | AbsoluteLocationPath

[2] AbsoluteLocationPath ::=  
     '/' RelativeLocationPath? 
     | AbbreviatedAbsoluteLocationPath

[3] RelativeLocationPath ::= 
     Step 
     | RelativeLocationPath '/' Step
     | AbbreviatedRelativeLocationPath

[4] Step ::= 
    AxisSpecifier NodeTest Predicate*
    | AbbreviatedStep
    
[4a] StepAttributeOnly ::=  
    'attribute' '::' NameTest 
    | '@' '::' NameTest

[5] AxisSpecifier ::=  
   AxisName '::' 
   | AbbreviatedAxisSpecifier

[6] AxisName ::= 
   'ancestor'
  |'ancestor-or-self'
  | 'attribute'
  | 'child'
  | 'descendant'
  | 'descendant-or-self'
  | 'following'
  | 'following-sibling'
  | 'namespace'
  | 'parent'
  | 'preceding'
  | 'preceding-sibling'
  | 'self'

[7] NodeTest ::= 
    NameTest 
    | NodeType '(' ')'
    | 'processing-instruction' '(' Literal ')'

[8] Predicate ::= 
     '[' PredicateExpr ']'

[9] PredicateExpr ::= 
     Expr

[10] AbbreviatedAbsoluteLocationPath ::=  
       '//' RelativeLocationPath
[11] AbbreviatedRelativeLocationPath ::=  
       RelativeLocationPath '//' Step
[12] AbbreviatedStep ::= 
       '.' | '..'
[13] AbbreviatedAxisSpecifier ::= 
       '@'?
 

 
[14] Expr ::= OrExpr

[15] PrimaryExpr ::= 
    VariableReference
    | '(' Expr ')'
    | Literal
    | Number
    | FunctionCall
 

[16] FunctionCall ::= 
      FunctionName '(' ( Argument ( ',' Argument )* )? ')'

[17] Argument ::= Expr

[18] UnionExpr ::=  PathExpr | UnionExpr '|' PathExpr

[19] PathExpr ::= LocationPath
    | FilterExpr
    | FilterExpr '/' RelativeLocationPath
    | FilterExpr '//' RelativeLocationPath
    
[20] FilterExpr ::= PrimaryExpr
    | FilterExpr Predicate

[21] OrExpr ::= AndExpr | OrExpr 'or' AndExpr

[22] AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr

[23] EqualityExpr ::= RelationalExpr
    | EqualityExpr '=' RelationalExpr
    | EqualityExpr '!=' RelationalExpr
    
[24] RelationalExpr ::= AdditiveExpr
    | RelationalExpr '<' AdditiveExpr
    | RelationalExpr '>' AdditiveExpr
    | RelationalExpr '<=' AdditiveExpr
    | RelationalExpr '>=' AdditiveExpr

[25] AdditiveExpr ::=
    MultiplicativeExpr
    | AdditiveExpr '+' MultiplicativeExpr
    | AdditiveExpr '-' MultiplicativeExpr
    
[26] MultiplicativeExpr ::= UnaryExpr
    | MultiplicativeExpr MultiplyOperator UnaryExpr
    | MultiplicativeExpr 'div' UnaryExpr
    | MultiplicativeExpr 'mod' UnaryExpr

[27] UnaryExpr ::= UnionExpr
    PrimaryExpr
    | StepAttributeOnly
    | '-' UnaryExpr

[28] ExprToken ::= 
    '(' | ')' | '[' | ']' | '.' | '..' | '@' | ',' | '::'
    | NameTest
    | NodeType
    | Operator
    | FunctionName
    | AxisName
    | Literal
    | Number
    | VariableReference

[29] Literal ::= '"' [^"]* '"' | "'" [^']* &uot;'"

[30] Number ::= Digits ('.' Digits?)?  | '.' Digits

[31] Digits ::= [0-9]+

[32] Operator ::= 
    OperatorName | MultiplyOperator
    | '/' | '//' | '|' | '+' | '-' | '=' | '!='
    | '<' | '<=' | '>' | '>='

[33] OperatorName ::= 
    'and' | 'or' | 'mod' | 'div'

[34] MultiplyOperator ::= '*'

[35] FunctionName ::= QName - NodeType

[36] VariableReference ::= '$' QName

[37] NameTest ::= 
    '*' | NCName ':' '*' | QName

[38] NodeType ::= 
    'comment'
    | 'text'
    | 'processing-instruction'
    | 'node'

[39] ExprWhitespace ::= S

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.

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

6. Algorithm

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

For parsing:

1. Split up the union expression by "|". i.e. break up the locationPath | locationPath | .. into individual location paths.
2. Split up each location paths to get individual steps and the final predicate. i.e. break up the / step / step / step .. / step [ predicate ] to get the steps and optional predicate. Two slashes together indicates descendant axis.
3. The predicate will have an expression involving attribute names e.g. @a = "foo" and @b > "bar" You need to have an expression parsing and evaluating engine to do this.

For executing:

1. A streaming XML Parser (e.g. StAX), reads an XML document and produces "events" like StartElement, EndElement, TextNode etc. At any point this parser only remembers the current node. If the current node is an start element, then it also reads all the attributes for that element. To execute a streaming XPath you maintain a stack of ancestor element names, i.e whenever you get a StartElement tag, you need to push the element QName onto this stack, and when you get an EndElement tag you need to pop it off.
2. As you stream through the nodes, you need to execute this XPath expression for every node. I.e. utilize the current element, the current element's attributes and the stack of ancestors to evaluate the XPath expression.

   For each locationPath, match up the steps to the ancestor stack, If they match, evaluate the predicate with the current element's expression. If that passes too, this element and all its descendants are included.