[PATCH tcp-2.6 0/2]: SACK block validation

Hi,

SACK block validation to tcp-2.6 tree. Before preparing this, I rebased
tcp-2.6 to net-2.6 (not 2.6.23) because of DSACK patch in net-2.6 (some
conflicts will occur). I did some very basic testing with this. No
TCPSACKDiscards occured in it but it's kind of hard for me to fully
test the whole internet without being a server end for most of it,
maybe I should start abusing all port probers for that purpose by using
them as sinks... :-)

This patchset addresses the only issue I found while trying to address
your earlier comments (found in here):
  http://marc.info/?l=linux-netdev&m=118060110632768&w=2
It's perfectly ok for timedout_continue to be NULL and it's being
checked for except when the result of find for tp->highest_sack is
accessed (that will be a valid skb because sacked_out > 0). Actually
I didn't fully understand what was the concern with timedout_continue
rather than with skb... But this problem was located anyway, so the
comment itself proved useful (and DSACK regression got fixed too due
to it :-)).

If they it looks sane, you can consider applying to tcp-2.6 (rebasing
is needed for that). I'm not entirely sure if I can add MIB stuff
just like that (couldn't find any examples from the available history)
though some info will definately be useful when trying to figure out
regression reports (due to flawed TCP implementation of the peer).
Yes, it might cause some troubles when communicating with broken TCP
implementations.

Do you have some plans regarding tcp-2.6? FYI, I've also discovered
that the current implementation of timedout_mark_forward is flawed
because "tcp_skb_timedout() boundary" is advanced whenever
retransmissions there occur but I probably don't have time to address
that until mid-July or so. I think that the hint is not coming back
though as TCP can use a binary search that finds TCBCB_TAGBITS
boundary using the RB-tree. My other plans include, e.g., combining
highest_sack(+fackets_out) and sack fastpath hints but that requires
some benchmarking first to see how frequently they are different, I
suspect it won't really happen that often, so most of the time we have
three u32s and one skb ptr "pointing" the very same place (fackets stuff
is not really pointing but related like you said earlier)... :-)

--
 i.

From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <redacted>

SACK processing code has been sort of russian roulette as no
validation of SACK blocks is previously attempted. It is not
very clear what all kinds of broken SACK blocks really mean
(e.g., one that has start and end sequence numbers reversed).

This fixes also one remote triggerable NULL-ptr access:
start_seq was trusted as a valid mark_lost_entry_seq but
without validation it is relatively easy to inject an invalid
sequence number there that will cause a crash in the lost
marker code. Other SACK processing code seems safe so this could
have been fixed locally but that would leave SACK processing
hazardous in case of future modifications. IMHO, it's just
better to close the whole roulette rather than disarming just
one bullet.

Signed-off-by: Ilpo Järvinen <redacted>
---
 net/ipv4/tcp_input.c |   40 ++++++++++++++++++++++++++++++++++++++++
 1 files changed, 40 insertions(+), 0 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 4c8882e..ebd9739 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c

@@ -977,6 +977,27 @@ static void tcp_update_reordering(struct sock *sk, const int metric,
  * so that we are allowed not to be bothered by order of our actions,
  * when multiple events arrive simultaneously. (see the function below).
  *
+ * SACK block validation.
+ * ----------------------
+ *
+ * SACK block range validation checks that the received SACK block fits to
+ * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT.
+ * Note that SND.UNA is not included to the range though being valid because
+ * it means that the receiver is rather inconsistent with itself (reports
+ * SACK reneging when it should advance SND.UNA).
+ *
+ * With D-SACK the lower bound is extended to cover sequence space below
+ * SND.UNA down to undo_marker, which is the last point of interest. But
+ * there all simplicity ends, TCP might receive valid D-SACKs below that.
+ * As long as they reside fully below undo_marker they do not affect
+ * behavior in anyway and can therefore be safely ignored. In rare cases
+ * (which are really theoretical ones), the D-SACK will nicely cross that
+ * boundary due to skb fragmentation and packet reordering past skb's
+ * retransmission. To consider them correctly, the acceptable range must
+ * be extended even more though the exact amount is rather hard to
+ * quantify (from the state TCP has?), so in boundary crossing case
+ * simply adjust start_seq to undo_marker.
+ *
  * Reordering detection.
  * --------------------
  * Reordering metric is maximal distance, which a packet can be displaced

@@ -1243,9 +1264,28 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb,
 		struct sk_buff *skb;
 		__u32 start_seq = ntohl(sp->start_seq);
 		__u32 end_seq = ntohl(sp->end_seq);
+		u32 valid_range_start;
 		int fack_count;
 		state.dup_sack = (found_dup_sack && (i == state.first_sack_index));
 
+		/* SACK validation: start_seq == snd_una is non-sensical */
+		valid_range_start = tp->snd_una + 1;
+
+		if (state.dup_sack && tp->undo_marker) {
+			valid_range_start = tp->undo_marker;
+
+			/* Undo_marker boundary crossing, see comments above */
+			if (before(start_seq, tp->undo_marker) &&
+			    after(end_seq, tp->undo_marker))
+			    	start_seq = tp->undo_marker;
+		}
+
+		/* Discard SACK blocks that are seemingly bad */
+		if (before(start_seq, valid_range_start) ||
+		    after(end_seq, tp->snd_nxt) ||
+		    !before(start_seq, end_seq))
+			continue;
+
 		skb = cached_skb;
 		fack_count = cached_fack_count;
 

-- 
1.5.0.6

From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <redacted>

Signed-off-by: Ilpo Järvinen <redacted>
---
 include/linux/snmp.h |    1 +
 net/ipv4/proc.c      |    1 +
 net/ipv4/tcp_input.c |    4 +++-
 3 files changed, 5 insertions(+), 1 deletions(-)

diff --git a/include/linux/snmp.h b/include/linux/snmp.h
index 802b3a3..6e64a70 100644
--- a/include/linux/snmp.h
+++ b/include/linux/snmp.h

@@ -231,6 +231,7 @@ enum
 	LINUX_MIB_TCPABORTONLINGER,		/* TCPAbortOnLinger */
 	LINUX_MIB_TCPABORTFAILED,		/* TCPAbortFailed */
 	LINUX_MIB_TCPMEMORYPRESSURES,		/* TCPMemoryPressures */
+	LINUX_MIB_TCPSACKDISCARD,		/* TCPSACKDiscard */
 	__LINUX_MIB_MAX
 };
 

diff --git a/net/ipv4/proc.c b/net/ipv4/proc.c
index 3b690cf..d5a8de0 100644
--- a/net/ipv4/proc.c
+++ b/net/ipv4/proc.c

@@ -244,6 +244,7 @@ static const struct snmp_mib snmp4_net_list[] = {
 	SNMP_MIB_ITEM("TCPAbortOnLinger", LINUX_MIB_TCPABORTONLINGER),
 	SNMP_MIB_ITEM("TCPAbortFailed", LINUX_MIB_TCPABORTFAILED),
 	SNMP_MIB_ITEM("TCPMemoryPressures", LINUX_MIB_TCPMEMORYPRESSURES),
+	SNMP_MIB_ITEM("TCPSACKDiscard", LINUX_MIB_TCPSACKDISCARD),
 	SNMP_MIB_SENTINEL
 };
 

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index ebd9739..e26d8ca 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c

@@ -1283,8 +1283,10 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb,
 		/* Discard SACK blocks that are seemingly bad */
 		if (before(start_seq, valid_range_start) ||
 		    after(end_seq, tp->snd_nxt) ||
-		    !before(start_seq, end_seq))
+		    !before(start_seq, end_seq)) {
+			NET_INC_STATS_BH(LINUX_MIB_TCPSACKDISCARD);
 			continue;
+		}
 
 		skb = cached_skb;
 		fack_count = cached_fack_count;

-- 
1.5.0.6

From: "Ilpo_Järvinen" <redacted>
Date: Tue, 19 Jun 2007 01:25:57 +0300

From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <redacted>

SACK processing code has been sort of russian roulette as no
validation of SACK blocks is previously attempted. It is not
very clear what all kinds of broken SACK blocks really mean
(e.g., one that has start and end sequence numbers reversed).

This fixes also one remote triggerable NULL-ptr access:
start_seq was trusted as a valid mark_lost_entry_seq but
without validation it is relatively easy to inject an invalid
sequence number there that will cause a crash in the lost
marker code. Other SACK processing code seems safe so this could
have been fixed locally but that would leave SACK processing
hazardous in case of future modifications. IMHO, it's just
better to close the whole roulette rather than disarming just
one bullet.

Signed-off-by: Ilpo Järvinen <redacted>

This looks good applied.

Does mainline 2.6.x has this NULL-ptr issues too?  If so
we'll have to fix it there very soon.

