Subject: [tcpm] thoughts on draft-moncaster-tcpm-rcv-cheat-00

From: Mark Allman <[email-masked]>
Date: Tue, 20 Mar 2007 15:48:23 -0400

Folks-

I have a few thoughts on draft-moncaster-tcpm-rcv-cheat-00.  These are
said without my co-chair hat.  They are my own thoughts and nobody else
would want them no doubt.

(1) On Threats.

    The draft says that as opposed to Sherwood's work that posits that
    (0wned) receiver's will optimistically ACK to hose the network, "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."  This latter is also the
    underlying theme of Savage's work.  I don't think I buy this
    self-interest motivation for optimistic ACKing.

    (As a matter of fact I don't exactly buy Sherwood's motivation
    either.  But, I buy it **a ton** more than the self interest
    motivation.)

    The problem here is that if optimistic ACKing goes wrong it hoses an
    application that is trying to be self-interested.  If a TCP
    connection ACKs a packet that has been actually lost then recovering
    is not easy.  Certainly, we can use HTTP range requests and FTP
    restarts and such application mechanisms to start again.  But, at
    that point it seems to me at best a crapshoot whether you're going
    to end up with better performance than simply playing by the rules.
    Bottom line here is that it is a gamble to optimistically ACK to
    gain performance if you care about the data, IMO.

    [[ Note: Savage had two other items that I could see being used for
       self interest: sending tons of dupacks and dividing ACKs.  These
       do not have near the downside of ACKing something that has been
       lost and so there may be incentive to actually use these things.
       On the other hand, there are straightforward mitigations to
       these, as well.  (See RFC3465, RFC2581 and the 2581bis I-D.) ]]

    In section 3.1 of the draft there is a discussion that says if the
    application can tolerate missing data then the above argument that
    it is hard to recover doesn't apply because we can just move on
    without the data.  Um.  Yeah, but .... Err, TCP provides a
    *reliable* byte stream.  How would one actually hook up arbitrary
    apps to this model?  Do we really think that Microsoft is going to
    include a setsockopt called ABUSE_THE_SENDER and then change all the
    APIs such that out of order data can be passed up (with some notion
    of where it belongs in the stream) when the app wants to goose the
    sender?  Or, do we think applications are going to start writing
    their own TCPs that read and write raw packets to get around the
    pesky OS notions of how things ought to work?

    Maybe I am just blinded by laziness here, but I don't understand
    this point *at all*.  I understand how optimistic ACKs might be used
    to abuse the network--because nobody cares about the data.  But, I
    cannot conjure the intuition about how lost segments in a reliable
    protocol can be masked in the name of self interest.

(2) Who Do We Trust?

    In some sense this all comes down to whether we want to continue to
    trust receivers.  We certainly trust senders to do the right thing.
    The network should probably do something about this state of
    affairs.  But, wouldn't that also help with the problem of receivers
    coaxing the sender to transmit faster than appropriate?  Fate
    sharing and all.  If we trust the senders then why not trust the
    receivers are likely to be doing the right thing?  How paranoid do
    we want to be for what sort of benefit?
    
    This is my main question... I would argue that up until this point
    we have seen no big problems with the current trust model.  So, what
    is the benefit of deciding we no longer generally trust receivers
    (for congestion control purposes) and what is the cost?

(3) New Options.

    It seems odd to me that in some places in the document the authors
    admit that a cooperative option could be incentivized and in others
    they ignore this.  I.e., a general transport nonce could be required
    by the sender to send quite fast.  So, a receiver cannot just ignore
    it and expect good service.  Seems reasonable to me.  (Exact policy
    and how to phase this in seems like a detail.)

(4) Reordering.

    A number of people have measured reordering.  Paxson, Partridge,
    Savage, etc.  It is probably worth it to check into more than just
    [Piratla].  My general feeling from these works is that the
    probability that an arbitrary packet will be reordered is very
    slight.  However, on some paths reordering is quite heavy.  I think
    it is sort of dubious to suggest that just because a sender sees no
    reordering reported that this should be suspicious.

