Subject: Re: [Cellar] test4.mkv and EBML Elements with Unknown Size

From: Steve Lhomme <[email-masked]>
Date: Sat, 2 Jan 2016 10:06:05 +0100

2015-12-31 9:33 GMT+01:00 Moritz Bunkus <[email-masked]>:
> Hey,
>
>> The Matroska Test file suite is at
>> http://matroska.org/downloads/test_w1.html. This includes test4.mkv
>> which is an example of a live stream recording. However the file
>> doesn’t appear to adhere to the EBML specs. It the file written wrong
>> or are we missing something in the EBML specification?
>>
>> Within this file is this extract from the beginning of the Segment
>> element to the end of the Element ID of the Info Element.
>>
>> 18 53 80 67 FF 0A 0A 0A…
>
> Uhm… this is indeed invalid. A master must only contain child elements,
> not additional data. To put it differently: all child elements of a
> master element must cover the whole space occupied by the master without
> any gaps in between.

Did we handle that part in the newer specs ? It makes sense. But is it
possible that one byte is missing from a file ? If so the whole thing
becomes unusable just because of that missing byte. If it's at the end
of a master or an non vital element, it should not matter too much.
But that's a tricky thing to detect (an extra byte is easier).
Transfers over UDP may have these gaps of data.

Also the segment being of unknown/infinite size, anything is contained
within, unless a new Segment comes.

> I honestly don't know that file was created. libmatroska contains
> programs to create a couple of those files in its "tests" sub-directory,
> but test4 is not among them. Judging from the download page you've
> linked it's possible that the file was created with mkclean – in that
> case I would say that mkclean produces non-compliant files.
>
> Steve?

IIRC it was created manually with a hex editor.

>> I understand that 0x18538067 is the Element ID of the Segment Element.
>>
>> The 0xFF represents the case where as the EBML draft spec states, "An
>> Element Data Size with all VINT_DATA bits set to one is reserved as an
>> indicator that the size of the Element is unknown.”
>
> Correct.
>
>> Next, between the Element Data Size of the Segment Element and the
>> beginning of the Info Element there is 134 bytes of 0x0A! In this case
>> 0x0A can not be a valid start of an Element ID since for this file the
>> EBMLMaxIDLength is 4 (via the default). Thus the Segment
>> Master-element has child data that is not an EBML Element.
>
> Correct.
>
> Like I said, invalid.
>
> I definitely do not want to adjust the specs to allow arbitrary data in
> arbitrary places that a parser has to be able to skip over.

But that's not what this file is about. It's about error recovery. A
proper parser should treat all the 0A as garbage and look for some
proper data. That's what libebml does.

This file was inspired by the live streaming mode of GStreamer that
sends the header (Segment Info + Track Info) and whatever matroska
data comes after. Including the remaining of the Cluster that's
currently streaming. That part should be treated as garbage (and
luckily there is no false alarm of valid Level1+size elements in the
garbage data).

> Kind regards,
> mosu
>
> _______________________________________________
> Cellar mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cellar
>

-- 
Steve Lhomme
Matroska association Chairman

---

From: Dave Rice <[email-masked]>
Date: Sun, 3 Jan 2016 16:50:05 -0500

Hi,

> On Jan 2, 2016, at 4:06 AM, Steve Lhomme <[email-masked]> wrote:
> 
> Did we handle that part in the newer specs ? It makes sense.

Partly, in the EBML Document section, https://github.com/Matroska-Org/ebml-specification/blob/master/specification.markdown#ebml-document, it states: "An EBML Document MAY only consist of EBML Elements and MUST NOT contain any data that is not part of an EBML Element.” But this refers to the EBML Document as a whole and not the sub-elements.

The Master-element definition says: “The Master-element contains zero, one, or many other elements.” But the language is not exclusive to say that the Master-element may ONLY contain zero, one, or many other elements.

I propose to add to the Master-element definition the line: “The Element Data stored within Master-elements MUST only consist of EBML Elements and MUST NOT contain any data that is not part of an EBML Element.” I send this as a pull request here https://github.com/Matroska-Org/ebml-specification/pull/45. The patch is here:

From ba9973706d35934ea4c5e8f50d66d5ac3f725fd2 Mon Sep 17 00:00:00 2001
From: dericed <[email-masked]>
Date: Sun, 3 Jan 2016 16:29:43 -0500
Subject: [PATCH] clarify that Master-elements may only contain elements

---
 specification.markdown | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/specification.markdown b/specification.markdown
index b90020c..4159bdb 100644
--- a/specification.markdown
+++ b/specification.markdown
@@ -141,7 +141,7 @@ Element Data Type:   Master-element
 
     Endianness:     None
     Length:         A Master-element may declare any length (included zero) up to the maximum Element Data Size value permitted. The Master-element may also use an unknown length. See the section on Element Data Size for rules that apply to elements of unknown length.
-    Definition:     The Master-element contains zero, one, or many other elements. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at levels 3.
+    Definition:     The Master-element contains zero, one, or many other elements. The Element Data stored within Master-elements MUST only consist of EBML Elements and MUST NOT contain any data that is not part of an EBML Element. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at levels 3.
 
 Element Data Type:   Binary
 
-- 
2.6.4

> But is it

These suggestions may pertain more to suggestions on a parser than for the specification.

> within, unless a new Segment comes.

According to the current EBML draft spec: "The end of the Master-element is determined by the beginning of the next element that is not a valid sub-element of the Master-element.” I realize that this need a little more clarity so I added this patch to the same pull request referenced above.

From 64bc489282a51891535815e0cea4d00b42c25564 Mon Sep 17 00:00:00 2001
From: dericed <[email-masked]>
Date: Sun, 3 Jan 2016 16:37:50 -0500
Subject: [PATCH] clarification on the end of Master-elements

---
 specification.markdown | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/specification.markdown b/specification.markdown
index 4159bdb..e1b6857 100644
--- a/specification.markdown
+++ b/specification.markdown
@@ -71,7 +71,7 @@ The Element Data Size expresses the length in octets of Element Data. The Elemen
 
 Although an Element ID with all VINT\_DATA bits set to zero is invalid, an Element Data Size with all VINT\_DATA bits set to zero is allowed for EBML Data Types which do not mandate a non-zero length. An Element Data Size with all VINT\_DATA bits set to zero indicates that the Element Data of the Element is zero octets in length. Such an Element is referred to as an Empty Element. If an Empty Element has a `default` value declared then that default value MUST be interpreted as the value of the Empty Element. If an Empty Element has no `default` value declared then the semantic meaning of Empty Element is defined as part of the definition of the EBML Element Types.
 
-An Element Data Size with all VINT\_DATA bits set to one is reserved as an indicator that the size of the Element is unknown. The only reserved value for the VINT\_DATA of Element Data Size is all bits set to one. This rule allows for an Element to be written and read before the size of the Element is known; however unknown Element Data Size values SHOULD NOT be used unnecessarily. An Element with an unknown Element Data Size MUST be a Master-element in that it contains other EBML Elements as sub-elements. The end of the Master-element is determined by the beginning of the next element that is not a valid sub-element of the Master-element.
+An Element Data Size with all VINT\_DATA bits set to one is reserved as an indicator that the size of the Element is unknown. The only reserved value for the VINT\_DATA of Element Data Size is all bits set to one. This rule allows for an Element to be written and read before the size of the Element is known; however unknown Element Data Size values SHOULD NOT be used unnecessarily. An Element with an unknown Element Data Size MUST be a Master-element in that it contains other EBML Elements as sub-elements. The end of a Master-element with unknown size is determined by the beginning of the next element that is not a valid sub-element of that Master-element.
 
 For Element Data Sizes encoded at octet lengths from one to eight, this table depicts the range of possible values that can be encoded as an Element Data Size. An Element Data Size with an octet length of 8 is able to express a size of 2^56-2 or 72,057,594,037,927,934 octets (or about 72 petabytes).
 
-- 
2.6.4

> proper data. That's what libebml does.

To be clear. In this case, the file has a MaxIDLength of 4 and thus 0x0A (aka 0b00001010) is invalid as the first byte of an Element ID. So is this correct logic?

For a generic EBML parser:
It should skip the invalid 0x0A bytes, because they are not valid Element IDs according to the MaxIDLength. In this case it should then skip ahead to the Info Element.

For a Matroska parser:
It should skip the invalid 0x0A bytes until it encounters the first valid Element iD of an Element that may be a child Element of Segment?

> luckily there is no false alarm of valid Level1+size elements in the

The use of 32 bit Element IDs at Level 1 of Matroska makes more sense with this logic. A false alarm should be rare with garbage.

With the example provided, the EBML Stream structure would be

EBML/
Segment/
	Info/
	Track/
	<<< GARBAGE FRAGMENTARY CLUSTER >>>
	Cluster/

Should this be considered a valid EBML Stream? The pull request reference makes this invalid, otherwise the spec is very unclear about the presence of garbage, non Element Data within a Master-element.

>> mosu

[...]

> Matroska association Chairman

Dave Rice

---

From: Steve Lhomme <[email-masked]>
Date: Mon, 4 Jan 2016 08:44:48 +0100

> I propose to add to the Master-element definition the line: “The Element Data stored within Master-elements MUST only consist of EBML Elements and MUST NOT contain any data that is not part of an E…

