Subject: Re: [Cbor] CDDL: Solving the regexp issue

From: Sean Leonard <[email-masked]>
Date: Tue, 20 Mar 2018 06:22:14 -0700

I have been meaning to respond to this, sorry for the long lag time.

I disagree strongly with the dependency on XSD Regular Expressions.
The primary technical argument is that XSD REs incorporate the 
definition of "XmlChar" (see also "normal character") aka XML character, 
which is extraordinarily convoluted (and does include certain ranges of 
Unicode code points, yet does not actually include all Unicode code 
points). Another such instance of Unicode accretion is "IsBlock", which 
allows for regular expressions that go through the Unicode Blocks.txt, 
which in combination with other Unicode source material, is not a 
reasonable dependency for smaller devices.

~~Proposal~~
My (tentative) proposal instead is to focus on POSIX Extended Regular 
Expressions instead:
http://www.boost.org/doc/libs/1_50_0/libs/regex/doc/html/boost_regex/syntax/basic_extended.html
https://en.wikibooks.org/wiki/Regular_Expressions/POSIX-Extended_Regular_Expressions
http://pubs.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap09.html#tag_09_04

Technical arguments:
* POSIX EREs appear to be a strict subset of Perl regular expression and 
PCRE technology. For example, POSIX character classes [:digit:] == \d 
are supported by PCRE. XSD does not support this.
* AFAICT, there are no droppings from Unicode in the way that exist in 
XSD REs.
* It means that the text can still refer to PCRE as an expectation 
(which aligns with RFC 7049), while defining a normative minimum 
conformance requirement.

Non-technical arguments:
* There is a valid normative reference for it.
* POSIX ERE as a normative base doesn't actually change CDDL "v1.0" from 
"v0.x". Changing to XSD would actually change things, which (in my view) 
would then have to be changed back.

Furthermore, there was impetus at the November meeting to remove syntax 
elements such as regular expressions from quoted strings, making them 
first-class parts of the grammar. This promotes readability and allows 
syntax highlighters the ability to highlight and validate such parts.

So the text (taken from draft-greevenbosch-appsawg-cbor-cddl-11, prior 
to the XSD change) is proposed to read:

3.8.3.  Control operator .regexp

    A ".regexp" control indicates that the text string given as a target
    needs to match the regular expression given as a value in the
    control type. POSIX Extended Regular Expressions are always supported.
    PCRE and its full syntax are recommended as an implementation choice,
    since [RFC7049] itself specifies PCRE.

                  nai = tstr .regexp /^[:word:]+@[:word:]+(.[:word:]+)+$/

                    Figure 9: Control with a POSIX ERE / PCRE regexp

    The CDDL tool proposes:

                        "[email-masked]"

Respectfully submitted,

Sean

On 1/24/2018 12:04 PM, Carsten Bormann wrote:
> At IETF 100, we had a another discussion about regular expressions.
> I don’t think we went home with a clear idea of how to solve this problem.
> Giving up and just not doing regular expression in the first version of CDDL certainly was one choice.
> But, since, there has been time to analyze the issue some more.
>
> Here is a proposal for addressing the regexp issue:
>
> https://cbor-wg.github.io/cddl/matching/draft-ietf-cbor-cddl.html#rfc.section.3.8.3
>
> Why use XSD REs?
>
> * There is a valid normative reference for them.
> * There is precedent for using XSD REs in IETF specifications, e.g. in YANG (RFC 7950).
> * They actually have been designed for the kind of use we are employing them for (albeit in an XML context).
> * There are no undesirable UTF-16 droppings in XSD REs, as there would have been in JavaScript REs.
>
> The solution proposed works quite well and allows us to have a reasonable .regexp in the 1.0 CDDL RFC.
> (It is just a tad less straightforward to implement than PCRE was.  Oh well.)
>
> We can always add more controls for other RE types later.  (This also provides a powerful incentive to continue coupling REs with the main extension point for the CDDL language: controls.)
>
> Grüße, Carsten
>
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Jim Hague <[email-masked]>
Date: Thu, 22 Mar 2018 19:11:17 +0000

> are supported by PCRE. XSD does not support this.

POSIX ERE's aren't quite a strict subset of PCRE (which in turn AIUI aren't in 
fact 100% Perl-compatible). Specifically, POSIX always looks for the longest 
of a left-most match while PCRE stops on the first valid match. Friedl gives 
the example pattern 'one(self)?(selfsufficient)?' matching the string 
'oneselfsufficient' - PCRE matches 'oneself' while POSIX ERE matches 
'oneselfsufficient'.

XSD isn't wonderful, but comparing the differences between XSD, POSIX ERE and 
PCRE2 via  https://www.regular-expressions.info/refbasic.html I have to 
(reluctantly) conclude that for a normative reference XSD is closer match for 
basic regex use, while quietly praying that everyone actually implements a 
PCRE2 option.
-- 
Jim Hague - [email-masked]          Never trust a computer you can't lift.

---

From: Sean Leonard <[email-masked]>
Date: Thu, 22 Mar 2018 14:12:04 -0700

> On Mar 22, 2018, at 12:11 PM, Jim Hague <[email-masked]> wrote:
> 

Hi Jim,

This is a well-stated technical argument so I appreciate that.

I looked closely at the pattern matching, however, and find some flaws that need to be addressed.

First of all, the Friedl example pattern you gave:
> one(self)?(selfsufficient)?

matches the following strings (irrespective of greediness):

one
oneself    => $1 = “self”
oneselfsufficient  => $1 = “” $2 = “selfsufficient”)
oneselfselfsufficient  => $1 = “self” $2 = “selfsufficient”
oneselfselfsufficiently  => $1 = “self” $2 = “selfsufficient”

So, with respect to the input:

> oneselfsufficient

the first three strings:
one
oneself
oneselfsufficient

all potentially match. Which one is returned depends on the implementation.

I ran the differences through some online regex analyzers, my local bash prompt, and RegexBuddy v4 (tests pretty much everything under the sun: a very worthwhile tool).

POSIX ERE does indeed look for the longest of the leftmost match (matches “oneselfsufficient”); PCRE stops on the first valid match (matches “oneself”).

But running the test on “XML Schema” matches “oneselfsufficient”, not “oneself”! So actually the XSD reliance itself is problematic. The reason appears to be because XSD has no concept of anchoring. Further inspection reveals that that XSD also does not support word boundaries or lookaround. These flaws, in combination with the “Unicode droppings”, just hammer the nails in the coffin for XSD in my mind.

The better way forward now appears to be go to back to PCRE/PCRE2, and just deal with the reference issue directly.

On that front, PCRE/PCRE2 are BSD 2-clause licensed. There is also the public documentation:
https://www.pcre.org/pcre2.txt

which itself ought to suffice for documentation. I mean, the ZIP file format is standardized across many SDOs (including this one) based on PKWare’s APPNOTE.txt, so I see reliance on pcre.txt/pcre2.txt as better than that situation. See also pcresyntax, pcrepattern.

Sean

---

From: Jim Hague <[email-masked]>
Date: Wed, 28 Mar 2018 16:09:08 +0100

Hi Sean,

Apologies for the delay in responding.

On Thursday, 22 March 2018 21:12:04 BST Sean Leonard wrote:
> I ran the differences through some online regex analyzers, my local bash
> prompt, and RegexBuddy v4 (tests pretty much everything under the sun: a
> very worthwhile tool).
> 
> POSIX ERE does indeed look for the longest of the leftmost match (matches
> “oneselfsufficient”); PCRE stops on the first valid match (matches
> “oneself”).
> 
> But running the test on “XML Schema” matches “oneselfsufficient”, not
> “oneself”! So actually the XSD reliance itself is problematic. The reason
> appears to be because XSD has no concept of anchoring.

I've been playing directly with xmllint, and I see what you mean. I'd perhaps 
characterise it in PCRE terms as XSD having implicit anchors at start and end 
of the pattern. In other words, a XSD pattern "XML" would need to be expressed 
as PCRE "^XML$" to give the same effect.

I've also realised that (as far as I can see), POSIX ERE's longest leftmost 
match isn't the problem I thought it was, beyond some potential inefficiency 
(as a true POSIX engine will have to exhaust every possible option looking for 
the longest possible match). In the context of CDDL, the only question is 
'does the entire regexp match' - the contents of subexpressions cannot be 
retrieved, and so my example from Friedl is not relevant.

It also occurs to me that I've so far been thinking of CDDL as a specification 
notation rather than a mechanism for ongoing validation of input or output 
(where limited environments are important).
 
> Further inspection
> reveals that that XSD also does not support word boundaries or lookaround.
> These flaws, in combination with the “Unicode droppings”, just hammer the
> nails in the coffin for XSD in my mind.

