Set64::insert() panics

[tkuestner]

Hello!

first of all: nice crate. It really fits my needs.

I found that the following code snippet panics with "attempt to add with overflow" (about 50% of the times I run it on my machine):

use tinyset::Set64;
let mut a: Set64<u64> = Set64::new();
let mut b: Set64<u64> = Set64::new();
a.insert(u64::MAX);
a.insert(8589934592);
a.insert(8589934593);
a.insert(17179869184);
a.insert(17179869185);
a.insert(12884901889);
b.insert(17179869187);
b.insert(17179869188);
b.insert(12884901889);
b.insert(12884901890);
b.insert(12884901891);
b.insert(12884901892);
let c = &a - &b;

I guess it only panics sometimes because tinyset internally uses a random number generator.

Side question: Is the random number generator cryptographically secure? If yes, would you consider adding the option (feature) of using an pseudo RNG when security is not a requirement?

[droundy]

Thanks for the report! I'll try to get to this soon. Do you think you could get a pull request in with this as a failing test?

[droundy]

As it turns out I was able to get it done this morning. Thanks again for the report! At first I thought this wasn't likely to be a real bug (i.e. wrapping add would turn out to be what we wanted), but since tinyset randomizes the size of the hash table, it is not a power of two, and this really did give incorrect behavior!

Regarding your other question with regard to randomization, there is a default feature called rand to use the rand crate, and if you disable it, you get a very simple pseudorandom number generator seeded by the system time. This still doesn't give you reproducible results, however (due to the seeding). I see that this needs documentation, and it might be nice to have a way to turn off the seeding based on time.

The use of the randomization is to provide some protection against collision DOS attacks. It's not very sophisticated (we don't hash the numbers!), we just randomize the size of the table when we grow it, so attackers shouldn't be able to guess integers that are identical modulo the length of the table. This also protects us a bit from non-attacker DOS simply caused by a bunch of values differing by n*1024 or something.

[tkuestner]

Hi, thanks for responding so quickly and fixing the bug.
I will test disabling the rand feature and see if it makes a difference in my application.