arithmetic: signed integer overflow

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

arithmetic: signed integer overflow

David Fifield
Running /usr/games/arithmetic with a range of INT_MAX trips a "can't
happen" check, because of a signed integer overflow.
        $ arithmetic -r 2147483647
        arithmetic: bug: inconsistent penalties.

The actual overflow happens before a call to getrandom:
        right = getrandom(rangemax + 1, op, 1);
        left = getrandom(rangemax + 1, op, 0);
        result = getrandom(rangemax + 1, op, 0);
        left = getrandom(rangemax + 1, op, 0);
        result = getrandom(rangemax + 1, op, 0);
getrandom receives INT_MAX+1 == INT_MIN. arc4random_uniform treats it as
a uint32_t; i.e., 0x80000000, but the result is cast back into a signed
int. The following check (value < maxval) always fails.

There is another overflow inside getrandom, one which depends on values
accumulated at runtime, namely the "penalty" counters that increase the
occurrence of numbers you've gotten wrong before:
        value = arc4random_uniform(maxval + penalty[op][operand]);
Every time you guess an answer wrong, the value for (op, operand) in the
penalty grows by 5. If you get enough answers wrong, eventually the sum
maxval + penalty[op][operand] will exceed 0x7fffffff, and there's a
chance that arc4random_uniform will return a value that overflows a
signed int. If you get even more answers wrong, then eventually the sum
will overflow even a uint32_t; but realistically you will probably run
into memory problems before that because each wrong answer also
allocates a node in a linked list.

Here is a patch that (I think) fixes all the above mentioned overflows
but the last, and turns the last into a signed overflow instead of an
unsigned overflow. It would take about 429 million ((1<<31) / 5) wrong
answers to provoke that last overflow. The patch just uses uint32_t for
the rangemax variable and penalty counters.

Index: arithmetic.c
===================================================================
RCS file: /cvs/src/games/arithmetic/arithmetic.c,v
retrieving revision 1.27
diff -u -p -u -r1.27 arithmetic.c
--- arithmetic.c 11 Sep 2016 14:21:17 -0000 1.27
+++ arithmetic.c 27 Dec 2018 04:14:20 -0000
@@ -70,7 +70,7 @@
 #include <time.h>
 #include <unistd.h>
 
-int getrandom(int, int, int);
+int getrandom(uint32_t, int, int);
 __dead void intr(int);
 int opnum(int);
 void penalise(int, int, int);
@@ -82,7 +82,7 @@ const char keylist[] = "+-x/";
 const char defaultkeys[] = "+-";
 const char *keys = defaultkeys;
 int nkeys = sizeof(defaultkeys) - 1;
-int rangemax = 10;
+uint32_t rangemax = 10;
 int nright, nwrong;
 time_t qtime;
 #define NQUESTS 20
@@ -115,7 +115,7 @@ main(int argc, char *argv[])
  break;
  }
  case 'r':
- rangemax = strtonum(optarg, 1, INT_MAX, &errstr);
+ rangemax = strtonum(optarg, 1, (1ULL<<31)-1, &errstr);
  if (errstr)
  errx(1, "invalid range, %s: %s", errstr, optarg);
  break;
@@ -266,9 +266,10 @@ retry:
  * penalties themselves.
  */
 
-int penalty[sizeof(keylist) - 1][2];
+uint32_t penalty[sizeof(keylist) - 1][2];
 struct penalty {
- int value, penalty; /* Penalised value and its penalty. */
+ int value; /* Penalised value. */
+ uint32_t penalty; /* Its penalty. */
  struct penalty *next;
 } *penlist[sizeof(keylist) - 1][2];
 
@@ -300,9 +301,9 @@ penalise(int value, int op, int operand)
  * we find the corresponding value and return that, decreasing its penalty.
  */
 int
-getrandom(int maxval, int op, int operand)
+getrandom(uint32_t maxval, int op, int operand)
 {
- int value;
+ uint32_t value;
  struct penalty **pp, *p;
 
  op = opnum(op);
@@ -313,7 +314,7 @@ getrandom(int maxval, int op, int operan
  * are positions to be located in the penalty list.
  */
  if (value < maxval)
- return(value);
+ return((int)value);
  value -= maxval;
 
  /*