I'm not sure I'd be overjoyed at being stuck with POSIX ERE word boundary 
expressions, myself. And I can understand why some might find Unicode matching 
in XSD useful. Lookaround might be nice to have, definitely.

> On that front, PCRE/PCRE2 are BSD 2-clause licensed. There is also the
> public documentation: https://www.pcre.org/pcre2.txt
> 
> which itself ought to suffice for documentation. I mean, the ZIP file format
> is standardized across many SDOs (including this one) based on PKWare’s
> APPNOTE.txt, so I see reliance on pcre.txt/pcre2.txt as better than that
> situation. See also pcresyntax, pcrepattern.

Being a relative newbie to the IETF process, I have to defer to others on what 
might constitute a proper normative reference. I'm certainly not convinced 
that POSIX ERE is a big win over XSD. PCRE(2) would be definite plus for me, 
if only on familiarity grounds, but if it's not immediately possible then I 
think I'd hope for it in future rather than delay WGLC.
-- 
Jim Hague - [email-masked]          Never trust a computer you can't lift.

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 29 Mar 2018 08:20:22 +1300

On 29/03/2018 04:09, Jim Hague wrote:
...
> (where limited environments are important).

Yes. The question "Does this CBOR bytestring match that CDDL specification?"
is much harder than "Does this CDDL specification say what I mean?"
It's also, I think, out of scope according to the current CDDL draft:
  "The main goal for the convention is to provide a unified notation
   that can be used when defining protocols that use CBOR.  We term the
   convention "Concise data definition language", or CDDL."

(I'm not sure this helps to decide on a regexp reference, however.)

...
> might constitute a proper normative reference.

The reality is that once you get outside both RFCs and formal documents from
other well-established standards organizations, it becomes a matter of judgment
and YMMV, and persuading the IESG that it's OK.

   Brian

---

From: Jeffrey Yasskin <[email-masked]>
Date: Wed, 28 Mar 2018 23:45:45 +0000

On Wed, Mar 28, 2018 at 12:20 PM Brian E Carpenter <
[email-masked]> wrote:

> ....

I strongly disagree with the claim that these are different questions. :)
If a specification doesn't say exactly which bytestrings are allowed, then
it encourages non-interoperable implementations and possibly security
vulnerabilities in the gaps between those implementations, which isn't
acceptable in the modern world. If CDDL doesn't define exactly which
bytestrings match a CDDL specification, then CDDL is not useful for modern
specifications.

Jeffrey

> ....

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 29 Mar 2018 10:39:03 +0900

Hi Jeffrey,

this is an interesting train of thought.

Most of the specifications in the network space use the English language, sometimes aided by some illustrations or ad-hoc notation, to specify what is the protocol.

Another observation is that the focus of protocol specification has moved from compliance to interoperability.

There is a limited return from specifying compliance in a more rigid way.  Where it is easy to do (and, in particular, where we have usable formal description techniques such as ABNF), we of course should do it.  But arguing that all protocol specification must be done in a formally watertight way leads nowhere good.  (As an example, we still have English language parts in many ABNF specifications.)

Now what is CDDL about?  It is intended as a formal description technique, and the intention is to occupy about the same space for tree-structured data that ABNF occupies for textual data.  So I would indeed expect that it can be decided in an unambiguous way whether a data item serialized in CBOR (or JSON) is matched by a CDDL spec or not.  I also would expect the language to be quite usable during a time when we still figure out some corner cases of this (but we should work on figuring them out, and of course fix what we already know).

A completely different question is whether a validator that checks each incoming data item against a CDDL specification is desirable or not.  The majority of implementations of protocols specified in ABNF are not directly interpreting or generated from that ABNF.  I would expect the situation to be similar for CDDL.  

That said, I have written two ANBF parser generators and one-and-a-half CDDL validators in my life so far, so I definitely think there is space for appropriate tools.  I just don’t think that tool implementation considerations should be overriding concerns for the development of the CDDL language — it should focus on the quality of the specifications that can be made while using it.  (As an example, the fact that XSD regexps have less viable implementations available than PCRE or Posix concerns me less than the question which of these formats can be best used for specification, which includes non-technical concerns such as stable reference.)

Grüße, Carsten

---

From: Brian E Carpenter <[email-masked]>
Date: Thu, 29 Mar 2018 14:56:49 +1300

> bytestrings match a CDDL specification, then CDDL is not useful for modern

