×

zbMATH — the first resource for mathematics

Automatic abstraction refinement for timed automata. (English) Zbl 1141.68431
Raskin, Jean-François (ed.) et al., Formal modeling and analysis of timed systems. 5th international conference, FORMATS 2007, Salzburg, Austria, October 3–5, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-75453-4/pbk). Lecture Notes in Computer Science 4763, 114-129 (2007).
Summary: We present a fully automatic approach for counterexample guided abstraction refinement of real-time systems modelled in a subset of timed automata. Our approach is implemented in the Moby/RT tool environment, which is a CASE tool for embedded system specifications. Verification in Moby/RT is done by constructing abstractions of the semantics in terms of timed automata which are fed into the model checker Uppaal. Since the abstractions are over-approximations, absence of abstract counterexamples implies a valid result for the full model. Our new approach deals with the situation in which an abstract counterexample is found by Uppaal. The generated abstract counterexample is used to construct either a concrete counterexample for the full model or to identify a slightly refined abstraction in which the found spurious counterexample cannot occur anymore. Hence, the approach allows for a fully automatic abstraction refinement loop starting from the coarsest abstraction towards an abstraction for which a valid verification result is found. Nontrivial case studies demonstrate that this approach computes small abstractions fast without any user interaction.
For the entire collection see [Zbl 1138.68007].

MSC:
68Q45 Formal languages and automata
68Q60 Specification and verification (program logics, model checking, etc.)
Software:
CMC; Uppaal
PDF BibTeX XML Cite
Full Text: DOI