shithub: puzzles

Info  •  Files  •  Log  •  Branches

Add validate_params bounds checks in a few more games.

Ben tells me that his recent work in this area was entirely driven by
fuzzing: he added bounds checks in validate_params when the fuzzer had
managed to prove that the lack of them allowed something buggy to
happen.

It seemed worth doing an eyeball-review pass to complement that
strategy, so in this commit I've gone through and added a few more
checks that restrict the area of the grid to be less than INT_MAX.

Notable in this commit: cube.c had to do something complicated because
in the triangular-grid modes the area isn't calculated as easily as
w*h, and Range's existing check that w+h-1 < SCHAR_MAX is sufficient
to rule out w*h being overlarge _but_ should be done before w*h is
ever computed.

--- a/cube.c

+++ b/cube.c

@@ -542,12 +542,36 @@

     if (params->solid < 0 || params->solid >= lenof(solids))

 	return "Unrecognised solid type";

+    if (params->d1 < 0 || params->d2 < 0)

+        return "Grid dimensions may not be negative";

+

     if (solids[params->solid]->order == 4) {

 	if (params->d1 <= 1 || params->d2 <= 1)

 	    return "Both grid dimensions must be greater than one";

+        if (params->d2 > INT_MAX / params->d1)

+	    return "Grid area must not be unreasonably large";

     } else {

 	if (params->d1 <= 0 && params->d2 <= 0)

 	    return "At least one grid dimension must be greater than zero";

+

+        /*

+         * Check whether d1^2 + d2^2 + 4 d1 d2 > INT_MAX, without overflow:

+         *

+         * First check d1^2 doesn't overflow by itself.

+         *

+         * Then check d2^2 doesn't exceed the remaining space between

+         * d1^2 and INT_MAX.

+         *

+         * If that's all OK then we know both d1 and d2 are

+         * individually less than the square root of INT_MAX, so we

+         * can safely multiply them and compare against the

+         * _remaining_ space.

+         */

+        if ((params->d1 > INT_MAX / params->d1) ||

+            (params->d2 > (INT_MAX - params->d1*params->d1) / params->d2) ||

+            (params->d1*params->d2 > (INT_MAX - params->d1*params->d1 -

+                                      params->d2*params->d2) / params->d2))

+	    return "Grid area must not be unreasonably large";

     }

     for (i = 0; i < 4; i++)

--- a/filling.c

+++ b/filling.c

@@ -188,6 +188,8 @@

 {

     if (params->w < 1) return "Width must be at least one";

     if (params->h < 1) return "Height must be at least one";

+    if (params->w > INT_MAX / params->h)

+        return "Width times height must not be unreasonably large";

     return NULL;

 }

--- a/range.c

+++ b/range.c

@@ -911,8 +911,8 @@

     int const w = params->w, h = params->h;

     if (w < 1) return "Error: width is less than 1";

     if (h < 1) return "Error: height is less than 1";

+    if (w > SCHAR_MAX - (h - 1)) return "Error: w + h is too big";

     if (w * h < 1) return "Error: size is less than 1";

-    if (w + h - 1 > SCHAR_MAX) return "Error: w + h is too big";

     /* I might be unable to store clues in my puzzle_size *grid; */

     if (full) {

         if (w == 2 && h == 2) return "Error: can't create 2x2 puzzles";

--- a/rect.c

+++ b/rect.c

@@ -218,6 +218,8 @@

 {

     if (params->w <= 0 || params->h <= 0)

 	return "Width and height must both be greater than zero";

+    if (params->w > INT_MAX / params->h)

+        return "Width times height must not be unreasonably large";

     if (params->w*params->h < 2)

 	return "Grid area must be greater than one";

     if (params->expandfactor < 0.0F)

--- a/slant.c

+++ b/slant.c

@@ -226,6 +226,8 @@

     if (params->w < 2 || params->h < 2)

 	return "Width and height must both be at least two";

+    if (params->w > INT_MAX / params->h)

+        return "Width times height must not be unreasonably large";

     return NULL;

 }

--- a/unruly.c

+++ b/unruly.c

@@ -286,6 +286,8 @@

         return "Width and height must both be even";

     if (params->w2 < 6 || params->h2 < 6)

         return "Width and height must be at least 6";

+    if (params->w2 > INT_MAX / params->h2)

+        return "Width times height must not be unreasonably large";

     if (params->unique) {

         static const long A177790[] = {

             /*