TCP Maintenance and Minor T. Moncaster
Extensions BT
Internet-Draft B. Briscoe
Intended status: Standards Track BT & UCL
Expires: August 24, 2007 A. Jacquet
BT
February 20, 2007
A TCP Test to Allow Senders to Identify Receiver Cheating
draft-moncaster-tcpm-rcv-cheat-00
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 August 24, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
The honesty of TCP senders and receivers has become a major concern
to the Internet community. Currently, TCP senders rely on receiver
honesty so they can correctly react to network congestion. Such
honesty cannot be taken for granted. Receivers may conceal dropped
packets to prevent their flow being subject to a congestion response
Moncaster, et al. Expires August 24, 2007 [Page 1]
Internet-Draft TCP Test Against Receiver Cheating February 2007
or may acknowledge data optimistically to get a higher bandwidth.
This document introduces a simple two-stage test of receiver honesty.
Once a receiver fails the first stage it can be subjected to the
second stage test that conclusively proves cheating. The performance
hit of the first stage is very slight compared to the second. So,
although the first stage is not decisive, it selects which receivers
are acting suspiciously enough to warrant the second stage. This
specification does not modify the TCP protocol - the tests only
require a change to sender implementations.
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.
Moncaster, et al. Expires August 24, 2007 [Page 2]
Internet-Draft TCP Test Against Receiver Cheating February 2007
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5
3. The Problems . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1. Concealing Lost Segments . . . . . . . . . . . . . . . . . 6
3.2. Optimistic Acknowledgements . . . . . . . . . . . . . . . 7
4. Requirements for a robust solution . . . . . . . . . . . . . . 9
5. Existing Proposals . . . . . . . . . . . . . . . . . . . . . . 10
5.1. Randomly Skipped Segments . . . . . . . . . . . . . . . . 10
5.2. The ECN nonce . . . . . . . . . . . . . . . . . . . . . . 10
5.3. A transport layer nonce . . . . . . . . . . . . . . . . . 11
6. The Test for Receiver Cheating . . . . . . . . . . . . . . . . 12
6.1. Solution Overview . . . . . . . . . . . . . . . . . . . . 12
6.2. Probabilistic Testing . . . . . . . . . . . . . . . . . . 12
6.2.1. Performing the Probabilistic Test . . . . . . . . . . 13
6.2.2. Assessing the Probabilistic Test . . . . . . . . . . . 15
6.2.3. RTT Measurement Considerations . . . . . . . . . . . . 15
6.2.4. Protocol Details for the Probabilistic Test . . . . . 17
6.3. Deterministic Testing . . . . . . . . . . . . . . . . . . 18
6.3.1. Performing the Deterministic Test . . . . . . . . . . 18
6.3.2. Assessing the Deterministic Test . . . . . . . . . . . 19
6.3.3. Protocol Details for the Deterministic Test . . . . . 19
6.4. Responding to Cheating . . . . . . . . . . . . . . . . . . 20
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
8. Security Considerations . . . . . . . . . . . . . . . . . . . 20
9. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 21
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 22
11. Comments Solicited . . . . . . . . . . . . . . . . . . . . . . 22
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22
12.1. Normative References . . . . . . . . . . . . . . . . . . . 22
12.2. Informative References . . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23
Intellectual Property and Copyright Statements . . . . . . . . . . 25
Moncaster, et al. Expires August 24, 2007 [Page 3]
Internet-Draft TCP Test Against Receiver Cheating February 2007
1. Introduction
This document specifies how a TCP sender implementation can be
modified to detect a cheating 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.
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 no-one can be trusted is extremely hard within the
current Internet architecture. This specification deals with one
specific case: where a TCP sender is well-behaved and wants to ensure
its receivers behave 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 hugely improve
its own download speed, without any need for the sender to be a
willing accomplice.
To be clear, the measures in this specification are intended for
senders that can be trusted to behave. Unless all senders are
trusted, this scheme alone cannot prevent other misbehaving senders
from causing congestion collapse of the Internet. But the more
trustworthy senders that deploy these measures, the less likely that
misbehaving receivers will be able to find senders that can be fooled
into causing congestion collapse.
However, 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 cheating receivers. A large
server relies 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
misbehaving receivers, it may well hit its own resource limits and
Moncaster, et al. Expires August 24, 2007 [Page 4]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 loss to test that the receiver
behaves as it should within the basic TCP protocol.
This document specifies a two-stage test in which the sender
deliberately re-orders some data segments so as to check if the
destination honestly 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. However,
failing it raises sufficient suspicion to warrant the more intrusive
but conclusive second stage. The second stage proves beyond doubt
whether the receiver is cheating but it also requires significant re-
ordering, which harms performance. Therefore it should not be used
unless a receiver is already strongly suspected of cheating (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
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].
Moncaster, et al. Expires August 24, 2007 [Page 5]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 assumption that
packets are most likely to be lost through deliberately being dropped
by a congested node rather than through transmission losses or
errors.
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 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
Moncaster, et al. Expires August 24, 2007 [Page 6]
Internet-Draft TCP Test Against Receiver Cheating February 2007
(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.
|---.__ 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
Moncaster, et al. Expires August 24, 2007 [Page 7]
Internet-Draft TCP Test Against Receiver Cheating February 2007
concealed during such an 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
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
Moncaster, et al. Expires August 24, 2007 [Page 8]
Internet-Draft TCP Test Against Receiver Cheating February 2007
to cause a denial of service. This highlights the potential severity
of such an attack were one to be launched.
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 honesty test MUST NOT adversely affect the existing
congestion control and avoidance algorithms since one of the
primary aims of any honesty 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 honesty 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 honesty. 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 dishonesty it identifies, it
SHOULD be certain of the receiver's dishonesty 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.
Moncaster, et al. Expires August 24, 2007 [Page 9]
Internet-Draft TCP Test Against Receiver Cheating February 2007
5. Existing Proposals
5.1. Randomly Skipped Segments
[Sherwood] suggests a simple approach to test a receiver's honesty.
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 [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 congestion marked then it loses
Moncaster, et al. Expires August 24, 2007 [Page 10]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 large 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
breaches requirement 4. On the face of it there is no obvious route
Moncaster, et al. Expires August 24, 2007 [Page 11]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 hurt
honest receivers thus breaching requirement 6. 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 are probably cheating. The
sender can then prove the dishonesty 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.
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
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.
Moncaster, et al. Expires August 24, 2007 [Page 12]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 honesty 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. Typically D might be less than 6. 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
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.
Moncaster, et al. Expires August 24, 2007 [Page 13]
Internet-Draft TCP Test Against Receiver Cheating February 2007
|--.._ |
|--.._`--.._ |
|--.._`--.._`--.._ | +----------------------------+
|--.._`--.._`--.._`--.._ | | 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
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.
Moncaster, et al. Expires August 24, 2007 [Page 14]
Internet-Draft TCP Test Against Receiver Cheating February 2007
6.2.2. Assessing the Probabilistic Test
This approach to testing receiver honesty 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
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
Moncaster, et al. Expires August 24, 2007 [Page 15]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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' | +----------------------------+
| |
Figure 4: Measuring the RTT during a test
Moncaster, et al. Expires August 24, 2007 [Page 16]
Internet-Draft TCP Test Against Receiver Cheating February 2007
6.2.4. Protocol Details for the Probabilistic Test
o Periodically and randomly, any heavily loaded TCP sender SHOULD
check the honesty of its receivers using the probabilistic test.
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.
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 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.
Therefore, the distribution of selections of D is likely to be
skewed towards lower values.
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.
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.
Moncaster, et al. Expires August 24, 2007 [Page 17]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 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
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].
Moncaster, et al. Expires August 24, 2007 [Page 18]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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
only written to document a test procedure to establish dishonesty,
not what the sender should or must do if the receiver fails the test.
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.
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 folloiwng the arrival of the first 3
dupliacte 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 dishonesty.
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.
Moncaster, et al. Expires August 24, 2007 [Page 19]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 Cheating
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
connections more rigorously.
7. IANA Considerations
This memo includes no request to IANA.
8. 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
Moncaster, et al. Expires August 24, 2007 [Page 20]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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.4.
[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
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.
9. 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 not cheating. 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 honesty of a receiver in a manner that both
encourages honest behaviour and proves dishonesty 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.
Moncaster, et al. Expires August 24, 2007 [Page 21]
Internet-Draft TCP Test Against Receiver Cheating February 2007
10. Acknowledgements
{ToDo:}
11. 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.
12. References
12.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.
12.2. Informative References
[Piratla] Piratla, N., Jayasumana, A., and T. Banka, "On Reorder
Density and its Application to Characterization of Packet
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",
Moncaster, et al. Expires August 24, 2007 [Page 22]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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
Bob Briscoe
BT & UCL
B54/77, Adastral Park
Martlesham Heath
Ipswich IP5 3RE
UK
Phone: +44 1473 645196
Email: bob.briscoe@bt.com
Moncaster, et al. Expires August 24, 2007 [Page 23]
Internet-Draft TCP Test Against Receiver Cheating February 2007
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 August 24, 2007 [Page 24]
Internet-Draft TCP Test Against Receiver Cheating February 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 August 24, 2007 [Page 25]