Subject: apology to Bob
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Date: Fri, 10 Apr 92 12:54:45 MST

Of course Bob is correct and any posting of 
his TWA paper to this group should have come from 
through him. Please disregard my posting. 

Sean W. O'Malley

Date: Fri, 10 Apr 92 12:21:20 PDT
From: [email-masked]
Posted-Date: Fri, 10 Apr 92 12:21:20 PDT
To: [email-masked], [email-masked]
Subject: Re:  Bradens PAWS bug

	From [email-masked] Fri Apr 10 09:35:14 1992
	Date: Fri, 10 Apr 92 09:33:39 MST
	From: "Sean O'Malley" <[email-masked]>
	To: [email-masked]
	Subject: Bradens PAWS bug

	Bob Braden put out a document to the endtoend interest group 
	outline a set of problems with the PAWS mechanism. The question 
	is does this group want to reopen the PAWS discussion?

Sean,

This is an inaccurate characterization of my message.  My note is NOT
about a bug in PAWS; mmy tests indicate that PAWS works just fine.  My
note might be described as a bug in the current TCP, but I would not
use such a term, for fear of what Communication Weekly would do with
it!

PAWS still does exactly what it was designed to do: prevent TCP errors
caused by high bandwidths.  PAWS has the bonus that it fixes the most
serious of the TWA hazards, erroneous data delivery.  PAWS cannot
prevent unnecessary (but probably extremely rare) connection failures
due to TWA.

There is a real question whether the TWA hazards are more than a highly
theoretical exercise.  I do not think the research on this is complete
(which is why I did not send it to the tcplw list).  I pointed out in
my note that I believe that 64-bit sequence numbers will solve the TWA
hazards.  I also believe that instituting 64-bit sequence numbers is a
subtle issue, that needs to be approached with some care and
understanding.  In short, it is a useful avenue for research at this
time.

Sean, you will find the Internet community downright hostile, if you do
not show the normal courtesies due to fellow researchers -- like
checking with someone before forwarding his paper to a mailing list,
especially with misleading implications.

Bob Braden

Date: Fri, 10 Apr 92 09:33:39 MST
From: "Sean O'Malley" <[email-masked]>
To: [email-masked]
Subject: Bradens PAWS bug

Bob Braden put out a document to the endtoend interest group 
outline a set of problems with the PAWS mechanism. The question 
is does this group want to reopen the PAWS discussion?

Bob's Document follows:

 
                                                              April 2, 1992

              TIME-WAIT ASSASSINATION HAZARDS FOR TCP
                       Bob Braden, USC-ISI

Experiments to validate the proposed TCP extensions led me to
investigate an interesting class of TCP failures that I call the
"Time-Wait Assassination" (TWA) hazards.  I believe that these hazards
exist in current TCP at current rates, although they may be more likely
on "fast" network paths, those with bandwidth >> 2Mbps.  This note
describes the hazards, gives examples, and discusses possible
prevention measures.  In particular, it considers the impact of
Jacobson's time-stamp based PAWS ("Protect Against Wrapped Sequences")
mechanism, which is one of the proposed TCP extensions.

1. Time-Wait Assassination

TCP uses sequence numbers to protect against old duplicate segments
from the current incarnation of a given connection (defined by a
particular host and port pair).  If the bandwidth is very high, the
PAWS mechanism of RFC-1185 will effectively extend the sequence numbers
so wrap-around will not be a hazard.  Time-Wait state removes the
hazard due to old duplicate segments from an earlier instance of the
same connection [See e.g. Appendix to RFC-1185].  Time-Wait state
prevents reopening the same TCP connection for 4 minutes, which is
assumed to be time enough for all old duplicates to die in the
Internet.

We now observe that Time-Wait state can be killed ("assassinated") by
an old duplicate segment, either data or ACK, from the current or an
earlier incarnation of the same connection.  Figure 1 shows an
example.

In Figure 1, segments 1-5 are copied exactly from Figure 13 of RFC-793,
showing a normal close handshake.  Packets 5.1, 5.2, and 5.3 are an
extension to this sequence, illustrating TWA.   Here 5.1 is ANY OLD
SEGMENT that is unacceptable to TCP A.  It might be unacceptable
because of its sequence number or because of an old PAWS timestamp.  In
either case, TCP A sends an ACK segment 5.2 for its current SND.NXT and
RCV.NXT.  Since it has no state for this connection, TCP B reflects
this as RST segment 5.3, which assassinates the TIME-WAIT state at A!

