Fuzz testing

[ept]

Even though we already have a solid suite of unit tests with near-complete coverage, fuzz testing with large numbers of pseudorandomly generated inputs would provide further reassurance, especially when switching to the new data structures that have lots of opportunities for subtle bugs.

A while ago I already wrote a minimal CRDT implementation with the intention of providing a test oracle that gives the expected answer. However, I have not yet written the test case generator and the test execution logic.

[pvh]

Do you have a strategy in mind for this, @ept? Seems like a fun little project to experiment with.

[ept]

I had in mind the following approach, which tests only the backend, not the frontend (I think that's good because it allows the same fuzz tests to be run against both JS and wasm backends, and it avoids having to fiddle around with the proxies stuff in the frontend):

• Write a minimal frontend that can be updated based on a patch received from the backend, and which maintains the document state at a node (including all existing object IDs and element IDs of all list elements).
• Make a deterministically seeded pseudorandom number generator for all the following random choices; wire up the test framework so that it reports the seed on any test failure, and allows the test to be re-run with a seed specified as command-line argument.
• Instantiate three nodes; in each execution step, randomly pick one of them to do something. That "something" may be to generate a new change, or to apply a change received from another node (apply the binary change to the backend, take the resulting patch, and apply the patch to the minimal frontend).
• If generating a new change, randomly pick the number of operations to generate. For each operation, randomly pick one of the existing objects in the document (including the root) as the target of the operation.
• If the target object is a map, randomly pick an existing key in that object or a new key, pick an operation type (set, del, makeMap, makeList), and pick a value (in the case of set).
• If the target object is a list, randomly pick whether to insert or to update/delete. If insert, randomly pick as insertion position either the head or after any existing list element (identified by elemID). If update/delete, randomly pick one of the list elements. If insert or update, pick a value or makeMap/makeList. Update the frontend so that subsequent operations in the same change can refer to the element that was just inserted, if any.
• Pass this generated change to Backend.applyLocalChange to binary-encode it, and enqueue it as a future change to apply on the other nodes. Keep a separate queue for every source node so that different nodes may apply the same changes in different orders if they come from different nodes.
• After some randomly chosen number of time steps, stop generating new changes and apply all the outstanding changes that have not yet been applied. Then check that the document state is the same at all three nodes.
• Check whether Backend.load(Backend.save(doc)) works (throws an exception if we are not able to reconstruct the verbatim original change history from the compressed document), and that Backend.getPatch(doc) restores the same document state as before the save().