But that makes such streaming files illegal according to the specs.
VLC does the same when "broadcast" streaming over HTTP. And even a
Chromecast can handle such stream starting with the end of a Cluster
(ie garbage). Given it's mostly compressed data it can be any octet.
That's why the level-1 elements are all 4 octets in Matroska, to avoid
false positives.

It was not originally designed to work like that but GStreamer
implemented streaming like that and luckily it was fitting the
existing parsers. VLC followed later. Knowing the VLC code, it would
take a bit of work to allow clean EBML data to be sent. For now the
different muxing/sending stages don't signal synchronization points
like that. Only the header (Segment Info).

Again, IMO it's not an issue for parsers that should be resilient to
bad data. Changing this text will not make much difference regarding
to that. Maybe the specs should also cover what happens when bad data
are found ? Like bad CRC, duplicate elements, etc.

>  Element Data Type:   Binary

Fine with me.

> To be clear. In this case, the file has a MaxIDLength of 4 and thus 0x0A (aka 0b00001010) is invalid as the first byte of an Element ID. So is this correct logic?

Yes. It's bad data so it should be skipped.

> It should skip the invalid 0x0A bytes until it encounters the first valid Element iD of an Element that may be a child Element of Segment?

It's true that when you know the expected semantic, you can detect
false alarms a lot better. When you don't, 4-octets Level-1 elements
are not much help. So pure EBML recovery tools should not expect great
results.

> Should this be considered a valid EBML Stream? The pull request reference makes this invalid, otherwise the spec is very unclear about the presence of garbage, non Element Data within a Master-elem…

It's invalid EBML data. And should stay that way. But a semantic
parser SHOULD (MUST?) be able to handle this.

---

From: Dave Rice <[email-masked]>
Date: Sun, 10 Jan 2016 14:32:58 -0500

Hi,

> On Jan 4, 2016, at 2:44 AM, Steve Lhomme <[email-masked]> wrote:
> 
> (ie garbage).

Here is the current definition of Master-element and a proposed update based on the discussion in this thread.

current definition of Master-element
========
The Master-element contains zero, one, or many other elements. The Element Data stored within Master-elements MUST only consist of EBML Elements and MUST NOT contain any data that is not part of an EBML Element. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at levels 3.
========

proposed update to definition of Master-element
========
The Master-element contains zero, one, or many other elements. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at levels 3. Element Data stored within Master-elements SHOULD only consist of EBML Elements and SHOULD NOT contain any data that is not part of an EBML Element. When EBML is used in transmission or streaming, data that is not part of an EBML Element is permitted to be present within a Master-element. In this case, the reader should read the Element Data of the Master-element octet by octet until a valid Element ID at the same level or the next greater level of the Master-element is found. What Element IDs are considered valid within a Master-element is identified by the EBML Schema for that version of the EBML Document Type. Any data contained with a Master-element that is not part of an Element SHOULD be ignored.
========

Question: Can non-Element data in Master-elements be restricted to certain EBML Levels?

> Given it's mostly compressed data it can be any octet.

This is a good point, but it is not noted within the EBML Specification. I propose adding this to the definition of ‘id’ within the EBML Schema Element Attributes section:

"To reduce the risk of false positives while parsing EBML Streams, Level 1 EBML Element IDs SHOULD be at least 4 octets in length. Element IDs at Level 1 MAY use shorter octet lengths to facilitate padding and optimize edits to EBML Documents; for instance, the EBML Void Element uses an Element ID with a one octet length to allow its usage in more writing and editing scenarios."

> are found ? Like bad CRC, duplicate elements, etc.

I think it should though perhaps in a new section. I added an issue here https://github.com/Matroska-Org/ebml-specification/issues/48 to deal with this eventually, but not to expand the scope of this current thread too much.

> Yes. It's bad data so it should be skipped.

I added a statement to this in the proposed definition update above, using ‘ignored’ rather than ‘skipped’.

> are not much help. So pure EBML recovery tools should not expect great

I didn’t address this in the proposal above, but should we. Perhaps we could clarify that a parser SHOULD have a semantic understanding of the version and doctype that it is parser, else the results are unexpected?

> parser SHOULD (MUST?) be able to handle this.

Let me know if you think the proposed definition above address this well. I placed all the referenced changes in this pull request so it may be reviewed in context: https://github.com/Matroska-Org/ebml-specification/pull/49.

[…]

Dave Rice

---

From: Steve Lhomme <[email-masked]>
Date: Mon, 11 Jan 2016 10:37:35 +0100

