Abstract Interpretation and Partition Refinement for Model Checking

Author: Dennis Dams
Language of presentation: English
Advisor: Dr. Rob Gerth
Promoters: Prof.Dr. Jos Baeten, Prof.Dr. Werner Damm
Date of defence: July 1st, 1996
Institution granting degree: Eindhoven University of Technology, The Netherlands


Jump to:


Additional info:

[BIBTeX entry]

If you are interested in receiving a copy, send me a mail.


Summary:

(Note: This text contains some simple LaTeX formatting commands.)

Properties of a program that are expressed in a temporal logic may be verified by checking whether they are satisfied in the transition graph, called the (concrete) model, representing all possible behaviours of the program. This approach to verification is called \emph{model checking}. The size of the model, which is usually exponential in the size of the program, forms a limiting factor in the application of model checking. \emph{Abstraction techniques} may alleviate this ``state-explosion problem''. The idea is that the transition graph is reduced by ignoring certain aspects of the program, resulting in an abstract model. If every formula from a collection $L$ that is satisfied in this abstract model also holds in the full concrete model, then $L$ is said to be (weakly) \emph{preserved}. If in addition we have that falsehood of an $L$-formula in the abstraction implies that it also does not hold in the concrete model, we speak of \emph{strong} preservation. After the introductory Chapters 1 and 2, Chapter 3 gives a general introduction to abstraction theories.

In Chapter 4, we present a number of preservation results for (fragments of) $CTL^*$ (\emph{Computation Tree Logic}), which is a temporal logic in which a variety of reactive properties may be specified. In particular, we show how weak preservation of full $CTL^*$ may be obtained by interpreting the universal and existential path-quantifiers along different transition relations of \emph{mixed transition systems}. Besides preservation results, an abstraction technique should come with a method to construct abstract models in an effective way. We illustrate how \emph{abstract interpretation} of the program text may be used for this purpose. Towards the end of the chapter we suggest how abstract interpretation may be adapted to construct strongly preserving abstractions.

Chapters 5 and 6 deal with the construction of strongly preserving abstract models. Chapter 5 investigates under which conditions an abstract model strongly preserves a given collection $L \subseteq CTL^*$ of properties. From these conditions, an algorithm is derived that repeatedly splits up the abstract states until strong preservation is attained. For various subsets of $CTL^*$ such partition refinement algorithms are developed in more detail. The splittings that are performed by these algorithms are directly based on the form of the formulae to be strongly preserved --- whence the term \emph{logical partition refinement}.

For a few fragments of $CTL^*$, partition refinement algorithms exist which are based on the observation that the equivalence relations that the fragments induce (two states are equivalent if they satisfy the same formulae), coincide with \emph{behavioural} equivalences like bisimulation. Chapter 6 shows how these algorithms may be seen as instantiations of a generic scheme, by parametrising them with the notion of \emph{splitter}. A new fragment of $CTL^*$ is then considered, leading to another instantiation of the behavioural partition refinement algorithm. The induced equivalence of this fragment is coarser than stuttering equivalence (branching bisimulation) --- yet, we expect that its expressive power is still sufficient for many specifications occurring in practice.


