Incremental Inductive Verification of Parameterized Timed Systems

T. Isenberg, ACM Transactions on Embedded Computing Systems (2017) 47:1-47:24.

Download
Restricted 90-a47-isenberg.pdf 584.87 KB
Journal Article
Author
Abstract
We propose and extend an approach for the verification of safety properties for parameterized timed systems modeled as networks of timed automata. For this task, we introduce an incremental workflow that is based on our algorithm IC3 with Zones. It proceeds in a cycle in which single models of the system are verified, and the verification results are employed for the reasoning about the entire system. Starting with the smallest instances, the verification of the safety property is carried out fast and efficient. On successful verification, the algorithm produces an inductive strengthening of the safety property. We reuse this result and try to reason about the entire parameterized timed system. To this end, we extrapolate the inductive strengthening into a candidate for the next-larger model. In case this candidate is a valid inductive strengthening for the next larger model, our main theorem reasons about all models of the parameterized timed system, stating that the safety property holds true for all models. Otherwise, the main cycle starts over with the verification of the next larger model. This workflow is iterated indefinitely, until able to reason about the entire parameterized timed system, until a counterexample trace is found, or until the single models become too large to be handled in the verification. We reuse the intermediate results in a Feedback-loop in order to accelerate the verification runs for the single models. Furthermore, we consider an extended formalism in comparison to our previous publications.
Publishing Year
Journal Title
ACM Transactions on Embedded Computing Systems
Issue
2
Page
47:1-47:24
LibreCat-ID

Cite this

Isenberg T. Incremental Inductive Verification of Parameterized Timed Systems. ACM Transactions on Embedded Computing Systems. 2017;(2):47:1-47:24. doi:10.1145/2984640
Isenberg, T. (2017). Incremental Inductive Verification of Parameterized Timed Systems. ACM Transactions on Embedded Computing Systems, (2), 47:1-47:24. https://doi.org/10.1145/2984640
@article{Isenberg_2017, title={Incremental Inductive Verification of Parameterized Timed Systems}, DOI={10.1145/2984640}, number={2}, journal={ACM Transactions on Embedded Computing Systems}, publisher={ACM}, author={Isenberg, Tobias}, year={2017}, pages={47:1-47:24} }
Isenberg, Tobias. “Incremental Inductive Verification of Parameterized Timed Systems.” ACM Transactions on Embedded Computing Systems, no. 2 (2017): 47:1-47:24. https://doi.org/10.1145/2984640.
T. Isenberg, “Incremental Inductive Verification of Parameterized Timed Systems,” ACM Transactions on Embedded Computing Systems, no. 2, pp. 47:1-47:24, 2017.
Isenberg, Tobias. “Incremental Inductive Verification of Parameterized Timed Systems.” ACM Transactions on Embedded Computing Systems, no. 2, ACM, 2017, pp. 47:1-47:24, doi:10.1145/2984640.
Main File(s)
File Name
90-a47-isenberg.pdf 584.87 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T13:13:04Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar