integer overflow yields incorrect results and buffer overflow on 64-bit machines

[Vincent Lefevre]

I've reported the following bug here:

  http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=467463

It occurs on machines with 64-bit address space and 32-bit int's
(and sufficient memory (RAM + swap), such as a bit more than 16 GB).
Enabling assertions can probably detect the bug earlier (I haven't
checked).

GMP doesn't check for integer overflows internally. In particular, the
number of limbs is stored in an int (32 bits under Linux), which isn't
sufficient, and the testcase below shows that one can get incorrect
results. What occurs is that the correct number of limbs is allocated,
but an incorrect (lower) value is stored and the current size _mp_size
is incorrect too. With the test below, the _mp_size field becomes
negative due to the integer overflow, which means a negative number
(instead of positive): sign(2^c) = -1.

Moreover what appears to be the most significant limb is no longer
non-zero, so that one can get erratic behavior, e.g. buffer overflow
(at least when reading, as shown in the testcase, and probably worse
with user-defined alloc functions, because *__gmp_reallocate_func
would be called with an incorrect old_size value).

$ gcc -Wall -O2 gmp_powof2.c -o gmp_powof2 -lgmp
$ ./gmp_powof2 0x2000000000
sizeof(mp_size_t)    = 8
sizeof(n->_mp_alloc) = 4
sizeof(n->_mp_size)  = 4
c = 137438953472 = 0x2000000000 bits
n->_mp_alloc = -2147483646 = 0x80000002 limbs
n->_mp_size  = -2147483647 = 0x80000001 limbs
sign(2^c) = -1
d = 137438953344 = 0x1fffffff80 bits
p->_mp_alloc = 1 = 0x1 limbs
p->_mp_size  = 1 = 0x1 limbs
popcount(p) = 0
Divisibility test...
zsh: floating point exception (core dumped)  ./gmp_powof2 0x2000000000

------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main (int argc, char **argv)
{
  mpz_t n, p;
  unsigned long c, d;

  if (argc != 2)
    {
      fprintf (stderr, "Usage: gmp_powof2 <count>\n");
      exit (1);
    }

  printf ("sizeof(mp_size_t)    = %d\n", (int) sizeof(mp_size_t));
  printf ("sizeof(n->_mp_alloc) = %d\n", (int) sizeof(n->_mp_alloc));
  printf ("sizeof(n->_mp_size)  = %d\n", (int) sizeof(n->_mp_size));

  c = strtoul (argv[1], NULL, 0);
  printf ("c = %lu = 0x%lx bits\n", c, c);

  mpz_init_set_si (n, 1);
  mpz_mul_2exp (n, n, c);
  printf ("n->_mp_alloc = %d = 0x%x limbs\n",
          n->_mp_alloc, (unsigned int) n->_mp_alloc);
  printf ("n->_mp_size  = %d = 0x%x limbs\n",
          n->_mp_size, (unsigned int) n->_mp_size);
  printf ("sign(2^c) = %d\n", mpz_sgn (n));

  d = 64 * ((unsigned long) - n->_mp_size - 1);
  printf ("d = %lu = 0x%lx bits\n", d, d);

  mpz_init (p);
  mpz_tdiv_q_2exp (p, n, d);
  mpz_abs (p, p);
  printf ("p->_mp_alloc = %d = 0x%x limbs\n",
          p->_mp_alloc, (unsigned int) p->_mp_alloc);
  printf ("p->_mp_size  = %d = 0x%x limbs\n",
          p->_mp_size, (unsigned int) p->_mp_size);
  printf ("popcount(p) = %lu\n", mpz_popcount (p));
  /* p can have a single limb 0. */

  printf ("Divisibility test...\n");
  printf ("mpz_divisible_p (p, p) = %d\n", mpz_divisible_p (p, p));
  mpz_clear (p);

  return 0;
}
------------------------------------------------------------------------

-- 
Vincent Lefèvre <vincent at vinc17.org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)