Timed Modal Specification —Theory and Tools

Kārlis Čerāns, Jens Chr. Godskesen, Kim G. LarsenBRICS 1997 · DOI

Abstract

This paper presents the theory of Timed Modal Specifications (TMS) and its implementation in the Epsilon tool. TMS extends real-timed process calculi to allow for loose or partial specifications through the use of "may" and "must" modalities. This framework supports a formal notion of refinement, generalizing the classical notion of bisimulation, and enables compositional verification of real-time systems. We demonstrate the practical application of TMS through the compositional verification of a train crossing example using the Epsilon tool.

Introduction

The design and verification of real-time systems require formalisms that can handle both concurrency and strict temporal constraints. Traditional process calculi, while powerful, often suffer from a lack of flexibility. They typically describe exact system behaviors, making it difficult to express the "looseness" or partiality required during the early stages of the engineering lifecycle. In such systems, a specification might be too rigid, treating any deviation in timing as a failure, even when such deviations are acceptable in practice.

To bridge this gap, we introduce Timed Modal Specifications (TMS). TMS allows engineers to write partial specifications that can be incrementally refined into concrete implementations. This approach supports the standard engineering practice of stepwise refinement, where high-level requirements are gradually transformed into detailed designs.

The TMS Framework: May and Must Modalities

The core of TMS is the extension of real-timed process calculi with two distinct types of transitions:

  • Must ($\Box$): Transitions that are required. Any valid implementation of the specification must be able to perform these actions.
  • May ($\diamond$): Transitions that are allowed. An implementation can choose to include these actions or omit them.

By definition, every "must" transition is also a "may" transition. This duality allows for a formal refinement ordering ($\triangleleft$). A specification $S$ is said to refine $T$ if $S$ is more "constrained"—meaning it requires more mandatory actions (more "musts") and permits fewer optional actions (fewer "mays") than $T$. This refinement relation generalizes the classical notion of bisimulation, providing a mathematical foundation for incremental system development.

Compositional Verification

One of the primary advantages of the TMS framework is its support for compositional verification. TMS specifications can be combined using the constructs of real-time calculus. We define "time-sensitive" notions of refinement that are preserved by these constructs, allowing for a "divide and conquer" approach to verification. If a component $A$ is shown to refine specification $A'$, it can be safely integrated into a larger system without the need to re-verify the entire assembly. This property is essential for scaling formal methods to complex, modular systems.

Furthermore, the theory includes "weak" refinements that allow designers to abstract away from internal system actions ($\tau$) or specific timing details when they are not relevant to the current level of analysis.

The Epsilon Tool

To provide automated support for TMS, we developed Epsilon, a tool for verifying refinements. Epsilon is a timed extension of the Tav system and is designed to handle the challenges of a dense time domain (non-negative reals).

Since checking an infinite number of real-valued time points is impossible, Epsilon utilizes symbolic region graphs. This technique partitions the infinite state space of time into a finite number of manageable regions, enabling automatic verification. Epsilon supports several types of refinement, including strong, weak, time-abstracted, and trajectory-step refinements.

Case Study: The Train Crossing

The utility of TMS and Epsilon is demonstrated through the verification of a classic formal methods benchmark: the Train Crossing. The system consists of four interacting components: a train, a track crossing, a gate, and a controller.

Using Epsilon, we modeled these components and verified that a specific implementation (with fixed timing delays) correctly refines a high-level safety specification. For example, we proved that the gate remains closed whenever a train is inside the crossing. The analysis revealed that safety is highly sensitive to internal timing parameters; the system is only safe if the sum of the controller's delay and the gate's closing time is strictly less than the train's approach time ($U + X < A$).

Conclusion

Timed Modal Specifications offer a flexible and mathematically rigorous framework for the design of real-time systems. By incorporating "may" and "must" modalities, TMS supports the natural engineering process of stepwise refinement. The Epsilon tool further demonstrates that these theoretical concepts can be effectively automated, providing a practical path for the compositional verification of complex temporal systems.

Summary updated

Abstract

In this paper we present the theory of Timed Modal Specifications (TMS) together with its implementation, the tool Epsilon. TMS and Epsilon are timed extensions of respectively Modal Specifications [Lar90, LT88] and the Tav system [GLZ89, BLS92].&lt;br /&gt;The theory of TMS is an extension of real-timed process calculi with the specific aim of allowing loose or partial specifications. Looseness of specifications allows implementation details to be left out, thus allowing several and varying implementations. We achieve looseness of specifications by introducing two modalities to transitions of specifications: a may and a must modality. This allows us to define a notion of refinement, generalizing in a natural way the classical notion of bisimulation. Intuitively, the more must-transitions and the fewer may-transitions a specification has, the finer it is. Also, we introduce notions of refinements abstracting from time and/or internal computation.&lt;br /&gt;TMS specifications may be combined with respect to the constructs of the real-time calculus [Wan90]. "Time-sensitive" notions of refinements that are preserved by these constructs are defined,&lt;br /&gt; thus enabling compositional verification. Epsilon provides automatic tools for verifying refinements. We apply Epsilon to a compositional verification of a train crossing example.
BibTeX
@inproceedings{cerans1997timed,
  author = {Kārlis Čerāns and Jens Chr. Godskesen and Kim G. Larsen},
  title = {{Timed Modal Specification —Theory and Tools}},
  booktitle = {BRICS},
  year = {1997},
  doi = {10.7146/brics.v4i11.18802},
}
Figure