Correlations of different DXSM streams with increments coresidual to MULTIPLIER-1

[thynson]

Michael made some exploits to the DXSM output scrambler.
See: https://guru.multimedia.cx/how-correlated-is-pcg-dxsm-output/

[thynson]

** UPDATE: The following code only fails PractRand when seed with 0, @michaelni provide an example that fail for abitrary seed.
Combining two correlated stream (with increments of 1 and MULTIPLIER respectively) interleaved

#include <stdint.h>
#include <stdio.h>
#include <time.h>

#define STATE_BITS 64
#define STATET uint64_t
#define OUTT uint32_t
#define MULTIPLIER 6364136223846793005ULL



static OUTT pcg_dxsm(STATET *state, STATET inc) {
    *state = *state * MULTIPLIER + inc;

    OUTT h = *state >>   STATE_BITS / 2;
    h     ^= h      >>   STATE_BITS / 4;
    h     *= MULTIPLIER;
    h     ^= h      >> 3*STATE_BITS / 8;
    return h * (*state | 1);
}


int main(int argc, char **argv) {

    uint32_t buff[4096];
    uint64_t seed = 0; // EDIT: It only fails PractRand quickly when seed with 0
    STATET state1 = seed;
    STATET state2 = seed;
    while (1) {
        for (int i = 0; i < 2048; i++) {
            buff[2 * i] = pcg_dxsm(&state1, 1);
            buff[2 * i + 1] = pcg_dxsm(&state2, MULTIPLIER );
        }

        fwrite(buff, sizeof(uint32_t), 4096, stdout);
    }
}

fails PractRand quickly

RNG_test using PractRand version 0.95
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 512 megabytes (2^29 bytes), time= 2.8 seconds
  Test Name                         Raw       Processed     Evaluation
  BCFN(2+0,13-1,T)                  R>+99999  p = 0           FAIL !!!!!!!!  
  BCFN(2+1,13-1,T)                  R>+99999  p = 0           FAIL !!!!!!!!  
  BCFN(2+2,13-2,T)                  R>+99999  p = 0           FAIL !!!!!!!!  
  BCFN(2+3,13-2,T)                  R=+14777  p =  4e-7552    FAIL !!!!!!!!  
  BCFN(2+4,13-3,T)                  R= +2007  p =  8.5e-950   FAIL !!!!!!!   
  BCFN(2+5,13-3,T)                  R=+256.8  p =  2.5e-121   FAIL !!!!!     
  BCFN(2+6,13-4,T)                  R= +31.1  p =  1.5e-13    FAIL           
  DC6-9x1Bytes-1                    R>+99999  p = 0           FAIL !!!!!!!!  
  Gap-16:A                          R>+99999  p = 0           FAIL !!!!!!!!  
  Gap-16:B                          R>+99999  p = 0           FAIL !!!!!!!!  
  FPF-14+6/16:(0,14-0)              R= +61.4  p =  2.0e-56    FAIL !!!!      
  FPF-14+6/16:(1,14-0)              R= +63.9  p =  9.0e-59    FAIL !!!!      
  FPF-14+6/16:(2,14-0)              R= +46.9  p =  4.7e-43    FAIL !!!       
  FPF-14+6/16:(3,14-0)              R= +40.7  p =  2.9e-37    FAIL !!!       
  FPF-14+6/16:(4,14-0)              R= +37.1  p =  5.4e-34    FAIL !!!       
  FPF-14+6/16:(5,14-1)              R= +27.5  p =  4.1e-24    FAIL !!        
  FPF-14+6/16:(6,14-2)              R= +16.3  p =  4.9e-14    FAIL           
  FPF-14+6/16:(7,14-2)              R= +15.3  p =  3.9e-13   VERY SUSPICIOUS 
  FPF-14+6/16:(8,14-3)              R= +14.2  p =  3.1e-12   VERY SUSPICIOUS 
  FPF-14+6/16:(9,14-4)              R=  +8.9  p =  3.3e-7   mildly suspicious
  FPF-14+6/16:all                   R=+117.9  p =  3.8e-110   FAIL !!!!!     
  BRank(12):256(4)                  R= +1339  p~=  7.1e-713   FAIL !!!!!!!   
  BRank(12):384(1)                  R= +1401  p~=  7.1e-423   FAIL !!!!!!!   
  BRank(12):512(2)                  R= +3017  p~=  3.3e-909   FAIL !!!!!!!   
  BRank(12):768(1)                  R= +3597  p~=  7e-1084    FAIL !!!!!!!!  
  BRank(12):1K(2)                   R= +7157  p~=  1e-2155    FAIL !!!!!!!!  
  BRank(12):1536(1)                 R= +7989  p~=  7e-2406    FAIL !!!!!!!!  
  BRank(12):2K(1)                   R=+10916  p~=  3e-3287    FAIL !!!!!!!!  
  mod3n(5):(1,9-6)                  R>+99999  p = 0           FAIL !!!!!!!!  
  mod3n(5):(2,9-6)                  R>+99999  p = 0           FAIL !!!!!!!!  
  ...and 199 test result(s) without anomalies

