Subject: [Cbor] Using cddl-control to dissect byte strings

From: Christian Amsüss <[email-masked]>
Date: Fri, 30 Jul 2021 13:36:04 +0200

Hi,

continuing my theme of creatively abusing CDDL constructs, I may have
found a practical use case for .cat that is not just about constants
handling.

(The usual caveats for these tricks apply: While CDDL has the
expressitivity to do it, common tools WILL PROBABLY NOT implement the
full genericness).

In EDHOC, a byte shaving step may require moving two semantically
separate byte strings, one of which has known length, into a single byte
string; in a minimal similar example:

    message = [(number: uint, key: bstr, data: bstr)]

becomes

    message = [(number: uint, key_and_data: bstr)]

Unfortunately, this means parsers built from the CDDL will need an
additional manual step in which the implementer writes down the prose
description of key_and_hash into code that splits key from hash.

With cat, this can be expressed in a way that the CDDL parser generator
has a chance to do the right thing again:

    message = [(number: uint, key .cat data)]
    key = bstr .size 16
    data = bstr

As the length depends on earlier exchanged messages, one might use
generics to pull out the constant of 16 -- probably breaking the tool's
neck in the process: (Carsten's Ruby generator tool is still with me on
this)

    message_alg42 = message<4>
    message<L> = [(number: uint, key<L> .cat data)]
    key<L> = bstr .size L
    data = bstr

I don't know at this point whether any form of this should be suggested
for use with EDHOC if and when the byte shaving change is performed.

Opinions from CBOR?

Thanks
Christian

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 30 Jul 2021 13:55:36 +0200

I think the subject of this message should be 

## Using cddl-control to make CBOR even less schema-less

But indeed, what you propose is one way to compose your byte strings, if you *have* to do it.

I’d probably use .abnfb for many of these; at least if (like in this example) you don't need to go back to CDDL names (which is a shortcoming I have a plan for, but that will happen later this year).

You mentioned the cddl tool generator — does the validator choke on this?

(I don’t want to think about .det here.)

(BTW: I would like to fix one bug in the generics implementation before we aggressively market the use of generics to the CDDL user crowd.)

(BTW^2: Why the [()]?  It does look very important, but maybe not necessary?)

Grüße, Carsten

> On 2021-07-30, at 13:36, Christian Amsüss <[email-masked]> wrote:
> 
> Signed PGP part
> Hi,
>

---

From: Christian Amsüss <[email-masked]>
Date: Fri, 30 Jul 2021 14:43:28 +0200

> ## Using cddl-control to make CBOR even less schema-less

An action from this very fitting observation could be to decorate any
use of such a construction with text like:

| This concatenation touches the fringes of CBOR applicability: We
| sacrifice discernible CBOR structure to save off single bytes, which
| runs counter to CBOR's priorization of being schemaless over
| serialization compactness {{Section E of RFC8949}}. This approach is
| not recommended for general use without clear size boundaries that
| need to be met.

> I’d probably use .abnfb for many of these; at least if (like in this
> example) you don't need to go back to CDDL names (which is a
> shortcoming I have a plan for, but that will happen later this year).

I'm curious to see that.

(For this particular case, ABNF might not easily cut it, for the string
length will only be known at runtime, and the steps to get the generic
length into the ABNF processor will make this exercise look tame in
comparison).

> You mentioned the cddl tool generator — does the validator choke on this?

    $ cat minhoc.cddl
    message_alg42 = [message<4>]
    message<L> = (number: uint, key<L> .cat data)
    key<L> = bstr .size L
    data = bstr
    $ cddl minhoc.cddl generate | tee minhoc.diag
    [1146, h'B3BFE8437065727369737473']
    $ diag2cbor.rb minhoc.diag > minhoc.cbor
    $ cddl minhoc.cddl validate minhoc.cbor
    CDDL validation failure
    [ full output at the end of the mail ]

> (I don’t want to think about .det here.)

For purposes of parser building (which is even stricter than validation,
for validation probably doesn't need to find a *unique* assignment),
there are reversible and irreversible controls; det is just
irreversible, as is `bstr .cat bstr` without further constraints.

> (BTW^2: Why the [()]?  It does look very important, but maybe not

Just an effect of me editing around; needless, and fixed in current
example.

BR
c

---

CDDL validation failure (nil for [1146, "\xB3\xBF\xE8Cpersists"]):
["\xB3\xBF\xE8Cpersists",
 [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]],
 "\n" +
 "occur 0 < 1, not reached at 1 in array [1146, \"\\xB3\\xBF\\xE8Cpersists\"] for [:array, [:member, 1, 1, [:text, \"number\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]][\"\\xB3\\xBF\\xE8Cpersists\", [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]], \"\\noccur 0 < 1, not reached at 1 in array [1146, \\\"\\\\xB3\\\\xBF\\\\xE8Cpersists\\\"] for [:array, [:member, 1, 1, [:text, \\\"number\\\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]]\"] -- cannot complete (false, 2) array [1146, \"\\xB3\\xBF\\xE8Cpersists\"] for [:array, [:member, 1, 1, [:text, \"number\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]]"]
[h'B3BFE8437065727369737473', [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]], "\noccur 0 < 1, not reached at 1 in array [1146, \"\\xB3\\xBF\\xE8Cpersists\"] for [:array, [:member, 1, 1, [:text, \"number\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]][\"\\xB3\\xBF\\xE8Cpersists\", [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]], \"\\noccur 0 < 1, not reached at 1 in array [1146, \\\"\\\\xB3\\\\xBF\\\\xE8Cpersists\\\"] for [:array, [:member, 1, 1, [:text, \\\"number\\\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]]\"] -- cannot complete (false, 2) array [1146, \"\\xB3\\xBF\\xE8Cpersists\"] for [:array, [:member, 1, 1, [:text, \"number\"], [:prim, 0]], [:member, 1, 1, nil, [:anno, :cat, [:anno, :size, [:prim, 2], [:int, 4]], [:prim, 2]]]]"]

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 30 Jul 2021 15:45:26 +0200

>> You mentioned the cddl tool generator — does the validator choke on this?
[…]
>    CDDL validation failure

Yeah, I just looked at the code I wrote 2020-11-17.
The generator is fine, the validator focuses on the case where both lhs and rhs are single value (“extractable”) types; it probably should have a better message than “?” for when that is not the case.

> irreversible, as is `bstr .cat bstr` without further constraints.

`bstr .cat bstr` is rather easy to match :-)

In this case, there simply is ambiguity where the bytes go (and the number of solutions is exactly the number of input bytes).
(It is not quite clear how to apply “preferred choice” here; greedy matching might be the equivalent.
Hope that uncertainty doesn’t stop us from going forward with .cat.)

Parsing (as opposed to matching) regexps have greedy and non-greedy occurrence indicators to disambiguate various use cases of this.
But the complexity of regexp code is exactly what I wouldn’t want in CDDL…

So I’d stick with the observation that you can write CDDL that tools will have trouble with.  I’d like to be able to cover at least

(bstr .size nn) .cat bstr
and
bstr .cat (bstr .size nn)

in a future version of the tool, but as soon as nn is a multi-value type (e.g., range), we’d need to invoke preferred choice again.

Grüße, Carsten

---

From: Christian Amsüss <[email-masked]>
Date: Fri, 30 Jul 2021 16:36:04 +0200

Hello,

> Hope that uncertainty doesn’t stop us from going forward with .cat.)

I don't think so.

First, it talks about validation and not parsing/matching, and there
ambiguity is fine.

And the, it already points out that tooling support is expected to be
limited once the arguments to .cat are not literals.

> But the complexity of regexp code is exactly what I wouldn’t want in CDDL…

I don't see a need to go out of our ways to accommodate creative abuses.
Whoever wants to use it more seriously for these purposes is still
welcome to define controls that suit their needs (but may find that they
don't gain wide traction due to the new complexity).

BR
c

-- 
Beware paths which narrow future possibilities. Such paths divert you
from infinity into lethal traps.
  -- Leto Atreides II