Themen für das Seminar: Model Checking

Themen für das Seminar:
Model Checking
2. Februar 2004
Inhaltsverzeichnis
1 Allgemein
1.1 Model Checking und Temporal Logics . . . . . . . . . . .
1.2 Binary Decision Diagrams and Symbolic Model Checking
1.3 From model checking to a temporal proof . . . . . . . . .
1.4 Partial Order Reduction, Equivalences, Preorders . . . .
.
.
.
.
2
2
2
2
2
2 Software Model Checking
2.1 Symbolic Model Checking of Software . . . . . . . . . . . . . .
2.2 Space-Reduction Strategies . . . . . . . . . . . . . . . . . . . .
2.3 Automatically Verifying Concurrent Queue Algorithms . . . .
3
3
3
4
3 Parallel and Distributed Model Checking
3.1 Parallel Model Checking for LTL, CTL∗ , and Lµ . . . . . . . .
3.2 Distributed Branching Bisimulation Reduction of State Spaces
4
4
5
1
.
.
.
.
.
.
.
.
1
Allgemein
Der Begriff Model Checking faßt automatische Verifikationsverfahren zusammen, bei denen die Übereinstimmung eines gegebenen Systems oder Programms mit einer Spezifikation überprüft wird. Die Spezifikation ist oft als logische Formel gegeben, beispielsweise als temporallogische Formel. Besonders
interessant ist es, Model-Checking-Techniken auf verteilte und nebenläufige
Systeme anzuwenden.
1.1
Model Checking und Temporal Logics
Kapitel 3 und 4 aus [CGP99].
1.2
Binary Decision Diagrams and Symbolic Model
Checking
Kapitel 5 und 6 aus [CGP99].
1.3
From model checking to a temporal proof
Doron Peled und Lenore Zuck [PZ01]. In Proceedings of the 8th international
SPIN workshop on Model checking of software, Toronto, Canada, 2001. Vom
Netz der Uni Frankfurt aus über http://portal.acm.org verfügbar.
Zusammenfassung
Model checking is used to automatically verify temporal properties
of finite state systems. It is usually considered to be ‘sucessful’, when
an error, in the form of a counterexample to the checked property,
is found. We present the dual approach, where, in the presence of no
counterexample, we automatically generate a proof that the checked
property is satisfied by the given system. Such a proof can be used
to obtain intuition about the verified system. This approach can be
added as a simple extension to existing model checking tools.
1.4
Partial Order Reduction, Equivalences, Preorders
Kapitel 10 und 11 aus [CGP99].
2
2
2.1
Software Model Checking
Symbolic Model Checking of Software
Flavio Lerda, Nishant Sinha und Michael Theobald [LST03]. In Electronic Notes in Theoretical Computer Science, Volume 89, Issue 3, September
2003. Vom Netz der Uni Frankfurt aus über http://www1.elsevier.com/gejng/31/29/23/141/23/30/89.3.008.pdf verfügbar.
Zusammenfassung
Model checking is a popular formal verification technique for both
software and hardware. The verification of concurrent software predominantly employs explicit-state model checkers, such as Spin, that use
partial-order reduction as a main technique to deal with large state
spaces efficiently. In the hardware domain, the introduction of symbolic model checking has been considered a breakthrough, allowing
the verification of systems clearly out-of-reach of any explicit-state
model checker. This paper introduces ImProviso, a new algorithm for
model checking of software that efficiently combines the advantages
of partial-order reduction with symbolic exploration. ImProviso uses
implicit BDD representations for both the state space and the transition relation together with a new implicit in-stack proviso for efficient
partial-order reduction. The new approach is inspired by the Twophase partial-order reduction algorithm for explicit-state model checking.
Initial experimental results show that the proposed algorithm improves the existing symbolic model checking approach and can be used to
tackle problems that are not tractable using explicit-state methods.
2.2
Space-Reduction Strategies for Model Checking
Dynamic Software
Matthew Dwyer Robby, John Hatcliff und Radu Iosif [RDHI03]. In Electronic Notes in Theoretical Computer Science, Volume 89, Issue 3, September
2003. Vom Netz der Uni Frankfurt aus über http://www1.elsevier.com/gejng/31/29/23/141/23/31/89.3.009.pdf verfügbar.
Zusammenfassung
Effective model-checking of modern object-oriented software systems requires providing support for program features such as dynamically created threads, heap-allocated objects and garbage collection. These features have often proven problematic to treat using many
previous model-checking frameworks that do not provide sophisticated
3
heap representations and optimizations. In this paper, we define a flexible framework for combined heap and thread symmetry reductions
in explicit-state model checking that can be tuned to trade run-time
overhead for precision. In addition, we describe various strategies for
duplication-reducing state-space encodings for object-oriented heap
structures. We have implemented these techniques in Bogor (our extensible software model-checking framework), and we present empirical data to support the effectiveness of these memory reductions on a
collection of realistic examples and to demonstrate that they improve
upon previous approaches. These techniques, formalized in a group
theoretic framework, can be applied to any non-deterministic heap
object diagram.
2.3
Automatically Verifying Concurrent Queue Algorithms
Eran Yahav und Mooley Sagiv [YS03]. In Electronic Notes in Theoretical Computer Science, Volume 89, Issue 3, September 2003.
Vom Netz der Uni Frankfurt aus über http://www1.elsevier.com/gejng/31/29/23/141/23/31/89.3.006.pdf verfügbar.
Zusammenfassung
Concurrent FIFO queues are a common component of concurrent
systems. Using a single shared lock to prevent concurrent manipulations of queue contents reduces system concurrency. Therefore, many
algorithms were suggested to increase concurrency while maintaining
the correctness of queue manipulations. This paper shows how to automatically verify partial correctness of concurrent FIFO queue algorithms using existing abstract interpretation techniques. In particular,
we verify all the safety properties originally specified for two concurrent queue algorithms without imposing an a priori bound on the
number of allocated objects and threads.
3
3.1
Parallel and Distributed Model Checking
Parallel Model Checking for LTL, CTL∗ , and Lµ
Martin Leucker, Rafal Somla und Michael Weber [LSW03]. In Electronic
Notes in Theoretical Computer Science, Volume 89, Issue 3, September
2003. Vom Netz der Uni Frankfurt aus über http://www1.elsevier.com/gejng/31/29/23/141/47/25/89.1.003.pdf verfügbar.
Zusammenfassung
4
We describe a parallel model-checking algorithm for the fragment
of the my-calculus that allows one alternation of minimal and maximal
fixed-point operators. This fragment is also known as L2µ . Since LTL
and CTL∗ can be encoded in this fragment, we obtain parallel model
checking algorithms for practically important temporal logics.
Our solution is based on a characterization of this problem in terms
of two-player games. We exhibit the structure of their game graphs
and show that we can iteratively work with game graphs that have
the same special structure as the ones obtained for L1µ -formulae. Since
good parallel algorithms for colouring game-graphs for L1µ -formulae
exist, it is straightforward to implement this algorithm in parallel and
good run-time results can be expected.
3.2
Distributed Branching Bisimulation Reduction of
State Spaces
Stefan Blom und Simona Orzan [BO03]. In Electronic Notes in
Theoretical Computer Science, Volume 89, Issue 3, September 2003.
Vom Netz der Uni Frankfurt aus über http://www1.elsevier.com/gejng/31/29/23/141/47/31/89.1.009.pdf verfügbar.
Zusammenfassung
Enumerative model checking tools are limited by the size of the
state space to which they can be applied. Reduction modulo branching
bisimulation usually results in a much smaller state space and therefore enables model checking of much larger state spaces. We present
an algorithm for reducing state spaces modulo branching bisimulation
which is suitable for distributed implementation. The target architecture is a cluster with a high bandwidth interconnect. The algorithm
is based on partition refinement and it works on transition systems
which contain cycles of invisible steps, without eliminating strongly
connected components first. To avoid fine grained parallelism, the algorithm refines the whole partition instead of just a single block in
the partition. We prove correctness and also present some experimental results obtained with single threaded and distributed prototypes.
Literatur
[BO03]
Blom, Stefan und Simona Orzan: Distributed Branching Bisimulation Reduction of State Spaces. In: Brim, Lubos und Orna
Grumberg (Herausgeber): Electronic Notes in Theoretical Computer Science, Band 89. Elsevier, 2003.
5
[CGP99] Clarke, Jr., Edmund M., Orna Grumberg und Doron A.
Peled: Model checking. MIT Press, 1999.
[LST03]
Lerda, Flavio, Nishant Sinha und Michael Theobald:
Symbolic Model Checking of Software. In: Cook, Byron, Scott
Stoller und Willem Visser (Herausgeber): Electronic Notes
in Theoretical Computer Science, Band 89. Elsevier, 2003.
[LSW03] Leucker, Martin, Rafal Somla und Michael Weber: Parallel Model Checking for LTL, CTL∗ , and Lµ . In: Brim, Lubos
und Orna Grumberg (Herausgeber): Electronic Notes in Theoretical Computer Science, Band 89. Elsevier, 2003.
[PZ01]
Peled, Doron und Lenore Zuck: From model checking to a
temporal proof. In: Proceedings of the 8th international SPIN workshop on Model checking of software, Seiten 1–14. Springer-Verlag
New York, Inc., 2001.
[RDHI03] Robby, Matthew Dwyer, John Hatcliff und Radu Iosif:
Space-Reduction Strategies for Model Checking Dynamic Software. In: Cook, Byron, Scott Stoller und Willem Visser
(Herausgeber): Electronic Notes in Theoretical Computer Science,
Band 89. Elsevier, 2003.
[YS03]
Yahav, Eran und Mooley Sagiv: Automatically Verifying
Concurrent Queue Algorithms. In: Cook, Byron, Scott Stoller und Willem Visser (Herausgeber): Electronic Notes in
Theoretical Computer Science, Band 89. Elsevier, 2003.
6