(5) RTTs.

    It is not clear to me why we need to assess the RTT during the test
    period.  Just leave things alone and it'll be fine.  What am I
    missing here?

(6) Sherwood Redux.

    It seems to me that this whole solution is really the same as
    Rob's.  You guys have chosen different parameters for the same
    process.  And, you have broken it into two pieces to try to mitigate
    the negative impacts.  But, fundamentally these things are pretty
    much the same, I think.

(7) An Alternate Scheme.

    There is another scheme that has been floated that you did not
    mention.  In "DoS vulnerability of TCP by acknowledging not received
    segments" (draft-azcorra-tcpm-tcp-blind-ack-dos-01.txt; expired, but
    I am sure you can all find it) the authors propose essentially using
    the sequence space for a singular nonce.  That is, vary the packet
    size a bit (randomly) and watching for ACKs that do not land on the
    right segment boundaries.  At the very least this should be
    mentioned.

    (This was presented to the TCPM WG a while back (and, TSVWG too, I
    think).  It gained no traction.

My main question is (2).  The rest of this is really minor stuff.
(Although, if one wanted to seriously look at the solution space I think
(7) is pretty important.)

allman

_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Joe Touch <[email-masked]>
Date: Wed, 21 Mar 2007 01:41:18 -0700

> would want them no doubt.

I had a few at the meeting as well as a few new ideas; here's a capture
of them on-list (they're mostly clarification or suggestion), as well as
comments on Mark's:

- Nagle
	I wonder whether the algorithm should prohibit stalling
	partial segments when Nagle is enabled, to avoid unintended
	interactions with Nagle.

- tcp-secure
	It would be useful to address interactions with tcp-secure,
	esp whether delaying segments could affect a correctly-behaving
	receiver RST-ing a connection.

- malicious vs. unexpected (not noted at the meeting)
	Receivers MUST ack at least once every two received segments,
	but can ack every one. There's a bit of play in there - a
	correctly-behaving receiver could ACK every segment. Nothing
	in the 1-2 range should be considered an error - including
	changes during a connection. It might be useful to indicate
	this as "odd" or "unexpected", but not "bad" per se; some
	choices could be considered "unfortunate" even if not
	malicious (ACK every 1.5 segments).

>     we want to be for what sort of benefit?

FWIW, I didn't see this as being paranoid, but as a test system. You
decide whether the behavior is malicious separate from whether it's
in-spec, in-spec but ill-advised, or out-of-spec.

Malicious is intent; let's leave that out.

>     right segment boundaries.  At the very least this should be

ACKs that don't land on segment boundaries could be hard to figure out,
esp. with Nagle on. And receivers need not ACK every byte received; some
optimized implementations (variants of RDDP) try to resynch boundaries
at the segment layer to provide inferred alignment to data boundaries.

The point is that not ACKing on a boundary isn't malicious, but it can
be reported as "odd" or "unexpected".

Joe

---

From: Mark Allman <[email-masked]>
Date: Wed, 21 Mar 2007 08:41:29 -0400

Joe-

> > (2) Who Do We Trust?
> > 
> >     In some sense this all comes down to whether we want to continue
> >     to trust receivers.  We certainly trust senders to do the right
> >     thing.  The network should probably do something about this
> >     state of affairs.  But, wouldn't that also help with the problem
> >     of receivers coaxing the sender to transmit faster than
> >     appropriate?  Fate sharing and all.  If we trust the senders
> >     then why not trust the receivers are likely to be doing the
> >     right thing?  How paranoid do we want to be for what sort of
> >     benefit?
> 

OK, well then make the case that I should care without worrying about
the intent.

How do we improve the state of the world by figuring out if the receiver
is in or out of spec with regards to ACKing data that has not arrived.
If this is a simple implementation mistake that causes a receiver to ACK
data that has not arrived then it seems pretty clear that it'll be found
and fixed pretty readily because things just won't work.  Do we want to
add something to every implementation to test for such a bug?  Or, for a
bazillion other possible bugs?

This work is advertised as for combating malicious receivers who are not
in-spec in an attempt to either (1) gain an advantage for themselves or
(2) to coax the sender to transmit at an inappropriate rate to hose the
network.  In that context, I think the question of how well we should
trust the receivers is well within bounds.  If you have another
important and practical reason that we should be doing such a test that
does not involve maliciousness then I'd love to hear it.  If you have
one I'd then be more inclined to agree with your much broader notion
that we need not worry about intent.

> ACKs that don't land on segment boundaries could be hard to figure
> out, esp. with Nagle on. And receivers need not ACK every byte
> received; some optimized implementations (variants of RDDP) try to
> resynch boundaries at the segment layer to provide inferred alignment
> to data boundaries.
> 

Just to be clear.... I was not advocating this scheme and if my words
above come off that way, I screwed up.  I was noting that someone wrote
down a scheme to combat this optimistic ACKing business that
draft-moncaster-tcpm-rcv-cheat-00 did not consider as related work.
You and I often don't see eye-to-eye, but surely we agree that related
work should be discussed as such.

(And, in fact, we also agree that randomizing the segment boundaries for
finding optimistic ACKers can be problematic.  I.e., I agree with the
technical points above.)

allman

---

From: Joe Touch <[email-masked]>
Date: Wed, 21 Mar 2007 06:36:14 -0700

> OK, well then make the case that I should care without worrying about

It might be useful for test purposes. After re-reading the doc, I still
don't presume that it requires that all TCPs deploy this. I'd prefer if
it were more explicit, but my read was that it was intended as a way to
test - when testing is what you want to do.

Testing could be added to an operational TCP, or could be just part of a
test TCP. The former might be running to do ongoing monitoring, to alert
a human to look into possible anomalies. The latter would be just for
test purposes.

Now, as to whether all TCPs -should- do this test, I'll point out the
irony in thinking this is incorrect when TCP-secure is. My point there
was that such errors aren't attacks per se (just as here), and that
these sorts of tests are useful to monitor things and escalate, but not
as a required part of any implementation. I agree with you that TCP
assumes that endpoints behave generally well, and that the only things
it MUST (or even SHOULD, IMO) include are those REQUIRED for correct
operation.

Security and detecting malicious endpoints is not required, and must be
optional.

> bazillion other possible bugs?

Definitely not. I like this as a test suite, but not as a requirement.

> that we need not worry about intent.

I think we're agreeing; I agree this shouldn't be part of regular
operations, but still think the tests described could be useful for
informational purposes only.

> work should be discussed as such.

Oh - I agree about the related work stuff...

> finding optimistic ACKers can be problematic.  I.e., I agree with the

Right, then we agree on both points.

Here are some others:

MUST/SHOULD/MAY - these are not appropriate in the requirements section;
they usually refer to a protocol solution, not a requirement, IMO.
i.e., it's ON in sections 6.2.4 and 6.3.3, but not in section 4

JOe

---

From: Mark Allman <[email-masked]>
Date: Wed, 21 Mar 2007 10:07:18 -0400

> test - when testing is what you want to do.

My read was much much different.  My read of this document is that they
are proposing a technique that normal everyday TCP senders should use to
detect receivers that are attempting to fool the senders into
transmitting faster than normal CC would allow.

> informational purposes only.

OK.  If someone wrote an i-d that said this was a testing technique only
and not meant for general use then I'd respond to that i-d differently,
I bet.  I am responding to what I believe this document is proposing
... and, that is a technique to vet receivers on-the-fly during normal
operations to combat maliciousness.

allman

---

From: Joe Touch <[email-masked]>
Date: Wed, 21 Mar 2007 07:18:08 -0700

Mark Allman wrote:
...
> operations to combat maliciousness.

I'll propose that this could be a change/clarification to the current
document. Thoughts from others on the list?

Joe

---

From: "Caitlin Bestler" <[email-masked]>
Date: Wed, 21 Mar 2007 09:22:50 -0700

Joe Touch wrote:
> Mark Allman wrote:
> ...
>> OK.  If someone wrote an i-d that said this was a testing technique
>> only and not meant for general use then I'd respond to that i-d
>> differently, I bet.  I am responding to what I believe this document
>> is proposing ... and, that is a technique to vet receivers on-the-fly
>> during normal operations to combat maliciousness.
> 
> I'll propose that this could be a change/clarification to the
> current document. Thoughts from others on the list?
> 
> Joe

I fully agree with Mark's sentiments on this. The techniques
proposed are not suitable for default deployment, especially
not with anything even approach a SHOULD.

In fact I would say that the test SHOULD NOT be used by anyone
who has not considered it's potential adverse impacts. 

The most important adverse impact is that any receiver has a
finite capability for tracking gaps in the TCP sequence. Every
gap that it tracks requires some resources. Not much, but it
doesn't have to be when this is a per connection cost.

There has already been an calculation made as to the optimal
amount of resources to have available to minimize resource
allocations while minimizing the risk of having to drop a 
packet due to lack of resources to track one more gap.
Since the receiver has no way of knowing which of its
connections will be tested, it must make these extra
resources available to all connections. If the specific
receiver pre-allocates resources to each established
connection then this could be a problem.

The proposed test eats at that safety margins and/or
requires that more safety margin be allocated. Neither
should be forced onto receivers because some servers
are incapable of protecting themselve with simple
application layer defenses (like not transmitting
more than X to an anonymous client).

Doing the proposed test as part of network monitoring
and/or diagnostics is completely reasonable. As is
injecting noise to test network robustness. But neither
is something that should be done routinely by a production
stack.

---

From: Rob Sherwood <[email-masked]>
Date: Wed, 21 Mar 2007 12:51:17 -0400

>     (for congestion control purposes) and what is the cost?

I would argue that we don't, or at least *shouldn't*, trust senders
either.  You say there have been no big problems with the current trust
model, but DDoS attacks are a serious issue for many operators, and
the heart of the problem is that those senders are not trusted to send
useful data.  The difference is that there is no clear solution to the
malicious sender problem (to be fair, researchers are working on this),
but I don't see this as a good reason to not solve the untrusted receiver
end of the problem.

>     and how to phase this in seems like a detail.)

As per previous mails, I don't believe this style differentiated-service
solution would solve the general DoS problem.  If nodes that do not
negotiate the nonce have service reduced to some smallish maximum
rate, e.g., 5 KB/s, then a malicious attacker needs to just connect
to many more servers to obtain the same amount of malicious traffic.
Hundreds of thousands of servers, all sending at 5KB/s, is still a
significant/dangerous amount of traffic.  The high level concern is that
it is not possible for servers to coordinate among themselve to rate
limit the total amount of traffic caused by a single malicious receiver.

>     think).  It gained no traction.

