Issue 49 - Equivalence-based Random Testing

Another weekend, another weekend read, this time all about Equivalence-based Random Testing

This is the Part 2 of a two part series on Random Testing Strategies. We will use Issue 47 - Speculative Modifications as an example. Speculative Modifications refer to the ability to rollback (the effects of) a multi-step process after the n-th step, replicating the developer experience of transactions for an in memory data structure.

This week, we will discuss Equivalence-based Random Testing.

Equivalence-based Random Testing leverages the concept of equivalence classes—groups of states or behaviors that are indistinguishable under the system's specifications.

By ensuring that different sequences of operations produce equivalent results, we can validate that the system adheres to its specification without the explicitly predicting its exact behavior.

Recall the Collection class, which manages a set of items and applies commands to modify its state. The Transaction class maintains redo and undo stacks, so changes can be rolled back when desired.

In traditional testing, we predict the exact state of the collection after a transaction is committed:

c = Collection()
t = Transaction(c)
t.insert(1, User("foo", "foo@example.org"))
t.insert(2, User("bar", "bar@example.org"))
t.commit()
assert c == Collection([
    (1, User("foo", "foo@example.org")),
    (2, User("bar", "bar@example.org"))
])

In equivalence-based testing, we compare sequences of operations and leverage inherent equivalencies. For example:

A new collection executing a sequence of transactions, some committing, some aborting, must be equal to a new collection executing only the committed transactions

First, we generate a list of transactions including a the decision to commit or rollback the transaction; random_operations() generates a list of insert, update, or delete commands with random parameters.

transactions = [
    (random_operations(), random.choice([0, 1])) for _ in range(100)
]

We use a function to apply a transaction, committing or rolling back based on the flag.

def apply_transactions(c, transactions):
  for ops, commit in transactions:
    t = Transaction(c)
    for op in ops:
      if op[0] == "insert":
        t.insert(op[1], op[2])
      elif op[0] == "update":
        t.update(op[1], op[2])
      elif op[0] == "delete":
        t.delete(op[1])
     if commit:
       t.commit()
     else:
       t.rollback()

Now we test the system by applying transactions to two collections:

1. 1st Collection

   Apply all transactions, committing or rolling back based on the flag.

2. 2nd Collection

   Apply only the transactions that are flagged to commit.

c1 = Collection()
apply_transactions(c1, transactions)
c2 = Collection()
apply_transactions(c2, [(o, 1) for o, c in transactions if c])
assert c1 == c2, "Collections are not equivalent!"

By comparing the final states of either collections, we verify that transactions that roll back leave no trace. This equivalence-based testing approach avoids predicting exact outcomes yet validates that the system adheres to its guarantees.

Happy Testing!