2016-01-10 20:32 GMT+01:00 Dave Rice <[email-masked]>:
> The Master-element contains zero, one, or many other elements. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at levels 3. Element Data stored within Master-elements SHOULD only consist of EBML Elements and SHOULD NOT contain any data that is not part of an EBML Element. When EBML is used in transmission or streaming, data that is not part of an EBML Element is permitted to be present within a Master-element. In this case, the reader should read the Element Data of the Master-element octet by octet until a valid Element ID at the same level or the next greater level of the Master-element is found. What Element IDs are considered valid within a Master-element is identified by the

I think the way it must be discard is too specific. This is
implementation details that should not be in the specs. IMO something
like "the reader should skip data until a valid Element ID at the same
level or the next greater level of the Master-element is found".

EBML Schema for that version of the EBML Document Type. Any data
contained with a Master-element that is not part of an Element SHOULD
be ignored.
> Question: Can non-Element data in Master-elements be restricted to certain EBML Levels?

If that ever occurs that should be specific to specific semantics. So
the question might be: should it be part of the semantic definition?
We haven't got to that part of Matroska yet. So we may keep that
question for when we get there. IMO the tricky question is whether
semantic definition should be able to generate code solely based on
this definition, regardless of the format. This is not the case in
Matroska where some elements refer to other elements directly or
indirectly.

> "To reduce the risk of false positives while parsing EBML Streams, Level 1 EBML Element IDs SHOULD be at least 4 octets in length. Element IDs at Level 1 MAY use shorter octet lengths to facilitate…

Level 0 as well. I agree with the addition.

> I didn’t address this in the proposal above, but should we. Perhaps we could clarify that a parser SHOULD have a semantic understanding of the version and doctype that it is parser, else the result…

Maybe semantics should tell if they allow arbitrary data (à la
GStreamer streaming) or not. That might be added to the EBML header.
So it may even be set arbitrarily in any EBML stream. If we started
from scratch we would make such flag off by default. But that would
mean all these live recordings might end up non parsable by strict
EBML parsers.

---

From: Dave Rice <[email-masked]>
Date: Mon, 11 Jan 2016 21:31:25 -0500

> On Jan 11, 2016, at 4:37 AM, Steve Lhomme <[email-masked]> wrote:
> 
> level or the next greater level of the Master-element is found”.

I updated my draft locally to use your phrasing and sent this in a pull request at: Also updated in a pull request: https://github.com/Matroska-Org/ebml-specification/pull/50
New Master-element definition:
==========
The Master-element contains zero, one, or many other elements. Elements contained within a Master-element must be defined for use at levels greater than the level of the Master-element. For instance is a Master-element occurs on level 2 then all contained Elements must be valid at level 3. Element Data stored within Master-elements SHOULD only consist of EBML Elements and SHOULD NOT contain any data that is not part of an EBML Element. When EBML is used in transmission or streaming, data that is not part of an EBML Element is permitted to be present within a Master-element. In this case, the reader should skip data until a valid Element ID of the same level or the next greater level of the Master-element is found. What Element IDs are considered valid within a Master-element is identified by the EBML Schema for that version of the EBML Document Type. Any data contained with a Master-element that is not part of an Element SHOULD be ignored.
==========

> Matroska where some elements refer to other elements directly or

Skipping issue for now then, though we had earlier (pre-CELLAR) discussed on matroska-devel to have an EBML Schema Attribute to declare if the Master-element is allows to use an unknown size or not. Are the two issues of allowance of unknown size and permission to include junk data related? Is there an Element that would use one and not the other?

> Level 0 as well. I agree with the addition.

Updated to:
==========
To reduce the risk of false positives while parsing EBML Streams, EBML Element IDs defined for use at Level 0 or Level 1 SHOULD be at least 4 octets in length. Element IDs defined for use at Level 0 or Level 1 MAY use shorter octet lengths to facilitate padding and optimize edits to EBML Documents; for instance, the EBML Void Element uses an Element ID with a one octet length to allow its usage in more writing and editing scenarios.
==========
Also updated in a pull request: https://github.com/Matroska-Org/ebml-specification/pull/50

[…]

>>>>> proper data. That's what libebml does.

Moritz, Does the line "When EBML is used in transmission or streaming, data that is not part of an EBML Element is permitted to be present within a Master-element.” in the proposed update to the Master-element definition resolve the issue raised here?

> mean all these live recordings might end up non parsable by strict

We could add an EBML Header Element which has a default value of allowing arbitrary data. Future writers could then be clear when they do not intend to do this.

Also as noted above we could consider adding an EBML Schema Attribute to say if the Element is allowed to have unknown size. A quality of unknown size could then be the presence of arbitrary data, but I’m unclear if these two qualities always go together.

[…]

Dave RIce