# Support turning off hashmap randomness **URL:** \ **Category:** language design\ **Created:** [July 26, 2023, 3:10pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234 "2023-07-26T15:10:38Z")\ **Posts on this page:** 17\ **Page:** 1
**Author:** ![joonazan](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/joonazan/32/11115_2.png) [@joonazan](https://internals.rust-lang.org/u/joonazan)\ **Post date:** [July 26, 2023, 3:10pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/1 "2023-07-26T15:10:38Z")
I'm having trouble fuzzing and benchmarking Rust programs because of the random seeding of `std::collections::HashMap`. The random behaviour makes fuzzing instrumentation see differences when there are none. People using `cargo fuzz` will just have poor results with no indication of a problem. AFL++ reported the stability of my target to be only 60-70%. Disabling randomization brought the stability to 100.00% In theory, people can support different hashers in their code. But HashMap is used in many common dependencies as well, so they'd have to override every dependency. Instead, I used `-Z build-std` and edited the constructor of RandomState to be deterministic. Before that, I tried using cargo's patch feature to override hashbrown but that didn't work. I'm sure many people would benefit from being able to do this in a clean way. In std's code hashmaps have their own code for true randomness. Maybe the system clock should also be disabled. Other randomness can probably be dealt with by using cargo's patch feature on the rand crate. I don't know what the best solution would be but I wanted to write about this since I didn't find a thread anywhere even though this problem makes Rust essentially unfuzzable. I did find this other thread just now, which is about problems benchmarking. The getrandom solution there is cleaner than what I have but I would never have thought of that even though I read the relevant source code. > [@Proposal: Support setting fixed hash seed for benchmarking purposes](https://internals.rust-lang.org/t/proposal-support-setting-fixed-hash-seed-for-benchmarking-purposes/13696): > > New here, so forgive me if this is the wrong place to post proposals, or if I'm doing it wrong. Use case When benchmarking, one wants to get rid of sources of noise. Randomized hash functions are one such source of noise. The solution is to set a fixed seed—somehow. Solutions Custom logic (not good enough) One alternative is to have each application or libraries have its own custom logic for doing this. However, dependencies may also be creating HashMaps; it would be unworkable to have everyon… ---
**Author:** ![8573](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/8573/32/4913_2.png) [@8573](https://internals.rust-lang.org/u/8573)\ **Post date:** [July 27, 2023, 2:05am UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/2 "2023-07-27T02:05:47Z")
It could make sense to file a ticket at [https://github.com/rust-fuzz/book/issues](https://github.com/rust-fuzz/book/issues) to recommend a solution, after (or before) a solution is found here. ---
**Author:** ![bascule](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bascule/32/3057_2.png) [@bascule](https://internals.rust-lang.org/u/bascule)\ **Post date:** [July 30, 2023, 8:26pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/3 "2023-07-30T20:26:50Z")
FYI, while this may make sense for fuzzing, for the benchmarking use case it may have [unexpected effects on HashMap performance](https://morestina.net/blog/1843/the-stable-hashmap-trap) including degrading certain O(n) operations to O(n^2). This is because the HashMap implementation relies on a randomized hasher as a "fix" for ["accidentally quadratic" behavior](https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion). ---
**Author:** ![8573](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/8573/32/4913_2.png) [@8573](https://internals.rust-lang.org/u/8573)\ **Post date:** [July 30, 2023, 8:40pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/4 "2023-07-30T20:40:34Z")
> [@8573](#): > > It could make sense to file a ticket at [https://github.com/rust-fuzz/book/issues](https://github.com/rust-fuzz/book/issues) This was done: > > > Almost all Rust code uses \`std::collections::HashMap\` with the default hasher. T…his makes instrumentation almost useless. > > For example, one of my targets didn't even manage to produce a valid input after days. After I disabled Hashmap randomization, fuzzing even found a crash in a few hours. > > \## Ways to solve this > > My solution: edit the standard library. Cross-platform, but not easy to package. > > LLVM solution: do not instrument hash maps. It is unclear to me how to do this because \[the instructions\](https://github.com/AFLplusplus/AFLplusplus/blob/stable/instrumentation/README.instrument\_list.md) are C++ specific. > > Linux solution: define your own \`getrandom\` function. > > I also recommend AFL++ first, because it tracks whether the same input produces the same trace and warns about it. > > For a more wordy explanation, see this post: https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234 ---
**Author:** ![joonazan](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/joonazan/32/11115_2.png) [@joonazan](https://internals.rust-lang.org/u/joonazan)\ **Post date:** [July 31, 2023, 12:26am UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/5 "2023-07-31T00:26:07Z")
@bascule That is very good to know! So instead of a fixed seed, a pseudorandom seed should be used for deterministic results; especially when benchmarking. ---
**Author:** ![jdahlstrom](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jdahlstrom/32/3351_2.png) [@jdahlstrom](https://internals.rust-lang.org/u/jdahlstrom)\ **Post date:** [July 31, 2023, 6:07pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/6 "2023-07-31T18:07:25Z")
By the way, the use of an OS entropy source is AFAIK the only reason `Hash(Map|Set)` are not in `alloc`. It would be awesome if whatever mechanism used to turn off nondeterminism would also enable non-`std` use. Conversely, it would be pretty frustrating if there were a mechanism to make the two collections entirely OS-agnostic but they still weren't available in `alloc`. ---
**Author:** ![bjorn3](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bjorn3/32/2736_2.png) [@bjorn3](https://internals.rust-lang.org/u/bjorn3)\ **Post date:** [July 31, 2023, 6:51pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/7 "2023-07-31T18:51:30Z")
I think having two mutually exclusive features (liballoc HashMap and HashDOS protected HashMap) in the standard library would be pretty bad. Some libraries will depend on one feature and others on the other feature, splitting the ecosystem. ---
**Author:** ![jdahlstrom](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jdahlstrom/32/3351_2.png) [@jdahlstrom](https://internals.rust-lang.org/u/jdahlstrom)\ **Post date:** [July 31, 2023, 7:22pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/8 "2023-07-31T19:22:21Z")
In fact the only reason `HashMap` is in `std` is the default generic parameter: ```rust pub struct HashMap ^^^^^^^^^^^ ``` Indeed the culprit is a single call in `RandomState::new`: ```rust sys::hashmap_random_keys() ``` Instantiating `HashMap` with any `alloc`-compatible hasher makes it itself `alloc`-compatible, it's merely the existence of the default parameter that binds it in `std`. This is not an optimal situation. The hasher is made to be swappable (and is, of course, commonly changed to some faster, deterministic version when DDOS is irrelevant) so I don't think it's a big problem that `no_std` compiled code uses a different instantiation than `std`. * * * One way to switch off nondeterminism in the current language is to simply use a type alias, something like: ```rust #[cfg(not(test))] type HashMap = std::collections::HashMap; #[cfg(test)] type HashMap = std::collections::HashMap; ``` ---
**Author:** ![bjorn3](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/bjorn3/32/2736_2.png) [@bjorn3](https://internals.rust-lang.org/u/bjorn3)\ **Post date:** [July 31, 2023, 8:07pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/9 "2023-07-31T20:07:36Z")
You can't implement `HashMap::new` in libstd if HashMap is in liballoc, but it needs to be for HashMap::new to create a new RandomState as hasher. Making it generic over the hasher will break type inference for basically all code using HashMap::new. ---
**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\ **Post date:** [July 31, 2023, 9:17pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/10 "2023-07-31T21:17:31Z")
> [@bjorn3](#): > > You can't implement `HashMap::new` in libstd if HashMap is in liballoc, [...] While this is true in the strict sense, - changing the bound from `S = RandomState` to `S: Default` would be considered a minor breaking change (though of high impact, likely requiring [defaults to affect inference](https://faultlore.com/blah/defaults-affect-inference/) in order to be accepted); - std (and alloc/core) has access to the perma-unstable rustc-specific internal hack to bypass this (`#[rustc_allow_incoherent_impl]`) which is already used elsewhere in order to pretend to be a single coherence unit, and which _could_ be used to provide `alloc::collections::HashMap::<_, _, RandomState>::new` from std; - (primarily used for inherent impls on primitives) - (but is also used for alloc impls on non-primitive core types, e.g. `CStr::to_string_lossy`) - (but I did not find one in std not on a primitive type) - there's hope towards eventually extending this style of coherent "friend" crates beyond its private use for core/alloc/std; and - there's hope towards eventually collapsing the std facade into one (logical) crate (moreso than the current status) via features and the mythical "portability lint." In short: yes, but hopefully eventually no. ---
**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\ **Post date:** [August 1, 2023, 7:10am UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/11 "2023-08-01T07:10:15Z")
If I remember well `#[rustc_allow_incoherent_impl]` doesn't support trait implementations, and there's an `impl` of `FromIterator` for `HashMap` which would still be a blocker for `HashMap` in `alloc`. Also, `std` implements `HashMap` by delegating to `hashbrown`, which depends on `alloc`, so moving `HashMap` to `alloc` would create a cyclic dependency (which I guess could be fixed by copy-pasting `hashbrown` in `alloc`?) ---
**Author:** ![afetisov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/afetisov/32/8508_2.png) [@afetisov](https://internals.rust-lang.org/u/afetisov)\ **Post date:** [August 1, 2023, 1:01pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/12 "2023-08-01T13:01:01Z")
This would be an awesome change. I had a nasty surprise with HashMap while developing for a certain embedded environment. While in general it has `std`, the getrandom call specifically is not supported, and caused the device to hang. It took a lot of trial and error to find the issue, particularly since HashMap::new just doesn't look like something capable of nasty surprises, and RandomState isn't something one even thinks about 99,99% of the time. Imho it's one of the cases where rand not being part of std bites people. Ideally HashMap should have explicitly taken an RNG for the RandomState generation, and the current HashMap::new would be a common convenience method which passes the system RNG. ---
**Author:** ![mjbshaw](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/mjbshaw/32/5103_2.png) [@mjbshaw](https://internals.rust-lang.org/u/mjbshaw)\ **Post date:** [August 3, 2023, 4:45pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/13 "2023-08-03T16:45:20Z")
> [@afetisov](#): > > the current HashMap::new would be a common convenience method which passes the system RNG. I think it would be nice if I could fuzz code without requiring the code to manually pass a fuzzing-friendly RNG. One option would be to use `#[cfg(fuzzing)]` in std (to turn determinism on), though this would require shipping a separate std binary built just for fuzzing. And I don't know if afl.rs builds with `#[cfg(fuzzing)]`. Another option would be to have some global function that returns whether or not determinism should be used. When building for fuzzing rustc could link against a definition that returns `true` (i.e. deterministic behavior), and when building for normal non-fuzzing purposes it could link against a definition that returns `false` (i.e. nondeterministic behavior). This shouldn't require rebuilding std or shipping two separate std binaries. And if built with LTO then LLVM should be able to inline the definition and trim the dead code. ---
**Author:** ![newpavlov](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/newpavlov/32/3290_2.png) [@newpavlov](https://internals.rust-lang.org/u/newpavlov)\ **Post date:** [August 3, 2023, 5:49pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/15 "2023-08-03T17:49:16Z")
There is a [vague proposal](https://github.com/rust-random/getrandom/issues/21) to integrate `getrandom` into `std` and allow to overwrite its implementation similarly to `alloc`. It would allow to move `HashMap` into `alloc` (probably, behind a feature flag?) and would make it possible to use PRNG with fixed seed as a `getrandom` impl for fuzzing and testing. It's not enough for full reproducibility with multi-threaded code (program results may differ depending on whether thread A or B got to call `getrandom` first), but since `HashMap` cashes random seed after first initialization and then simply increments it, it will not be a big issue if you do the first initialization before spawning threads. ---
**Author:** ![joonazan](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/joonazan/32/11115_2.png) [@joonazan](https://internals.rust-lang.org/u/joonazan)\ **Post date:** [October 23, 2023, 4:21pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/16 "2023-10-23T16:21:10Z")
Overriding getrandom on Linux actually isn't as good as modifying the standard library. It does make each run of a program deterministic but fuzzers want to run multiple experiments in a single program to reduce process spawning overhead. They would need some way to reset the global rng, which sounds like a difficult thing to implement. Big programs where it is difficult to change every instance of Hashmap will probably be so slow that the classic method of forking the process is fast enough, though. ---
**Author:** ![the8472](https://avatars.discourse-cdn.com/v4/letter/t/0ea827/32.png) [@the8472](https://internals.rust-lang.org/u/the8472)\ **Post date:** [October 23, 2023, 6:07pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/17 "2023-10-23T18:07:03Z")
maybe they could do some library loading shenanigans to get separate instances of the standard library and the function-to-fuzz? ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [January 21, 2024, 6:07pm UTC](https://internals.rust-lang.org/t/support-turning-off-hashmap-randomness/19234/18 "2024-01-21T18:07:22Z")
Closed on January 21, 2024, 6:07pm UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.