Marius Minea

Partial Order Reduction for Verification of Timed Systems Degree Type: Ph.D. in Computer Science
Advisor(s): Edmund Clarke
Graduated: December 1999

Abstract:

This dissertation presents solutions for the application of partial order methods to the verification of timed systems, with the purpose of reducing the size of the explored state space.

Timed systems, which rely on timing information to operate correctly, pose special difficulties for automatic verification. Not only does the size of their state space grow exponentially with the number of components, as in any concurrent system, but some of the history of past transitions becomes part of the timed state. This hinders the use of partial order reduction, a technique which is applicable if different transition interleavings lead to the same state. We have given a partial order reduction algorithm for systems described as networks of timed automata, which preserves formulas in a timed extension of linear temporal logic. The algorithm is based on a modified local-time semantics, which allows individual automata to execute independently except for synchonization transitions.

More generally, we have investigated the application of partial order reduction in a continuous-time model whose semantics is defined in terms of timed traces. We show how to separate the causal dependence of transitions from their time ordering due to concurrency and how this leads to the application of partial order reduction. As particular instances of this framework we obtain improved algorithms for timed event/level structures and time Petri nets, as well as our algorithm for timed automata.

We have evaluated the performance of our partial order reduction approach on several timed automata benchmarks. The resulting reduction in space stems from two sources: the local-time model reduces the number of generated time regions, while the partial order techniques applied from the domain of untimed systems reduce the explored control state space.

Thesis Committee:
Edmund M. Clarke (Chair)
Randal E. Bryant
Jeannette M. Wing
Doron Peled (Bell Laboratories)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Formal verification, model checking, partial order reduction, timed systems