10123
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{Base}%
|
17056
|
4 |
%
|
|
5 |
\isadelimtheory
|
|
6 |
%
|
|
7 |
\endisadelimtheory
|
|
8 |
%
|
|
9 |
\isatagtheory
|
|
10 |
%
|
|
11 |
\endisatagtheory
|
|
12 |
{\isafoldtheory}%
|
|
13 |
%
|
|
14 |
\isadelimtheory
|
|
15 |
%
|
|
16 |
\endisadelimtheory
|
10123
|
17 |
%
|
10867
|
18 |
\isamarkupsection{Case Study: Verified Model Checking%
|
10395
|
19 |
}
|
11866
|
20 |
\isamarkuptrue%
|
10123
|
21 |
%
|
|
22 |
\begin{isamarkuptext}%
|
10362
|
23 |
\label{sec:VMC}
|
10867
|
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
|
10795
|
27 |
state systems (implementations) with respect to temporal logic formulae
|
10867
|
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
|
10178
|
30 |
we consider a simple modal logic called propositional dynamic
|
11458
|
31 |
logic (PDL)\@. We then proceed to the temporal logic CTL, which is
|
10867
|
32 |
used in many real
|
40406
|
33 |
model checkers. In each case we give both a traditional semantics (\isa{{\isaliteral{5C3C5475726E7374696C653E}{\isasymTurnstile}}}) and a
|
10123
|
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
|
10867
|
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
|
10123
|
38 |
and the model checker agree.
|
|
39 |
|
10133
|
40 |
\underscoreon
|
10123
|
41 |
|
11458
|
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:
|
10133
|
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}
|
11458
|
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.
|
10123
|
72 |
|
11458
|
73 |
Abstracting from this concrete example, we assume there is a type of
|
10281
|
74 |
states:%
|
10133
|
75 |
\end{isamarkuptext}%
|
17175
|
76 |
\isamarkuptrue%
|
|
77 |
\isacommand{typedecl}\isamarkupfalse%
|
|
78 |
\ state%
|
10133
|
79 |
\begin{isamarkuptext}%
|
|
80 |
\noindent
|
11458
|
81 |
Command \commdx{typedecl} merely declares a new type but without
|
10983
|
82 |
defining it (see \S\ref{sec:typedecl}). Thus we know nothing
|
10281
|
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
|
10867
|
88 |
transition system, i.e.\ a relation between states:%
|
10133
|
89 |
\end{isamarkuptext}%
|
17175
|
90 |
\isamarkuptrue%
|
|
91 |
\isacommand{consts}\isamarkupfalse%
|
40406
|
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}}%
|
10133
|
93 |
\begin{isamarkuptext}%
|
|
94 |
\noindent
|
27015
|
95 |
This is Isabelle's way of declaring a constant without defining it.
|
10133
|
96 |
Finally we introduce a type of atomic propositions%
|
10123
|
97 |
\end{isamarkuptext}%
|
17175
|
98 |
\isamarkuptrue%
|
|
99 |
\isacommand{typedecl}\isamarkupfalse%
|
40406
|
100 |
\ {\isaliteral{22}{\isachardoublequoteopen}}atom{\isaliteral{22}{\isachardoublequoteclose}}%
|
10123
|
101 |
\begin{isamarkuptext}%
|
|
102 |
\noindent
|
10133
|
103 |
and a \emph{labelling function}%
|
10123
|
104 |
\end{isamarkuptext}%
|
17175
|
105 |
\isamarkuptrue%
|
|
106 |
\isacommand{consts}\isamarkupfalse%
|
40406
|
107 |
\ L\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}state\ {\isaliteral{5C3C52696768746172726F773E}{\isasymRightarrow}}\ atom\ set{\isaliteral{22}{\isachardoublequoteclose}}%
|
10123
|
108 |
\begin{isamarkuptext}%
|
|
109 |
\noindent
|
10133
|
110 |
telling us which atomic propositions are true in each state.%
|
10123
|
111 |
\end{isamarkuptext}%
|
17175
|
112 |
\isamarkuptrue%
|
17056
|
113 |
%
|
|
114 |
\isadelimtheory
|
|
115 |
%
|
|
116 |
\endisadelimtheory
|
|
117 |
%
|
|
118 |
\isatagtheory
|
|
119 |
%
|
|
120 |
\endisatagtheory
|
|
121 |
{\isafoldtheory}%
|
|
122 |
%
|
|
123 |
\isadelimtheory
|
|
124 |
%
|
|
125 |
\endisadelimtheory
|
10123
|
126 |
\end{isabellebody}%
|
|
127 |
%%% Local Variables:
|
|
128 |
%%% mode: latex
|
|
129 |
%%% TeX-master: "root"
|
|
130 |
%%% End:
|