[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03

TCP Maintenance and Minor                                   T. Moncaster
Extensions                                                            BT
Internet-Draft                                                B. Briscoe
Intended status: Standards Track                                BT & UCL
Expires: December 7, 2007                                     A. Jacquet
                                                                      BT
                                                            June 5, 2007


    A TCP Test to Allow Senders to Identify Receiver Non-Compliance
                   draft-moncaster-tcpm-rcv-cheat-01

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on December 7, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   The TCP protocol relies on receivers sending accurate and timely
   feedback to the sender.  Currently the sender has no means to verify
   that a receiver is correctly sending this feedback according to the
   protocol.  A receiver that is non-compliant has the potential to
   disrupt a sender's resource allocation, increasing its transmission



Moncaster, et al.       Expires December 7, 2007                [Page 1]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   rate on that connection which in turn could adversely affect the
   network itself.  This document presents a two stage test process that
   can be used to identify whether a receiver is non-compliant.  The
   tests enshrine the principle that one shouldn't attribute to malice
   that which may be accidental.  The first stage test causes minimum
   impact to the receiver but raises a suspicion of non-compliance.  The
   second stage test can then be used to verify that the receiver is
   non-compliant.  This specification does not modify the core TCP
   protocol - the tests can either be implemented as a test suite or as
   a stand-alone test through a simple modification to the sender
   implementation.

Status

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.
   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.  Internet-Drafts are draft documents valid for a maximum of
   six months and may be updated, replaced, or obsoleted by other
   documents at any time.  It is inappropriate to use Internet-Drafts as
   reference material or to cite them other than as "work in progress."
   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.  The list of Internet-
   Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Changes from previous drafts (to be removed by the RFC Editor)

   From -00 to -01:

      Draft rewritten to emphasise testing for non-compliance.  Some
      changes to protocol to remove possible unwanted interactions with
      other TCP variants.  Sections added on comparison of solutions and
      alternative uses of test.













Moncaster, et al.       Expires December 7, 2007                [Page 2]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  5

   2.  Requirements notation  . . . . . . . . . . . . . . . . . . . .  7

   3.  The Problems . . . . . . . . . . . . . . . . . . . . . . . . .  7
     3.1.  Concealing Lost Segments . . . . . . . . . . . . . . . . .  7
     3.2.  Optimistic Acknowledgements  . . . . . . . . . . . . . . .  9

   4.  Requirements for a robust solution . . . . . . . . . . . . . . 11

   5.  Existing Proposals . . . . . . . . . . . . . . . . . . . . . . 12
     5.1.  Randomly Skipped Segments  . . . . . . . . . . . . . . . . 12
     5.2.  The ECN nonce  . . . . . . . . . . . . . . . . . . . . . . 12
     5.3.  A transport layer nonce  . . . . . . . . . . . . . . . . . 13

   6.  The Test for Receiver Cheating . . . . . . . . . . . . . . . . 14
     6.1.  Solution Overview  . . . . . . . . . . . . . . . . . . . . 14
     6.2.  Probabilistic Testing  . . . . . . . . . . . . . . . . . . 14
       6.2.1.  Performing the Probabilistic Test  . . . . . . . . . . 15
       6.2.2.  Assessing the Probabilistic Test . . . . . . . . . . . 17
       6.2.3.  RTT Measurement Considerations . . . . . . . . . . . . 17
       6.2.4.  Negative Impacts of the Test . . . . . . . . . . . . . 19
       6.2.5.  Protocol Details for the Probabilistic Test  . . . . . 19
     6.3.  Deterministic Testing  . . . . . . . . . . . . . . . . . . 21
       6.3.1.  Performing the Deterministic Test  . . . . . . . . . . 21
       6.3.2.  Assessing the Deterministic Test . . . . . . . . . . . 21
       6.3.3.  Protocol Details for the Deterministic Test  . . . . . 22
     6.4.  Responding to Non-Compliance . . . . . . . . . . . . . . . 22
     6.5.  Possible Interactions With Other TCP Features  . . . . . . 23
       6.5.1.  TCP Secure . . . . . . . . . . . . . . . . . . . . . . 23
       6.5.2.  Nagle Algorithm  . . . . . . . . . . . . . . . . . . . 23
       6.5.3.  Delayed Acknowledgements . . . . . . . . . . . . . . . 23
     6.6.  Possible Consequences of the Tests . . . . . . . . . . . . 23

   7.  Comparison of the Different Solutions  . . . . . . . . . . . . 24

   8.  Alternative Uses of the Test . . . . . . . . . . . . . . . . . 25

   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 26

   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 26

   11. Conclusions  . . . . . . . . . . . . . . . . . . . . . . . . . 27

   12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 28




Moncaster, et al.       Expires December 7, 2007                [Page 3]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   13. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 28

   14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28
     14.1. Normative References . . . . . . . . . . . . . . . . . . . 28
     14.2. Informative References . . . . . . . . . . . . . . . . . . 28

   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29
   Intellectual Property and Copyright Statements . . . . . . . . . . 31











































Moncaster, et al.       Expires December 7, 2007                [Page 4]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


1.  Introduction

   This document specifies how a TCP sender implementation can be
   modified to detect a non-compliant receiver.  It uses the standard
   wire protocol and protocol semantics of basic TCP [RFC0793] without
   modification.

   When any network resource (e.g. a link) becomes congested, the
   congestion control protocol [RFC2581] within TCP/IP relies on the
   voluntary compliance of all senders and all receivers that are using
   paths through the resource.  The protocol expects all receivers to
   correctly feed back congestion information and it expects each sender
   to respond by backing off its rate in response to this information.

   Over the past several years the Internet has become increasingly
   adversarial.  Self-interested or malicious parties may produce non-
   compliant protocol implementations if it is to their advantage, or to
   the disadvantage of their chosen victims.  To enforce congestion
   control when trust can not be taken for granted is extremely hard
   within the current Internet architecture.  This specification deals
   with one specific case: where a TCP sender is TCP compliant and wants
   to ensure its receivers are compliant as well.

   Simple attacks have been published showing that TCP receivers can
   manipulate feedback to fool TCP senders into massively exceeding the
   compliant rate [Savage].  Such receivers might want to make senders
   unwittingly launch a denial of service attack on other flows sharing
   part of the path between them [Sherwood].  But a more likely
   motivation is simple self-interest---a receiver can improve its own
   download speed, without any need for the sender to be a willing
   accomplice.  [Savage] quotes results that show this attack can reduce
   the time taken to download an HTTP file over a real network by half,
   even with a relatively cautious optimisitic acknowledgemnt strategy.

   There is currently no evidence that any TCP implementations are
   exploiting any of the attacks mentioned above.  However this may be
   simply a result of the fact that there is no widely available test to
   identify such attacks.  This document describes a test process that
   can identify such non-compliance by receivers should it start to
   become an issue.  The test can be deployed as a separate test suite,
   or in existing senders, but this document does not mandate that it
   should be implemented by senders.  The aim of the authors is to
   provide a test that is safe to implement and that can be recommended
   by the IETF.

   The measures in this specification are intended for senders that can
   be trusted to behave.  As all senders can not be trusted, this scheme
   can not prevent misbehaving senders from causing congestion collapse



Moncaster, et al.       Expires December 7, 2007                [Page 5]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   of the Internet.  However the very existence of a test scheme such as
   this should act as a disincentive against non-compliant receivers.

   Senders do not have to be motivated solely by "the common good" to
   deploy these changes.  It is directly in their own interest for
   senders serving multiple receivers (e.g. large file servers and
   certain file-sharing peers) to detect non-compliant receivers.  A
   large server relies in part on honest network congestion feedback to
   efficiently apportion its own resources between receivers.  If such a
   large server devotes an excessive fraction of its own resources to
   non-compliant receivers, it may well hit its own resource limits and
   have to starve other half-connections even if their network path has
   spare capacity.

   In order for a sender to test a receiver, we avoid requiring the
   receiver to have deployed any new or optional protocol features, as
   any misbehaving receiver could simply circumvent the test by claiming
   it did not support the optional feature.  Instead, the sender
   emulates network re-ordering then network loss to test that the
   receiver reacts as it should as defined within the basic TCP
   protocol.  It is important that the level of emulated re-ordering
   that such a test introduces should not adversely impact compliant
   receivers.

   This document specifies a two-stage test in which the sender
   deliberately re-orders some data segments so as to check if the
   destination correctly acknowledges out-of-order segments.  The first
   stage test introduces a small reordering which will have a related
   very minor performance hit.  It is not a conclusive test of
   compliance.  However, failing it strongly suggests the receiver is
   non-compliant.  This raises sufficient suspicion to warrant the more
   intrusive but conclusive second stage if this non-compliance is going
   to be sanctioned.  The second stage proves beyond doubt whether the
   receiver is non-compliant but it also requires significant re-
   ordering, which harms performance.  Therefore it should not be used
   unless a receiver is already strongly suspected of non-compliance
   (through failing the first stage).

   The technique is designed to work with all known variants of TCP,
   with or without ECN [RFC3168], with or without SACK [RFC2018], and so
   on.  The technique is probably transferable to derivatives of TCP,
   such as SCTP [RFC2960], but separate specifications will be required
   for such related transports.  The requirements for a robust solution
   in Section 4 serve as guidelines for these separate specifications.

   The document is structured as follows.  It begins with a detailed
   description of the problems outlined above.  It cites some published
   results that show how damaging these problems potentially are.  It



Moncaster, et al.       Expires December 7, 2007                [Page 6]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   sets out some simple requirements that have to be met by any robust
   solution.  It examines three existing proposed solutions in more
   detail, compares them against the list of requirements and
   demonstrates why they are not suitably robust.  It then details the
   proposed two-stage re-ordering test, directly utilising one of the
   solutions already proposed as its second stage and modifying it
   slightly for the first stage.


2.  Requirements notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].


