Performace data and comparison

--On Dienstag, 7. Mai 2002 12:24 -1000 Joseph Reagle <reagle@w3.org> wrote:

> On Monday 06 May 2002 21:01, Christian Geuer-Pollmann wrote:
>> PS: Actually, I don't know why [2] is not considered by anybody be worth
>> to have a closer look at.
>
> I think it is worth consideration, and we want to think about
> functionality  and performance. Merlin mentioned he didn't feel the
> functionality that  compelling but I'd like to here from others. Since in
> another email you  mentioned your hoping to respond to John's request for
> performance results,  perhaps you could share numbers on this point too!

OK, here they are:

Hi all,

today, I did some performance testing on xmldsig-xfilter2 and on my own 
approach for filtering. For these tests, I used the sample file which John 
supplied (the pureedge data) and the illustrated sample from the 
xmldsig-xfilter2 filter spec.

To have a rough idea on the comparison to other signatures, I also created 
a detached signature for a 300kB GIF image. To get a little bit more 
accurate data, I created each signature 600 times. To eliminate the 
influence of public key crypto, all these "signatures" are HMAC-SHA1's. The 
test machine is a Pentium3, 733MHz, 256MB RAM, Windows 2000, SUN Java JRE 
1.3.1.

#####################################

Test description:

#####################################

simple_gif_detached:

A detached signature over a 300 kilo bytes binary file (no transforms). The 
file (should) come from the operating systems and hard drives cache (600 
reads on the same file...).

#####################################

pureedge_xfilter2:

This is an enveloped signature which is embedded into the 
"LeaveRequest.xfd" file. It uses the transform:

<ds:Transforms>
<ds:Transform Algorithm="http://www.w3.org/2002/04/xmldsig-filter2">
<dsig-xpath:XPath 
xmlns:dsig-xpath="http://www.w3.org/2002/04/xmldsig-filter2" 
Filter="subtract">
/XFDL/page[@sid='PAGE1']/*[@sid='CHECK16' or
                           @sid='CHECK17' or
                           @sid='FIELD47' or
                           @sid='BUTTON2' or
                           @sid='FIELD48']
 |
/XFDL/page/triggeritem[not(attribute::sid) |
                       /XFDL/page/*/triggeritem]
 |
here()/ancestor::ds:Signature[1]</dsig-xpath:XPath>
</ds:Transform>
</ds:Transforms>

#####################################

pureedge_apachefilter

This is an enveloped signature which is embedded into the 
"LeaveRequest.xfd" file. The transform results in the same result as 
pureedge_xfilter2 does. It uses the proprietary transform:

<ds:Transforms>
<ds:Transform 
Algorithm="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter
">
<xx:XPathAlternative 
xmlns:xx="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter">
<xx:IncludeButSearch>
/
</xx:IncludeButSearch>
<xx:Exclude>
/XFDL/page[@sid='PAGE1']/*[@sid='CHECK16' or
                           @sid='CHECK17' or
                           @sid='FIELD47' or
                           @sid='BUTTON2' or
                           @sid='FIELD48']
 |
/XFDL/page/triggeritem[not(attribute::sid) |
                       /XFDL/page/*/triggeritem]
 |
here()/ancestor::ds:Signature[1]</xx:Exclude>
</xx:XPathAlternative>
</ds:Transform>
</ds:Transforms>

#####################################

xfilter2spec_xfilter2_3 and xfilter2spec_apachefilter_3 are both applied to 
the sample from section 4 in 
<http://www.w3.org/Signature/Drafts/xmldsig-xfilter2/>. The ..xfilter2_3 
uses the three <ds:Transform>s from the example, the ..apachefilter_3 
results in the same nodeset using the following transform:

<ds:Transforms>
<ds:Transform 
Algorithm="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter
">
<xx:XPathAlternative 
xmlns:xx="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter">
<xx:IncludeButSearch>
//ToBeSigned | //ReallyToBeSigned
</xx:IncludeButSearch>
<xx:ExcludeButSearch>
/ | //NotToBeSigned
</xx:ExcludeButSearch>
<xx:Exclude>
here()/ancestor::ds:Signature[1]
</xx:Exclude>
</xx:XPathAlternative>
</ds:Transform>
</ds:Transforms>

#####################################

Timing Results:

Number of iterations: 600

simple_gif_detached              294,503 seconds (0,49 second per iteration)
----------------------------------------------------------------------------
pureedge_xfilter2              1.144,620 seconds (1,91 second per iteration)
pureedge_apachefilter          1.205,240 seconds (2,00 second per iteration)
----------------------------------------------------------------------------
xfilter2spec_xfilter2_3          138,910 seconds (0,23 second per iteration)
xfilter2spec_apachefilter_3      131,178 seconds (0,22 second per iteration)

What you can see here is that my approach is 5% slower than the current 
spec for the pureedge example and 5% faster for the example from the spec. 
My guess is the following:

It's not possible with xmldsig-xfilter2 to do the operations from 
subsequent transforms in a single step; each transform MUST be handled 
individualy, so each transform costs time. If you do multiple 
xmldsig-xfilter2 operations for selecting the right nodes, this becomes 
more and more inefficient.

'My' transform does the complete selection in a single step. These is no 
need to do multiple union/intersect/subtract ops in a sequence to select 
the right things. So I guess that the runtime of my transform is -- well, 
not constant, but -- depending on the form of the selected subtrees.

#####################################

To test this, I took the (very small) example from section 4 and created 
three different signatures using both transform algos:

xfilter2spec_xfilter2_1 only does this:

 - intersect(//ToBeSigned)

xfilter2spec_xfilter2_2 does this:

 - intersect(//ToBeSigned)
 - subtract(//NotToBeSigned)

xfilter2spec_xfilter2_3 was the full magic (mentioned earlier):

 - intersect(//ToBeSigned)
 - subtract(//NotToBeSigned)
 - union(//ReallyToBeSigned)

#################################

xfilter2spec_apachefilter_1, xfilter2spec_apachefilter_2 and 
xfilter2spec_apachefilter_3 produce the same results using my transform:

#################################

xfilter2spec_apachefilter_1:

<ds:Transform 
Algorithm="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter
">
<xx:XPathAlternative 
xmlns:xx="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter">
<xx:IncludeButSearch>
//ToBeSigned
</xx:IncludeButSearch>
<xx:ExcludeButSearch>
/
</xx:ExcludeButSearch>
<xx:Exclude>
here()/ancestor::ds:Signature[1]
</xx:Exclude>
</xx:XPathAlternative>
</ds:Transform>

#################################

xfilter2spec_apachefilter_2

<ds:Transform 
Algorithm="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter
">
<xx:XPathAlternative 
xmlns:xx="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter">
<xx:IncludeButSearch>
//ToBeSigned
</xx:IncludeButSearch>
<xx:ExcludeButSearch>
/ | //NotToBeSigned
</xx:ExcludeButSearch>
<xx:Exclude>
here()/ancestor::ds:Signature[1]
</xx:Exclude>
</xx:XPathAlternative>
</ds:Transform>

#################################

xfilter2spec_apachefilter_3

<ds:Transform 
Algorithm="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter
">
<xx:XPathAlternative 
xmlns:xx="http://www.nue.et-inf.uni-siegen.de/~geuer-pollmann/#xpathFilter">
<xx:IncludeButSearch>
//ToBeSigned | //ReallyToBeSigned
</xx:IncludeButSearch>
<xx:ExcludeButSearch>
/ | //NotToBeSigned
</xx:ExcludeButSearch>
<xx:Exclude>
here()/ancestor::ds:Signature[1]
</xx:Exclude>
</xx:XPathAlternative>
</ds:Transform>

#################################

When you look at the results below, you see that each step in the 
xfilter2spec_xfilter2_(1/2/3) adds more processing time, while this is not 
the case for 'my' transform: I can't tell why they are as they are.

xfilter2spec_xfilter2_1          109,337 seconds (0,18 second per iteration)
xfilter2spec_xfilter2_2          122,206 seconds (0,20 second per iteration)
xfilter2spec_xfilter2_3          138,910 seconds (0,23 second per iteration)
----------------------------------------------------------------------------
xfilter2spec_apachefilter_1      130,297 seconds (0,22 second per iteration)
xfilter2spec_apachefilter_2      123,268 seconds (0,21 second per iteration)
xfilter2spec_apachefilter_3      131,178 seconds (0,22 second per iteration)

#################################

To show you what I did, I attach a ZIP containing all signatures (doc) and 
the de-references and transfomed octets (ref). (I did not include the GIF, 
it's simply 318 KB (326.587 Bytes).