buglwIP - A Lightweight TCP/IP stack - Bugs: bug #51447, Sequence number comparisons invoke...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #51447: Sequence number comparisons invoke implementation-defined behavior

Submitter:  Ambroz Bizjak <abizjak>
Submitted:  Tue 11 Jul 2017 10:19:32 PM UTC
   
 
Category:  TCP Severity:  3 - Normal
Item Group:  Crash Error Status:  In Progress
Privacy:  Public Assigned to:  goldsimon
Open/Closed:  Open Planned Release:  None
lwIP version:  git head

Jump to the original submission

Thu 31 Jan 2019 12:29:55 PM UTC, comment #15: 

It seems like this has been broken by commit a3d27e30e04bf1daa70dbe63e6c140f42fa7ab97 from 9th september 2004 which added TCP_SEQ_BETWEEN and uses it to replace various range tests.

That did work for valid segments, but it at least broke this check where 'seqno' and 'pcb->rcv_nxt' are exactly 0x80000000 apart.

I would fix it by reverting that commit for this line in question, but I first want to check the other changes that commit included to see if there are more problems of this kind.

Simon Goldschmidt <goldsimon>
Group administrator
Thu 31 Jan 2019 09:52:02 AM UTC, comment #14: 

Response from Stian Skjelstad on mailinglist:

Looking at Hiromasa ITO numbers:

if (TCP_SEQ_BETWEEN(pcb->rcv_nxt, seqno + 1, seqno + tcplen - 1)) {
                      u32         u32         u32       u16

seqno + 1          : 0x13d897cb
seqno + tcplen - 1 : 0x13d897ca /* this is smaller than seqno + 1, so already here, we see that this test should currently ALWAYS fail, when viewed with human eyes. It should be impossible to fit a number within the given range*/
pcb->rcv_nxt       : 0x93d897ca

TCP_SEQ_GEQ(0x93d897ca, 0x13d897cb) && TCP_SEQ_LEQ (0x93d897ca, 0x13d897ca)

/* signed compare*/      /* signed compare*/
  (0x7FFFFFFF >= 0)   && ( 0x80000000 <= 0)
  (2147483647 >= 0)   && (-2147483648 <= 0)


It looks like we should inspect tcplen before checking TCP_SEQ_BETWEEN. Currently tcplen is checked for greater than zero, but it should be greater than 1 for the current test to be valid (parameter 3 should be same size or greater than 2)

Dirk Ziegelmeier <dziegel>
Group administrator
Tue 29 Jan 2019 12:20:07 PM UTC, comment #13: 

It's a bug, but it's not a bug in TCP_SEQ_BETWEEN.

TCP_SEQ_BETWEEN(test, low, high) answers the question: if I start with "low" and keep incrementing it (modulo 2^32), will I hit "test" before I hit "high" (i'm ignoring "or equals" for brevity)?  For the numbers given the correct answer is true and the macro correctly returns true.

The bug is that the wrong question is asked, tcplen probably needs more checks, I haven't looked.

Valery Ushakov <uwe>
Tue 29 Jan 2019 09:49:20 AM UTC, comment #12: 

Reopen bug so this does not get lost

Dirk Ziegelmeier <dziegel>
Group administrator
Tue 29 Jan 2019 02:27:45 AM UTC, comment #11: 

I found some testcases caused a crash by this bug in fuzzing with AFL.
(I used experimental multi-packet fuzzing and some additional seeds made by myself.)

It happened in tcp_recieve()...(around tcp_in.c:1429 in lwIP v2.1.2)


/* --- code snippet start --- */

if (TCP_SEQ_BETWEEN(pcb->rcv_nxt, seqno + 1, seqno + tcplen - 1)) {

    u32_t off32 = pcb->rcv_nxt - seqno;

    /* This assertion failed and crashed. */
    LWIP_ASSERT("insane offset!", (off32 < 0xffff));

    [...]

}

/* --- code snippet end --- */


In one testcase caused a crash, arguments of TCP_SEQ_BETWEEN were as below.


seqno + 1          : 0x13d897cb
seqno + tcplen - 1 : 0x13d897ca
pcb->rcv_nxt       : 0x93d897ca


In this case, TCP_SEQ_BETWEEN should return FALSE, but actually, returned TRUE because ((pcb->rcv_nxt) - (seqno + tcplen - 1)) >= 2^31.
Then, off32 was greater than 0xffff, so LWIP_ASSERT failed and crashed.

I think,  this result shows that this bug is not just "theoretical" but "practical".

Hiromasa Ito <vhertz>
Mon 17 Jul 2017 07:52:49 PM UTC, comment #10: 

@Simon, all can be expressed in terms of LT as I have shown in the first post. Here is passing test code showing my macros behave the same as current ones in edge cases (a=b-1, a=b, a=b+1).



#include <assert.h>
#include <stdint.h>

typedef uint32_t u32_t;
typedef int32_t s32_t;

#define TCP_SEQ_LT(a,b) ((u32_t)((u32_t)(a) - (u32_t)(b)) >= 0x80000000u)
#define TCP_SEQ_LEQ(a,b) (!(TCP_SEQ_LT(b,a)))
#define TCP_SEQ_GT(a,b) TCP_SEQ_LT(b,a)
#define TCP_SEQ_GEQ(a,b) TCP_SEQ_LEQ(b,a)

#define TCP_SEQ_LT_OLD(a,b)     ((s32_t)((u32_t)(a) - (u32_t)(b)) < 0)
#define TCP_SEQ_LEQ_OLD(a,b)    ((s32_t)((u32_t)(a) - (u32_t)(b)) <= 0)
#define TCP_SEQ_GT_OLD(a,b)     ((s32_t)((u32_t)(a) - (u32_t)(b)) > 0)
#define TCP_SEQ_GEQ_OLD(a,b)    ((s32_t)((u32_t)(a) - (u32_t)(b)) >= 0)

int main()
{
    assert(TCP_SEQ_LT    (5, 6));
    assert(TCP_SEQ_LT_OLD(5, 6));
   
    assert(!TCP_SEQ_LT    (6, 6));
    assert(!TCP_SEQ_LT_OLD(6, 6));
   
    assert(!TCP_SEQ_LT    (7, 6));
    assert(!TCP_SEQ_LT_OLD(7, 6));
   
   
    assert(TCP_SEQ_LEQ    (5, 6));
    assert(TCP_SEQ_LEQ_OLD(5, 6));
   
    assert(TCP_SEQ_LEQ    (6, 6));
    assert(TCP_SEQ_LEQ_OLD(6, 6));
   
    assert(!TCP_SEQ_LEQ    (7, 6));
    assert(!TCP_SEQ_LEQ_OLD(7, 6));
   
   
    assert(!TCP_SEQ_GT    (5, 6));
    assert(!TCP_SEQ_GT_OLD(5, 6));
   
    assert(!TCP_SEQ_GT    (6, 6));
    assert(!TCP_SEQ_GT_OLD(6, 6));
   
    assert(TCP_SEQ_GT    (7, 6));
    assert(TCP_SEQ_GT_OLD(7, 6));
   
   
    assert(!TCP_SEQ_GEQ    (5, 6));
    assert(!TCP_SEQ_GEQ_OLD(5, 6));
   
    assert(TCP_SEQ_GEQ    (6, 6));
    assert(TCP_SEQ_GEQ_OLD(6, 6));
   
    assert(TCP_SEQ_GEQ    (7, 6));
    assert(TCP_SEQ_GEQ_OLD(7, 6));
   
   
    // Sanity check asserts are enabled
    assert(0);
   
    return 0;
}

Ambroz Bizjak <abizjak>
Fri 14 Jul 2017 06:06:00 PM UTC, comment #9: 

Given that it works on all systems I know and this is purely theoretical, let's wait until we see the first quantum computers that have incompatible implementation-defined behaviour :-)

Seriously, for _LT and _GEQ, the change is straigthforward. However, for _LEQ and _GT, it seems to me we would have to add "!= 0" as an extra check, having 2 checks instead of 1.

Simon Goldschmidt <goldsimon>
Group administrator
Fri 14 Jul 2017 05:50:43 PM UTC, comment #8: 

For these cases, the subject can be changed after creation.

Simon Goldschmidt <goldsimon>
Group administrator
Thu 13 Jul 2017 10:54:02 PM UTC, comment #7: 

@uwe Yes I had already corrected myself, there is no need to reiterate it.

I provided a simple change that resolves the issue. If the lwIP developers don't care about it, I will refrain from making further arguments.

Ambroz Bizjak <abizjak>
Thu 13 Jul 2017 09:54:17 PM UTC, comment #6: 

@abizjak - If you want to start nit-picking, you may at least try to be careful about your own wording.  Your summary claims "undefined behavior", but then you quote the relevant part of the standard that says "implementation-defined behavior".

So, basically you complain that lwip assumes 2-complement.

@mywave - converting -1 to u32_t is done by repeatedly adding ("mathematically") UINT32_MAX+1, so (after just one iteration) you will get the expected 0xffffffff

Valery Ushakov <uwe>
Wed 12 Jul 2017 05:01:39 PM UTC, comment #5: 

See that GCC generates identical code for the s32 cast and my solution, showing these really are equivalent: https://godbolt.org/g/S4gp7J

Ambroz Bizjak <abizjak>
Wed 12 Jul 2017 04:59:56 PM UTC, comment #4: 

C99 standard says this:

------
6.3.1.3 Signed and unsigned integers

1 When a value with integer type is converted to another integer type other than _Bool, if
the value can be represented by the new type, it is unchanged.

2 Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type.49)

3 Otherwise, the new type is signed and the value cannot be represented in it; either the
result is implementation-defined or an implementation-defined signal is raised.
------

In other words, converting any integer type to some unsigned integer type is always safe (modulo reduction), but converting to a signed integer type is not. It is not literally undefined behavior but still not something one should rely on.

I'm not saying the current macro gives incorrect results just that it invokes implementation-defined behavior according to the C standard. I think its behavior is perfectly sane otherwise (and equivalent to the solutions I gave).

Consider the case where a is 0xFFFFFFFF and b is 0. Then ((u32_t)(a)-(u32_t)(b)) has value 0xFFFFFFFF (and type u32_t or something wider that can represent any u32_t in case of promotions). Then, (s32_t)((u32_t)(a)-(u32_t)(b)) invokes implementation-defined behavior because 0xFFFFFFFF cannot be represented in s32_t.

Ambroz Bizjak <abizjak>
Wed 12 Jul 2017 07:26:23 AM UTC, comment #3: 

** Example: s16_t into u32_t will cause numbers to not be signed extended (-1 will become 0x0000ffff for example).

(swapped around in the example)


Stian Sebastian Skjelstad <mywave>
Wed 12 Jul 2017 07:23:32 AM UTC, comment #2: 

typecasting between s32_t and u32_t is not undefined behaviour. On (almost all) systems, CPU work in 2nd compliments and the only differences about u32_t and s32_t are which branch instructions or which comparison instruction to use.

The only situations where unwanted results might occur is when going from 16bit into 32bit. Example: u16_t into s32_t will cause numbers to not be signed extended (-1 will become 0x0000ffff for example).

The current macro will for example detect sequence number 0x00000004 to come after 0xfffffffe, since it only looks at the delta, ignoring that it has wrapped around zero.


In which situation does the current macro fail to give the correct result?



(file #41185)

Stian Sebastian Skjelstad <mywave>
Tue 11 Jul 2017 10:26:13 PM UTC, comment #1: 

forgot to cast the diferences to u32... the right code is:

#define TCP_SEQ_LT(a,b) ((u32_t)((u32_t)(a) - (u32_t)(b)) >= 0x80000000u)
#define TCP_SEQ_LT(a,b) (((u32_t)((u32_t)(a) - (u32_t)(b)) & 0x80000000u) != 0)
#define TCP_SEQ_LT(a,b) ((u32_t)((u32_t)(a) - (u32_t)(b)) >> 31)

Ambroz Bizjak <abizjak>
Tue 11 Jul 2017 10:19:32 PM UTC, original submission:  

See TCP_SEQ_LT and similar macros:
http://git.savannah.gnu.org/cgit/lwip.git/tree/src/include/lwip/priv/tcp_priv.h#n106

Two u32 are subtracted and the result is converted to s32. This is undefined behavior when the value is not representable in s32.

Fixed code:

#define TCP_SEQ_LT(a,b)     (((u32_t)(a) - (u32_t)(b)) >= 0x80000000u)
or
#define TCP_SEQ_LT(a,b)     ((((u32_t)(a) - (u32_t)(b)) & 0x80000000u) != 0)
or
#define TCP_SEQ_LT(a,b)     (((u32_t)(a) - (u32_t)(b)) >> 31)

In other words, a is less then b when the most significant bit in (a - b) mod 2^32 is set. One can see how this is exactly the same as the current implementation except for the the lack of undefined behavior, considering twos complement difference is the same thing as unsigned difference bitwise, and the sign bit is the most significant bit.

And the others can be expressed in terms of this one:

#define TCP_SEQ_LEQ(a,b)    (!(TCP_SEQ_LT(b,a)))
#define TCP_SEQ_GT(a,b)     TCP_SEQ_LT(b,a)
#define TCP_SEQ_GEQ(a,b)    TCP_SEQ_LEQ(b,a)

This is a theoretical bug, I chose "Crash Error" since it can in theory cause a crash.

Ambroz Bizjak <abizjak>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #41185:  u32.c added by mywave (798B - text/plain - test-case)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by dziegel (Posted a comment)
  • -email is unavailable- added by vhertz (Posted a comment)
  • -email is unavailable- added by goldsimon (Posted a comment)
  • -email is unavailable- added by uwe (Posted a comment)
  • -email is unavailable- added by mywave (Updated the item)
  • -email is unavailable- added by abizjak (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 8 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-01-31 goldsimon StatusNone In Progress
    2019-01-29 dziegel StatusWont Fix None
        Open/ClosedClosed Open
    2017-07-14 goldsimon StatusNone Wont Fix
        Assigned toNone goldsimon
        Open/ClosedOpen Closed
    2017-07-14 goldsimon SummarySequence number comparisons invoke undefined behavior Sequence number comparisons invoke implementation-defined behavior
    2017-07-12 mywave Attached File- Added u32.c, #41185

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code