CISPA
Browse

Parameterized Verification of Disjunctive Timed Networks.

Download (1.01 MB)
conference contribution
posted on 2025-04-22, 08:36 authored by Étienne André, Paul EichlerPaul Eichler, Swen JacobsSwen Jacobs, Shyam Lal KarraShyam Lal Karra
We introduce new techniques for the parameterized verification of disjunctive timed networks (DTNs), i.e., networks of timed automata (TAs) that communicate via location guards that enable a transition only if there is another process in a given location. This computational model has been considered in the literature before, example applications are gossiping clock synchronization protocols or planning problems. We address the minimum-time reachability problem (Minreach) in DTNs, and show how to efficiently solve it based on a novel zone graph algorithm. We further show that solving Minreach allows us to construct a summary TA capturing exactly the possible behaviors of a single TA within a DTN of arbitrary size. The combination of these two results enables the parameterized verification of DTNs, while avoiding the construction of an exponential-size cutoff system required by existing results. Additionally, we develop sufficient conditions for solving Minreach and parameterized verification problems even in certain cases where locations that appear in location guards can have clock invariants, a case that has usually been excluded in the literature. Our techniques are also implemented, and experiments show their practicality.

History

Editor

Dimitrova R ; Lahav O ; Wolff S

Primary Research Area

  • Reliable Security Guarantees

Name of Conference

International Conference on Verification Model Checking and Abstract Interpretation (VMCAI)

CISPA Affiliation

  • Yes

Journal

VMCAI (1)

Volume

14499

Page Range

124-146

Publisher

Springer

Open Access Type

  • Not Open Access

BibTeX

@inproceedings{André:Eichler:Jacobs:Karra:2024, title = "Parameterized Verification of Disjunctive Timed Networks.", author = "André, Étienne" AND "Eichler, Paul" AND "Jacobs, Swen" AND "Karra, Shyam Lal", editor = "Dimitrova, Rayna" AND "Lahav, Ori" AND "Wolff, Sebastian", year = 2024, month = 1, journal = "VMCAI (1)", pages = "124--146", publisher = "Springer", issn = "0302-9743", doi = "10.1007/978-3-031-50524-9_6" }