Dynamic hash table size (with static has load)

Shachar Shemesh rsync at shemesh.biz
Sun Feb 26 16:55:18 GMT 2006


Wayne Davison wrote:

>On Sun, Feb 26, 2006 at 10:34:25AM +0200, Shachar Shemesh wrote:
>  
>
>>A line of credit would have been nice :-)
>>    
>>
>
>Sure 'nuff.
>  
>
‎Thanks.

>>2. In "sum_buf", sum1 is defined to be unsigned. It seems dangerous to
>>me to hash it into a signed index, even if it's almost guarenteed to be ok.
>>    
>>
>The result is an index into the array (and can be no larger than the max
>size of the array), so I like to use the same type as the other indexes.
>  
>
If you are not convinced, I will not press this matter further. Still,
the paranoid in me (I've spent over two years at Check Point,
manufacturer of Firewall-1, as their chief paranoid engineer)  (the
official title was "Security Focus Team Leader", thought) is uneasy with
this. Strike that, I think I can actually exploit this.

I'll draw you a scenario:
- Attacker puts just enough checksums in the count to make the 20%
expansion overflow the 32bit variable. We now get a tablesize of "1".
- The gettag divides the sums by 1, resulting in negative indexes into
the array.
- Profit

Conclusions:
- We need to guard the expansion code from integer overflows.
- Please, please please please please, make the indexes unsigned!

>>initialize the chain element to -1 instead of 0, as
>>that's the "null" value).
>>    
>>
>The latter was a bug, since it results in the 0th element being checked
>in every chain -- good catch.
>  
>
Thanks, but I really do think it's a simple style matter. As far as I
can tell, the chain variable is overwritten (s->sums[i].chain =
sum_table[t];) before the first time it is used, so no actual bug, just
style.

>..wayne..
>  
>
Shachar


Suggested guard code in case I did not convince you to switch to unsigned:

static const int32 MAXHASHES=(0x7fffffff-11)/10*8;


...


if( s->count > MAXHASHES )

    Error


If you do make the right decision ;-), the number above needs to be
amended a little.

static const size_t MAXHASHES=((~((size_t)0))-11)/10*8



More information about the rsync mailing list