[michaelni]

uint32_t buff[4096];
uint64_t seed = time(NULL);
while (1) {

    STATET state1 = seed;
    STATET state2 = seed;

If you reset the seed inside the loop, it will generate the same 4096 entry block repeatedly, i assume that is unintended

[thynson]

If you reset the seed inside the loop, it will generate the same 4096 entry block repeatedly, i assume that is unintended

Good catch, I edited it a bit before pasting to here

[michaelni]

If you reset the seed inside the loop, it will generate the same 4096 entry block repeatedly, i assume that is unintended

Good catch, I edited it a bit before pasting to here

If you fix a bug in the code, you need to re-run the practrand test. The practrand failure likely was because of the bug.

To see a real correlation with identical seeds
one of many possibilities is this:

    STATET state1 = seed;
    STATET state2 = seed;
    STATET inc1   = 1          - seed * (MULTIPLIER - 1);
    STATET inc2   = MULTIPLIER - seed * (MULTIPLIER - 1);
    while(1) {
        for (int i = 0; i < 2048; i++) {
            buff[2 * i    ] = pcg_dxsm(&state1, inc1);
            buff[2 * i + 1] = pcg_dxsm(&state2, inc2);
        }

        fwrite(buff, sizeof(uint32_t), 4096, stdout);
    }

[thynson]

@michaelni is right. I first seed them with 0, and then it fails the PractRand badly. Later I edited the code a bit to seed them from a timestamp but made a mistake and result in it fails PractRand too, which is mistake.

[imneme]

No one who uses PCG in a sane way ever has to worry about these issues, as you need carefully contrived related seeds to show any issue, and if you're in the business of contriving carefully related seeding pairs, you can claim issues for pretty much all PRNGs (assuming you're allowed to set the complete PRNG state through seeding).

I recommend folks read this 2017 blog post of mine on the topic of PCG's streams. In that post I describe what's going on when you change the LCG additive constant, and how you can make LCG outputs that only differ by one bit if you contrive the constants just right.

(There's also the thread on the Numpy GitHub.)

Overall, all PRNGs exist in a space of trade offs. We could work harder to scramble the LCG output so that even if we have a pair of LCGs have outputs that only differ by just one bit, the final permuted output would still be radically different, but that scrambling costs CPU cycles. Since you only see an issue with carefully contrived related choices for the stream, it's not something that is worth trying to address with stronger scrambling.

One thing the PCG paper invites readers to do is design their own permutation functions. There's basically a cookbook showing you techniques you can apply and rules to follow (as it turns out before I ever wrote the PCG paper, Bob Jenkins provided similar advice, which boils down to the idea that mixing must be reversible). So if my permutations aren't strong enough for you, feel free to make your own. If you can permute more strongly and just as fast as the existing PCG permutations, feel free to share a pull request.

[michaelni]

First id like to clarify that i intended to report the issues i found in a somewhat more coherent way, but i didnt find the time yet. And someone who wanted to help opened this issue. This is not what or how i planed to report things ;)

No one who uses PCG in a sane way ever has to worry about these issues,

