Property checks with a seeded generator

A table of cases tests the inputs a person thought of. A property tests a statement about every input, and a generator makes the inputs. The statement is usually one line, such as "addition commutes" or "reversing a string twice gives the string", and a case that breaks it is a counterexample. This page writes the generator and the loop by hand, with a seed, so a failure can be reproduced exactly.

A seeded generator

The generator is a linear congruential generator: one uint of state, a multiplication, an addition and a shift. The numbers are not random in the sense of a cryptographic source, and they are perfectly good for test inputs: the same seed gives the same sequence on every machine and in every run.

Console.WriteLine("properties 1.0"); var random = new SeededRandom(20240310); var check = new Properties(); check.ForAll("addition commutes", 100, () => { var a = random.Next(-1000, 1000); var b = random.Next(-1000, 1000); return a + b == b + a; }); check.ForAll("reversing twice is the original", 100, () => { var text = random.Text(8); return Reverse(Reverse(text)) == text; }); check.ForAll("sorting keeps every value", 100, () => { var values = random.Ints(5, -20, 20); var sorted = values.OrderBy(value => value).ToArray(); return sorted.SequenceEqual(values.OrderBy(value => value)); }); Console.WriteLine($"cases {check.Cases} failed {check.Failed}"); return check.Failed == 0 ? 0 : 1; static string Reverse(string text) => new(text.Reverse().ToArray()); sealed class Properties { public int Cases { get; private set; } public int Failed { get; private set; } public void ForAll(string name, int cases, Func<bool> property) { var failed = 0; for (var i = 0; i < cases; i++) { Cases++; if (!property()) { failed++; Failed++; } } Console.WriteLine($"{(failed == 0 ? "ok " : "FAIL")} {name}: {cases} cases, {failed} failed"); } } sealed class SeededRandom(int seed) { private uint _state = (uint)seed; public int Next(int min, int max) { _state = _state * 1103515245u + 12345u; var value = (int)(_state >> 16); return min + (int)((uint)value % (uint)(max - min)); } public int[] Ints(int count, int min, int max) { var values = new int[count]; for (var i = 0; i < count; i++) { values[i] = Next(min, max); } return values; } public string Text(int length) { const string Alphabet = "abcdefghij"; var chars = new char[length]; for (var i = 0; i < length; i++) { chars[i] = Alphabet[Next(0, Alphabet.Length)]; } return new string(chars); } }

Next(min, max) takes the high bits of the state and reduces them modulo the width of the range. The reduction is slightly biased towards the low values of the range, which matters for a simulation and not for a test input. Text(length) draws letters from a ten-letter alphabet, so a string of eight characters is a small space that the loop can cover many times.

Three properties

Each property is a lambda that draws its own inputs and returns a bool. ForAll runs it a hundred times, counts the failures and prints one line per property, so the report says which statement broke and how often:

dotnet run
echo "status: $?"

properties 1.0
ok   addition commutes: 100 cases, 0 failed
ok   reversing twice is the original: 100 cases, 0 failed
ok   sorting keeps every value: 100 cases, 0 failed
cases 300 failed 0
status: 0

Three hundred cases and no failure. A property that passes says the statement held for the three hundred inputs this generator produced, which is not a proof and is a stronger statement than three hand-written rows: the inputs were spread over the whole range, including the negative side of zero, the empty text of length zero if it were drawn, and the repeated values a small range produces.

A counterexample

The second program states a property that is false: it asks whether subtraction commutes. The loop stops at the first case that breaks it and prints the inputs, both results and the number of the case:

Console.WriteLine("counterexample 1.0"); var random = new SeededRandom(7); for (var i = 0; i < 100; i++) { var a = random.Next(-100, 100); var b = random.Next(-100, 100); if (a - b != b - a) { Console.WriteLine($"counterexample a={a} b={b}: a - b = {a - b}, b - a = {b - a}"); Console.WriteLine($"stopped at case {i + 1} of 100"); return 1; } } Console.WriteLine("no counterexample"); return 0; sealed class SeededRandom(int seed) { private uint _state = (uint)seed; public int Next(int min, int max) { _state = _state * 1103515245u + 12345u; var value = (int)(_state >> 16); return min + (int)((uint)value % (uint)(max - min)); } }

dotnet run
echo "status: $?"

counterexample 1.0
counterexample a=32 b=-94: a - b = 126, b - a = -126
stopped at case 1 of 100
status: 1

The first case already breaks it: 32 minus −94 is 126 and −94 minus 32 is −126. The counterexample is the useful part of a property test, and this one is small because the generator drew small numbers. A generator that drew large numbers would produce a correct failure that is harder to read, which is why the libraries of this kind shrink a failing input towards zero before they report it. This page does not shrink, and the property is one line, so the first counterexample is already readable.

Why a seed

A generator without a seed fails in a different place on every run, which makes a failure impossible to reproduce and a green run impossible to compare. The seed is part of the test: the page fixes 20240310 for the three properties and 7 for the counterexample, so the output above is the output of every run. A property test in a repository usually prints the seed of a failing run, so a reader can pass it back and see the same case.

The next page leaves values and goes to text: the output of a program compared with a file that holds the expected output, and the diff that says where the two differ.

Exercises

  1. Add a property that the sum of a list is the same after OrderBy.
  2. Add a property that fails only for a negative number and see how many cases the loop needs.
  3. Change the seed and check that the three properties still pass and the counterexample changes.
  4. Shrink a failing case by halving both numbers until the property still fails and one of them is zero.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is a property in a property test?

    Answer

    A statement about every input that the generator draws

    The page writes three of them as lambdas returning a bool.

  2. Why does the generator take a seed?

    Answer

    The same seed gives the same cases, so a failure can be reproduced

    The page fixes two seeds so its output is stable.

  3. What does this program print? var state = 7u; state = state * 1103515245u + 12345u; Console.WriteLine(state);

    Answer

    3429651764

    The multiplication and the addition are the two steps of the generator, and the value wraps in a uint.

  4. What is a counterexample?

    Answer

    An input for which the property is false

    The page prints 32 and −94 as the first counterexample of the wrong property.

  5. What does this program print? var a = 32; var b = -94; Console.WriteLine($"{a - b} {b - a}");

    Answer

    126 -126

    That is the pair of results the measured counterexample prints.

  6. Why is a modulo reduction of the state slightly biased?

    Answer

    The number of states is not a multiple of the range width

    The page says the bias matters for a simulation and not for a test input.

  7. What does this program print? Console.WriteLine(1u << 4);

    Answer

    16

    A shift to the left by four doubles the value four times.

  8. What does the ForAll loop report for a property?

    Answer

    Its name, the number of cases and the number of failures

    The measured lines read ok with 100 cases and 0 failed.

  9. Why does this page not shrink a failing case?

    Answer

    Shrinking is a feature of the libraries, and the page keeps the checker small

    The page names the feature and says what it would add.

  10. What does this program print? var text = "abc"; Console.WriteLine(new string(text.Reverse().ToArray()));

    Answer

    cba

    Reverse reverses the characters, which is half of the reversal property.

The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev