💻 computer science

Combining model checking with simulation-based techniques for protocol verification

This paper proposes a hybrid verification technique that overcomes the state space explosion problem in protocols like ABP and SWP by combining direct model checking on a highly abstracted Simple Communication Protocol (SCP) with simulation relations that formally link the more complex protocols to this simpler model.

Original authors: Takanori Ishibashi, Kazuhiro Ogata

Published 2026-07-21

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Takanori Ishibashi, Kazuhiro Ogata

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery in a city that keeps growing bigger every second. This is the world of computer science, specifically a field called formal verification. Think of it as a super-strict math game where we try to prove that a computer program or a communication protocol (the rules computers use to talk to each other) will never make a mistake. The goal is to check every single possible situation the computer could ever be in to make sure it stays safe.

The main tool detectives use for this is called model checking. It's like a robot that walks through every single room in a giant maze, checking if the walls are safe. But here's the catch: some mazes are so huge that they have more rooms than there are atoms in the universe. This problem is called state space explosion. If the maze gets too big, the robot gets stuck, runs out of memory, and gives up. It's like trying to count every grain of sand on a beach by picking them up one by one; you'll never finish.

To solve this, researchers often try to build a smaller, simpler map of the maze (called abstraction) or use a simulation. A simulation is like a shadow puppet show: if the shadow (the simple version) behaves correctly, then the real object (the complex version) should behave correctly too, provided the shadow is a faithful copy. The big question is: Can we combine the robot's thorough checking with the puppet show's simplicity to solve the biggest, most impossible mazes?

The Paper's Big Idea: The "Ladder" of Protocols

In this paper, Takanori Ishibashi and Kazuhiro Ogata from Japan propose a clever way to tackle the "too-big-to-check" problem. They focus on three communication protocols, which are just fancy rules for how computers send messages to each other. Think of these protocols as three different types of delivery services:

SCP (Simple Communication Protocol): This is the "Toy Version." It's very basic. Imagine a delivery service where you can only send one package at a time, and the truck has no storage space. It's tiny and easy to check.
ABP (Alternating Bit Protocol): This is the "Realistic Version." Now, the delivery service can handle a few more things, like keeping a small queue of packages and using a "yes/no" flag (a bit) to make sure messages aren't lost. It's bigger and harder to check.
SWP (Sliding Window Protocol): This is the "Mega-Complex Version." This is a high-speed delivery service where the truck can carry a whole fleet of packages at once (a "window" of messages) before waiting for a "got it!" signal. This creates a massive, exploding maze of possibilities that is impossible for a robot to check directly.

The authors' main finding is that you don't need to check the Mega-Complex Version directly. Instead, you can build a ladder of trust.

How the Ladder Works

The researchers used a computer language called Maude to write down the rules for these three protocols. They discovered that the Mega-Complex Version (SWP) is actually just a more detailed, "zoomed-in" version of the Realistic Version (ABP), which is itself a detailed version of the Toy Version (SCP).

Here is the magic trick they performed:

Check the Toy: First, they used the robot (model checking) to verify that the tiny Toy Version (SCP) is safe. Because it's so small, the robot finished the job in less than a second.
Build the Bridge (Simulation): Next, they proved mathematically that the Realistic Version (ABP) is just a "shadow" of the Toy Version. They showed that if the Toy Version is safe, the Realistic Version must be safe too, as long as the rules connecting them (called simulation relations) hold true. They used a mix of logic and computer commands to prove this connection without checking every single state of the Realistic Version.
Climb the Ladder: Finally, they did the same thing again. They proved that the Mega-Complex Version (SWP) is a "shadow" of the Realistic Version (ABP).

By chaining these connections together—SWP simulates ABP, and ABP simulates SCP—they proved that if the tiny Toy Version is safe, then the Mega-Complex Version is safe too.

The Results: Speed and Scale

The results were impressive. When the researchers tried to check the Mega-Complex Version (SWP) directly with a window size of 16 and message queues of 32, the robot crashed and gave up after an hour. The "state space explosion" was too much.

However, using their "Ladder" method:

They checked the tiny Toy Version in less than 1 second.
They proved the connections (the simulation relations) between the versions in less than 1 second each.
The entire verification for the massive, complex system was completed in under 3 seconds total.

The paper explicitly rules out the idea that you can just throw more computer power at the problem to solve it directly; for these large parameters, direct checking is simply infeasible. They also argue that while other methods exist, their approach is unique because it uses a standardized, semi-automated procedure within Maude to verify the connections, rather than relying on purely manual math proofs or complex, automated refinement loops that might get stuck.

Why It Matters

This isn't just a math puzzle. The authors show that by using what they call "domain knowledge" (understanding how these delivery services actually work), we can create these "Toy Versions" and "Bridges" to verify systems that were previously impossible to check. They even built a tool to help automate the boring parts of building these bridges, reducing the chance of human error.

In short, the paper proves that you don't need to count every grain of sand on the beach to know the beach is safe. If you can prove the sand in a small bucket is safe, and you can prove the bucket is just a smaller version of the beach, you've solved the mystery. This technique allows engineers to verify complex, real-world communication systems that were previously too big to trust.

Technical Summary: Combining Model Checking with Simulation-Based Techniques for Protocol Verification

Problem Statement
Model checking is a rigorous technique for verifying finite-state systems, yet it is frequently hindered by the state space explosion problem. As system parameters increase (e.g., channel capacities or window sizes), the reachable state space grows exponentially, rendering exhaustive verification infeasible. This paper addresses this limitation in the context of communication protocols, specifically the Alternating Bit Protocol (ABP) and the Sliding Window Protocol (SWP). While simpler abstractions like the Simple Communication Protocol (SCP) can be verified directly, increasing parameters in ABP and SWP causes the state space to exceed the capabilities of standard model checking tools, even with modern hardware.

Methodology
The authors propose a hybrid verification methodology that combines model checking with simulation relations to overcome state space explosion. The core theoretical foundation relies on the principle that if a concrete state machine $M$ is simulated by an abstract state machine $M_A$ , and $M_A$ satisfies an invariant property, then the corresponding invariant holds for $M$ .

The methodology is operationalized using the Maude rewriting logic language and involves two primary frameworks:

Direct Simulation Verification:
To verify a concrete protocol $M$ against an abstract protocol $M_A$ :
- Step 1: Perform direct model checking on the abstract machine $M_A$ to verify its invariant property.
- Step 2: Conjecture a simulation relation candidate $r$ between $M$ and $M_A$ . Prove that the invariant of $M$ is logically deducible from the invariant of $M_A$ under the assumption of $r$ , using static case splitting and reduction.
- Step 3: Demonstrate that $M$ is indeed simulated by $M_A$ . This involves verifying the simulation conditions (initial state correspondence and transition preservation) for all rewrite rules of $M$ .
- Implementation: Step 3 utilizes a three-command procedure in Maude:
  - srew: To find successor states in $M$ using fresh constants to represent arbitrary values.
  - red: To verify the simulation relation holds between the concrete and abstract states.
  - search: To confirm that the abstract machine can reach a corresponding state in zero or more steps.
- To ensure soundness despite using supersets of reachable states (due to undecidability of reachability), the authors employ Lemma 1, which proves that verifying the transition condition over these supersets is sufficient to guarantee the condition over the actual reachable states.
Composition of Simulation Relations:
For highly complex systems where a single abstraction is insufficient, the authors propose a hierarchical approach. This involves chaining simulation relations (e.g., $SWP \to ABP \to SCP$ ).
- The invariant of the most concrete system is deduced from the intermediate system, which is in turn deduced from the most abstract system.
- This allows the verification of systems with massive state spaces by leveraging the verified invariants of simpler, layered abstractions.

Key Contributions
The paper presents two main contributions:

A methodology combining model checking with simulation relations to verify systems where direct model checking fails due to state space explosion.
A methodology for the composition of simulation relations, enabling hierarchical verification by linking multiple layers of abstraction to handle even larger and more complex models.

Results and Case Studies
The authors evaluated their approach using three protocols: SCP, ABP, and SWP.

Case Study I (ABP):
- Challenge: Direct model checking of ABP with maxIndex = 64 and maxQueueLength = 32 resulted in a timeout (>3,600 seconds) due to state space explosion.
- Solution: The authors established a simulation relation from ABP to the simpler SCP.
- Outcome: The entire verification process (checking SCP, deducing the invariant, and verifying the simulation) was completed in less than 1 second per step. This confirmed that ABP satisfies its invariant property without exhaustive state exploration.
Case Study II (SWP):
- Challenge: SWP introduces window management and sequence numbers, creating a state space significantly larger than ABP, making direct verification impossible.
- Solution: The authors employed the composition of simulation relations: $SWP \to ABP \to SCP$ . They verified the simulation from SWP to ABP and combined it with the previously verified ABP-to-SCP relation.
- Outcome: The hierarchical approach successfully verified the invariant property of SWP (ensuring messages are received in order without loss or duplication) with parameters (windowSize = 16, maxQueueLength = 32) that would be infeasible for direct checking.

Significance and Claims
The paper claims that this approach effectively mitigates the state space explosion problem by shifting the computational burden from exhaustive state traversal to symbolic verification on smaller, abstract models. Key aspects of the significance include:

Scalability: The method allows for the formal verification of protocols with large parameters (e.g., window sizes and queue lengths) that are beyond the reach of direct model checking.
Reusability: Existing formal specifications can be reused as abstract models for new, more complex targets, significantly reducing verification effort.
Automation and Rigor: While constructing the abstract models and simulation relations requires manual domain knowledge, the validity of these relations is verified semi-automatically using standard Maude commands. The authors developed a support tool to automate case splitting and command execution, minimizing human error.
Distinction from Existing Work: Unlike Counterexample-Guided Abstraction Refinement (CEGAR), which is reactive and refines models based on spurious counterexamples, this approach is proactive, leveraging domain knowledge to construct strategic abstractions. This provides enhanced transparency and interpretability, as the simulation relations maintain a human-understandable mapping between concrete and abstract behaviors.

The authors conclude that by operationalizing simulation theory into a standardized sequence of Maude commands, they have bridged the gap between abstract theoretical relations and executable verification workflows, offering a practical and efficient pathway for verifying complex distributed systems.

Technical Summary: Combining Model Checking with Simulation-Based Techniques for Protocol Verification

More like this