Distributed eXplode: A High-Performance Model Checking Engine to Scale Up State-Space Coverage

Nageswar Keetha, Leon Wu, Gail E. Kaiser, Junfeng YangColumbia 2008 · DOI

TL;DR

This paper introduces "Distributed eXplode," a parallelized version of the eXplode model checker designed to tackle the "state explosion" problem in software verification. By distributing the state-space search across multiple machines, it significantly speeds up the process and allows for greater coverage of complex software behaviors, making it a valuable tool for finding elusive bugs.

What Problem Does This Paper Address?

Model checking is a powerful technique for verifying software by exploring all possible execution paths (the "state space"). However, for large and complex systems, the sheer number of possible states can become astronomically large, a phenomenon known as "state explosion." This makes it practically impossible for traditional, single-machine model checkers to explore the entire state space within reasonable time and resource limits. Consequently, critical bugs, especially those triggered by rare "corner cases," can remain hidden. The existing eXplode tool, while lightweight and deterministic, suffers from this limitation due to its serialized, single-threaded approach.

Methods

The core innovation is the development of "Distributed eXplode," which parallelizes the state-space search. Instead of a single eXplode instance exploring states sequentially, multiple eXplode instances run concurrently on different host machines. Each instance explores a subset of the generated state space.

Key to this approach is eXplode's lightweight state representation. A state is not stored in its entirety but as a "signature" (a hash of the state data) and a "trace" (the sequence of choices made to reach that state). This allows states to be efficiently distributed and reconstructed on different machines. When a new state is generated, it's checked against a "seen-set" (to avoid redundant work) and then distributed to participating hosts based on a hash function. If an eXplode instance finds a bug, it logs the trace leading to the error. The system also includes a lightweight local service on each host to manage eXplode clients and dynamically adjust the number of instances based on workload.

Datasets

Not discussed in the paper. The evaluation uses a custom test harness with a simple example involving integer variables and a function that simulates memory and CPU usage.

Key Insights and Ideas

  • Lightweight State Representation is Crucial for Distribution: The paper highlights that eXplode's ability to represent states as a signature and trace, rather than the full state data, is fundamental to its distributed nature. This significantly reduces communication overhead, making it feasible to distribute states across a network.
  • Parallelism Directly Addresses State Explosion: The core insight is that by parallelizing the search, the time to explore a large state space can be drastically reduced, enabling more comprehensive coverage than what's possible with a single machine.
  • Reconstructing States from Traces is a Viable Strategy: While reconstructing states from traces is computationally expensive, it's presented as a necessary trade-off to handle large states that would be prohibitive to send directly over a network.
  • Dynamic Workload Management is Important: The paper acknowledges the challenge of workload balancing and proposes a local service to manage eXplode instances, suggesting future work on more sophisticated distributed hash table (DHT) techniques for better load balancing.

Key Results

The paper demonstrates that Distributed eXplode significantly outperforms the standalone version.

  • Speedup: Running with multiple instances (up to 6 in their experiments) resulted in several times faster execution. For instance, processing 10,000 states took 3 minutes 28 seconds for one instance, while two parallel instances processed roughly 10,000 states each in 3 minutes 43 seconds.
  • Coverage: The distributed approach allows for more state space coverage in less time, which is crucial for finding bugs in complex systems.

Limitations and Future Work

  • Multithreaded Applications: Distributed eXplode, in its current form, cannot directly test multithreaded applications with heavy global data interleavings. The authors suggest converting such applications into an inter-leavings graph using techniques like Lamport's happens-before graph, which can then be searched serially and subsequently parallelized.
  • Seen-Set Locking: When multiple eXplode instances run on the same host, locking and updating the local seen-set can become a bottleneck, limiting scalability.
  • Environment State: The current implementation focuses on in-memory data for checkpoints and does not capture the state of the environment (e.g., opened files, network connections).

Future work includes:

  • Incorporating process virtualization techniques for live process checkpointing and migration.
  • Exploring distributed hash table (DHT) techniques (like Chord) for more robust load balancing, avoiding local seen-set locks, and gracefully handling hosts joining/leaving.
  • Investigating techniques to handle multithreaded applications more directly.

Summary updated

Abstract

Model checking the state space (all possible behaviors) of software systems is a promising technique for verification and validation. Bugs such as security vulnerabilities, file storage issues, deadlocks and data races can occur anywhere in the state space and are often triggered by corner cases; therefore, it becomes important to explore and model check all runtime choices. However, large and complex software systems generate huge numbers of behaviors leading to 'state explosion'. eXplode is a lightweight, deterministic and depth-bound model checker that explores all dynamic choices at runtime. Given an application-specific test-harness, eXplode performs state search in a serialized fashion - which limits its scalability and performance. This paper proposes a distributed eXplode engine that uses multiple host machines concurrently in order to achieve more state space coverage in less time, and is very helpful to scale up the software verification and validation effort. Test results show that Distributed eXplode runs several times faster and covers more state space than the standalone eXplode.
BibTeX
@inproceedings{keetha2008distributed,
  author = {Nageswar Keetha and Leon Wu and Gail E. Kaiser and Junfeng Yang},
  title = {{Distributed eXplode: A High-Performance Model Checking Engine to Scale Up State-Space Coverage}},
  booktitle = {Columbia},
  year = {2008},
  doi = {10.7916/d8zg714d},
}
Figure