5 ms·

This seems like a very bad idea to me. It's highly ingrained in my mind that rand() provides a deterministic sequence, and I use deterministic psudorandom sequ

This seems like a very bad idea to me. It's highly ingrained in my mind that rand() provides a deterministic sequence, and I use deterministic psudorandom sequences all the time. If you are changing this just in OpenBSD isn't that going to be a portability nightmare? I would find this behaviour in OpenBSD extremely surprising. I'm very sceptical of the concept that developers expect true randomness out of rand(). Unless the way people are taught this stuff has changed drastically, the very concept of randomness in computing was always introduced right alongside the idea that they don't produce true randomness. Infact, the need to call srand() or get the same sequence every time can't help but teach you the fact that it's a deterministic sequence.

tedunangst 12y ago
If people wanted deterministic sequences, they wouldn't be calling srand(time(NULL)). Or srand((time(NULL) + buf_len) ^ rand()). Or, my personal favorite, srand(getpid() * time(NULL) % ((unsigned int) -1)). Though I will admit it is very difficult for me to properly imagine what that developer was expecting.
- to3m 12y ago
  I imagine they wanted a different set of numbers each time, and didn't really care what they were, provided the sequence was vaguely unpredictable. On the face of it this doesn't sound to me like a great reason for breaking standardized behaviour - but you know what they say about people who comment from the sidelines.
- bmm6o 12y ago
  I tend to agree. The determinism of random() is a feature, but it's a feature that almost nobody actually needs. It's just that the alternatives are either more trouble than they're worth or platform-dependent.
  - kevin_thibedeau 12y ago
    I use the determinism with test cases generating random input data. Every run of a test case generates a random seed based off the system time and reports the seed used. When a failure happens, the seed is fixed using an environment variable. Then the failed case can be reproduced until the bug is tracked down. This isn't an unusual practice. The determinism in standard PRNG functions is an important feature not a weakness. Theo is being foolish. If he's unhappy with the way the *rand functions are being used he should just change the code calling into the library to use random seeds derived from a suitable entropy source, not change the library itself.
    - bmm6o 12y ago
      > This isn't an unusual practice. I would even say it's common within programs that generate random sets, but that those use cases make up a tiny minority of all the uses of rand(), and it shouldn't be difficult to determine them from context.
  - fryguy 12y ago
    Why are things like Mersenne Twister or linear congruential generators platform dependent? To me, there are three classes of reasons you would need random numbers: 1. Simulation. Things like Monte Carlo. In this case, only the statistical quality of the numbers matters. 2. Repeatable simulation. Things like fuzzing tests or benchmarks, where you want them to be repeatable. In this case, you care about determinism and the statistical quality of the numbers. 3. Resource allocation. In this case, you have a set of things that you want to be unique, but to either make them unpredictable (process numbers, invoice numbers) or unique without sharing state (guids). You care about the statistical quality and unpredictability here. The problem is that 2 and 3 are at odds with each other. 3 requires a constant source of entropy, and 2 requires there to be no entropy. I think the following slides are relevant: http://www.openbsd.org/papers/hackfest2014-arc4random/mgp00001.html http://www.openbsd.org/papers/hackfest2014-arc4random/mgp000...
    - nitrogen 12y ago
      I would add a #4: cryptography. You don't need to add entropy for #3. If a CSPRNG with n bits of initial entropy as a seed can satisfy #4, then it's also good enough for #3.
      - fryguy 12y ago
        My understanding is that the way cryptography is done is by having hardware entropy source in the CPU fed into some sort of hashing algorithm. Having a CSPRNG with only n bits of initial entropy either exposes the problem of if an attacker can somehow get the state of the CSPRNG, then they can predict future random numbers that are generated (and previous ones, depending on implementation). Constantly reseeding with entropy means that it's not possible to do that.
    - bmm6o 12y ago
      I meant that "true" random numbers are platform dependent.
  - needs 12y ago
    It's in fact half of a feature, because the generation method is not specified. So you can't use it for terrain generation in portable code, for example.
- Negitivefrags 12y ago
  I'm not going to argue that rand() isn't misused by programmers who don't know any better, but at the same time you have legions of coders who understand rand() very well and those expectations will be totally broken here. I wouldn't have even bothered to check the the man pages for rand before assuming it was deterministic for a given seed to srand().
  - deleted 12y ago
    [deleted]
dezgeg 12y ago
It's already not a terribly good idea to use rand() for deterministic pseudorandom numbers, as the generated sequence isn't portable between systems.
- bmm6o 12y ago
  The use cases are more about being able to repeat a run on a given system - a particular simulation or a unit test that triggered an error (e.g. a sequence of values in a hash table). I could probably come up with a story where I'd want rand to be portable across systems, but it wouldn't be plausible.
  - deleted 12y ago
    [deleted]
  - mikeash 12y ago
    For a relatively common example of where you want portable pseudo-randomness, many games generate "random" worlds with a known PRNG algorithm and expose the seeds to the player. Players can then share interesting worlds with other players by simply sharing the seed. They can also generate "personalized" worlds by using their name or other meaningful text as the seed. Of course, it's completely reasonable to expect such games to bring their own PRNG implementation for that.
    - clarry 12y ago
      > Of course, it's completely reasonable to expect such games to bring their own PRNG implementation for that. Indeed. I was going to point out that rand() and random() might be horrible options even if you want a deterministic, repeatable stream of random numbers. I am pretty sure celeron55 initially tried using these functions in world generation for minetest, and seeing the rng's output as cubes in a 3D image made it hilariously clear how predictable and patterned the output is.
- duskwuff 12y ago
  The sequence isn't necessarily even portable within a system, as the libraries used by your application may themselves call rand() in unpredictable ways. For instance, consider a DNS resolver that generates query IDs using rand(). If the resolver library generates a new ID for retransmitted queries (e.g, when a packet is dropped), any DNS resolution may desynchronize the state of the random number generator. And, just as if that weren't bad enough, consider multithreading. The order in which threads execute is unpredictable, so, if more than one thread calling rand() is executing at once, the state of the RNG may become dependent on the order threads run in. Long story short, setting a global RNG to a known state isn't a sufficient way to make a program deterministic.

tedunangst 12y ago

If people wanted deterministic sequences, they wouldn't be calling srand(time(NULL)). Or srand((time(NULL) + buf_len) ^ rand()). Or, my personal favorite, srand(getpid() * time(NULL) % ((unsigned int) -1)). Though I will admit it is very difficult for me to properly imagine what that developer was expecting.

to3m 12y ago
I imagine they wanted a different set of numbers each time, and didn't really care what they were, provided the sequence was vaguely unpredictable. On the face of it this doesn't sound to me like a great reason for breaking standardized behaviour - but you know what they say about people who comment from the sidelines.
bmm6o 12y ago
I tend to agree. The determinism of random() is a feature, but it's a feature that almost nobody actually needs. It's just that the alternatives are either more trouble than they're worth or platform-dependent.
- kevin_thibedeau 12y ago
  I use the determinism with test cases generating random input data. Every run of a test case generates a random seed based off the system time and reports the seed used. When a failure happens, the seed is fixed using an environment variable. Then the failed case can be reproduced until the bug is tracked down. This isn't an unusual practice. The determinism in standard PRNG functions is an important feature not a weakness. Theo is being foolish. If he's unhappy with the way the *rand functions are being used he should just change the code calling into the library to use random seeds derived from a suitable entropy source, not change the library itself.
  - bmm6o 12y ago
    > This isn't an unusual practice. I would even say it's common within programs that generate random sets, but that those use cases make up a tiny minority of all the uses of rand(), and it shouldn't be difficult to determine them from context.
- fryguy 12y ago
  Why are things like Mersenne Twister or linear congruential generators platform dependent? To me, there are three classes of reasons you would need random numbers: 1. Simulation. Things like Monte Carlo. In this case, only the statistical quality of the numbers matters. 2. Repeatable simulation. Things like fuzzing tests or benchmarks, where you want them to be repeatable. In this case, you care about determinism and the statistical quality of the numbers. 3. Resource allocation. In this case, you have a set of things that you want to be unique, but to either make them unpredictable (process numbers, invoice numbers) or unique without sharing state (guids). You care about the statistical quality and unpredictability here. The problem is that 2 and 3 are at odds with each other. 3 requires a constant source of entropy, and 2 requires there to be no entropy. I think the following slides are relevant: http://www.openbsd.org/papers/hackfest2014-arc4random/mgp00001.html http://www.openbsd.org/papers/hackfest2014-arc4random/mgp000...
  - nitrogen 12y ago
    I would add a #4: cryptography. You don't need to add entropy for #3. If a CSPRNG with n bits of initial entropy as a seed can satisfy #4, then it's also good enough for #3.
    - fryguy 12y ago
      My understanding is that the way cryptography is done is by having hardware entropy source in the CPU fed into some sort of hashing algorithm. Having a CSPRNG with only n bits of initial entropy either exposes the problem of if an attacker can somehow get the state of the CSPRNG, then they can predict future random numbers that are generated (and previous ones, depending on implementation). Constantly reseeding with entropy means that it's not possible to do that.
  - bmm6o 12y ago
    I meant that "true" random numbers are platform dependent.
- needs 12y ago
  It's in fact half of a feature, because the generation method is not specified. So you can't use it for terrain generation in portable code, for example.
Negitivefrags 12y ago
I'm not going to argue that rand() isn't misused by programmers who don't know any better, but at the same time you have legions of coders who understand rand() very well and those expectations will be totally broken here. I wouldn't have even bothered to check the the man pages for rand before assuming it was deterministic for a given seed to srand().
- deleted 12y ago
  [deleted]

dezgeg 12y ago

It's already not a terribly good idea to use rand() for deterministic pseudorandom numbers, as the generated sequence isn't portable between systems.

bmm6o 12y ago
The use cases are more about being able to repeat a run on a given system - a particular simulation or a unit test that triggered an error (e.g. a sequence of values in a hash table). I could probably come up with a story where I'd want rand to be portable across systems, but it wouldn't be plausible.
- deleted 12y ago
  [deleted]
- mikeash 12y ago
  For a relatively common example of where you want portable pseudo-randomness, many games generate "random" worlds with a known PRNG algorithm and expose the seeds to the player. Players can then share interesting worlds with other players by simply sharing the seed. They can also generate "personalized" worlds by using their name or other meaningful text as the seed. Of course, it's completely reasonable to expect such games to bring their own PRNG implementation for that.
  - clarry 12y ago
    > Of course, it's completely reasonable to expect such games to bring their own PRNG implementation for that. Indeed. I was going to point out that rand() and random() might be horrible options even if you want a deterministic, repeatable stream of random numbers. I am pretty sure celeron55 initially tried using these functions in world generation for minetest, and seeing the rng's output as cubes in a 3D image made it hilariously clear how predictable and patterned the output is.
duskwuff 12y ago
The sequence isn't necessarily even portable within a system, as the libraries used by your application may themselves call rand() in unpredictable ways. For instance, consider a DNS resolver that generates query IDs using rand(). If the resolver library generates a new ID for retransmitted queries (e.g, when a packet is dropped), any DNS resolution may desynchronize the state of the random number generator. And, just as if that weren't bad enough, consider multithreading. The order in which threads execute is unpredictable, so, if more than one thread calling rand() is executing at once, the state of the RNG may become dependent on the order threads run in. Long story short, setting a global RNG to a known state isn't a sufficient way to make a program deterministic.