Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement PartialEq/Eq on PRNG Generators where possible #964

Closed
rickvanprim opened this issue Apr 10, 2020 · 8 comments
Closed

Implement PartialEq/Eq on PRNG Generators where possible #964

rickvanprim opened this issue Apr 10, 2020 · 8 comments

Comments

@rickvanprim
Copy link

It would be nice if the various PRNG Generators implemented PartialEq/Eq (where possible) so that it's possible to validate determinism in a simulation.

Example

let rng = SomePrng::new();
let mut initial_state = State::new(rng);
let mut determinism_check_state = initial_state.clone();
simulate(&mut initial_state);
simulate(&mut determinism_check_state);
assert_eq!(&initial_state, &determinism_check_state);

Currently this has to be worked around by introducing a wrapper type that inappropriately peers into the implementation details of the PRNG Generator to do a memory compare.

@dhardy
Copy link
Member

dhardy commented Apr 10, 2020

This sounds perfectly reasonable to me, even for crypto PRNGs (as you say, it's possible to read the state anyway if one really wants to).

First thing would be to apply this to the rngs repo and rng crates in this repo, along with minor version bumps and changelogs (see contributor guide).

Finally, we can update the rand crate's StdRng and SmallRng.

PRs are welcome. (Sorry for not offering to do this myself, but I am a voluntary maintainer and already put quite a bit of time into reviews, communication, etc.)

@burdges
Copy link
Contributor

burdges commented May 4, 2020

Seems fine. I'm curious however:

Can you give more context for "validate determinism"? It's not for tests? You want to establish some property of simulate? Or..

You want basically assert_eq!(&rng, &rng.clone()); for a user supplied rng this? At present, rust crates most request trait compatibility in their documentation text, based upon the Hash+Eq examples from HashMap, all fancy Deref tricks, etc. We could add compatibility traits like pub trait HashAndEq : Hash+Eq {} but this seems excessive.

It'd be cool if rust supported #[test] methods for instantiations and/or traits that somehow ran with relevant user supplied types.

impl<K, V> HashMap<K, V, RandomState> where
    K: Eq + Hash + Arbitrary,
{
    #[test]
    fn eq_v_hash() {
        ...
    }
}

Anyways..

We do technically encourage one bit leaks about the internal state by doing this, but it appears fine since real exploits seem unlikely. :) I'd think R: Hash would pose more risk because some H: Hasher leak more and seem more exposed.

In this vein, there are increasingly impls that seem both essential and dangerous, with the canonical example being HashMap: Clone, but also RngCore+Clone. I've suggested lints against HashMap: Clone elsewhere, but you could imagine fancier tricks like CryptoRng+Clone and CryptoRng+PartialEq evoke lints when used together outside tests.

@dhardy
Copy link
Member

dhardy commented May 4, 2020

Interesting idea about supporting Hash (checksums are useful, but this is a potential data leak). I believe the default hasher is derived from SipHash but with reduced numbers of rounds, since this configuration is still unbroken and in any case it is not intended for security-related usage (other than preventing DoS attacks). Because of this, I agree that CryptoRng+Hash could be a concern.

I disagree about the proposed CryptoRng+PartialEq lint however. It doesn't facilitate any attack other than brute-force, and unsafe memory reads are already possible.

@burdges
Copy link
Contributor

burdges commented May 4, 2020

I agree CryptoRng+PartialEq seems harmless. We've no mechanism or precedent for such lints today, but they'd make more cases harmless, like HashMap: Cone. I actually wanted some trait incompatibility example when I wrote that, since Hash+Eq and RngCore+Clone resemble tests more than lints:

    #[cfg(not(test))]
    #[inline(always)]
    fn assert_clone_rng_compatability<R: RngCore+Clone>(_r: &mut R) { }

    #[cfg(test)] {
    fn assert_clone_rng_compatability<R: RngCore+Clone>(r: &mut R) {
        let mut x = [0u8; 32];
        r.clone().fill_bytes(&mut x);
        for _ in 0..(x.next_u32() as usize) {
            let mut y = [0u8; 32];
            r.clone().fill_bytes(&mut y);
            assert_eq!(x,y);
        }
    }

@rickvanprim
Copy link
Author

rickvanprim commented May 4, 2020

@burdges my current use case is essentially what the pseudo code at the top is. To ensure that I haven't broken determinism, I run each simulation step twice and assert that the newly produced states are identical. This necessitates that the PRNGs are stored as part of the state, which in turn means they need to be comparable.

@dhardy
Copy link
Member

dhardy commented May 29, 2020

I think we can close this now?

@vks
Copy link
Collaborator

vks commented Jul 13, 2020

It's implemented for StdRng and SmallRng, but not yet for the other RNGs (rust-random/rngs#6 is still open).

@vks
Copy link
Collaborator

vks commented Jul 15, 2020

Fixed by rust-random/rngs#7. PartialEq and Eq was not implemented for IsaacRng and Isaac64Rng, but they are deprecated anyway.

@vks vks closed this as completed Jul 15, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants