Issue 32 - Deterministic Simulation Testing

Improving Deterministic Simulation Testing

Another weekend, another weekend read, this time about Improving Deterministic Simulation Testing

---

Deterministic Simulation Testing (DST) is a powerful tool in the software tester’s tool belt. At its core, DST involves dividing a system into two primary components:

1. The application

2. The environment

The application and the environment interact via a well defined protocol (API).

Deterministic Simulation Testing substitutes the environment with a simulator: DST repeatedly executes an application in a simulated environment under changing initial conditions, monitoring that the correctness constraints are maintained across executions.

The Principle of Determinism

The composition of application and simulator must yield a deterministic system, that is, given the same initial state, the system will always yield the same trace of external events.

Now the progression of the system is determined by the intial state of the system. In practice the minimal initial state is the seed for a pseudo random number generator that the simulator uses to drive the system forward.

With this you can reproduce an entire execution by restarting the system with the same random seed.

The Challenge

While DST is able to identify and reproduce bugs, its basic form has a limitation: The simulator performs a random walk through the state space. This randomness means DST cannot target “interesting” situations for deeper exploration.

For instance, many systems exhibit unique behaviors when in unbalanced states. While DST can eventually uncover bugs in these situations, it may require a significant number of simulation runs to:

• First encounter an unbalanced situation

• Then find a bug within that unbalanced state

This raises the question: Can we enhance DST to more efficiently explore critical states?

Understanding the Random Seed

To grasp the solution, we need to explore the concept of a random seed. Essentially, a random seed is equivalent to an infinite list of numbers:

random.seed(0) = [0.844, 0.757, 0.420, ...] 

Each number in this sequence corresponds to an action that transitions the system from its current state to the next:

(Init) -> 0.844 -> (S1) -> 0.757 -> (S2) -> 0.420 -> S3

To correlate two runs, we simply need to use the same prefix in the number sequence:

[0.844, 0.757, 0.420, 0.250, ...] 
[0.844, 0.757, 0.420, 0.404, ...]

This results in two runs, branching off the same state:

(Init) -> 0.844 -> (S1) -> 0.757 -> (S2) -> 0.420 -> S3 -> 0.250 -> S4.1
(Init) -> 0.844 -> (S1) -> 0.757 -> (S2) -> 0.420 -> S3 -> 0.250 -> S4.2

The Enhanced Solution

To address the limitations of basic Deterministic Simulation Testing, we introduce a predicate to the testing process. This predicate is designed to identify interesting situations, such as system imbalances.

Conclusion

This approach combines the strengths of deterministic testing with a targeted exploration, potentially uncovering hard-to-find bugs more efficiently.

If you are interested to explore Deterministic Simulation Testing, check out Resonate’s DST example.

Happy Reading