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

Submitted by:  Ambroz Bizjak <abizjak>
Submitted on:  Tue 11 Jul 2017 10:19:32 PM UTC  
 
Category: TCPSeverity: 3 - Normal
Item Group: Crash ErrorStatus: Wont Fix
Privacy: PublicAssigned to: Simon Goldschmidt <goldsimon>
Open/Closed: ClosedPlanned Release: None
lwIP version: git head

(Jump to the original submission Jump to the original submission)

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>
Project AdministratorIn charge of this item.
Fri 14 Jul 2017 05:50:43 PM UTC, comment #8:

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

Simon Goldschmidt <goldsimon>
Project AdministratorIn charge of this item.
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>

 

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
  • -unavailable- added by goldsimon (Posted a comment)
  • -unavailable- added by uwe (Posted a comment)
  • -unavailable- added by mywave (Updated the item)
  • -unavailable- added by abizjak (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 5 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 14 Jul 2017 06:06:00 PM UTCgoldsimonStatusNone=>Wont Fix
      Assigned toNone=>goldsimon
      Open/ClosedOpen=>Closed
    Fri 14 Jul 2017 05:50:43 PM UTCgoldsimonSummarySequence number comparisons invoke undefined behavior=>Sequence number comparisons invoke implementation-defined behavior
    Wed 12 Jul 2017 07:23:32 AM UTCmywaveAttached File-=>Added u32.c, #41185

    Back to the top


    Powered by Savane 3.1-cleanup1