From: "Ilpo_Järvinen" <redacted>
Date: Tue, 19 Jun 2007 01:25:58 +0300

From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <redacted>

Signed-off-by: Ilpo Järvinen <redacted>

Adding this MIB item is perfectly fine, patch applied.

From: "Ilpo_Järvinen" <redacted>
Date: Tue, 19 Jun 2007 01:25:56 +0300

Do you have some plans regarding tcp-2.6?

It is sort-of stuck in the mud until some real performance analysis of
the RB-Tree stuff can be done.

I'm currently knee-deep in working on support for some virtualization
disk and network drivers on sparc64, but once I clear away with that I
hope to get to some performance work with the RB-Tree stuff.

On Mon, 18 Jun 2007, David Miller wrote:

From: "Ilpo_Järvinen" <redacted>
Date: Tue, 19 Jun 2007 01:25:57 +0300

quoted

From: =?ISO-8859-1?q?Ilpo_J=E4rvinen?= <redacted>

SACK processing code has been sort of russian roulette as no
validation of SACK blocks is previously attempted. It is not
very clear what all kinds of broken SACK blocks really mean
(e.g., one that has start and end sequence numbers reversed).

This fixes also one remote triggerable NULL-ptr access:
start_seq was trusted as a valid mark_lost_entry_seq but
without validation it is relatively easy to inject an invalid
sequence number there that will cause a crash in the lost
marker code. Other SACK processing code seems safe so this could
have been fixed locally but that would leave SACK processing
hazardous in case of future modifications. IMHO, it's just
better to close the whole roulette rather than disarming just
one bullet.

Signed-off-by: Ilpo Järvinen <redacted>

This looks good applied.

Does mainline 2.6.x has this NULL-ptr issues too? If so
we'll have to fix it there very soon.

The null-ptr issue is related to the new lost marker code which isn't
in the mainline (I have even tried to state this couple of times in the 
earlier posts so that you could have less worries as I understand that 
it's your highest priority concern :-)). I.e, the mainline lost marker 
code scans queue by using tcp_for_write_queue() or starts from the hint 
it has learned earlier, it doesn't have to trust any sequences that are
given by the peer in SACK block.

I'll try to explain this once again: Because the new lost marker 
fastpath blindly trusted start_seq from received SACK, it could be 
abused to search for a sequence number for which tcp_write_queue_find 
returns NULL (happens when the searched sequence is outside of current 
window).

Another trouble would nowadays occur if start_seq == snd_una because 
write_queue_find is now given start_seq - 1 (which is fully intentional, 
no need to find skb at start_seq but one below it). I disallowed SACK 
blocks starting from snd_una partly due to that, and partly due to it's 
non-sense interpretation. It would not end up to the lost marker though 
because sack reneging detection intervenes.

Obviously I would have alerted you and security folks if there would have 
been this problem in mainline & stable too (and probably had done a valid 
patch to those trees at the first time). In case you still want to verify 
mainline by yourself, you can see where start_seq and end_seq goes in 
mainline's sacktag (not very hard to see :-)). Like I've explained 
earlier, only serious suspect seems to be the calculation of pkt_len that 
is input to tcp_fragment. Other cases are relatively trivial. However, 
analytical analysis of pkt_len setting took me considerable amount of time 
due to vast number of negations which were able to defeat my brains at 
least partly. Therefore I really wouldn't mind if also you verify that 
pkt_len never becomes either zero or exceeds skb->len (even equal to 
skb->len is not very nice). Things I tried to consider are (you might find 
some additional thing to consider besides these): 
  - outside snd_una-snd_nxt start/end_seq
  - start/end_seq equal
  - start/end_seq reversing
  - 2^31 wrap problems
  - after/before ambiguity (discussed some time ago on netdev)
I couldn't find a problem causing case because the successive before() and 
after() jails were so tight. Neither did my limited bruteforcer succeed 
(as you can see, I wasn't that convinced about by my analysis validity)... 

For sure you're curious enough - have a nice day with the negations... ;-)
...Seriously, double verification of that pkt_len part wouldn't hurt 
considering it's complexity.

-- 
 i.

From: "Ilpo_Järvinen" <redacted>
Date: Wed, 20 Jun 2007 02:09:44 +0300 (EEST)

For sure you're curious enough - have a nice day with the negations... ;-)
...Seriously, double verification of that pkt_len part wouldn't hurt 
considering it's complexity.

Thanks for explaining everything, you've given me a lot of
chew on :)