Note that TWA is not at all an unlikely event, if there are any
duplicate segments that may be delayed in the network.  Furthermore,
TWA cannot be prevented by PAWS timestamps; the event may happen within
the same tick of the timestamp clock.  TWA is a consequence of TCP's
half-open connection discovery mechanism (see pp 33-34 of RFC-793) to
clean up after a system crash.



      TCP A                                                TCP B

  1.  ESTABLISHED                                          ESTABLISHED

  2.  (Close)
      FIN-WAIT-1  --> <SEQ=100><ACK=300><CTL=FIN,ACK>  --> CLOSE-WAIT

  3.  FIN-WAIT-2  <-- <SEQ=300><ACK=101><CTL=ACK>      <-- CLOSE-WAIT

  4.                                                       (Close)
      TIME-WAIT   <-- <SEQ=300><ACK=101><CTL=FIN,ACK>  <-- LAST-ACK

  5.  TIME-WAIT   --> <SEQ=101><ACK=301><CTL=ACK>      --> CLOSED

 - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  5.1. TIME-WAIT   <--  <SEQ=255><ACK=33> ... old duplicate

  5.2  TIME-WAIT   --> <SEQ=101><ACK=301><CTL=ACK>    -->  ????

  5.3  CLOSED      <-- <SEQ=301><CTL=RST>             <--  ????

 - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  6.  (2 MSL)
      CLOSED                           
                        Figure 1.  TWA Example

2. The TWA Hazards

If the connection is immediately reopened after a TWA event, the new
incarnation will be exposed to old duplicate non-SYN segments (the
3-way handshake handles SYN-segment hazards).

Clock-driven ISN selection guards against old duplicates for "short and
slow" connections [see eg the appendix to RFC-1185] [The algorithm used
by BSD for stepping ISN complicates the analysis slightly, but does not
change the conclusions].  However, clock-driven ISN selection does not
guard against old duplicates for "fast" or "long" connections;  in
either case, the sequence space of the old connection incarnation may
overlap the sequence space of the new incarnation.  Each of the
following possible hazards depend upon overlap of sequence space from
the previous incarnation.

H1. Old duplicate data may be accepted erroneously.

H2. The new connection may die.

    A duplicate segment (data or ACK) arriving in SYN-SENT state
    may kill the new connection after it has apparently opened
    successfully.

H3. The new connection may be de-synchronized, with the two ends
    in permanent disagreement on the state.

    Following the spec of RFC-793, this will result in an infinite ACK
    loop (!); it might be reasonable to change this aspect of RFC-793
    and kill the connection instead.  This hazard results from ACKing
    somethat that was not sent.  This may result from an old duplicate
    ACK or as a side-effect of hazard H1.

Example scenarios for these hazards are given later.  Note that each of
these requires the coincidence of the old duplicate falling into a
particular range of sequence numbers.  Thus, they are not as likely as
TWA itself.

I have demonstrated TWA and the three hazards H1, H2, and H3, using
stock Sun OS 4.1.1 TCP running in an simulated environment that
deliberately duplicates segments.  This environment is far more
hazardous than most real TCP's must cope with.  However, the
demonstration gives us confidence in the existence of the hazards.

3. Fixes for TWA Hazards

We discuss two possible fixes to the current TCP, to avoid these
hazards.

(F1)  Ignore RST segments in Time-Wait state.

      This is the simplest fix, and if the 2 minute MSL (Maximum
      Segment Lifetime) of TCP is enforced, it avoids all three
      hazards.  One could also argue that this is formally the correct
      thing to do; since one of Time-Wait state's functions is to allow
      any old duplicate segments to die, it should not be interrupted
      by a RST.  After a system crash, the Quiet Time at system startup
      will replace the Time-Wait delay.

      On the other hand, this fix leaves me a bit uneasy about
      robustness.  The RST mechanism is designed to bring
      both sides into agreement, and turning it off in Time-Wait
      state could make it more difficult to recover from some
      pathological situations.

