|
1 % |
|
2 \begin{isabellebody}% |
|
3 \def\isabellecontext{Base}% |
|
4 % |
|
5 \isadelimtheory |
|
6 % |
|
7 \endisadelimtheory |
|
8 % |
|
9 \isatagtheory |
|
10 % |
|
11 \endisatagtheory |
|
12 {\isafoldtheory}% |
|
13 % |
|
14 \isadelimtheory |
|
15 % |
|
16 \endisadelimtheory |
|
17 % |
|
18 \isamarkupsection{Case Study: Verified Model Checking% |
|
19 } |
|
20 \isamarkuptrue% |
|
21 % |
|
22 \begin{isamarkuptext}% |
|
23 \label{sec:VMC} |
|
24 This chapter ends with a case study concerning model checking for |
|
25 Computation Tree Logic (CTL), a temporal logic. |
|
26 Model checking is a popular technique for the verification of finite |
|
27 state systems (implementations) with respect to temporal logic formulae |
|
28 (specifications) \cite{ClarkeGP-book,Huth-Ryan-book}. Its foundations are set theoretic |
|
29 and this section will explore them in HOL\@. This is done in two steps. First |
|
30 we consider a simple modal logic called propositional dynamic |
|
31 logic (PDL)\@. We then proceed to the temporal logic CTL, which is |
|
32 used in many real |
|
33 model checkers. In each case we give both a traditional semantics (\isa{{\isaliteral{5C3C5475726E7374696C653E}{\isasymTurnstile}}}) and a |
|
34 recursive function \isa{mc} that maps a formula into the set of all states of |
|
35 the system where the formula is valid. If the system has a finite number of |
|
36 states, \isa{mc} is directly executable: it is a model checker, albeit an |
|
37 inefficient one. The main proof obligation is to show that the semantics |
|
38 and the model checker agree. |
|
39 |
|
40 \underscoreon |
|
41 |
|
42 Our models are \emph{transition systems}:\index{transition systems} |
|
43 sets of \emph{states} with |
|
44 transitions between them. Here is a simple example: |
|
45 \begin{center} |
|
46 \unitlength.5mm |
|
47 \thicklines |
|
48 \begin{picture}(100,60) |
|
49 \put(50,50){\circle{20}} |
|
50 \put(50,50){\makebox(0,0){$p,q$}} |
|
51 \put(61,55){\makebox(0,0)[l]{$s_0$}} |
|
52 \put(44,42){\vector(-1,-1){26}} |
|
53 \put(16,18){\vector(1,1){26}} |
|
54 \put(57,43){\vector(1,-1){26}} |
|
55 \put(10,10){\circle{20}} |
|
56 \put(10,10){\makebox(0,0){$q,r$}} |
|
57 \put(-1,15){\makebox(0,0)[r]{$s_1$}} |
|
58 \put(20,10){\vector(1,0){60}} |
|
59 \put(90,10){\circle{20}} |
|
60 \put(90,10){\makebox(0,0){$r$}} |
|
61 \put(98, 5){\line(1,0){10}} |
|
62 \put(108, 5){\line(0,1){10}} |
|
63 \put(108,15){\vector(-1,0){10}} |
|
64 \put(91,21){\makebox(0,0)[bl]{$s_2$}} |
|
65 \end{picture} |
|
66 \end{center} |
|
67 Each state has a unique name or number ($s_0,s_1,s_2$), and in each state |
|
68 certain \emph{atomic propositions} ($p,q,r$) hold. The aim of temporal logic |
|
69 is to formalize statements such as ``there is no path starting from $s_2$ |
|
70 leading to a state where $p$ or $q$ holds,'' which is true, and ``on all paths |
|
71 starting from $s_0$, $q$ always holds,'' which is false. |
|
72 |
|
73 Abstracting from this concrete example, we assume there is a type of |
|
74 states:% |
|
75 \end{isamarkuptext}% |
|
76 \isamarkuptrue% |
|
77 \isacommand{typedecl}\isamarkupfalse% |
|
78 \ state% |
|
79 \begin{isamarkuptext}% |
|
80 \noindent |
|
81 Command \commdx{typedecl} merely declares a new type but without |
|
82 defining it (see \S\ref{sec:typedecl}). Thus we know nothing |
|
83 about the type other than its existence. That is exactly what we need |
|
84 because \isa{state} really is an implicit parameter of our model. Of |
|
85 course it would have been more generic to make \isa{state} a type |
|
86 parameter of everything but declaring \isa{state} globally as above |
|
87 reduces clutter. Similarly we declare an arbitrary but fixed |
|
88 transition system, i.e.\ a relation between states:% |
|
89 \end{isamarkuptext}% |
|
90 \isamarkuptrue% |
|
91 \isacommand{consts}\isamarkupfalse% |
|
92 \ M\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{28}{\isacharparenleft}}state\ {\isaliteral{5C3C74696D65733E}{\isasymtimes}}\ state{\isaliteral{29}{\isacharparenright}}set{\isaliteral{22}{\isachardoublequoteclose}}% |
|
93 \begin{isamarkuptext}% |
|
94 \noindent |
|
95 This is Isabelle's way of declaring a constant without defining it. |
|
96 Finally we introduce a type of atomic propositions% |
|
97 \end{isamarkuptext}% |
|
98 \isamarkuptrue% |
|
99 \isacommand{typedecl}\isamarkupfalse% |
|
100 \ {\isaliteral{22}{\isachardoublequoteopen}}atom{\isaliteral{22}{\isachardoublequoteclose}}% |
|
101 \begin{isamarkuptext}% |
|
102 \noindent |
|
103 and a \emph{labelling function}% |
|
104 \end{isamarkuptext}% |
|
105 \isamarkuptrue% |
|
106 \isacommand{consts}\isamarkupfalse% |
|
107 \ L\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}state\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ atom\ set{\isaliteral{22}{\isachardoublequoteclose}}% |
|
108 \begin{isamarkuptext}% |
|
109 \noindent |
|
110 telling us which atomic propositions are true in each state.% |
|
111 \end{isamarkuptext}% |
|
112 \isamarkuptrue% |
|
113 % |
|
114 \isadelimtheory |
|
115 % |
|
116 \endisadelimtheory |
|
117 % |
|
118 \isatagtheory |
|
119 % |
|
120 \endisatagtheory |
|
121 {\isafoldtheory}% |
|
122 % |
|
123 \isadelimtheory |
|
124 % |
|
125 \endisadelimtheory |
|
126 \end{isabellebody}% |
|
127 %%% Local Variables: |
|
128 %%% mode: latex |
|
129 %%% TeX-master: "root" |
|
130 %%% End: |