3.  The Problems

   TCP is widely used as the end-to-end transport in the Internet.  In
   order to avoid the congestion collapses that plagued the Internet in
   the mid 1980's, TCP utilises a number of mechanisms to avoid
   congestion [RFC2581].  These mechanisms all rely on knowing that data
   has been received (through acknowledgments of that data) and knowing
   when congestion has happened (either through knowing that a segment
   was lost in flight or through being notified of an Explicit
   Congestion Notification (ECN) [RFC3168]).  TCP also uses a flow
   control mechanism to control the rate at which data is sent
   [RFC0813].  Both the flow control and congestion avoidance mechanisms
   utilise a transmission window that limits the number of
   unacknowledged segments that are allowed to be sent at any given
   time.  In order to work out the size of the transmission window, TCP
   monitors the average round trip time (RTT) for each flow and the
   number of unacknowledged segments still in flight.

   A strategising receiver can take advantage of the congestion and flow
   control mechanisms to increase its data throughput.  The three known
   ways in which it can do this are: optimistic acknowledgements,
   concealing segment losses and dividing acknowledgements into smaller
   parts.  The first two are examined in more detail below and details
   of the third can be found in [Savage].

3.1.  Concealing Lost Segments

   TCP is designed to view a lost segment as an indication of congestion
   on the channel.  This is because TCP makes the reasonable assumption
   that packets are most likely to be lost through deliberately being
   dropped by a congested node rather than through transmission losses
   or errors.



Moncaster, et al.       Expires December 7, 2007                [Page 7]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   In order to avoid congestion collapse [RFC3714], whichever TCP
   connection detects the congestion (through detecting that a packet
   has been dropped) is expected to respond to it either by reducing its
   congestion window to 1 segment after a timeout or by halving it on
   receipt of three duplicate acks (the precise rules are set out in
   [RFC2581]).

   For applications where missing data is not an issue, it is in the
   interest of a receiver to maximise the data rate it gets from the
   sender.  If it conceals lost segments by falsely generating
   acknowledgements for them it will not suffer a reduction in data
   rate.  There are a number of ways to make an application loss-
   insensitive.  Some applications such as streaming media are
   inherently insensitive anyway, as a loss will just be seen as a
   transient error.  TCP is widely used to transmit media files, either
   audio or video, which are relatively insensitive to data loss
   (depending on the encoding used).  Also senders may be serving data
   containing redundant parity to allow the application to recreate lost
   data.  A cheating receiver can also exploit application layer
   protocols such as the partial GET in HTTP 1.1 [RFC2616] to recover
   missing data over a secondary connection.






























