OpenBSD routes around POSIX

Posted Dec 11, 2014 2:02 UTC (Thu) by JoeBuck (subscriber, #2330)
Parent article: OpenBSD routes around POSIX

For uses of random numbers that are unrelated to cryptography, the ability to replay the sequence is an important feature. This is particularly true for simulation: if a bug is found from random simulation, fuzzing, or the like, you want to be able to find it again. If the seed is recorded the interesting traces can be replayed, and seeds can be produced using truly random processes to sample more of the simulation space.

Seems to me that it would be better to use a new API for applications that need truly random numbers rather than breaking portability on the old one.

OpenBSD routes around POSIX

Posted Dec 11, 2014 3:45 UTC (Thu) by mathstuf (subscriber, #69389) [Link]

I think that de Raadt probably sees the problem as serious enough to warrant the change. There are functions such as srand_deterministic and rand_deterministic already. But these have always been platform-specific anyways (so expecting Windows to give the same stream as Linux (or even glibc and musl) was already a lost cause for replays and such). de Raadt was also nice enough to come up with a list of projects which seem to actually expect the "deterministic" API, but that is of course limited to the OpenBSD ports selection.

OpenBSD routes around POSIX

Posted Dec 11, 2014 4:38 UTC (Thu) by jzbiciak (guest, #5246) [Link] (1 responses)

I actually use a deterministic random number generator in many of my programs, exactly for the purpose of reproducibility. But, I'm writing programs such as "random test generators" where a given input plus a given seed should produce the same test every time.

I also therefore use a dedicated random number class. (C++11 makes this very easy and very nice.) In fact, I use what I call "forked" random number generators, where a master generator (seeded by the test case seed) seeds child generators that I then hand to various subsystems. (Those children can be forked further for sub-subsystems, etc.)

The behavior of the whole tree depends on the original seed, but a tweak in behavior in one subsystem doesn't disturb the stream of pseudo-random numbers in another subsystem. This makes debugging and testing go much more smoothly.

All this to say: If you're writing simulation software that relies on the quality of the random numbers, reproducibility, and portability across multiple platforms, you likely abandoned the standard library rand()/random()/xrand48() a long time ago. You probably grabbed a copy of Mersenne Twister or any number of other, better generators and wrote your own wrappers around these things. I know I did eons ago. (And now with C++11's excellent random number library, I'm doing it with much less pain.)

I guess a part of me is a little surprised that 8800 packages showed up using rand() and friends. Then again, how many of them are actually negatively affected by bad random numbers?

OpenBSD routes around POSIX

Posted Dec 11, 2014 17:46 UTC (Thu) by alankila (guest, #47141) [Link]

Since you mention MT, I thought I'll add a bit here. My new geek hero, Melissa O'Neill, recently invented a new family of random number generators called PCG, where P stands for permuted. It's basically linear congruential generator combined to an output improving step, usually some variant of xor and shifting, but the consequence is a generator whose performance is near theoretical optimum, as it seems to pass statistical tests using fewest possible bits of state, e.g. mere 32 bits suffice to pass the SmallCrush test suite.

OpenBSD routes around POSIX

Posted Dec 11, 2014 5:44 UTC (Thu) by rsidd (subscriber, #2582) [Link]

Most people who do scientific simulations don't use the OS RNG functions -- they use, eg, the GSL versions (which support specifying a seed and replaying) or something else. Mainly, the OS-supplied versions are unreliable -- even if the OpenBSD version is excellent, the program needs to be portable.

OpenBSD routes around POSIX

Posted Dec 22, 2014 15:51 UTC (Mon) by mirabilos (subscriber, #84359) [Link] (1 responses)

If you want something that can be replayed, it’s not “random”. You list valid use cases, but I question that they can be use cases for an RNG. Sure, do it, but please don’t call it RNG, not even PRNG. Implementing an LFSR, LCG, etc. is dead easy.

Besides, POSIX doesn’t guarantee reproducibility between exec() anyway…

OpenBSD routes around POSIX

Posted Dec 22, 2014 16:33 UTC (Mon) by raven667 (subscriber, #5198) [Link]

I'm pretty sure that any PRNG given the same inputs will produce the same outputs and that is randomness that is suitable for crypto purposes. The randomness is introduced by seeding with something unpredictable and not knowing how far into the stream you have read not that the values produced will be unpredictable if you know the seed and how many bytes have been read.