[RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder]

[-- Attachment #1: Type: text/plain, Size: 79 bytes --]

As written, the function will access element [30] of a 30-element array.

OK?


[-- Attachment #2: hashtab.txt --]
[-- Type: text/plain, Size: 764 bytes --]

2011-03-03  Michael Snyder  <msnyder@vmware.com>

	* hashtab.c (higher_prime_index): Prevent array overrun.

Index: hashtab.c
===================================================================
RCS file: /cvs/src/src/libiberty/hashtab.c,v
retrieving revision 1.38
diff -u -p -u -p -r1.38 hashtab.c
--- hashtab.c	3 Feb 2011 07:23:59 -0000	1.38
+++ hashtab.c	3 Mar 2011 22:01:08 -0000
@@ -173,9 +173,9 @@ static unsigned int
 higher_prime_index (unsigned long n)
 {
   unsigned int low = 0;
-  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
+  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
 
-  while (low != high)
+  while (low < high)
     {
       unsigned int mid = low + (high - low) / 2;
       if (n > prime_tab[mid].prime)

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[DJ Delorie]

> As written, the function will access element [30] of a 30-element array.

Um, no?

      unsigned int mid = low + (high - low) / 2;

This can never give mid == high unless low == high, which won't happen
in that loop.

The math wants to search everything from (including) low to
(excluding) high.

(but I'm willing to be proven wrong...)

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder]

[-- Attachment #1: Type: text/plain, Size: 772 bytes --]

DJ Delorie wrote:
>> As written, the function will access element [30] of a 30-element array.
> 
> Um, no?

Y-uh-huh!

>       unsigned int mid = low + (high - low) / 2;
> 
> This can never give mid == high unless low == high, which won't happen
> in that loop.
> 
> The math wants to search everything from (including) low to
> (excluding) high.
> 
> (but I'm willing to be proven wrong...)

I am willing to do that!   ;-)

Compile this program, run it under gdb with the input "0xffffffff", and 
step through the code.  You will see it assign the value "30" to "low" 
and use it to access the array.

I suppose you could do it directly just by loading gdb into gdb,
putting a breakpoint at the above function, and then calling it
from gdb with the input 0xffffffff.





[-- Attachment #2: hash.c --]
[-- Type: text/x-csrc, Size: 2426 bytes --]

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

typedef unsigned int hashval_t;

struct prime_ent
{
  hashval_t prime;
  hashval_t inv;
  hashval_t inv_m2;     /* inverse of prime-2 */
  hashval_t shift;
};

static struct prime_ent const prime_tab[] = {
  {          7, 0x24924925, 0x9999999b, 2 },
  {         13, 0x3b13b13c, 0x745d1747, 3 },
  {         31, 0x08421085, 0x1a7b9612, 4 },
  {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
  {        127, 0x02040811, 0x0624dd30, 6 },
  {        251, 0x05197f7e, 0x073260a5, 7 },
  {        509, 0x01824366, 0x02864fc8, 8 },
  {       1021, 0x00c0906d, 0x014191f7, 9 },
  {       2039, 0x0121456f, 0x0161e69e, 10 },
  {       4093, 0x00300902, 0x00501908, 11 },
  {       8191, 0x00080041, 0x00180241, 12 },
  {      16381, 0x000c0091, 0x00140191, 13 },
  {      32749, 0x002605a5, 0x002a06e6, 14 },
  {      65521, 0x000f00e2, 0x00110122, 15 },
  {     131071, 0x00008001, 0x00018003, 16 },
  {     262139, 0x00014002, 0x0001c004, 17 },
  {     524287, 0x00002001, 0x00006001, 18 },
  {    1048573, 0x00003001, 0x00005001, 19 },
  {    2097143, 0x00004801, 0x00005801, 20 },
  {    4194301, 0x00000c01, 0x00001401, 21 },
  {    8388593, 0x00001e01, 0x00002201, 22 },
  {   16777213, 0x00000301, 0x00000501, 23 },
  {   33554393, 0x00001381, 0x00001481, 24 },
  {   67108859, 0x00000141, 0x000001c1, 25 },
  {  134217689, 0x000004e1, 0x00000521, 26 },
  {  268435399, 0x00000391, 0x000003b1, 27 },
  {  536870909, 0x00000019, 0x00000029, 28 },
  { 1073741789, 0x0000008d, 0x00000095, 29 },
  { 2147483647, 0x00000003, 0x00000007, 30 },
  /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
  { 0xfffffffb, 0x00000006, 0x00000008, 31 }
};

static unsigned int
higher_prime_index (unsigned long n)
{
  unsigned int low = 0;
  unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);

  while (low != high)
    {
      unsigned int mid = low + (high - low) / 2;
      if (n > prime_tab[mid].prime)
        low = mid + 1;
      else
        high = mid;
    }

  /* If we've run out of primes, abort.  */
  if (n > prime_tab[low].prime)
    {
      fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
      abort ();
    }

  return low;
}


int
main (int argc, char **argv)
{
  if (argc < 2)
    {
      fprintf (stderr, "Usage: hash <number>\n");
      return 1;
    }

  printf ("Answer: %d\n", higher_prime_index (strtoul (argv[1], NULL, 0)));
  return 0;
}

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[DJ Delorie]

Bizzare, the problem isn't the hash loop, it's the error handler at
the end!  It never uses [30] for the main loop, only if you give it a
number between 0xfffffffb and 0xffffffff - and in the case where it
would use [30], it's supposed to abort anyway.

I couldn't figure out why your patch worked until I realized that the
main loop still fails!  It works because the error handler just
doesn't abort, returning the last array entry, which happens to be the
right one.

I think a suitable comment explaining what's actually going on, and
why it still works, is warranted... but your patch is OK with me
otherwise :-)

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder]

DJ Delorie wrote:
> Bizzare, the problem isn't the hash loop, it's the error handler at
> the end!  It never uses [30] for the main loop, only if you give it a
> number between 0xfffffffb and 0xffffffff - and in the case where it
> would use [30], it's supposed to abort anyway.
> 
> I couldn't figure out why your patch worked until I realized that the
> main loop still fails!  It works because the error handler just
> doesn't abort, returning the last array entry, which happens to be the
> right one.
> 
> I think a suitable comment explaining what's actually going on, and
> why it still works, is warranted... but your patch is OK with me
> otherwise :-)

Please give me the comment, and I'll check it in.

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Mike Stump]

On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote:
> DJ Delorie wrote:
>>> As written, the function will access element [30] of a 30-element array.
>> Um, no?
> 
> Y-uh-huh!

fight fight fight...  :-)  There can be only one.

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder]

Mike Stump wrote:
> On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote:
>> DJ Delorie wrote:
>>>> As written, the function will access element [30] of a 30-element array.
>>> Um, no?
>> Y-uh-huh!
> 
> fight fight fight...  :-)  There can be only one.

Oh, did I forget the smiley?   ;-)

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Dave Korn]

On 03/03/2011 23:00, Mike Stump wrote:
> On Mar 3, 2011, at 2:26 PM, Michael Snyder wrote:
>> DJ Delorie wrote:
>>>> As written, the function will access element [30] of a 30-element array.
>>> Um, no?
>> Y-uh-huh!
> 
> fight fight fight...  :-)  There can be only one.

  I was just wondering whether now would be a good time to mention that having
prime-sized hash tables is only a workaround against the danger of someone
providing an inadequate hash function implementation in the first place?

    cheers,
      DaveK

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[DJ Delorie]

>   I was just wondering whether now would be a good time to mention

Probably not, gcc being in stage 4 and all...

Re: [RFA] libiberty/hashtab.c, higher_prime_index: avoid array overrun

[Michael Snyder]

DJ Delorie wrote:
>> As written, the function will access element [30] of a 30-element array.
> 
> Um, no?
> 
>       unsigned int mid = low + (high - low) / 2;
> 
> This can never give mid == high unless low == high, which won't happen
> in that loop.
> 
> The math wants to search everything from (including) low to
> (excluding) high.
> 
> (but I'm willing to be proven wrong...)


Whee, here we go...


(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file 
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)

Breakpoint 2, higher_prime_index (n=4294967295)
     at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175       unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176       unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178       while (low < high)
(gdb)
180           unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181           if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182             low = mid + 1;
1: low = 0(gdb) b higher_prime_index
Breakpoint 2 at 0x79bed4: file 
/data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c, line 175.
(gdb) print higher_prime_index(0xffffffff)

Breakpoint 2, higher_prime_index (n=4294967295)
     at /data/home/msnyder/cvs/localhost/src/libiberty/hashtab.c:175
175       unsigned int low = 0;
The program being debugged stopped while in a function called from GDB.
Evaluation of the expression containing the function
(higher_prime_index) will be abandoned.
When the function is done executing, GDB will silently stop.
(gdb) n
176       unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]) - 1;
(gdb)
178       while (low < high)
(gdb)
180           unsigned int mid = low + (high - low) / 2;
(gdb) display low
1: low = 0
(gdb) n
181           if (n > prime_tab[mid].prime)
1: low = 0
(gdb)
182             low = mid + 1;
1: low = 0
(gdb)
178       while (low < high)
1: low = 16
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182             low = mid + 1;

(gdb)
178       while (low < high)
1: low = 16
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 16
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 16
(gdb)
182             low = mid + 1;
1: low = 16
(gdb)
178       while (low < high)
1: low = 24
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 24
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 24
(gdb)
182             low = mid + 1;
1: low = 24
(gdb)
178       while (low < high)
1: low = 28
(gdb)
180           unsigned int mid = low + (high - low) / 2;
1: low = 28
(gdb)
181           if (n > prime_tab[mid].prime)
1: low = 28
(gdb)
182             low = mid + 1;
1: low = 28
(gdb)
178       while (low < high)
1: low = 30
(gdb)
188       if (n > prime_tab[low].prime)
1: low = 30
(gdb)