XML Signature should not require
DOM. There are existing streaming XML Signature implementations but
they make various assumptions. It would be better to formalize
these assumptions and requirements at the standardization level, rather than
leave it up to each implementation.
3.5.1 Overheads of DOM
DOM parsers have a large overhead.
Suppose there is a 1MB XML document. If this loaded into memory as a
byte array
it remains as a 1MB byte array. But if it is parsed into a DOM it
explodes to 5-10x in
size. This is because in DOM, each XML node has to become an
object. Objects have overheads
of memory book keeping, virtual function tables etc. Also each XML
node needs parent, next sibling, previous sibling pointers, and it
also needs prefix, namespaceURI
etc, which could be objects
themselves. All these eat up memory and it is a popular misconception
that memory is very cheap.
Even if this memory were temporary allocation only it would still
be expensive - in garbage collected languages allocating
and freeing too much of memory triggers the
garbage collector too often which drastically slows down the
system. Also this 10x DOM explosion can result
in physical memory getting exhausted and requiring more pages to be
swapped from disk. That is why
web services often use streaming XML parsers on the server side. DOM
parsers will croak and groan
if asked to process multiple large XML documents simultaneously,
whereas streaming XML parsers
will happily chug along because of their low memory consumption.
3.5.2 One Pass
It is important to distinguish between one-pass and streamability. Streamability means not requiring
to have the whole document in a parsed form available for random access, i.e. not requiring a DOM.
While one pass is desirable, two pass doesn't take away all the merits of streaming.
Suppose the signature value is before the data to be signed. This means that the signature value cannot be
updated in the first pass, but only in the second pass - this is not really bad from the performance point of view.
Let us the say the document is being streamed out into 1MB byte array, then in the first pass write some dummy bytes
for this signature value and remember the location, and in the 2nd pass just update this location with the actual
signature bytes, so the 2nd pass is very quick.
Also streamability does not require the ordering between the subelements of signature element.
It can be assumed that
the entire
Signature element (assuming it is detached or enveloped signature)
will be loaded up into a java/c++ object, so the order of the elements
inside the Signature element does not affect streamability.
Verification in particular cannot be 1 pass - let us say you have a
signed 1GB incoming message, which you need to verify first and then
upload to a database. So you have to make two passes on this data - a
first pass to verify and second pass to upload to the database. One cannot
combine these two into 1 pass because verification result is
determined only after reading the last byte.
3.5.3 Nodeset
The main impediment to streamability is the transform chain, because
many of the transforms are defined on nodesets and nodeset requires a
DOM. An XPath transform is the biggest culprit as there are many XPath
expressions which cannot be streamed. It is necessary to define a
streamable subset of XPath (which has been done for XPath
1.0, see [XMLDSIG-XPATH]).
Nodesets have another big problem. This nodeset concept was borrowed from
XPath 1.0, and an XPath nodeset introduces a new kind of XML node -
the namespace
node. Namespace nodes are different from namespace declarations in an
important way - they are not
inherited. This means they need to be repeated for every node for
which
they are applicable. To give an example, if there is a document
with 100 namespace declarations at the top element and with 99 child
elements of the top element, a regular DOM
will only have 200 (1 top element node + 99 child element nodes + 100
attribute nodes), whereas a nodeset will have
10,100 nodes (1 top element + 99 child element + 100*100 namespace
nodes).
A naive implementation which uses the nodeset as defined
will therefore be very slow, and be also be
subject to various denial of service attacks. A smart
implementation can try to not expand the nodeset
fully and use inheritance, but they it won't be fully
compliant with the XML Signature spec. This is
because an XPath filter can address each of namespace
nodes individually and filter them out, even
though it is meaningless in XML. The Y4 test vector in the
Exclusive
Canonicalization Implementation and Interoperability
Report has an example of this. Because
of these performance problems some implementations do not
support this Y4 test vector or only support it
conditionally.
3.5.4 Streaming XPath Profile for XML Signature 2.0
XML Signature requires a profile of XPath to enable
streaming.
Signature verification can be done in two passes. The first pass is a
very cursory pass to collect the signature
element and signing keys from the document. Signatures are
often present in the beginning of the document, so this
usually a very short pass. At the end of the first pass,
the IncludedXPath and ExcludedPath are taken
from each
reference and used to construct "state machines" from these
XPaths.
After the first pass, the second pass is performed.
In this pass the document is parsed
using a streaming XML parser to generate XML
events. These events are fed into a state machine. If the
event is accepted by an IncludedXpath, but
not accepted by
an ExcludedXPath then it is included, in that
case the event is passed on to a streaming canonicalizer,
and then to a
streaming digestor.
At the end of the second pass the result is digests for each
reference.
The operation and requirements of this XPath profile is different
from the requirements of other XPath profiles, such as that for XSLT
template processing [XSLT21]. For this reason, XML Security
requires its own XPath
profile, although it might be suitable for other uses as well.
The reason the XSLT XPath profile is not suitable is that the
assumptions and requirements are different.
In XSLT processing the XPaths are not known in advance. The XSLT
processor has to be ready to process any XPath that it comes
across, so it maintains a context. This context consists of all the
ancestors of the current element and some histograms so that it can
process the position() function. The XPath needs to
evaluated with
only this context and nothing else. This is a fundamental difference
from XML Signature model. In XML Signature, the XPaths are known in
advance, and being continuously evaluated for every node. But in
XSLT, they are evaluated only once.
The XPath subset is defined as the kind of subset can be
evaluated with the XPath context. In the XSLT profile, for example,
all sideways axis are
disallowed by the subset i.e. following, preceding,
following-sibling, or preceding-sibling. But the Signature subset
allows following, and following-sibling.
Another big difference is the way this subset is defined. XML
Signature defines the subset by syntax. Although this kind of
definition is simpler to define and understand, it results in XPaths
that are allowed in one syntax, but not allowed in another
syntax. e.g. /a/b is allowed, but (/a)/b is
not allowed in XML
Signature. XSLT defines the subset by a "data flow graph". This has
restrictions like once you start going up, you can't go down. (See the
seven such rules
in http://www.w3.org/TR/xslt-21/#streamability-conditions.)
While XML Signature is very strict in allowing only attributes in
predicate, XSLT is much more lax, e.g. /a[b] is not
allowed in XML
Signature, but is allowed in XSLT, because the rule 4 says that it is
ok to go downwards as long you don't revisit a node more than once.
Another difference arising from this evaluation model is that XSLT
allows relative XPaths - in fact that is a very important part of
XSLT. There is always a current context node, when evaluating the XSLT
XPath. So it allows parent and ancestor axis.
In summary, the two subsets have completely different purpose and
there is no benefit in making them similar, that will only cripple
both the use cases.
There are subsets whose use cases are similar to XML
Signature where XPath expressions are known in advance and XPath
expressions are used for
selection. An example is the WS-Transfer use case.