0
$\begingroup$

I have an application that depends on a random number generator to perform. The application might be sensitive to the quality of the random numbers, but I don't know for sure. I'd like to test this, and if it is, what the degree of sensitivity is.

I've currently got a xorshift1024* PRNG plugged in. It's fast and I can directly inject a full 1024 bit state.

I need to be able to degrade it in a controlled fashion, ranging from it's high quality native mode to something quite bad. By quite bad, I mean something far far worse than a simple linear congruential generator. I'm not interested in slowly changing it's output distribution from uniform to say, normal. I just want to be able to make it (technically) crappier and crappier.

I have the sense that this might be a common requirement in other testing applications, so there might be a best practice methodology. At this point my only alternative is to switch off the generator entirely.

Is there a way to incrementally degrade the quality of my PRNG?

$\endgroup$
  • 1
    $\begingroup$ There are many ways you could degrade its output: e.g., changing the distribution to be non-uniform, reducing the space of possible output values, introducing short-range or long-range correlations between successive output values, etc. Do you have one you'd like to focus on or that would make the most sense for your application? As it stands this feels pretty broad, like it might admit many possible answers (any community votes?). $\endgroup$ – D.W. Jan 5 '16 at 2:14
  • $\begingroup$ @D.W. I've specified the generator I'm currently using. $\endgroup$ – Paul Uszak Jan 5 '16 at 2:36
  • 1
    $\begingroup$ OK, but that wasn't what I was asking. Maybe I wasn't clear enough. I'm asking how you want to degrade it, or what type of degradation makes the most sense for your particular scenario. Alternatively, you could tell us what criteria you expect to use to evaluate answers: something to help us narrow down the space of possible methods, or to evaluate candidate answers. $\endgroup$ – D.W. Jan 5 '16 at 2:48
  • $\begingroup$ @D.W. I'm not sure what else to add. All I want is for it to be less and less uniform. No particular output distribution. More and more of all the things that make a really bad random generator even badder. Final evaluation will be via DIEHARD on the application's output, NOT on the PRNG itself. This is not a test of the PRNG. This requirement is atypical then? $\endgroup$ – Paul Uszak Jan 5 '16 at 3:39
  • $\begingroup$ One way is to use the RC4 stream cipher as a PRNG, and incorrectly use the XOR swap technique to swap array elements. This was done in the The Underhanded C Contest 2007 $\endgroup$ – Nayuki Jun 19 '16 at 3:47
2
$\begingroup$

There are many possible ways to degrade its output, but here is one simple choice:

Think of your PRNG as outputting a sequence of bits. For a good PRNG, each bit would be uniformly distributed (equally likely to be 0 or 1), independent of the previous bits. We can build a degraded PRNG where each bit of the output is 1 with probability $p$ or 0 with probability $1-p$, independent of all of the previous bits. This gives us a parameter $p$ that can be varied from $1/2$ down to $0$: with $p=1/2$, there's no degradation, and smaller values of $p$ correspond to increasing amounts of degradation. Effectively, $p$ is a tuning knob that allows us to control the amount of degradation.

From this, you can derive a way to get other quantities. If you want a 32-bit integer, you generate each of its bits using this degraded PRNG. etc.

This model has some nice properties. For instance, if you generate a random $k$-bit value using your degraded PRNG, the resulting value will have $k h_2(p)$ bits of entropy. This varies from $k$ bits smoothly down to $0$ bits as $p$ varies from $p=1/2$ down to $p=0$. As a very crude approximation, the $k$-bit value will be approximately uniformly distributed on a set of size $2^{k h_2(p)}$; as $p$ gets smaller (as you introduce more degradation), the size of this set gets smaller smoothly.

Of course, we can't tell you whether this is the "right" degradation model for your particular application, as that will depend on your particular application. There are many other possible ways of degrading a PRNG's output, and since we haven't been given any specific criteria for selecting among them, I have semi-arbitrarily chosen one that is especially simple to implement and simple to think about.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.