Abstract
We present a technique designed to automatically compute predicate abstractions for dense real-timed models represented as networks of timed automata. We use the CIPM algorithm in our previous work which computes new invariants for timed automata control locations and prunes the model, to compute a predicate abstraction of the model. We do so by taking information regarding control locations and their newly computed invariants into account.
Introduction
Model checking is a powerful tool for finding bugs in hardware and software, but it suffers from the "state-space explosion" problem—the number of possible system states grows exponentially with the number of variables. This is especially true for real-time systems, where time is a continuous (dense) variable, adding infinite complexity. To manage this, researchers use predicate abstraction, which maps an infinite-state system to a simpler, finite-state model. However, this technique has historically faced two major hurdles: the manual effort required to define predicates through trial and error, and the risk of producing "spurious counterexamples" (false alarms) if the abstraction is too coarse.
Methodology: The CIPM Algorithm
The authors propose a two-step automated approach to overcome these hurdles. First, they employ the CIPM (Creating New Invariants by CIPM) algorithm. This tool analyzes the incoming transitions of every "location" (control state) in a timed automaton to strengthen local invariants—rules that must be true while in that state—and prune "idle" transitions that can never be taken.
Second, the method automates predicate generation by using the invariants discovered by CIPM. Instead of manual input, the system collects all invariants into a global set and defines abstract states as pairs of control locations and "cubes" (conjunctions of these predicates). Crucially, it only considers cubes that are satisfiable in conjunction with a location's specific invariant, preventing the creation of impossible abstract states.
Key Results: State-Space Reduction
The primary result of this approach is a dramatic reduction in the complexity of the abstract model. By identifying and removing unreachable transitions early, the authors prevent the abstraction from wasting resources on irrelevant parts of the state space. Furthermore, pairing specific control locations with their newly discovered invariants ensures the abstraction is fine enough to distinguish critical clock regions without being unnecessarily complex.
In one illustrative example, a naive abstraction would generate 24 abstract states, while a standard abstraction with basic checks would generate 12. The proposed method, by contrast, reduces the model to just 4 abstract states, as illustrated in the figure above. This reduction is vital for making the verification of complex, concurrent real-time systems computationally feasible.
Conclusion and Future Work
While the current prototype successfully automates the initial abstraction phase, the authors note that very coarse abstractions may still require a refinement scheme, such as Counterexample-Guided Abstraction Refinement (CEGAR). Integrating this automated method into a full refinement loop is a primary goal for future research. Additionally, while the method handles dense time, the underlying constraints must remain linear integer expressions to ensure decidability within the timed automaton framework.
Summary updated