Subject: [quicwg/base-drafts] STREAM frame boundaries (#146)

From: Marten Seemann <[email-masked]>
Date: Thu, 12 Jan 2017 23:35:54 -0800

We had a [discussion](https://groups.google.com/a/chromium.org/forum/#!topic/proto-quic/j747iwug-Hg) about this earlier on the proto-quic mailing list, but as far as I remember, we never reached a conclusion or discussed this on the IETF mailing list.

There are two options:

1. STREAM frame boundaries MUST be preserved when retransmitting them, i.e. a STREAM frame that is being retransmitted MAY be split into further pieces, but MUST NOT be combined with other STREAM frames.
2. STREAM frames MAY be reassembled before retransmitting them, and STREAM frame boundaries need not be preserved.

Option 1. is what Chrome and quic-go are currently implementing. 2. is what the draft is specifying in the current version ([here](https://github.com/quicwg/base-drafts/blob/master/draft-ietf-quic-transport.md#sending-and-receiving-data)).

If we decide for 1., this needs to be reflected in the draft. If we decide for 2., we need to remove the QUIC_OVERLAPPING_STREAM_DATA (0x8057) error.

-- 
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/issues/146

---

From: janaiyengar <[email-masked]>
Date: Fri, 13 Jan 2017 17:09:52 -0800

Interesting point. I agree that the two are in opposition to each other. How about option (2), but change the OVERLAPPING_STREAM_DATA error to mean that the data in the overlapping region is different?

-- 
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/issues/146#issuecomment-272588549

---

From: Mike Bishop <[email-masked]>
Date: Fri, 13 Jan 2017 17:31:07 -0800

That would require the implementation to retain the data after it's delivered to the application, in order to check against incoming data, wouldn't it?  Seems implausible.

-- 
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/issues/146#issuecomment-272590537

---

From: Marten Seemann <[email-masked]>
Date: Sat, 14 Jan 2017 00:50:12 -0800

Some more thoughts on the two options:

If we decide for option (1), we **must** require each retransmission to contain a STOP_WAITING frame (or, as soon as we remove them from the protocol (#66), an ACK frame). Otherwise the receipt of a delayed packet for which a retransmission of a split STREAM_FRAME was already received would cause an overlapping stream data error.

For option (2), implementations have to be careful about a DoS where the attacker sends overlapping stream data, in an attempt to consume O(N^2) memory (N: number of bytes of the receive window). This attack doesn't exist for option (1), since overlapping stream data results in an error (and unnecessary retransmitted STREAM frames can be discarded right away).

-- 
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/issues/146#issuecomment-272611282

---

From: ianswett <[email-masked]>
Date: Sat, 14 Jan 2017 11:14:33 -0800

I think #2 is the right option, even though both implementations do #1 at the moment because it's easier.  Your point about splitting STREAM_FRAMEs makes this even more clear.

I'm ok with changing OVERLAPPING_STREAM_DATA to DIFFERENT_OVERLAPPING_STREAM_DATA or something similar, with the understanding that a receiver SHOULD(or MAY?) verify that the data is identical, but we can't use MUST there. 

Mike, in regards to memory usage, streams don't delivery data out of order, so the data delivered to the app would not be verified as you mentioned, but it'd be easy to verify any buffered overlaps.  

For option (2), it's certainly possible to have a receive buffer approach where N^2 memory is not consumed by copying the non-overlapping data and discarding the stream frame.  TCP manages to implement a receive buffer without N^2 issues, so I think it's not a concern for QUIC with option 2, but I could be missing something?

-- 
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/issues/146#issuecomment-272646119

---

From: Mike Bishop <[email-masked]>
Date: Sat, 14 Jan 2017 15:11:08 -0800

Maybe CONFLICTING_STREAM_DATA?  So the logic would be that data which has already been delivered to the app gets silently discarded, new data gets added to the buffer, and existing data gets checked.  If the check reveals a conflict do we reset the stream, or the connection?

-- 
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/issues/146#issuecomment-272660308

---

From: Martin Thomson <[email-masked]>
Date: Sun, 15 Jan 2017 13:58:38 -0800

Assuming that the data is authenticated, then a connection-level error is appropriate. For the crypto handshake, I am inclined to say that you can make it optionally a connection-level error as well.  That does leave the connection open to attack, but that requires an on-path attacker, who have many other options at their disposal during the opening exchange.

Failing noisily means that we learn about it and are incentivized to fix it.

Like @ianswett observes, it's good to have a less-than-MUST strength requirement here because some implementations will just throw stuff out if they already think that they have it.  Checking for a match might cost them memory or time they don't have; and we shouldn't force the check on every implementation.  We should probably have some implementations check though.

Making a check mandatory doesn't lead to the insane memory requirement @marten-seemann suggests since you just generate a fatal error on the first infringement.

-- 
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/issues/146#issuecomment-272727069

---

From: Marten Seemann <[email-masked]>
Date: Sun, 15 Jan 2017 19:05:53 -0800

I didn't mean to imply that N^2 is the memory requirement to check for CONFLICTING_STREAM_DATA erros (or however they will be called). I was just pointing out that the scenario where an attacker sends a lot of overlapping stream data should be something to keep in mind when implementing a STREAM frame sorter.
I saw some implementation notes in some other parts of the draft, so I thought this might be something worth pointing out if we decide for option (2).

-- 
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/issues/146#issuecomment-272763898

---

From: mirjak <[email-masked]>
Date: Mon, 16 Jan 2017 03:27:39 -0800

Given that the implementation of option (1) is simpler anyway, what's the benefit of (2)?

-- 
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/issues/146#issuecomment-272837083

---

From: ianswett <[email-masked]>
Date: Mon, 16 Jan 2017 05:36:29 -0800

Marten, agreed that an N^2 attack is a case to keep in mind when implementing, and we should possibly note that in the doc.   

The main negative to me of option (1) is that it means you can never merge or split a stream frame once it's sent.  @marten-seemann ,  were you implying that this was possible with stop-waiting frames?  

I'd like to discuss this at the interim, because it seems important and resolvable, so adding to the list.

-- 
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/issues/146#issuecomment-272863472

---

From: Marten Seemann <[email-masked]>
Date: Mon, 16 Jan 2017 06:11:18 -0800

I don't think option (1) is easier. In fact, the need to check for an OVERLAPPING_STREAM_DATA error be used for a DoS against the receiver:
If the received data contains gaps, the receiver has to store all STREAM frames until the gaps are filled and the data can be read by the application. For every incoming STREAM frame the receiver now has to check, if it 1. entirely fills a gap, 2. completely overlaps with received data, or 3. overlaps the boundary between already received data and a gap.  This check can be performed in O(log N) per frame, so the computational complexity of the STREAM frame sorter is O(N log N), where N is the number of STREAM frames an attacker can send within one flow control window.

Because of this DoS vulnerability we introduced a maximum number of gaps that a client may send in quic-go, and I believe Chrome did the same.

@ianswett: Merging frames was never possible, since we're explicitly checking for OVERLAPPING_STREAM_DATA errors. To avoid those errors under all circumstances (especially when packets get delayed), it was necessary to include a STOP_WAITING in **every** packet containing retransmitted stream data. As soon as we drop STOP_WAITINGs, we would have to include an ACK instead in **every** such packet, which seems undesirable, given that ACKs are bigger than STOP_WAITINGs.

-- 
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/issues/146#issuecomment-272870920

---

From: Marten Seemann <[email-masked]>
Date: Mon, 16 Jan 2017 06:48:31 -0800

Speaking of DoSes, I don't think that checking for CONFLICTING_STREAM_DATA comes for free, if an attacker sends stream data with a lot of gaps.
I'm not sure that there's an algorithm that doesn't have the same complexity as the one described above, or doesn't incur a memory overhead of O(N) (which is significant, since N can be on the order of megabytes per stream).

If I'm correct, this might be an argument against introducing a CONFLICTING_STREAM_DATA error.

-- 
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/issues/146#issuecomment-272881595

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Jan 2017 18:01:09 -0800

@marten-seemann, Can't you just have the inbound buffer (up to the flow control credit in size) with all the pieces that have been received in place, then you compare the incoming frame (up to MTU-some in size) with the corresponding pieces that you have?  The nasty cost here is that every octet has 257 values: the 256 values of an octet you have and the octet you don't have.  Storing that efficiently will be the only challenge, especially if you have lots of small non-contiguous ranges.

I don't think that we can account for non-contiguous ranges in the flow control accounting.  Well, much.  You could insist that STREAM data be provided in N-bit blocks.

As @ianswett points out and I think we've agreed, not everyone will be required to do that check.  Not everyone can do the check (at least efficiently). Some could just overwrite, others could just repair the gaps.

-- 
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/issues/146#issuecomment-273002730

---

From: Marten Seemann <[email-masked]>
Date: Mon, 16 Jan 2017 18:37:47 -0800

@martinthomson: All my DoS considerations don't apply to the average case (where you only have a few non-contiguous range), they're only relevant for the worst case (tens of thousands of non-contiguous range). But the worst case is exactly what an attacker will hit us with.
As you mention, we need an additional bit per byte to store if we already received that particular byte. Since caching STREAM frames is probably the biggest RAM requirement of a QUIC implementation, as an implementor I'd choose to not increase that by a factor of 1/8.

I'm not sure I understand your point about flow control. The only thing that matters for a receiver is the highest offset of data contained in a STREAM frame (both for checking for flow control violations and for making adjustments to the connection-level flow control credit).

-- 
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/issues/146#issuecomment-273007357

---

From: Martin Thomson <[email-masked]>
Date: Mon, 16 Jan 2017 19:07:23 -0800

It's not a bit per byte, it's much less.  Though it's probably one way to store it that balances storage and the potential for storage blow-out.

Not sure where you got the 1/8 from.  My point was that if we reduce the granularity that a sender can fragment on from per-byte to per-many-bytes, then that 1-bit-per-byte overhead is reduced proportionally.  A change like that could propagate to flow control: because you account on a block basis rather than a byte basis, so you can only move the offset in whole multiples of blocks.  The same goes for the offset field in the STREAM frame.

-- 
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/issues/146#issuecomment-273011039

---

From: ianswett <[email-masked]>
Date: Tue, 17 Jan 2017 07:54:04 -0800

I believe Marten is concerned about the overhead to track what's in the contiguous buffers, not the storage of buffered data itself.

If the extra amount of memory is limited to a small constant factor on top of the actual storage, is this a DDoS we're concerned about?  Sending small stream frames requires quite a bit of extra overhead already.

-- 
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/issues/146#issuecomment-273209147

---

From: Marten Seemann <[email-masked]>
Date: Tue, 17 Jan 2017 09:55:37 -0800

@ianswett Correct, that's what I was concerned about. I don't think there is a DoS opportunity here, if one decides to allocate an additional buffer that keeps track of which bytes were already received. The DoS opportunity comes from optimizing for the average case (few gaps in stream data), by using a data structure that doesn't require a constant overhead, but only allows for O(log N) lookups.

I'd like to discuss if we really need to define a CONFLICTING_STREAM_DATA error at all. For QUIC, the stream data is an opaque byte stream anyway, and if the peer decides to send nonsensical data on that stream, there's nothing that QUIC can do against that.
I can't imagine any attack on a QUIC implementation that could be achieved by sending conflicting stream data. The only thing a CONFLICTING_STREAM_DATA error would actually help with is debugging an implementation that doesn't correctly assemble STREAM frames in retransmissions, and this seems like a kind of bug that could easily be caught by some unit tests.

-- 
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/issues/146#issuecomment-273246184

---

From: ianswett <[email-masked]>
Date: Tue, 17 Jan 2017 10:14:31 -0800

Good point, the only value of CONFLICTING_STREAM_DATA I can imagine is debugging correctness issues.  But I don't think that's a good enough reason to include it in the transport.

-- 
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/issues/146#issuecomment-273251545

---

From: Dragana Damjanovic <[email-masked]>
Date: Wed, 18 Jan 2017 00:25:30 -0800

A side note: This will not happen very often, actually very rarely, but still it can happen.
A original packet has packetId of size 8bits and for a retransmission of that packet packetId increases to 16bits. Fragmenting frames in many-bites frames will be inefficient, the packets will not be fully used. If only one packet is lost we will have a 1bit frame to retransmit.
Also choosing to reduce the granularity will be inefficient because max frame size depend on packetId size, for example.

-- 
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/issues/146#issuecomment-273412587

---

From: ianswett <[email-masked]>
Date: Wed, 18 Jan 2017 07:22:45 -0800

The scenario you describe definitely can happen often enough to be a problem.  The solution we've been using is to ensure there's enough available packet number space for all outstanding packets + packets that may be sent in the future(including retransmissions) to avoid having to fragment one byte of payload into a new stream frame.

-- 
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/issues/146#issuecomment-273504775

---

From: Victor Vasiliev <[email-masked]>
Date: Mon, 23 Jan 2017 11:58:45 -0800

One of the important aspects why (2) is preferable to (1) is that when migrating a connection, the client might end up on a path where retransmitting STREAM frames as-is is infeasible due to the MTU of the new path being too low.

-- 
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/issues/146#issuecomment-274599410

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 23 Jan 2017 20:28:45 -0800

Closed #146.

-- 
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/issues/146#event-933931658

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 23 Jan 2017 20:28:45 -0800

Discussed in Tokyo; consensus in the room to take Option 2, and remove the error code.

-- 
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/issues/146#issuecomment-274706929