I think this statement is a little dangerous. Because "sane way" is not very well defined. But iam certainly interrested in how to initialize PCG-DXSM in a sane way if i want only non correlated streams?

I was told the seed needs to be the same, Now for each given fixed seed theres a wide range of differing increment pairs that show correlations.

as you need carefully contrived related seeds to show any issue, and if you're in the business of contriving carefully related seeding pairs, you can claim issues for pretty much all PRNGs (assuming you're allowed to set the complete PRNG state through seeding).

I recommend folks read this 2017 blog post of mine on the topic of PCG's streams. In that post I describe what's going on when you change the LCG additive constant, and how you can make LCG outputs that only differ by one bit if you contrive the constants just right.

Pairs that differ by one bit in the LCG output are a tiny subset of cases that show correlations

What i found concerning is that it seems not well understood how much of the space in PCG-DXSM are correlated streams. And thats what i tried to look into a bit, by looking at what kinds of correlations there are, and in that respect, i found it interresting every time i found a new class of correlations. I have not deeply looked into how much this is a practical issue with randomly selected seeds and increments. but it seems there are in excess of 2^64 correlated streams for each randomly picked stream in pcg64-dxsm. Which one can see as a lot or as little depending on point of view

Thanks

[imneme]

The right thing to do (for any PRNG, not just PCG) is use random entropy to initialize PRNG state (in PCG's case, that's current LCG-state value and LCG-increment). That's it, that's all. If you're not doing that, you're almost certainly doing it wrong, again for almost any PRNG.

For SplitMix, for example, (which is a permuted counter-based PRNG), if we just switch the stream (a.k.a. its increment or “gamma” as they call it) to the wrong (hand-chosen) value, we may end up with the same generator going backwards, or going forwards at half or double speed, which will obviously create correlations. The standard SplitMix implementation make such errors harder by usually using its own internal state to choose the stream when you split, but it's not hard to make it do the wrong thing if we put our minds to it.

So what's going on with PCG's streams is similar to some other generators of the past. As another example, you'd find similar correlations in Marsaglia's XorWow for different settings of the counter variable. XorWow is worse, because it doesn't do any permutation at all after adding in its counter.

In PCG's case, a way to think of the stream selected is that in effect we're choosing a different output permutation from the a base PRNG. Generally speaking, if you pick two output permutations at random, they'll look very different even when the underlying base PRNGs are as perfectly lined up as they can be, but if you are somehow weirdly unlucky, they might not be that different.

Likewise, for the underlying LCG sequence, your randomly-chosen starting points will likely be quite different from each other and not at all aligned. But it's possible you could be catastrophically unlucky and pick two nearby starting points and overlap.

But if you pick a random starting point and a random “stream”, you're you've made it even more unlikely that somehow choose wrong. And the other thing is that these streams are incredibly cheap, they cost almost nothing in terms of execution time—LCG or MCG we're talking about 1.25 ns per 64-bit random number (with an AMD Ryzen 9 7900X but pretty similar on current Apple CPUs) before doing anything clever like using vector instructions.

(I think this is all pretty well covered by that 2017 blog post.)

[michaelni]

The right thing to do (for any PRNG, not just PCG) is use random entropy to initialize PRNG state (in PCG's case, that's current LCG-state value and LCG-increment). That's it, that's all. If you're not doing that, you're almost certainly doing it wrong, again for almost any PRNG.

Ok, so if we randomly initialize a PRNG with 128+127 bits (that being seed and increment/stream selector) and draw lets say a billion values from it. How often can we do this before our set contains a correlated pair of streams ? With a ideal/perfect PRNG I think we would roughly need sqrt(2^(128-30) * 2^127) ~ 2^112 (simply the birthday paradox hitting overlapping sequences) for the 64bit output 128 bit state case and 2^48 for the 32bit output / 64bit state case. What can we expect to be able to draw out of a PCG-DXSM here before we see correlations? Iam asking this because its a more clear way to quantify the amount of correlations and because I have not seen this stated anywhere and ATM i have a feeling below what value these are but no proof. (I dont want to waste my time trying to proof correlations ocuring in a random set when thats already known/expected, OTOH if its not known thats a interesting exercise)