(F2)  Use PAWS to avoid the hazards.

      Mechanism: ignore RST segments in Time-Wait state, but only long
      enough to guarantee that the timestamp clocks on both ends have
      ticked.  Then PAWS will prevent old duplicate data segments from
      interfering with new incarnation.  For reasons explained below,
      it may not eliminate all old duplicate ACK segments, so hazards
      H2 and H3 still exist.

      In the language of the forthcoming TCP Extensions RFC:

           When processing a RST bit in TIME-WAIT state:

               If (Snd.TS.OK is off) or (Time.in.TW.state() >= Q)
                   then enter the CLOSED state, delete the TCB,
                   drop the RST segment, and return.

               else simply drop the RST segment and return. 
                     
      Here "Time.in.TW.state()" is a function returning the elapsed time
      since Time-Wait state was entered, and Q is a constant that is at
      least twice the longest possible period for timestamp clocks.
      The TCP Extension RFC requires a period in the range of 1 sec - 1
      ms.  Thus, we could choose Q = 2 seconds.

      This assumes that the timestamp clock at each end continues to
      advance at a constant rate, whether or not there are any open
      connections.  We do not have to consider what happens across a
      system crash (e.g., the timestamp clock may jump randomly),
      because of the assumed Quiet Time at system startup.

      Once this change is in place, the initial timestamps that occur
      on the SYN and {SYN,ACK} segment reopening the connection will be
      larger than any timestamp on a segment from earlier
      incarnations.  As a result, the PAWS mechanism operating in the
      new connection incarnation will avoid the H1 hazard, ie.
      acceptance of old duplicate data.

      I have demonstrated the effectiveness of F2 in preventing
      acceptance of old duplicate data segments in the Sun OS TCP
      mentioned earlier.

      Unfortunately, these tests also revealed a somewhat surprising
      fact: old duplicate ACKs from the earlier incarnation can still
      slip past PAWS, so that F2 will not prevent failures H2 or H3.
      What happens is that Time-Wait state effectively regenerates the
      timestamp of an old duplicate ACK.  That is, when an old
      duplicate arrives in Time-Wait state, an extended TCP will send
      out its own ACK with a timestamp option containing its CURRENT
      timestamp clock value.  If this happens immediately before the
      TWA mechanism kills Time-Wait state, the result will be a "new
      old duplicate" segment with a current timestamp, which may be
      able to pass the PAWS test on the reopened connection.

We can modify F2 to accomodate the second function of TIME-WAIT state,
supporting the bi-directional reliable close of TCP.  We would do so by
replacing Q by max(Q, N*RTT), where N is chosen constant and RTT is the
measured round-trip time.  We choose N large enough so that there is
sufficient probability of the close completing successfully if at all
possible, and assume that the RTT is appproximately the same in both
directions.  It only possible to have many short connections if RTT
is very small, in which case the mimimum TIME-WAIT time reduces to Q.

Shortening TIME-WAIT state as in F2 is very attractive, since it helps
the problem of excessive resources tied up by many short connections.
Unfortunately, it does not prevent H2 or H3.  Only F1 will do that.
Whether H2 and H3 are critical depends upon how often they happen, and
what assumptions applications make about TCP semantics.  In fact, many
production TCPs have (despite the advice of the researchers who
developed TCP) incorporated keep-alives which tended to often kill
connections unnecessarily.  The frequency of occurrence of H2 and H3
may well be much lower than keep-alive failures or total communication
failures.

4.  A More Radical Solution  

O'Malley and Peterson have suggested that simply expanding the TCP
sequence space to 64 bits would be simpler than PAWS for preventing
wrapped sequence numbers.  We should consider the impact on the TWA
hazards of using 64-bit sequence numbers.

The 64 bit space is so large that sequence numbers need "never" be
reused.  If a connection ran at a terabyte per second, the sequence
space would take over 200 years to wrap its sign bit.  If we assume no
connection lasts that long, there will be no "long" connections.  We
can also increase the frequency of the timer-driven ISN selection to
e.g. incrementing the low order bit every nanosecond.  Then all
connections will "short" and "slow" in the sense of the Appendix to
RFC-1185, and the timer-driven ISN selection will prevent any overlap
of sequence numbers in successive connections.

64 bit sequence numbers will not prevent TWA itself - the early
termination of Time-Wait state due to an old duplicate from the SAME
incarnation.  However, 64 bit sequence numbers WILL prevent the
accompanying hazards H1, H2, and H3, since these hazards all depend
upon sequence number reuse across connection incarnations.
Furthermore, 64 bits sequences plus a limited connection lifetime (200
years) will obviate the need to Time-Wait state to let old duplicates
die.   Then Time-Wait state will be required only to support reliable
close; therefore, Time-Wait state timeout can be set to N*RTT, allowing
many short connections (i.e., "transactions") when RTT is small.

Thus, I concur with O'Malley and Peterson that expansion to 64 bit
sequence space is an attractive fix, at least from the viewpoint of the
ideal world of research.  It amounts to rescaling the problem out of
existence.  It is probably not a temporary fix, as it will extend
reliable TCP operation to speeds which are many orders of magnitude
beyond the likely upper limit of usefulness of a window-based
protocol.

 
_______________________________________________________________________
_______________________________________________________________________
Appendix

SCENARIOS:

Each of the following scenarios assumes that a TWA event has
occurred and that the connection has been reopened soon thereafter.

