Concurrent software verification with states, events, and deadlocks |
| |
Authors: | Sagar Chaki Edmund Clarke Joël Ouaknine Natasha Sharygina Nishant Sinha |
| |
Affiliation: | (1) Software Engineering Institute, Carnegie Mellon University, Pittsburgh, USA;(2) Computer Science Department, Carnegie Mellon University, Pittsburgh, USA;(3) Oxford University Computing Laboratory, Oxford, UK |
| |
Abstract: | We present a framework for model checking concurrent software systems which incorporates both states and events. Contrary
to other state/event approaches, our work also integrates two powerful verification techniques, counterexample-guided abstraction
refinement and compositional reasoning. Our specification language is a state/event extension of linear temporal logic, and
allows us to express many properties of software in a concise and intuitive manner. We show how standard automata-theoretic
LTL model checking algorithms can be ported to our framework at no extra cost, enabling us to directly benefit from the large
body of research on efficient LTL verification.
We also present an algorithm to detect deadlocks in concurrent message-passing programs. Deadlock- freedom is not only an
important and desirable property in its own right, but is also a prerequisite for the soundness of our model checking algorithm.
Even though deadlock is inherently non-compositional and is not preserved by classical abstractions, our iterative algorithm
employs both (non-standard) abstractions and compositional reasoning to alleviate the state-space explosion problem. The resulting
framework differs in key respects from other instances of the counterexample-guided abstraction refinement paradigm found
in the literature.
We have implemented this work in the magic verification tool for concurrent C programs and performed tests on a broad set
of benchmarks. Our experiments show that this new approach not only eases the writing of specifications, but also yields important
gains both in space and in time during verification. In certain cases, we even encountered specifications that could not be
verified using traditional pure event-based or state-based approaches, but became tractable within our state/event framework.
We also recorded substantial reductions in time and memory consumption when performing deadlock-freedom checks with our new
abstractions. Finally, we report two bugs (including a deadlock) in the source code of Micro-C/OS versions 2.0 and 2.7, which
we discovered during our experiments.
This research was sponsored by the National Science Foundation (NSF) under grants no. CCR-9803774 and CCR-0121547, the Office
of Naval Research (ONR) and the Naval Research Laboratory (NRL) under contract no. N00014-01-1-0796, the Army Research Office
(ARO) under contract no. DAAD19-01-1-0485, and was conducted as part of the Predictable Assembly from Certifiable Components
(PACC) project at the Software Engineering Institute (SEI).
This article combines and builds upon the papers (CCO+04) and (CCOS04).
Received December 2004
Revised July 2005
Accepted July 2005 by Eerke A. Boiten, John Derrick, Graeme Smith and Ian Hayes |
| |
Keywords: | Concurrent software Model checking Temporal logic States and events Deadlock Compositional reasoning Counterexample-guided abstraction refinement |
本文献已被 SpringerLink 等数据库收录! |
|