I wasn't clear. I didn't mean that the question "Does this bytestring match
the specification?" is *unanswerable*. I meant that writing a general-purpose
syntax-driven verifier is hard - as hard as writing any general recursive-descent
syntax checker. For my own rather trivial CDDL use case, I tried but gave up and
wrote a very ad hoc parser instead.

(Of course you can use Carsten's tools but I think he'll agree they have some
limitations.)

    Brian

---

From: Sean Leonard <[email-masked]>
Date: Wed, 28 Mar 2018 23:00:04 -0700

> (Of course you can use Carsten's tools but I think he'll agree they have some

I need to spend more time making a formal proposal, but I want to make 
some preliminary observations.

When writing grammars that are implemented in actual products (as 
opposed to academic exercises), there is a tension between "descriptive" 
-- these are the ways to express valid protocol units -- and 
"prescriptive" -- the sender or receiver MUST do such and such, or MUST 
NOT do such and such (the consequence of violating the latter, is 
prescribed, or proscribed, as the case may be). In many ways, it is the 
difference between Markdown on the descriptive side, and XML on the other.

The problem with XML and its associated desiderata (XML schemas, etc.) 
is that they are too rigid and complicated. The specs are super-long and 
processors need to follow a large set of arcane rules that result in 
utter failure to ingest any part of the data structure if there is so 
much as one character that is out-of-place.

CDDL has "DESCRIPTIVE" in the name so generally I am more aligned with 
Carsten's interpretation as a formal description technique. I would also 
add to this, that CDDL in its current form is not so rigid about 
validating productions as a parser. That is a good thing because it 
means that a lot of ambiguous cases don't have to result in fatality. 
The counterargument that it affects "security" does not hold much water 
for me because things that are ambiguous, need to be considered 
ambiguous when doing a security analysis.

To the extent that CDDL is used as a validator, such a validator should 
output a validated production to the smallest possible unit that it can, 
and ignore or "red-flag" 🚩 the smallest possible invalid parts, rather 
than failing validation entirely.

Just to pick out one area: it has always struck me that CBOR groups with 
respect to maps (and arrays) should be considered open-ended. Consider 
the CDDL:

                              person = {(
                                age: int,
                                name: tstr,
                                employer: tstr,
                              )}

Now consider the CBOR (diagnostic notation):

     {"age": 6, "name": "Foobar", "employer": "Akamai", 
"favouriteDrink": "Pepsi"}

The CBOR could have been produced by an earlier spec of person, that 
later got augmented. (That is what /= and //= are for.) It seems to me 
that a CDDL-based parser that is trying to figure out whether the input 
matches the CDDL grammar, should output this:

     {"age": 6, "name": "Foobar", "employer": "Akamai", 
†("favouriteDrink": "Pepsi")}

where † (dagger) means "red-flag". What I mean by red-flag is, "this 
part wasn't part of the CDDL spec but it's still there so you can just 
ignore it, or you can try to deal with it at a higher software layer, 
but you are on your own". A reasonable output with the red-flagged 
elements removed would be:

     {"age": 6, "name": "Foobar", "employer": "Akamai"}

...which, of course, would be a production that could have come from the 
original CDDL.

Keeping the red-flagged content in the output is also sensible, so that 
a higher software layer can try to poly-fill in functionality that the 
lower layer was not compiled to have knowledge of at the time (for 
example, if the lower layer is some system library).

As a second example, consider the CBOR (diagnostic notation):

     {"age": null, "name": "Foobar", "employer": "Akamai"}

It's a more interesting case, because "age" is a valid key but int 
doesn't match null. A reasonable output could be:

     {"age": †(null), "name": "Foobar", "employer": "Akamai"}

This is because null doesn't match int, but "age" matched. The 
application will have to figure out what to do with the structure in the 
absence of a required item, but it is still "useful" in that the 
application can still extract the other map elements. Bear in mind that 
the /= operator in CDDL can augment age in an additional spec, by 
allowing null to appear in that position. Therefore †(null) is a quite 
sensible result. However, the problem is that if †(null) is stripped 
out, you are left with invalid CBOR since a key has to have a value.

Another way to deal with it would be:

     {†("age": null), "name": "Foobar", "employer": "Akamai"}

Namely: ignore the age key/value pair entirely--treat it as if it were 
absent (as opposed to "age" being present but the value being absent). 
However, if "age": null is stripped, the production as a whole doesn't 
comply with the CDDL grammar.

This leads us to the next possibility: which would be:

†({"age": null, "name": "Foobar", "employer": "Akamai"})

Which means that the entire production does not match, because age is a 
required key/value pair, and a matching production is not present. This 
might seem like the best from a "security" standpoint, but it could lead 
to denial-of-service.

Now consider this CDDL instead:

                              person = {(
                                ? age: int,
                                name: tstr,
                                employer: tstr,
                              )}

And our CBOR:
     {"age": null, "name": "Foobar", "employer": "Akamai"}

In this case, I can more confidently say that the red-flagged output of 
a CDDL parser should be:
     {†("age": null), "name": "Foobar", "employer": "Akamai"}

because "age": null does not match age: int, but age: int is optional, 
so the red-flag-stripped CBOR:
     {"name": "Foobar", "employer": "Akamai"}

would be a production generated from the original CDDL grammar.

For those with ASN.1 experience (shudder), consider that ASN.1 
specifications are CLOSED by default. If you say:

     SomeStruct ::= SEQUENCE {
         foo INTEGER,
         bar IA5String
     }

Then you can never expand the SEQUENCE in future versions of the 
protocol. Early specs dealt with this by saying "ANY DEFINED BY (some 
OID or integer)"; later on, open types and templates were developed. 
Then came "extensibility", aka the ellipsis:

     SomeStruct ::= SEQUENCE {
         foo INTEGER,
         bar IA5String,
         ...
     }

which means more-or-less what is being proposed above: if there is 
extraneous ASN.1 data after the bar IA5String, don't error out, but just 
ignore it and maybe when you update your software we will be able to 
make some sense out of it. It has now come to the point that ASN.1 
people recommend using ellipses all over the place, or just throwing 
your hands up and turning it on with EXTENSIBILITY IMPLIED. See 
<http://lionet.info/asn1c/blog/2010/09/21/question-extensibility-removing-fields/>.

I would like to think that a good CDDL parser would try to cope with a 
reasonable spectrum of productions, including productions from future 
versions. Red-flagging the smallest sub-production unit that is 
out-of-CDDL-spec is one such way to resolve the tension between the two.

Please do not burn down my straw man before I put the rest of the 
bundles of hay together. :) Just think about it.

