Re: Function overflow relies on undefined behavior

[Caio Giuliani]

Hello,

I was just reading the source code and found it by chance.

Signed integer overflow is known to be Undefined Behavior (UB) in the C standard.

You must simply avoid it. Trying to observe its effects is wrong.

Though I found it by chance, some tools (such as static analysers and compiler's ub sanitizer) could help, but I have no experience with them.

If the code is taking much longer, you could try substituting the test with a macro such as

#define addition_overflows(u, v) ((u > 0 && v > INT_MAX - u)  || (u < 0 && v < INT_MIN - u))

but it would have no effect if the compiler is already inlining the function.

Best,

Caio

Em sex., 17 de dez. de 2021 às 08:22, Domingo Alvarez Duarte <mingodad@gmail.com> escreveu:

Hello Caio !

How have you come to find this problem ?

Looking through compiler warnings ?

Trying to solve a specific problem ?

Using your proposed overflow function and testing the all models in the "examples" folder I didn't found any difference on the results other than it takes a bit longer to solve then (before the compiler was effectively eliminating the "overflow" function).

Cheers !

On 15/12/21 16:37, Domingo Alvarez Duarte wrote:

Hello Caio !

Thank you for your discovery !

I can confirm what you've found, here is small C program to test it:

====

#include <stdio.h>

#include <limits.h>
static int overflow2(int u, int v)
{     /* check for integer overflow on computing u + v */
      if (u > 0 && v > INT_MAX - u) return 1;
      if (u < 0 && v < INT_MIN - u) return 1;
      return 0;
}

static int overflow(int u, int v)
{     /* check for integer overflow on computing u + v */
      if (u > 0 && v > 0 && u + v < 0) return 1;
      if (u < 0 && v < 0 && u + v > 0) return 1;
      return 0;
}

int main() {
    int max_u = 10;
    for(int u= 0, v = 0; u< max_u; ++u, ++v)
        printf("== %d : %d : %d : %d\n", u, v, overflow(u,v), overflow2(u,v));
    for(int u= 0, v = INT_MAX-max_u; u < max_u; ++u, ++v)
        printf(":::: %d : %d : %d : %d\n", u, v, overflow(u,v), overflow2(u,v));
    return 0;
}

====

Output without optimization:

====

gcc -o overflow overflow.c

./overflow

== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 1 : 1
:::: 7 : 2147483644 : 1 : 1
:::: 8 : 2147483645 : 1 : 1
:::: 9 : 2147483646 : 1 : 1

====

Output without optimization:

====

gcc -O2 -o overflow2 overflow.c
./overflow2
== 0 : 0 : 0 : 0
== 1 : 1 : 0 : 0
== 2 : 2 : 0 : 0
== 3 : 3 : 0 : 0
== 4 : 4 : 0 : 0
== 5 : 5 : 0 : 0
== 6 : 6 : 0 : 0
== 7 : 7 : 0 : 0
== 8 : 8 : 0 : 0
== 9 : 9 : 0 : 0
:::: 0 : 2147483637 : 0 : 0
:::: 1 : 2147483638 : 0 : 0
:::: 2 : 2147483639 : 0 : 0
:::: 3 : 2147483640 : 0 : 0
:::: 4 : 2147483641 : 0 : 0
:::: 5 : 2147483642 : 0 : 0
:::: 6 : 2147483643 : 0 : 1  <<< always 0
:::: 7 : 2147483644 : 0 : 1  <<< always 0
:::: 8 : 2147483645 : 0 : 1  <<< always 0
:::: 9 : 2147483646 : 0 : 1  <<< always 0

====

Cheers !

On 15/12/21 16:01, Caio Giuliani wrote:

Greetings,

Files src/misc/okalg.c and src/api/mcfrelax.c define the following function:
static int overflow(int u, int v)
{     /* check for integer overflow on computing u + v */
      if (u > 0 && v > 0 && u + v < 0) return 1;
      if (u < 0 && v < 0 && u + v > 0) return 1;
      return 0;
}
It contains integer overflow, which is undefined behavior by the C standard.
As I tested, both GCC 11.1.0 and clang 13.0.0 make this function always return 0 from optimization level O1 onwards.
Particularly function glp_mincost_relax4 appears to have received ad-hoc patches on the places this function is used.

I propose, instead, the following:
#include <limits.h>
static int overflow(int u, int v)
{     /* check for integer overflow on computing u + v */
      return (u > 0 && v > INT_MAX - u) return 1;
      if (u < 0 && v < INT_MIN - u) return 1;
      return 0;
}

Best regards,

--

Caio Merlini Giuliani

Operations Research Analyst

WPLEX Software Ltda

www.wplex.com.br

--

Caio Merlini Giuliani

Operations Research Analyst

WPLEX Software Ltda

www.wplex.com.br