[BUG] before() integer overflow

[BUG] before() integer overflow

[Nicolas Bareil]

Hello!


In include/net/tcp.h, the before() function is defined like this :

 241 /*
 242  * The next routines deal with comparing 32 bit unsigned ints
 243  * and worry about wraparound (automatic with unsigned arithmetic).
 244  */
 245 
 246 static inline int before(__u32 seq1, __u32 seq2)
 247 {
 248         return (__s32)(seq1-seq2) < 0;
 249 }
 250 #define after(seq2, seq1)   before(seq1, seq2)


If seq1 = 0xffffff and seq2 = 0 (so seq1 > seq2), the difference is
equal to 0xffffff, or -1 as a 32 bits signed number.

 => before() will return true instead of false.

It's not really a big deal[1], but I didn't understand why my invalid
packets were accepted when playing with Netfilter code.

If I'm not wrong, a trivial patch could be :

diff --git a/include/net/tcp.h b/include/net/tcp.h
index 8983386..2b01227 100644
--- a/include/net/tcp.h
+++ b/include/net/tcp.h
@@ -248,7 +248,7 @@ extern int tcp_memory_pressure;
 
 static inline int before(__u32 seq1, __u32 seq2)
 {
-        return (__s32)(seq1-seq2) < 0;
+        return ((__u64)seq1-seq2) < 0;
 }
 #define after(seq2, seq1)      before(seq1, seq2)

Thanks


Footnotes: 
[1]  The TCP sequence number space is divided by two, now on 31 bits,
     phear! :) 
-- 
Nicolas Bareil                                  http://chdir.org/~nico/
OpenPGP=0xAE4F7057 Fingerprint=34DB22091049FB2F33E6B71580F314DAAE4F7057

Re: [BUG] before() integer overflow

[Ben Hutchings]

Nicolas Bareil wrote:
> 
> Hello!
> 
> 
> In include/net/tcp.h, the before() function is defined like this :
> 
>  241 /*
>  242  * The next routines deal with comparing 32 bit unsigned ints
>  243  * and worry about wraparound (automatic with unsigned arithmetic).
>  244  */
>  245 
>  246 static inline int before(__u32 seq1, __u32 seq2)
>  247 {
>  248         return (__s32)(seq1-seq2) < 0;
>  249 }
>  250 #define after(seq2, seq1)   before(seq1, seq2)
> 
> 
> If seq1 = 0xffffff and seq2 = 0 (so seq1 > seq2), the difference is
> equal to 0xffffff, or -1 as a 32 bits signed number.
> 
>  => before() will return true instead of false.
[...]

That's exactly what we want.  The initial sequence number is random (and
TCP streams are not limited to 4GB) so the sequence can wrap around.  0
follows 0xffffffff.  If we were to compare sequence numbers from two
packets more than 2GB apart in the stream, this comparison would give
the wrong answer, but currently this is not likely to be a problem.

Ben.

-- 
Ben Hutchings, Senior Software Engineer, Solarflare Communications
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [BUG] before() integer overflow

[David Stevens]

netdev-owner@vger.kernel.org wrote on 08/05/2008 10:19:18 AM:

> 
> If seq1 = 0xffffff and seq2 = 0 (so seq1 > seq2), the difference is
> equal to 0xffffff, or -1 as a 32 bits signed number.

        In the sequence space, 0xffffffff is before 0 (by 1), so
before() should return true. In your example, you don't have enough
f's for it to be -1 as a signed number, so I'm assuming you mean
8 of them there. If you mean 6 f's, then the result is not -1, but the
positive number 0xffffff, which returns false.

                                                                +-DLS

Re: [BUG] before() integer overflow

[Nicolas Bareil]

David Stevens <dlstevens@us.ibm.com> writes:
>         In the sequence space, 0xffffffff is before 0 (by 1), so
> before() should return true. In your example, you don't have enough
> f's for it to be -1 as a signed number, so I'm assuming you mean
> 8 of them there. If you mean 6 f's, then the result is not -1, but the
> positive number 0xffffff, which returns false.

Yes I meant 8 f (I should change my too small fonts ;) )

Thanks to Ben for his explanation, I thought the PAWS was handled in a
specific way. Sorry!

-- 
Nicolas Bareil                                  http://chdir.org/~nico/
OpenPGP=0xAE4F7057 Fingerprint=34DB22091049FB2F33E6B71580F314DAAE4F7057