As per Relevance of the word duplicate, we have this rfc below:
Network Working Group R.
Request for Comments: 1337
May 1992
TIME-WAIT Assassination Hazards in
Status of This
This memo provides information for the Internet community. It
not specify an Internet standard. Distribution of this memo
unlimited
This note describes some theoretically-possible failure modes for
connections and discusses possible remedies. In particular, one
simple fix is identified
1.
Experiments to validate the recently-proposed TCP extensions [RFC
1323] have led to the discovery of a new class of TCP failures,
have been dubbed the "TIME-WAIT Assassination hazards". This
describes these hazards, gives examples, and discusses
prevention measures
The failures in question all result from old duplicate segments.
brief, the TCP mechanisms to protect against old duplicate
are [RFC-793]:
(1) The 3-way handshake rejects old duplicate initial
segments, avoiding the hazard of replaying a connection
(2) Sequence numbers are used to reject old duplicate data and
segments from the current incarnation of a given
(defined by a particular host and port pair). Sequence
are also used to reject old duplicate segments
For very high-speed connections, Jacobson's PAWS ("
Against Wrapped Sequences") mechanism [RFC-1323]
extends the sequence numbers so wrap-around will not introduce
hazard within the same incarnation
(3) There are two mechanisms to avoid hazards due to old
segments from an earlier instance of the same connection;
the Appendix to [RFC-1185] for details
Braden [Page 1]
RFC 1337 TCP TIME-WAIT Hazards May 1992
For "short and slow" connections [RFC-1185], the clock-
ISN (initial sequence number) selection prevents the overlap
the sequence spaces of the old and new incarnations [RFC-793].
(The algorithm used by Berkeley BSD TCP for stepping
complicates the analysis slightly but does not change
conclusions.)
(4) TIME-WAIT state removes the hazard of old duplicates for "fast
or "long" connections, in which clock-driven ISN selection
unable to prevent overlap of the old and new sequence spaces
The TIME-WAIT delay allows all old duplicate segments
enough to die in the Internet before the connection is reopened
(5) After a system crash, the Quiet Time at system startup
old duplicates to disappear before any connections are opened
Our new observation is that (4) is unreliable: TIME-WAIT state can
prematurely terminated ("assassinated") by an old duplicate data
ACK segment from the current or an earlier incarnation of the
connection. We refer to this as "TIME-WAIT Assassination" (TWA).
Figure 1 shows an example of TIME-WAIT assassination. Segments 1-5
are copied exactly from Figure 13 of RFC-793, showing a normal
handshake. Packets 5.1, 5.2, and 5.3 are an extension to
sequence, illustrating TWA. Here 5.1 is *any* old segment that
unacceptable to TCP A. It might be unacceptable because of
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
segment 5.3, which assassinates the TIME-WAIT state at A
Braden [Page 2]
RFC 1337 TCP TIME-WAIT Hazards May 1992
TCP A TCP
1. ESTABLISHED
(Close
2. FIN-WAIT-1 --> --> CLOSE-
3. FIN-WAIT-2 <-- <-- CLOSE-
(Close
4. TIME-WAIT <-- <-- LAST-
5. TIME-WAIT --> -->
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
5.1. TIME-WAIT <-- ... old
5.2 TIME-WAIT --> --> ????
5.3 CLOSED <-- <-- ????
(prematurely
Figure 1. TWA
Note that TWA is not at all an unlikely event if there are
duplicate segments that may be delayed in the network. Furthermore
TWA cannot be prevented by PAWS timestamps; the event may
within the same tick of the timestamp clock. TWA is a consequence
TCP's half-open connection discovery mechanism (see pp 33-34
[RFC-793]), which is designed to clean up after a system crash
2. The TWA
2.1
If the connection is immediately reopened after a TWA event,
new incarnation will be exposed to old duplicate segments (
for the initial segment, which is handled by the 3-
handshake). There are three possible hazards that result
H1. Old duplicate data may be accepted erroneously
H2. The new connection may be de-synchronized, with the two
in permanent disagreement on the state. Following the
of RFC-793, this desynchronization results in an infinite
Braden [Page 3]
RFC 1337 TCP TIME-WAIT Hazards May 1992
loop. (It might be reasonable to change this aspect of RFC
793 and kill the connection instead.)
This hazard results from acknowledging something that was
sent. This may result from an old duplicate ACK or as
side-effect of hazard H1.
H3. The new connection may die
A duplicate segment (data or ACK) arriving in SYN-SENT
may kill the new connection after it has apparently
successfully
Each of these hazards requires that the seqence space of the
connection overlap to some extent with the sequence space of
previous incarnation. As noted above, this is only possible
"fast" or "long" connections. Since these hazards all require
coincidence of an old duplicate falling into a particular range
new sequence numbers, they are much less probable than TWA itself
TWA and the three hazards H1, H2, and H3 have been demonstrated
a stock Sun OS 4.1.1 TCP running in an simulated environment
massively duplicates segments. This environment is far
hazardous than most real TCP's must cope with, and the
were carefully tuned to create the necessary conditions for
failures. However, these demonstrations are in effect
existence proof for the hazards
We now present example scenarios for each of these hazards.
scenario is assumed to follow immediately after a TWA
terminated the previous incarnation of the same connection
2.2 HAZARD H1: Acceptance of erroneous old duplicate data
Without the protection of the TIME-WAIT delay, it is possible
erroneous old duplicate data from the earlier incarnation to
accepted. Figure 2 shows precisely how this might happen
Braden [Page 4]
RFC 1337 TCP TIME-WAIT Hazards May 1992
TCP A TCP
1. ESTABL. --> --> ESTABL
2. ESTABL. <-- <-- ESTABL
3. (old dupl)... --> ESTABL
4. ESTABL. <-- <-- ESTABL
5. ESTABL. --> --> ESTABL
6. ... <-- ESTABL
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
7a. ESTABL. --> --> ESTABL
8a. ESTABL. <-- ...
9a. ESTABL. --> --> ESTABL
Figure 2: Accepting Erroneous
The connection has already been successfully reopened after
assumed TWA event. Segment 1 is a normal data segment and
2 is the corresponding ACK segment. Old duplicate data segment 3
from the earlier incarnation happens to fall within the
receive window, resulting in a duplicate ACK segment #4.
erroneous data is queued and "lurks" in the TCP reassembly
until data segment 5 overlaps it. At that point, either 80 or 40
bytes of erroneous data is delivered to the user B; the
depends upon the particulars of the reassembly algorithm,
may accept the first or the last duplicate data
As a result, B sends segment 6, an ACK for sequence = 640,
is 40 beyond any data sent by A. Assume for the present that
ACK arrives at A *after* A has sent segment 7a, the next full
segment. In that case, the ACK segment 8a acknowledges data
has been sent, and the error goes undetected. Another
continuation after segment 6 leads to hazard H3, shown below
2.3 HAZARD H2: De-synchronized
This hazard may result either as a side effect of H1 or
from an old duplicate ACK that happens to be acceptable
acknowledges something that has not been sent
Braden [Page 5]
RFC 1337 TCP TIME-WAIT Hazards May 1992
Referring to Figure 2 above, suppose that the ACK generated by
old duplicate data segment arrived before the next data
had been sent. The result is an infinite ACK loop, as shown
the following alternate continuation of Figure 2.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
7b. ESTABL. <-- ...
(ACK something not
sent => send ACK
8b. ESTABL. --> --> ESTABL
(Below window =>
send ACK
9b. ESTABL. <-- <-- ESTABL
(etc.!)
Figure 3: Infinite ACK
2.4 HAZARD H3: Connection
An old duplicate ACK segment may lead to an apparent refusal
TCP A's next connection attempt, as illustrated in Figure 4.
indicates the TCP window field SEG.WIND.*
TCP A TCP
1. CLOSED
2. SYN-SENT --> --> SYN-
3. ... <-- SYN-
4. SYN-SENT <-- ... (old duplicate
5. SYN-SENT --> -->
6. ESTABLISHED <-- ...
7. ESTABLISHED --> -->
8. CLOSED <-- <--
Figure 4: Connection Failure from Old
Braden [Page 6]
RFC 1337 TCP TIME-WAIT Hazards May 1992
The key to the failure in Figure 4 is that the RST segment 5
acceptable to TCP B in SYN-RECEIVED state, because the
space of the earlier connection that produced this old
overlaps the new connection space. Thus, in segment #5
falls within TCP B's receive window [101,900). In experiments
this failure mode was very easy to demonstrate. (Kurt Matthys
pointed out that this scenario is time-dependent: if TCP A
timeout and retransmit the initial SYN after segment 5 arrives
before segment 6, then the open will complete successfully.)
3. Fixes for TWA
We discuss three possible fixes to TCP to avoid these hazards
(F1) Ignore RST segments in TIME-WAIT state
If the 2 minute MSL is enforced, this fix avoids all
hazards
This is the simplest fix. One could also argue that it
formally the correct thing to do; since allowing time for
duplicate segments to die is one of TIME-WAIT state's functions
the state should not be truncated by a RST segment
(F2) Use PAWS to avoid the hazards
Suppose that the TCP ignores RST segments in TIME-WAIT state
but only long enough to guarantee that the timestamp clocks
both ends have ticked. Then the PAWS mechanism [RFC-1323]
prevent old duplicate data segments from interfering with
new incarnation, eliminating hazard H1. For reasons
below, however, it may not eliminate all old duplicate
segments, so hazards H2 and H3 will still exist
In the language of the TCP Extensions RFC [RFC-1323]:
When processing a RST bit in TIME-WAIT state
If (Snd.TS.OK is off) or (Time.in.TW.state() >= W
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
time since TIME-WAIT state was entered, and W is a constant
is at least twice the longest possible period for
clocks, i.e., W = 2 secs [RFC-1323].
Braden [Page 7]
RFC 1337 TCP TIME-WAIT Hazards May 1992
This assumes that the timestamp clock at each end continues
advance at a constant rate whether or not there are any
connections. We do not have to consider what happens across
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
on the SYN and {SYN,ACK} segments reopening the connection
be larger than any timestamp on a segment from
incarnations. As a result, the PAWS mechanism operating in
new connection incarnation will avoid the H1 hazard, ie
acceptance of old duplicate data
The effectiveness of fix (F2) in preventing acceptance of
duplicate data segments, i.e., hazard H1, has been
in the Sun OS TCP mentioned earlier. Unfortunately, these
revealed a somewhat surprising fact: old duplicate ACKs
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
duplicate ACK. That is, when an old duplicate arrives in TIME
WAIT state, an extended TCP will send out its own ACK with
timestamp option containing its CURRENT timestamp clock value
If this happens immediately before the TWA mechanism
TIME-WAIT state, the result will be a "new old duplicate
segment with a current timestamp that may pass the PAWS test
the reopened connection
Whether H2 and H3 are critical depends upon how often
happen and what assumptions the applications make about
semantics. In the case of the H3 hazard, merely trying the
again is likely to succeed. Furthermore, many production
have (despite the advice of the researchers who developed TCP
incorporated a "keep-alive" mechanism, which may
connections unnecessarily. The frequency of occurrence of H
and H3 may well be much lower than keep-alive failures
transient internet routing failures
(F3) Use 64-bit Sequence
O'Malley and Peterson [RFC-1264] have suggested expansion of
TCP sequence space to 64 bits as an alternative to PAWS
avoiding the hazard of wrapped sequence numbers within the
incarnation. It is worthwhile to inquire whether 64-
sequence numbers could be used to avoid the TWA hazards as well
Using 64 bit sequence numbers would not prevent TWA - the
termination of TIME-WAIT state. However, it appears that
Braden [Page 8]
RFC 1337 TCP TIME-WAIT Hazards May 1992
combination of 64-bit sequence numbers with an
modification of the TCP parameters could defeat all of the
hazards H1, H2, and H3. The basis for this is explained in
appendix to this memo. In summary, it could be arranged
the same sequence space would be reused only after a very
period of time, so every connection would be "slow" and "short".
4.
Of the three fixes described in the previous section, fix (F1),
ignoring RST segments in TIME-WAIT state, seems like the best short
term solution. It is certainly the simplest. It would be
desirable to do an extended test of this change in a
environment, to ensure there is no unexpected bad effect of
RSTs in TIME-WAIT state
Fix (F2) is more complex and is at best a partial fix. (F3),
64-bit sequence numbers, would be a significant change in
protocol, and its implications need to be thoroughly understood
(F3) may turn out to be a long-term fix for the hazards discussed
this note
APPENDIX: Using 64-bit Sequence
This appendix provides a justification of our statement that 64-
sequence numbers could prevent the TWA hazards
The theoretical ISN calculation used by TCP is
ISN = (R*T) mod 2**n
where T is the real time in seconds (from an arbitrary origin,
when the system is started), R is a constant, currently 250 KBps,
n = 32 is the size of the sequence number field
The limitations of current TCP are established by n, R, and
maximum segment lifetime MSL = 4 minutes. The shortest time Twrap
wrap the sequence space is
Twrap = (2**n)/
where r is the maximum transfer rate. To avoid old
segments in the same connection, we require that Twrap > MSL (
practice, we need Twrap >> MSL).
Braden [Page 9]
RFC 1337 TCP TIME-WAIT Hazards May 1992
The clock-driven ISN numbers wrap in time TwrapISN
TwrapISN = (2**n)/
For current TCP, TwrapISN = 4.55 hours
The cases for old duplicates from previous connections can be
into four regions along two dimensions
* Slow vs. fast connections, corresponding to r < R or r >= R
* Short vs. long connections, corresponding to duration E <
TwrapISN or E >= TwrapISN
On short slow connections, the clock-driven ISN selection rejects
duplicates. For all other cases, the TIME-WAIT delay of 2*MSL
required so old duplicates can expire before they infect a
incarnation. This is discussed in detail in the Appendix to [RFC
1185].
With this background, we can consider the effect of increasing n
64. We would like to increase both R and TwrapISN far enough
all connections will be short and slow, i.e., so that the clock
driven ISN selection will reject all old duplicates. Put
way, we want to every connection to have a unique chunk of
seqence space. For this purpose, we need R larger than the
foreseeable rate r, and TwrapISN greater than the longest
connection duration E
In fact, this appears feasible with n = 64 bits. Suppose that we
R = 2**33 Bps; this is approximately 8 gigabytes per second,
reasonable upper limit on throughput of a single TCP connection
Then TwrapISN = 68 years, a reasonable upper limit on TCP
duration. Note that this particular choice of R corresponds
incrementing the ISN by 2**32 every 0.5 seconds, as would happen
the Berkeley BSD implementation of TCP. Then the low-order 32
of a 64-bit ISN would always be exactly zero
[RFC-793] Postel, J., "Transmission Control Protocol", RFC-793,
USC/Information Sciences Institute, September 1981.
[RFC-1185] Jacobson, V., Braden, R., and Zhang, L., "
Extension for High-Speed Paths", RFC-1185, Lawrence Berkeley Labs
USC/Information Sciences Institute, and Xerox Palo Alto
Center, October 1990.
Braden [Page 10]
RFC 1337 TCP TIME-WAIT Hazards May 1992
[RFC-1263] O'Malley, S. and L. Peterson, "TCP
Considered Harmful", RFC-1263, University of Arizona,
1991.
[RFC-1323] Jacobson, V., Braden, R. and D. Borman "TCP
for High Performance", RFC-1323, Lawrence Berkeley Labs
USC/Information Sciences Institute, and Cray Research, May 1992.
Security
Security issues are not discussed in this memo
Author's Address
Bob
University of Southern
Information Sciences
4676 Admiralty
Marina del Rey, CA 90292
Phone: (213) 822-1511
EMail: Braden@ISI.
Braden [Page 11]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
