Unit testing methods with indeterminate output

Question

I have a class that is meant to generate a random password of a length that's also random, but limited to be between a defined min and max length.

I'm constructing unit tests, and ran into an interesting little snag with this class. The whole idea behind a unit test is that it should be repeatable. If you run the test a hundred times, it should give the same results a hundred times. If you're depending on some resource that may or may not be there or may or may not be in the initial state you expect then you're meant to mock the resource in question to ensure that your test really is always repeatable.

But what about in cases where the SUT is supposed to generate indeterminate output?

If I fix the min and max length to the same value then I can easily check that the generated password is of the expected length. But if I specify a range of acceptable lengths (say 15 - 20 chars), then you now have the problem that you could run the test a hundred times and get 100 passes but on the 101st run you might get a 9 character string back.

In the case of the password class, which is fairly simple at its core, it shouldn't prove a huge problem. But it got me thinking about the general case. What is the strategy that's usually accepted as the best one to take when dealing with SUTs that are generating indeterminate output by design?

Answer 1

"Non-deterministic" output should have a way of becoming deterministic for the purposes of unit testing. One way to handle randomness is to allow replacement of the random engine. Here is an example (PHP 5.3+):

function DoSomethingRandom($getRandomIntLessThan)
{
    if ($getRandomIntLessThan(2) == 0)
    {
        // Do action 1
    }
    else
    {
        // Do action 2
    }
}

// For testing purposes, always return 1
$alwaysReturnsOne = function($n) { return 1; };
DoSomethingRandom($alwaysReturnsOne);

You could make a specialized test version of the function which returns any sequence of numbers you want to make sure the test is fully repeatable. In the real program, you can have a default implementation which could be the fallback if not overridden.

Answer 2

The actual output password might not be determinate each time the method is executed, but it will still have determinate features that can be tested, such as minimum length, characters falling within a determinate character set, etc.

You can also test that the routine returns a determinate result each time by seeding your password generator with the same value each time.

Answer 3

Test against "the contract". When the methods is defined as "generates passwords of 15 to 20 characters length with a-z", test it this way

$this->assertTrue ((bool) preg_match('^[a-z]{15,20}$', $password));

Additional you can extract the generation, so everything, that relies on it, can get tested using another "static" generator class

class RandomGenerator implements PasswordGenerator {
  public function create() {
    // Create $rndPwd
    return $rndPwd;
  }
}

class StaticGenerator implements PasswordGenerator {
  private $pwd;
  public function __construct ($pwd) { $this->pwd = $pwd; }
  public function create      ()     { return $this->pwd; }
}

Answer 4

You have a Password generator and you need a random source.

As you stated in the question a random makes non-deterministic output as it is global state. Meaning it accesses something outside of the system to generate values.

You can never get rid of something like that for all your classes but you can separate the password generation for the creation of random values.

<?php
class PasswordGenerator {

    public function __construct(RandomSource $randomSource) {
        $this->randomSource = $randomSource
    }

    public function generatePassword() {
        $password = '';
        for($length = rand(10, 16); $length; $length--) {
            $password .= $this-toChar($this->randomSource->rand(1,26));
        }
    }

}

If you structure the code like this you can mock out the RandomSource for your tests.

You will not be able to 100% test the RandomSource but the suggestions you got for testing the values in this question can be applied to it (Like testing that rand->(1,26); always returns a number from 1 to 26.

Answer 5

In the case of a particle physics Monte Carlo, I have written "unit tests"{*} that invoke the non-deterministic routine with a preset random seed, and then run a statistical number of times and check for violations of constraints (energy levels above the input energy must be inaccessible, all passes must select some level, etc) and regressions against the previously recorded results..

---

{*} Such test violate the "make the test fast" principle for unit testing, so you might feel better characterizing them in some other way: acceptance tests or regression tests, for instance. Still, I used my unit testing framework.

Answer 6

You actually have multiple responsibilities here. Unit testing and in particular TDD is great for highlighting this sort of thing.

Responsibilities are:

1) Random number generator. 2) Password formatter.

The password formatter uses the random number generator. Inject the generator into your formatter via its constructor as an interface. Now you can fully test your random number generator (statistical test) and you can test the formatter by injecting a mocked random number generator.

Not only do u get better code you get better tests.

Answer 7

Many unit testing difficulties become trivial when you refactor your code to sever dependencies. A database, a file system, the user, or in your case, a source of randomness.

Another way of looking at is that unit tests are supposed to answer the question "does this code do what I intend it to do?". In your case, you don't know what you intend the code to do because it's non-deterministic.

With this mind, separate your logic in to small, easily understood, easily-tested-in-isolation parts. Specifically, you create a distinct method (or class!) that takes a source of randomness as its input, and produces the password as an output. That code is clearly deterministic.

In your unit test, you feed it the same not-quite-random input every time. For very small random streams, just hard-code the values in your test. Otherwise, provide a constant seed to the RNG in your test.

At a higher level of testing (call it "acceptance" or "integration" or whatever), you'll let the code run with a true random source.

Answer 8

I have to disagree with the accepted answer, for two reasons:

1. Overfitting
2. Impracticability

(Notice that it may be a good answer in many circumstances, but not in all, and maybe not in most.)

