January 2024 - dfdl-wg - lists.ogf.org

Example schema that illustrates pathological DFDL behaviors
by Mike Beckerle 07 Feb '24

07 Feb '24

I have been concerned for a while that combinations of the features in DFDL v1.0 can be used in ways that are just far too powerful for what is needed for data format expression. For example, if the input is n bits, how large should the corresponding infoset be when the data is parsed using a DFDL schema? Clearly at least O(n) since there are n bits and each bit could create an element in the infoset. But should it be able to be O(n^2) ? I can think of no use case for this. Intuition about data formats suggests that the infoset should always be linearly related in size to the size of the input data, and that the constant factor on that should be relatively small. Furthermore, the time taken to parse data should be linearly related to the size of the data. I think lots of people are thinking DFDL parsing should be implementable in a circuit, and the memory requirements are proportional to the data size. It doesn't make sense to try to make hardware implementations of DFDL if that's not going to be the case. Turns out, using DFDL v1.0 using dfdl:occursCountKind='expression' and dfdl:inputValueCalc, can create an infoset from parsing that is super-exponentially larger than the input data. Yes, it is finite, and bounded to some function of the size of the input data. But we don't even have notations for this kind of numeric growth. The schema I created consumes a 3 bit integer as the data. The size of the infoset grows like this: - input 000 -> infoset size 1 - input 001 -> infoset size 1 - input 010 -> infoset size 256 - input 011 -> infoset size is over 10,000 elements - ... - input 111 -> infoset size is larger than the number of atoms in the universe. There are TDML tests for this schema that illustrate this (except that last one) But it is always finite! No recursion is required to do this. With infinite space and time available it WILL terminate. I believe the language remains theoretically decidable. The README in this schema project discusses this and other pathological cases, and suggests things we can do to restrict DFDL so that this kind of pathological behavior is not allowed. Really we want the largest infoset that can be created from - n bits of data - a schema of size s to be O(sn) in size. I have started an argument in the README about why O(sn) is the right target. Basically there are practical schemas that can meet O(sn) as a lower bound. I believe this can be achieved by adding more forward-progress requirements to DFDL - all arrays should have to make forward progress when parsing, not just unbounded arrays, and reused groups/types should have to make forward progress at points of reuse. By doing that, we ensure that to make a giant infoset, you have to be consuming a giant number of bits. Right now this stuff is just living in a personal github repo, but I'll give it an official better home either in DFDLSchemas or as part of Apache Daffodil, or something later. If this is of interest, please take a look at this github pull request below. ---------- Forwarded message --------- From: Mike Beckerle <notifications(a)github.com> Date: Wed, Jan 24, 2024 at 3:50 PM Subject: [mbeckerle/superexp] Example schema that illustrates pathological DFDL behaviors (PR #1) To: mbeckerle/superexp <superexp(a)noreply.github.com> Cc: Mike Beckerle <mbeckerle(a)apache.org>, Your activity < your_activity(a)noreply.github.com> Illustrates DFDL issues where parsing small data can lead to explosively larger parse output. Super exponentially larger. The expressive power of DFDL should be restricted so that this is not possible. See the README.md for discussion of the issue. ------------------------------ You can view, comment on, or merge this pull request online at: https://github.com/mbeckerle/superexp/pull/1 Commit Summary - 46dbae6 <https://github.com/mbeckerle/superexp/pull/1/commits/46dbae6b2dc5acd76d6954…> First version of this example schema File Changes (9 files <https://github.com/mbeckerle/superexp/pull/1/files>) - *A* .gitattributes <https://github.com/mbeckerle/superexp/pull/1/files#diff-618cd5b83d62060ba3d…> (5) - *M* .gitignore <https://github.com/mbeckerle/superexp/pull/1/files#diff-bc37d034bad56458379…> (7) - *M* README.md <https://github.com/mbeckerle/superexp/pull/1/files#diff-b335630551682c19a78…> (96) - *A* build.sbt <https://github.com/mbeckerle/superexp/pull/1/files#diff-5634c415cd8c8504fdb…> (30) - *A* project/build.properties <https://github.com/mbeckerle/superexp/pull/1/files#diff-cbc85b9df7818a480f2…> (1) - *A* src/exp.dfdl.xsd <https://github.com/mbeckerle/superexp/pull/1/files#diff-9751c75e50c64f92bee…> (84) - *A* src/superexp.dfdl.xsd <https://github.com/mbeckerle/superexp/pull/1/files#diff-2c057f270cab45f3f05…> (72) - *A* test/TestSuperexp.scala <https://github.com/mbeckerle/superexp/pull/1/files#diff-c6b466d6536f0f670f9…> (35) - *A* test/TestSuperexp.tdml <https://github.com/mbeckerle/superexp/pull/1/files#diff-f1b4e40b448ec3ab530…> (117) Patch Links: - https://github.com/mbeckerle/superexp/pull/1.patch - https://github.com/mbeckerle/superexp/pull/1.diff — Reply to this email directly, view it on GitHub <https://github.com/mbeckerle/superexp/pull/1>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AALUDAZF7ZM5XWD72HZ4Z5DYQ…> . You are receiving this because you are subscribed to this thread.Message ID: <mbeckerle/superexp/pull/1(a)github.com>

1 1

Updated invitation with note: DFDL Workgroup - DFDL Spec Issues and Actions @ Wed Feb 7, 2024 11am - 12pm (EST) (dfdl-wg@ogf.org)
by Mike Beckerle 25 Jan '24

25 Jan '24

This event has been updated with a note: "I need to change this one call to a different day. I've chosen to try moving it to Wednesday Feb 7. " Changed: time DFDL Workgroup - DFDL Spec Issues and Actions Wednesday Feb 7, 2024 ⋅ 11am – 12pm Eastern Time - New York Location Google Meet https://www.google.com/maps/search/Google+Meet?hl=en Join with Google Meet https://meet.google.com/ifg-hknz-ysw?hs=224 Please send email to open discussions and add agenda for this meeting. If there are no specific topics I will cancel the meeting. Organizer Mike Beckerle mbeckerle.dfdl(a)gmail.com Guests Mike Beckerle - organizer frostmar(a)uk.ibm.com Mike Beckerle - optional smhdfdl(a)gmail.com - optional jens.jensen(a)stfc.ac.uk - optional alan.sill(a)ttu.edu - optional mbeckerle(a)owlcyberdefense.com - optional braddk(a)us.ibm.com - optional dfdl-wg(a)ogf.org - optional wiloneil(a)uk.ibm.com - optional wolfgang.ziegler(a)z-rands.de - optional View all guest info https://calendar.google.com/calendar/event?action=VIEW&eid=amJnNXNxYzdwZmlo… Reply for dfdl-wg(a)ogf.org and view more details https://calendar.google.com/calendar/event?action=VIEW&eid=amJnNXNxYzdwZmlo… Your attendance is optional. ~~//~~ Invitation from Google Calendar: https://calendar.google.com/calendar/ You are receiving this email because you are an attendee on the event. To stop receiving future updates for this event, decline this event. Forwarding this invitation could allow any recipient to send a response to the organizer, be added to the guest list, invite others regardless of their own invitation status, or modify your RSVP. Learn more https://support.google.com/calendar/answer/37135#forwarding

1 0

DFDL == ISO/IEC DIS 23415
by Mike Beckerle 22 Jan '24

22 Jan '24

Links: https://www.iso.org/standard/87444.html says we're in under development status https://www.iso.org/obp/ui/en/#iso:std:iso-iec:23415:dis:ed-1:v1:en Mike Beckerle Apache Daffodil PMC | daffodil.apache.org OGF DFDL Workgroup Co-Chair | www.ogf.org/ogf/doku.php/standards/dfdl/dfdl Owl Cyber Defense | www.owlcyberdefense.com

1 0

ISO JTC1 ballot approved !
by Mike Beckerle 22 Jan '24

22 Jan '24

Looks like ISO JTC1 has approved our PAS application. I am not sure what next steps are. Presumably we'll have to create a version of the spec in ISO preferred formatting style, and our branding may need to change some. ---------- Forwarded message --------- From: Wolfgang Ziegler <wolfgang.ziegler(a)z-rands.de> Date: Mon, Jan 22, 2024 at 3:50 AM Subject: Re: Any word from ISO JTC1? To: <mbeckerle(a)apache.org> Cc: GFSG Group <gfsg(a)ogf.org> Dear Mike, we finally received the notification from the JTC1 secretary. "Sorry for the late notification. The DIS ballot was approved 100%. I can now ask ISO to publish. I will let you know if I need anything from you." Congratulations! We'll get in contact with you, if ISO needs something additional for the publishing process. Best regards Wolfgang Am 09.01.24 um 22:50 schrieb Wolfgang Ziegler: > Dear Mike, > > Happy new year! > > We had a brief discussion in our GFSG meeting yesterday also and > I’ve sent a mail to Lisa and their colleagues asking for updates. > > I’ve got no response yet but I’ll inform you once I have more information. > > Best regards > > Wolfgang > > -- > Dr. Wolfgang Ziegler > z-rands > > Im tiefen Bruch 23, D-53773 Hennef, Germany > > Tel: +49 2242 80371 <tel:+49%202242%2080371>; Mobil: +49 151 50445303 > <tel:+49%20151%2050445303> > > StandICT - Supporting European Experts Presence in International Standardisation > Activities in ICT > www.standict.eu <http://www.standict.eu/>, www.linkedin.com/in/standict > <http://www.linkedin.com/in/standict>, > twitter: @Stand_ICT > >> Am 09.01.2024 um 22:13 schrieb Mike Beckerle <mbeckerle(a)apache.org>: >> >> >> Happy new year! >> >> Any news from the ISO/JTC1 folks? Any status we can get? >> >> Thanks >> >> Mike Beckerle >> Apache Daffodil PMC |daffodil.apache.org <http://daffodil.apache.org/> >> OGFDFDLWorkgroup Co-Chair | www.ogf.org/ogf/doku.php/standards/dfdl/dfdl >> <http://www.ogf.org/ogf/doku.php/standards/dfdl/dfdl> >> Owl Cyber Defense | www.owlcyberdefense.com < http://www.owlcyberdefense.com/> >> >> -- Dr. Wolfgang Ziegler z-rands www.z-rands.de Im tiefen Bruch 23, D-53773 Hennef, Germany Tel: +49 2242 80371; Mobil: +49 151 50445303 StandICT - Supporting European Experts Presence in International Standardisation Activities in ICT www.standict.eu, www.linkedin.com/in/standict, twitter: @Stand_ICT

1 0

ICU and dfdl:textNumberPattern issue
by Mike Beckerle 15 Jan '24

15 Jan '24

We've run into an issue with dfdl:textNumberPattern, which is an ICU number pattern. I'll discuss here, and then suggest this is a fix needed in DFDL generally, but we should discuss that hypothesis. The motivating example is fixed length 5 character integer text data. The data ranges from -9999 to 99999. Note that the minus sign uses up one of the 5 characters that can be a digit for positive values. Consider the value -123 and textNumberPattern of "00000;-0". The value unparses as -00123 which is length 6 so too long. The padding feature of ICU number patterns can be used to "fix" this. Consider textNumberPattern="*0####0". The "*0" notation means to use 0 as the padding character to replace the "#" when needed. Now the value 123 unparses as 00123 but ... here's the problem.... -123 unparses as 0-123. Notice how the zero padding is before the minus sign when we wanted it to appear after. This problem is caused by ICU taking nearly all the information from the positive part of the textNumberPattern. The negative part of the pattern, if it exists, is used only to define the affix (prefix or suffix or both) that indicate negative values. The problem is that positive numbers commonly have no affix, so the position of padding characters relative to the affix cannot always be determined from the positive pattern alone. Hence, if textNumberPattern specifies a pad character before the number pattern and without a positive prefix, then ICU defaults to a pad position of PAD_BEFORE_PREFIX with no way to change it with just the pattern. This behavior is reasonable for most cases, like when the pad character is a space. However, if the pad character in textNumberPattern is '0', then negative numbers are padded with a '0' before the negative sign. So we get the errant behavior where a pattern of "*0####0" unparses -123 to "0-123". This is very unlikely to be what the user wants with this pattern. Now suppose the positive pattern required a prefix "+" sign. The textNumberPattern of "+*0####0" works properly because ICU determines that the padding is PAD_AFTER_PREFIX from the positive pattern where the "*0" is after the "+" prefix. The proposed fix to this issue that we're implementing in Daffodil is this: If both negative and positive patterns define padding on the same affix, and the positive pattern has an empty string for that affix, then we use the pad position from the negative pattern. In all other cases, the pad character in the negative pattern is ignored following usual ICU behavior. For example, a textNumberPattern of "*0####0;-*00" formats a negative number with zero padding after the hyphen, whereas normal ICU behavior would ignore the negative pattern and zero pad before the hyphen. I would suggest this is something that is a needed fix in general for DFDL. The workaround when you have the fixed length number use case (-9999 to 99999) is very ugly, treating the minus sign as an initiator and creating separate elements for positive and negative values, or punting on this integer and treating the whole thing as a string. Arguably, this might be considered an ICU bug, but ICU's API can be used to specify the PAD_AFTER_PREFIX behavior, so it's not like ICU doesn't let you achieve the needed behavior, it's just not something that can be achieved using only the ICU pattern string. But ICU maintainers may or may not consider this to be a bug. Mike Beckerle Apache Daffodil PMC | daffodil.apache.org OGF DFDL Workgroup Co-Chair | www.ogf.org/ogf/doku.php/standards/dfdl/dfdl Owl Cyber Defense | www.owlcyberdefense.com

2 2

Confirming DFDL Workgroup call today (2024-01-11)
by Mike Beckerle 11 Jan '24

11 Jan '24

Hope to see you there. I will, hopefully, send out agenda in advance.

1 1

spec bug: Figure 4
by Mike Beckerle 11 Jan '24

11 Jan '24

Section 13.6.1.1, Figure 4: dfdl:textNumberPattern BNF Syntax has a line: vinteger := ('#'* '0'* 'V' '0'* '0') | (integer 'V') prefix := '\u0000'..'\uFFFD' - specialCharacters This is missing a line ending before "prefix", which is a separate production of this BNF grammar. Mike Beckerle Apache Daffodil PMC | daffodil.apache.org OGF DFDL Workgroup Co-Chair | www.ogf.org/ogf/doku.php/standards/dfdl/dfdl Owl Cyber Defense | www.owlcyberdefense.com

2 2

clarification - argument expression to fn:count() function
by Mike Beckerle 11 Jan '24

11 Jan '24

The description of fn:count in section 18.5.2.5 says fn:count() can be called on a node-sequence. It does not seem to require an array/optional path. This seems to be suggesting that if you have say.... <element name="b" type="xs:int"/> <element name="a" type="xs:int"/> <element name="b" type="xs:int" minOccurs="0"/> That one could write fn:count(b) and it should return 1 or 2. The Daffodil project calls this a "query-style" expression, as opposed to just a basic path expression. Furthermore, in the first paragraph of section 18.5.2.5 it says "(Note that DFDL v1.0 does not support sequences of length > 1 as the final results of expressions.)" which suggests that some expressions can constructively return node sequences of length > 1 as intermediate results. Presumably fn:count(b) above is such a situation, as the expression 'b' returns 2 nodes. The above all suggests to me that fn:count(a) would be legal where 'a' is a scalar. This is just always 1 of course. But Section 35 says: Expression value is not single node § Most DFDL expression contexts require an expression to identify a single node, not an array (aka sequence of nodes). There are a few exceptions such as the fn:count(…) function, where the path expression must be to an array or optional element. o Expression value is not array element or optional element. § Some DFDL expression contexts require an array or an optional element. § Example: The fn:count(...) function argument must be to an array or optional element. It is a Schema Definition Error if the argument expression is otherwise. Experience at the Daffodil project is that allowing fn:count argument expression to be a non-array non-optional element, where fn:count would always return 1, just hides errors that are very hard to find, and this situation comes up often as a schema is written. Usually the expression to fn:count is initially correct with an array/optional as the argument, but element nesting evolves, and the paths need updating, but end up referring not to the array/optional element, but that name is now of a scalar enclosing element of the array, so the fn:count is always 1, and the schema is incorrect because the expression is not doing what is intended, but no error is detected. This is then quite hard to isolate and fix. A concrete example of this experience is you start with a schema like: <element name="record" maxOccurs="unbounded"> <complexType> <sequence> .... elements of the record But then you need the valueLength of the whole array of all the records, to store the length for unparsing, so you revise this to: <element name="record"> <complexType> <sequence> <element name="item" maxOccurs="unbounded"/> <complexType> <sequence> .... elements of each record 'item'. And now, paths you had like fn:count(foo/bar/record) are no longer to an array, they are to a scalar, so always return 1. This is decidedly unhelpful in a large schema. It is far better if fn:count(foo/bar/record) becomes an SDE because record is now scalar. So the clarification I'm seeking is whether section 35 was just missed when updates were made about this node-sequence stuff, or if it is reasonable to implement the restrictions in Section 35. I am biased. I want the restrictions in Section 35, but this was muddy enough that I thought we should get a clarification first. Daffodil already doesn't implement any query-style expressions so the fn:count(b) example above would be an SDE in Daffodil. Mike Beckerle Apache Daffodil PMC | daffodil.apache.org OGF DFDL Workgroup Co-Chair | www.ogf.org/ogf/doku.php/standards/dfdl/dfdl Owl Cyber Defense | www.owlcyberdefense.com

2 1