Issue 48 - Assertion-based Random Testing

An exploration of Assertion-based Random Testing

Dec 08, 2024

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

This is the Part 1 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 Assertion-based Random Testing.

Testing Primer

Unit tests are a staple for building confidence in your code—or driving development (see Test Driven Development). However, unit tests come with notable shortcomings:

Example-based. Unit tests rely on specific examples, like add(2, 3) == 5, requiring you to anticipate the result.
Unobservable paths. Stretches within an execution where internal states and state transitions are not directly observable, limiting tests to the final result.

Random testing addresses the first issue by expanding the sample space, by increasing the number of test cases to a confidence threshold.

Assertion-based testing addresses the second issue by making invariant violations observable. By adding assertions throughout the code, we can detect invariant violations along execution paths that are otherwise unobservable.

Assertions do not try to predict correct results; assertions enforce invariants by halting execution if violated. A test passes if the test runs to completion without triggering an assertion failure.

Assertion-based Random Testing

Let’s revisit the Speculative Modifications example to see how assertions enhance random testing.

Custom Assert

First, we create a custom assertion mechanism: Using os._exit ensures that assertion failures bypass any exception-handling logic, halting the program immediately.

import os

def Assert(condition, message="Assertion failed"):
    if not condition:
        print(f"Assertion Violation: {message}")
        os._exit(666)

Adding Assertions to the Collection Class

Recall the Collection class, which manages a set of items and applies commands to modify its state. The Collection class raises application-level exceptions for invalid operations like duplicate inserts or updates and deletes on non-existent items:

class Collection:

  def __init__(self):
    self._items = {}
    
  def apply(self, action):

    if isinstance(action, Insert):
->    if action.id in self._items:
        raise KeyError(f"Item with id {action.id} already exists")
      self._items[action.id] = action.item

    elif isinstance(action, Update):
->    if action.id not in self._items:
        raise KeyError(f"Item with id {action.id} not found")
      for key, value in action.part.items():
        setattr(self._items[action.id], key, value)

    elif isinstance(action, Delete):
->    if action.id not in self._items:
        raise KeyError(f"Item with id {action.id} not found")
      del self._items[action.id]

The Transaction maintains redo and undo stacks. Whenever a state modification is placed on the redo stack, a compensating modification is placed on the undo stack. Changes can be rolled back when desired, for example, in the event of a correctness violation.

class Transaction:

  def __init__(self, collection):
    self.collection = collection
    self.redo_stack = []
    self.undo_stack = []

  def get(self, id):
    return self.collection._items[id]

  def insert(self, id, item):
    redo = Insert(id, item)
    undo = Delete(id)
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)
        
  def update(self, id, part):
    item = self.collection._items[id]
    redo = Update(id, part)
    undo = Update(id, {key: getattr(item, key) for key in part})
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)

  def delete(self, id):
    item = self.collection._items[id]
    redo = Delete(id)
    undo = Insert(id, item)
    self.redo_stack.append(redo)
    self.undo_stack.append(undo)
    self.collection.apply(redo)

  def commit(self):
    self.redo_stack.clear()
    self.undo_stack.clear()
    
  def rollback(self):
    for action in reversed(self.undo_stack):
      self.collection.apply(action)
    self.redo_stack.clear()
    self.undo_stack.clear()

Adding Assertions to the Transaction Class

The Transaction class manages redo and undo stacks, enabling state modifications to be rolled back when necessary. Here, assertions enforce invariants during the rollback process. For instance:

Before applying an Insert, the item should not already exist.
Before applying an Update, the item should exist.
Before applying a Delete, the item should exist.

def rollback(self):
  for action in reversed(self.undo_stack):
        
    if isinstance(action, Insert):
      Assert(action.id not in self.collection._items, "...")
 
    elif isinstance(action, Update):
      Assert(action.id in self.collection._items, "...")

    elif isinstance(action, Delete):
      Assert(action.id in self.collection._items, "...")

    # Apply the undo action
    self.collection.apply(action)

  # Clear stacks after rollback
  self.redo_stack.clear()
  self.undo_stack.clear()

While the Collection class already raises exceptions for invalid operations, these are application-level exceptions intended to be caught and handled gracefully. Invariant violations, on the other hand, are catastrophic failures that indicate fundamental flaws in logic.

Assertions ensure these failures are surfaced immediately, avoiding scenarios where exception handling inadvertently masks the problem.

Conclusion

Now we can simply write a test case that executes random inserts, updates, and deletes on a collection－as long as the test case doesn’t halt (even if the test case throws an exception), the test passes: All invariants were met.

Happy Testing

The Weekend Read