Property based testing

[waalge]

This has come up in other places but afaics there isnt a discussion thread for it (please redirect and close this one if there is)

[KtorZ]

Here's the outcome of the latest discussion we've just had with @waalge this morning.

Aiken's Property-based Testing Framework

Goals

1. Allow Aiken developers to write comprehensive property-based tests for various parts of their Aiken program.

For the sake of the argument here, we won't dwell on the differences between property-based testing and fuzzy testing (fundamentally, property-testing is more guided and search for defects in expected behaviors whereas fuzzy testing only looks for the absence for fatal failures from a much wider input domain).

So said differently, we want an easier way for Aiken developers to test the behavior of pure functions by supplying arbitrary inputs to them and observing properties that should hold for a chosen input domain. This is currently cumbersome to realize due to the lack of side-effects, and in particular a (pseudo-)random generator.

While any Aiken custom-type is in principle representable as a Plutus' Data, we can technically provide default generators for any Aiken type with two gotchas:

1. Opaque types usually enforces invariant which cannot be expressed through the type-system itself. Those invariants would likely escape the generators unless we have a way to tie back generators to types (this relates to other discussions about traits/type-classes).

2. In many (most?) cases, one do not want input domain as wide as allowed by the type-system; especially due to the very restricted set of types in Plutus Core -- and thus Aiken.

Those points mean we need ways of defining and combining custom generators.

2. Minimize the changes to the Aiken language & Rust PVM

We want to avoid, as much as possible, to introduce test-specifics elements to the language. Because these rapidly gets in-the-way of learning and makes the compiler more complex than it needs to be. One other consequence is that it reduces the contribution friendliness to such a framework (e.g. if upgrades to the property-based testing framework require constantly shipping new versions of the compiler).

One option we could consider for example is the addition of a new builtin that would act as a (pseudo-)random beacon. Of course, such a builtin would be unacceptable in a validator. This however introduces discrepancy between VMs, and also requires to possibly introduce changes in the VM that we would rather avoid.

3. Keep-it-simple so that it doesn't immediately throw off newcomers

Property-based testing is already in itself a complicated topic. One of the challenge (and desire) we have with this framework is to make property-based testing accessible even to those with little to no experience in functional programming. The most intuitive way to build such an on-chain framework is to rely on a State Monad to provide a declarative API on top of what is effectively a random beacon.

In essence, a Generator a is nothing more than a wrapper around seed -> (a, seed); a functional API on top of that would be nothing more than a composition of function. Yet, it's easy to loose people into functional jargons here with functors, applicatives and whatnot. We have to be cautious of the learning curve.

Current ideas

fuzzer & via

We want to extend the language with two new keywords: fuzzer and via. The fuzzer keyword will be used to register a new type of definitions to the AST, which can only ever be referenced from tests. So it's similar to the test keyword, with the difference that those functions must comply with a specific signature:

fuzzer foo(seed: Seed) -> (a, Seed) {
  ...
}

Seed here is a new type to be introduced in the Prelude which can be roughly defined as:

type Seed {
  seed: Int,
  size: Int,
}

These definitions can then be referenced using the via keyword, in the signature of a test. Consequently, we will now allow test to carry arguments. For example:

test my_test(a: ScriptContext via my_awesome_fuzzer) {
  ...
} 

This will instruct to the test runner to run the fuzzer referenced by my_awesome_fuzzer to produce a random sequence of a of type ScriptContext. Said differently, the signature of my_awesome_fuzzer here would be something like Seed -> (ScriptContext, Seed).

Constructing fuzzers

Building fuzzers by hand will rapidly become cumbersome. Which is why we want to build an Aiken library for building fuzzers. This implies that fuzzers have the ability to call into other fuzzers (and functions). This doesn't present any challenge since fuzzers are fundamentally already functions.

We have very good inspirations in the wild such as elm-explorations/test which boils down to having a Fuzz abstractions akin to a state monad type Fuzz a = Seed -> (a, Seed). From that, we can build a minimal albeit useful API for defining fuzzers:

