TL;DR
This paper introduces "time-darts," a novel data structure for representing the state space of timed automata, offering a more compact and efficient alternative to existing methods like Difference Bound Matrices (DBMs). Time-darts enable faster and more memory-efficient verification of real-time systems, particularly for models with larger constants.
What Problem Does This Paper Address?
Verifying real-time systems, often modeled as timed automata, is crucial for ensuring their correct behavior. A key challenge in this process is the efficient representation and exploration of the system's state space. Traditional methods like DBMs, while powerful, suffer from quadratic or cubic time complexity for operations, leading to state-space explosion, especially when dealing with large constants in the system's timing constraints. Discretization offers a linear-time alternative but can also lead to state-space explosion. This paper aims to bridge this gap by proposing a new data structure that balances compactness and efficiency, outperforming existing methods in various experimental scenarios.
Methods
The core contribution is the introduction of time-darts, a new symbolic data structure for representing configurations of timed automata. A time-dart is a triple (γ, w, p) where:
γis an "anchor point," a clock valuation where at least one clock is zero.wis a "waiting distance," representing the minimum time delay before a state can transition.pis a "passed distance," representing the maximum time delay before a state can transition.
The paper defines a reachability algorithm (Algorithm 2) that operates on these time-darts. This algorithm iteratively explores reachable states by selecting time-darts from a "passed-waiting list" and computing successor states. Crucially, it uses a bounded discrete semantics and an "extrapolation" technique to ensure termination and correctness, allowing it to represent large sets of states with a single time-dart. The algorithm's operations are designed to have linear time complexity with respect to the number of clocks.
Datasets
The paper does not introduce new datasets. Instead, it evaluates its proposed method on existing benchmarks and problem instances commonly used in the field of timed automata verification:
- Task Graph Scheduling (TGS): Scaled by the number of tasks.
- Bridge Crossing Vikings: A modified version of a standard planning problem.
- Train Level Crossing: Generated from timed-arc Petri nets.
- Fischer's Protocol: A classic mutual exclusion problem, scaled by the maximum constant (MC).
Key Insights and Ideas
- Compact State Representation: Time-darts offer a significantly more compact representation of timed automaton states compared to complete discretization, especially for models with large constants. A single time-dart can represent an arbitrary large set of states.
- Linear Time Complexity: Operations on time-darts are designed to have linear time complexity in the number of clocks, a significant advantage over DBMs which have quadratic or cubic complexity.
- Scalability with Constants: The time-dart approach demonstrates superior performance and scalability when dealing with larger timing constants in the models, a weakness of traditional discretization methods.
- Practical Alternative: For certain classes of timed automata (e.g., those with counting features or non-strict guards), time-darts offer a practical and efficient alternative to DBM-based engines, which can struggle with state-space explosion even for moderately sized constants.
Key Results
The experimental results consistently show that the time-dart reachability algorithm outperforms the naive discrete reachability algorithm in terms of both verification time and memory usage.
- Speedup: In many cases, time-darts achieved significant speedups. For instance, in the Fischer's protocol experiment, time-darts could verify models with a maximum constant of 66, while full discretization was limited to a maximum constant of 18 within the same time limit.
- Memory Reduction: The number of discovered and stored states was consistently lower with the time-dart approach, indicating a more efficient state-space exploration. For example, in the T155 Task Graph Scheduling model with 10 tasks, time-darts discovered 4,700,607 states and stored 347,136, whereas naive discretization discovered 1,740,066 states but stored 136,639 (though the naive approach was OOM for 8 tasks).
- Scalability: The advantage of time-darts becomes more pronounced as the constants in the timed automata models increase.
Limitations and Future Work
- Limitations:
- The current implementation is in Python, which is an interpreted language and may not reflect the full potential performance compared to compiled languages.
- The algorithms were implemented without further optimizations like partial order reduction, symmetry reduction, or advanced extrapolation techniques.
- The current approach uses a single global maximum constant (MC), which might not be optimal for all models.
- Future Work:
- Implement the time-dart algorithm in C++ with additional optimizations, including considering local constants instead of a global one.
- Extend the framework to handle liveness properties.
- Investigate the verification of models with clock invariants and diagonal guards.
- Explore federations of time-darts to further reduce sensitivity to scaling constants.
Summary updated