3

How would I express a Behavior Driven Development (BDD) acceptance criteria/story/scenario that indicates items should be random to some degree on a Home screen of an app like Instagram?

Here's what I've thought of so far:

Scenario: Random images appear in Home screen

Given 1000 images
And each view of the Home screen shows 10 random images
And the user has viewed the Home screen 99 times
When the user views the Home screen for the 100th time
Then no image should have appeared on the Home screen more than 25 times

From a user perspective, this seems like a good way to express the requirement. However, if I run this test in a BDD framework as part of Continuous Integration (CI), then there is some chance it will not pass once in a while.

So, are there any better ways to specify an acceptance criteria for randomness that will only fail if there is a bug in the code and not due to the randomness itself?

  • 1
    The only thing I can think of that would be valid is some sort of fuzzy heuristic, as in "given this particular statistical analysis and a sufficient number of trials, the output will be accurate to this bell curve within 2 standard deviations" or somesuch. It would most likely be applied to the random function, with some assurances that it is being applied correctly to the problem domain (perhaps with some integration tests using known random seed values). – Robert Harvey Jan 28 '15 at 5:32
  • 1
    Given that with randomness Everything not forbidden is compulsory this may be an insurmountable problem. If you run the unit test enough, a case where the same image appears 100 times will happen. Also, I wonder if this brushes up against Goedel or the Halting problem. I think your best bet is peer review of the relevant code. – user949300 Jan 28 '15 at 7:33
  • 1
    Since a good PRNG is generally indistinguishable from true randomness, and true randomness is unpredictable, there's no way to do this such that the test can't ever fail. The only way to be sure is to review the code in charge of selecting random images and verify that it unconditionally calls a PRNG, and then verify that the PRNG is suitable for your needs. – Doval Jan 28 '15 at 12:44
  • 2
    What you're asking for isn't randomness, you're asking to randomly select 10 images from the pool and remove them until the rest of the images in the pool have been given the same treatment. – Blrfl Jan 28 '15 at 12:58
6

With randomized algorithms in a CI environment it is of utmost importance, that the result of the test is as non-random as possible. You must under any means find a way to ensure that a correct implementation will almost always result in a passed test. Otherwise, you or your co-workers will be forced to disable the test and plan to rewrite it. You cannot block the whole downstream due to a random test failing. It is also not acceptable having to rebuild "because sometimes it just doesn't work".

Therefore, you can and should not write any tests that involve an algorithm with a random result, but try to verify a concrete result. As Robert Harvey pointed out, the only meaningful way to deal with the quality of a random distribution is to analyze it in a mathematical/statistical way. How deep down you go into that rabbit hole though, is a matter of personal preference and the importance and required accuracy of the unit under test.

You could indeed try to measure values like standard deviations if your sample is large enough. You could also go for a more practical approach, like, ensuring that a certain number of different images is displayed within X views. For the latter though you still need to keep in mind that you must formulate a criterion, for which the likelihood that it is violated by a correct implementation due to a random variation is extremely small. Preferably, it should be smaller than the probability that your CI servers' hardware fails.

When writing the actual tests, there are generally two things to keep in mind with randomness:

  1. Seed. As Robert Harvey already mentioned, you can make life easier on yourself when you know which seed caused the failure. Randomness is really hard to "reproduce" otherwise. I do not advise using a fixed seed though. You should take a fresh seed on each run, because you want your algorithm to be CI-tested on loads of different values over the time. But you should take care, that the test failure messages contain whichever seed was used.

  2. Performance. If you are writing BDD tests for acceptance criteria it may not be much of a problem. If you include such tests within unit tests though, it will be significantly slower than other tests due to the required repeated runs. Some books claim that a unit test should be faster than 10ms. That's pretty much impossible if you try to run a randomized algorithm 1000 times. 10ms may sound extreme, but once you want to run hundreds of thousands of these tests it does sum up quickly - even more so when you need repeated runs.

  • Thanks @frank, looks like I was on the right track with a statistical approach. Most helpful advice I got from you was "Preferably, it should be smaller than the probability that your CI servers' hardware fails." Darn good point, thank you! – Michael Osofsky Jan 30 '15 at 5:57

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.