Subject: [quicwg/base-drafts] Avoid data corruption with wrapped Largest Reference. (#2261)

From: Bence Béky <[email-masked]>
Date: Wed, 26 Dec 2018 09:39:32 -0800

A dynamic table entry that has not been acknowledged by the decoder must not be
evicted by the encoder, even if there has never been any references to it.  This
is already alluded to in the current spec at
https://quicwg.org/base-drafts/draft-ietf-quic-qpack.html#eviction by the phrase
"acknowledged by the decoder", but since "acknowledged" is used interchangeably
for acknowledging the insertion instruction and acknowledging references, a
reader could understand this to mean "all references acknowledged".  In
addition, at three other places eviction of entries with unacknowledged
references are banned, with unambigously no ban on eviction of unacknowledged
entries with no references.  I argue that more explicit language would be
beneficial.

This issue has already been discussed at
https://github.com/quicwg/base-drafts/issues/1644#issuecomment-411894178
and below.

Note that avoiding this kind of corruption could also be achieved by banning an
encoder from inserting entries that it does not immediately reference, but this
is probably way too restrictive.  For example, an encoder might wish to achieve
best latency and speculatively improve future compression ratio at the expense
of potentially wasting current bandwidth by encoding header fields as literals
while inserting them at the same time for potiential future use.  This is
already alluded to in the spec at multiple places.

Below is a specific scenario when this issue might cause corruption:

Suppose MaxEntries is 5.

Suppose that there is a fresh connection, with an empty dynamic table, and there
is a header list to be sent that has two header fields which fit in the dynamic
table together.

Suppose one encoder implementation inserts these two header fields into the
dynamic table, and encodes the header list using two Indexed Header Field
instructions, referring to absolute indices 1 and 2.  This header block will
have an abstract Largest Reference value of 2, which is encoded as 3 on the
wire.  A spec compliant decoder should have no difficultly correctly decoding
this header block.

Suppose another encoder implementation starts by adding 10 unique entries, all
different from the two header fields in the header list to be sent, to the
dynamic table, but does not emit references to any of them.   Of course in the
end only the last couple will stay in the dynamic table, the rest will be
evicted.  This can be considered spec compliant depending on how one interprets
the spec, see above.  Suppose that after this, this encoder implementation
encodes our header list by inserting both header fields into the dynamic table,
with absolute indices 11 and 12, and using two Indexed Header Field instructions
on the request stream.  The abstract Largest Reference value is 12, which is
encoded as 3 on the wire since 2 * MaxEntries == 10.

Now suppose that out of the 12 instructions on the encoder stream, only the
first two arrive before all the request stream data are received.  The remaining
10 instructions on the encoder stream are delayed on the wire.  Now a spec
compliant decoder sees the same header block on the request stream, bit by bit,
as above, and two insertions on the encoder stream.  It will emit dynamic table
entires 1 and 2, which are different from the encoded header list.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/2261

-- Commit Summary --

  * Avoid data corruption with wrapped Largest Reference.

-- File Changes --

    M draft-ietf-quic-qpack.md (57)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2261.patch
https://github.com/quicwg/base-drafts/pull/2261.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2261

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 17:23:56 -0800

You should really create a new issue for these things.  Because this comment relates only to the issue, not the proposed fix.  I haven't read the proposed changes, though I will if you think that there is a fix in there that is worth keeping after this.

Anyhow, the example is invalid here:

> another encoder implementation starts by adding 10 unique entries

Because:

> The encoder MUST NOT evict a dynamic table entry unless it has first been acknowledged by the decoder.

And you can only ever fit 5 entries in that table.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2261#issuecomment-450599368

---

From: csillagasz <[email-masked]>
Date: Sun, 30 Dec 2018 18:00:40 -0800

> And you can only ever fit 5 entries in that table.

That's exactly the issue: "it has first been acknowledged by the decoder" is ambigous.  "Acknowledged" is being used throughout the text with two different meanings, most often to refer to references, not insertions.  The ban on evicting an entry the insertion of which has not been acknowledged, that you are quoting, only occurs once out of four different locations talking about when an entry can be evicted.  The other three places clearly only ban evicting an entry with unacknowledged references (note the use of the same word), giving the impression that acknowledgement of the insertion is not necessary before eviction.

Since the design is correct if you read it right, but wording is not as clear as I think it should be, I consider this issue editorial.  The change I propose in this PR is meant to be an improvement on clarity.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2261#issuecomment-450601017

---

From: Bence Béky <[email-masked]>
Date: Sun, 30 Dec 2018 18:01:25 -0800

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2261#issuecomment-450601057

---

From: Martin Thomson <[email-masked]>
Date: Sun, 30 Dec 2018 18:06:22 -0800

OK, having read the changes, I agree with them.  They consolidate the fix by creating two conditions that cause an entry to be "blocking".

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/2261#issuecomment-450601275