Awesome

SMHasher - A hash function test-bench in C++

This is a fork of Google's "smhasher" suite, available here:

https://chromium.googlesource.com/external/smhasher

It incorporates changes from Reini Urban's fork as well. See:

https://github.com/rurban/smhasher

Compared to those versions it has been substantially extended to:

• Use better stats internally (g-test)
• Better test how the hash functions are seeded
• Separate timing of hashing from that of initialization

My personal interest is to develop and test hash functions which are suitable in contexts where the hash function will be seeded relatively rarely, must perform well, are sufficiently "strong" that they can be safely used to hash untrusted data.

This is a level of security below that of a proper message digest, but above that of "your average hash function".

In particular a hash function must not leak information about its seed, and must not have any inherent weaknesses that allow an attacker to construct a collision attack without knowing the seed.

I have tried to enhance the smhasher package to make it easier to test the scenario outlined above. Your mileage may vary.

A New API for seeding Hash functions

It would seem that smhasher was originally intended to test hash functions with 32 bit seeds, and this requirement was baked into the design in various ways. This is problematic because a hash with a larger seed will have to somehow map the 32-bit seed into a larger space, interfering with testing. While some hash functions have well defined mappings to handle 32 bit seeds many, if not most, do not. In a test like the avalanche test, the results of 32 bit test can easily differ from that of true seed-size testing.

So to properly test a hash function you need to be able to deal with whatever seed size it requires, and test based on that size.

Another issue is that some hash functions have expensive seeding operations which are intended to be amortized to a single seeding for many hash operations. Timing stats for such functions will not be accurate unless the action of seeding the state, and actually executing the hash function are separated.

So where the old interface was:

typedef void (*pfHash) ( const void *blob, const int len, const uint32_t seed, void *out );

I have changed to a new interface with two functions like this:

typedef void (*pfSeedState) ( const int seedbits, const void *seed, const void *state );
typedef void (*pfHashWithState) ( const void *blob, const int len, const void *state, void *out );

The seedbits argument in pfSeedState is provided to allow a single seed preparation function serve multiple seed sizes if required. Most implementations would ignore it as it would always be constant.

The pfSeedState function is optional, and when omitted it is assumed that the input "state" to the hash function corresponds exactly to that of the seed. In other words when there is no pfSeedState function defined the configuration for the hash should set the "statebits" to be the same as the "seedbits", and the "state seeding" operation will simply pass through the seed as a pointer.

The end result of all of this is that we now support any seed size, and provide support for no, shared, or unique state seeding functions.

How To Add A New Function

You will need to:

1. Implement functions that match the expected API.

2. Update main.cpp to contain a new HashInfo entry for the hash

   <pre> typedef struct HashInfo { const char * name; const char * desc; int seedbits; int statebits; int hashbits; uint32_t verification; pfSeedState seed_state; pfHashWithState hash_with_state; } HashInfo; </pre>

   For example:

   <pre> { "Spooky128", "Bob Jenkins' SpookyHash, 128-bit seed, 128-bit result", 128, 128, 128, 0xC633C71E, SpookyHash_seed_state_test, SpookyHash128_with_state_test }, </pre>

   The verification value can be set to 0x0, in which case failed verification tests will produce a warning, but allow you to continue testing, or you can just put whatever you like in there as we will update its value to be correct in a following step.

3. Compile And Build

   You can run ./SMHasher --validate to see if any hashes fail test. If they do the test harness will not let you continue until you correct them. The only exceptions are for those with a verification code of 0. If everything is good then you should see:

   <pre> Self-test PASSED. </pre>

   At this point if you set the verification value to 0 you are done. But you will want to return here later once you have finalized the implementation of your hash function.

4. Update the Verification Code for your Hash

   You can do this two ways, the first is run

    perl update_hashes.pl
   

   which /should/ update your hashes verification code (and only its code) automagically. If it says it has updated more then there is something wrong. Alternatively you can do what it does manually and run

    ./SMHasher --validate
   

   which will produce output saying what the expected, and actual verification codes were, you can then C&P the corrected code into the structure. For example:

   <pre> ./SMHasher --validate Self-test FAILED! Spooky128 - Verification value 0xC633C71E : Failed! (Expected 0xC633C70E) </pre>

   I would use the perl script personally.

5. Build Again.

   Once you have corrected the verification code you need to rebuild to bake it in. Once that is complete you are done. Happy testing!

About the tests

I have not reviewed ALL of the smhasher tests in detail yet. I have reviewed most of the stats logic, especially logic related to determining if a set of hash values is "random" or not, and upgraded it to use g-test.

If it is not documented below then I have not gotten around to it yet.

Sanity Test

This does some very basic tests. It verifies that the hash is consistent and that simple key changes produce changed hashes. It also verifies that the hash is capable of hashing a string of nulls without producing excess collisions, this is a simpler version of the "Zeroes" test.

Speed Tests

This test actually contains two subtests which can be run independently.

BulkSpeed Test

Times hashing very long keys at different alignments. Architectures that allow unaligned access will probably not see much difference at the different alignments.

KeySpeed Test

Times hashing keys of various lengths, ranging from the empty string to relatively long strings.

Differential Tests

This hashes strings of various sizes with relatively few bits set, and then looks for excess collisions. Hash functions with a weak mix function, or weak seeding will often fail these tests.

(NB: I don't know too much about these tests. More to come later.)

Avalanche Test

This tests that a hash meets the "strict avalanche criteria", which is that when changing any single bit of the input (seed or key) we expect about 50% of the output bits to change.

This is tested at various key lengths, including 0 byte keys, and stats are calculated about how input bit affects the output, and whether the results are random or not.

Passing tests look like this:

Worst bit shows how many percentages away from the expected 50/50 changed/unchanged ratio we want to see. Anything under %1.00 is considered acceptable. A scaled expected error is calculated for the test, and then the sum of the square of the difference from 0.5 is used to calculate an "error ratio". A good hash function should have a ratio of very close to or below 1. A bad hash function could have wildly higher numbers.

When tests fail two charts are produced which show how every bit of the input affected every bit of the hash produced. One chart shows the distance from the expected %50 change, and the other shows the g-test probability of getting that result. Additionally each "row" and "column" is checked to ensure that they are correct as well. The following is an example which shows a hash function which really does not mix very well at all, with many input bits having little if any affect on the output. Only the positions with "." in them are "ok".

Cyclic Tests

This tests various cyclic keys to ensure that they produce the expected collision counts.

TwoBytes

This tests keys composed of 2-character tuples repeated to various lengths.

Sparse Tests

This tests strings of various lengths with very few bits set. I have found This test is relatively sensitive. It will often fail when the other tests do not, especially when a hash has a weak mixing function.

Combination tests

I don't know what these tests do in detail yet.

Window Tests

These test that keys of various sizes produce hashes with good distributions across all of the bit ranges in the hash.

The exact validity of these tests is yet to be determined. Failing them is definitely bad, but passing these tests does not necessarily say much.

Currently the rule for failing a test is: the g-test of the bucket distribution must exceed the required confidence level, AND the distribution must produce a bad quality score. I have tested using the g-test alone and even hash functions like sha1 fail the tests, on the other hand, what the g-test considers non-random the quality score metric may consider within tolerance. These test need further mathematical rigour.

Text Tests

This tests various simple string keys of specific forms at different lengths and ensures they do not produce excessive collisions or bad distributions.

Zeroes Test

Tests keys consisting of only the null byte of various lengths.

Seed Tests

Tests hashing the same key with many different and unique seeds and then ensures that the result has a good distribution, and collision rate.

Effs Test

Similar to the Zeros test, this verifies that hashing keys of ever longer sequences of 0xFF bytes does not produce excess collisions and produces good distributions.

Collision Tests

These test that for a given set of keys the results produce the expected number of collisions. For instance with 262144 keys a 32 bit hash should produce about 8 collisions. The test will fail if the actual count exceeds double that of expected. This is not very sensitive, and my be adjusted later.

Distribution Tests

This checks that the hashes produce reasonable distributions.

XXX: Document exact rules.

Using the g-test

Where possible I have changed smhasher to use the g-test for determining if a distribution is non-random. The test is a more accurate version of the chi-square test and can be used to calculate the probability that the distribution of N items into M buckets is "random":

or in pseudo code:

 g += v * log(v/(n/m))
    for each non-zero v in buckets_array

The g-value follows a chi-squared distribution with the same number of degrees-of-freedom, so any function that can convert a chi-square value to a probability can be used with the g-test. We use:

 1.0 - gsl_sf_gamma_inc_Q( ( double(m) - 1.0) / 2.0, g )

from the GNU scientific library.

Wikipedia has more info on the <a href="https://en.wikipedia.org/wiki/G-test">G-Test</a> and the <a href="https://en.wikipedia.org/wiki/Chi-squared_distribution">Chi-Squared Distribution</a>.

Note that the standard C log() function suffers some interesting and subtle cancellation errors when its argument is very close to and above 1, so the actual code uses log1p() when v > n/m.

Quality Score

The distribution tests have always used a "score" to determine if the distribution was good. I did not understand the old score, and found it produced weird results, so I replaced it with something that seemed similar but better known to me.

The following assumes we are hashing /n/ items into /m/ buckets.

The old score was

which in pseudo-code is

sum_sq += v * v
    for v in buckets_array
old_score = 1.0 - ( ( ( n * n )  - 1.0 ) / ( sum_sq - n ) / m )

The new score is

which in pseudo-code is

qs_sum += ( v * ( v + 1.0 ) ) / 2.0
    for v in buckets_array
quality_score = qs_sum / ( ( n / ( 2.0 * m ) ) *
                           ( n + ( 2.0 * m ) - 1.0 ) )
score = abs( 1.0 - quality_score )

The quality score formula is from the Red Dragon book. A good hash function should have a quality score of close to one, with values between 0.95 to 1.05 being normal. In theory having a lower quality score is better, however excessively low values indicate non-random behavior that probably indicates some other weakness. Therefore our tests use the distance from 1 instead, and consider anything higher than 0.01 to be a failure.

Further discussion on hash functions and quality scores can be found <a href="http://www.strchr.com/hash_functions">here</a> (along with all kinds of other valuable information).