Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

32bit overflow does not work #125

Open
kfessel opened this issue Feb 7, 2022 · 9 comments
Open

32bit overflow does not work #125

kfessel opened this issue Feb 7, 2022 · 9 comments

Comments

@kfessel
Copy link

kfessel commented Feb 7, 2022

dtls_time.h seems to be uint32_t aware:

typedef uint32_t clock_time_t;

but these lines may produce problems with 32bit overflow:

these calculate possibly overflowing time stamps:

tinydtls/dtls.c

Line 1763 in 68b2521

n->t = now + 2 * CLOCK_SECOND;

tinydtls/dtls.c

Line 4534 in 68b2521

node->t = now + (node->timeout << node->retransmit_cnt);

these do not deal with overflowing timestamps:
calculating if the timeout happend: (timestamp passed by)

tinydtls/dtls.c

Line 4596 in 68b2521

while (node && node->t <= now) {

inserting (sorted) into the netq

while(p && p->t <= node->t) {

In #123 @boaks and me pointed that out

reference / line number are current develop branch

@kfessel
Copy link
Author

kfessel commented Feb 7, 2022

read later comment

(node && (now - node->t) < (((clock_time_t)0 - 1) / 2))

is true if (now > node->t) (taking overflow semantic into account)
(assuming (clock_time_t is some kind of unsigned integer -> defined overflow)

@kfessel
Copy link
Author

kfessel commented Feb 7, 2022

I did a bit of testing using https://godbolt.org/z/qKPeoazhr

overflow seems to be applied when the whole calculation is done ->

calculate an offset

const clock_time_t offset = (((clock_time_t)~0) >> 1);

add offset to difference then cast to _t and compare to offset

if (node && ((offset + now - node->t) > offset)){
  //now is later than node->t
}

(this works as well if for any reason clock_time_t would be signed)

@boaks
Copy link
Contributor

boaks commented Mar 29, 2022

typedef int32_t clock_time_s_t;
typedef uint32_t clock_time_u_t;

...

  clock_time_s_t ts1, ts2;
  clock_time_u_t tu1, tu2;

  // signed overflow
  ts1 = 0x7ffffff0;
  ts2 = ts1 + 32;

  tu1 = 0x7ffffff0;
  tu2 = tu1 + 32;

  dtls_warn("signed: %d %d %d %d\n", ts1, ts2, (ts2 - ts1) > 0, (ts2 - ts1) < 0);
  dtls_warn("unsign: %u %u %d %d\n", tu1, tu2, (tu2 - tu1) > 0,  (tu2 - tu1) < 0);

  // unsigned overflow
  ts1 = 0xfffffff0;
  ts2 = ts1 + 32;

  tu1 = 0xfffffff0;
  tu2 = tu1 + 32;

  dtls_warn("signed: %d %d %d %d\n", ts1, ts2, (ts2 - ts1) > 0, (ts2 - ts1) < 0);
  dtls_warn("unsign: %u %u %d %d\n", tu1, tu2, (tu2 - tu1) > 0,  (tu2 - tu1) < 0);

Prints

signed: 2147483632 -2147483632 1 0
unsign: 2147483632 2147483664 1 0
signed: -16 16 1 0
unsign: 4294967280 16 1 0

I'm not sure, why (((clock_time_t)0 - 1) / 2) should be used?

@boaks
Copy link
Contributor

boaks commented Mar 29, 2022

I'm not sure, why (((clock_time_t)0 - 1) / 2) should be used?#

OK, it's not that simple as in java ;-).

@kfessel
Copy link
Author

kfessel commented Mar 29, 2022

((offset + now - node->t) > offset

should be used
instead of

now - node->t > 0

since the later might lead into UB since singed overflow is not defined and might not work as expected if optimized and the compiler chose to do the substraction and the comparison on an larger type.
example:
loop1: is the working one (with magic offset) (magic offset can be written as ((T)~0)>>1 or ((T)0-1)/2)
loop2: works for signed values
loop3: is allways kindof wrong

the c off all loops is expected to equal the number of loops (300) or 0 (if TN_OFFSET if defined negative)

#include <stdio.h>
#include <stdint.h>

#define TN_OFFSET (50)

typedef uint8_t clock_time_t;

int main(void){
    volatile clock_time_t t = 0;
    volatile clock_time_t n = 0;
    const clock_time_t magic_offset = (((clock_time_t)~0) >> 1);
    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((clock_time_t)(magic_offset + n - t) < magic_offset){
            c++;
        }
    }
    printf("loop 1 c:%d \n", c);
    }

    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((clock_time_t)(n - t) < 0){
            c++;
        }
    }
    printf("loop 2 c:%d \n", c);
    }

    {
    int c = 0;
    for (int i = 0 ; i < 300; i ++ ){
        //i will overflow into t and n 
        t = i;
        n = i - TN_OFFSET;
        if ((n - t) < 0){
            c++;
        }
    }
    printf("loop 3 c:%d \n", c);
    }

    printf("%d\n", magic_offset);
    
    return 0;
}

compiler explorer example

boaks pushed a commit to bosch-io/tinydtls that referenced this issue Mar 29, 2022
Fixes issue: eclipse#125

Signed-off-by: Achim Kraus <achim.kraus@bosch.io>
boaks pushed a commit to bosch-io/tinydtls that referenced this issue Mar 29, 2022
Fixes issue: eclipse#125

Signed-off-by: Achim Kraus <achim.kraus@bosch.io>
boaks pushed a commit to bosch-io/tinydtls that referenced this issue Mar 30, 2022
Fixes issue: eclipse#125

Signed-off-by: Achim Kraus <achim.kraus@bosch.io>
boaks pushed a commit to bosch-io/tinydtls that referenced this issue Mar 30, 2022
Fixes issue: eclipse#125

Signed-off-by: Achim Kraus <achim.kraus@bosch.io>
boaks pushed a commit to bosch-io/tinydtls that referenced this issue Mar 30, 2022
Fixes issue: eclipse#125

Signed-off-by: Achim Kraus <achim.kraus@bosch.io>
@obgm
Copy link
Contributor

obgm commented May 27, 2022

@kfessel did you have a change to check with PR #131 merged?

@kfessel
Copy link
Author

kfessel commented May 27, 2022

Hi @obgm: since @boaks detected this issue though reading the code, I described it, @boaks developed the fixing PR (hence he solver what he read by writing) and I gave my cent to it (correct overflow handling regardless of singnedness).
I think we can consider this solved.
I never had a test for that other than reading. (I think this would require a Multiday session of DTLS)

@boaks
Copy link
Contributor

boaks commented May 27, 2022

I think, adding some unit test for the calculation may be an idea. But for now, there is too much other stuff already pending.

@obgm
Copy link
Contributor

obgm commented May 27, 2022

@kfessel sorry for the confusion

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants