LTL Model-Checking for Dynamic Pushdown Networks Communicating via Locks

摘要

A Dynamic Pushdown Network (DPN) is a set of pushdown systems (PDSs) where each process can dynamically create new instances of PDSs. DPNs are a natural model of multi-threaded programs with (possibly recursive) procedure calls and thread creation. Extension of DPNs with locks allows processes to synchronize via locks. Thus, DPNs with locks are a well adapted formalism to model multi-threaded programs that synchronize via locks. Therefore, it is important to have model-checking algorithms for DPNs with locks. However, in general, the model-checking problem of DPNs with locks against reachability properties, and hence Linear Temporal Logic (LTL), is undecidable. To obtain de-cidable results, we study in this work the model-checking problem of DPNs with well-nested locks against single-indexed Linear Temporal Logic (LTL) properties of the form E f i s.t. f i is a LTL formula interpreted over the PDS i. We show that this model-checking problem is decidable. We propose an automata-based approach for computing the set of configurations of a DPN with locks that satisfy the corresponding single-indexed LTL formula.