[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: New release (2.8) of XSV

• To: daniel@v...
• Subject: Re: New release (2.8) of XSV
• From: ht@i... (Henry S. Thompson)
• Date: Mon, 11 Oct 2004 14:56:55 +0100
• Cc: Jeff Rafter <lists@j...>, xmlschema-dev@w..., xml-dev@l...
• In-reply-to: <20041011131427.GC11346@d...> (Daniel Veillard'smessage of "Mon, 11 Oct 2004 15:14:27 +0200")
• References: <f5bfz4pvc2n.fsf@e...><4166BCB7.6020309@j...><f5b8yahqiit.fsf@e...><20041009124018.GD11758@d...><f5bsm8mkzhv.fsf@e...><20041011131427.GC11346@d...>
• User-agent: Gnus/5.1006 (Gnus v5.10.6) XEmacs/21.4 (Security ThroughObscurity, linux)

Daniel Veillard <daniel@v...> writes:

> On Sun, Oct 10, 2004 at 10:57:32PM +0100, Henry S. Thompson wrote:
>> Daniel Veillard <daniel@v...> writes:
>> 
>> > libxml2 regexps used counters since day 1 for min/maxoccurs
>> > implementation.  The explosion didn't look a supportable
>> > alternative to me as it opens the door to trivial DoS attacks or
>> > forces to break the schemas validation which is also a big
>> > problem if you consider schemas as a contract between two
>> > communicating parties.
>> 
>> I would be very interested, as I'm sure would others, in a description
>> of your algorithm.
>
> Well nothing fancy really. You need to add state to the regexp, in
> that case the state is the number of time you went through the
> transition labelled by the element name:namespace pair. Due to the
> single particle rule, it means you have no need to be able to
> rollback the state to enter a different transition labelled by the
> same name:namespace pair.  Which means the effective state required
> is purely linear based on the number of counted transition you have
> in your regexp: one integer counter is sufficient per such
> transition in the regexp runtime structure. It's actually more
> automata with state that I'm using than pure regexps.  And the
> generated constructs for something like x{a,b} involves 3 states
> (IIRC) a couple of epsilon transitions and the counted regexp, but
> it's not really rocket sience either, very similar to what I was
> taught in the classroom.

Right, that works fine for exponents on individual elements, but I
don't see how it works for groups.

Here's a real example from a published schema document [1]:

<xsd:sequence minOccurs="0" maxOccurs="1000">
    <xsd:element ref="ReferenceIdentification" minOccurs="0"/>
    <xsd:element ref="Message" minOccurs="0" maxOccurs="1000"/>
</xsd:sequence>

Or consider a (constructed) case that's tricky in a different way:

<xsd:sequence minOccurs="2" maxOccurs="2">
    <xsd:element ref="a" minOccurs="1" maxOccurs="2"/>
    <xsd:element ref="b" minOccurs="0"/>
</xsd:sequence>

which allows _inter alia_

 <a/><a/>
 <a/><a/><a/>
 <a/><a/><a/><a/>

ht
 
[1] http://www.idealliance.org/spacexml/files/spacexmlv100.zip
-- 
 Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                     Half-time member of W3C Team
    2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
            Fax: (44) 131 650-4587, e-mail: ht@i...
                   URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]

• References:
  • New release (2.8) of XSV
    • From: ht@i... (Henry S. Thompson)
  • Re: New release (2.8) of XSV
    • From: Jeff Rafter <lists@j...>
  • Re: New release (2.8) of XSV
    • From: ht@i... (Henry S. Thompson)
  • Re: New release (2.8) of XSV
    • From: ht@i... (Henry S. Thompson)

• Prev by Date: Re: [Shannon: information ~ uncertainty] Ramificationsto XML data exchange?
• Next by Date: Re: [Shannon: information ~ uncertainty] Ramificationsto XML data exchange?
• Previous by thread: Re: New release (2.8) of XSV
• Next by thread: Re: New release (2.8) of XSV
• Index(es):
  • Date
  • Thread