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

login
register
mail settings
Submitter Michael Snyder
Date March 3, 2011, 10:04 p.m.
Message ID <4D701056.1080208@vmware.com>
Download mbox | patch
Permalink /patch/85347/
State New
Headers show

Comments

Michael Snyder - March 3, 2011, 10:04 p.m.
As written, the function will access element [30] of a 30-element array.

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

	* hashtab.c (higher_prime_index): Prevent array overrun.
DJ Delorie - March 3, 2011, 10:11 p.m.
> 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...)
Michael Snyder - March 3, 2011, 10:26 p.m.
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.
Michael Snyder - March 3, 2011, 10:32 p.m.
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)
DJ Delorie - March 3, 2011, 10:59 p.m.
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 :-)
Mike Stump - March 3, 2011, 11 p.m.
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.
Michael Snyder - March 3, 2011, 11:24 p.m.
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?   ;-)
Dave Korn - March 4, 2011, 12:13 a.m.
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
DJ Delorie - March 4, 2011, 12:19 a.m.
>   I was just wondering whether now would be a good time to mention

Probably not, gcc being in stage 4 and all...
Michael Snyder - March 7, 2011, 12:51 a.m.
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.

Patch

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)