Timed Automata Robustness Analysis via Model Checking

Jaroslav Bendík, Ahmet Sencan, Ebru Aydin Gol, Ivana Cerná

TL;DR

This paper introduces novel methods for analyzing and tuning timed automata (TA) to handle uncertainties in timing constants during the design phase. They propose techniques to identify minimal sets of constraints to relax for reachability specifications and maximal sets of constraints to remove for safety specifications, offering valuable guidance for designers.

What Problem Does This Paper Address?

Timed automata (TA) are powerful for modeling time-critical systems, and model-checking tools can verify if a TA meets a specification. However, a common challenge in the design process is the uncertainty of exact timing constants. Designers might build a TA with the correct structure but struggle to fine-tune the timing to satisfy specifications. Even if a TA initially meets a specification, slight changes can lead to violations. Current model-checking tools often fail to provide actionable feedback on how to fix these issues. This paper addresses this by providing methods to analyze and tune TA constraints, making the design process more robust to timing uncertainties for reachability and safety properties.

Methods

The paper proposes a two-step approach for both reachability and safety specifications.

For reachability specifications, they first identify a Minimal Sufficient Reduction (MSR), which is a minimal set of clock constraints that, when removed, makes a target location reachable. Then, instead of just removing constraints, they relax the thresholds of these MSR constraints. Two methods are presented for relaxation:

  1. Mixed Integer Linear Programming (MILP): Finds a minimal relaxation along a specific witness path.
  2. Parameter Synthesis: Uses a tool to find a minimal relaxation that guarantees reachability across all witness paths, offering a globally optimal solution but being more computationally expensive.

For safety specifications, they introduce the concept of a Minimal Guarantee (MG), which is a minimal set of constraints that must be kept to ensure a safety property (e.g., avoiding unsafe locations). They then relax the constraints within this MG. Two scenarios are considered:

  1. Maximizing Total Change: Parametrizes each constraint in the MG and uses parameter synthesis to find a valuation that maximizes the total change in timing constants while preserving safety.
  2. Finding Robustness Degree: Identifies a single relaxation value that can be applied to all constraints in the MG, ensuring safety is maintained.

The core algorithms involve iterative identification and shrinking of reductions (sets of constraints) and the use of verifiers and parameter synthesis tools.

Datasets

The paper evaluates their methods on two collections of benchmarks:

  1. Scheduler Automata: A set of 24 test cases generated based on a machine scheduling problem, with varying numbers of clocks, paths, and intermediate locations.
  2. Benchmarks from Literature: 10 examples from existing research, including networks of TAs, covering both safety and reachability specifications.

Key Insights and Ideas

  • MSRs and MGs as Design Guidance: The concepts of MSRs and MGs provide concrete, minimal sets of constraints to focus on when tuning TA models, offering a more targeted approach than brute-force modification.
  • Relaxation vs. Removal: Simply removing constraints might be too drastic. Relaxing their thresholds offers a more nuanced way to satisfy specifications while staying closer to the original model.
  • Dual Problems for Reachability and Safety: The paper elegantly frames the problem for reachability (finding what to remove to enable something) and safety (finding what to keep to prevent something) as dual problems, using MSRs and MGs respectively.
  • Trade-offs in Relaxation Methods: The MILP approach for relaxation is faster but path-specific, while parameter synthesis is more computationally intensive but guarantees global optimality. This allows designers to choose based on their needs.
  • Symbolic Representation for Efficiency: To handle the exponential number of possible constraint combinations, the paper uses symbolic (Boolean formula) representations for sets of reductions, enabling efficient management.

Key Results

The paper's tool, Tamus, was implemented and evaluated.

  • MSR and MG Computation: Tamus could generate minimum MSRs and MGs for all benchmark models, often within seconds, even for large systems.
  • Relaxation Performance:
    • For MSR relaxation, the MILP method was found to be faster than parameter synthesis.
  • Parameter synthesis for MSR relaxation provided globally optimal solutions but was more computationally expensive.
  • For MG analysis, Imitator (a parameter synthesis tool) efficiently found robustness degrees and maximal total changes for most models.
  • Comparison with Existing Tools: The paper compares their approach with Imitator, showing that while Imitator can solve some problems, it often struggles with minimizing the number of modified constraints or times out on complex cases.

Limitations and Future Work

  • Computational Complexity: While Tamus is efficient, the underlying problem of finding MSRs and MGs can still be computationally intensive, especially for very large models. The paper notes that the performance depends on the number of simple clock constraints.
  • Heuristics for Choices: The choice of which reduction to shrink or which constraint to test can affect the overall performance. The authors mention that developing suitable heuristics for these choices is a direction for future work.
  • Networks of TAs: While the methods can be extended to networks of TAs, the current implementation of Tamus only supports single TAs.
  • Domain-Agnostic vs. Domain-Specific: The paper acknowledges that while domain-agnostic MSMP algorithms exist, domain-specific solutions (like theirs) are generally more efficient.
  • Future Work: The authors suggest developing better heuristics for making choices within their algorithms and extending the tool to handle networks of TAs.

Summary updated

Abstract

Timed automata (TA) have been widely adopted as a suitable formalism to model time-critical systems. Furthermore, contemporary model-checking tools allow the designer to check whether a TA complies with a system specification. However, the exact timing constants are often uncertain during the design phase. Consequently, the designer is often able to build a TA with a correct structure, however, the timing constants need to be tuned to satisfy the specification. Moreover, even if the TA initially satisfies the specification, it can be the case that just a slight perturbation during the implementation causes a violation of the specification. Unfortunately, model-checking tools are usually not able to provide any reasonable guidance on how to fix the model in such situations. In this paper, we propose several concepts and techniques to cope with the above mentioned design phase issues when dealing with reachability and safety specifications.
BibTeX
@article{bendik2022timed,
  author = {Jaroslav Bendík and Ahmet Sencan and Ebru Aydin Gol and Ivana Cerná},
  title = {{Timed Automata Robustness Analysis via Model Checking}},
  journal = {Log. Methods Comput. sci},
  year = {2022},
  doi = {10.46298/lmcs-18(3:12)2022},
}
Figure