Use fast-check to test concurrency consistency invariants

[CMCDragonkai]

Specification

We are likely to have alot of concurrency consistency invariants to test. EFS showed us alot of potential pitfalls and bugs in race conditions. SI helps at least ensure that we always have consistency at the DB layer, however it turns out testing concurrency is always really complicated and involves some overhead. Simple expect tests are not enough.

Here comes https://github.com/dubzzz/fast-check, it's a property based testing based on quickcheck. This can be used for quick light-weight model based testing.

Primarily quick-check related libraries provide 2 things:

1. A quick way of generating random data according to some schema, which is useful for any kind fuzzing (and we saw how fuzzing was useful in solving our DB encoding issues)
2. And a way to specify models and testing software if they fit our models.

While other model-based testing tools such as ModelJUnit 1 are perfectly valid alternatives, as a model-based testing tool, we selected QuickCheck [4] for the fact that it provides test case shrinking functionality whereby upon detecting a failure, it searches for smaller test cases which also generate the fault to aid debugging. Although initially developed as a tool for the Haskell programming language, it has been implemented on a number of platforms and for this work, we utilise the Erlang implementation [2]. QuickCheck is primarily a random test data generation tool but it also supports model-based testing. Given a model and a set of pre and postconditions, the tool is able to automatically generate test cases which are used to verify that the conditions hold in the context of different sequences of actions.

So we should see if fast-check can help us do concurrency testing in a number of domains:

1. Our network domain has lots of concurrency issues
2. Vaults domain - lots of reads/writes here
3. Nodes domain - lots of management of nodes
4. Gestalts and ACL domain

Additional context

• https://github.com/dubzzz/fast-check
• Implement a scheduledDelayedFunction dubzzz/fast-check#564 - issue about delaying scheduled functions so that the calls themselves can be made concurrent

Tasks

1. Investigate how fast-check can help with concurrent tests and fuzz tests
2. Investigate how to integrate fast-check into jest testing including timeouts and reporting
3. Apply fast-check to EFS tests and PK tests

[tegefaulkes]

Ok, looks like using a combination of fc.asyncProperty and fc.scheduler we gain finer control over the order of concurrent operations. it will run the test multiple times with a random order for the scheduler. This will help a lot in the EFS tests where in a lot of cases we run the test twice with two different orders. So we can reduce the lines of code for tests there.

One of the better features here is that we can specify a deterministic test for re-creating failures. Or we can define our own test conditions that will be run every time. When a test fails it will log out the exact conditions that led to the failures. To make full use of this we will need our own custom arbitraries https://github.com/dubzzz/fast-check/blob/main/packages/fast-check/documentation/AdvancedArbitraries.md .

Here is an example of how to use this.

  test('concurrent trusting gestalts', async () => {
    const acl = await ACL.createACL({ db, logger });
    await fc.assert(
      fc.asyncProperty(fc.scheduler(), async (s) => {

        await Promise.all([
          s.schedule(acl.setNodesPerm([nodeIdG1First, nodeIdG1Second] as Array<NodeId>, {
          gestalt: {
            notify: null,
          },
          vaults: {
            [vaultId1]: { pull: null },
          },
        })),
        s.schedule(acl.setNodesPerm([nodeIdG1First, nodeIdG1Second] as Array<NodeId>, {
          gestalt: {
            notify: null,
          },
          vaults: {
            [vaultId1]: { pull: null },
          },
        })),
        await s.waitAll()
        ]);
      })
    );
  })

example of the failure

Error: Property failed after 1 tests
{ seed: -1604596825, path: "0", endOnFailure: true }
Counterexample: [schedulerFor()`
-> [task${2}] promise rejected with value new Error("")
-> [task${1}] promise resolved`]
Shrunk 0 time(s)
Got error: ErrorDBTransactionConflict

Stack trace: ErrorDBTransactionConflict: 
    at constructor_.commit (/home/faulkes/matrixcode/polykey/js-polykey/node_modules/@matrixai/db/src/DBTransaction.ts:461:17)
    at /home/faulkes/matrixcode/polykey/js-polykey/node_modules/@matrixai/db/src/DB.ts:210:15
    at withF (/home/faulkes/matrixcode/polykey/js-polykey/node_modules/@matrixai/resources/src/utils.ts:31:7)

Hint: Enable verbose mode in order to have the list of all failing values encountered during the run

    at asyncThrowIfFailed (/home/faulkes/matrixcode/polykey/js-polykey/node_modules/fast-check/lib/check/runner/utils/RunDetailsFormatter.js:133:11)

I think fast-check's utility is limited here. If we're just testing for transaction conflicts then the order of operations doesn't really matter much. It can be useful for randomising values for testing such as IDs and strings if we want to add more robustness to our testing.

[tegefaulkes]

As for generating random values for testing. It can be done like so;

  test('random values', async () => {
    await fc.assert(
      fc.asyncProperty(
        // We can generate arrays
        fc.array(fc.integer(), {maxLength: 5}), 
        // We can filter for conditions on values
        fc.float().filter( num => num > 10), 
        fc.boolean(), 
        async (integer, float, bool) => {
        // We can set pre-conditions to adhere too.
        // If this condition is false then the test is tried again with new values.
        // The test will fail if this fails too often.
        fc.pre(integer[0] < float);
        console.log(integer, float, bool);
        // The fc.assert will fail in the case of a thrown error or if we return any falsy value.
        return bool;
      })
    );
  })

We provide a set of arbitraries types that are generated and then provided to the test. One very useful feature is that when a test failure happens it will shrink test values down to the simplest set causing the failure.

Example failure;

Error: Property failed after 1 tests
{ seed: -728782760, path: "2:1:0:0:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1:1", endOnFailure: true }
Counterexample: [[0],10.000000953674316,false]
Shrunk 24 time(s)
Got error: Property failed by returning false

Hint: Enable verbose mode in order to have the list of all failing values encountered during the run

    at asyncThrowIfFailed (/home/faulkes/matrixcode/polykey/js-polykey/node_modules/fast-check/lib/check/runner/utils/RunDetailsFormatter.js:133:11)

So this can be useful for for finding any intermittent errors in a test. Using the test failure information here we can deterministically run the same conditions that caused the failure over and over again. Very useful for finding some of the harder to find bugs.

[CMCDragonkai]

Detection of a transaction conflict wouldn't be useful unless the idea is upon a random selection of async operations, some will have conflicts and some will not under certain conditions.

It can also be applied to the counter racing to ensure that we don't have conflicts in that case and that the end state is consistent.

Also many of our domains have an expected end state after concurrent operations. We should use this.

[tegefaulkes]

Creating custom arbitrary seem simple enough. You can derive them from an existing arbitrary. Doing this we can also benefit from shrinkage.

  test('custon arbitrary', async () => {
     const nodeIdArb: fc.Arbitrary<NodeId> = fc.uint8Array({maxLength: 32, minLength: 32})
       .map((array) => IdInternal.fromBuffer<NodeId>(Buffer.from(array)));

    await fc.assert(
      fc.asyncProperty(
        nodeIdArb,
        async (nodeId) => {
          console.log(nodeId);
          return false;
        })
    );

  })

Will throw and shrink to;

Error: Property failed after 1 tests
{ seed: -1277985303, path: "0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0:0", endOnFailure: true }
Counterexample: [IdInternal.from([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0])]
Shrunk 29 time(s)
Got error: Property failed by returning false

Hint: Enable verbose mode in order to have the list of all failing values encountered during the run

    at asyncThrowIfFailed (/home/faulkes/matrixcode/polykey/js-polykey/node_modules/fast-check/lib/check/runner/utils/RunDetailsFormatter.js:133:11)

[tegefaulkes]

So in summary, this will be very useful for the following test cases.

• Concurrency tests where the order affects the outcome of the test. EFS does a lot of this.
• Using randomly generated test inputs for a variety of conditions are recreating an failures deterministically. For example setting permissions with a random set of permissions and nodes. Or testing node graph operations on random sets of nodes.
• Testing against state machines.

It's not so useful for;

• concurrency tests where the concurrent call results in error regardless of order.

[tegefaulkes]

For longer running tests we will need to adjust the amount of testing done using the numRuns and interruptAfterTimeLimit parameters for fc.assert.

[tegefaulkes]

domains that can make use of the deterministic random value generation.

• ACL
• claims
• gestalts
• nodes
• node graph
• sigchain
• validation?

can make use of scheduler for concurrency

• discovery - concurrently adding and consuming the queue, we can schedule mocking results as well.
• network - May be useful to combine tests where dfferent events happen. Such as who initiates a connection end.
• notifications - concurrent adding, reading and removing notifications.
• sessions
• vaults - for checking if locking prevents transaction conflicts and enforces seralisation.