Re: Explosion

[James Clark <jjc@jclark.com>]

This is just a limitation of JTREX.  It doesn't memoize the construction of
derivatives for attributes.  Just to prove to myself that this really was
the problem, I implemented a simple caching scheme for attribute
derivitives; with this fix, it could handle your cases with any exponential
increase in computation time.

Incidentally, this has nothing to do with attribute wildcards.   You could
equally well cause blow-up in the current JTREX implementation with a
sufficiently large choice of attributes.

----- Original Message -----
From: "Murata Makoto" <mura034@attglobal.net>
To: <trex@lists.oasis-open.org>
Sent: Sunday, May 06, 2001 8:52 PM
Subject: Explosion


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