Moncaster, et al.       Expires December 7, 2007                [Page 8]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


     |---.__    Drop            |     |---.__    Drop            |
     |---.__`---#200            |     |---.__`---#200            |
     |      `---.__             |     |      `---.__             |
     |             `---.__      |     |             `---.__      |
     |                  _,`300->|     |                  _,`300->|
     |           __,---'        |     |           __,---'        |
     |     _,---'               |     |     _,---'               |
     |<-100                     |     |<-300                     |
     |---.__                    |     |---.__                    |
     |---.__`---.__             |     |---.__`---.__             |
     |      `---.__`---.__      |     |---.__`---.__`---.__      |
     |             `---.__`400->|   ,-|---.__`---.__`---.__`400->|
     |                  _,`500->|   | |      `---.__`---._,`500->|
     |           __,---'        |   |R|           __~---.__`600->|
     |     _,---'               | - |T|     _,---'       _,`700->|
     |<-100                     | | |T|<-500      __,---'        |
     |---.__                    | | | |     _,---'               |
   ,-|---.__`---.__             | | `-|<-700                     |
   | |      `---.__`---.__      | |<-.
   | |             `---._,`600->| |   \
   |N|           __,---'_,`700->| -    +----------------------+
   |E|     _,---'__,---'        |      | receives segment 700 |
   |W|<-100_,---'               |      | much sooner          |
   | |<-100_                    |      +----------------------+
   |R|---.__`---.__             |
   |T|      `---.__`---.__      |
   |T|             `---._,`200->|
   | |           __,---'  `300->| <-- No ack as duplicate data
   | |     _,---'               |
   `-|<-700                     |

                    Figure 1: Concealing lost segments

3.2.  Optimistic Acknowledgements

   Optimistic acknowledgements were identified as a possible attack in
   [Savage].  If a receiver is downloading a file from a server, it is
   probably in its interest to acquire as high a bandwidth as possible
   for this.  One way of increasing the bandwidth is to encourage the
   sender to believe the round trip time is shorter than it actually is.
   This means the sender will open up its transmission window faster and
   thus will send data faster.  Of course any lost segments will also be
   concealed during this attack.

   The receiver can achieve this by sending acknowledgements for data it
   hasn't actually received yet.  As long as the acknowledgement is for
   a packet that has already been transmitted, the sender will assume
   the RTT has become shorter.  This will cause it to increase its



Moncaster, et al.       Expires December 7, 2007                [Page 9]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   transmission window more rapidly and thus send more data.  Optimistic
   acknowledgements are particularly damaging since they can also be
   used to significantly amplify the effect of a denial of service (DoS)
   attack on a network.  This form of attack is explained in more detail
   in [Sherwood].

     |---.__                    |     |---.__                    |
     |      `---.__             |     |      `---.__             |
     |             `---.__      |     |             `---.__      |
     |                  _,`100->|     |                  _,`100->|
     |           __,---'        |     |           __,---'        |
     |     _,---'               |     |     _,---'               |
     |<-100                     |     |<-100                     |
     |---.__                    |     |---.__                    |
   ,-|---.__`---.__             |   ,-|---.__`---.__             |
   | |      `---.__`---.__      |   |R|      `---.__`---.__      |
   |R|             `---.__`200->|   |T|             `---._,`200->|
   |T|                  _,`300->|   |T|           __,---'  `300->|
   |T|           __,---'        |   | |     _,---'               |
   | |     _,---'               |   `-|<-300                     |
   `-|<-300                     |     |---.__                    |
     |---.__                    |     |---.__`---.__             |
     |---.__`---.__             |     |---.__`---.__`---.__      |
     |---.__`---.__`---.__      |     |---.__`---.__`---._,`400->|
     |---.__`---.__`---.__`400->|     |      `---.__`---._,`500->|
     |      `---.__`---._,`500->|     |     _,---'__~---.__`600->|
     |           __~---.__`600->|     |<-500_,---'         `700->|
     |     _,---'       _,`700->|     |<-700                     |
     |<-500      __,---'        |
     |     _,---'               |
     |<-700                     |

   The flow on the left acknowledges data only once it is received.  The
   flow on the right acknowledges data before it is received and
   consequently the apparent RTT is reduced.

                   Figure 2: Optimistic acknowledgements

   In 2005 US-CERT (the United States Computer Emergency Readiness Team)
   issued a vulnerability notice [VU102014] specifically addressed to 80
   major network equipment manufacturers and vendors who could be
   affected if someone maliciously exploited optimistic acknowledgements
   to cause a denial of service.  This highlights the potential severity
   of such an attack were one to be launched.  It should be noted
   however that the primary motivation for using optimistic
   acknowledgement is likely to be the performance gain it gives rather
   than the possible negative impact on the network.  Application
   writers may well produce "Download Accelerators" that use optimistic



Moncaster, et al.       Expires December 7, 2007               [Page 10]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   acknowledgements to achieve the performance increase rather than the
   current parallel connection approach most use.  Users of such
   software would be effectively innocent parties to the potential harm
   that such a non-compliant TCP could cause.


4.  Requirements for a robust solution

   Since the above problems come about through the inherent behaviour of
   the TCP protocol, there is no gain in introducing a new protocol as
   misbehaving receivers can claim to only support the old protocol.
   The best approach is to provide a mechanism within the existing
   protocol to test whether a receiver is cheating.  The following
   requirements should be met by any such test in TCP and are likely to
   be applicable for similar tests in other transport protocols:

   1.  The compliance test must not adversely affect the existing
       congestion control and avoidance algorithms since one of the
       primary aims of any compliance test is to reinforce the integrity
       of congestion control.

   2.  Any test should utilise existing features of the TCP protocol.
       If it can be implemented without altering the existing protocol
       then implementation and deployment are easier.

   3.  The receiver should not play an active role in the process.  It
       is much more secure to have a check for compliance that only
       requires the receiver to behave as it should anyway.

   4.  It should not require the use of any negotiable TCP options.
       Since the use of such options is by definition optional, any
       misbehaving receiver could just choose not to use the appropriate
       option.

   5.  If this is a periodic test, the receiver must not be aware that
       it is being tested for compliance.  If the receiver can tell that
       it is being tested (by identifying the pattern of testing) it can
       choose to respond honestly only whilst it is being tested.  If
       the test is always performed this clearly doesn't apply.

   6.  If the sender actively sanctions any non-compliance it
       identifies, it should be certain of the receiver's non-compliance
       before taking action against it.  Any false positives might lead
       to inefficient use of network resources and could damage end-user
       confidence in the network.

   7.  The testing should not significantly reduce the performance of an
       innocent receiver.



Moncaster, et al.       Expires December 7, 2007               [Page 11]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


5.  Existing Proposals

5.1.  Randomly Skipped Segments

   [Sherwood] suggests a simple approach to test a receiver's
   compliance.  The test involves randomly dropping segments at the
   sender before they are transmitted.  All TCP "flavours" require that
   a receiver should generate duplicate acknowledgements for all
   subsequent segments until a missing segment is received.  This system
   requires that SACK be enabled so the sender can reliably tell that
   the duplicate acknowledgements are generated by the segment that is
   meant to be missing and are not concealing other congestion.  Once
   the first duplicate acknowledgement arrives, the missing segment can
   then be re-transmitted.  Because this loss has been deliberately
   introduced, the sender doesn't treat it as a sign of congestion.  If
   a receiver sends an acknowledgement for a segment that was sent after
   the gap, it proves it is behaving dishonestly and can thus be
   sanctioned.  As soon as the first duplicate acknowledgement is
   received the missing segment is re-transmitted.  This will introduce
   a 1 RTT delay for some segments which could adversely affect some
   low-latency applications.

   This scheme does work perfectly well in principle and does allow the
   sender to clearly identify dishonest behaviour.  However it fails to
   meet requirement 4 in Section 4 above since it requires SACK to be
   used.  If SACK were not used then it would fail to meet requirement 1
   as it would be impossible to differentiate between the loss
   introduced on purpose and any additional loss introduced by the
   network.

   It might be possible to incentivise the use of SACK by receivers by
   stating that senders are entitled to discriminate against receivers
   that don't support it.  Given that SACK is now widely implemented
   across the Internet this might be a feasible, but controversial,
   deployment strategy.  However the solution in Section 6 builds on
   Sherwood's scheme but avoids the need for SACK.

5.2.  The ECN nonce

   The authors of the ECN scheme [RFC3168] identified the failure to
   echo ECN marks as a potential attack on ECN.  The ECN nonce was
   proposed as a possible solution to this in experimental [RFC3540].
   It uses a 1 bit nonce in every IP header.  The nonce works by
   randomly setting the ECN field to ECN(0) or ECN(1).  It then
   maintains the least significant bit of the sum of this value and
   stores the expected sum for each segment boundary.  At the receiver
   end, the same 1-bit sum is calculated and is echoed back in the NS
   (nonce sum) flag added to the TCP header.  If a packet has been



Moncaster, et al.       Expires December 7, 2007               [Page 12]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   congestion marked then it loses the information of which ECT
   codepoint it was carrying.  A receiver wishing to conceal the ECN
   mark will have to guess whether to increment NS or not.  Once
   congestion has been echoed back and the source has started a
   congestion response the nonce sum in the TCP header is not checked.
   Once congestion recovery is over the source resets its NS to that of
   the destination and starts checking again.

   On the face of it this solution also fully covers the two problems
   identified in Section 3.  If a receiver conceals a lost segment it
   has to guess what mark was there and, over several guesses, is very
   likely to be found out.  If a receiver tries to use optimistic
   acknowledgements it has to guess what nonce was set on all the
   packets it acknowledges but hasn't received yet.  However there are
   some key weaknesses to this system.  Firstly, it assumes that ECN
   will be widely deployed (not currently true).  Secondly, it relies on
   the receiver honestly declaring support for both ECN and the ECN
   nonce - a strategising receiver can simply declare it is neither ECN
   nor ECN nonce capable and thus avoid the nonce.  Thirdly, the
   mechanism is suspended during any congestion response.  Comparing it
   against the requirements in Section 4 above, it is clear that the ECN
   nonce fails to meet requirements 3 and 4 and arguably fails to meet
   requirement 2 as [RFC3540] is experimental.  The authors do state
   that any sender that implements the ECN nonce is entitled to
   discriminate against any receiver that doesn't support it.  Given
   there are currently no implementations of the ECN nonce,
   discriminating against the overwhelming majority of receivers that
   don't support it is not a feasible deployment strategy.

5.3.  A transport layer nonce

   One possible solution to the above issues is a multi-bit transport
   layer nonce.  Two versions of this are proposed in [Savage].  The
   first is the so called "Singular Nonce" where each segment is
   assigned a unique random number.  This value is then echoed back to
   the receiver with the ack for that segment.  The second version is
   the "Cumulative Nonce" where the nonce is set as before, but the
   cumulative sum of all nonces is echoed back.  Whilst such a system is
   robust and allows a sender to correctly identify a misbehaving
   receiver, it has the key drawback that it requires either the
   creation of a new TCP option to carry the nonce and nonce reply or it
   requires the TCP header to be extended to include both these fields.

   This proposal clearly breaches several of the requirements listed in
   Section 4.  It breaches requirement 2 in that it needs a completely
   new TCP option or a change to the TCP header.  It breaches
   requirement 3 because it needs the receiver to actively echo the
   nonce (as does the ECN nonce scheme) and if it uses a TCP option it



Moncaster, et al.       Expires December 7, 2007               [Page 13]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   breaches requirement 4.  On the face of it there is no obvious route
   by which this sort of system can be widely implemented.


6.  The Test for Receiver Cheating

6.1.  Solution Overview

   The ideal solution to the above problems should fully meet the
   requirements set out in Section 4.  The most important of these is
   that the solution should leverage existing TCP behaviours rather than
   mandating new behaviours and options.  The proposed solution utilises
   TCP's receiver behaviour on detecting missing data.  To test a
   receiver the sender delays a segment during transmission by D
   segments.  There is a trade off because increasing D increases the
   probability of detecting cheating but also increases the probability
   of masking a congestion event during the test.  The completely safe
   strategy for the sender would be to reduce its rate pessimistically
   as if there were congestion during the test however this will impact
   the performance of honest receivers, thus breaching requirement 7.
   To overcome this dilemma, the test consists of two stages.  In the
   first stage, the sender uses small displacements without the
   pessimistic congestion response to determine which receivers appear
   to be non-compliant.  The sender can then prove the non-compliance of
   these receivers by subjecting them to a deterministic test.  This
   test uses a longer displacement but given the receiver is already
   under suspicion, it can risk harming performance by pessimistically
   reducing its rate as if the segment it held back was really lost by
   the network.  The tests can either be implemented as part of a test
   suite or as a stand-alone modification to the TCP sender
   implementation.  References to the TCP sender in the rest of the
   document should be taken to include either type of implementation.

6.2.  Probabilistic Testing

   The first requirement for a sender is to decide when to test a
   receiver.  This document doesn't specify when the test should be
   performed but the following guidance may be helpful.  The simplest
   option is for a sender to perform the test at frequent random
   intervals for all its half-connections.  There are also some
   heuristic triggers that might indicate the need for a test.  Firstly,
   if a sender is itself too busy, it would be sensible for it to test
   all its receivers.  Secondly, if the sender has many half-connections
   that are within a RTT of a congestion response, it would be sensible
   to test all the half-connections that aren't in a congestion
   response.  Thirdly, the sender could aim to test all its half-
   connections at least once.  Finally it is to be expected that there
   is a certain degree of existing segment reordering and thus a sender



Moncaster, et al.       Expires December 7, 2007               [Page 14]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   should be suspicious of any receiver that isn't generating as many
   duplicate acknowledgements as other receivers.  [Piratla] explores
   how prevalent reordering might be in the Internet though it is
   unclear whether the figures given are more widely applicable.

   The proposed solution depends, like the skipped segments solution, on
   the strict requirement that all TCP receivers have to send a
   duplicate acknowledgement as soon as they receive an out-of-order
   segment.  This acknowledges that some data has been received, however
   the acknowledgement is for the last in order segment that was
   received (hence duplicating an acknowledgment already made).  SACK
   extends this behaviour to allow the sender to infer exactly which
   segments are missing.  This leads to a simple statement: if a
   receiver is behaving honestly it must respond to an out-of-order
   packet by generating a duplicate acknowledgement.

   Following from the above statement, a sender can test the compliance
   of a given receiver by simply delaying transmission of a given
   segment by several places.  An honest receiver will respond to this
   by generating a number of duplicate acknowledgements.  The sender
   would strongly suspect a receiver of cheating if it received no
   duplicate acknowledgements as a result of the test.  A dishonest
   receiver can only conceal its actions by waiting until the delayed
   segment arrives and then generating an appropriate stream of
   duplicate acknowledgements to appear to be honest.

6.2.1.  Performing the Probabilistic Test

   The actual mechanism for conducting the test is extremely simple.
   Having decided to conduct a test the sender selects a segment, N. It
   then chooses a displacement, D (in segments) for this segment where
   strictly 2 < D < K - 2 where K is the current window size.  In
   practice only low values of D should be chosen to conceal the test
   among the background reordering and limit the chance of masking
   congestion.  D SHOULD be less than 6 for an initial test.  If K is
   less than 5, the sender can proceed straight to the deterministic
   test.  To conduct the probabilistic test, instead of transmitting
   segment N, it transmits N+1, N+2, etc. as shown in the figure below.
   Once it has transmitted N+D it can transmit segment N. The sender
   needs to record the sequence number, N as well as the displacement,
   D.

   According to data in [Piratla], as much as 15% of segments in the
   Internet arrive out of order though this claim may not be accurate.
   Whatever the actual degree of re-ordering, receivers always expect
   occasional losses of packets which they cannot distinguish from re-
   ordering without waiting for the re-ordered packet to arrive.
   Consequently a misbehaving receiver is unsure how to react to any