So what do I mean by that? Well, by overfitting I mean a typical problem of statistical testing: overfitting happens when you test a stochastic algorithm against an overly constrained set of data. If you then go back and refine your algorithm, you will implicitly make it fit the training data very well (you accidentally fit your algorithm to the test data), but all the other data maybe not at all (because you never test against it).

(Incidentally, this is always a problem that lurks with unit testing. This is why good tests are complete, or at least representative for a given unit, and this is hard in general.)

If you make your tests deterministic by making the random number generator pluggable, you always test against the same very small and (usually) non-representative data set. This skews your data and may lead to bias in your function.

The second point, impracticability, arises when you haven’t got any control over the stochastic variable. This doesn’t usually happen with random number generators (unless you need a “real” source of random) but it can happen when stochastics sneak into your problem by other ways. For instance, when testing concurrent code: race conditions are always stochastic, you cannot (easily) make them deterministic.

The only way to raise confidence in those cases is to test a lot. Lather, rinse, repeat. This raises confidence, up to a certain level (at which point the trade-off for additional test runs becomes negligible).

Answer 9

As the others have already mentioned, you unit test this code by removing the randomness.

You might also want to have a higher-level test that leaves the random number generator in place, tests only the contract (password length, allowed characters, ...) and, on failure, dumps enough information to allow you to reproduce the system state in the one instance where the random test failed.

It does not matter that the test itself is not repeatable -- as long as you can find the reason why it failed this one time.

Answer 10

Most of the above answers indicate that mocking the random number generator is the way to go, however I was simply using the built in mt_rand function. Allowing mocking would have meant rewriting the class to require a random number generator be injected at construction time.

Or so I thought!

One of the consequences of the addition of namespaces is that mocking built in PHP functions has gone from incredibly hard to trivially simple. If the SUT is in a given namespace then all you need to do is define your own mt_rand function in the unit test under that namespace, and it will be used instead of the built in PHP function for the duration of the test.

Here is the finalized test suite:

namespace gordian\reefknot\util;

/**
 * The following function will take the place of mt_rand for the duration of 
 * the test.  It always returns the number exactly half way between the min 
 * and the max.
 */
function mt_rand ($min = 42, $max = NULL)
{
    $min    = intval ($min);
    $max    = intval ($max);

    $max    = $max < $min? $min: $max;
    $ret    = round (($max - $min) / 2) + $min;

    //fwrite (STDOUT, PHP_EOL . PHP_EOL . $ret . PHP_EOL . PHP_EOL);
    return ($ret);
}

/**
 * Override the password character pool for the test 
 */
class PasswordSubclass extends Password
{
    const CHARLIST  = 'AAAAAAAAAA';
}

/**
 * Test class for Password.
 * Generated by PHPUnit on 2011-12-17 at 18:10:33.
 */
class PasswordTest extends \PHPUnit_Framework_TestCase
{

    /**
     * @var gordian\reefknot\util\Password
     */
    protected $object;

    const PWMIN = 15;
    const PWMAX = 20;

    /**
     * Sets up the fixture, for example, opens a network connection.
     * This method is called before a test is executed.
     */
    protected function setUp ()
    {
    }

    /**
     * Tears down the fixture, for example, closes a network connection.
     * This method is called after a test is executed.
     */
    protected function tearDown ()
    {

    }

    public function testGetPassword ()
    {
        $this -> object = new PasswordSubclass (self::PWMIN, self::PWMAX);
        $pw = $this -> object -> getPassword ();
        $this -> assertTrue ((bool) preg_match ('/^A{' . self::PWMIN . ',' . self::PWMAX . '}$/', $pw));
        $this -> assertTrue (strlen ($pw) >= self::PWMIN);
        $this -> assertTrue (strlen ($pw) <= self::PWMAX);
        $this -> assertTrue ($pw === $this -> object -> getPassword ());
    }

    public function testGetPasswordFixedLen ()
    {
        $this -> object = new PasswordSubclass (self::PWMIN, self::PWMIN);
        $pw = $this -> object -> getPassword ();
        $this -> assertTrue ($pw === 'AAAAAAAAAAAAAAA');
        $this -> assertTrue ($pw === $this -> object -> getPassword ());
    }

    public function testGetPasswordFixedLen2 ()
    {
        $this -> object = new PasswordSubclass (self::PWMAX, self::PWMAX);
        $pw = $this -> object -> getPassword ();
        $this -> assertTrue ($pw === 'AAAAAAAAAAAAAAAAAAAA');
        $this -> assertTrue ($pw === $this -> object -> getPassword ());
    }

    public function testInvalidLenThrowsException ()
    {
        $exception  = NULL;
        try
        {
            $this -> object = new PasswordSubclass (self::PWMAX, self::PWMIN);
        }
        catch (\Exception $e)
        {
            $exception  = $e;
        }
        $this -> assertTrue ($exception instanceof \InvalidArgumentException);
    }
}

I thought I'd mention this, because overriding PHP internal functions is another use for namespaces that simply hadn't occurred to me. Thanks to everyone for the help with this.

Answer 11

There is an additional test you should include in this situation, and that is one to ensure that repeated calls to the password generator actually produces different passwords. If you need a thread-safe password generator you should also test simultaneous calls using multiple threads.

This basically ensures that you are using your random function properly, and not re-seeding on every call.