Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Doing R&D work, I often find myself writing programs that have some large degree of randomness in their behavior. For example, when I work in Genetic Programming, I often write programs that generate and execute arbitrary random source code.

A problem with testing such code is that bugs are often intermittent and can be very hard to reproduce. This goes beyond just setting a random seed to the same value and starting execution over.

For instance, code might read a message from the kernal ring buffer, and then make conditional jumps on the message contents. Naturally, the ring buffer's state will have changed when one later attempts to reproduce the issue.

Even though this behavior is a feature it can trigger other code in unexpected ways, and thus often reveals bugs that unit tests (or human testers) don't find.

Are there established best practices for testing systems of this sort? If so, some references would be very helpful. If not, any other suggestions are welcome!

share|improve this question
5  
Can't you mock the kernel ring buffer too ? And other random aspects of your code ? –  Jonathan Merlet Oct 18 '12 at 14:21
1  
@JonathanMerlet Potentially, but the issue is that, when deployed, the code will have access to the real ring buffer (indeed, to a real OS). So if I only test on a mocked up version, then I'm just deferring the discovery of these bugs until later. –  John Doucette Oct 18 '12 at 14:28
    
It seems to me that the problem is not related to the program's random behaviour (since this can be controlled by the random seed) but to particular states of this 'kernel ring buffer'. So your question is actually 'how do I test a program that depends on external state', right? –  AakashM Oct 19 '12 at 9:51
    
@AakashM, yeah, that's a better way to phrase it. To be more specific, a program with an external state, which stochasticly accesses or alters the external state. –  John Doucette Oct 19 '12 at 11:36
add comment

4 Answers

up vote 6 down vote accepted

It is useful to add hooks, as suggested, to recreate exact states. Also instrument the system so that it can dump its "seeds" (in your case, including the PRNG seed as well as the kernel ring buffer, and any other sources of nondeterministic input.)

Then run your tests both with true random input, and regression-style with any previously-discovered interesting cases.

In the particular case of your access to the kernel, I'd recommend making a mock in any case. Use the mock to force equivalence classes that are less likely to show up in practice, in the spirit of "empty" and "full" for containers, or "0, 1, 2^n, 2^n+1, many" for countable things. Then you can test with the mock and with the real thing, knowing that you have handled and tested the cases you've thought of so far.

Basically, what I'm suggesting amounts to a mix of deterministic and nondeterministic inputs, with the deterministic ones being a mix of those you can think of and those you were surprised by.

share|improve this answer
add comment

I'm not a specialist in this domain, but there is a scientific litterature relative to stochastic program testing.

If you cannot easily create test classes, a statistical test can be used, as #Euphoric said. Borning et al. compare a traditional approach and a statistical one. A generalisation of the statistical tests suggested by @Euphoric could be the one discussed by Whittaker. He suggested to create a stochastic model of the desired (stochastic, in your case) behavior and then generate specific test cases from this model (see his dedicated paper).

share|improve this answer
    
Thanks! Looks very helpful. For those outside academic institutions, a preprint version of the paper can be pulled from the author's google code repository here: team4model.googlecode.com/svn/trunk/resources/paper/… –  John Doucette Oct 19 '12 at 11:59
add comment

I think statistical testing is the only way. Just like random numbers are "tested" for randomness by statistical tests, so need to be algorithms that use of random behavior.

Simply run the algorithm multiple times with either same or different input and compare it to each other. The problem with this approach is massive increase in computational time required to finish the testing.

share|improve this answer
add comment

One reasonable thing to do is to seed the random number generator with a constant value for the tests, so that you get a deterministic behavior.

share|improve this answer
1  
this; or mock out the prng entirely –  jk. Oct 18 '12 at 14:08
1  
Thanks for the suggestion! I do this for unit testing already, but I cannot test all possible programs by hand. –  John Doucette Oct 18 '12 at 14:29
2  
but this means that you can't test whether the randomness works properly.. –  Louis Rhys Oct 19 '12 at 7:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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