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

math/rand: seed global generator randomly #54880

Closed
rsc opened this issue Sep 6, 2022 · 59 comments
Closed

math/rand: seed global generator randomly #54880

rsc opened this issue Sep 6, 2022 · 59 comments

Comments

@rsc
Copy link
Contributor

rsc commented Sep 6, 2022

As a step toward a larger overhaul of math/rand (for example, #21835 or #26263), @robpike and I propose that math/rand seed the global generator randomly and deprecating Seed, rather than behaving as if Seed(1) had been called. A more aggressive step (which we are not proposing at the moment) would be to make the global Seed function a no-op.

Seeding the global generator randomly at startup eliminates the possibility of programs that don't call Seed depending on the algorithm behind the global functions. If the package randomly seeded the global generator, that would let us change the global generator's source algorithm as an implementation detail: nothing could tell that the algorithm was different.

Auto-seeding would also fix any programs that are missing calls to Seed and think they are getting non-deterministic values but are not. (This is a common mistake.)

Auto-seeding would break programs that have no calls to Seed and expect a deterministic sequence. The most common time this might happen would be in golden tests.

There are lots of other possible changes that could be made to math/rand, and we are intentionally leaving them all to the side for the purposes of this proposal. This proposal is only about auto-seeding, precisely because it targets the most common backwards compatibility concern that comes up in any other changes to math/rand. Addressing that one concern in isolation greatly simplifies any other changes we might make later.

I hope that this proposal discussion can focus on the impact of making this change, specifically programs that would break that we need to be concerned about. If it turns out that we can't make this change, then maybe we will propose a math/rand/v2 instead. But we'd like to understand whether it can be done in the original math/rand first.

Again please limit comments to the impact of auto-seeding and not on other possible changes to math/rand. Thank you!

@rsc rsc added this to the Proposal milestone Sep 6, 2022
@dominikh
Copy link
Member

dominikh commented Sep 6, 2022

While I am sympathetic to the idea, I believe this would be a violation of the backwards compatibility guarantee in a very direct manner. The package documentation clearly states that

Top-level functions, such as Float64 and Int, use a default shared Source that produces a deterministic sequence of values each time a program is run. Use the Seed function to initialize the default Source if different behavior is required for each run.

That is, the fact that the global RNG is deterministic isn't an implicit detail that people may be relying on; it's documented fact.

I don't believe that the downsides of accidentally using an unseeded RNG outweigh the cost of breaking compatibility, especially because this can't be considered a bug fix nor a security fix.

@zhangyunhao116
Copy link
Contributor

I guess the final implementation may be similar to https://github.com/zhangyunhao116/fastrand ? The internal implementation of this library has been widely used in my company, and we have proposed similar ideas internally, but we have not implemented it yet(replace math/rand with this library).

According to our experience, this change will not bring any negative effects in most cases(maybe ~99%?). In rare cases, this may break some services or tests(e.g., call Seed(1) and then generate a random slice, use it as a test case or send it to other places).

But I think it's not worthing to break the compatibility for golang/go, as @dominikh said before. I think math/rand/v2 or math/fastrand is better.

@robpike
Copy link
Contributor

robpike commented Sep 6, 2022

It's a bit of a stretch, but it can be argued that this is in fact a security issue. Programs that don't seed their random numbers will behave predictably, which can sometimes be a risk if the numbers are used to generate unique, supposedly unguessable results.

It was a design error, copied from Unix, to have rand be reproducible like this. It should be changed. The question is whether it can be changed without a version bump on the library.

@atdiar

This comment was marked as off-topic.

@kortschak
Copy link
Contributor

Programs that don't seed their random numbers will behave predictably, which can sometimes be a risk if the numbers are used to generate unique, supposedly unguessable results.

I'd say that if people are using math/rand [out of the box] for security-sensitive uses there are other problems.

@dallbee
Copy link

dallbee commented Sep 6, 2022

Go1 compatibility promise aside (and I do think this would be a compatibility break),

Seeding math/rand doesn't make it any less predictable. Instead, it just becomes easier to use as a footgun in security crtical contexts.

Today, it's common for junior devs to ask me why math/rand produces the same values every time they use it. This is a great learning point - they become aware of the difference between a PRNG and a CSPRNG.

Autoseeding would make it easy to think math/rand is suitable for all uses.

@seebs
Copy link
Contributor

seebs commented Sep 6, 2022

This would definitely break some existing programs, even if those programs are bad. I think, though, dallbee's point is the one I'm most concerned by. I am worried about anything that makes it easier for people to accidentally get apparently-not-horrible behavior from the default rand, without actually getting good enough behavior that it's reasonably safe. I'd rather have the behavior be sufficiently clearly bad that people are encouraged to change it.

@srowles
Copy link

srowles commented Sep 6, 2022

It's just an anecdote, but I tinker with procedural content generation toys from time to time, these are often UI based or 1-shot programs that provide an output. I often use the global random in those pieces of code and I initialise the seed based on some input.

Default seeding the global generator would not break my code, but making the global Seed() call a no-op would definitely break the code today I have today.

I also agree with the other comments that this should not be changed as it breaks documented behaviour (https://pkg.go.dev/math/rand#Seed)

I don't see that it's a security issue because nobody should be using math/rand for security related random and in fact the doc's for math/rand even explicitly cover this:

"For random numbers suitable for security-sensitive work, see the crypto/rand package."

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

Re security:

There's no positive security argument here. Code that needs true randomness should use crypto/rand.

But there's also no negative security argument here. People accidentally reaching for math/rand when they mean crypto/rand does not seem like justification for making math/rand as bad as possible.

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

Re general breakage and backwards compatibility:

@dominikh pointed out

Top-level functions, such as Float64 and Int, use a default shared Source that produces a deterministic sequence of values each time a program is run. Use the Seed function to initialize the default Source if different behavior is required for each run.

He reads that as a promise, but I read it as a warning (don't forget to call Seed).

Either way, using the global source and expecting a deterministic sequence is incredibly fragile. All it takes is one new import that happens to call Seed or Int (or any of the other getters) and your code breaks. Suppose instead of auto-seeding we made a change where some commonly used package (say, strings) called rand.Int a few times at init time. Is changing the number of times math/rand is called by a package's init function a breaking change for that package? That can't be right.

Auto-seeding is like you have a package linked into the binary that reads a non-deterministic amount of randomness from math/rand at init time.

To be clear, at the moment I am assuming that if you call global Seed(1) then determinism is restored. Programs that want determinism can and probably should ask for it explicitly.

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

Re specific breakage:

@zhangyunhao116 reported their experience:

According to our experience, this change will not bring any negative effects in most cases(maybe ~99%?). In rare cases, this may break some services or tests(e.g., call Seed(1) and then generate a random slice, use it as a test case or send it to other places).

In contrast, @seebs said:

This would definitely break some existing programs, even if those programs are bad.

I expect it would break some (again, latently fragile) golden tests. Those are annoying but easy to fix. What about non-tests? Can anyone think of a case where a non-test would break? That would concern me more.

@dr2chase
Copy link
Contributor

dr2chase commented Sep 6, 2022

Regarding security and warning new programmers of foot-guns, if that is a problem, the safer solution is to make the default RNG cryptographically secure, and when it shows up in profiles, then we have the discussion about whether this application needs the secure rand or not. Premature optimization, etc.

I favor this change. Current behavior is a foot-gun, adds to the learning curve for new Go programmers, adds one line of "don't forget" code to good programs, and it compromises security, where one of the rules (at least, my rules) for security is "you never know what's going to end up exposed to strangers on the internet".

I am less swayed by the need for compatibility here because the winning example is "tests". Those will break, they'll be easy to fix, it's unlikely that production code depends on this, and my actually-educated guess is that any such uses are unintentional and this change will fix (through removed security holes) more code than it breaks.

I am not sure what to do with Seed. Short-term, we'll need "Seed(1)" to fix any tests that this breaks, but then what's the plan for changing the RNG down the road, if that becomes necessary, or or if people are swayed by my
Great Idea in the first paragraph? Special case Seed(1) to select the old RNG?

@srowles
Copy link

srowles commented Sep 6, 2022

Regarding security and warning new programmers of foot-guns, if that is a problem, the safer solution is to make the default RNG cryptographically secure

Pseudo random has use-cases beyond security use cases, using it to produce "random" but deterministic output. This is useful for a wide range of scenarios.

Pseudo random shouldn't be removed from the core library just because some use cases are better with cryptographic random, not everything needs or wants real random behaviour or the overhead of secure random when pseudo is good enough.

@dallbee
Copy link

dallbee commented Sep 6, 2022

@rsc said:

Either way, using the global source and expecting a deterministic sequence is incredibly fragile...

Perhaps bordering on counter-proposal territory, but maybe having a global PRNG is the problem here?

Leave the behavior alone, deprecate it, put up big warning signs that users should initialize their own source. Expose LockedSource for convenience.

I think it's pretty valid that folks here are wanting a PRNG to produce a deterministic sequence. I also appreciate that the global source is fragile and can easily be misused.

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

Perhaps bordering on counter-proposal territory, but maybe having a global PRNG is the problem here?

Having a global deterministic PRNG is the problem. If it's not guaranteed to be deterministic, there are many possible paths forward.

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

I am not sure what to do with Seed. Short-term, we'll need "Seed(1)" to fix any tests that this breaks, but then what's the plan for changing the RNG down the road, if that becomes necessary

The plan is that Seed would do two things: (1) select the original algorithm as the global source and (2) seed it. Until Seed is called, you get the better algorithm.

@rsc
Copy link
Contributor Author

rsc commented Sep 6, 2022

I forgot to mention that if you want to try the change out, you can patch in https://go-review.googlesource.com/427963, or as a rough approximation you can put

func init() { rand.Seed(time.Now().UnixNano()) } 

in any package you like.

@josharian
Copy link
Contributor

Can anyone think of a case where a non-test would break?

I can imagine using math/rand to do deterministic-yet-random codegen for correctly-shaped random input data for a simulation. Broadly speaking, the line between tests and prod is looser in many contexts in which math/rand gets used.

But to be fair, I don’t know of any cases concretely.

@josharian
Copy link
Contributor

It’s also worth noting that this proposal is a bit of a surprise. There have been multiple discussions about de-global-lock-ing math/rand over many years, always with the apparent understanding that we couldn’t change the math/rand value stream. (I’m on my phone, but I believe this is documented in #26263, at least as of the time of that issue.) It might be helpful to share some context about why your thinking has evolved.

@beoran
Copy link

beoran commented Sep 7, 2022

First of all, a non cryptographical, seedable RNG like that of math/rand is useful not only for tests, but also for games , simulations, and scientific models. The sequence should be predictable in some use cases, so we definitely need the Seed function to stay functional.

I am not sure about the impact on backwards compatibility. The documentation does not exactly say what random series you are getting by default. Is it the same as after calling Seed(0)?

And I assume there was some serious security issue related to this that triggered this issue? It is documented well enough that we cannot use math/rand for secure random numbers, so I am more agreeing with those who say crypto/rand should have been used in stead.

If the issue is that too many people ignore this warning, then we can deprecate the whole package and move it to a new package a bit like ioutil.

@rsc
Copy link
Contributor Author

rsc commented Sep 7, 2022

In #21835, @robpike wrote on Sept 11 2017:

We propose to make this generator the default one in math/rand for Go 2. The Go 1 compatibility decree could allow it to happen today, but we have chosen in the past to take the guarantee more literally than is expressed by also requiring that the generated stream of bits will never change. This decision was made when a fix was done, but enough tests in production were discovered that depended on the exact stream that it was deemed simpler to lock down the implementation rather than to fix all the tests.

@josharian asked much more recently:

It’s also worth noting that this proposal is a bit of a surprise. There have been multiple discussions about de-global-lock-ing math/rand over many years, always with the apparent understanding that we couldn’t change the math/rand value stream. (I’m on my phone, but I believe this is documented in #26263, at least as of the time of that issue.) It might be helpful to share some context about why your thinking has evolved.

It came up because Rob and I were discussing math/rand as an example of a possible v2 package in the standard library (it is a good test case for v2 machinery precisely because it is so simple). We've meant to replace the generator for a long time, and if we do that it would be good to avoid making the same mistakes over again. But then we also got to talking about how much we can fix the current math/rand without a v2.

As Josh noted, the stumbling block for lots of possible API evolution has been the default Seed(1) behavior. So we thought it made sense to file a proposal focused on really understanding the true amount of flexibility we have for just that one detail, separate from any other API changes.

One thing that has changed since 2017 is we have five more years of experience with programmers use of math/rand. It does get used in many reasonable contexts, but what we see over and over is (1) programmers forgetting to Seed; (2) programmers seeding in their package "just in case"; (3) programs breaking when a program that did (1) but also imported a package that did (2) removes the import; and so on.

To be clear, the outcome is not a foregone conclusion here. But at the same time, I haven't seen compelling specifics of breakage yet either.

@rsc
Copy link
Contributor Author

rsc commented Sep 7, 2022

I meant to add that I don't have any records of which tests Rob was talking about in the 2017 comment, but I am rerunning all of Google's Go tests with an init-time auto-seeding change and will report what I find. If anyone else has large code bases and can do the same, more data is always good.

@rsc
Copy link
Contributor Author

rsc commented Sep 7, 2022

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@kortschak
Copy link
Contributor

While I'm not convince of the need of the change and I do find the comment above (#54880 (comment)) compelling from a pedagogical perspective, the autoseeding should not break any reasonable simulation as anyone doing a reasonable simulation would already have included an option to set the seed since a single run with a seed would not be strong enough for any conclusions of a simulation to be drawn. I'd also note that for any reasonable simulation code the author should probably be using their own local PRNG source rather than the package source to avoid locking costs, and the non-reproducibility that would come from sharing random sources between concurrent execution threads.

@beoran
Copy link

beoran commented Sep 8, 2022

Just an experiment that shows that now, not seeding the RNG and generating numbers exactly the same as generating numbers after seeding it with Seed(1). I do wonder why it is not Seed(0)?

https://go.dev/play/p/Qph7qlRbjUg

Anyway, randomly seeding the RNG alone doesn't seem like a big backwards compatibility problem, as the sequence was not specified, and we can always call Seed(1) to get the original sequence back.

@rsc
Copy link
Contributor Author

rsc commented Sep 8, 2022

I meant to add that I don't have any records of which tests Rob was talking about in the 2017 comment, but I am rerunning all of Google's Go tests with an init-time auto-seeding change and will report what I find. If anyone else has large code bases and can do the same, more data is always good.

I ran all of Google's Go tests with auto-seeding, and the failed test rate was about 2 per 10,000. The failures were all golden test failures, as one would expect.

@frioux
Copy link

frioux commented Sep 8, 2022

I just want to go on the record that this seems like a clear improvement, makes the generation of random numbers or picking a user at random or whatever much easier, and is welcome from me and mine.

@ianlancetaylor
Copy link
Contributor

Just to look at some other languages:

  • C: The POSIX rand function acts as though srand(1) is called at program startup. Similarly for the POSIX random function, which assumes srandom(1).
  • Java: math.Random returns random numbers with a randomly chosen seed ("sets the seed of the random number generator to a value very likely to be distinct from any other invocation").
  • Python: random.random uses the current system time as a default seed.
  • Rust: there are several random number generators. As far as I can tell you have to either provide a seed or you get a random one.

So Go copied C's seed behavior, but it seems that several other languages did not.

imup-bot added a commit to imup-io/client that referenced this issue Apr 1, 2023
# [0.10.0](v0.9.0...v0.10.0) (2023-04-01)

### Bug Fixes

* additional context for error messages ([5d5cc66](5d5cc66))
* rand.Seed deprecated as auto seeding is now the default golang/go#54880 ([f3127d0](f3127d0))
* use log not slog ([591fe0c](591fe0c))

### Features

* replace logrus with slog ([e67098f](e67098f))
ijsong added a commit to kakao/varlog that referenced this issue Apr 3, 2023
ijsong added a commit to kakao/varlog that referenced this issue Apr 5, 2023
aramprice added a commit to cloudfoundry/bosh-dns-release that referenced this issue Apr 6, 2023
- `rand.Seed()` has been deprecated for a while
- as of Golang 1.20 it is no longer necessary to call `rand.Seed()` (or
  similar)
  - See:golang/go#54880

This commit removes two structs which appear to have existed as carriers
for two slice-type specific implementations of `Shuffle()`.

It turns out that the `rand` package implements a `Shuffle()` method
(now/already/??) which can replace these two implementations.

By doing this replacement a number of tests needed to be updated to
handle non-deterministic output ("shuffled" collections are returned).
Previously these tests had relied on mocking the internal `Shuffle()`
functions. The tests now use the `ConsistOf()` matcher.
AlexanderYastrebov added a commit to zalando/skipper that referenced this issue Jul 2, 2023
Global random generator is automatically seeded since go1.20,
see https://go.dev/doc/go1.20#math/rand and golang/go#54880

This change uses global generator to seed random sources instead of time.Now().UnixNano().

Signed-off-by: Alexander Yastrebov <alexander.yastrebov@zalando.de>
romain-dartigues added a commit to orange-cloudfoundry/logs-service-broker that referenced this issue Sep 13, 2023
aruneshpa added a commit to aruneshpa/vm-operator that referenced this issue Sep 25, 2023
controller-runtime v15 has a min Golang version requirement that
breaks the container builds. This change bumps up the Go version used
to build the container. Starting 1.21 Golang, go.mod requires the Go
version and treats that as min required go version to compile your
binary. So, also bump up the Go version for local builds.

Additional changes:

- As per golang/go#56319
and golang/go#54880, global rand is
automatically, randomly seeded. So we don't need to call `Seed`
anymore.

- Package ioutil has been deprecated. Port the code to use replacement
methods.
aruneshpa added a commit to vmware-tanzu/vm-operator that referenced this issue Sep 25, 2023
controller-runtime v15 has a min Golang version requirement that
breaks the container builds. This change bumps up the Go version used
to build the container. Starting 1.21 Golang, go.mod requires the Go
version and treats that as min required go version to compile your
binary. So, also bump up the Go version for local builds.

Additional changes:

- As per golang/go#56319
and golang/go#54880, global rand is
automatically, randomly seeded. So we don't need to call `Seed`
anymore.

- Package ioutil has been deprecated. Port the code to use replacement
methods.
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which couldn't be used at the time because it can't be interfered with
from unrelated packages by means of calling rand.Seed, see #10575.
rand.Seed is deprecated since GO 1.20 and per the paragraph above the
global source is seeded by default. This makes it unlikely that packages
would interfere with the global PRNG state anymore and the top-level
math/rand functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
tklauser added a commit to cilium/cilium that referenced this issue Dec 8, 2023
Since Go 1.20 the top-level math/rand functions are auto-seeded by
default, see https://go.dev/doc/go1.20#library and
golang/go#54880. They also use the runtime's
lock-free fastrand64 function when 1. Seed has not been called and 2.
GODEBUG=randautoseed=0 is not used, see
golang/go#49892.

This allows to drop SafeRand and use the global source again. SafeRand
was originally introduced in commit fac5dde ("rand: add and use
concurrency-safe PRNG source") to fix #10988 by providing a
concurrency-safe PRNG source other than the global math/rand source
which could be used at the time because it can't be interfered with from
unrelated packages by means of calling rand.Seed, see #10575. rand.Seed
is deprecated since Go 1.20 and per the paragraph above the global
source is seeded by default. This makes it unlikely that packages would
interfere with the global PRNG state anymore and the top-level math/rand
functions are safe to use again.

Signed-off-by: Tobias Klauser <tobias@cilium.io>
@golang golang locked and limited conversation to collaborators Feb 3, 2024
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests