Verifying a Sliding Window Protocol in mCRL

Wan Fokkink, Jan Friso Groote, Jun Pang, Bahareh Badban, Jaco van de PolVU 2004

TL;DR

This paper presents a formal verification of a sliding window protocol (SWP) using the µCRL process algebra. The authors prove that their SWP, with an arbitrary finite window size and modulo arithmetic for sequence numbers, is equivalent to a simple FIFO queue of the same capacity. This work represents a significant milestone in formally verifying complex communication protocols.

What Problem Does This Paper Address?

Sliding window protocols (SWPs) are fundamental to reliable data transmission over lossy channels, ensuring efficient bandwidth usage. However, their formal verification has proven surprisingly difficult, even for seemingly simple variants. Previous attempts often focused on simplified cases (e.g., single-bit sequence numbers or fixed window sizes) or only proved safety properties. This paper tackles the challenge of formally verifying a general SWP with arbitrary finite window sizes and modulo arithmetic for sequence numbers, aiming to prove both safety and liveness properties.

Methods

The authors employ the µCRL (Micro Concurrent Process Language) process algebra, which combines process algebra with equational abstract data types. Their verification strategy involves a series of transformations:

  1. Linearization: Eliminating parallel operators from the µCRL specification.
  2. Argument Stripping: Removing data parameters from communication actions.
  3. Modulo Arithmetic Elimination: Getting rid of modulo operations to simplify the specification.

The core of the proof relies on established techniques in process algebra:

  • Branching Bisimulation: A strong form of behavioral equivalence used to compare process specifications.
  • Axiomatic Theory: The proof is conducted entirely within the formal framework of µCRL's axioms and data type properties.
  • Proof Principles: The paper utilizes sum elimination, CL-RSP (for proving strong bisimilarity), and the cones and foci method (for proving branching bisimilarity).
  • Model Checking (PVS): All lemmas for data types and invariants, as well as correctness proofs, were checked using the PVS theorem prover.

Datasets

Not discussed in the paper. The paper focuses on formal verification of a protocol specification, not on empirical evaluation with datasets.

Key Insights and Ideas

  • SWP as a Queue: A key insight is that a correctly functioning SWP with modulo arithmetic and a finite window size behaves identically to a simple FIFO queue of the same capacity. This simplifies the verification target significantly.
  • Complexity of Modulo Arithmetic: The paper highlights the inherent difficulty in formally reasoning about protocols that use modulo arithmetic for sequence numbers. The verification process requires careful elimination of these modulo operations.
  • Milestone in Verification: The authors emphasize that this work, taking 13 years to complete, represents a significant achievement in process algebraic verification, demonstrating the power of the methodology for complex systems.
  • Importance of Data Types and Invariants: The rigorous proof relies heavily on establishing and proving properties of the underlying data types (Booleans, Natural Numbers, Buffers) and system invariants, which are crucial for maintaining correctness throughout the transformations.

Key Results

The paper successfully proves that their µCRL specification of a sliding window protocol with an arbitrary finite window size $n$ and sequence numbers modulo $2n$ is branching bisimilar to a FIFO queue of capacity $2n$. This implies both safety (no data loss or corruption) and liveness (messages are eventually delivered) properties of the protocol, under the assumption of fairness. The paper provides a detailed formal proof using a combination of process algebraic techniques and theorem proving.

Limitations and Future Work

  • Channel Capacity: The current verification assumes lossy channels with a capacity of one. The authors mention that ongoing research aims to extend the verification to a setting with channels of unbounded capacity.
  • Fairness Assumption: The liveness properties are proven under the assumption of fairness, which is a standard assumption in process algebra but might not always hold in real-world systems.
  • Manual Proof: While parts were checked with PVS, the core proof involves significant manual reasoning, which can be intricate and time-consuming.

The future work mentioned is the extension to unbounded channel capacity.

Summary updated

Abstract

We prove the correctness of a sliding window protocol with an arbitrary finite window size n and sequence numbers modulo 2n. The correctness consists of showing that the sliding window protocol is branching bisimilar to a queue of capacity 2n. The proof is given entirely on the basis of an axiomatic theory.
BibTeX
@inproceedings{fokkink2004verifying,
  author = {Wan Fokkink and Jan Friso Groote and Jun Pang and Bahareh Badban and Jaco van de Pol},
  title = {{Verifying a Sliding Window Protocol in mCRL}},
  booktitle = {VU},
  year = {2004},
}
Figure