Introduction

Property-Based Testing checks whether a system behaves correctly for wide range of automatically generated inputs. Property-based testing provides the following benefits over standard testing techniques:

1. Better coverage: standard example-based tests check scenarios that we think of; property-based testing allows us to check scenarios that we forgot to think about.
2. Better scalability: a single property-based test can replace a large number of example-based tests.

A Simple Example

To illustrate the advantages of property-based testing, consider this implementation of binary search:

bool binary_search(const std::vector<int> &xs, int key) {
  std::size_t max = xs.size(), min = 0;
  while (min < max) {
    auto mid = lib::midpoint(min, max);
    if (key < xs[mid])
      max = mid - 1;
    else if (key > xs[mid])
      min = mid + 1;
    else
      return true;
  }
  return false;
}

Is binary_search implemented correctly? We can write a few simple example-based tests:

TEST(BinarySearch, Examples) {
  EXPECT_FALSE(binary_search({}, 0));
  EXPECT_TRUE(binary_search({0}, 0));
  EXPECT_TRUE(binary_search({0, 1, 2}, 2));
  EXPECT_TRUE(binary_search({0, 1, 2, 3, 4, 5}, 2));
}

Code coverage tools will confirm that the above test executes every line of code in binary_search. Nonetheless, binary_search does have a bug. This bug is revealed by running by a simple property-based test:

HALCHECK_TEST(BinarySearch, Membership) {
  // Generate a random ("arbitrary") sorted vector.
  auto xs = gen::arbitrary<std::vector<int>>("xs"_s); // (a)
  std::sort(xs.begin(), xs.end());
 
  // Generate a random element of xs.
  auto x = gen::element_of("x"_s, xs); // (b)
 
  // halcheck does no logging by default.
  // It is good practice to log your inputs in case the test fails.
  LOG(INFO) << "xs: " << testing::PrintToString(xs);
  LOG(INFO) << "x: " << testing::PrintToString(x);
 
  // Since x is an element of xs,
  // binary_search(xs, x) should always return true.
  EXPECT_TRUE(binary_search(xs, x)); // (c)
}

The above test reveals that binary_search({0, 1}, 0) returns false instead of true. Fixing this bug is left as an exercise to the reader.

Elements of a Property-Based Test

Property-based tests require three things:

1. a system under test whose correctness we would like to test,
2. a set of generators which produce inputs for the system under test, and
3. a property which determines if the system under test behaves correctly.

In the above example, the system under test is the function binary_search. There are two generators, marked by (a) and (b). Finally, the oracle is marked by (c) ^[1].

The system under test is usually given, so the main challenge of property-based testing lies in devising generators and properties. Property-based testing frameworks (such as halcheck) primarily support test execution and writing generators (see the generator reference.)

---

[1] Properties need not be explicitly asserted. Sometimes you just want to test that a piece of code does not crash.