Moncaster, et al.       Expires December 7, 2007               [Page 15]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   out-of-order packets it receives.  It should be noted that the
   natural reordering may reduce the displacement deliberately
   introduced by the test so the sender should conduct the test more
   than once.

       |--.._                        |
       |--.._`--.._                  |
       |--.._`--.._`--.._            |   +----------------------------+
       |--.._`--.._`--.._`--.._      |   | This figure shows how an   |
       |--.._`--.._`--.._`--.._`N-1->|   | honest receiver reacts to  |
       |--.._`--.._`--.._`--.._`N+1->|   | a probabilistic test with  |
       |--.._`--.._`--.._`-=.._`N+2->|   | D=4. It sends 4 duplicate  |
       |     `--.._`-=.._`-=.._`N+3->|   | acknowledgements back to   |
       |      _,--'_-=.._`-=.._`N+4->|   | the sender before sending  |
       |<-N-1'_,--'__,--':-=.._`-N-->|   | an acknowledgement for N+4 |
       |<-N-1'_,--'__,--'__,--'`N+5->|   +----------------------------+
       |<-N-1'_,--'__,--'__,--'__,--'|
       |<-N-1'_,--'__,--'__,--'      |
       |<-N-1'_,--'__,--'            |
       |<-N+4'_,--'                  |
       |<-N+5'

      Figure 3: A receiver reacting honestly to a probabilistic test

   During testing, loss of segment L in the range from N+1 to N+D
   inclusive will be temporarily masked by the duplicate
   acknowledgements from the intentional gap that was introduced.  In
   this case the sender's congestion response will be delayed by at most
   the offset D. If there is an actual loss during the test then, once
   the receiver receives segment N, it will generate an acknowledgement
   for L-1.  This will lie between N and N+D. Thus it is reasonable to
   treat receipt of any acknowledgement between N and N+D inclusive as
   an indication of congestion and react accordingly.  This will also
   discourage the receiver from sending optimistic acknowledgements in
   case these prove to lie in the middle of a testing sequence, in which
   case it will trigger a congestion response by the sender.  It also
   means a dishonest receiver has to wait for a full K segments after
   any genuine lost segment to be sure it isn't a test as it will
   otherwise trigger a congestion response.  Delaying by that long will
   quickly increase the RTT estimate and will soon reduce the
   transmission rate by as much as if the receiver had reacted honestly
   to the congestion.

   As an additional safety measure, if the sender is performing slow
   start when it decides to test the receiver, it should change to
   congestion avoidance.  The reason for this is in case there is any
   congestion that is concealed during the test.  If there is
   congestion, and the sender's window is still increasing



Moncaster, et al.       Expires December 7, 2007               [Page 16]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   exponentially, this might significantly exacerbate the situation.
   This does mean that any receiver being tested during this period will
   suffer reduced throughput, but such testing should only be triggered
   by the sender being overloaded.

6.2.2.  Assessing the Probabilistic Test

   This approach to testing receiver compliance appears to meet all the
   requirements set out in Section 4.  The most attractive feature is
   that it enforces equivalence with honest behaviour.  That is to say,
   a receiver can either honestly report the missing packets or it can
   suffer a reduced throughput by delaying segments and increasing the
   RTT.  The only significant drawback is that during a test it
   introduces some delay to the reporting of actual congestion.  Given
   that TCP only reacts once to congestion in each RTT the delay doesn't
   significantly adversely affect the overall response to severe
   congestion.

   Some receivers may choose to behave dishonestly despite this.  These
   can be quickly identified by looking at their acknowledgements.  A
   receiver that never sends duplicate acknowledgements in response to
   being tested is likely to be misbehaving.  Equally, a receiver that
   delays transmission of the duplicate acknowledgements until it is
   sure it is being tested will leave an obvious pattern of
   acknowledgements that the sender can identify.  Because a receiver is
   unlikely to be able to differentiate this test from actual re-
   ordering events, the receiver will be forced to behave in the same
   fashion for any re-ordered packet even in the absence of a test,
   making it continually appear to have longer RTT.

6.2.3.  RTT Measurement Considerations

   Clearly, if the sender has re-ordered segment N, it cannot use it to
   take an accurate RTT measurement.  However it is desirable to ensure
   that, during a test, the sender still measures the RTT of the flow.
   One of the key aspects of this test is that the only way to cheat is
   for a dishonest receiver to delay sending acknowledgements until it
   is certain a test is happening.  If accurate RTTs can be measured
   during a test, this delay will cause a dishonest receiver to suffer
   an increase in RTT and thus a reduction in data throughput.  This
   will help act as a disincentive to cheating.

   Measurement of the RTT usually depends on receiving an
   acknowledgement for a segment and measuring the delay between when
   the segment was sent and when the acknowledgement arrives.  The TCP
   timestamp option is often used to provide accurate RTT measurement
   but again, this is not going to function correctly during a test
   phase.  During a test therefore, the RTT has to be estimated using



Moncaster, et al.       Expires December 7, 2007               [Page 17]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   the arrival of duplicate acknowledgements.  Figure 4 shows how one
   can measure the RTT in this way, and also demonstrates how this will
   increase if a dishonest sender chooses to cheat.  However it is not
   sufficient simply to measure a single RTT during the test.  A clever
   receiver might decide that the safe reaction to any missing segment
   is to immediately send one or two duplicate acknowledgements in order
   to disrupt this RTT measurement without running the risk of
   triggering a fast retransmit if the segment is genuinely missing.

       |`--._                      |
    ,--|`--._`--._                 |  +----------------------------+
   | C |`--._`--._`--._            |  | Segment N is delayed by 3  |
   | h |`--._`--._`--._`--._       |  | segments. This triggers 3  |
   | e |`--._`--._`--._`--._`-N-1->|  | duplicate acknowledgements |
   | c |     `--._`--._`--._`-N+1->|  +----------------------------+
   | k |          `--._`--._`=N+2->|
   |   |               `-=._`=N+3->|  +----------------------------+
   | R |           _,--'_,- `=-N=->|  | The RTT can be measured by |
   | T |      _,--'_,--'_,--'_,-' ,|  | timing the gap between N+1 |
   | T |<-N-1'_,--'_,--'_,--'_,--' |  | being sent and the 1st     |
    `--|<-N-1'_,--'_,--'_,--'      |  | duplicate acknowledgement  |
       |<-N-1'_,--'_,--'           |  | being received.            |
       |<-N-1'_,--'                |  +----------------------------+
       |<-N+3'                     |
       |                           |


       |`--._                      |
    ,--|`--._`--._                 |  +----------------------------+
   | R |`--._`--._`--._            |  | Segment N is delayed by 3  |
   | T |`--._`--._`--._`--._       |  | segments. The sender has   |
   | T |`--._`--._`--._`--._`-N-1->|  | decided to cheat so it has |
   |   |     `--._`--._`--._`-N+1->|  | to wait until it gets sent |
   | g |          `--._`--._`=N+2->|  | segment N.                 |
   | r |                `-=.`-N+3->|  +----------------------------+
   | e |           _,--'    `--N-->|
   | a |      _,--'               ,|  +----------------------------+
   | t |<-N-1'               _,--',|  | Once N arrives it has to   |
   | e |   |            _,--'_,--',|  | send a couple of duplicate |
   | r |  GAP      _,--'_,--'_,--',|  | acknowledgements so it     |
   |   |   |  _,--'_,--'_,--'      |  | appears to be honest. This |
    `--|<-N-1'_,--'_,--'           |  | will increase the RTT that |
       |<-N-1'_,--'                |  | the sender is measuring.   |
       |<-N+3'                     |  +----------------------------+
       |                           |






Moncaster, et al.       Expires December 7, 2007               [Page 18]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


                 Figure 4: Measuring the RTT during a test

6.2.4.  Negative Impacts of the Test

   It is important to be aware that keeping track of out-of-order data
   segments uses some memory resources at the receiver.  Clearly this
   test introduces additional re-ordering to the network and
   consequently will lead to receivers using additional resources.  In
   order to mitigate against this, any sender that implements the test
   should only conduct the test at relatively long intervals (of the
   order of several RTTs).

6.2.5.  Protocol Details for the Probabilistic Test

   o  Any TCP sender MAY check the compliance of its receivers using the
      probabilistic test periodically and randomly.  In particular, it
      would be advantageous for any sender that is heavily loaded to
      identify if it is being taken advantage of by a non-compliant
      receiver(s).

   o  The decision to test MUST be randomised and MAY be based on: the
      current load on the sender; whether the receiver is undergoing a
      congestion response; whether the receiver appears to have
      different flow characteristics to the others; when the receiver
      was last tested.  The interval between tests SHOULD be relatively
      long (order of several RTTs).

   o  To perform the test, the sender MUST select a segment N. The
      transmission of this segment MUST be delayed by D places.  D MUST
      lie between 2 and K-2 exclusively where K is the current size of
      the transmit window.  D SHOULD lie between 2 and 6 exclusively
      except in those circumstances when a receiver has failed to
      respond as expected to an earlier test but the sender chooses not
      to proceed to the deterministic test.  D MUST be generated pseudo-
      randomly and unpredictably.  The actual delay SHOULD be such that
      the receiver can't distinguish the test segment from the
      background traffic.  If there are less than D segments worth of
      data in the send buffer then the test should be aborted.

   o  If K < 5, the sender should move straight to the deterministic
      test Section 6.3.3.

   o  The sequence number N of the delayed segment MUST be recorded by
      the sender as must the amount of delay D.

   o  The senders enters the test phase when it transmits segment N+1
      instead of N.




Moncaster, et al.       Expires December 7, 2007               [Page 19]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   o  The sender MUST NOT use segment N to measure the RTT of the flow.
      This is because it won't get a true acknowledgement for this
      segment.

   o  The sender SHOULD use segment N+1 to measure the RTT using the
      first duplicate acknowledgement it receives to calculate the RTT.
      This is to ensure that a dishonest receiver will suffer from an
      increased RTT estimate.  The sender SHOULD continue checking the
      RTT throughout the test period.

   o  If the sender receives any duplicate acknowledgements during a
      testing phase it MUST check to see if they were generated by
      segment N (i.e. the acknowledged sequence number will be N-1).  If
      they are caused by segment N the sender SHOULD NOT react as if
      they are an indication of congestion.

   o  If the sender receives an acknowledgement for a segment with a
      sequence number between N and N+D inclusively it MUST treat this
      as an indication of congestion and react appropriately.

   o  A sender stops being in a test phase when either it receives the
      acknowledgement for segment N+D or when it has received at least D
      duplicate acknowledgments, whichever happens sooner.

   o  If a sender in a test phase receives D or more duplicate
      acknowledgements, then it MUST retransmit segment N and react as
      if there is congestion as specified in [RFC2581].  This is to
      allow for the possibility that segment N may be lost.

   o  If the sender is in the slow start phase it MUST move to
      congestion avoidance as soon as it begins a test.  It MAY choose
      to return to slow start once the test is completed.

   o  If a sender is in a test phase and receives no duplicate
      acknowledgements from the receiver it MUST treat this as
      suspicious and SHOULD perform the more rigorous deterministic test
      set out in Section 6.3.3.

   o  If a sender is in a test phase and the next segment to be
      transmitted has either the SYN or RST bits set, then it must
      immediately stop the test, and transmit segment N before
      transmitting the SYN or RST segment.

   o  A sender MAY choose to monitor the pattern of acknowledgements
      generated by a receiver.  A dishonest receiver is likely to send a
      distinctive pattern of duplicate acknowledgments during a test
      phase.  As they are unable to detect whether it is a test or not
      they are also forced to behave the same in the presence of any



Moncaster, et al.       Expires December 7, 2007               [Page 20]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


      segment reordering caused by the network.

6.3.  Deterministic Testing

   If after one or more probabilistic tests the sender deems that a
   receiver is acting suspiciously, the sender can perform a
   deterministic test similar to the skipped segment scheme in
   Section 5.1 above.

6.3.1.  Performing the Deterministic Test

   In order to perform the deterministic test the sender again needs to
   choose a segment, M to use for testing.  This time the sender holds
   back the segment until the receiver indicates that it is missing.
   Once the receiver sends a duplicate acknowledgement for segment M-1
   then the sender transmits segment M. In the meantime data
   transmission should proceed as usual.  If SACK is not in use, this
   test clearly increases the delay in reporting of genuine segment
   losses by up to a RTT.  This is because it is only once segment M
   reaches the receiver that it will be able to acknowledge the later
   loss.  Therefore, unless SACK is in use, the sender MUST
   pessimistically perform a congestion response following the arrival
   of 3 duplicate acknowledgements for segment M-1 as mandated in
   [RFC2581].

6.3.2.  Assessing the Deterministic Test

   A dishonest receiver that is concealing segment losses will establish
   that this isn't a probabilistic test once the missing segment fails
   to arrive within the space of 1 congestion window.  In order to
   conceal the loss the receiver will simply carry on acknowledging all
   subsequent data.  The sender can therefore state that if it receives
   an acknowledgement for a segment with a sequence number greater than
   M before it has actually sent segment M then the receiver must be
   cheating.  A sender would be expected to close a connection with any
   receiver that had failed the deterministic test, but this draft was
   not written to specify what a sender should or must do if a receiver
   fails the test, only how to establish such non-compliance.

   It is important to be aware that a third party who is able to
   correctly guess the initial sequence number of a connection might be
   able to masquerade as a receiver and send acknowledgements on their
   behalf to make them appear dishonest.  Such an attack can be
   identified because an honest receiver will also be generating a
   stream of duplicate acknowledgements until such time as it receives
   the missing segment.





Moncaster, et al.       Expires December 7, 2007               [Page 21]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


6.3.3.  Protocol Details for the Deterministic Test

   o  If a sender has reason to suspect that a receiver is reacting
      dishonestly to the probabilistic test it SHOULD perform the more
      thorough deterministic test.

   o  To perform the deterministic test the sender MUST select a segment
      M at random.  The sender MUST store this segment in the buffer of
      unacknowledged data without sending it and MUST record the
      sequence number.

   o  If SACK is not being used, the receiver must pessimistically
      perform a congestion response following the arrival of the first 3
      duplicate acknowledgments for segment M-1 as mandated in
      [RFC2581].

   o  If the receiver sends an acknowledgement for a segment that was
      sent after segment M should have been sent, but before segment M
      is actually sent, then the receiver has proved its non-compliance.
      The only possible exception to this is if the receiver is also
      sending a correct stream of duplicate acknowledgements as this
      implies that a third party is interfering with the connection.

   o  As soon as the first duplicate acknowledgement for segment M-1
      arrives, segment M MUST be transmitted.  The effective delay, D,
      of segment M MUST be calculated and stored.

   o  If a sender is in a test phase and the next segment to be
      transmitted has either the SYN or RST bits set, then it must
      immediately stop the test, and transmit segment N before
      transmitting the SYN or RST segment.

   o  Any subsequent acknowledgement for a segment between M and M+D
      MUST be treated as an indication of congestion and responded to
      appropriately as specified in [RFC2581].

6.4.  Responding to Non-Compliance

   Having identified that a receiver is actually being dishonest, the
   appropriate response is to terminate the connection with that
   receiver.  If a sender is under severe attack it might also choose to
   ignore all subsequent requests to connect by that receiver.  However
   this is a risky strategy as it might give an increased incentive to
   launch an attack against someone by making them appear to be behaving
   dishonestly.  It also is risky in the current network where many
   users might share a quite small bank of IP addresses assigned
   dynamically to them by their ISP's DHCP server.  A safer alternative
   to blacklisting a given IP address might be to simply test future



Moncaster, et al.       Expires December 7, 2007               [Page 22]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   connections more rigorously.

6.5.  Possible Interactions With Other TCP Features

   In order to be safe to deploy, this test must not cause any
   unforeseen interactions with other existing TCP features.  This
   section looks at some of the possible interactions that might happen
   and seeks to show that they are not harmful.

6.5.1.  TCP Secure

   [I-D.ietf-tcpm-tcpsecure] is a WG Internet Draft that provides a
   solution to some security issues around the injection of spoofed TCP
   packets into a TCP connection.  The mitigations to these attacks
   revolve round limiting the acceptable sequence numbers for RST and
   SYN segments.  In order to ensure there is no unforeseen interaction
   between TCP Secure and this test the test protocol has been specified
   such that a test will be aborted if a SYN or RST segment is sent.

6.5.2.  Nagle Algorithm

   The Nagle algorithm allows a TCP sender to have one small segment
   waiting to be acknowledged at a time.  This is designed for
   interactive applications where the data needs to be echoed back to
   the sender and is intended to reduce the number of small packets that
   are generated.  The protocol definition for the probabilistic test
   only allows the test to proceed if there are D or more segments
   waiting to be sent.  This should remove any possible adverse
   interactions with the Nagle algorithm.  However this assertion will
   need to be checked and the safe strategy may prove to be to ensure
   that partial segments are never delayed if Nagle is in operation or
   even to suspend testing altogether.

6.5.3.  Delayed Acknowledgements

   [RFC2581] allows for the generation of delayed acknowledgements for
   data segments.  However the tests in this document rely on triggering
   the generation of duplicate acknowledgements.  These must be
   generated for every out of order packet that is received and should
   be generated immediately the packet is received.  Consequently these
   mechanisms have no effect on the tests set out in this document.

6.6.  Possible Consequences of the Tests

   Earlier in this document we asserted that these tests don't change
   the TCP protocol.  We make this assertion for two reasons.  Firstly
   the protocol can be implemented as a shim that sits between the TCP
   and IP layers.  Secondly the network and receiver are unable to



Moncaster, et al.       Expires December 7, 2007               [Page 23]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   differentiate between a sender that implements these tests and a
   sender where the IP layer re-orders packets before transmission.
   However the tests might have some impact on the debugging of a TCP
   implementation.  It will also have an impact on debugging traces as
   it creates additional reordering.  The authors feel that these
   effects are sufficiently minor to be safely ignored.  If an author of
   a new TCP implementation wishes to be certain that they won't be
   affected by the tests during debugging they simply need to ensure
   that the sender they are connecting to is not undertaking the tests.

   A potentially more problematic consequence is the potential increase
   in packet reordering that this test might introduce.  However the
   degree of reordering introduced in the probabilistic test is strictly
   limited.  This should have minimal impact on the network as a whole
   although this assertion would benefit from testing by the wider
   Internet Community.


7.  Comparison of the Different Solutions

   The following table shows how all the approaches described in this
   document compare against the requirements set out in Section 4.





























Moncaster, et al.       Expires December 7, 2007               [Page 24]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


    +----------------+------+------+--------+---------+---------+
    |  Requirement   | Rand | ECN  |Transp. | Stage 1 | Stage 2 |
    |                | skip |nonce | nonce  |  test   |  test   |
    |                | segs |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    |   Congestion   |      |      |        |         |         |
    |    Control     | Yes  | Yes  |  Yes   |   Yes   |   Yes   |
    |   unaffected   |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    |    Utilise     |      |      |        |         |         |
    |    existing    | Yes  | No** |   No   |   Yes   |   Yes   |
    |    features    |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    |    Receiver    | Yes  |  No  |   No   |   Yes   |   Yes   |
    |  passive role  |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    | No negotiable  |Yes * |  No  |   No   |   Yes   |   Yes   |
    |  TCP options   |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    |    Receiver    | Yes  | N/A  |  N/A   |   Yes   |   Yes   |
    |    unaware     |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
    |   Certain of   | Yes  | Yes  |  Yes   | strong  |   Yes   |
    | non-compliance |      |      |        |suspicion|         |
    +----------------+------+------+--------+---------+---------+
    | Innocent rcvr. |      |      |        |         |         |
    | not adversely  |  No  | Yes  |  Yes   |   Yes   |   No    |
    |   affected     |      |      |        |         |         |
    +----------------+------+------+--------+---------+---------+
   *  Safer when SACK is used
   ** Currently Experimental RFC with no known available implementation

   Table 1 Comparing different solutions against the requirements

   The table highlights that the three existing schemes looked at in
   detail in Section 5 all fail on at least two of these requirements.
   Whilst this doesn't necessarily make them bad solutions it does mean
   that they are harder to implement than the new tests presented in
   this document.


8.  Alternative Uses of the Test

   Thus far, the two stage test process described in this document has
   been examined in terms of being a test for compliance by a receiver
   to the TCP protocol, specifically in terms of the protocol's reaction
   to segment reordering.  The probabilistic test however could also be
   used for other test purposes.  For instance the test can be used to



Moncaster, et al.       Expires December 7, 2007               [Page 25]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   confirm that a receiver has correctly implemented TCP SACK.  Because
   the sender knows exactly which segments have been reordered, it can
   confirm that the gaps in the data as reported by SACK are indeed
   correct.  The test could also be incorporated as part of a test suite
   to test the overall compliance of new TCP implementations.


9.  IANA Considerations

   This memo includes no request to IANA.


10.  Security Considerations

   The two tests described in this document provide a solution to two of
   the significant security problems that were outlined in [Savage].
   Both these attacks could potentially cause major congestion of
   senders own resources (by making them transmit at too high a rate)
   and could lead to network congestion collapse through subverting the
   correct reporting of congestion or by amplifying any DoS attack
   [Sherwood].  The proposed solution cannot alone prevent misbehaving
   senders from causing congestion collapse of the Internet.  However,
   the more widely it is deployed by trustworthy senders, the more these
   particular attacks would be mitigated through ensuring accurate
   reporting of segment losses.  The more senders that deploy these
   measures, the less likely it is that a misbehaving receiver will be
   able to find a sender to fool into causing congestion collapse.

   It should be noted that if a third party is able to correctly guess
   the initial sequence number of a connection, they might be able to
   masquerade as a receiver and send acknowledgements on their behalf to
   make them appear dishonest during a deterministic test.

   Due to the wording of [RFC2581] a receiver wishing to establish
   whether a probabilistic test is happening can keep their
   acknowledgement clock running (thus maintaining transmission rate) by
   generating pairs of duplicate acknowledgements for segments it
   received prior to the gap in the data stream caused by the test.
   This would allow a receiver to subsequently send any additional
   duplicate acknowledgements that would be necessary to make it appear
   honest.  Such behaviour by a receiver would be readily apparent by
   examining the pattern of the acknowledgements.  Should receivers
   prove able to exploit this to their advantage, there might be a need
   to change some of the musts and shoulds laid out in Section 6.2.5.

   [Savage] also identified a further attack involving splitting
   acknowledgements into smaller parts.  TCP is designed such that
   increases in the congestion window are driven by the arrival of a



Moncaster, et al.       Expires December 7, 2007               [Page 26]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   valid acknowledgement.  It doesn't matter if this acknowledgement
   covers all of a transmitted segment or not.  This means a receiver
   that divides all its acknowledgements into two will cause the
   congestion window to open at twice the rate it would do otherwise.
   The tests described above can't protect against that attack.  However
   there is a straightforward solution to this - every time the sender
   transmits a new segment it increments a counter; every acknowledgment
   it receives decrements that counter; if the counter reaches zero, the
   sender won't increase its congestion window in response to a new
   acknowledgement arriving.  To comply with this document, senders MUST
   implement a solution to this problem.


11.  Conclusions

   The issue of mutual trust between TCP senders and receivers is a
   significant one in the current Internet.  This document has
   introduced a mechanism by which honest senders can verify that their
   receivers are compliant with the current TCP protocol.  The whole
   process is robust, lightweight, elegant and efficient.  The
   probabilistic test might delay a congestion notification by a
   fraction of a RTT, however this is compensated for by the protocol
   reacting more rapidly to any such indication.  The deterministic test
   carries a greater risk of delaying congestion notification and
   consequently the protocol mandates that a congestion response should
   happen whilst performing the test.  The two tests combine to provide
   a mechanism to allow the sender to judge the compliance of a receiver
   in a manner that both encourages compliant behaviour and proves non-
   compliance in a robust manner.  The most attractive feature of this
   scheme is that it requires no active participation by the receiver as
   it utilises the standard behaviour of TCP in the presence of missing
   data.  The only changes required are at the sender.

   As mentioned in the introduction, the tests described in this
   document aren't intended to become a necessary feature for compliant
   TCP stacks.  Rather, the intention is to provide a safe testing
   mechanism that a sender could choose to implement were it to decide
   there is a need.  If optimistic acknowledgements do start to become
   widely exploited the authors of this draft feel it would be valuable
   to have an IETF-approved test that can be used to identify non-
   compliant receivers.  In the mean-time these tests can be used for a
   number of alternative purposes such as testing that a new receiver
   stack is indeed compliant with the protocol and testing if a receiver
   has correctly implemented SACK.

   In the longer term it would be hoped that the TCP protocol could be
   modified to make it robust against such non-compliant behaviour,
   possibly through the incorporation of a cumulative transport layer



Moncaster, et al.       Expires December 7, 2007               [Page 27]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   nonce as described in Section 5.3.


12.  Acknowledgements

   The authors would like to acknowledge the assistance and comments
   they received from contributors to the TCPM mailing list.  In
   particular we would like to thank Mark Allman, Caitlin Bestler, Lars
   Eggert, Gorry Fairhurst, John Heffner, David Mallone, Gavin
   McCullagh, Anantha Ramaiah, Rob sherwood, Joe Touch and Michael
   Welzl.


13.  Comments Solicited

   Comments and questions are encouraged and very welcome.  They can be
   addressed to the IETF TCP Maintenance and Minor Extensions working
   group mailing list <tcpm@ietf.org>, and/or to the authors.


14.  References

14.1.  Normative References

   [RFC0793]  Postel, J., "Transmission Control Protocol", STD 7,
              RFC 793, September 1981.

   [RFC0813]  Clark, D., "Window and Acknowledgement Strategy in TCP",
              RFC 813, July 1982.

   [RFC2018]  Mathis, M., Mahdavi, J., Floyd, S., and A. Romanow, "TCP
              Selective Acknowledgment Options", RFC 2018, October 1996.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2581]  Allman, M., Paxson, V., and W. Stevens, "TCP Congestion
              Control", RFC 2581, April 1999.

14.2.  Informative References

   [I-D.ietf-tcpm-tcpsecure]
              Ramaiah, A., "Improving TCP's Robustness to Blind In-
              Window Attacks", draft-ietf-tcpm-tcpsecure-07 (work in
              progress), February 2007.

   [Piratla]  Piratla, N., Jayasumana, A., and T. Banka, "On Reorder
              Density and its Application to Characterization of Packet



Moncaster, et al.       Expires December 7, 2007               [Page 28]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


              Reordering", 2005.

   [RFC2616]  Fielding, R., Gettys, J., Mogul, J., Frystyk, H.,
              Masinter, L., Leach, P., and T. Berners-Lee, "Hypertext
              Transfer Protocol -- HTTP/1.1", RFC 2616, June 1999.

   [RFC2960]  Stewart, R., Xie, Q., Morneault, K., Sharp, C.,
              Schwarzbauer, H., Taylor, T., Rytina, I., Kalla, M.,
              Zhang, L., and V. Paxson, "Stream Control Transmission
              Protocol", RFC 2960, October 2000.

   [RFC3168]  Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
              of Explicit Congestion Notification (ECN) to IP",
              RFC 3168, September 2001.

   [RFC3540]  Spring, N., Wetherall, D., and D. Ely, "Robust Explicit
              Congestion Notification (ECN) Signaling with Nonces",
              RFC 3540, June 2003.

   [RFC3714]  Floyd, S. and J. Kempf, "IAB Concerns Regarding Congestion
              Control for Voice Traffic in the Internet", RFC 3714,
              March 2004.

   [Savage]   Savage, S., Wetherall, D., and T. Anderson, "TCP
              Congestion Control with a Misbehaving Receiver", 1999.

   [Sherwood]
              Sherwood, R., Bhattacharjee, B., and R. Braud,
              "Misbehaving TCP Receivers Can Cause Internet-Wide
              Congestion Collapse", 2005.

   [VU102014]
              Doherty, "Optimistic TCP Acknowledgements Can Cause Denial
              of Service".


Authors' Addresses

   Toby Moncaster
   BT
   B54/70, Adastral Park
   Martlesham Heath
   Ipswich  IP5 3RE
   UK

   Phone: +44 1473 648734
   Email: toby.moncaster@bt.com




Moncaster, et al.       Expires December 7, 2007               [Page 29]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


   Bob Briscoe
   BT & UCL
   B54/77, Adastral Park
   Martlesham Heath
   Ipswich  IP5 3RE
   UK

   Phone: +44 1473 645196
   Email: bob.briscoe@bt.com


   Arnaud Jacquet
   BT
   B54/70, Adastral Park
   Martlesham Heath
   Ipswich  IP5 3RE
   UK

   Phone: +44 1473 647284
   Email: arnaud.jacquet@bt.com































Moncaster, et al.       Expires December 7, 2007               [Page 30]


Internet-Draft     TCP Test Against Receiver Cheating          June 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgments

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).  This document was produced
   using xml2rfc v1.32 (of http://xml.resource.org/) from a source in
   RFC-2629 XML format.



Moncaster, et al.       Expires December 7, 2007               [Page 31]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/