[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC