Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel narrowing-based verification method for the formal analysis of real-time systems, addressing challenges posed by an unbounded number of agents and messages as well as infinite state spaces due to dense time. By integrating rewriting modulo SMT, logical variable narrowing, and a constraint store, the method enables symbolic representation and reasoning without imposing bounds on participating processes. The implementation, evaluated through the verification of a timed mutual exclusion protocol, demonstrates the framework's soundness and expressiveness in analyzing various real-time models, including parametric timed automata.
A groundbreaking verification method allows for the analysis of real-time systems with unbounded agents and infinite states, ensuring soundness without limiting the number of processes involved.
The formal analysis of real-time systems must address two dimensions of infiniteness: an unbounded number of agents and messages, and a potentially infinite state space induced by dense time. We present a novel narrowing-based verification method that deals with both dimensions. Our approach integrates (i) rewriting modulo SMT for symbolic representation of timing constraints, (ii) narrowing with logical variables to reason about systems with an unknown number of agents, and (iii) a constraint store over partially instantiated terms, in the style of constraint logic programming. We further introduce a folding mechanism that, under certain conditions, ensures termination of the symbolic analysis. The method has been implemented as an extension of the Maude rewriting engine. We evaluate the approach by verifying the correctness of a timed mutual exclusion protocol without imposing bounds on the number of participating processes. Moreover, we show that the framework uniformly supports the analysis of other real-time models, including parametric timed automata with unspecified components that our method can synthesize. Our results suggest that the proposed framework provides a sound and expressive basis for the symbolic verification of real-time rewrite theories.