Subject: [Cbor] List of not-well-formed CBOR and test vectors

From: Laurence Lundblade <[email-masked]>
Date: Mon, 29 Jul 2019 11:49:18 -0700

I think I’ve made a comprehensive list of all things that are not well formed by going through the latest draft and my decoder. There are about a dozen of them. I’ve also created 110 test vectors that cover them pretty thoroughly. 

Everything is here <https://github.com/laurencelundblade/QCBOR/blob/not_well_formed/test/not_well_formed_cbor.h> in a C header. The dozen types of non-well-formedness are listed as comments in the header file. The test vectors are in an array that can be used for testing. It is BSD-3 license.

I’ve turned up one bug in the RFC’s pseudo code. It doesn’t catch an indefinite length string as a segment in another indefinite length string. 

I’d like to get some review, some folks to try it out and such to see if I’ve missed anything and all is right. When that is done I’ll make a pull request for the draft out it. Probably in about two weeks.

So please look it over and try it against your implementation.

LL

---

From: Thiago Macieira <[email-masked]>
Date: Mon, 29 Jul 2019 12:24:47 -0700

On Monday, 29 July 2019 11:49:18 PDT Laurence Lundblade wrote:
> I think I’ve made a comprehensive list of all things that are not well
> formed by going through the latest draft and my decoder. There are about a
> dozen of them. I’ve also created 110 test vectors that cover them pretty
> thoroughly.
> 
> Everything is here
> <https://github.com/laurencelundblade/QCBOR/blob/not_well_formed/test/not_w
> ell_formed_cbor.h> in a C header. The dozen types of non-well-formedness are
> listed as comments in the header file. The test vectors are in an array
> that can be used for testing. It is BSD-3 license.
> 
> I’ve turned up one bug in the RFC’s pseudo code. It doesn’t catch an
> indefinite length string as a segment in another indefinite length string.
> 
> I’d like to get some review, some folks to try it out and such to see if
> I’ve missed anything and all is right. When that is done I’ll make a pull
> request for the draft out it. Probably in about two weeks.

Hello Laurence

I'll add your test vectors to TinyCBOR soon and see if there's anything I 
didn't catch. You're welcome to do the same with my test data, see:
https://github.com/intel/tinycbor/blob/dev/tests/parser/tst_parser.cpp#L1538-L1767

There are 194 entries in that list, though some of them are slightly duplicate 
of one another. There are a couple that also test implementation limits, like 
strings bigger than half your machine's address space. Some others aren't 
testing invalid CBOR, but common parsing mistakes like reading a size of -1 or 
overflowing counters / pointers.

Another that I came across but isn't seen in the test list was that my buffer 
was always followed by a NUL byte, which masked one read-past-the-end. The 
trick for that test is in
https://github.com/intel/tinycbor/blob/dev/tests/parser/tst_parser.cpp#L159-L192
which always places the data to be parsed at the end of a page, followed by a 
page with no read access.

And if you look at https://github.com/intel/tinycbor/blob/dev/tests/parser/
tst_parser.cpp#L1796-L2155. you'll see an extensive list of strict, canonical 
mode and JSON-compatibility testing.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel System Software Products

---

From: Carsten Bormann <[email-masked]>
Date: Tue, 30 Jul 2019 11:23:03 +0200

> I think I’ve made a comprehensive list of all things that are not well formed by going through the latest draft and my decoder. There are about a dozen of them. I’ve also created 110 test vectors t…

Nice!
I actually find 111 vectors there.  
If I run these through the (slightly instrumented) pseudocode of the appendix, I get:

   2 SHORT
  10 FINITE
  14 SHORT
   1 BREAK
  14 SHORT
   7 BREAK
   2 RESIDUAL
  25 SIMPLE
   4 INDEF
   4 SHORT
  24 AI
   2 SHORT
   2 BREAK

Where:

- SHORT = premature EOF
- RESIDUAL = data remaining after decoding
1 AI = reserved AI
2 SIMPLE = impermissible coding of simple value
3 FINITE = indefinite inside indefinite length string
4 BREAK = break stop code outside indefinite length item or as map value
5 INDEF = wrong major type for indefinite length

(The numbers in this list enumerate the calls to “fail()” in the pseudocode in the appendix.)

Why are you testing only 25 of the 32 impermissible SIMPLE cases?

Grüße, Carsten

PS: These test vectors base64url-encoded in JSON:

[
  "X0EA",
  "f2EA",
  "X2EA_w",
  "f0EA_w",
  "XwD_",
  "XyH_",
  "X4D_",
  "X6D_",
  "X8AA_w",
  "X-D_",
  "X19BAP__",
  "f39hAP__",
  "gQ",
  "ggA",
  "mgH_AA",
  "oQ",
  "ogEC",
  "nw",
  "nwEC",
  "vw",
  "vwECAQI",
  "n4AA",
  "gZ8",
  "gYGBgYGBgYGB",
  "n5-fn5______",
  "n4GfgZ-f____",
  "n4KfgZ-f_____w",
  "GA",
  "GQ",
  "Gg",
  "Gw",
  "GQE",
  "GgEC",
  "GwECAwQFBgc",
  "OA",
  "WA",
  "eA",
  "mA",
  "uA",
  "2A",
  "-A",
  "gf8",
  "ggD_",
  "of8",
  "of8A",
  "oQD_",
  "ogAA_w",
  "_w",
  "gP8",
  "n___",
  "-AA",
  "-AE",
  "-AI",
  "-AM",
  "-AQ",
  "-AU",
  "-AY",
  "-Ac",
  "-Ag",
  "-Ak",
  "-Ao",
  "-As",
  "-Aw",
  "-A0",
  "-A4",
  "-A8",
  "-BA",
  "-BE",
  "-BI",
  "-BM",
  "-BQ",
  "-BU",
  "-BY",
  "-Bc",
  "-Bg",
  "Hw",
  "Pw",
  "3wA",
  "3w",
  "QQ",
  "YQ",
  "Wv____8A",
  "ev____8A",
  "HA",
  "HQ",
  "Hg",
  "PA",
  "PQ",
  "Pg",
  "XA",
  "XQ",
  "Xg",
  "fA",
  "fQ",
  "fg",
  "nA",
  "nQ",
  "ng",
  "vA",
  "vQ",
  "vg",
  "3A",
  "3Q",
  "3g",
  "_A",
  "_Q",
  "_g",
  "oQA",
  "ogAAAA",
  "vwD_",
  "vwAAAP8"
]

---

From: Laurence Lundblade <[email-masked]>
Date: Wed, 31 Jul 2019 20:01:16 -0700

> Why are you testing only 25 of the 32 impermissible SIMPLE cases?

Because I’m confused about unassigned vs reserved in this table (just realized I was confused):

                       +---------+-----------------+
                       | Value   | Semantics       |
                       +---------+-----------------+
                       | 0..19   | (Unassigned)    |
                       |         |                 |
                       | 20      | False           |
                       |         |                 |
                       | 21      | True            |
                       |         |                 |
                       | 22      | Null            |
                       |         |                 |
                       | 23      | Undefined value |
                       |         |                 |
                       | 24..31  | (Reserved)      |
                       |         |                 |
                       | 32..255 | (Unassigned)    |
                       +---------+-----------------+

Neither sections 7.1 nor 9.2 mention 24..31. 

These of course can’t be represented by the single byte 0xf8 through 0xff because those are float and such, but there seems to be no trouble representing the with 0xf8 0x18 through 0xf8 0x1f.

Why wouldn’t 24 through 255 be considered unassigned and encoded 0xf8 0x18 through 0xf8 0xff?

LL

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 1 Aug 2019 08:52:52 +0200

> Why wouldn’t 24 through 255 be considered unassigned and encoded 0xf8 0x18 through 0xf8 0xff?

Because we considered those values confusing, and decided to give up on 8 potential values in exchange for reducing this confusion.  See Section 2.3 of RFC 7049 (parenthesis in first paragraph on page 13).

Whether that was a particularly wise decision can be discussed.  Since we already have to check for too-low values in the second byte of 7.24, checking for 32 is not more onerous than checking for 24 (see pseudocode).  Giving up 8 values seems to be of limited concern given the number of allocations of Simple values so far.  Changing this now, however, would be a backward compatibility issue that we need to avoid.

Grüße, Carsten