In the mid-1990s, formal verification of concurrent systems was well-established for reasoning about event ordering, but incorporating quantitative time remained a significant challenge. Engineers needed tools that could handle specific delays—for instance, ensuring a response occurs exactly 5ms after a request. Furthermore, standard verification tools often provided binary "pass/fail" results without explaining why a design failed. This paper introduces an extension to the EPSILON verification tool, which utilizes Timed Modal Specifications (TMS) to verify real-time systems and automatically generate diagnostic information for failed designs.
Methodology: Timed Modal Specifications
The core of the approach lies in Timed Modal Specifications (TMS), a real-time extension of process algebras like the Calculus of Communicating Systems (CCS). TMS introduces a critical distinction between required and allowed behaviors.
- Modalities: Unlike traditional models where all transitions are mandatory, TMS allows for "loose" specifications. Required events must occur, while allowed events may occur but are not mandatory. This flexibility enables a single specification to represent an entire family of potential implementations.
- Refinement ($\triangleleft$): A design $S$ is considered a refinement of a specification $T$ if $S$ performs only the actions allowed by $T$ and fulfills all actions required by $T$.
- EPSILON Tool: This automated tool supports three levels of refinement: strong (strict timing), observational (abstracting internal "silent" steps), and time-abstracting (logical sequence only).
Diagnostic Generation and Insights
The primary innovation is the automated generation of diagnostic feedback. When a refinement check fails, EPSILON produces a logical formula—based on Hennessy-Milner logic—that pinpoints the error. For example, a formula like [acc](del)tt indicates that after an 'accept' action, the system enters a state where a 'delivery' action is expected but cannot be performed. This provides developers with a clear "counter-example" for debugging.
A key insight of TMS is the "power of looseness." By using dashed lines in graphical representations to denote allowed but non-mandatory time progression, designers can specify acceptable ranges for delays (e.g., delivery between 2ms and 5ms) rather than fixed points.
Case Study: Timed Stop-and-Wait Protocol
The authors evaluate their methodology using a Timed Stop-and-wait Protocol. This case study highlights how real-time safety often depends on the precise balancing of system parameters, such as the sender’s timeout ($X$), the medium's delay ($Y$), and the receiver’s turnaround time ($Z$).
Key findings from the protocol analysis include:
- Safety Verification: The tool proved that the protocol remains safe only if the medium's timeout ($Y$) exceeds the receiver's delay ($Z$). If $Y < Z$, EPSILON correctly identifies a potential deadlock.
- Performance Bounds: The sender's timeout ($X$) was shown to define the upper bound for the system's end-to-end delay.
- Error Detection: In a retransmitting sender model, the tool identified a subtle bug where a timeout that is too aggressive ($X \le Z$) leads to duplicate message delivery. The tool provided a specific logical property to explain this failure.
Conclusion
While the paper provides an intuitive overview, it acknowledges limitations such as the informal presentation of underlying algorithms and the potential for state-space explosion in larger systems. Future work aims to refine the synthesis of diagnostic formulas to make them even more accessible to practicing engineers.
Summary updated