Explosion

[Murata Makoto <mura034@attglobal.net>]

I created simple but malicious patterns, which make validation takes
exponential time.  Explosion arises because of wild cards for attributes.

These patterns and instances are malicious and will be used rarely.  But 
I'm not sure if there are realistic examples which lead to explosion.

Case 1:

pattern

<element name="foo">
  <oneOrMore>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar1"><empty/></element>
    <attribute>
      <anyName/>
    </attribute>
  </oneOrMore>
</element>

XML instance

<foo
a0=""
a1=""
a2=""
...>
<bar1/>
...
<bar1/>
</foo>

number of attributes	elapsed time of JTREX(milliseconds)
20			1760 
22			2630
24			5600
26			13180
28			33010
30			85130


Case 2:

pattern

<element name="foo">
  <oneOrMore>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar1"><empty/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar2"><empty/></element>
    <attribute>
      <anyName/>
    </attribute>
  </oneOrMore>
</element>

XML instance

<foo
a0=""
a1=""
a2=""
...>
<bar1/>
<bar2/>
...
<bar1/>
<bar2/>
</foo>

number of attributes	elapsed time of JTREX(milliseconds)
12			1210
15			1710
18			4510
21			23350
24			140560


Case 3:

pattern

<element name="foo">
  <oneOrMore>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar1"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar2"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar3"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
  </oneOrMore>
</element>

XML instance

<foo
a0=""
a1=""
a2=""
...>
<bar1/>
<bar2/>
<bar3/>
...
<bar1/>
<bar2/>
<bar3/>
</foo>

number of attributes	elapsed time of JTREX(milliseconds)
8			490
12			820
16			3740
20			46740


Case 4:


pattern

<element name="foo">
  <oneOrMore>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar1"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar2"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar3"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
    <element name="bar4"><anyString/></element>
    <attribute>
      <anyName/>
    </attribute>
  </oneOrMore>
</element>

XML instance

<foo
a0=""
a1=""
a2=""
...>
<bar1/>
<bar2/>
<bar3/>
<bar4/>
...
<bar1/>
<bar2/>
<bar3/>
<bar4/>
</foo>

number of attributes	elapsed time of JTREX(milliseconds)

5			440
10			600
15			4120
20			106510

Cheers,

Makoto