Subject: Just what does "new" mean ?

From: Andreas Jungmaier <[email-masked]>
Date: Tue, 30 Mar 2004 15:52:45 +0200

Hi list,

you might want to ensure a fixed size font to understand the
picture below:

Assume (for simplicity) RWND==CWND==4000, all chunks that are sent
are of length 1000, all TSNs up to and including 0 have been acked.
All messages are sent ordered, and on one stream.

                   A                                      B
TSN 1              | ----------------------> X            |
TSN 2              | ----------------------------------> /| recv TSN 2, SACK
TSN 3              | ---------------------------------> //| recv TSN 3, SACK    
TSN 4              | -----------------------------------> | recv TSN 4, SACK    
TSN 5              | -----------------------------------> | recv TSN 5, SACK              
SACK(CTSNA 0)[2,2] | <------------------------------ //// |             
SACK(CTSAN 0)[2,3] | <------------------------------ ///  |             
SACK(CTSNA 0)[2,4] | <------------------------------ //   |             
SACK(CTSAN 0)[2,5] | <------------------------------ /    |             
TSN 1              | ----------Fast RTX-----------------> | Dropped, RWND==0
                                                            (send SACK with
                                                             arwnd==0)   

Now, the SACKs received by A allow A to send even more data, since 
they actually acknowledge the receipt of TSNs 2, 3 and so on. 
So: the receiver ends up (pretty soon) with a ARWND of 0.

The rule from the imp guide now says:
"The SCTP endpoint MUST always acknowledge the reception of each
 valid DATA chunk when the DATA chunk received is inside its receive
 window.

 When the receiver's advertised window is 0, the receiver MUST drop
 all new incoming DATA chunk and immediately send back a SACK with
 the current receive window showing only DATA chunks received and
 accepted so far.  The dropped DATA chunk MUST NOT be included in the
 SACK as they were not accepted."

Does this not require the receiver to drop the retransmission in the 
above case (since it is "new") ? 
Is the sender behavior incorrect in this case ?

- From Section 6.1 (also imp guide):
"At any given time, the sender MUST NOT transmit new data to a
 given transport address if it has cwnd or more bytes of data
 outstanding to that transport address. The sender may exceed cwnd
 by up to (PMTU-1) bytes on a new transmission if the cwnd is not
 currently exceeded."

In this case "new" referrs to data that has not yet been sent, whereas 
in the above case, "new" referrs to data that has never been received,
is that correct ?

Thanks

- -- Dipl.-Ing. Andreas Jungmaier              
Computer Networking Technology Group     
University of Duisburg-Essen                       
http://www.exp-math.uni-essen.de/~ajung   
PGP Key-ID: D382 4AC0             

PGP Key-Fingerprint: 228C 7C2C 3381 2DD4  9998 2812 5C0B 0B04  D382 4AC0

---

From: Janardhan Iyengar <[email-masked]>
Date: Tue, 30 Mar 2004 10:13:13 -0500 (EST)

Hi Andreas,

> TSN 1              | ----------Fast RTX-----------------> | Dropped, RWND==0

[...]

> Is the sender behavior incorrect in this case ?

I do think that the sender's behaviour is incorrect - the sender should
not send any more than allowed by rwnd. In your example, since rwnd is
4000 bytes, TSN 5 should not have been sent at all by the sender.
From Section 6.1 (A):
      "At any given time, the data sender MUST NOT transmit new data to
      any destination transport address if its peer's rwnd indicates
      that the peer has no buffer space ..."

That said, I am interested in understanding what happens when the sender
indeed violates the spec in this respect. How does the receiver
handle such a situation ? (The receiver could stall and the sender would
suffer, but that seems quite drastic.)

regards,
jana

---------------------------------------------------------------
         Visit www.narmada.org, www.indiatogether.org
---------------------------------------------------------------

---

From: Andreas Jungmaier <[email-masked]>
Date: Tue, 30 Mar 2004 17:20:56 +0200

Hi Janar,

> suffer, but that seems quite drastic.)

That's exactly what I think, and how I stumbled into this issue...
My sender mistakenly sent too much data, and the simulation got into 
this deadlock...

Andreas

- -- 
Dipl.-Ing. Andreas Jungmaier              
Computer Networking Technology Group     
University of Duisburg-Essen                       
http://www.exp-math.uni-essen.de/~ajung   
PGP Key-ID: D382 4AC0

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 30 Mar 2004 20:04:20 +0200

Andreas,

TSN 1 should not be dropped, because it is not new. It
would be interesting to show in your figure the reported
a_rwnd.

Because I would assume that an implementation would ack
TSN 2 with the gap report not with a_rwnd = 3000, but less
to leave space for TSN 1. I would expect something like
SACK(CTSNA 0; A_RWND 1500)[2,2]
SACK(CTSNA 0; A_RWND 1)[2,3]     (SWS)
SACK(CTSNA 0; A_RWND 0)[2,4]
SACK(CTSNA 0; A_RWND 0)[2,4]     (dropping TSN 5)

So you will wait for T3 to expire. Of course you can get
it fast retransmitted by having a larger window than 4000.

The important point here is that you should always have left
to accept missing data. If that is not possible you must
reneg. But this should only be the last possible solution.

Best regards
Michael

On Mar 30, 2004, at 3:52 PM, Andreas Jungmaier wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi list,
>
>                                                             (send SACK 
> with
It is NOT new. New means 'higher' TSN than all other seen chunks.
> in the above case, "new" referrs to data that has never been received,
Yes, I think so. New is a pretty vage word....
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.2.3 (GNU/Linux)
>
> iD8DBQFAaXutXAsLBNOCSsARAulaAJwMV5YBZc4SxmwpG6UCSm0Wa2Ih2gCcCUWb
> yysxKnNjCW/lulAXCggc45c=
> =zcAw
> -----END PGP SIGNATURE-----

---

From: Andreas Jungmaier <[email-masked]>
Date: Tue, 30 Mar 2004 20:51:35 +0200

Michael,

> would be interesting to show in your figure the reported

Interesting: this is pretty much what I discussed a while ago
with Ivan (and actually that was my original point for this
thread): what is NEW ?

One could say that TSN 1 is new (because B has not yet seen it).
This ought to be specified more precisely in the imp guide.

                    A                                      B
> SACK(CTSNA 0; A_RWND 0)[2,4]     (dropping TSN 5)

Something like that is nowhere in the specs ! If I understand you 
correctly, that means you assume the dropped TSN to be of an MTU size 
(which would be something like 1452 rather than 1500 for IPv4 over 
Ethernet), and make the implementation deduct a full MTU for each
missing TSN ? I am not sure that would work.
 
> it fast retransmitted by having a larger window than 4000.

4000 was just an example.

> The important point here is that you should always have room 
> left to accept missing data. If that is not possible you must

Really, in case of a sender behaving like this (which it clearly
should not do, I am sure you agree), reneg is probably the only 
way to avoid a deadlock...

- --

---

From: Michael Tuexen <[email-masked]>
Date: Tue, 30 Mar 2004 22:29:46 +0200

Andreas,
see my comments inline.
Best regards
Michael

> with Ivan (and actually that was my original point for this
I agree, it might be not clear.
> This ought to be specified more precisely in the imp guide.
I'll take that to the list of things to clarify.
>                                                              (send 
> SACK with
This does not have to be in the spec, because it is local behaviour.
You should always have room to accept the missing data. How you do
this depends on your implementation. You might have a shared buffer
(MBUFs, for example) for the whole protocol. You example assumes that
you really have a specific buffer for an association.
The number 1500 is only an example. Looking at implementations you
use some pool elements of fixed size. You only have the choice between
some values. I just wanted to make clear that you might reduce the 
a_rwnd
due to gaps. I do know that the above description is vage, but there
is a lot of implementation dependent stuff and if you really have no
space left you have to reneg. That is why reneg exists.
> 4000 was just an example.
I know.
> way to avoid a deadlock...
If you as a receiver accept so much data that you can not handle
from a buffer point of view the data which fills gaps you did not
make the best choice as a receiver... You must use reneg in that
case. I think the problem in your example the behaviour of the
receiver is not OK, what is wrong with the sender?

You just have to apply the correct meaning of 'new', I think.
> iD8DBQFAacG3XAsLBNOCSsARAiKHAKDoGFkn4q890N/3P2L/8bnM8DYg5ACggpUA
> GyXA7BgufbbXFyOjSmO+4XE=
> =rhxm

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Tue, 30 Mar 2004 15:41:14 -0700

Andreas,

Yes, the sender is wrong, but if the receiver does not allow some limited
(non-advertised) headroom on the receive buffer, these effects can always
occur.

Consider that the sender may not be just be incorrect, it may be a malicious
tear-drop attacker.

To be invulnerable to both, the receive must either reneg or abort.

Abort is ok because the sender has violated the protocol (sending beyond the
peer's RWND).

Reneg is more robust to poor sender implementations.  When TSN 1 is received,
knowing that there are gap acked TSNs in the receive buffer, the sender could
reneg on one or more of the gap acked TSNs and clear them from the receive
buffer, making room for the cummulatively ackable TSN.  The simplest approach
might be to clear all gap acked TSNs (TSN 2 through 5 in the example) from the
receive buffer when the receive buffer is full and the received TSN advances
the cummulative ack point.  This simple approach most effectively thwarts most
tear-drop attacks.

If the received TSN does not advance the cumulative ack point, it is a window
probe (TSN 6) and can be dropped.  (The sender would be in error because the
IG says that zero window probes SHOULD only be sent with all outstanding data
cummulatively acked and no data in flight, which is not the circumstance
here.)

Renegging was always intended to be able to clear an accumulation of gap acked
TSNs from the receive buffer impeding progress of the cummulative ack point.
This is perhaps a classical example of a circumstance where renegging is best
applied.

The IG says that new data is dropped when the receive buffer is full, but it
does not preclude the implementation from harvesting receive buffer space by
renegging to accommodate progress on the cummulative ack point, which is what
a robust receiver would do here.  A less forgiving receiver can abort the
association due to the sender's protocol violation.

--brian

-- 
Brian F. G. Bidulock    ¦ The reasonable man adapts himself to the ¦
[email-masked]    ¦ world; the unreasonable one persists in  ¦
http://www.openss7.org/ ¦ trying  to adapt the  world  to himself. ¦
                        ¦ Therefore  all  progress  depends on the ¦
                        ¦ unreasonable man. -- George Bernard Shaw ¦

---

From: Kacheong Poon <[email-masked]>
Date: Tue, 30 Mar 2004 17:48:02 -0800

> (non-advertised) headroom on the receive buffer, these effects can always

Do you mean to suggest that a receiver should always allow receiving
data outside its advertised receive window?  This does not seem right.
I guess unless the protocol spec is broken, a receiver implementation
should not need to cope with it this way.  Do you see a case when this
can happen when both sides conform to the current spec?

> Consider that the sender may not be just be incorrect, it may be a malicious

By tear-drop attacker, do you mean a similar mechanism as in the IP
fragments attack?  If you do, I don't think it is an effective attack
which we need to be concerned.  And an appropriate response to this
kind of attack in the SCTP level (leaving a hole in the receive queue
to hold up buffers) is to time out.  For example, the application
can time out and abort the association if it does not receive anything
for a  specified period of time.  Handling this in the SCTP level does
not seem to be a good solution.

-- 

						K. Poon.
						[email-masked]

---

From: "Brian F. G. Bidulock" <[email-masked]>
Date: Tue, 30 Mar 2004 23:36:28 -0700

Kacheong,

> data outside its advertised receive window?  This does not seem right.

Consider that when the packet arrives, to determine whether it is "new" or
"old" it must first have been received and buffered to be examined regardless
of the receiver window.  If the system refuses to receive any packets beyond
the advertised receive window, it cannot follow the specification and make the
"new" vs. "old" determination.

In fact, as I believe you mentioned in another mail on this thread, the
advertised window and available receive buffer space are not necessarily the
same thing.  And in most implementations of TCP or SCTP they are not.  The
already buffered packet is "charged" to the receive buffer (and window).  No
resource allocation occurs at this point, just a resource accounting.  The
packet is creditted to the IP queue and charged to the socket if you will.

Although there are indeed less classical implementations, this is the typical
arrangement.

> can happen when both sides conform to the current spec?

My point is that if packets are not permitted to be receive, buffered and
examined by the socket even though the advertised receive window has fallen to
zero, then the implementation cannot conform to the specification.

Consider also the zero window probe, which was the other thing that we debated
and resolved along with accepting packets after a_rwnd is zero.  If an
implementation discards packets entirely when a_rwnd is zero, then it will be
unable to respond to zero window probes.  It must buffer the packet and
examine it (beyond a_rwnd) to be able to discard and SACK it.

> not seem to be a good solution.

Tear-drop like attacks rely upon leaving holes and causing the receiver (or
sender) to allocate resources excessively.  I don't mean the neo-classical
tear-drop attack (where resources are unwisely allocated unbounded for the
gaps rather), but a situation where the described scenario can be used by
an attacker to cause an implementation to overcommit resources.

Consider, for examle, an HTTP server with similar receive characeteristics
to those described by Adreas.  Upon connection, the  attacker intentionally
skips TSN 1 and then sends data until the advertised receive window falls to
zero.  As the HTTP server sits on the socket waiting for data, and data
indications will not be forthcoming (make all the packets segments of a single
unit data) the service process is hung for a period and the memory allocation
for the receive buffer is frozen.  If the server is overcommitting memory on
receive buffers, repetitions of this procedure in a not unreasonably short
period will result in denial of service.

If the receiver does not include allocations necessary to maintain gaps in the
receive window (or buffer) accounting, it could be possible to introduce gaps
that cause the memory allocation to grow excessively if not unbounded.
Consider sending a 1 byte data chunks, skipping a TSN, sending another 1 byte
data chunks, skipping a TSN, and so on.  If there is no hard limit on
overheads require to track gaps, a problem will occur.

I refer to these as tear-drop attacks because they all rely on the same
principle as the neo-classical TCP tear-drop attack.  In the neo-classical TCP
tear-drop attack, an implementation that allocates memory for missing segments
without consideration for window or buffer limits are susceptible to the
attack in sending a kiss of death segment which skips large extents of
intervening segments, causing buffer overflow.

If any resource is allocated for intervening missing TSNs, an attacker might
be able to send a TSN far advanced from the cumulative ack point and cause an
allocation overflow.

Perhaps I am wrong to call these tear-drops, but perhaps my meaning is more
clear now.

Renegging (or aborting of course) is a way of freeing resources associated
with things not directly related to advancing the cumulative ack point.  All
of these types of attacks depend upon allocating, overallocating, or freezing
resources that do not advance the cummulativve ack point.  Renegging when the
limit is reached is a simple way of thwarting these types of attacks.

--brian

---

From: Andreas Jungmaier <[email-masked]>
Date: Wed, 31 Mar 2004 11:41:35 +0200

Brian,

please see my comments below:

> (non-advertised) headroom on the receive buffer, these effects can always

The sender is wrong because it sends more data than the ARWND allows
(in my example it sends 5 packets with 1000 bytes each), and ARWND was
4000 bytes.

However, in this case, as soon as the receiver B announces a ZERO arwnd 
in the SACK chunks returned to A, it is required to drop any NEW chunks, 
as stated in the IG. 

Now, if NEW means anything it has not seen so far (which could be one
way to interpret the word "new"), this will cause a deadlock.

I absolutely agree with you that in this (corner) case, the receiver
should reneg, or it could start dropping (higher) TSNs received before 
the window finally closes, and thus always keep room for TSNs that 
advance the CTSNA (e.g. at the point in time when it starts to announce 
a 1 byte ARWND during SWS avoidance). 

I also agree with you that implementations always need at least room
to store and look at a newly received packet with data -- but that 
generally is the case, I think...

                   A                                      B
TSN 1              | ----------------------> X            |
TSN 2              | ----------------------------------> /| recv TSN 2,SACK 
TSN 3              | ---------------------------------> //| recv TSN 3,SACK 
TSN 4              | -----------------------------------> | recv TSN 4,SACK 
TSN 5              | -----------------------------------> | recv TSN 5,SACK 
SACK(CTSNA 0)[2,2] | <------------------------------>//// |
SACK(CTSAN 0)[2,3] | <------------------------------ ///  |
SACK(CTSNA 0)[2,4] | <------------------------------ //   |
SACK(CTSAN 0)[2,5] | <------------------------------ /    |
TSN 1              | ----------Fast RTX-----------------> | Dropped, RWND==0
                                                            (send SACK with
                                                             arwnd==0)
"When the receiver's advertised window is 0, the receiver MUST drop
 all new incoming DATA chunk and immediately send back a SACK with
 the current receive window showing only DATA chunks received and
 accepted so far.  The dropped DATA chunk MUST NOT be included in the
 SACK as they were not accepted."

- --

---

From: Kacheong Poon <[email-masked]>
Date: Wed, 31 Mar 2004 20:06:50 -0800

> Although there are indeed less classical implementations, this is the typical

Agreed.  But we are talking about whether at the SCTP protocol level,
the protocol engine should queue a new (we should stick with the obvious
meaning of not yet received) packet when its receive window is full.
We are not concerned in this discussion with the memory already
allocated to hold the packet in a system.

> examine it (beyond a_rwnd) to be able to discard and SACK it.

I understand this point.  But I think we should stick to the question
of whether an SCTP stack should accept a new packet when its receive
window is full.  We can assume that the SCTP stack can actually look
at the packet and determine that it is the destined recipient and
the normal checks pass (CRC32c, verf tag...).

> an attacker to cause an implementation to overcommit resources.

This is what I guessed.

> overheads require to track gaps, a problem will occur.

OK.

> limit is reached is a simple way of thwarting these types of attacks.

I understand your point.  And there are many ways to deal with this
kind of attack.  For example, the app layer time out as I mentioned
in the previous mail can help.  Or the SCTP layer can decide to free up
some packets as you suggested.  My point is that the stack does not need
to do this defense only when the receive window is full.  If the memory
resource is tight, the SCTP layer may decide not to queue any out
of order packets.

What we are dealing with here is that at the protocol level, SCTP
should not accept new packets when its receive window is full.  We need
to make sure that no conforming SCTP implementation will hit the dead
lock situation discussed so far.  If this is true, then we can think
of whether good SCTP implementations should accommodate non-conforming
implementations.  And I don't think this has to be tied to the attack
you mentioned above.

-- 

						K. Poon.
						[email-masked]