Subject: [tcpm] Handling of FIN in the reassembly queue

From: Andre Oppermann <[email-masked]>
Date: Fri, 22 Feb 2008 00:09:22 +0100

The TCP reassembly queue is very good at handling and queuing out of
order data.  However correctly handling and queuing an out of order
FIN seems to be a bit tricky for a number of (broken) edge cases:

  1. FIN points into the middle of already queued data (or hole);
       Ignore the FIN and integrate the data?
       Ignore the whole segment with the bogus FIN?
       Integrate the data, move the FIN and flush excess data?

  2. FIN was already received and another one arrives pointing
     into the middle of already queue data (or hole);
       Ignore the FIN and integrate the data?
       Ignore the whole segment with the bogus FIN?
       Integrate the data, move the FIN and flush excess data?

  3. FIN was already received and another one arrives pointing
     beyond the previous one;
       Ignore the FIN and integrate the data (if within previous FIN)?
       Ignore the whole segment with the bogus FIN?
       Integrate the data and move the FIN?

  4. FIN without data pointing beyond already queued data;
       Queuing a standalone FIN w/o data and not directly attaching
       to the end of the queue complicates the implementation a lot.
       Is it acceptable to ignore the FIN for the moment and have it
       retransmitted (with or without data) later?

For reference the traditional reassembly queue implementation doesn't
care and queues any segment with FIN in any place.  Depending on the
hole situation this can lead to strange behavior and only ever partly
dequeued data.

Any input, insight and discussion welcome. :-)

-- 
Andre

_______________________________________________
tcpm mailing list
[email-masked]
http://www.ietf.org/mailman/listinfo/tcpm

---

From: "Anantha Ramaiah (ananth)" <[email-masked]>
Date: Thu, 21 Feb 2008 18:23:44 -0800

Andre,
        
> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Andre Oppermann
> Sent: Thursday, February 21, 2008 3:09 PM
> To: [email-masked]
> Subject: [tcpm] Handling of FIN in the reassembly queue
> 
> The TCP reassembly queue is very good at handling and queuing 
> out of order data.  However correctly handling and queuing an 
> out of order FIN seems to be a bit tricky for a number of 
> (broken) edge cases:
> 
>   1. FIN points into the middle of already queuedh data (or hole);

I would think discarding the FIN would be fine, but if the FIN gets
retransmitted again, then this puts a question mark on the data sitting
on the reassembly queue and in such cases we can possibly conclude the
data in the reassembly queue is bogus? 

This brings up another question  : suppose a TCP stack has sent s1, s2
s3 and s3 with FIN, assume s1 is dropped, is it ok to retransmit s1 with
FIN bit set (some stacks might see the state and blindly color the
segment with FIN) I don't think this is allowed? 

>        Integrate the data, move the FIN and flush excess data?

In the regular case (in-order) if the data is already consumed by the
application and the window has slided, TCP simply ignores the duplicate
data. Now for data sitting in the retransmission queue, we should
probably do the same, I would ignore the whole segment. [ I know in this
case FIN is extra]

>        Integrate the data and move the FIN?

Ignore the FIN.

>        retransmitted (with or without data) later?

Actually it depends on how the reassembly queue is implemented, if you
have a descriptor block for each data element sitting in the reassembly
queue, then you simply set a bit that indicating FIN is present which
you could do for the last segment sitting in the reassembly queue.

> 
> For reference the traditional reassembly queue implementation 
> doesn't care and queues any segment with FIN in any place.  
> Depending on the hole situation this can lead to strange 
> behavior and only ever partly dequeued data.
> 

I think it is an interesting discussion for sure :-). There are other
cases which come to mind as well (half-close and simultaneous close
cases)

-Anantha

---

From: David Borman <[email-masked]>
Date: Fri, 22 Feb 2008 12:17:10 -0600

Andre (and Anantha),

> data in the reassembly queue is bogus?

First, an important point:  Despite the fact that the BSD code calls  
it a reassembly queue, TCP does *NOT* have a reassembly queue, it has  
a *resequencing* queue.  This distinction is important, because its  
purpose is to defer processing of packets that were received out-of- 
order.  TCP packets are processed in sequence, as ordered by SEG.SEQ.   
In the resequencing queue, optimizations can be done to coalesce  
adjacent packets, but that doesn't change the fact that it is still a  
resequencing queue, for packets that have not yet been processed.   
(But as a side note, that's not entirely true.  Some processing of out- 
of-order packets has to happen when the packets arrive.  For example,  
the ACK field needs to be processed, as well as the Urgent pointer,  
but I won't go into the details here.)

For any TCP connection, in each direction there can be only one FIN,  
it will never move, and there will never be any valid data transmitted  
after the FIN.  So, if you get into this situation, you already have a  
problem, you just don't know what the problem is.  Either the  
previously received out-of-sequence data is bad, or the current packet  
with the FIN is bad, but you don't know which.

As to what to do if this scenario should actually happen:  If these  
packets were received in sequence, the packet with the FIN would put  
us into CLOSE-WAIT state.  The data in the packets with SEG.SEQ after  
the FIN would then be ignored, see page 75 in RFC 793.  So, it seems  
that the thing to do would be to integrate the data with the FIN, and  
flush the previously received data that is after the FIN.

> segment with FIN) I don't think this is allowed?

Absolutely not.  The FIN is part of the sequence space, it occupies  
one byte at the end of s3.  If you set FIN on s1, that is the same  
place in the sequence space as the first byte of s2.

> probably do the same, I would ignore the whole segment. [ I know in  

You should be consistent.  Once again, I'd say integrate the data and  
FIN into the resequencing queue, and flush the excess data beyond this  
FIN.

>>       Integrate the data and move the FIN?

Being consistent, throw away this new packet, since it is beyond the  
previous FIN.

>>       retransmitted (with or without data) later?

Yes, you can always throw away any out-of-sequence packets.  It's the  
same as if the packet got lost and never arrived in the first place.   
It'll arrive again either with the missing data just before the FIN,  
or in a separate retranmission or any other non-data packets with the  
same sequence number as the FIN.

> you could do for the last segment sitting in the reassembly queue.

The FIN occupies a specific byte in the sequence space.  You should  
still be able to attach the FIN at the end of the resequencing queue  
with a specific sequence number, you'd just have a length of zero with  
a bit saying that it contains the FIN.  Otherwise, you can always just  
ignore the FIN.

>> behavior and only ever partly dequeued data.

Yes, some interesting things could happen with the scenarios you  
mention, and not always the right thing.

			-David Borman

---

From: "Anantha Ramaiah (ananth)" <[email-masked]>
Date: Fri, 22 Feb 2008 11:38:16 -0800

David,
   Pl see inline..

> For any TCP connection, in each direction there can be only 
> one FIN, it will never move, and there will never be any 
> valid data transmitted after the FIN.  So, if you get into 
> this situation, you already have a problem, you just don't 
> know what the problem is.  Either the previously received 
> out-of-sequence data is bad, or the current packet with the 
> FIN is bad, but you don't know which.
> 
> As to what to do if this scenario should actually happen:  If 
> these packets were received in sequence, the packet with the 
> FIN would put us into CLOSE-WAIT state.  The data in the 
> packets with SEG.SEQ after the FIN would then be ignored, see 
> page 75 in RFC 793.  So, it seems that the thing to do would 
> be to integrate the data with the FIN, and flush the 
> previously received data that is after the FIN.

Agreed. Just to be clear, the rationale for me suggesting to drop the
segment with FIN in this case is :

If this is a genuine FIN, it would get retransmitted again. So you know
what to do the next time, ie., So just give it a chance one time, I
think this is more safer and robust but YMMV.

> > application and the window has slided, TCP simply ignores the 
> > duplicate data. Now for data sitting in the retransmission 
> queue, we 
> > should probably do the same, I would ignore the whole segment. [ I 
> > know in this case FIN is extra]
> 
> You should be consistent.  Once again, I'd say integrate the 
> data and FIN into the resequencing queue, and flush the 
> excess data beyond this FIN.

Well, we have already received a FIN, which means that ( going by your
CLOSEWAIT state example) we don't want to accept any data beyond this as
per RFC. Now we got a FIN which is way before the current sequence
number, in which case I would think it makes sense to ignore it. My
consistency reasons are :-
- if it would have been received in-order, we would have moved to
CLOSEWAIT and would have discarded the new FIN as duplicate ( the
receive window already slided, app might have already the data). TCP
window slides forward and in this and there is no provision for data
"overwrite". 

> Being consistent, throw away this new packet, since it is 
> beyond the previous FIN.

Yes, when I said ignore I meant discard, sorry should have been clear.

I would think it makes sense to throw away the FIN whether it is beyond
or before the previous FIN, to make things consistent. YMMV.

-Anantha

---

From: David Borman <[email-masked]>
Date: Fri, 22 Feb 2008 15:28:14 -0600

> think this is more safer and robust but YMMV.

Well, now you have to remember that you previously got this FIN, so  
that if it shows up again out of sequence you can do something  
different.  I don't like that additional complexity.  Keep it simple.   
(Or are you saying just keep ignoring the out-of-sequence FIN until  
the holes are filled and it shows up in sequence?)

> window slides forward and in this and there is no provision for data

But we haven't processed that data & FIN yet, because they came out of  
order.  They are to be processed in SEG.SEQ order, which means the  
earlier FIN is processed first (unless you received something like  
SEG1.SEQ=100,LEN=100,FIN and then SEG2.SEQ=150,LEN=0,FIN, in which  
case the later sequenced FIN would be processed first...)

The bottom line is that if you have two FINs, or data beyond a FIN,  
the connection is screwed up and it probably isn't worth putting much  
effort into dealing with this scenario.  Certainly it is not worth  
trying to optimize.  Your safest bet is to go to a fallback position  
and toss all the suspect data.  So, I'll stick with my original  
suggestion that all the out of sequence data after the earlier  
(sequence numbered) FIN be thrown away.  But we should probably also  
throw away the earlier FIN (and any data that it arrived with).  Then  
we've tossed all the suspect data, and the other side can retransmit  
what it thinks is the correct data, assuming it is able to do so.

			-David

---

From: Andre Oppermann <[email-masked]>
Date: Sun, 24 Feb 2008 01:59:50 +0100

> On Feb 22, 2008, at 1:38 PM, Anantha Ramaiah (ananth) wrote:

David, Anantha,

> Well, now you have to remember that you previously got this FIN, so that 
> if it shows up again out of sequence you can do something different.  I 
> don't like that additional complexity.  Keep it simple.  (Or are you 
> saying just keep ignoring the out-of-sequence FIN until the holes are 
> filled and it shows up in sequence?)
> 
> 
> SEG1.SEQ=100,LEN=100,FIN and then SEG2.SEQ=150,LEN=0,FIN, in which case 
> the later sequenced FIN would be processed first...)
> 
> The bottom line is that if you have two FINs, or data beyond a FIN, the 
> connection is screwed up and it probably isn't worth putting much effort 
> into dealing with this scenario.  Certainly it is not worth trying to 
> optimize.  Your safest bet is to go to a fallback position and toss all 
> the suspect data.  So, I'll stick with my original suggestion that all 
> the out of sequence data after the earlier (sequence numbered) FIN be 
> thrown away.  But we should probably also throw away the earlier FIN 
> (and any data that it arrived with).  Then we've tossed all the suspect 
> data, and the other side can retransmit what it thinks is the correct 
> data, assuming it is able to do so.

After reading and sleeping one night over this excellent discussion I realized
that we are unsafe at any speed here.

We may get hit with a FIN attack just as we may get hit with a RST attack.
A FIN anywhere in the window is valid and gets queued in the reassembly
queue for later processing.  This wrecks a TCP session by either ending
it prematurely in one direction (accepting the FIN closest to left edge),
or by preventing its legitimate ending (accepting only the first FIN and
waiting for data that never comes).  This is a serious threat.  Maybe even
more so than a pure RST attack with the same complexity.  It is much more
subtle and can cause long hangs for TCP based protocols that do not have
their own keepalive ping exchange.  tcpsecure doesn't even mention it.
I guess nodoby thought of the reassembly and its effects yet.  FIN deserves
its own section as well.

The solution I've come up with is to only accept a FIN when it matches the
left edge (rcv_nxt) either perfectly or accompanied by data that advances
rcv_nxt (the missing segment).  All data beyond that point in the reassembly
queue is then to be flushed.  All FINs that do not fulfill this condition are
to be ignored and not queued.  The only remaining question then is whether to
ignore the whole segment data that came with the FIN.  Probably not.  We can't
say if this is real FIN or not and consequently we can't say whether the
segment data is real or not.  We however have to assume it is real because
we don't have any evidence to the contrary (provided all tcp input validity
checks have been done previously).  This is a quite simple solution and it
avoids a lot of complexity in FIN handling in the reassembly queue.

If my reasoning and rationale is agreed with I can write up a FIN section
for tcpsecure over the next few days.

-- 
Andre

---

From: Jakob Heitz <[email-masked]>
Date: Sat, 23 Feb 2008 18:00:33 -0800

> for tcpsecure over the next few days.

You are free to drop any received data (including FIN) that you
have not yet acknowledged. The peer will retransmit. I suggest you
drop any segment that contains a suspicious FIN, and I stress drop
the whole segment. After all, if the FIN is suspicious, it will make
the rest of the segment suspicious too. I would call a FIN suspicious
if the resequencing queue contains any data (or another FIN) with a
higher sequence number. I would then drop all of this data higher in
the resequencing queue as well. All data in the resequencing queue
has not been acknowledged (even if it's SACKed) and the peer will
retransmit.

--
Jakob Heitz.

---

From: "Anantha Ramaiah (ananth)" <[email-masked]>
Date: Sat, 23 Feb 2008 21:47:44 -0800

Andre,
 
> 
> After reading and sleeping one night over this excellent 
> discussion I realized that we are unsafe at any speed here.
> 
> A FIN anywhere in the window is valid and gets queued in the 
> reassembly queue for later processing.  This wrecks a TCP 
> session by either ending it prematurely in one direction 
> (accepting the FIN closest to left edge), or by preventing 
> its legitimate ending (accepting only the first FIN and 
> waiting for data that never comes).  This is a serious 
> threat.  Maybe even more so than a pure RST attack with the 
> same complexity.  It is much more subtle and can cause long 
> hangs for TCP based protocols that do not have their own 
> keepalive ping exchange.  tcpsecure doesn't even mention it.
> I guess nodoby thought of the reassembly and its effects yet. 
>  FIN deserves its own section as well.

Actually as part of the data mitigation tcp-secure does mention FIN
attack, in the sense the strict ACK sequence number checking would
strengthen robustness in dealing with malicious data segments and that
includes FIN segments. 

FWIW, Murali and I are in the process of writing a document which
outlines the re-assembly (re-sequencing to use the correct terminology)
queue related DOS scenarios. We didn't consider FIN attacks as such..

> 
> The solution I've come up with is to only accept a FIN when 
> it matches the left edge (rcv_nxt) either perfectly or 
> accompanied by data that advances rcv_nxt (the missing 
> segment).  All data beyond that point in the reassembly queue 
> is then to be flushed.  All FINs that do not fulfill this 
> condition are to be ignored and not queued.  The only 
> remaining question then is whether to ignore the whole 
> segment data that came with the FIN.  Probably not.  We can't 
> say if this is real FIN or not and consequently we can't say 
> whether the segment data is real or not.  We however have to 
> assume it is real because we don't have any evidence to the 
> contrary (provided all tcp input validity checks have been 
> done previously).  This is a quite simple solution and it 
> If my reasoning and rationale is agreed with I can write up a 
> FIN section for tcpsecure over the next few days.

I would think having a separate document to address this instead of
putting stuff in tcp-secure since :

- the one which you are talking is about formulating the rules about
what to do with out-of-order FIN. It makes sense for a descriptive
document (like your original email) and outline pros and cons of each
method.

- tcpsecure has a section on data mitigation but it is about correcting
the liberal ACK checking allowed by 793 and it applies to ANY data
segment and also FIN. 

- tcpsecure has come a long way, and adding more stuff at this point
sounds uneasy to me. But that's just me.. 

My few cents,

-Anantha

---

From: David Borman <[email-masked]>
Date: Mon, 25 Feb 2008 11:22:26 -0600

My comments are at the bottom.
			-David Borman

On Feb 23, 2008, at 8:00 PM, Jakob Heitz wrote:

>>> case
>> reassembly
>> whether the

I agree with Jakob.  If you don't trust the FIN, you shouldn't trust  
the data, either.  Accept and queue any out-of-sequence FINs, and only  
worry about them if you get 1) a second FIN that doesn't match the  
first, 2) a FIN before data that you've already received, or 3) data  
after the FIN.  At that point, flush all the data from the first FIN  
to the end, including any data that came with that FIN.  Otherwise, if  
you reject all FINs until they show up right at the end of the  
connection, you are placing a penalty on all well-behaved TCP  
connections that just happen to have a packet loss or reordering of  
data packets just prior to the FIN.  Optimize for the common case, not  
the exception.  And keep in mind that there are perfectly legitimate  
reasons to get overlapping data (including the FIN), especially when  
retransmitting, but I won't go into the details here.

			-David Borman