[imneme]

First, let's just think about how much compute that is in this best case. Let's assume 1ns per random number, that's (2^112 * 2^30) ns. And if you want to store all the results, it's (2^112 * 2^30 * 2^64) bits, if we use one atom of silicon per bit somehow, that's going to be about a million stellar masses worth to store them all.

Let's suppose that somehow PCG DXSM were only half that, with you only needing to collect 2^56 separate outputs. Now you just need to devote 2.5 billion years of compute to your problem, and your one-atom-per-bit computer is just going to need 600 quadrillion tons of silicon, if you can somehow manage 1 atom per bit. There's enough silicon in Earth's crust to do that, but obviously the number goes up if you need more than one atom. Then you're going to run your algorithm to hunt for the correlations. Let's hope it's somehow that's O(n).

But then we have another interesting question. If we've got that much storage and that much compute, what would happen if we took other PRNGs and looked for (possibly weak) correlations in their outputs. What would we find? As I recall, some evidence during the Numpy discussion showed that (some) LFSRs can also be correlated even when not exactly overlapping.

You also mention using DXSM for smaller-state PRNGs. But that would be a bit silly. When the main parts of your state fit in just one 64-bit register, it's much easier to usr RXSM. Part of the point of the 128-bit versions is to pick a permutation that is a bit weaker because it's good enough and cheaper.

Finally, let's switch gears, and imagine we have someone who uses some awesome PRNG, and decides to pass the output of time() to seed their PRNG (perhaps through std::seed_seq to fill out all the state). And let's suppose they run their code on everyone's smart phone. Or as another scenario, let's suppose a researcher plucks a “favorite” number out of their mind for the seed for their research. What does the distribution of those seeds look like compared to, say, all possible seedings? How often to these choices occur when people write software? How many times is everyone using the exact same numbers, even when they had a perfect PRNG. Or what if they just made a single call to std::random_device and seed with a 32-bit number?

[michaelni]

Let's suppose that somehow PCG DXSM were only half that, with you only needing to collect 2^56 separate outputs. Now you just need to devote 2.5 billion years of compute to your problem, and your one-atom-per-bit computer is just going to need 600 quadrillion tons of silicon, if you can somehow manage 1 atom per bit. There's enough silicon in Earth's crust to do that, but obviously the number goes up if you need more than one atom. Then you're going to run your algorithm to hunt for the correlations. Let's hope it's somehow that's O(n).

ultimately a pencil and a sheet of paper would do. What the goal is, is to find some bounds on the correlated sequences. And i think this is useful as this PRNG is used by default in a few places.
I think users should know if they should expect a correlated sequence in 2^112 or in 2^80 random picks. People are also listing the period of the PRNGs and not how much silicon it would need to store the whole period.

But then we have another interesting question. If we've got that much storage and that much compute, what would happen if we took other PRNGs and looked for (possibly weak) correlations in their outputs. What would we find? As I recall, some evidence during the Numpy discussion showed that (some) LFSRs can also be correlated even when not exactly overlapping.

Theres a large number of weak PRNGs and it takes effort to analyze each specific PRNG. (because my galaxy sized computer collapsed into a black hole so i cannot brute force compute these correlations)
For plain LFSRs theres obviously linear dependencies, like the mersene twister. Personally i use SFC64 nowadays for non security uses but i spend little time analyzing it. I only wrote some code to compute its state from its output

Finally, let's switch gears, and imagine we have someone who uses some awesome PRNG, and decides to pass the output of time() to seed their PRNG (perhaps through std::seed_seq to fill out all the state). And let's suppose they run their code on everyone's smart phone. Or as another scenario, let's suppose a researcher plucks a “favorite” number out of their mind for the seed for their research. What does the distribution of those seeds look like compared to, say, all possible seedings? How often to these choices occur when people write software? How many times is everyone using the exact same numbers, even when they had a perfect PRNG. Or what if they just made a single call to std::random_device and seed with a 32-bit number?

People do interesting things, my bank encrypted my data sent over email with my birthday as password for example. I tried telling them that all living people dont have a whole lot of different brithdays but they never replied.

[lemire]

I think users should know if they should expect a correlated sequence in 2^112 or in 2^80 random picks.

@imneme's point was that the exploit you found was not something that people had to worry about (No one who uses PCG in a sane way ever has to worry about these issues, as you need carefully contrived related seeds to show any issue, and if you're in the business of contriving carefully related seeding pairs, you can claim issues for pretty much all PRNGs).

I am curious: do you disagree with her point?

[michaelni]

@lemire, I have not opened this issue. What i intended, was to once i finish my investigation of the stream correlations to report it. It was just some reader of my blog who opened this issue (and iam certain he just wanted to help but it caused a bit of confusion, i think). The code posted here does not represent very well what i found btw

I was quite surprised by the amount of correlations in PCG-DXSM, and i do not believe that all PRNGs have such issues.
I mean i can pick 2 seeds at random and find many increments that result in correlated sequences. I can pick a seed and an increment and generate as many correlated seed,increment pairs as i could store. I can definitely not do that with some other PRNGs.

The thing people need to worry about, is if they generate seeds and increments in some non random way.

What i will do, is look more into this as my time permits and ill report things i find. Only after that, can i say if theres anything people need to worry about. This is "work in progress"

[lemire]

@michaelni That's a fair answer and I think you are saying "maybe it matters".

[imneme]

I think users should know if they should expect a correlated sequence in 2^112 or in 2^80 random picks

I think more insight into how things work is overall a good thing, and investigating these kinds of questions is interesting, or even fascinating. So I think it’s cool to see folks get interested in PRNGs and explore, and there are numerous rabbit holes to head down.

But if I were making a list of things typical PRNG users “should know”, that nuance would be be pretty far down the list. As I mentioned earlier, far higher on my list would be having them understand that a single 32-bit number is inadequate to seed any PRNG, as would understanding you can’t just use rng() % range. I’d also love to see more folks think about whether they’re doing the right thing when they try to generate a random float in the range [0,1).

One other thing is that while someone using the Frontier supercomputer possibly does need to think about potential issues when you draw more than 2^80 random numbers (since their machine might consume 2^60 numbers per second), most folks are never going to be in that situation, so it’d be a moot concern. Alas, that mootness might not be apparent—in my experience, people often don’t always come to sensible conclusions when given a possible issue to worry about.

To give some other examples, some folks are fearful of randomized algorithms because they worry that infinitesimal probabilities “might happen”. Told that there’s a 3.8 × 10^-66 chance that random-pivot quicksort might use more than 100 stack slots when sorting 1000 numbers”, some folks will say “oh, so there is a chance” when in practice this kind of probability equates to “don’t worry about it, it’ll never happen”.

Closer to home, I saw some fear-based thinking in your blog post where you wrote:

JSF64 is omitted because its minimal cycle length is unknown, and that's like using code that very likely will work instead of knowing it will work

I recommend you read the analysis of JSF in my blog post Random Invertible Mapping Statistics. In particular, I show there would only be a short cycle in jsf32 if a 281 trillion to one chance occurrence happened in the design of the generator (not each time you use it, a one-time chance when it was designed). For jsf64, if we assume you'll grab 2^64 numbers from each seed, the odds that he included a short cycle is 340 billion billion billion billion to one. I'm incredibly confident that Bob Jenkins wasn't that unlucky.

So to my eye, you rejected a perfectly good generator that has withstood some of the most targeted testing of any out there. (Fun fact, according to David Blackman, a fair amount of effort in PRNG testing was done just to try to “bust this little PRNG”.)

In short, often people can get obsessed with worrying about vanishingly unlikely things, while at the same time being blind to issues that might have real impact.

But stepping back, the high-order bit is that I’m pleased to see your work, and I look forward to seeing what you find. PCG has always been considered as a family with the idea that new family members can be added. If it turns out that some audiences want even stronger scrambling, we can see what we can come up with. We always know that we could resort to applying a maximal-avalanche hash function, but the question is always whether we can get what we need with less compute than that, because the big concern for many people is how much it costs to generate a number.