JSON with blobs, still context-free
Pen and paper design.
The Science of InsecurityI took Meredith Patterson and Sergey Bratus by their word and tried to solve my next network communication problem without crossing the line beyond deterministic context-free languages. The upshot of said talk was that most if not all security problems stem from the fact that some software component could not foresee the consequences of its input. From a language-theoretic point of view, the problem boils down to recognizing the set (
language) of acceptable inputs. There are different classes of languages whose recognizers require increasingly complex mechanisms. Things are basically pleasant with regular languages and one step up, aforementioned deterministic context-free ones. Up to this point we can algorithmically decide whether two specifications describe the same language; whether two peers in the network are cleanly interoperable. When I was looking for a good data serialization format, in addition to my original requirements, I went looking for one that had a deterministic context-free grammar. Incidentally, one of the things I wanted to be able to do was efficiently transfer relatively large blocks of arbitrary data. Unfortunately, what immediately catapults you into the land of (mildly) context-sensitive languages are length fields. JSON (as implied by the title) would have been my favorite choice, but the best way to put binary blobs in it is by encoding them as Base64-encoded strings.
{ "message": "Hi, Bob!"
, "attachment": "ZGFmdXFpc3RoaXM="
}
could weas much as
do we want to. So below is the answer I came up with. The idea is to break binary data into chunks of uniform size. I chose 4096 bytes rather arbitrarily. Allow one final chunk of variable length and encode that one in Base64. So every 4kB, there is one character (#) which means
another 4k coming. There need not be any such
raw chunks; they are always followed by exactly one (possibly empty) Base64 string enclosed in %. Examples:
#.....#.....%ZGFmdXFp%
#.....#.....%%
%ZGFmdXFp%
- Stay deterministic context-free.
- Avoid escaping or re-encoding every byte in binary blobs.
- Simple grammar.
- Self-describing structure.
- Stay reasonably human-readable and human-writable.
- Minimize attack surface for bugs.
- Plus: Allow exact representation of binary floating point numbers.
- Plus: Allow strings to use any character encoding.
- Plus: Do not use newlines as syntax, allow arbitrary values to be serialized into single lines.
- Plus: Provide for easy streaming of values.
- Optimal size.
- Optimal speed.
- Proper superset of UTF-8-encoded JSON.
- Types:
- Null
- Boolean
- Number
- Byte-Array
- String
- List (= JSON
arrays
) - Record (= JSON
objects
)
- Defined in ABNF.
- ~150 lines.
- Transcribes trivially to a PEG.
- All syntax is ASCII.
- No other external encodings allowed.
- Strings are tagged with their encoding.
- No tag means UTF-8.
- JSON-style unicode escapes \u.... supported for compatibility.
- UTF-16 surrogate pairs recognized by grammar.
- Parsers SHOULD properly recode these for UTF-8 strings.
- Arbitrary bytes in strings via hexadecimal escapes \x...
- Numbers are arbitrary-precision rationals.
- Hexadecimal notation for numbers supported.
- Including hexadecimal fraction and exponent notation.
- Top-level
document
consists of one value of any type.- JSON only allows arrays and objects.
- Defined syntax for top-level value streams.
- Values terminated by newlines.
- Allows parser for rule stream-element to simply be called repeatedly on input stream.
{ "null": null
, "boolean": true
, "integer": 1234
, "rational": 1234.56
, "exponent": 1234.56e2
, "hexadecimal": 0x123AB.CDxE
, "bytes": %ZGFmdXFp%
, "string": "Hello"
, "encoding": "Mot\xF6rhead"_latin1
, "list": [23,"skidoo"]
, "record": {}
}
datalangand resides in a repository here:
darcs get http://code.khjk.org/datalang/