Before I knew of this draft, I came up with and discarded this
solution, as described in the extended version of my CCS paper
(http://www.cs.umd.edu/~capveg/optack/optack-extended.pdf).  It's two
faults are that the ACKs are not cummulative, allowing the lazy version
of the attack to persist, and the concern that network middleboxes
(NATs,proxies,etc.) could be repacking packet sizes, breaking the
correctness of this scheme.  The extended version of the paper also
covers a litany of other possible solutions and how they compare to the
skipped segments solution.

Also, relative to Joe's comments: I too read this draft as a amendment
to the "standard,everyone's,everywhere's" TCP, and not just for testing
purposes.

- Rob
.

---

From: Rob Sherwood <[email-masked]>
Date: Wed, 21 Mar 2007 13:21:25 -0400

> doesn't have to be when this is a per connection cost.

I don't understand this concern -- each the receiver's rcvbuf is
advertised with each packet, no?  A receiver should not advertise more
then it can actually buffer, so as long as the TCP test respects the
window, is this really a concern?

- Rob
.

---

From: "Caitlin Bestler" <[email-masked]>
Date: Wed, 21 Mar 2007 10:48:20 -0700

Rob Sherwood wrote:
>> The most important adverse impact is that any receiver has a finite
>> capability for tracking gaps in the TCP sequence. Every gap that it
>> tracks requires some resources. Not much, but it doesn't have to be
>> when this is a per connection cost.
> 
> I don't understand this concern -- each the receiver's rcvbuf
> is advertised with each packet, no?  A receiver should not
> advertise more then it can actually buffer, so as long as the
> TCP test respects the window, is this really a concern?
> 
> - Rob
> .

It is not the buffer space that is in question. It is
remembering the number of disjoint sequences that have
been received.

---

From: Mark Allman <[email-masked]>
Date: Wed, 21 Mar 2007 14:04:12 -0400

> either.  You say there have been no big problems with the current
> trust model, but DDoS attacks are a serious issue for many operators,
> and the heart of the problem is that those senders are not trusted to
> send useful data.  The difference is that there is no clear solution
> to the malicious sender problem (to be fair, researchers are working
> on this), but I don't see this as a good reason to not solve the
> untrusted receiver end of the problem.

I was not clear.  Trusting senders to control their own rates is
stupid.  I do not want to get into a discussion about congestion control
theory.  But, even in a world that looks like the one we have now where
we do have reliance on the senders to do roughly the right thing we
should still be able to check that and verify it in some way.  At the
end of the day the network needs to protect itself.

Further, my ambiguous writing above about not having big problems with
the current trust model was in reference to the trust we have in the
receivers.  Certainly we have had problems with the trust we place in
senders.

Is the delta of trusting the receivers a big enough deal to worry about
separately or should that just fall under the concept of fate sharing
and we should just let something hammer on the sender that is spewing
inappropriately?  Is the threat posed by receivers lying big enough to
add a bunch of goop to implementations?

If I could ever so briefly put my co-chair hat back on ... I'm
interested in people's thoughts on this issue and document.  I know what
the people with solutions think.  I know what I have been saying for a
good long while.  I'd like to know what other people think.

allman

---

From: "Anantha Ramaiah \(ananth\)" <[email-masked]>
Date: Thu, 22 Mar 2007 03:55:17 -0700

> remembering the number of disjoint sequences that have been received.

FWIW, almost all TCP stacks have the counters maintained on a per TCP
connection basis for out-of-order bytes/data received, # of times
fast-retransmissions etc., not sure to what degree these would help
here.

-Anantha

---

From: Joe Touch <[email-masked]>
Date: Thu, 22 Mar 2007 04:04:14 -0700

> fast-retransmissions etc., not sure to what degree these would help

High-speed, high-performance (large number of connections) systems may
not have all these counters, and shouldn't be required to.

Joe

---

From: David Malone <[email-masked]>
Date: Thu, 22 Mar 2007 11:10:02 +0000

> inappropriately?

I've been trying to sort this out in my head. To some extent, it
may depend on who congestion control is a service to.

It seems fairly clear that the network benefits from congestion
control. The sender may also benefit, because it can prevent the
sender sending many packets which will probably be dropped, which
is a waste of effort on the sender's part.

OTOH, I don't think congestion control has ever been a service to
the receivers for two reasons. First, a receiver controls the
advertised window, and so had a mechanism for keeping (honest)
senders under control even before cwnd came along. Second, it seems
to me that congestion control probably works against receivers that
want to get bulk data quickly (as demonstrated by apps that open
multiple connections, but also a receiver with SACK could do quite
well if they could disable a sender's cwnd and just manage the
retransmissions themselves).

Based on this, it seems that the congestion control part of TCP
should trust the receiver less than it trusts the sender or the
network.

> Is the threat posed by receivers lying big enough to

I guess this is probably the crux of the matter. TCP implementations
have already grown quite a lot of goop in response to problems, but
usually after they're seen in practice rather than before. Until
someone builds a download accelerator using dishonest TCP receivers
and HTTP range requests, it may not be worth fixing.

	David.

---

From: "Caitlin Bestler" <[email-masked]>
Date: Thu, 22 Mar 2007 08:38:42 -0700

> -----Original Message-----
> From: Joe Touch [mailto:[email-masked]] 
> Sent: Thursday, March 22, 2007 4:04 AM
> To: Anantha Ramaiah (ananth)
> Cc: Caitlin Bestler; Rob Sherwood; [email-masked]
> Subject: Re: [tcpm] thoughts on draft-moncaster-tcpm-rcv-cheat-00
> 
> 
> 
> remembering the 
> >> number of disjoint sequences that have been received.
> > 
> High-speed, high-performance (large number of connections) 
> systems may not have all these counters, and shouldn't be required to.
> 
> Joe
> 
> 

I would hope that they could deal with at least one gap. The point is
that receivers like this need to do some serious tradeoffs to determine
what they track on a per connection basis. The resources available to
each high speed connection are engineered to cover the expected number
of gaps with a safety margin. The proposed test eats at that safety 
margin, and hence is not benign. High speed receivers should not be
forced to increase those margins because the IETF encouraged deployment
of this testing strategy.

---

From: Janardhan Iyengar <[email-masked]>
Date: Thu, 22 Mar 2007 21:41:01 -0400

> should trust the receiver less than it trusts the sender or the

I don't buy this.

A receiver that is interested in actually receiving data will want fewer 
losses. A receiver that is interested in receiving data asap will want 
fewer losses and fewer loss recovery periods. By trying to get around 
congestion control *completely*, it will cause losses for itself, and 
shoot itself in the foot.

My 2c at a late hour.
- jana

-- 
Janardhan R. Iyengar
Visiting Assistant Professor
Connecticut College
http://cs.conncoll.edu/iyengar/

---

From: <[email-masked]>
Date: Fri, 23 Mar 2007 09:07:57 -0000

Just to confirm, we certainly aren't intending that this should be added
as a requirement to all TCP stacks. Rather, the intention is to create a
safe standard mechanism by which senders can go about testing the
behaviour of receivers if they feel they are under pressure. The test
also has possible application as a means of network characterisation,
perhaps as a part of a TCP test stack.

We feel that it is essential that the test is appropriately specified
with due consideration for any interactions with other mechanisms within
TCP as well as taking into account any unintended state exhaustion
affect that it might cause as well as any effect on congestion control.

Toby

________________________________________________________________________
____
Toby Moncaster, <[email-masked]> Networks Research Centre, BT
Research
B54/70 Adastral Park, Martlesham Heath, Ipswich, IP53RE, UK.  +44 1473
648734 

-----Original Message-----
From: Joe Touch [mailto:[email-masked]] 
Sent: 21 March 2007 14:18
To: [email-masked]
Cc: [email-masked]
Subject: Re: [tcpm] thoughts on draft-moncaster-tcpm-rcv-cheat-00

Mark Allman wrote:
...

Joe

---

From: David Malone <[email-masked]>
Date: Fri, 23 Mar 2007 09:43:20 +0000

> shoot itself in the foot.

I don't think losses are a problem for a bulk receiver. Let me try
to explain why; please tell me if I'm talking nonsense. Imagine
the following scheme:

	1) The sender sends as fast as possible, beginning from the
	start of the data.

	2) The receiver lets the sender know about gaps once it is
	fairly sure it is a gap and not a reordering.

	3) The sender resends gaps when it first hears about them.
	Otherwise it retransmits any un-transmitted data or, if
	there is no un-transmitted data, it goes back to the beginning
	of the list of unacked data and works its way through that.

On a bulk transfer, the receiver will receive data at the rate
available on the tightest link and will not receive any data twice
until we get down to there being less than a few RTTs worth of data
left to send. The sender is never idle until the the receiver has
all the data.

Unless I've missed something, this means the receiver is getting
new data at the largest rate it can for most of the data transfer.
This scheme is relatively close to what happens if you disable cwnd
at the sender, have SACK and have a big receiver advertised window.
I'm not sure how a receiver could get substantially better long-term
throughput.

The situation is different if the receiver wants the data with some
sort of control on delay. If we have multiple competing receivers,
then we have some complicated game where it may not pay for everyone
to do this. However, when asking "who should we trust" you can't
depend on the game to keep everyone honest (cf spam?).

	David.

---

From: Joe Touch <[email-masked]>
Date: Thu, 29 Mar 2007 14:55:20 -0700

Toby,

The doc should state this explicitly and early (and imply it in the
title and in the abstract).

It would be useful to couch it as "intended to be reasonably safe when
deployed for test purposes and used sparingly so"; I think there are
reasonable concerns about what would happen if everyone's receiver
implemented this on a wide scale, and there ought to be a section
describing these concerns.

Joe