Table of Contents:

  Acknowledgements........................................................vii

  1 Program Analysis and Verification.......................................1
    1.1 Program Verification................................................2
    1.2 Program Analysis....................................................4
    1.3 Scope of the Thesis.................................................5
    1.4 Related Work........................................................8
        1.4.1 Program analysis and Abstract Interpretation..................8
        1.4.2 Program verification.........................................10

  2 Preliminaries..........................................................13
    2.1 Relations and Functions............................................14
    2.2 Lattice and Fixpoint Theory........................................15
        2.2.1 Orderings....................................................15
        2.2.2 Functions over posets........................................16
        2.2.3 Galois connections...........................................17
    2.3 Temporal Logic.....................................................18
        2.3.1 Nextless fragments...........................................20
    2.4 Transition Systems.................................................21
        2.4.1 Interpretation of CTL$^{*}$..................................22
        2.4.2 Behavioural preorders and equivalences.......................25
        2.4.3 Model checking...............................................27

  3 Abstraction and Preservation...........................................29
    3.1 Introduction.......................................................30
        3.1.1 Abstract Interpretation......................................30
        3.1.2 Overview of the chapter......................................34
    3.2 Preservation Results...............................................34
        3.2.1 Frameworks for weak preservation.............................35
        3.2.2 Strong preservation..........................................49
    3.3 Abstract Semantics.................................................50
        3.3.1 Approximation of fixpoints...................................51
    3.4 Related Work.......................................................54
    3.5 Concluding Remarks.................................................55

  4 Abstract Interpretation of Nondeterministic Systems....................57
    4.1 Introduction.......................................................58
        4.1.1 Overview of the chapter......................................58
    4.2 Abstract Kripke Structures.........................................59
        4.2.1 Valuation of literals........................................60
        4.2.2 Abstract initial states......................................61
        4.2.3 Abstract transition relations................................62
    4.3 Abstract Interpretation of Programs................................67
        4.3.1 Example: dining mathematicians...............................69
    4.4 Approximations.....................................................75
        4.4.1 Abstract interpretation gives approximations.................79
        4.4.2 Dining mathematicians continued (I)..........................82
    4.5 Optimal Abstract Interpretations...................................83
        4.5.1 Conditions on the abstract domain............................83
        4.5.2 Adapting the abstract interpretation.........................87
    4.6 Computing Approximations...........................................87
    4.7 Practical Application..............................................89
    4.8 Refinement of Abstractions.........................................92
        4.8.1 Abstraction families.........................................93
    4.9 Related Work......................................................100
        4.9.1 Comparing the simulation-based and
                Galois-insertion approach.................................103
        4.9.2 [KDG95a]: An application....................................107
    4.10 Concluding Remarks...............................................112

  5 Logical Partition Refinement..........................................115
    5.1 Introduction......................................................116
        5.1.1 Overview of the chapter.....................................119
    5.2 Preliminaries.....................................................120
    5.3 Companions........................................................122
    5.4 A Generic Splitting Algorithm.....................................126
    5.5 Splitting for $\forall$CTL........................................129
        5.5.1 Termination.................................................130
    5.6 Splitting for $\varphi \in \forall$CTL............................136
        5.6.1 Example.....................................................138
    5.7 Related Work......................................................141
    5.8 Concluding Remarks................................................142

  6 Logics, Equivalences and Behavioural Partition Refinement.............145
    6.1 Introduction......................................................146
        6.1.1 Logics and equivalences.....................................147
        6.1.2 Equivalences and partition refinement algorithms............148
        6.1.3 Overview of the chapter.....................................148
    6.2 CTL$^{*}$, CTL, and Bisimulation..................................149
    6.3 Nextless CTL$^{*}$ and CTL........................................152
        6.3.1 The Next operator...........................................152
        6.3.2 CTL$^{*}$(U), CTL(U) and stuttering equivalence.............155
    6.4 Partition Refinement Algorithms...................................163
    6.5 Flat CTL and CTL$^{*}$............................................167
        6.5.1 flat$^{-}$CTL(U) and flat equivalence.......................170
        6.5.2 flatCTL$^{*}(U) and flat star equivalence...................173
    6.6 Partition Refinement for Flat Logics..............................178
    6.7 Related Work......................................................179
    6.8 Concluding Remarks................................................180

  7 In Conclusion.........................................................183
    7.1 Research Goal & Approach..........................................184
    7.2 Conclusions.......................................................185
        7.2.1 Weak preservation...........................................186
        7.2.2 Strong preservation.........................................187
    7.3 Looking Ahead.....................................................189

  Bibliography............................................................191

  Samenvatting (Summary in Dutch).........................................211

  Index...................................................................215

  Curriculum Vitae........................................................219