type Fuzz<a> = Seed -> (a, Seed)

fn constant(a: a) -> Fuzz<a>

fn bool() -> Fuzz<Bool>

fn int() -> Fuzz<Int>
fn int_range(lo: Int, hi: Int) -> Fuzz<Int>

fn bytearray() -> Fuzz<ByteArray>
fn bytearray_range(lo: Int, hi: Int) -> Fuzz<ByteArray>

fn list(fuzz: Fuzz<a>) -> Fuzz<List<a>>   
fn list_range(lo: Int, hi: Int, fuzz: Fuzz<a>) -> Fuzz<a>

fn map(f: fn(a) -> b, fuzz_a: Fuzz<a>) -> Fuzz<b>
fn map2(f: fn(a, b) -> result, fuzz_a: Fuzz<a>, fuzz_b: Fuzz<b>) -> Fuzz<result> 

fn and_then(f: fn(a) -> Fuzz(b), fuzz_a: Fuzz<a>) -> Fuzz<b>

fn one_of(fuzzs: List<Fuzz<a>>) -> Fuzz<a>

Note that, once we have support for the fuzzer keyword, we can likely simplify most of those definitions by declaring them as fuzzer, possibly making some arguments implicit.

A simple example:

fuzzer foo -> Fuzz<(Int, Int)> {
  let random_int = int_range(0, 100)
  map2((_,_), random_int, random_int)
}

Running and aggregating tests

One of the immediate challenge that comes with property tests is how to present a meaningful report to developers.

The costing of property tests and their execution happens in two isolated steps. One step actually comes from executing the fuzzer with a given seed; collecting the new seed and the generated value as a result. Then, the execution of the test happens. One clear benefits of separating those evaluations is how we can now more precisely measure the cost of executing tests without factoring in the cost of producing the test values.

By default, we will want to run tests 100 times and collect executions costs for those 100 iterations. Iterations will also be using a growing size parameter for generators, to get more and more complex. So providing something like an average cost isn't really meaningful from a user perspective. Yet, printing all the results on the screen is also out of the question.

So, initially, we do want to at least report on the average, median, best and worst case when printing to a terminal, and default to providing all the results when printing to a file (using a structured format like TOML or JSON).

On failure, we can try to find a smaller counter example by running the test with smaller sized generator, following a similar approach to the one described in MiniThesis.

Further ideas

Classification & coverage

There's no good property without labels and coverage. This could be easily added on top of the framework through the use and analysis of specific traces. We leave this out of the immediate scope but is something we likely want to revisit soon enough to enhance both the report and the efficiency of the tests.

Automatic detection of order of approximation

One possible area where the test runner could be useful is if we were able to provide an order of approximation (e.g. O(n), O(log(n)), ...) for a particular chunk of logic, in function of the internal size parameter of the generator. This can potentially be determined by performing some regression fitting on the measured costs with the a priori knowledge of how the Plutus cost model works (and the various costing mechanisms that are used).

Resources / References

• MiniThesis: A very minimal implementation of the core idea of Hypothesis.
• elm-explorations/test: A test library in Elm with support for fuzzing and integrated shrinking.
• elm/random: Low-level plumbing for handling randomness in Elm.
• Moving Beyond Types: Article about Hypothesis and its general approach.
• Hedgehog: One of Haskell's property-based testing framework.
• QuickCheck: Original paper on QuickCheck "A Lightweight Tool for Random Testing of Haskell Programs".

[Quantumplation]

👋 Awesome! This is one of those things that I've talked with KtorZ about often, but never actually gotten around to making a real initiative, so definitely appreciate you stepping up to do the hard part @waalge ;)

I'd love to be a help, though time is pretty limited. I also plan on building / proposing a transaction level fuzzer at some point. Given the differences you mention between property based testing and fuzzing, would it make sense to revise some of the terminology? In particular, instead of fuzzer, I'd suggest using the keyword generator, and instead of the type Fuzz<a>, call it Generator<a>. Just my two cents / mild preference of course, if you feel strongly about the terminology it won't bother me 😅