HAZARD H1: Acceptance of erroneous old duplicate data.

      TCP A                                                  TCP B

 1. ESTABL.  --> <SEQ=400><ACK=101><DATA=100><CTL=ACK> -->  ESTABL.
 
 2. ESTABL.  <--     <SEQ=101><ACK=500><CTL=ACK>     <--    ESTABL.

 3.  (old dupl)...<SEQ=560><ACK=101><DATA=80><CTL=ACK> -->  ESTABL.

 4. ESTABL.  <--     <SEQ=101><ACK=500><CTL=ACK>     <--    ESTABL.
 
 5. ESTABL.  --> <SEQ=500><ACK=101><DATA=100><CTL=ACK> -->  ESTABL.

 6.             ...  <SEQ=101><ACK=640><CTL=ACK>     <--    ESTABL.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
 
 7a. ESTABL.  --> <SEQ=600><ACK=101><DATA=100><CTL=ACK> -->  ESTABL.
 
 8a. ESTABL.  <--    <SEQ=101><ACK=640><CTL=ACK> ...

 9a. ESTABL.  --> <SEQ=700><ACK=101><DATA=100><CTL=ACK> -->  ESTABL.

                   Figure 2: Accepting Erroneous Data

Old duplicate data segment 3 falls within the current receive window
and is queued.  It "lurks" in the TCP reassembly queue until segment 5
overlaps it.  At that point, either 80 or 40 bytes of erroneous data is
delivered to the user B; the choice depends upon the particulars of the
reassembly algorithm, which may accept the first or the last duplicate
data.

As a result, B sends segment 6, an ACK for something that A did not
send.  Assume for the present that this ACK arrives at A *after* A has
sent segment 7a, the next full data segment.  In that case, the ACK
segment 8a acknowledges data that has been sent, and the error goes
undetected.  Another possible continuation after segment 6 leads to
hazard H3, as shown below.

________________________________________________________________________

HAZARD H2:  Connection Failure

      TCP A                                                    TCP B

  1.  CLOSED                                                   LISTEN

  2.  SYN-SENT    --> <SEQ=100><CTL=SYN>                  --> SYN-RECEIVED

  3.         ... <SEQ=400><ACK=101><CTL=SYN,ACK><WIN=800> <-- SYN-RECEIVED

  4.  SYN-SENT    <-- <SEQ=300><ACK=123><CTL=ACK> ... (old duplicate)

  5.  SYN-SENT    --> <SEQ=123><CTL=RST>                    --> LISTEN
  
  6.  ESTABLISHED  <-- <SEQ=400><ACK=101><CTL=SYN,ACK><W=900> ...

  7.  ESTABLISHED  --> <SEQ=101><ACK=401><CTL=ACK>          --> LISTEN

  8.  CLOSED      <--  <SEQ=401><CTL=RST>                   <-- LISTEN

         Figure 3: Connection Failure from Old Duplicate

TCP A sees an apparent refusal of its connection attempt, due to the
old duplicate ACK segment #4.  The key to this failure is that the RST
segment 5 is acceptable to TCP B in SYN-RECEIVED state.  This is only
possible when the sequence space of the earlier connection that
produced this old duplicate overlaps the new connection space; e.g.,
<SEQ=123> in segment #5 falls within TCP B's receive window [100,900).

Note that PAWS cannot prevent this failure mode.  The PAWS procedure
does not maintain the remote timestamp between connections, so it
cannot do a timestamp check on a segment received in SYN-SENT state.
Even if it did a timestamp check, the timestamp might be current
because of the regeneration feature of Time-Wait state, and even if it
failed, the result would probably be just to send the same RST segment

It was quite easy to demonstrate this failure mode.

___________________________________________________________________
___________________________________________________________________

HAZARD H3: De-synchronized Connection

As mentioned earlier, this can happen either as a side effect of H1
or directly from an old duplicate ACK that happens to be exactly
acceptable but ACKs something that has not been sent.

Referring to Figure 2 above, suppose that the ACK generated by the old
duplicate data segment arrived before the next data segment had been
sent.  The result is an infinite ACK loop, as shown by the following
alternate continuation of Figure 2.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
 
 7b. ESTABL.  <--    <SEQ=101><ACK=640><CTL=ACK>   ...
(ACK something not yet
 sent => send ACK)

 8b. ESTABL.  -->    <SEQ=600><ACK101><CTL=ACK>       -->   ESTABL.
                                                      (Below window =>
                                                       send ACK)

 9b. ESTABL.  <--    <SEQ=101><ACK=640><CTL=ACK>     <--    ESTABL.

                          (etc.!)

                Figure 4: Infinite ACK loop
___________________________________________________________________