Best regards,

Sean

---

From: Pete Cordell <[email-masked]>
Date: Thu, 29 Mar 2018 11:23:29 +0100

On 29/03/2018 00:45, Jeffrey Yasskin wrote:
> On Wed, Mar 28, 2018 at 12:20 PM Brian E Carpenter 
> <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     .....
> I strongly disagree with the claim that these are different questions. 
> :) If a specification doesn't say exactly which bytestrings are allowed, 
> then it encourages non-interoperable implementations and possibly 
> security vulnerabilities in the gaps between those implementations, 
> which isn't acceptable in the modern world. If CDDL doesn't define 
> exactly which bytestrings match a CDDL specification, then CDDL is not 
> useful for modern specifications.

I think there is a distinction between the two, but it is a small one. 
The main issue with the above paragraph is the word "exactly".

A human reader should be allowed to be as pedantic as a computer in 
their interpretation of the CDDL.

The difference is that the human can also read the comments!  So you can 
have:

    email = tstr .regexp "[^\\s@]+@\\S+(\\.\\S+)+" ; see RFC 5322

So, as with ABNF, you can have a slightly looser definition in the CDDL 
that is still useful (not least because it allows you to be exact about 
the other 99% of the spec that can be accurately expressed), while also 
making it clear that there is slightly more pedantry to be dealt with in 
higher layers of software than the specification language can express.

In some ways, the question "Does this CBOR bytestring match that CDDL 
specification?" is much EASIER than "Does this CDDL specification say 
what I mean?" because you can come up with CDDL that will match any CBOR :-)

Pete.
-- 
---------------------------------------------------------------------
Pete Cordell
http://json-content-rules.org Rule :-)
---------------------------------------------------------------------

---

From: Jeffrey Yasskin <[email-masked]>
Date: Thu, 29 Mar 2018 17:31:11 +0000

> wrote a very ad hoc parser instead.

Ah, yep, I agree with you here. Sorry for misunderstanding. I also expect
most implementations of protocols specified using CDDL to use custom
parsers rather than sharing a generic CDDL parser.

> higher layers of software than the specification language can express.

I also agree with this: it's definitely useful for CDDL to accept a
superset of the bytestrings the protocol actually intends to accept, with
English used to specify which subset is actually accepted. It's only a
problem for the CDDL to be ambiguous about which strings it accepts.

Jeffrey