CHAPTER 4 MODEL CHECKING OF FINITE-STATE SYSTEMS One way to show that a program or system meets the designer’s specification is to manually construct a proof using axioms and inference rules in a deductive system such as temporal logic, a first-order logic capable of expressing relative ordering of events. This traditional, manual approach to concurrent program verification is tedious and error-prone even for small programs. For finite-state concurrent systems and systems that can be represented as such, we can use model checking instead of proof construction to check their correctness relative to their specifications. In the model checking approach, we represent the concurrent system as a finite- state graph, which can be viewed as a finite Kripke structure. The specification or safety assertion is expressed in propositional temporal logic formulas. We can then check whether the system meets its specification using an algorithm called a model checker. In other words, the model checker determines whether the Kripke structure is a model of the formula(s). Several model checkers are available and they vary in code and run-time complexity. Here we describe one of the first model checkers, pro- posed by [Clarke, Emerson, and Sistla, 1986], and a more efficient symbolic model checker, developed later by [Burch et al., 1990a]. In Clarke, Emerson, and Sistla’s [1986] approach, the system to be checked is represented by a labeled finite-state graph and the specification is written in a propo- sitional, branching-time temporal logic called computation tree logic (CTL). The use of linear-time temporal logic, which can express fairness properties, is ruled out since a model checker such as logic has high complexity. Instead, fairness requirements are moved into the semantics of CTL. In this chapter, we use the terms program and system interchangeably. 86 Real-Time Systems: Scheduling, Analysis, and Verification. Albert M. K. Cheng Copyright ¶ 2002 John Wiley & Sons, Inc. ISBN: 0-471-18406-3 SYSTEM SPECIFICATION 87 4.1 SYSTEM SPECIFICATION To construct the finte-state graph corresponding to a given concurrent program, we have to thoroughly understand the program and determine the effect of each state- ment or action in the program. If a flow or control graph has been used in the design of the program, we can use it to determine the effect of each statement. One way to construct the finite-state graph is to begin with the initial state labeled with the initial values of all program variables or attributes, which are called labels here. Then for each possible next statement, we execute the statement and examine any change to one or more program variables. We construct a new state if it is different from any existing state. Note that sometimes we need to construct a new state even if its labels are the same as those in an existing state because the sequence of actions leading to the present state is different from that leading to the existing state. A directed edge is constructed from the state we are considering to the new state. We repeat this state and edge construction step for each new state until there are no states to consider. An example program and the corresponding finite-state graph in adjacency matrix form are shown in section 4.4.1. For other systems that are not computer programs, we can perform a similar graph construction. First, we identify the state attributes that are relevant in the system to be specified in the CTL structure. Example. In a railroad crossing scenario, the train has several possible positions: BEFORE-APPROACH means that the train has not been detected by the crossing sensor so it is far from the crossing, APPROACH means that the train has been de- tected by the crossing sensor and is approaching the crossing, BEFORE-CROSSING means that the train is near the crossing but is not on it yet, CROSSING means that the train is crossing and thus occupying the crossing intersection, and AFTER- CROSSING means that the train has left the crossing. Therefore, the state attribute train-position has one of the above five values at a given time or state here. Next, we simulate or actually execute the possible actions in the system and observe the changes in the state attributes in a way similar to that of executing statements in a program and observing the changes in the program variables. We can then construct the finite-state graph as described above and shown in Figure 4.1. Note that given a particular system to be specified, we can model it with the level of details required by our goal. In the railroad crossing example, each position of the train can be further divided into more precise numerical coordinates. This of course requires more states and transitions in the CTL structure, which in turn makes the analysis more complex. The state-graph construction is very important since the correctness of the model checking depends on correctly capturing the concurrent program to be checked in the state graph. This construction is not discussed in [Clarke, Emerson, and Sistla, 1986] but an algorithm for it can be easily implemented [Cheng et al., 1993; Zupan and Cheng, 1994b] (see chapters 10 and 12). We first formally define the CTL structure. 88 MODEL CHECKING OF FINITE-STATE SYSTEMS S 0 (GATE_UP, BEFORE_APPROACH) (GATE_DOWN, AFTER_CROSSING) (GATE_DOWN, CROSSING) (GATE_DOWN, NEAR_CROSSING) (GATE_UP, APPROACH) S 1 S 2 S 3 S 4 Figure 4.1 CTL structure for the railroad crossing system. CTL Structure: Formally, the CTL structure (state graph) is a triple, M = (S, R, P),where 1. S is a finite set of states, 2. R is a binary relation on S which gives the possible transitions between states, and 3. P assigns to each state the set of atomic propositions true in that state. The next step is to specify the specification or safety assertion in CTL. CTL consists of a set AP of atomic propositions, which can be attributes such as C1 (process 1 in critical section), program variable value C = 1 (variable C has value 1), or BEFORE-CROSSING in the railroad crossing scenario. Every atomic proposition is a CTL formula. More complex CTL formulas can be constructed using the operators NOT, AND, AX, EX, AU, and EU. The operators NOT and AND have their usual meanings. To define the remaining operators, we need to define a path as an infinite, directed sequence of states (some of which may be the same) in the CTL structure. The symbol X is the next-time operator. The formula AX f 1 means that f 1 holds in every immediate successor of the current program state. Alternatively, the formula EX f 1 means that f 1 holds in some immediate successor of the current program state. The symbol U is the until operator. The formula A[ f 1 U f 2 ] means that for every computation path there exists an initial prefix of the path such that f 2 holds at the CLARKE–EMERSON–SISTLA MODEL CHECKER 89 last state of the prefix and f 1 holds at all other states along the prefix. Alternatively, the formula E[ f 1 U f 2 ] means that for some computation path there exists an initial prefix of the path such that f 2 holds at the last state of the prefix and f 1 holds at all other states along the prefix. To simplify the specification, we use the following abbreviations. AF( f ) means A[True U f ]: f holds in the future along every path from the initial state s 0 ,so f is inevitable. EF( f ) means E[True U f ]: some path from the initial state s 0 exists that leads to a state at which f holds, so f potentially holds. EG( f ) means NOT AF(NOT f ): some path from the initial state s 0 exists on which f holds at every state. AG( f ) means NOT EF(NOT f ): f holds at every state on every path from the initial state s 0 ,so f holds globally. Figure 4.1 shows the finite-state graph of our simple railroad crossing system. Each state consists of two variables (gate-position, train-position). The initial state is s0. 4.2 CLARKE–EMERSON–SISTLA MODEL CHECKER The Clarke–Emerson–Sistla (CES) model checker can determine whether a for- mula f 0 written in CTL is true in a given CTL structure. It uses a compositional approach to analysis and hence operates in stages. The first stage checks all subfor- mulas of length 1 in f 0 , that is, all atomic propositions. These atomic propositions hold in states having labels that are identical to these propositions. The second stage checks all subformulas of length 2 in f 0 based on the results in stage 1, and labels each state with the subformulas that hold in that state, and so on. As a result, each state will be labeled with the set of subformulas of length less than or equal to i after the completion of the ith stage. At completion, the model checker will have checked the entire formula of length n. The following data structures and functions [Clarke, Emerson, and Sistla, 1986] to access the labels associated with each state. The variables arg1andarg2 refer to the first and second arguments of a binary temporal operator. The variable labeled[s][ f ] is true if state s is labeled with formula numbered f , false otherwise. The function addlabel(s, f, labeled) adds formula f to the current label of state s by modifying the array labeled. To simplify the input of CTL formulas and internal processing, we use prefix no- tation to write the formulas. Now the length of a formula is equal to the total number of operands and operators in it. Suppose that formula f is assigned an integer i.If f is unary (e.g., f = NOT f 1 ), then we assign the integers i +1 through i + length( f 1 ) to the subformulas of f 1 .If f is binary (e.g., f = AU f 1 f 2 ), then we assign the integers i + 1 through i + length( f 1 ) to the subformulas of f 1 and i + length( f 1 ) + 1 through i + length( f 1 ) +length( f 2 ) to the subformulas of f 2 . Using this assignment, in one pass through f , we can build two arrays, nf[length( f )] and sf[length( f )], where nf[i] is the ith subformula of f in the above numbering and sf[i] is the list of numbers assigned to the immediate subformulas of the i th formula. For example, if f = (AU (NOT CROSSING) GATE-DOWN), then nf and sf are 90 MODEL CHECKING OF FINITE-STATE SYSTEMS nf[1] (AU (NOT CROSSING) GATE-DOWN) sf[1] (2 4) nf[2] (NOT CROSSING) sf[2] (3) nf[3] CROSSING sf[3] nil nf[4] GATE-DOWN sf[4] nil. Therefore, we can determine in constant time the operator of a formula f and the numbers assigned to its arguments given f ’s number. This enables us to effi- ciently implement the function labelgraph. Instead of using the function labeled as in [Clarke, Emerson, and Sistla, 1986], we use the array labeled[][] and the initial ar- ray initlabeled[][], making the access and update faster. labeled[s][a] is true if state s is labeled with formula number a. To handle an arbitrary formula f , we apply the labelgraph function to each sub- formula of f , starting with the highest numbered (simplest) formula and working backwards. Note that the indices in the following C code start from 0 instead of 1 since arrays in C are indexed from 0. for (fi=flength; fi >= 1; fi ) labelgraph(fi,s,&correct); The following C function labelgraph( fi, s, b) determines whether fi holds in state s. Note that it can handle seven cases: fi is atomic or has one of the following operators (NOT, AND, AX, EX, AU, or EU). /*===========================================================================*/ /* function labelgraph */ /*===========================================================================*/ /* procedure labelgraph (fi,s,b) */ labelgraph (fi,s,b) short fi, s; Boolean *b; { short i; switch(nf[fi-1][0].opcode) { case atomic: atf(fi,s,b); break; case nt: ntf(fi,s,b); break; case ad: adf(fi,s,b); break; case ax: axf(fi,s,b); break; case ex: exf(fi,s,b); break; CLARKE–EMERSON–SISTLA MODEL CHECKER 91 case au: for (i=0; i <= numstates; i++) marked[i] = false; for (i=0; i <= numstates; i++) if (!marked[i]) auf(fi,s,b); break; case eu: euf(fi,s,b); break; } } /*labelgraph*/ The following recursive C function auf( fi, s, b) determines whether the formula fiwith an AU operator holds in state s. The code for initialization and for processing formulas with the other six operators is listed in section 4.5. /*=========================================================================*/ /* function auf */ /* In : fi = input formula number */ /* s = state of the transition graph at which f is to be proved */ /* Out : b = true if formula f is true at state s */ /* Description: */ /* Use DFS to determine whether (au arg1 arg2) is true in state s */ /*=========================================================================*/ /* procedure auf (fi,s,b) */ auf (fi,s,b) short fi, s; Boolean *b; { short a1, a2, s1; Boolean b1; a1 = sf[fi-1].arg1; a2 = sf[fi-1].arg2; *b = true; /* # # If s is marked, check to see if s is labeled with fi; return true # if it is, else false. # */ if (marked[s]) { if (labeled[s][fi-1]) *b = true; else *b = false; } 92 MODEL CHECKING OF FINITE-STATE SYSTEMS else /* # # If the state has not been visited (marked), mark it and check to see # if it is labeled with the argument 2. # */ { marked[s] = true; if (labeled[s][a2-1] || initlabeled(s,nf[a2-1])) { addlabel(s,fi,labeled); *b = true; } else if (!(labeled[s][a1-1] || initlabeled(s,nf[a1-1]))) { *b = false; } else { /* # # For all successor states of s, check to see if f is true. # */ s1=0; while (*b && (s1 <= numstates)) { if ((s != s1) && (e[s][s1] == 1)) { auf(fi,s1,&b1); if (!b1) *b = false; } s1=s1+1; } if (*b) addlabel(s,fi,labeled); } } } /*auf*/ The function auf basically performs a depth-first search of the CTL structure starting from state s. It checks whether each path from s has a prefix with states labeled with the first argument of AU and eventually leading to a state labeled with the second argument of AU. It does so by labeling state s and the successor states of s that satisfy the formula fi, and then calling the function itself recursively to perform the same check. As soon as a state that is not labeled with the first argument is reached prior to reaching a state labeled with the second argument, the function returns false. APPLICATIONS 93 4.2.1 Analysis Complexity If the states in the CTL structure are correctly labeled with arg1andarg2of f , func- tion auf requires time O(number of states in CTL structure+number of transitions). Since each pass through the main loop takes time O(number of states in CTL structure + number of transitions), the entire model checker requires O(length( f ) ∗ , (number of states in CTL structure + number of transitions)). 4.3 EXTENSIONS TO CTL Extensions to CTL are needed to handle the verification of correctness along fair ex- ecution sequences and to specify absolute time instead of relative ordering of events. Here, we discuss how to extend CTL to handle fairness properties. For example, with a real-time rule-based program, we would like to consider the execution paths (se- quences of rule firings) in which enabled rules are equally likely to be selected for execution, that is, a fair scheduler is assumed. Similarly, with a collection of con- current processes, we would like to consider only the computation paths in which each process is executed infinitely often. In general, a fairness condition asserts that requests for service are granted sufficiently often [Garbay et al., 1980]. Many def- initions exist of “requests” and “sufficiently often.” Here, we say a path is fair if enabled events in each state along the path are equally likely to happen. CTL cannot express the correctness of fair executions. More precisely, the prop- erty that some proposition P should eventually hold on all fair executions cannot be specified in CTL. To handle fairness while maintaining an efficient model checking algorithm, we modify the semantics of CTL [Clarke, Emerson, and Sistla, 1986] to yield a new logic called CTL-F. It has the same syntax but a structure is now a 4-tuple (S, R, P, F ),whereS, R, P have the same meaning as described earlier and F is a collection of predicates on S. A path is F-fair iff for each g ⊆ F, infinitely many states on the path satisfy predicate g. In CTL-F, all path quantifiers range over fair paths but the semantics remain the same as in CTL. For any given finite structure M = (S, R, P), collection F = G 1 , ,G n of subsets of S,andstates 0 ∈ S, there exists an F-fair path in M starting at s 0 iff there exists a strongly connected compo- nent C of the graph of M such that (1) a finite path exists from s 0 to a state t ∈ C and (2) for each G i a state t i ∈ C ∩ G i exists. 4.4 APPLICATIONS One application of a model checker is to determine whether a program will termi- nate, that is, reach a fixed point, under all conditions. For instance, the module mcf in [Browne, Cheng, and Mok, 1988] (described in chapter 10) is a temporal logic model checker based on the Clarke–Emerson–Sistla algorithm for checking the sat- isfiability of temporal logic formulas written in CTL. Our model checker assumes that strong fairness is observed by the scheduler, that is, rules that are enabled in- finitely often will eventually fire. Under this assumption, a cycle in the state space 94 MODEL CHECKING OF FINITE-STATE SYSTEMS graph that has at least one edge exiting from it is sufficient to allow the program to reach a fixed point in a finite number of iterations. (The program will leave the states in the cycle because the rule associated with the exit edge must eventually fire.) How- ever, the model checker will warn the designer that the program may require a finite but unbounded number of iterations to reach a fixed point. 4.4.1 Analysis Example We now describe how a model checker can be applied to determine whether a rule- based program written in the EQL (equational logic) language (described in chapter 10) will always terminate. The purpose of the following program is to determine whether an object is detected at each monitor-decide cycle. The system consists of two processes and an external alarm clock which invokes the program by periodically setting the variable wakeup to true. (* Example EQL Program *) PROGRAM distributed; CONST false = 0; true = 1; a=0; b=1; VAR synca, syncb, wakeup, objectdetected : BOOLEAN; arbiter : INTEGER; INPUTVAR sensora, sensorb : INTEGER; INIT synca := true, syncb := true, wakeup := true, objectdetected := false, arbiter := a RULES (* process A *) objectdetected := true ! synca := false IF (sensora = 1) AND (arbiter = a) AND (synca = true) [] objectdetected := false ! synca := false IF (sensora = 0) AND (arbiter = a) AND (synca = true) [] arbiter := b ! synca := true ! wakeup := false IF (arbiter = a) AND (synca = false) AND (wakeup = true) (* process B *) [] objectdetected := true ! syncb := false IF (sensorb = 1) AND (arbiter = b) AND (syncb = true) APPLICATIONS 95 AND (wakeup = true) [] objectdetected := false ! syncb := false IF (sensorb = 0) AND (arbiter = b) AND (syncb = true) AND (wakeup = true) [] arbiter := a ! syncb := true ! wakeup := false IF (arbiter = b) AND (syncb = false) AND (wakeup = true) TRACE objectdetected PRINT synca, syncb, wakeup, objectdetected, arbiter, sensora, sensorb END. In this example, the input variables are sensora and sensorb and the program variables are objectdetected, synca, syncb, arbiter,andwakeup. The symbol [] is a rule separator and the symbol ! separates parallel assignments within the same rule. Each process runs independently of the other. An alarm clock external to the pro- gram is used to invoke the processes after some specified period of time. A rule is fired by executing the assignment statement when the enabling condition becomes true. In this example, the shared variable arbiter is used as a control-synchronization variable which enforces mutually exclusive access to shared variables such as object- detected by different processes. The variables synca and syncb are used as control- synchronization variables within process A and process B, respectively. Note that for each process, at most two rules will be fired before control is transferred to the other process. Initially, process A is given mutually exclusive access to variables objectdetected and synca. The EQL program with the initial input values can be represented by a finite state– space graph. An automatic graph generator for this purpose is available [Cheng et al., 1993]. Finite State Space Graph Corresponding to Input Program: state next states rule # 1 2 3 4 5 6 0: 100000 1: 112111 2: 222222 State Labels: state (synca, syncb, wakeup, objectdetected, arbiter, sensora, sensorb) 0 1110010 1 0111010 2 1101110 Next, we write the CTL temporal logic formula for checking whether this program will reach a fixed point in finite time from the initial state corresponding to the initial [...]... 108 MODEL CHECKING OF FINITE-STATE SYSTEMS */ if (f[fi-1].opcode != atomic) { do { j = j + 1; i = i + 1; nf[fi-1][j-1].op[0] = f[i-1].op[0]; nf[fi-1][j-1].op[1] = f[i-1].op[1]; nf[fi-1][j-1].opcode = f[i-1].opcode; nf[fi-1][j-1].p = f[i-1].p; } while (!(f[i-1].p . interchangeably. 86 Real-Time Systems: Scheduling, Analysis, and Verification. Albert M. K. Cheng Copyright ¶ 2002 John Wiley & Sons, Inc. ISBN: 0-4 7 1-1 840 6-3 SYSTEM. true; if (labeled[s][a 2-1 ] || initlabeled(s,nf[a 2-1 ])) { addlabel(s,fi,labeled); *b = true; } else if (!(labeled[s][a 1-1 ] || initlabeled(s,nf[a 1-1 ]))) { *b = false; } else