Automatic Verification of Real-Timed Systems Using EPSILON

Jens Chr. Godskesen, Kim G. Larsen, Arne SkouBRICS 1994 · DOI

Abstract: In this paper we report on an application and extension of the theory of Timed Modal Specifications (TMS) and its associated verification tool EPSILON. The novel feature with which EPSILON has been extended is the ability to automatically generate diagnostic information in cases of erroneous refinement steps.

Introduction

Verifying real-time systems is a complex task because correctness is intrinsically linked to quantitative timing constraints rather than just the logical sequence of events. Historically, formal methods often treated time qualitatively (e.g., event A must precede event B). However, for concurrent systems where safety depends on specific millisecond-level timeouts, automated quantitative verification is essential.

A significant hurdle in existing verification tools is their "black box" nature. When a tool determines that a system implementation fails to meet its specification, it often provides no explanation. This paper introduces an extension to the EPSILON tool that synthesizes diagnostic information, helping designers pinpoint exactly where timing dependencies fail during refinement.

Methodology: Timed Modal Specifications

The framework is built upon Timed Modal Specifications (TMS), a real-time extension of process algebras like CCS. TMS allows for "loose" specifications by distinguishing between two types of transitions:

  1. Required transitions: Actions that must be available in any valid implementation.
  2. Allowed transitions: Actions that may be available, providing flexibility for different implementation strategies.
A Timed Modal Specification diagram showing required and allowed transitions for a parameterized component.

The EPSILON tool, an extension of the TAV (Tools for Automatic Verification) system, automates the check for refinement orderings. The core innovation is the Diagnostic Synthesis engine. When a refinement check fails, the tool generates a logical formula that characterizes the discrepancy. For instance, a formula like [acc]{del}tt indicates that after an 'accept' action, the specification requires a 'delivery' to be possible, but the implementation fails to provide it.

Case Study: Timed Stop-and-wait Protocol

To evaluate the tool, the authors modeled a Timed Stop-and-wait Protocol. This system consists of three main components: a sender ($S$), a receiver ($R$), and a faulty medium ($M$). The protocol's behavior is governed by three critical timing parameters:

  • $X$: The sender's retransmission timeout.
  • $Y$: The medium's internal timeout.
  • $Z$: The receiver's processing delay.
The state-transition architecture of the Timed Stop-and-wait Protocol, showing the interaction between Sender (S), Medium (M), and Receiver (R).

Key Results and Diagnostics

Using EPSILON, the authors identified several critical safety conditions for the protocol:

  • Deadlock Prevention: The protocol is safe only if the medium's timeout is greater than the receiver's delay ($Y > Z$). If $Y < Z$, the medium might time out and drop a message while the receiver is still processing it. EPSILON correctly identified this deadlock risk and provided the logical formula explaining the failure.
  • Retransmission Integrity: For a sender that retransmits, the sender's timeout must be greater than the receiver's delay ($X > Z$). If $X < Z$, the tool demonstrated that the system could erroneously deliver the same message twice, generating a diagnostic trace to prove the violation.
  • Performance Bounds: The analysis confirmed that the sender's timeout period ($X$) effectively sets the upper bound for the total input-to-output delay of the system.

Conclusion

The extension of EPSILON to include diagnostic synthesis transforms formal verification from a simple pass/fail check into a powerful debugging tool for real-time systems. While the current output is logical formulas, future work aims to translate these into human-readable traces or graphical counter-examples. Additionally, further research is required to address the state-space explosion problem to ensure these techniques scale to industrial-sized systems.

Summary updated

Abstract

In this paper we report on an application and extension of the theory of &lt;em&gt;Timed Modal Specifications&lt;/em&gt; (TMS) and its associated verification tool E&lt;small&gt;PSILON&lt;/small&gt;. The novel feature with which E&lt;small&gt;PSILON&lt;/small&gt; has been extended is the ability to automatically generate &lt;em&gt; diagnostic information&lt;/em&gt; in cases of erroneous refinement steps.
BibTeX
@inproceedings{godskesen1994automatic,
  author = {Jens Chr. Godskesen and Kim G. Larsen and Arne Skou},
  title = {{Automatic Verification of Real-Timed Systems Using EPSILON}},
  booktitle = {BRICS},
  year = {1994},
  doi = {10.7146/brics.v1i19.21648},
}
Figure